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