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