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