00001 #ifndef BM__H__INCLUDED__
00002 #define BM__H__INCLUDED__
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032 #ifndef BM_NO_STL
00033 # include <iterator>
00034 #endif
00035
00036 #ifdef _MSC_VER
00037 #pragma warning( push )
00038 #pragma warning( disable : 4311 4312 4127)
00039 #endif
00040
00041
00042 #ifdef BMSSE42OPT
00043 # ifdef BM64OPT
00044 # undef BM64OPT
00045 # define BM64_SSE4
00046 # endif
00047 # undef BMSSE2OPT
00048 #endif
00049
00050
00051 #include "bmconst.h"
00052 #include "bmdef.h"
00053
00054
00055 #ifdef BMSSE42OPT
00056 # define BMVECTOPT
00057 # include "bmsse4.h"
00058 #endif
00059
00060 #ifdef BMSSE2OPT
00061 # undef BM64OPT
00062 # define BMVECTOPT
00063 # include "bmsse2.h"
00064 #endif
00065
00066
00067 #include "bmfwd.h"
00068 #include "bmfunc.h"
00069 #include "encoding.h"
00070 #include "bmalloc.h"
00071 #include "bmblocks.h"
00072
00073 namespace bm
00074 {
00075
00076
00077 #ifdef BMCOUNTOPT
00078
00079 # define BMCOUNT_INC ++count_;
00080 # define BMCOUNT_DEC --count_;
00081 # define BMCOUNT_VALID(x) count_is_valid_ = x;
00082 # define BMCOUNT_SET(x) count_ = x; count_is_valid_ = true;
00083 # define BMCOUNT_ADJ(x) if (x) ++count_; else --count_;
00084
00085 #else
00086
00087 # define BMCOUNT_INC
00088 # define BMCOUNT_DEC
00089 # define BMCOUNT_VALID(x)
00090 # define BMCOUNT_SET(x)
00091 # define BMCOUNT_ADJ(x)
00092
00093 #endif
00094
00095
00096
00097
00098
00099
00100
00101
00102
00103
00104
00105
00106
00107
00108
00109
00110
00111
00112
00113
00114
00115
00116
00117
00118
00119 template<class Alloc>
00120 class bvector
00121 {
00122 public:
00123
00124 typedef Alloc allocator_type;
00125 typedef blocks_manager<Alloc> blocks_manager_type;
00126
00127 typedef bm::id_t size_type;
00128
00129
00130 struct statistics : public bv_statistics
00131 {};
00132
00133
00134
00135
00136
00137
00138
00139
00140 class reference
00141 {
00142 public:
00143 reference(bvector<Alloc>& bv, bm::id_t position)
00144 : bv_(bv),
00145 position_(position)
00146 {}
00147
00148 reference(const reference& ref)
00149 : bv_(ref.bv_),
00150 position_(ref.position_)
00151 {
00152 bv_.set(position_, ref.bv_.get_bit(position_));
00153 }
00154
00155 operator bool() const
00156 {
00157 return bv_.get_bit(position_);
00158 }
00159
00160 const reference& operator=(const reference& ref) const
00161 {
00162 bv_.set(position_, (bool)ref);
00163 return *this;
00164 }
00165
00166 const reference& operator=(bool value) const
00167 {
00168 bv_.set(position_, value);
00169 return *this;
00170 }
00171
00172 bool operator==(const reference& ref) const
00173 {
00174 return bool(*this) == bool(ref);
00175 }
00176
00177
00178 const reference& operator&=(bool value) const
00179 {
00180 bv_.set_bit_and(position_, value);
00181 return *this;
00182 }
00183
00184
00185 const reference& operator|=(bool value) const
00186 {
00187 if (value != bv_.get_bit(position_))
00188 {
00189 bv_.set_bit(position_);
00190 }
00191 return *this;
00192 }
00193
00194
00195 const reference& operator^=(bool value) const
00196 {
00197 bv_.set(position_, value != bv_.get_bit(position_));
00198 return *this;
00199 }
00200
00201
00202 bool operator!() const
00203 {
00204 return !bv_.get_bit(position_);
00205 }
00206
00207
00208 bool operator~() const
00209 {
00210 return !bv_.get_bit(position_);
00211 }
00212
00213
00214 reference& flip()
00215 {
00216 bv_.flip(position_);
00217 return *this;
00218 }
00219
00220 private:
00221 bvector<Alloc>& bv_;
00222 bm::id_t position_;
00223 };
00224
00225 typedef bool const_reference;
00226
00227
00228
00229
00230
00231 class iterator_base
00232 {
00233 friend class bvector;
00234 public:
00235 iterator_base() : bv_(0), position_(bm::id_max), block_(0) {}
00236
00237 bool operator==(const iterator_base& it) const
00238 {
00239 return (position_ == it.position_) && (bv_ == it.bv_);
00240 }
00241
00242 bool operator!=(const iterator_base& it) const
00243 {
00244 return ! operator==(it);
00245 }
00246
00247 bool operator < (const iterator_base& it) const
00248 {
00249 return position_ < it.position_;
00250 }
00251
00252 bool operator <= (const iterator_base& it) const
00253 {
00254 return position_ <= it.position_;
00255 }
00256
00257 bool operator > (const iterator_base& it) const
00258 {
00259 return position_ > it.position_;
00260 }
00261
00262 bool operator >= (const iterator_base& it) const
00263 {
00264 return position_ >= it.position_;
00265 }
00266
00267
00268
00269
00270
00271
00272 bool valid() const
00273 {
00274 return position_ != bm::id_max;
00275 }
00276
00277
00278
00279
00280
00281 void invalidate()
00282 {
00283 position_ = bm::id_max;
00284 }
00285
00286 public:
00287
00288
00289 struct bitblock_descr
00290 {
00291 const bm::word_t* ptr;
00292 unsigned bits[32];
00293 unsigned idx;
00294 unsigned cnt;
00295 bm::id_t pos;
00296 };
00297
00298
00299 struct dgap_descr
00300 {
00301 const gap_word_t* ptr;
00302 gap_word_t gap_len;
00303 };
00304
00305 protected:
00306 bm::bvector<Alloc>* bv_;
00307 bm::id_t position_;
00308 const bm::word_t* block_;
00309 unsigned block_type_;
00310 unsigned block_idx_;
00311
00312
00313 union block_descr
00314 {
00315 bitblock_descr bit_;
00316 dgap_descr gap_;
00317 } bdescr_;
00318 };
00319
00320
00321
00322
00323
00324
00325
00326
00327
00328
00329
00330
00331
00332
00333
00334
00335 class insert_iterator
00336 {
00337 public:
00338 #ifndef BM_NO_STL
00339 typedef std::output_iterator_tag iterator_category;
00340 #endif
00341 typedef unsigned value_type;
00342 typedef void difference_type;
00343 typedef void pointer;
00344 typedef void reference;
00345
00346 insert_iterator(bvector<Alloc>& bvect)
00347 : bvect_(bvect),
00348 max_bit_(bvect.size())
00349 {
00350 }
00351
00352 insert_iterator& operator=(bm::id_t n)
00353 {
00354 BM_ASSERT(n < bm::id_max);
00355
00356 if (n >= max_bit_)
00357 {
00358 max_bit_ = n;
00359 if (n >= bvect_.size())
00360 {
00361 bvect_.resize(n + 1);
00362 }
00363 }
00364
00365 bvect_.set(n);
00366 return *this;
00367 }
00368
00369
00370 insert_iterator& operator*() { return *this; }
00371
00372 insert_iterator& operator++() { return *this; }
00373
00374 insert_iterator& operator++(int) { return *this; }
00375
00376 protected:
00377 bm::bvector<Alloc>& bvect_;
00378 bm::id_t max_bit_;
00379 };
00380
00381
00382
00383
00384
00385 class enumerator : public iterator_base
00386 {
00387 public:
00388 #ifndef BM_NO_STL
00389 typedef std::input_iterator_tag iterator_category;
00390 #endif
00391 typedef unsigned value_type;
00392 typedef unsigned difference_type;
00393 typedef unsigned* pointer;
00394 typedef unsigned& reference;
00395
00396 public:
00397 enumerator() : iterator_base() {}
00398 enumerator(const bvector<Alloc>* bvect, int position)
00399 : iterator_base()
00400 {
00401 this->bv_ = const_cast<bvector<Alloc>*>(bvect);
00402 if (position == 0)
00403 {
00404 go_first();
00405 }
00406 else
00407 {
00408 this->invalidate();
00409 }
00410 }
00411
00412 bm::id_t operator*() const
00413 {
00414 return this->position_;
00415 }
00416
00417 bm::id_t value() const
00418 {
00419 return this->position_;
00420 }
00421
00422 enumerator& operator++()
00423 {
00424 return this->go_up();
00425 }
00426
00427 enumerator operator++(int)
00428 {
00429 enumerator tmp = *this;
00430 this->go_up();
00431 return tmp;
00432 }
00433
00434
00435 void go_first()
00436 {
00437 BM_ASSERT(this->bv_);
00438
00439 #ifdef BMCOUNTOPT
00440 if (this->bv_->count_is_valid_ &&
00441 this->bv_->count_ == 0)
00442 {
00443 this->invalidate();
00444 return;
00445 }
00446 #endif
00447
00448 blocks_manager_type* bman = &(this->bv_->blockman_);
00449 bm::word_t*** blk_root = bman->blocks_root();
00450
00451 this->block_idx_ = this->position_= 0;
00452 unsigned i, j;
00453
00454 for (i = 0; i < bman->top_block_size(); ++i)
00455 {
00456 bm::word_t** blk_blk = blk_root[i];
00457
00458 if (blk_blk == 0)
00459 {
00460 this->block_idx_ += bm::set_array_size;
00461 this->position_ += bm::bits_in_array;
00462 continue;
00463 }
00464
00465
00466 for (j = 0; j < bm::set_array_size; ++j,++(this->block_idx_))
00467 {
00468 this->block_ = blk_blk[j];
00469
00470 if (this->block_ == 0)
00471 {
00472 this->position_ += bits_in_block;
00473 continue;
00474 }
00475
00476 if (BM_IS_GAP(this->block_))
00477 {
00478 this->block_type_ = 1;
00479 if (search_in_gapblock())
00480 {
00481 return;
00482 }
00483 }
00484 else
00485 {
00486 this->block_type_ = 0;
00487 if (search_in_bitblock())
00488 {
00489 return;
00490 }
00491 }
00492
00493 }
00494
00495 }
00496
00497 this->invalidate();
00498 }
00499
00500 enumerator& go_up()
00501 {
00502
00503 ++this->position_;
00504 typedef typename iterator_base::block_descr block_descr_type;
00505
00506 block_descr_type* bdescr = &(this->bdescr_);
00507
00508 switch (this->block_type_)
00509 {
00510 case 0:
00511 {
00512
00513
00514
00515
00516 unsigned idx = ++(bdescr->bit_.idx);
00517 if (idx < bdescr->bit_.cnt)
00518 {
00519 this->position_ = bdescr->bit_.pos +
00520 bdescr->bit_.bits[idx];
00521 return *this;
00522 }
00523 this->position_ += 31 - bdescr->bit_.bits[--idx];
00524
00525 const bm::word_t* pend = this->block_ + bm::set_block_size;
00526
00527 while (++(bdescr->bit_.ptr) < pend)
00528 {
00529 bm::word_t w = *(bdescr->bit_.ptr);
00530 if (w)
00531 {
00532 bdescr->bit_.idx = 0;
00533 bdescr->bit_.pos = this->position_;
00534 bdescr->bit_.cnt = bm::bit_list_4(w, bdescr->bit_.bits);
00535 this->position_ += bdescr->bit_.bits[0];
00536 return *this;
00537 }
00538 else
00539 {
00540 this->position_ += 32;
00541 }
00542 }
00543
00544 }
00545 break;
00546
00547 case 1:
00548 {
00549 if (--(bdescr->gap_.gap_len))
00550 {
00551 return *this;
00552 }
00553
00554
00555 if (*(bdescr->gap_.ptr) == bm::gap_max_bits - 1)
00556 {
00557 break;
00558 }
00559 gap_word_t prev = *(bdescr->gap_.ptr);
00560 unsigned int val = *(++(bdescr->gap_.ptr));
00561
00562 this->position_ += val - prev;
00563
00564
00565 if (*(bdescr->gap_.ptr) == bm::gap_max_bits - 1)
00566 {
00567 break;
00568 }
00569 prev = *(bdescr->gap_.ptr);
00570 val = *(++(bdescr->gap_.ptr));
00571 bdescr->gap_.gap_len = (gap_word_t)val - prev;
00572 return *this;
00573 }
00574
00575 default:
00576 BM_ASSERT(0);
00577
00578 }
00579
00580
00581
00582
00583 ++(this->block_idx_);
00584 unsigned i = this->block_idx_ >> bm::set_array_shift;
00585 unsigned top_block_size = this->bv_->blockman_.top_block_size();
00586 for (; i < top_block_size; ++i)
00587 {
00588 bm::word_t** blk_blk = this->bv_->blockman_.blocks_root()[i];
00589 if (blk_blk == 0)
00590 {
00591 this->block_idx_ += bm::set_array_size;
00592 this->position_ += bm::bits_in_array;
00593 continue;
00594 }
00595
00596 unsigned j = this->block_idx_ & bm::set_array_mask;
00597
00598 for(; j < bm::set_array_size; ++j, ++(this->block_idx_))
00599 {
00600 this->block_ = blk_blk[j];
00601
00602 if (this->block_ == 0)
00603 {
00604 this->position_ += bm::bits_in_block;
00605 continue;
00606 }
00607
00608 if (BM_IS_GAP(this->block_))
00609 {
00610 this->block_type_ = 1;
00611 if (search_in_gapblock())
00612 {
00613 return *this;
00614 }
00615 }
00616 else
00617 {
00618 this->block_type_ = 0;
00619 if (search_in_bitblock())
00620 {
00621 return *this;
00622 }
00623 }
00624
00625
00626 }
00627
00628 }
00629
00630
00631 this->invalidate();
00632 return *this;
00633 }
00634
00635
00636 private:
00637 bool search_in_bitblock()
00638 {
00639 BM_ASSERT(this->block_type_ == 0);
00640
00641 typedef typename iterator_base::block_descr block_descr_type;
00642 block_descr_type* bdescr = &(this->bdescr_);
00643
00644
00645 bdescr->bit_.ptr = this->block_;
00646
00647 const word_t* ptr_end = this->block_ + bm::set_block_size;
00648
00649 do
00650 {
00651 register bm::word_t w = *(bdescr->bit_.ptr);
00652
00653 if (w)
00654 {
00655 bdescr->bit_.idx = 0;
00656 bdescr->bit_.pos = this->position_;
00657 bdescr->bit_.cnt =
00658 bm::bit_list_4(w, bdescr->bit_.bits);
00659 this->position_ += bdescr->bit_.bits[0];
00660
00661 return true;
00662 }
00663 else
00664 {
00665 this->position_ += 32;
00666 }
00667
00668 }
00669 while (++(bdescr->bit_.ptr) < ptr_end);
00670
00671 return false;
00672 }
00673
00674 bool search_in_gapblock()
00675 {
00676 BM_ASSERT(this->block_type_ == 1);
00677
00678 typedef typename iterator_base::block_descr block_descr_type;
00679 block_descr_type* bdescr = &(this->bdescr_);
00680
00681 bdescr->gap_.ptr = BMGAP_PTR(this->block_);
00682 unsigned bitval = *(bdescr->gap_.ptr) & 1;
00683
00684 ++(bdescr->gap_.ptr);
00685
00686 for (;true;)
00687 {
00688 register unsigned val = *(bdescr->gap_.ptr);
00689
00690 if (bitval)
00691 {
00692 gap_word_t* first = BMGAP_PTR(this->block_) + 1;
00693 if (bdescr->gap_.ptr == first)
00694 {
00695 bdescr->gap_.gap_len = (gap_word_t)val + 1;
00696 }
00697 else
00698 {
00699 bdescr->gap_.gap_len =
00700 (gap_word_t)(val - *(bdescr->gap_.ptr-1));
00701 }
00702
00703 return true;
00704 }
00705 this->position_ += val + 1;
00706
00707 if (val == bm::gap_max_bits - 1)
00708 {
00709 break;
00710 }
00711
00712 bitval ^= 1;
00713 ++(bdescr->gap_.ptr);
00714
00715 }
00716
00717 return false;
00718 }
00719
00720 };
00721
00722
00723
00724
00725
00726
00727
00728
00729
00730
00731 class counted_enumerator : public enumerator
00732 {
00733 public:
00734 #ifndef BM_NO_STL
00735 typedef std::input_iterator_tag iterator_category;
00736 #endif
00737 counted_enumerator() : bit_count_(0){}
00738
00739 counted_enumerator(const enumerator& en)
00740 : enumerator(en)
00741 {
00742 if (this->valid())
00743 bit_count_ = 1;
00744 }
00745
00746 counted_enumerator& operator=(const enumerator& en)
00747 {
00748 enumerator* me = this;
00749 *me = en;
00750 if (this->valid())
00751 this->bit_count_ = 1;
00752 return *this;
00753 }
00754
00755 counted_enumerator& operator++()
00756 {
00757 this->go_up();
00758 if (this->valid())
00759 ++(this->bit_count_);
00760 return *this;
00761 }
00762
00763 counted_enumerator operator++(int)
00764 {
00765 counted_enumerator tmp(*this);
00766 this->go_up();
00767 if (this->valid())
00768 ++bit_count_;
00769 return tmp;
00770 }
00771
00772
00773
00774
00775
00776
00777 bm::id_t count() const { return bit_count_; }
00778
00779 private:
00780 bm::id_t bit_count_;
00781 };
00782
00783 friend class iterator_base;
00784 friend class enumerator;
00785
00786 public:
00787
00788 #ifdef BMCOUNTOPT
00789 bvector(strategy strat = BM_BIT,
00790 const gap_word_t* glevel_len = bm::gap_len_table<true>::_len,
00791 size_type bv_size = bm::id_max,
00792 const Alloc& alloc = Alloc())
00793 : count_(0),
00794 count_is_valid_(true),
00795 blockman_(glevel_len, bv_size, alloc),
00796 new_blocks_strat_(strat),
00797 size_(bv_size)
00798 {}
00799
00800 bvector(size_type bv_size,
00801 bm::strategy strat = BM_BIT,
00802 const gap_word_t* glevel_len = bm::gap_len_table<true>::_len,
00803 const Alloc& alloc = Alloc())
00804 : count_(0),
00805 count_is_valid_(true),
00806 blockman_(glevel_len, bv_size, alloc),
00807 new_blocks_strat_(strat),
00808 size_(bv_size)
00809 {}
00810
00811
00812 bvector(const bm::bvector<Alloc>& bvect)
00813 : count_(bvect.count_),
00814 count_is_valid_(bvect.count_is_valid_),
00815 blockman_(bvect.blockman_),
00816 new_blocks_strat_(bvect.new_blocks_strat_),
00817 size_(bvect.size_)
00818 {}
00819
00820 #else
00821
00822
00823
00824
00825
00826
00827
00828
00829
00830
00831
00832
00833
00834
00835
00836
00837
00838
00839 bvector(strategy strat = BM_BIT,
00840 const gap_word_t* glevel_len = bm::gap_len_table<true>::_len,
00841 size_type bv_size = bm::id_max,
00842 const Alloc& alloc = Alloc())
00843 : blockman_(glevel_len, bv_size, alloc),
00844 new_blocks_strat_(strat),
00845 size_(bv_size)
00846 {}
00847
00848
00849
00850
00851 bvector(size_type bv_size,
00852 strategy strat = BM_BIT,
00853 const gap_word_t* glevel_len = bm::gap_len_table<true>::_len,
00854 const Alloc& alloc = Alloc())
00855 : blockman_(glevel_len, bv_size, alloc),
00856 new_blocks_strat_(strat),
00857 size_(bv_size)
00858 {}
00859
00860
00861 bvector(const bvector<Alloc>& bvect)
00862 : blockman_(bvect.blockman_),
00863 new_blocks_strat_(bvect.new_blocks_strat_),
00864 size_(bvect.size_)
00865 {}
00866
00867 #endif
00868
00869 bvector& operator=(const bvector<Alloc>& bvect)
00870 {
00871 clear(true);
00872 resize(bvect.size());
00873 bit_or(bvect);
00874 return *this;
00875 }
00876
00877 reference operator[](bm::id_t n)
00878 {
00879 BM_ASSERT(n < size_);
00880 return reference(*this, n);
00881 }
00882
00883
00884 bool operator[](bm::id_t n) const
00885 {
00886 BM_ASSERT(n < size_);
00887 return get_bit(n);
00888 }
00889
00890 void operator &= (const bvector<Alloc>& bvect)
00891 {
00892 bit_and(bvect);
00893 }
00894
00895 void operator ^= (const bvector<Alloc>& bvect)
00896 {
00897 bit_xor(bvect);
00898 }
00899
00900 void operator |= (const bvector<Alloc>& bvect)
00901 {
00902 bit_or(bvect);
00903 }
00904
00905 void operator -= (const bvector<Alloc>& bvect)
00906 {
00907 bit_sub(bvect);
00908 }
00909
00910 bool operator < (const bvector<Alloc>& bvect) const
00911 {
00912 return compare(bvect) < 0;
00913 }
00914
00915 bool operator <= (const bvector<Alloc>& bvect) const
00916 {
00917 return compare(bvect) <= 0;
00918 }
00919
00920 bool operator > (const bvector<Alloc>& bvect) const
00921 {
00922 return compare(bvect) > 0;
00923 }
00924
00925 bool operator >= (const bvector<Alloc>& bvect) const
00926 {
00927 return compare(bvect) >= 0;
00928 }
00929
00930 bool operator == (const bvector<Alloc>& bvect) const
00931 {
00932 return compare(bvect) == 0;
00933 }
00934
00935 bool operator != (const bvector<Alloc>& bvect) const
00936 {
00937 return compare(bvect) != 0;
00938 }
00939
00940 bvector<Alloc> operator~() const
00941 {
00942 return bvector<Alloc>(*this).invert();
00943 }
00944
00945 Alloc get_allocator() const
00946 {
00947 return blockman_.get_allocator();
00948 }
00949
00950
00951
00952
00953
00954
00955
00956
00957 bool set_bit(bm::id_t n, bool val = true)
00958 {
00959 BM_ASSERT(n < size_);
00960 return set_bit_no_check(n, val);
00961 }
00962
00963
00964
00965
00966
00967
00968
00969 bool set_bit_and(bm::id_t n, bool val = true)
00970 {
00971 BM_ASSERT(n < size_);
00972 return and_bit_no_check(n, val);
00973 }
00974
00975
00976
00977
00978
00979
00980
00981
00982 bool set_bit_conditional(bm::id_t n, bool val, bool condition)
00983 {
00984 BM_ASSERT(n < size_);
00985 if (val == condition) return false;
00986 return set_bit_conditional_impl(n, val, condition);
00987 }
00988
00989
00990
00991
00992
00993
00994
00995
00996 bvector<Alloc>& set(bm::id_t n, bool val = true)
00997 {
00998 set_bit(n, val);
00999 return *this;
01000 }
01001
01002
01003
01004
01005
01006
01007
01008 bvector<Alloc>& set()
01009 {
01010 BMCOUNT_VALID(false)
01011 set_range(0, size_ - 1, true);
01012 return *this;
01013 }
01014
01015
01016
01017
01018
01019
01020
01021
01022
01023
01024
01025
01026
01027 bvector<Alloc>& set_range(bm::id_t left,
01028 bm::id_t right,
01029 bool value = true);
01030
01031
01032
01033 insert_iterator inserter()
01034 {
01035 return insert_iterator(*this);
01036 }
01037
01038
01039
01040
01041
01042
01043 void clear_bit(bm::id_t n)
01044 {
01045 set(n, false);
01046 }
01047
01048
01049
01050
01051
01052
01053
01054
01055 void clear(bool free_mem = false)
01056 {
01057 blockman_.set_all_zero(free_mem);
01058 BMCOUNT_SET(0);
01059 }
01060
01061
01062
01063
01064
01065 bvector<Alloc>& reset()
01066 {
01067 clear();
01068 return *this;
01069 }
01070
01071
01072
01073
01074
01075
01076 bm::id_t count() const;
01077
01078
01079
01080
01081 size_type capacity() const
01082 {
01083 return blockman_.capacity();
01084 }
01085
01086
01087
01088
01089 size_type size() const
01090 {
01091 return size_;
01092 }
01093
01094
01095
01096
01097
01098 void resize(size_type new_size);
01099
01100
01101
01102
01103
01104
01105
01106 unsigned count_blocks(unsigned* arr) const
01107 {
01108 bm::word_t*** blk_root = blockman_.get_rootblock();
01109 typename blocks_manager_type::block_count_arr_func func(blockman_, &(arr[0]));
01110 for_each_nzblock(blk_root, blockman_.effective_top_block_size(),
01111 func);
01112 return func.last_block();
01113 }
01114
01115
01116
01117
01118
01119
01120
01121
01122
01123
01124 bm::id_t count_range(bm::id_t left,
01125 bm::id_t right,
01126 unsigned* block_count_arr=0) const;
01127
01128
01129 bm::id_t recalc_count()
01130 {
01131 BMCOUNT_VALID(false)
01132 return count();
01133 }
01134
01135
01136
01137
01138
01139
01140
01141
01142 void forget_count()
01143 {
01144 BMCOUNT_VALID(false)
01145 }
01146
01147
01148
01149
01150 bvector<Alloc>& invert();
01151
01152
01153
01154
01155
01156
01157
01158 bool get_bit(bm::id_t n) const;
01159
01160
01161
01162
01163
01164
01165 bool test(bm::id_t n) const
01166 {
01167 return get_bit(n);
01168 }
01169
01170
01171
01172
01173
01174 bool any() const
01175 {
01176 #ifdef BMCOUNTOPT
01177 if (count_is_valid_ && count_) return true;
01178 #endif
01179
01180 word_t*** blk_root = blockman_.get_rootblock();
01181 if (!blk_root)
01182 return false;
01183 typename blocks_manager_type::block_any_func func(blockman_);
01184 return for_each_nzblock_if(blk_root,
01185 blockman_.effective_top_block_size(),
01186 func);
01187 }
01188
01189
01190
01191
01192 bool none() const
01193 {
01194 return !any();
01195 }
01196
01197
01198
01199
01200
01201 bvector<Alloc>& flip(bm::id_t n)
01202 {
01203 set(n, !get_bit(n));
01204 return *this;
01205 }
01206
01207
01208
01209
01210
01211 bvector<Alloc>& flip()
01212 {
01213 return invert();
01214 }
01215
01216
01217
01218 void swap(bvector<Alloc>& bv)
01219 {
01220 if (this != &bv)
01221 {
01222 blockman_.swap(bv.blockman_);
01223 bm::xor_swap(size_,bv.size_);
01224 #ifdef BMCOUNTOPT
01225 BMCOUNT_VALID(false)
01226 bv.recalc_count();
01227 #endif
01228 }
01229 }
01230
01231
01232
01233
01234
01235
01236
01237
01238 bm::id_t get_first() const { return check_or_next(0); }
01239
01240
01241
01242
01243
01244
01245
01246
01247 bm::id_t get_next(bm::id_t prev) const
01248 {
01249 return (++prev == bm::id_max) ? 0 : check_or_next(prev);
01250 }
01251
01252
01253
01254
01255
01256
01257
01258
01259 bm::id_t extract_next(bm::id_t prev)
01260 {
01261 return (++prev == bm::id_max) ? 0 : check_or_next_extract(prev);
01262 }
01263
01264
01265
01266
01267
01268
01269
01270
01271
01272
01273
01274
01275
01276 void calc_stat(struct bm::bvector<Alloc>::statistics* st) const;
01277
01278
01279
01280
01281
01282 bm::bvector<Alloc>& bit_or(const bm::bvector<Alloc>& vect)
01283 {
01284 BMCOUNT_VALID(false);
01285 combine_operation(vect, BM_OR);
01286 return *this;
01287 }
01288
01289
01290
01291
01292
01293 bm::bvector<Alloc>& bit_and(const bm::bvector<Alloc>& vect)
01294 {
01295 BMCOUNT_VALID(false);
01296 combine_operation(vect, BM_AND);
01297 return *this;
01298 }
01299
01300
01301
01302
01303
01304 bm::bvector<Alloc>& bit_xor(const bm::bvector<Alloc>& vect)
01305 {
01306 BMCOUNT_VALID(false);
01307 combine_operation(vect, BM_XOR);
01308 return *this;
01309 }
01310
01311
01312
01313
01314
01315 bm::bvector<Alloc>& bit_sub(const bm::bvector<Alloc>& vect)
01316 {
01317 BMCOUNT_VALID(false);
01318 combine_operation(vect, BM_SUB);
01319 return *this;
01320 }
01321
01322
01323
01324
01325
01326
01327
01328 void set_new_blocks_strat(strategy strat)
01329 {
01330 new_blocks_strat_ = strat;
01331 }
01332
01333
01334
01335
01336
01337
01338
01339 strategy get_new_blocks_strat() const
01340 {
01341 return new_blocks_strat_;
01342 }
01343
01344
01345
01346
01347
01348
01349
01350 enum optmode
01351 {
01352 opt_free_0 = 1,
01353 opt_free_01 = 2,
01354 opt_compress = 3
01355 };
01356
01357
01358
01359
01360
01361
01362
01363
01364
01365
01366
01367
01368
01369 void optimize(bm::word_t* temp_block = 0,
01370 optmode opt_mode = opt_compress,
01371 statistics* stat = 0);
01372
01373
01374
01375
01376
01377
01378
01379
01380 void optimize_gap_size();
01381
01382
01383
01384
01385
01386
01387
01388
01389 void set_gap_levels(const gap_word_t* glevel_len);
01390
01391
01392
01393
01394
01395
01396
01397
01398 int compare(const bvector<Alloc>& bvect) const;
01399
01400
01401
01402
01403
01404
01405
01406
01407
01408
01409
01410
01411 bm::word_t* allocate_tempblock() const
01412 {
01413 blocks_manager_type* bm =
01414 const_cast<blocks_manager_type*>(&blockman_);
01415 return bm->get_allocator().alloc_bit_block();
01416 }
01417
01418
01419
01420
01421
01422
01423
01424
01425
01426 void free_tempblock(bm::word_t* block) const
01427 {
01428 blocks_manager_type* bm =
01429 const_cast<blocks_manager_type*>(&blockman_);
01430 bm->get_allocator().free_bit_block(block);
01431 }
01432
01433
01434
01435
01436 enumerator first() const
01437 {
01438 typedef typename bvector<Alloc>::enumerator enumerator_type;
01439 return enumerator_type(this, 0);
01440 }
01441
01442
01443
01444
01445
01446 enumerator end() const
01447 {
01448 typedef typename bvector<Alloc>::enumerator enumerator_type;
01449 return enumerator_type(this, 1);
01450 }
01451
01452
01453 const bm::word_t* get_block(unsigned nb) const
01454 {
01455 return blockman_.get_block(nb);
01456 }
01457
01458 void combine_operation(const bm::bvector<Alloc>& bvect,
01459 bm::operation opcode);
01460
01461 private:
01462
01463 bm::id_t check_or_next(bm::id_t prev) const;
01464
01465
01466
01467
01468 bm::id_t check_or_next_extract(bm::id_t prev);
01469
01470
01471
01472
01473 bool set_bit_no_check(bm::id_t n, bool val);
01474
01475
01476
01477
01478 bool and_bit_no_check(bm::id_t n, bool val);
01479
01480 bool set_bit_conditional_impl(bm::id_t n, bool val, bool condition);
01481
01482
01483 void combine_operation_with_block(unsigned nb,
01484 unsigned gap,
01485 bm::word_t* blk,
01486 const bm::word_t* arg_blk,
01487 int arg_gap,
01488 bm::operation opcode);
01489 public:
01490 void combine_operation_with_block(unsigned nb,
01491 const bm::word_t* arg_blk,
01492 int arg_gap,
01493 bm::operation opcode)
01494 {
01495 bm::word_t* blk = const_cast<bm::word_t*>(get_block(nb));
01496 bool gap = BM_IS_GAP(blk);
01497 combine_operation_with_block(nb, gap, blk, arg_blk, arg_gap, opcode);
01498 }
01499 private:
01500 void combine_count_operation_with_block(unsigned nb,
01501 const bm::word_t* arg_blk,
01502 int arg_gap,
01503 bm::operation opcode)
01504 {
01505 const bm::word_t* blk = get_block(nb);
01506 bool gap = BM_IS_GAP(blk);
01507 combine_count_operation_with_block(nb, gap, blk, arg_blk, arg_gap, opcode);
01508 }
01509
01510
01511
01512
01513
01514
01515
01516 void extend_gap_block(unsigned nb, gap_word_t* blk)
01517 {
01518 blockman_.extend_gap_block(nb, blk);
01519 }
01520
01521
01522
01523
01524 void set_range_no_check(bm::id_t left,
01525 bm::id_t right,
01526 bool value);
01527 public:
01528
01529 const blocks_manager_type& get_blocks_manager() const
01530 {
01531 return blockman_;
01532 }
01533
01534 blocks_manager_type& get_blocks_manager()
01535 {
01536 return blockman_;
01537 }
01538
01539
01540 private:
01541
01542
01543
01544 #ifdef BMCOUNTOPT
01545 mutable id_t count_;
01546 mutable bool count_is_valid_;
01547 #endif
01548
01549 blocks_manager_type blockman_;
01550 strategy new_blocks_strat_;
01551 size_type size_;
01552 };
01553
01554
01555
01556
01557
01558
01559
01560 template<class Alloc>
01561 inline bvector<Alloc> operator& (const bvector<Alloc>& v1,
01562 const bvector<Alloc>& v2)
01563 {
01564 #ifdef BM_USE_EXPLICIT_TEMP
01565 bvector<Alloc, MS> ret(v1);
01566 ret.bit_and(v2);
01567 return ret;
01568 #else
01569 return bvector<Alloc>(v1).bit_and(v2);
01570 #endif
01571 }
01572
01573
01574
01575 template<class Alloc>
01576 inline bvector<Alloc> operator| (const bvector<Alloc>& v1,
01577 const bvector<Alloc>& v2)
01578 {
01579 #ifdef BM_USE_EXPLICIT_TEMP
01580 bvector<Alloc, MS> ret(v1);
01581 ret.bit_or(v2);
01582 return ret;
01583 #else
01584 return bvector<Alloc>(v1).bit_or(v2);
01585 #endif
01586 }
01587
01588
01589
01590 template<class Alloc>
01591 inline bvector<Alloc> operator^ (const bvector<Alloc>& v1,
01592 const bvector<Alloc>& v2)
01593 {
01594 #ifdef BM_USE_EXPLICIT_TEMP
01595 bvector<Alloc, MS> ret(v1);
01596 ret.bit_xor(v2);
01597 return ret;
01598 #else
01599 return bvector<Alloc>(v1).bit_xor(v2);
01600 #endif
01601 }
01602
01603
01604
01605 template<class Alloc>
01606 inline bvector<Alloc> operator- (const bvector<Alloc>& v1,
01607 const bvector<Alloc>& v2)
01608 {
01609 #ifdef BM_USE_EXPLICIT_TEMP
01610 bvector<Alloc, MS> ret(v1);
01611 ret.bit_sub(v2);
01612 return ret;
01613 #else
01614 return bvector<Alloc>(v1).bit_sub(v2);
01615 #endif
01616 }
01617
01618
01619
01620
01621
01622
01623 template<typename Alloc>
01624 bvector<Alloc>& bvector<Alloc>::set_range(bm::id_t left,
01625 bm::id_t right,
01626 bool value)
01627 {
01628 if (right < left)
01629 {
01630 return set_range(right, left, value);
01631 }
01632
01633 BM_ASSERT(left < size_);
01634 BM_ASSERT(right < size_);
01635
01636 BMCOUNT_VALID(false)
01637 BM_SET_MMX_GUARD
01638
01639 set_range_no_check(left, right, value);
01640
01641 return *this;
01642 }
01643
01644
01645
01646 template<typename Alloc>
01647 bm::id_t bvector<Alloc>::count() const
01648 {
01649 #ifdef BMCOUNTOPT
01650 if (count_is_valid_) return count_;
01651 #endif
01652 word_t*** blk_root = blockman_.get_rootblock();
01653 if (!blk_root)
01654 {
01655 BMCOUNT_SET(0);
01656 return 0;
01657 }
01658 typename blocks_manager_type::block_count_func func(blockman_);
01659 for_each_nzblock2(blk_root, blockman_.effective_top_block_size(),
01660 func);
01661
01662 BMCOUNT_SET(func.count());
01663 return func.count();
01664 }
01665
01666
01667
01668 template<typename Alloc>
01669 void bvector<Alloc>::resize(size_type new_size)
01670 {
01671 if (size_ == new_size) return;
01672 if (size_ < new_size)
01673 {
01674 blockman_.reserve(new_size);
01675 size_ = new_size;
01676 }
01677 else
01678 {
01679 set_range(new_size, size_ - 1, false);
01680 size_ = new_size;
01681 }
01682 }
01683
01684
01685
01686 template<typename Alloc>
01687 bm::id_t bvector<Alloc>::count_range(bm::id_t left,
01688 bm::id_t right,
01689 unsigned* block_count_arr) const
01690 {
01691 BM_ASSERT(left <= right);
01692
01693 unsigned count = 0;
01694
01695
01696 unsigned nblock_left = unsigned(left >> bm::set_block_shift);
01697 unsigned nblock_right = unsigned(right >> bm::set_block_shift);
01698
01699 const bm::word_t* block = blockman_.get_block(nblock_left);
01700 bool left_gap = BM_IS_GAP(block);
01701
01702 unsigned nbit_left = unsigned(left & bm::set_block_mask);
01703 unsigned nbit_right = unsigned(right & bm::set_block_mask);
01704
01705 unsigned r =
01706 (nblock_left == nblock_right) ? nbit_right : (bm::bits_in_block-1);
01707
01708 typename blocks_manager_type::block_count_func func(blockman_);
01709
01710 if (block)
01711 {
01712 if ((nbit_left == 0) && (r == (bm::bits_in_block-1)))
01713 {
01714 if (block_count_arr)
01715 {
01716 count += block_count_arr[nblock_left];
01717 }
01718 else
01719 {
01720 func(block);
01721 }
01722 }
01723 else
01724 {
01725 if (left_gap)
01726 {
01727 count += gap_bit_count_range(BMGAP_PTR(block),
01728 (gap_word_t)nbit_left,
01729 (gap_word_t)r);
01730 }
01731 else
01732 {
01733 count += bit_block_calc_count_range(block, nbit_left, r);
01734 }
01735 }
01736 }
01737
01738 if (nblock_left == nblock_right)
01739 {
01740 return count + func.count();
01741 }
01742
01743 for (unsigned nb = nblock_left+1; nb < nblock_right; ++nb)
01744 {
01745 block = blockman_.get_block(nb);
01746 if (block_count_arr)
01747 {
01748 count += block_count_arr[nb];
01749 }
01750 else
01751 {
01752 if (block)
01753 func(block);
01754 }
01755 }
01756 count += func.count();
01757
01758 block = blockman_.get_block(nblock_right);
01759 bool right_gap = BM_IS_GAP(block);
01760
01761 if (block)
01762 {
01763 if (right_gap)
01764 {
01765 count += gap_bit_count_range(BMGAP_PTR(block),
01766 (gap_word_t)0,
01767 (gap_word_t)nbit_right);
01768 }
01769 else
01770 {
01771 count += bit_block_calc_count_range(block, 0, nbit_right);
01772 }
01773 }
01774
01775 return count;
01776 }
01777
01778
01779
01780 template<typename Alloc>
01781 bvector<Alloc>& bvector<Alloc>::invert()
01782 {
01783 BMCOUNT_VALID(false)
01784 BM_SET_MMX_GUARD
01785
01786 bm::word_t*** blk_root = blockman_.get_rootblock();
01787 typename blocks_manager_type::block_invert_func func(blockman_);
01788 for_each_block(blk_root, blockman_.top_block_size(), func);
01789 if (size_ == bm::id_max)
01790 {
01791 set_bit_no_check(bm::id_max, false);
01792 }
01793 else
01794 {
01795 set_range_no_check(size_, bm::id_max, false);
01796 }
01797
01798 return *this;
01799 }
01800
01801
01802
01803 template<typename Alloc>
01804 bool bvector<Alloc>::get_bit(bm::id_t n) const
01805 {
01806 BM_ASSERT(n < size_);
01807
01808
01809 unsigned nblock = unsigned(n >> bm::set_block_shift);
01810
01811 const bm::word_t* block = blockman_.get_block(nblock);
01812
01813 if (block)
01814 {
01815
01816 unsigned nbit = unsigned(n & bm::set_block_mask);
01817 unsigned is_set;
01818
01819 if (BM_IS_GAP(block))
01820 {
01821 is_set = gap_test(BMGAP_PTR(block), nbit);
01822 }
01823 else
01824 {
01825 unsigned nword = unsigned(nbit >> bm::set_word_shift);
01826 nbit &= bm::set_word_mask;
01827
01828 is_set = (block[nword] & (((bm::word_t)1) << nbit));
01829 }
01830 return is_set != 0;
01831 }
01832 return false;
01833 }
01834
01835
01836
01837 template<typename Alloc>
01838 void bvector<Alloc>::optimize(bm::word_t* temp_block,
01839 optmode opt_mode,
01840 statistics* stat)
01841 {
01842 word_t*** blk_root = blockman_.blocks_root();
01843
01844 if (!temp_block)
01845 temp_block = blockman_.check_allocate_tempblock();
01846
01847 typename
01848 blocks_manager_type::block_opt_func opt_func(blockman_,
01849 temp_block,
01850 (int)opt_mode,
01851 stat);
01852 if (stat)
01853 {
01854 stat->bit_blocks = stat->gap_blocks
01855 = stat->max_serialize_mem
01856 = stat->memory_used
01857 = 0;
01858 ::memcpy(stat->gap_levels,
01859 blockman_.glen(), sizeof(gap_word_t) * bm::gap_levels);
01860 stat->max_serialize_mem = sizeof(id_t) * 4;
01861
01862 }
01863
01864 for_each_nzblock(blk_root, blockman_.effective_top_block_size(),
01865 opt_func);
01866
01867 if (stat)
01868 {
01869 unsigned safe_inc = stat->max_serialize_mem / 10;
01870 if (!safe_inc) safe_inc = 256;
01871 stat->max_serialize_mem += safe_inc;
01872 stat->memory_used += sizeof(*this) - sizeof(blockman_);
01873 stat->memory_used += blockman_.mem_used();
01874 }
01875 }
01876
01877
01878
01879 template<typename Alloc>
01880 void bvector<Alloc>::optimize_gap_size()
01881 {
01882 struct bvector<Alloc>::statistics st;
01883 calc_stat(&st);
01884
01885 if (!st.gap_blocks)
01886 return;
01887
01888 gap_word_t opt_glen[bm::gap_levels];
01889 ::memcpy(opt_glen, st.gap_levels, bm::gap_levels * sizeof(*opt_glen));
01890
01891 improve_gap_levels(st.gap_length,
01892 st.gap_length + st.gap_blocks,
01893 opt_glen);
01894
01895 set_gap_levels(opt_glen);
01896 }
01897
01898
01899
01900 template<typename Alloc>
01901 void bvector<Alloc>::set_gap_levels(const gap_word_t* glevel_len)
01902 {
01903 word_t*** blk_root = blockman_.blocks_root();
01904 typename
01905 blocks_manager_type::gap_level_func gl_func(blockman_, glevel_len);
01906 for_each_nzblock(blk_root, blockman_.top_block_size(),gl_func);
01907
01908 blockman_.set_glen(glevel_len);
01909 }
01910
01911
01912
01913 template<typename Alloc>
01914 int bvector<Alloc>::compare(const bvector<Alloc>& bvect) const
01915 {
01916 int res;
01917 unsigned bn = 0;
01918
01919 unsigned top_blocks = blockman_.effective_top_block_size();
01920 unsigned bvect_top_blocks = bvect.blockman_.effective_top_block_size();
01921
01922 if (bvect_top_blocks > top_blocks) top_blocks = bvect_top_blocks;
01923
01924 for (unsigned i = 0; i < top_blocks; ++i)
01925 {
01926 const bm::word_t* const* blk_blk = blockman_.get_topblock(i);
01927 const bm::word_t* const* arg_blk_blk =
01928 bvect.blockman_.get_topblock(i);
01929
01930 if (blk_blk == arg_blk_blk)
01931 {
01932 bn += bm::set_array_size;
01933 continue;
01934 }
01935
01936 for (unsigned j = 0; j < bm::set_array_size; ++j, ++bn)
01937 {
01938 const bm::word_t* arg_blk = arg_blk_blk ? arg_blk_blk[j] : 0;
01939 const bm::word_t* blk = blk_blk ? blk_blk[j] : 0;
01940 if (blk == arg_blk) continue;
01941
01942
01943
01944
01945 if (!blk || !arg_blk)
01946 {
01947 const bm::word_t* pblk;
01948 bool is_gap;
01949
01950 if (blk)
01951 {
01952 pblk = blk;
01953 res = 1;
01954 is_gap = BM_IS_GAP(blk);
01955 }
01956 else
01957 {
01958 pblk = arg_blk;
01959 res = -1;
01960 is_gap = BM_IS_GAP(arg_blk);
01961 }
01962
01963 if (is_gap)
01964 {
01965 if (!gap_is_all_zero(BMGAP_PTR(pblk), bm::gap_max_bits))
01966 {
01967 return res;
01968 }
01969 }
01970 else
01971 {
01972 bm::wordop_t* blk1 = (wordop_t*)pblk;
01973 bm::wordop_t* blk2 =
01974 (wordop_t*)(pblk + bm::set_block_size);
01975 if (!bit_is_all_zero(blk1, blk2))
01976 {
01977 return res;
01978 }
01979 }
01980
01981 continue;
01982 }
01983
01984 bool arg_gap = BM_IS_GAP(arg_blk);
01985 bool gap = BM_IS_GAP(blk);
01986
01987 if (arg_gap != gap)
01988 {
01989 bm::wordop_t temp_blk[bm::set_block_size_op];
01990 bm::wordop_t* blk1;
01991 bm::wordop_t* blk2;
01992
01993 if (gap)
01994 {
01995 gap_convert_to_bitset((bm::word_t*)temp_blk,
01996 BMGAP_PTR(blk));
01997
01998 blk1 = (bm::wordop_t*)temp_blk;
01999 blk2 = (bm::wordop_t*)arg_blk;
02000 }
02001 else
02002 {
02003 gap_convert_to_bitset((bm::word_t*)temp_blk,
02004 BMGAP_PTR(arg_blk));
02005
02006 blk1 = (bm::wordop_t*)blk;
02007 blk2 = (bm::wordop_t*)temp_blk;
02008
02009 }
02010 res = bitcmp(blk1, blk2, bm::set_block_size_op);
02011
02012 }
02013 else
02014 {
02015 if (gap)
02016 {
02017 res = gapcmp(BMGAP_PTR(blk), BMGAP_PTR(arg_blk));
02018 }
02019 else
02020 {
02021 res = bitcmp((bm::wordop_t*)blk,
02022 (bm::wordop_t*)arg_blk,
02023 bm::set_block_size_op);
02024 }
02025 }
02026
02027 if (res != 0)
02028 {
02029 return res;
02030 }
02031
02032
02033 }
02034
02035 }
02036
02037 return 0;
02038 }
02039
02040
02041
02042
02043 template<typename Alloc>
02044 void bvector<Alloc>::calc_stat(struct bvector<Alloc>::statistics* st) const
02045 {
02046 st->bit_blocks = st->gap_blocks
02047 = st->max_serialize_mem
02048 = st->memory_used = 0;
02049
02050 ::memcpy(st->gap_levels,
02051 blockman_.glen(), sizeof(gap_word_t) * bm::gap_levels);
02052
02053 unsigned empty_blocks = 0;
02054 unsigned blocks_memory = 0;
02055 gap_word_t* gapl_ptr = st->gap_length;
02056
02057 st->max_serialize_mem = sizeof(id_t) * 4;
02058
02059 unsigned block_idx = 0;
02060
02061 unsigned top_size = blockman_.effective_top_block_size();
02062
02063 for (unsigned i = 0; i < top_size; ++i)
02064 {
02065 const bm::word_t* const* blk_blk = blockman_.get_topblock(i);
02066
02067 if (!blk_blk)
02068 {
02069 block_idx += bm::set_array_size;
02070 st->max_serialize_mem += sizeof(unsigned) + 1;
02071 continue;
02072 }
02073
02074 for (unsigned j = 0;j < bm::set_array_size; ++j, ++block_idx)
02075 {
02076 const bm::word_t* blk = blk_blk[j];
02077 if (IS_VALID_ADDR(blk))
02078 {
02079 st->max_serialize_mem += empty_blocks << 2;
02080 empty_blocks = 0;
02081
02082 if (BM_IS_GAP(blk))
02083 {
02084 ++(st->gap_blocks);
02085
02086 bm::gap_word_t* gap_blk = BMGAP_PTR(blk);
02087
02088 unsigned mem_used =
02089 bm::gap_capacity(gap_blk, blockman_.glen())
02090 * sizeof(gap_word_t);
02091
02092 *gapl_ptr = gap_length(gap_blk);
02093
02094 st->max_serialize_mem += *gapl_ptr * sizeof(gap_word_t);
02095 blocks_memory += mem_used;
02096
02097 ++gapl_ptr;
02098 }
02099 else
02100 {
02101 ++(st->bit_blocks);
02102 unsigned mem_used = sizeof(bm::word_t) * bm::set_block_size;
02103 st->max_serialize_mem += mem_used;
02104 blocks_memory += mem_used;
02105 }
02106 }
02107 else
02108 {
02109 ++empty_blocks;
02110 }
02111 }
02112 }
02113
02114 unsigned safe_inc = st->max_serialize_mem / 10;
02115 if (!safe_inc) safe_inc = 256;
02116 st->max_serialize_mem += safe_inc;
02117
02118
02119
02120 st->memory_used += sizeof(*this) - sizeof(blockman_);
02121 st->memory_used += blockman_.mem_used();
02122 st->memory_used += blocks_memory;
02123 }
02124
02125
02126
02127
02128
02129 template<class Alloc>
02130 bool bvector<Alloc>::set_bit_no_check(bm::id_t n, bool val)
02131 {
02132
02133 unsigned nblock = unsigned(n >> bm::set_block_shift);
02134
02135 int block_type;
02136
02137 bm::word_t* blk =
02138 blockman_.check_allocate_block(nblock,
02139 val,
02140 get_new_blocks_strat(),
02141 &block_type);
02142
02143 if (!blk) return false;
02144
02145
02146 unsigned nbit = unsigned(n & bm::set_block_mask);
02147
02148 if (block_type == 1)
02149 {
02150 unsigned is_set;
02151 unsigned new_block_len;
02152
02153 new_block_len =
02154 gap_set_value(val, BMGAP_PTR(blk), nbit, &is_set);
02155 if (is_set)
02156 {
02157 BMCOUNT_ADJ(val)
02158
02159 unsigned threshold =
02160 bm::gap_limit(BMGAP_PTR(blk), blockman_.glen());
02161
02162 if (new_block_len > threshold)
02163 {
02164 extend_gap_block(nblock, BMGAP_PTR(blk));
02165 }
02166 return true;
02167 }
02168 }
02169 else
02170 {
02171 unsigned nword = unsigned(nbit >> bm::set_word_shift);
02172 nbit &= bm::set_word_mask;
02173
02174 bm::word_t* word = blk + nword;
02175 bm::word_t mask = (((bm::word_t)1) << nbit);
02176
02177 if (val)
02178 {
02179 if ( ((*word) & mask) == 0 )
02180 {
02181 *word |= mask;
02182 BMCOUNT_INC;
02183 return true;
02184 }
02185 }
02186 else
02187 {
02188 if ((*word) & mask)
02189 {
02190 *word &= ~mask;
02191 BMCOUNT_DEC;
02192 return true;
02193 }
02194 }
02195 }
02196 return false;
02197 }
02198
02199
02200
02201 template<class Alloc>
02202 bool bvector<Alloc>::set_bit_conditional_impl(bm::id_t n,
02203 bool val,
02204 bool condition)
02205 {
02206
02207 unsigned nblock = unsigned(n >> bm::set_block_shift);
02208
02209 int block_type;
02210 bm::word_t* blk =
02211 blockman_.check_allocate_block(nblock,
02212 val,
02213 get_new_blocks_strat(),
02214 &block_type);
02215 if (!blk)
02216 return false;
02217
02218
02219 unsigned nbit = unsigned(n & bm::set_block_mask);
02220
02221 if (block_type == 1)
02222 {
02223 bm::gap_word_t* gap_blk = BMGAP_PTR(blk);
02224 bool old_val = (gap_test(gap_blk, nbit) != 0);
02225
02226 if (old_val != condition)
02227 {
02228 return false;
02229 }
02230
02231 if (val != old_val)
02232 {
02233 unsigned is_set;
02234 unsigned new_block_len =
02235 gap_set_value(val, gap_blk, nbit, &is_set);
02236 BM_ASSERT(is_set);
02237 BMCOUNT_ADJ(val)
02238
02239 unsigned threshold =
02240 bm::gap_limit(gap_blk, blockman_.glen());
02241 if (new_block_len > threshold)
02242 {
02243 extend_gap_block(nblock, gap_blk);
02244 }
02245 return true;
02246 }
02247 }
02248 else
02249 {
02250 unsigned nword = unsigned(nbit >> bm::set_word_shift);
02251 nbit &= bm::set_word_mask;
02252
02253 bm::word_t* word = blk + nword;
02254 bm::word_t mask = (((bm::word_t)1) << nbit);
02255 bool is_set = ((*word) & mask) != 0;
02256
02257 if (is_set != condition)
02258 {
02259 return false;
02260 }
02261 if (is_set != val)
02262 {
02263 if (val)
02264 {
02265 *word |= mask;
02266 BMCOUNT_INC;
02267 }
02268 else
02269 {
02270 *word &= ~mask;
02271 BMCOUNT_DEC;
02272 }
02273 return true;
02274 }
02275 }
02276 return false;
02277
02278 }
02279
02280
02281
02282
02283 template<class Alloc>
02284 bool bvector<Alloc>::and_bit_no_check(bm::id_t n, bool val)
02285 {
02286
02287 unsigned nblock = unsigned(n >> bm::set_block_shift);
02288
02289 int block_type;
02290 bm::word_t* blk =
02291 blockman_.check_allocate_block(nblock,
02292 val,
02293 get_new_blocks_strat(),
02294 &block_type);
02295 if (!blk) return false;
02296
02297
02298 unsigned nbit = unsigned(n & bm::set_block_mask);
02299
02300 if (block_type == 1)
02301 {
02302 bm::gap_word_t* gap_blk = BMGAP_PTR(blk);
02303 bool old_val = (gap_test(gap_blk, nbit) != 0);
02304
02305 bool new_val = val & old_val;
02306 if (new_val != old_val)
02307 {
02308 unsigned is_set;
02309 unsigned new_block_len =
02310 gap_set_value(new_val, gap_blk, nbit, &is_set);
02311 BM_ASSERT(is_set);
02312 BMCOUNT_ADJ(val)
02313
02314 unsigned threshold =
02315 bm::gap_limit(gap_blk, blockman_.glen());
02316 if (new_block_len > threshold)
02317 {
02318 extend_gap_block(nblock, gap_blk);
02319 }
02320 return true;
02321 }
02322 }
02323 else
02324 {
02325 unsigned nword = unsigned(nbit >> bm::set_word_shift);
02326 nbit &= bm::set_word_mask;
02327
02328 bm::word_t* word = blk + nword;
02329 bm::word_t mask = (((bm::word_t)1) << nbit);
02330 bool is_set = ((*word) & mask) != 0;
02331
02332 bool new_val = is_set & val;
02333 if (new_val != val)
02334 {
02335 if (new_val)
02336 {
02337 *word |= mask;
02338 BMCOUNT_INC;
02339 }
02340 else
02341 {
02342 *word &= ~mask;
02343 BMCOUNT_DEC;
02344 }
02345 return true;
02346 }
02347 }
02348 return false;
02349 }
02350
02351
02352
02353
02354 template<class Alloc>
02355 bm::id_t bvector<Alloc>::check_or_next(bm::id_t prev) const
02356 {
02357 for (;;)
02358 {
02359 unsigned nblock = unsigned(prev >> bm::set_block_shift);
02360 if (nblock >= bm::set_total_blocks)
02361 break;
02362
02363 if (blockman_.is_subblock_null(nblock >> bm::set_array_shift))
02364 {
02365 prev += (bm::set_blkblk_mask + 1) -
02366 (prev & bm::set_blkblk_mask);
02367 }
02368 else
02369 {
02370 unsigned nbit = unsigned(prev & bm::set_block_mask);
02371 int no_more_blocks;
02372 const bm::word_t* block =
02373 blockman_.get_block(nblock, &no_more_blocks);
02374
02375 if (no_more_blocks)
02376 {
02377 BM_ASSERT(block == 0);
02378 break;
02379 }
02380
02381 if (block)
02382 {
02383 if (IS_FULL_BLOCK(block)) return prev;
02384 if (BM_IS_GAP(block))
02385 {
02386 if (bm::gap_find_in_block(BMGAP_PTR(block),
02387 nbit,
02388 &prev))
02389 {
02390 return prev;
02391 }
02392 }
02393 else
02394 {
02395 if (bm::bit_find_in_block(block, nbit, &prev))
02396 {
02397 return prev;
02398 }
02399 }
02400 }
02401 else
02402 {
02403 prev += (bm::set_block_mask + 1) -
02404 (prev & bm::set_block_mask);
02405 }
02406
02407 }
02408 if (!prev) break;
02409 }
02410
02411 return 0;
02412 }
02413
02414
02415
02416
02417 template<class Alloc>
02418 bm::id_t bvector<Alloc>::check_or_next_extract(bm::id_t prev)
02419 {
02420 for (;;)
02421 {
02422 unsigned nblock = unsigned(prev >> bm::set_block_shift);
02423 if (nblock >= bm::set_total_blocks) break;
02424
02425 if (blockman_.is_subblock_null(nblock >> bm::set_array_shift))
02426 {
02427 prev += (bm::set_blkblk_mask + 1) -
02428 (prev & bm::set_blkblk_mask);
02429 }
02430 else
02431 {
02432 unsigned nbit = unsigned(prev & bm::set_block_mask);
02433
02434 int no_more_blocks;
02435 bm::word_t* block =
02436 blockman_.get_block(nblock, &no_more_blocks);
02437
02438 if (no_more_blocks)
02439 {
02440 BM_ASSERT(block == 0);
02441 break;
02442 }
02443
02444
02445 if (block)
02446 {
02447 if (IS_FULL_BLOCK(block))
02448 {
02449 set(prev, false);
02450 return prev;
02451 }
02452 if (BM_IS_GAP(block))
02453 {
02454 unsigned is_set;
02455 unsigned new_block_len =
02456 gap_set_value(0, BMGAP_PTR(block), nbit, &is_set);
02457 if (is_set) {
02458 BMCOUNT_DEC
02459 unsigned threshold =
02460 bm::gap_limit(BMGAP_PTR(block), blockman_.glen());
02461 if (new_block_len > threshold)
02462 {
02463 extend_gap_block(nblock, BMGAP_PTR(block));
02464 }
02465 return prev;
02466 } else {
02467 if (bm::gap_find_in_block(BMGAP_PTR(block),
02468 nbit,
02469 &prev))
02470 {
02471 set(prev, false);
02472 return prev;
02473 }
02474 }
02475 }
02476 else
02477 {
02478 if (bm::bit_find_in_block(block, nbit, &prev))
02479 {
02480 BMCOUNT_DEC
02481
02482 unsigned nbit =
02483 unsigned(prev & bm::set_block_mask);
02484 unsigned nword =
02485 unsigned(nbit >> bm::set_word_shift);
02486 nbit &= bm::set_word_mask;
02487 bm::word_t* word = block + nword;
02488 bm::word_t mask = ((bm::word_t)1) << nbit;
02489 *word &= ~mask;
02490
02491 return prev;
02492 }
02493 }
02494 }
02495 else
02496 {
02497 prev += (bm::set_block_mask + 1) -
02498 (prev & bm::set_block_mask);
02499 }
02500
02501 }
02502 if (!prev) break;
02503 }
02504
02505 return 0;
02506 }
02507
02508
02509
02510 template<class Alloc>
02511 void bvector<Alloc>::combine_operation(
02512 const bm::bvector<Alloc>& bvect,
02513 bm::operation opcode)
02514 {
02515 typedef void (*block_bit_op)(bm::word_t*, const bm::word_t*);
02516 typedef void (*block_bit_op_next)(bm::word_t*,
02517 const bm::word_t*,
02518 bm::word_t*,
02519 const bm::word_t*);
02520
02521 unsigned top_blocks = blockman_.top_block_size();
02522 unsigned bvect_top_blocks = bvect.blockman_.top_block_size();
02523
02524 if (size_ == bvect.size_)
02525 {
02526 BM_ASSERT(top_blocks >= bvect_top_blocks);
02527 }
02528 else
02529 if (size_ < bvect.size_)
02530 {
02531 size_ = bvect.size_;
02532
02533 blockman_.reserve_top_blocks(bvect_top_blocks);
02534 top_blocks = blockman_.top_block_size();
02535 }
02536 else
02537 if (size_ > bvect.size_)
02538 {
02539 if (opcode == BM_AND)
02540 {
02541 set_range(bvect.size_, size_ - 1, false);
02542 if (bvect_top_blocks < top_blocks)
02543 {
02544
02545 top_blocks = bvect_top_blocks;
02546 }
02547 }
02548 }
02549
02550 bm::word_t*** blk_root = blockman_.blocks_root();
02551 unsigned block_idx = 0;
02552 unsigned i, j;
02553
02554 BM_SET_MMX_GUARD
02555
02556
02557 top_blocks = blockman_.effective_top_block_size();
02558 if (top_blocks < bvect.blockman_.effective_top_block_size())
02559 {
02560 if (opcode != BM_AND)
02561 {
02562 top_blocks = bvect.blockman_.effective_top_block_size();
02563 }
02564 }
02565
02566 for (i = 0; i < top_blocks; ++i)
02567 {
02568 bm::word_t** blk_blk = blk_root[i];
02569 if (blk_blk == 0)
02570 {
02571 if (opcode == BM_AND)
02572 {
02573 block_idx += bm::set_array_size;
02574 continue;
02575 }
02576 const bm::word_t* const* bvbb = bvect.blockman_.get_topblock(i);
02577 if (bvbb == 0)
02578 {
02579 block_idx += bm::set_array_size;
02580 continue;
02581 }
02582
02583 unsigned r = i * bm::set_array_size;
02584 for (j = 0; j < bm::set_array_size; ++j)
02585 {
02586 const bm::word_t* arg_blk = bvect.blockman_.get_block(i, j);
02587 if (arg_blk )
02588 combine_operation_with_block(r + j,
02589 0, 0,
02590 arg_blk, BM_IS_GAP(arg_blk),
02591 opcode);
02592 }
02593 continue;
02594 }
02595
02596 if (opcode == BM_AND)
02597 {
02598 unsigned r = i * bm::set_array_size;
02599 for (j = 0; j < bm::set_array_size; ++j)
02600 {
02601 bm::word_t* blk = blk_blk[j];
02602 if (blk)
02603 {
02604 const bm::word_t* arg_blk = bvect.blockman_.get_block(i, j);
02605 if (arg_blk)
02606 combine_operation_with_block(r + j,
02607 BM_IS_GAP(blk), blk,
02608 arg_blk, BM_IS_GAP(arg_blk),
02609 opcode);
02610 else
02611 blockman_.zero_block(i, j);
02612 }
02613
02614 }
02615 }
02616 else
02617 {
02618 unsigned r = i * bm::set_array_size;
02619 for (j = 0; j < bm::set_array_size; ++j)
02620 {
02621 bm::word_t* blk = blk_blk[j];
02622 const bm::word_t* arg_blk = bvect.blockman_.get_block(i, j);
02623 if (arg_blk || blk)
02624 combine_operation_with_block(r + j, BM_IS_GAP(blk), blk,
02625 arg_blk, BM_IS_GAP(arg_blk),
02626 opcode);
02627 }
02628 }
02629 }
02630
02631 }
02632
02633
02634
02635
02636
02637 template<class Alloc>
02638 void
02639 bvector<Alloc>::combine_operation_with_block(unsigned nb,
02640 unsigned gap,
02641 bm::word_t* blk,
02642 const bm::word_t* arg_blk,
02643 int arg_gap,
02644 bm::operation opcode)
02645 {
02646 gap_word_t tmp_buf[bm::gap_equiv_len * 3];
02647 const bm::gap_word_t* res;
02648 unsigned res_len;
02649 int level;
02650 unsigned threshold;
02651
02652
02653 if (opcode == BM_OR || opcode == BM_XOR)
02654 {
02655 if (!blk && arg_gap)
02656 {
02657 res = BMGAP_PTR(arg_blk);
02658 res_len = bm::gap_length(res);
02659 level = -1;
02660 threshold = 0;
02661 goto assign_gap_result;
02662 }
02663 }
02664
02665 if (gap)
02666 {
02667 if (arg_gap)
02668 {
02669 {
02670 gap_operation_func_type gfunc =
02671 operation_functions<true>::gap_operation(opcode);
02672 BM_ASSERT(gfunc);
02673 res = (*gfunc)(BMGAP_PTR(blk),
02674 BMGAP_PTR(arg_blk),
02675 tmp_buf,
02676 res_len);
02677 }
02678 BM_ASSERT(res == tmp_buf);
02679 ++res_len;
02680
02681 BM_ASSERT(!(res == tmp_buf && res_len == 0));
02682
02683
02684
02685 if (gap_is_all_zero(res, bm::gap_max_bits))
02686 {
02687 blockman_.zero_block(nb);
02688 return;
02689 }
02690
02691
02692
02693 level = gap_level(BMGAP_PTR(blk));
02694 threshold = blockman_.glen(level)-4;
02695
02696 assign_gap_result:
02697 int new_level = gap_calc_level(res_len, blockman_.glen());
02698 if (new_level == -1)
02699 {
02700 blockman_.convert_gap2bitset(nb, res, res_len-1);
02701 return;
02702 }
02703
02704 if (res_len > threshold)
02705 {
02706 gap_word_t* new_blk =
02707 blockman_.allocate_gap_block(new_level, res);
02708 set_gap_level(new_blk, new_level);
02709
02710 bm::word_t* p = (bm::word_t*)new_blk;
02711 BMSET_PTRGAP(p);
02712
02713 if (blk)
02714 {
02715 blockman_.set_block_ptr(nb, p);
02716 blockman_.get_allocator().free_gap_block(BMGAP_PTR(blk),
02717 blockman_.glen());
02718 }
02719 else
02720 {
02721 blockman_.set_block(nb, p, true);
02722 }
02723 return;
02724 }
02725
02726
02727
02728
02729 BM_ASSERT(blk);
02730
02731 set_gap_level(tmp_buf, level);
02732 ::memcpy(BMGAP_PTR(blk), tmp_buf, res_len * sizeof(gap_word_t));
02733 return;
02734 }
02735 else
02736 {
02737
02738
02739
02740 if (arg_blk == 0)
02741 {
02742 switch (opcode)
02743 {
02744 case BM_AND:
02745 blockman_.zero_block(nb);
02746 return;
02747 case BM_OR: case BM_SUB: case BM_XOR:
02748 return;
02749 }
02750 }
02751 gap_word_t* gap_blk = BMGAP_PTR(blk);
02752 if (opcode == BM_AND)
02753 {
02754 unsigned gap_cnt = gap_bit_count(gap_blk);
02755 if (gap_cnt < 128)
02756 {
02757 gap_word_t tmp_buf[bm::gap_equiv_len * 3];
02758 gap_word_t arr_len =
02759 gap_convert_to_arr(tmp_buf, gap_blk,
02760 bm::gap_equiv_len-10);
02761 BM_ASSERT(gap_cnt == arr_len);
02762 blockman_.zero_block(nb);
02763 unsigned arr_i = 0;
02764 int block_type;
02765 blk =
02766 blockman_.check_allocate_block(nb,
02767 true,
02768 BM_GAP,
02769 &block_type,
02770 false
02771 );
02772 BM_ASSERT(block_type==1);
02773 gap_blk = BMGAP_PTR(blk);
02774 unsigned threshold = bm::gap_limit(gap_blk, blockman_.glen());
02775 for (; arr_i < arr_len; ++arr_i)
02776 {
02777 gap_word_t bit_idx = tmp_buf[arr_i];
02778 if (bm::test_bit(arg_blk, bit_idx))
02779 {
02780 unsigned is_set;
02781 unsigned new_block_len =
02782 gap_set_value(true, gap_blk, bit_idx, &is_set);
02783 BM_ASSERT(is_set);
02784 if (new_block_len > threshold)
02785 {
02786 gap_blk =
02787 blockman_.extend_gap_block(nb, gap_blk);
02788 if (gap_blk == 0)
02789 {
02790 blk = blockman_.check_allocate_block(
02791 nb,
02792 true,
02793 this->get_new_blocks_strat(),
02794 &block_type,
02795 false
02796 );
02797 BM_ASSERT(block_type == 0);
02798
02799 for (++arr_i; arr_i < arr_len; ++arr_i)
02800 {
02801 bit_idx = tmp_buf[arr_i];
02802 if (bm::test_bit(arg_blk, bit_idx))
02803 {
02804 or_bit_block(blk, bit_idx, 1);
02805 }
02806 }
02807 return;
02808 }
02809 }
02810 }
02811 }
02812
02813 return;
02814 }
02815 }
02816
02817 blk = blockman_.convert_gap2bitset(nb, gap_blk);
02818 }
02819 }
02820 else
02821 {
02822 if (arg_gap)
02823 {
02824 if (IS_VALID_ADDR(blk))
02825 {
02826
02827
02828 gap_operation_to_bitset_func_type gfunc =
02829 operation_functions<true>::gap_op_to_bit(opcode);
02830 BM_ASSERT(gfunc);
02831 (*gfunc)(blk, BMGAP_PTR(arg_blk));
02832 return;
02833 }
02834
02835
02836
02837 gap_word_t* temp_blk = (gap_word_t*) blockman_.check_allocate_tempblock();
02838 arg_blk =
02839 gap_convert_to_bitset_smart((bm::word_t*)temp_blk,
02840 BMGAP_PTR(arg_blk),
02841 bm::gap_max_bits);
02842
02843 }
02844 }
02845
02846
02847 bm::word_t* dst = blk;
02848
02849 bm::word_t* ret;
02850 if (dst == 0 && arg_blk == 0)
02851 {
02852 return;
02853 }
02854
02855 switch (opcode)
02856 {
02857 case BM_AND:
02858 ret = bit_operation_and(dst, arg_blk);
02859 goto copy_block;
02860 case BM_XOR:
02861 ret = bit_operation_xor(dst, arg_blk);
02862 if (ret && (ret == arg_blk) && IS_FULL_BLOCK(dst))
02863 {
02864 ret = blockman_.get_allocator().alloc_bit_block();
02865 #ifdef BMVECTOPT
02866 VECT_XOR_ARR_2_MASK(ret,
02867 arg_blk,
02868 arg_blk + bm::set_block_size,
02869 bm::all_bits_mask);
02870 #else
02871 bm::wordop_t* dst_ptr = (wordop_t*)ret;
02872 const bm::wordop_t* wrd_ptr = (wordop_t*) arg_blk;
02873 const bm::wordop_t* wrd_end =
02874 (wordop_t*) (arg_blk + bm::set_block_size);
02875
02876 do
02877 {
02878 dst_ptr[0] = bm::all_bits_mask ^ wrd_ptr[0];
02879 dst_ptr[1] = bm::all_bits_mask ^ wrd_ptr[1];
02880 dst_ptr[2] = bm::all_bits_mask ^ wrd_ptr[2];
02881 dst_ptr[3] = bm::all_bits_mask ^ wrd_ptr[3];
02882
02883 dst_ptr+=4;
02884 wrd_ptr+=4;
02885
02886 } while (wrd_ptr < wrd_end);
02887 #endif
02888 break;
02889 }
02890 goto copy_block;
02891 case BM_OR:
02892 ret = bit_operation_or(dst, arg_blk);
02893 copy_block:
02894 if (ret && (ret == arg_blk) && !IS_FULL_BLOCK(ret))
02895 {
02896 ret = blockman_.get_allocator().alloc_bit_block();
02897 bit_block_copy(ret, arg_blk);
02898 }
02899 break;
02900
02901 case BM_SUB:
02902 ret = bit_operation_sub(dst, arg_blk);
02903 if (ret && ret == arg_blk)
02904 {
02905 ret = blockman_.get_allocator().alloc_bit_block();
02906 #ifdef BMVECTOPT
02907 VECT_ANDNOT_ARR_2_MASK(ret,
02908 arg_blk,
02909 arg_blk + bm::set_block_size,
02910 bm::all_bits_mask);
02911 #else
02912
02913 bm::wordop_t* dst_ptr = (wordop_t*)ret;
02914 const bm::wordop_t* wrd_ptr = (wordop_t*) arg_blk;
02915 const bm::wordop_t* wrd_end =
02916 (wordop_t*) (arg_blk + bm::set_block_size);
02917
02918 do
02919 {
02920 dst_ptr[0] = bm::all_bits_mask & ~wrd_ptr[0];
02921 dst_ptr[1] = bm::all_bits_mask & ~wrd_ptr[1];
02922 dst_ptr[2] = bm::all_bits_mask & ~wrd_ptr[2];
02923 dst_ptr[3] = bm::all_bits_mask & ~wrd_ptr[3];
02924
02925 dst_ptr+=4;
02926 wrd_ptr+=4;
02927
02928 } while (wrd_ptr < wrd_end);
02929 #endif
02930 }
02931 break;
02932 default:
02933 BM_ASSERT(0);
02934 ret = 0;
02935 }
02936
02937 if (ret != dst)
02938 {
02939 blockman_.set_block(nb, ret);
02940 blockman_.get_allocator().free_bit_block(dst);
02941 }
02942 }
02943
02944
02945
02946 template<class Alloc>
02947 void bvector<Alloc>::set_range_no_check(bm::id_t left,
02948 bm::id_t right,
02949 bool value)
02950 {
02951
02952 unsigned nblock_left = unsigned(left >> bm::set_block_shift);
02953 unsigned nblock_right = unsigned(right >> bm::set_block_shift);
02954
02955 bm::word_t* block = blockman_.get_block(nblock_left);
02956 bool left_gap = BM_IS_GAP(block);
02957
02958 unsigned nbit_left = unsigned(left & bm::set_block_mask);
02959 unsigned nbit_right = unsigned(right & bm::set_block_mask);
02960
02961 unsigned r =
02962 (nblock_left == nblock_right) ? nbit_right :(bm::bits_in_block-1);
02963
02964 bm::gap_word_t tmp_gap_blk[5] = {0,};
02965
02966
02967
02968 unsigned nb;
02969 if ((nbit_left == 0) && (r == bm::bits_in_block - 1))
02970 {
02971 nb = nblock_left;
02972 }
02973 else
02974 {
02975 gap_init_range_block<gap_word_t>(tmp_gap_blk,
02976 (gap_word_t)nbit_left,
02977 (gap_word_t)r,
02978 (gap_word_t)value,
02979 bm::bits_in_block);
02980
02981 combine_operation_with_block(nblock_left,
02982 left_gap,
02983 block,
02984 (bm::word_t*) tmp_gap_blk,
02985 1,
02986 value ? BM_OR : BM_AND);
02987
02988 if (nblock_left == nblock_right)
02989 return;
02990 nb = nblock_left+1;
02991 }
02992
02993
02994
02995 unsigned nb_to = nblock_right + (nbit_right ==(bm::bits_in_block-1));
02996
02997 if (value)
02998 {
02999 for (; nb < nb_to; ++nb)
03000 {
03001 block = blockman_.get_block(nb);
03002 if (IS_FULL_BLOCK(block))
03003 continue;
03004
03005 blockman_.set_block(nb, FULL_BLOCK_ADDR);
03006 blockman_.free_block(block);
03007 }
03008 }
03009 else
03010 {
03011 for (; nb < nb_to; ++nb)
03012 {
03013 block = blockman_.get_block(nb);
03014 if (block == 0)
03015 continue;
03016 blockman_.set_block(nb, 0, false );
03017 blockman_.free_block(block);
03018
03019 }
03020 }
03021
03022 if (nb_to > nblock_right)
03023 return;
03024
03025 block = blockman_.get_block(nblock_right);
03026 bool right_gap = BM_IS_GAP(block);
03027
03028 gap_init_range_block<gap_word_t>(tmp_gap_blk,
03029 (gap_word_t)0,
03030 (gap_word_t)nbit_right,
03031 (gap_word_t)value,
03032 bm::bits_in_block);
03033
03034 combine_operation_with_block(nblock_right,
03035 right_gap,
03036 block,
03037 (bm::word_t*) tmp_gap_blk,
03038 1,
03039 value ? BM_OR : BM_AND);
03040
03041 }
03042
03043
03044
03045
03046 }
03047
03048 #include "bmundef.h"
03049
03050 #ifdef _MSC_VER
03051 #pragma warning( pop )
03052 #endif
03053
03054
03055 #endif