- Main Page
- Modules
- Namespaces
- Data Structures
- Files
- Examples

- File List
- Globals

# 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
    00100 /** @defgroup bmagic BitMagic C++ Library
    00101  *  For more information please visit:  http://bmagic.sourceforge.net
    00102  *
    00103  */
    00104
    00105
    00106 /** @defgroup bvector The Main bvector<> Group
    00107  *  This is the main group. It includes bvector template: front end of the bm library.
    00108  *  @ingroup bmagic
    00109  */
    00110
    00111
    00112
    00113
    00114 /*!
    00115    @brief bitvector with runtime compression of bits.
    00116    @ingroup bvector
    00117 */
    00118
    00119 template<class Alloc>
    00120 class bvector
    00121 {
    00122 public:
    00123
    00124     typedef Alloc  allocator_type;
    00125     typedef blocks_manager<Alloc>      blocks_manager_type;
    00126     /** Type used to count bits in the bit vector */
    00127     typedef bm::id_t                   size_type;
    00128
    00129     /** Statistical information about bitset's memory allocation details. */
    00130     struct statistics : public bv_statistics
    00131     {};
    00132
    00133     /**
    00134         @brief Class reference implements an object for bit assignment.
    00135         Since C++ does not provide with build-in bit type supporting l-value
    00136         operations we have to emulate it.
    00137
    00138         @ingroup bvector
    00139     */
    00140     class reference
    00141     {
    00142     public:
    00143         reference(bvector<Alloc>& bv, bm::id_t position)
    00144         : bv_(bv),
    00145           position_(position)
    00146         {}
    00147
    00148         reference(const reference& ref)
    00149         : bv_(ref.bv_),
    00150           position_(ref.position_)
    00151         {
    00152             bv_.set(position_, ref.bv_.get_bit(position_));
    00153         }
    00154
    00155         operator bool() const
    00156         {
    00157             return bv_.get_bit(position_);
    00158         }
    00159
    00160         const reference& operator=(const reference& ref) const
    00161         {
    00162             bv_.set(position_, (bool)ref);
    00163             return *this;
    00164         }
    00165
    00166         const reference& operator=(bool value) const
    00167         {
    00168             bv_.set(position_, value);
    00169             return *this;
    00170         }
    00171
    00172         bool operator==(const reference& ref) const
    00173         {
    00174             return bool(*this) == bool(ref);
    00175         }
    00176
    00177         /*! Bitwise AND. Performs operation: bit = bit AND value */
    00178         const reference& operator&=(bool value) const
    00179         {
    00180             bv_.set_bit_and(position_, value);
    00181             return *this;
    00182         }
    00183
    00184         /*! Bitwise OR. Performs operation: bit = bit OR value */
    00185         const reference& operator|=(bool value) const
    00186         {
    00187             if (value != bv_.get_bit(position_))
    00188             {
    00189                 bv_.set_bit(position_);
    00190             }
    00191             return *this;
    00192         }
    00193
    00194         /*! Bitwise exclusive-OR (XOR). Performs operation: bit = bit XOR value */
    00195         const reference& operator^=(bool value) const
    00196         {
    00197             bv_.set(position_, value != bv_.get_bit(position_));
    00198             return *this;
    00199         }
    00200
    00201         /*! Logical Not operator */
    00202         bool operator!() const
    00203         {
    00204             return !bv_.get_bit(position_);
    00205         }
    00206
    00207         /*! Bit Not operator */
    00208         bool operator~() const
    00209         {
    00210             return !bv_.get_bit(position_);
    00211         }
    00212
    00213         /*! Negates the bit value */
    00214         reference& flip()
    00215         {
    00216             bv_.flip(position_);
    00217             return *this;
    00218         }
    00219
    00220     private:
    00221         bvector<Alloc>&   bv_;       //!< Reference variable on the parent.
    00222         bm::id_t          position_; //!< Position in the parent bitvector.
    00223     };
    00224
    00225     typedef bool const_reference;
    00226
    00227     /*!
    00228         @brief Base class for all iterators.
    00229         @ingroup bvector
    00230     */
    00231     class iterator_base
    00232     {
    00233     friend class bvector;
    00234     public:
    00235         iterator_base() : bv_(0), position_(bm::id_max), block_(0) {}
    00236
    00237         bool operator==(const iterator_base& it) const
    00238         {
    00239             return (position_ == it.position_) && (bv_ == it.bv_);
    00240         }
    00241
    00242         bool operator!=(const iterator_base& it) const
    00243         {
    00244             return ! operator==(it);
    00245         }
    00246
    00247         bool operator < (const iterator_base& it) const
    00248         {
    00249             return position_ < it.position_;
    00250         }
    00251
    00252         bool operator <= (const iterator_base& it) const
    00253         {
    00254             return position_ <= it.position_;
    00255         }
    00256
    00257         bool operator > (const iterator_base& it) const
    00258         {
    00259             return position_ > it.position_;
    00260         }
    00261
    00262         bool operator >= (const iterator_base& it) const
    00263         {
    00264             return position_ >= it.position_;
    00265         }
    00266
    00267         /**
    00268            \fn bool bm::bvector::iterator_base::valid() const
    00269            \brief Checks if iterator is still valid. Analog of != 0 comparison for pointers.
    00270            \returns true if iterator is valid.
    00271         */
    00272         bool valid() const
    00273         {
    00274             return position_ != bm::id_max;
    00275         }
    00276
    00277         /**
    00278            \fn bool bm::bvector::iterator_base::invalidate()
    00279            \brief Turns iterator into an invalid state.
    00280         */
    00281         void invalidate()
    00282         {
    00283             position_ = bm::id_max;
    00284         }
    00285
    00286     public:
    00287
    00288         /** Information about current bitblock. */
    00289         struct bitblock_descr
    00290         {
    00291             const bm::word_t*   ptr;      //!< Word pointer.
    00292             unsigned            bits[32]; //!< Unpacked list of ON bits
    00293             unsigned            idx;      //!< Current position in the bit list
    00294             unsigned            cnt;      //!< Number of ON bits
    00295             bm::id_t            pos;      //!< Last bit position before
    00296         };
    00297
    00298         /** Information about current DGAP block. */
    00299         struct dgap_descr
    00300         {
    00301             const gap_word_t*   ptr;       //!< Word pointer.
    00302             gap_word_t          gap_len;   //!< Current dgap length.
    00303         };
    00304
    00305     protected:
    00306         bm::bvector<Alloc>*     bv_;         //!< Pointer on parent bitvector
    00307         bm::id_t                position_;   //!< Bit position (bit idx)
    00308         const bm::word_t*       block_;      //!< Block pointer.(NULL-invalid)
    00309         unsigned                block_type_; //!< Type of block. 0-Bit, 1-GAP
    00310         unsigned                block_idx_;  //!< Block index
    00311
    00312         /*! Block type dependent information for current block. */
    00313         union block_descr
    00314         {
    00315             bitblock_descr   bit_;  //!< BitBlock related info.
    00316             dgap_descr       gap_;  //!< DGAP block related info.
    00317         } bdescr_;
    00318     };
    00319
    00320     /*!
    00321         @brief Output iterator iterator designed to set "ON" bits based on
    00322         input sequence of integers (bit indeces).
    00323
    00324         STL container can be converted to bvector using this iterator
    00325         Insert iterator guarantees the vector will be dynamically resized
    00326         (set_bit does not do that).
    00327
    00328         @note
    00329         If you have many bits to set it is a good idea to use output iterator
    00330         instead of explicitly calling set, because iterator may implement
    00331         some performance specific tricks to make sure bulk insert is fast.
    00332
    00333         @ingroup bvector
    00334     */
    00335     class insert_iterator
    00336     {
    00337     public:
    00338 #ifndef BM_NO_STL
    00339         typedef std::output_iterator_tag  iterator_category;
    00340 #endif
    00341         typedef unsigned value_type;
    00342         typedef void difference_type;
    00343         typedef void pointer;
    00344         typedef void reference;
    00345
    00346         insert_iterator(bvector<Alloc>& bvect)
    00347             : bvect_(bvect),
    00348               max_bit_(bvect.size())
    00349         {
    00350         }
    00351
    00352         insert_iterator& operator=(bm::id_t n)
    00353         {
    00354             BM_ASSERT(n < bm::id_max);
    00355
    00356             if (n >= max_bit_)
    00357             {
    00358                 max_bit_ = n;
    00359                 if (n >= bvect_.size())
    00360                 {
    00361                     bvect_.resize(n + 1);
    00362                 }
    00363             }
    00364
    00365             bvect_.set(n);
    00366             return *this;
    00367         }
    00368
    00369         /*! Returns *this without doing anything (no-op) */
    00370         insert_iterator& operator*() { return *this; }
    00371         /*! Returns *this. This iterator does not move (no-op) */
    00372         insert_iterator& operator++() { return *this; }
    00373         /*! Returns *this. This iterator does not move (no-op)*/
    00374         insert_iterator& operator++(int) { return *this; }
    00375
    00376     protected:
    00377         bm::bvector<Alloc>&   bvect_;
    00378         bm::id_t              max_bit_;
    00379     };
    00380
    00381     /*!
    00382         @brief Constant input iterator designed to enumerate "ON" bits
    00383         @ingroup bvector
    00384     */
    00385     class enumerator : public iterator_base
    00386     {
    00387     public:
    00388 #ifndef BM_NO_STL
    00389         typedef std::input_iterator_tag  iterator_category;
    00390 #endif
    00391         typedef unsigned   value_type;
    00392         typedef unsigned   difference_type;
    00393         typedef unsigned*  pointer;
    00394         typedef unsigned&  reference;
    00395
    00396     public:
    00397         enumerator() : iterator_base() {}
    00398         enumerator(const bvector<Alloc>* bvect, int position)
    00399             : iterator_base()
    00400         {
    00401             this->bv_ = const_cast<bvector<Alloc>*>(bvect);
    00402             if (position == 0)
    00403             {
    00404                 go_first();
    00405             }
    00406             else
    00407             {
    00408                 this->invalidate();
    00409             }
    00410         }
    00411
    00412         bm::id_t operator*() const
    00413         {
    00414             return this->position_;
    00415         }
    00416
    00417         bm::id_t value() const
    00418         {
    00419             return this->position_;
    00420         }
    00421
    00422         enumerator& operator++()
    00423         {
    00424             return this->go_up();
    00425         }
    00426
    00427         enumerator operator++(int)
    00428         {
    00429             enumerator tmp = *this;
    00430             this->go_up();
    00431             return tmp;
    00432         }
    00433
    00434
    00435         void go_first()
    00436         {
    00437             BM_ASSERT(this->bv_);
    00438
    00439         #ifdef BMCOUNTOPT
    00440             if (this->bv_->count_is_valid_ &&
    00441                 this->bv_->count_ == 0)
    00442             {
    00443                 this->invalidate();
    00444                 return;
    00445             }
    00446         #endif
    00447
    00448             blocks_manager_type* bman = &(this->bv_->blockman_);
    00449             bm::word_t*** blk_root = bman->blocks_root();
    00450
    00451             this->block_idx_ = this->position_= 0;
    00452             unsigned i, j;
    00453
    00454             for (i = 0; i < bman->top_block_size(); ++i)
    00455             {
    00456                 bm::word_t** blk_blk = blk_root[i];
    00457
    00458                 if (blk_blk == 0) // 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
    00722     /*!
    00723         @brief Constant input iterator designed to enumerate "ON" bits
    00724         counted_enumerator keeps bitcount, ie number of ON bits starting
    00725         from the position 0 in the bit string up to the currently enumerated bit
    00726
    00727         When increment operator called current position is increased by 1.
    00728
    00729         @ingroup bvector
    00730     */
    00731     class counted_enumerator : public enumerator
    00732     {
    00733     public:
    00734 #ifndef BM_NO_STL
    00735         typedef std::input_iterator_tag  iterator_category;
    00736 #endif
    00737         counted_enumerator() : bit_count_(0){}
    00738
    00739         counted_enumerator(const enumerator& en)
    00740         : enumerator(en)
    00741         {
    00742             if (this->valid())
    00743                 bit_count_ = 1;
    00744         }
    00745
    00746         counted_enumerator& operator=(const enumerator& en)
    00747         {
    00748             enumerator* me = this;
    00749             *me = en;
    00750             if (this->valid())
    00751                 this->bit_count_ = 1;
    00752             return *this;
    00753         }
    00754
    00755         counted_enumerator& operator++()
    00756         {
    00757             this->go_up();
    00758             if (this->valid())
    00759                 ++(this->bit_count_);
    00760             return *this;
    00761         }
    00762
    00763         counted_enumerator operator++(int)
    00764         {
    00765             counted_enumerator tmp(*this);
    00766             this->go_up();
    00767             if (this->valid())
    00768                 ++bit_count_;
    00769             return tmp;
    00770         }
    00771
    00772         /*! @brief Number of bits ON starting from the .
    00773
    00774             Method returns number of ON bits fromn the bit 0 to the current bit
    00775             For the first bit in bitvector it is 1, for the second 2
    00776         */
    00777         bm::id_t count() const { return bit_count_; }
    00778
    00779     private:
    00780         bm::id_t   bit_count_;
    00781     };
    00782
    00783     friend class iterator_base;
    00784     friend class enumerator;
    00785
    00786 public:
    00787
    00788 #ifdef BMCOUNTOPT
    00789     bvector(strategy          strat      = BM_BIT,
    00790             const gap_word_t* glevel_len = bm::gap_len_table<true>::_len,
    00791             size_type         bv_size    = bm::id_max,
    00792             const Alloc&      alloc      = Alloc())
    00793     : count_(0),
    00794       count_is_valid_(true),
    00795       blockman_(glevel_len, bv_size, alloc),
    00796       new_blocks_strat_(strat),
    00797       size_(bv_size)
    00798     {}
    00799
    00800     bvector(size_type         bv_size,
    00801             bm::strategy      strat      = BM_BIT,
    00802             const gap_word_t* glevel_len = bm::gap_len_table<true>::_len,
    00803             const Alloc&      alloc = Alloc())
    00804     : count_(0),
    00805       count_is_valid_(true),
    00806       blockman_(glevel_len, bv_size, alloc),
    00807       new_blocks_strat_(strat),
    00808       size_(bv_size)
    00809     {}
    00810
    00811
    00812     bvector(const bm::bvector<Alloc>& bvect)
    00813      : count_(bvect.count_),
    00814        count_is_valid_(bvect.count_is_valid_),
    00815        blockman_(bvect.blockman_),
    00816        new_blocks_strat_(bvect.new_blocks_strat_),
    00817        size_(bvect.size_)
    00818     {}
    00819
    00820 #else
    00821     /*!
    00822         \brief Constructs bvector class
    00823         \param strat - operation mode strategy,
    00824                        BM_BIT - default strategy, bvector use plain bitset
    00825                        blocks, (performance oriented strategy).
    00826                        BM_GAP - memory effitent strategy, bvector allocates
    00827                        blocks as array of intervals(gaps) and convert blocks
    00828                        into plain bitsets only when enthropy grows.
    00829         \param glevel_len
    00830            - pointer on C-style array keeping GAP block sizes.
    00831             (Put bm::gap_len_table_min<true>::_len for GAP memory saving mode)
    00832         \param bv_size
    00833           - bvector size (number of bits addressable by bvector), bm::id_max means
    00834           "no limits" (recommended).
    00835           bit vector allocates this space dynamically on demand.
    00836
    00837         \sa bm::gap_len_table bm::gap_len_table_min set_new_blocks_strat
    00838     */
    00839     bvector(strategy          strat      = BM_BIT,
    00840             const gap_word_t* glevel_len = bm::gap_len_table<true>::_len,
    00841             size_type         bv_size    = bm::id_max,
    00842             const Alloc&      alloc      = Alloc())
    00843     : blockman_(glevel_len, bv_size, alloc),
    00844       new_blocks_strat_(strat),
    00845       size_(bv_size)
    00846     {}
    00847
    00848     /*!
    00849         \brief Constructs bvector class
    00850     */
    00851     bvector(size_type         bv_size,
    00852             strategy          strat      = BM_BIT,
    00853             const gap_word_t* glevel_len = bm::gap_len_table<true>::_len,
    00854             const Alloc&      alloc      = Alloc())
    00855     : blockman_(glevel_len, bv_size, alloc),
    00856       new_blocks_strat_(strat),
    00857       size_(bv_size)
    00858     {}
    00859
    00860
    00861     bvector(const bvector<Alloc>& bvect)
    00862         :  blockman_(bvect.blockman_),
    00863            new_blocks_strat_(bvect.new_blocks_strat_),
    00864            size_(bvect.size_)
    00865     {}
    00866
    00867 #endif
    00868
    00869     bvector& operator=(const bvector<Alloc>& bvect)
    00870     {
    00871         clear(true); // 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
    00951     /*!
    00952        \brief Sets bit n.
    00953        \param n - index of the bit to be set.
    00954        \param val - new bit value
    00955        \return  TRUE if bit was changed
    00956     */
    00957     bool set_bit(bm::id_t n, bool val = true)
    00958     {
    00959         BM_ASSERT(n < size_);
    00960         return set_bit_no_check(n, val);
    00961     }
    00962
    00963     /*!
    00964        \brief Sets bit n using bit AND with the provided value.
    00965        \param n - index of the bit to be set.
    00966        \param val - new bit value
    00967        \return  TRUE if bit was changed
    00968     */
    00969     bool set_bit_and(bm::id_t n, bool val = true)
    00970     {
    00971         BM_ASSERT(n < size_);
    00972         return and_bit_no_check(n, val);
    00973     }
    00974
    00975     /*!
    00976        \brief Sets bit n only if current value is equal to the condition
    00977        \param n - index of the bit to be set.
    00978        \param val - new bit value
    00979        \param condition - expected current value
    00980        \return TRUE if bit was changed
    00981     */
    00982     bool set_bit_conditional(bm::id_t n, bool val, bool condition)
    00983     {
    00984         BM_ASSERT(n < size_);
    00985         if (val == condition) return false;
    00986         return set_bit_conditional_impl(n, val, condition);
    00987     }
    00988
    00989
    00990     /*!
    00991         \brief Sets bit n if val is true, clears bit n if val is false
    00992         \param n - index of the bit to be set
    00993         \param val - new bit value
    00994         \return *this
    00995     */
    00996     bvector<Alloc>& set(bm::id_t n, bool val = true)
    00997     {
    00998         set_bit(n, val);
    00999         return *this;
    01000     }
    01001
    01002
    01003
    01004     /*!
    01005        \brief Sets every bit in this bitset to 1.
    01006        \return *this
    01007     */
    01008     bvector<Alloc>& set()
    01009     {
    01010         BMCOUNT_VALID(false)
    01011         set_range(0, size_ - 1, true);
    01012         return *this;
    01013     }
    01014
    01015
    01016     /*!
    01017         \brief Sets all bits in the specified closed interval [left,right]
    01018         Interval must be inside the bvector's size.
    01019         This method DOES NOT resize vector.
    01020
    01021         \param left  - interval start
    01022         \param right - interval end (closed interval)
    01023         \param value - value to set interval in
    01024
    01025         \return *this
    01026     */
    01027     bvector<Alloc>& set_range(bm::id_t left,
    01028                               bm::id_t right,
    01029                               bool     value = true);
    01030
    01031
    01032     /*! Function erturns insert iterator for this bitvector */
    01033     insert_iterator inserter()
    01034     {
    01035         return insert_iterator(*this);
    01036     }
    01037
    01038
    01039     /*!
    01040        \brief Clears bit n.
    01041        \param n - bit's index to be cleaned.
    01042     */
    01043     void clear_bit(bm::id_t n)
    01044     {
    01045         set(n, false);
    01046     }
    01047
    01048
    01049     /*!
    01050        \brief Clears every bit in the bitvector.
    01051
    01052        \param free_mem if "true" (default) bvector frees the memory,
    01053        otherwise sets blocks to 0.
    01054     */
    01055     void clear(bool free_mem = false)
    01056     {
    01057         blockman_.set_all_zero(free_mem);
    01058         BMCOUNT_SET(0);
    01059     }
    01060
    01061     /*!
    01062        \brief Clears every bit in the bitvector.
    01063        \return *this;
    01064     */
    01065     bvector<Alloc>& reset()
    01066     {
    01067         clear();
    01068         return *this;
    01069     }
    01070
    01071
    01072     /*!
    01073        \brief Returns count of bits which are 1.
    01074        \return Total number of bits ON.
    01075     */
    01076     bm::id_t count() const;
    01077
    01078     /**
    01079         \brief Returns bvector's capacity (number of bits it can store)
    01080     */
    01081     size_type capacity() const
    01082     {
    01083         return blockman_.capacity();
    01084     }
    01085
    01086     /*!
    01087         \brief return current size of the vector (bits)
    01088     */
    01089     size_type size() const
    01090     {
    01091         return size_;
    01092     }
    01093
    01094     /*!
    01095         \brief Change size of the bvector
    01096         \param new_size - new size in bits
    01097     */
    01098     void resize(size_type new_size);
    01099
    01100     /*! \brief Computes bitcount values for all bvector blocks
    01101         \param arr - pointer on array of block bit counts
    01102         \return Index of the last block counted.
    01103         This number +1 gives you number of arr elements initialized during the
    01104         function call.
    01105     */
    01106     unsigned count_blocks(unsigned* arr) const
    01107     {
    01108         bm::word_t*** blk_root = blockman_.get_rootblock();
    01109         typename blocks_manager_type::block_count_arr_func func(blockman_, &(arr[0]));
    01110         for_each_nzblock(blk_root, blockman_.effective_top_block_size(),
    01111                          func);
    01112         return func.last_block();
    01113     }
    01114
    01115     /*!
    01116        \brief Returns count of 1 bits in the given diapason.
    01117        \param left - index of first bit start counting from
    01118        \param right - index of last bit
    01119        \param block_count_arr - optional parameter (bitcount by bvector blocks)
    01120               calculated by count_blocks method. Used to improve performance of
    01121               wide range searches
    01122        \return Total number of bits ON.
    01123     */
    01124     bm::id_t count_range(bm::id_t left,
    01125                          bm::id_t right,
    01126                          unsigned* block_count_arr=0) const;
    01127
    01128
    01129     bm::id_t recalc_count()
    01130     {
    01131         BMCOUNT_VALID(false)
    01132         return count();
    01133     }
    01134
    01135     /*!
    01136         Disables count cache. Next call to count() or recalc_count()
    01137         restores count caching.
    01138
    01139         @note Works only if BMCOUNTOPT enabled(defined).
    01140         Othewise does nothing.
    01141     */
    01142     void forget_count()
    01143     {
    01144         BMCOUNT_VALID(false)
    01145     }
    01146
    01147     /*!
    01148         \brief Inverts all bits.
    01149     */
    01150     bvector<Alloc>& invert();
    01151
    01152
    01153     /*!
    01154        \brief returns true if bit n is set and false is bit n is 0.
    01155        \param n - Index of the bit to check.
    01156        \return Bit value (1 or 0)
    01157     */
    01158     bool get_bit(bm::id_t n) const;
    01159
    01160     /*!
    01161        \brief returns true if bit n is set and false is bit n is 0.
    01162        \param n - Index of the bit to check.
    01163        \return Bit value (1 or 0)
    01164     */
    01165     bool test(bm::id_t n) const
    01166     {
    01167         return get_bit(n);
    01168     }
    01169
    01170     /*!
    01171        \brief Returns true if any bits in this bitset are set, and otherwise returns false.
    01172        \return true if any bit is set
    01173     */
    01174     bool any() const
    01175     {
    01176     #ifdef BMCOUNTOPT
    01177         if (count_is_valid_ && count_) return true;
    01178     #endif
    01179
    01180         word_t*** blk_root = blockman_.get_rootblock();
    01181         if (!blk_root)
    01182             return false;
    01183         typename blocks_manager_type::block_any_func func(blockman_);
    01184         return for_each_nzblock_if(blk_root,
    01185                                    blockman_.effective_top_block_size(),
    01186                                    func);
    01187     }
    01188
    01189     /*!
    01190         \brief Returns true if no bits are set, otherwise returns false.
    01191     */
    01192     bool none() const
    01193     {
    01194         return !any();
    01195     }
    01196
    01197     /*!
    01198        \brief Flips bit n
    01199        \return *this
    01200     */
    01201     bvector<Alloc>& flip(bm::id_t n)
    01202     {
    01203         set(n, !get_bit(n));
    01204         return *this;
    01205     }
    01206
    01207     /*!
    01208        \brief Flips all bits
    01209        \return *this
    01210     */
    01211     bvector<Alloc>& flip()
    01212     {
    01213         return invert();
    01214     }
    01215
    01216     /*! \brief Exchanges content of bv and this bitvector.
    01217     */
    01218     void swap(bvector<Alloc>& bv)
    01219     {
    01220         if (this != &bv)
    01221         {
    01222             blockman_.swap(bv.blockman_);
    01223             bm::xor_swap(size_,bv.size_);
    01224     #ifdef BMCOUNTOPT
    01225             BMCOUNT_VALID(false)
    01226             bv.recalc_count();
    01227     #endif
    01228         }
    01229     }
    01230
    01231
    01232     /*!
    01233        \fn bm::id_t bvector::get_first() const
    01234        \brief Gets number of first bit which is ON.
    01235        \return Index of the first 1 bit.
    01236        \sa get_next, extract_next
    01237     */
    01238     bm::id_t get_first() const { return check_or_next(0); }
    01239
    01240     /*!
    01241        \fn bm::id_t bvector::get_next(bm::id_t prev) const
    01242        \brief Finds the number of the next bit ON.
    01243        \param prev - Index of the previously found bit.
    01244        \return Index of the next bit which is ON or 0 if not found.
    01245        \sa get_first, extract_next
    01246     */
    01247     bm::id_t get_next(bm::id_t prev) const
    01248     {
    01249         return (++prev == bm::id_max) ? 0 : check_or_next(prev);
    01250     }
    01251
    01252     /*!
    01253        \fn bm::id_t bvector::extract_next(bm::id_t prev)
    01254        \brief Finds the number of the next bit ON and sets it to 0.
    01255        \param prev - Index of the previously found bit.
    01256        \return Index of the next bit which is ON or 0 if not found.
    01257        \sa get_first, get_next,
    01258     */
    01259     bm::id_t extract_next(bm::id_t prev)
    01260     {
    01261         return (++prev == bm::id_max) ? 0 : check_or_next_extract(prev);
    01262     }
    01263
    01264
    01265     /*!
    01266        @brief Calculates bitvector statistics.
    01267
    01268        @param st - pointer on statistics structure to be filled in.
    01269
    01270        Function fills statistics structure containing information about how
    01271        this vector uses memory and estimation of max. amount of memory
    01272        bvector needs to serialize itself.
    01273
    01274        @sa statistics
    01275     */
    01276     void calc_stat(struct bm::bvector<Alloc>::statistics* st) const;
    01277
    01278     /*!
    01279        \brief Logical OR operation.
    01280        \param vect - Argument vector.
    01281     */
    01282     bm::bvector<Alloc>& bit_or(const  bm::bvector<Alloc>& vect)
    01283     {
    01284         BMCOUNT_VALID(false);
    01285         combine_operation(vect, BM_OR);
    01286         return *this;
    01287     }
    01288
    01289     /*!
    01290        \brief Logical AND operation.
    01291        \param vect - Argument vector.
    01292     */
    01293     bm::bvector<Alloc>& bit_and(const bm::bvector<Alloc>& vect)
    01294     {
    01295         BMCOUNT_VALID(false);
    01296         combine_operation(vect, BM_AND);
    01297         return *this;
    01298     }
    01299
    01300     /*!
    01301        \brief Logical XOR operation.
    01302        \param vect - Argument vector.
    01303     */
    01304     bm::bvector<Alloc>& bit_xor(const bm::bvector<Alloc>& vect)
    01305     {
    01306         BMCOUNT_VALID(false);
    01307         combine_operation(vect, BM_XOR);
    01308         return *this;
    01309     }
    01310
    01311     /*!
    01312        \brief Logical SUB operation.
    01313        \param vect - Argument vector.
    01314     */
    01315     bm::bvector<Alloc>& bit_sub(const bm::bvector<Alloc>& vect)
    01316     {
    01317         BMCOUNT_VALID(false);
    01318         combine_operation(vect, BM_SUB);
    01319         return *this;
    01320     }
    01321
    01322
    01323     /*!
    01324        \brief Sets new blocks allocation strategy.
    01325        \param strat - Strategy code 0 - bitblocks allocation only.
    01326                       1 - Blocks mutation mode (adaptive algorithm)
    01327     */
    01328     void set_new_blocks_strat(strategy strat)
    01329     {
    01330         new_blocks_strat_ = strat;
    01331     }
    01332
    01333     /*!
    01334        \brief Returns blocks allocation strategy.
    01335        \return - Strategy code 0 - bitblocks allocation only.
    01336                  1 - Blocks mutation mode (adaptive algorithm)
    01337        \sa set_new_blocks_strat
    01338     */
    01339     strategy  get_new_blocks_strat() const
    01340     {
    01341         return new_blocks_strat_;
    01342     }
    01343
    01344
    01345     /*!
    01346         \brief Optimization mode
    01347         Every next level means additional checks (better compression vs time)
    01348         \sa optimize
    01349     */
    01350     enum optmode
    01351     {
    01352         opt_free_0    = 1, ///< Free unused 0 blocks
    01353         opt_free_01   = 2, ///< Free unused 0 and 1 blocks
    01354         opt_compress  = 3  ///< compress blocks when possible
    01355     };
    01356
    01357     /*!
    01358        \brief Optimize memory bitvector's memory allocation.
    01359
    01360        Function analyze all blocks in the bitvector, compresses blocks
    01361        with a regular structure, frees some memory. This function is recommended
    01362        after a bulk modification of the bitvector using set_bit, clear_bit or
    01363        logical operations.
    01364
    01365        Optionally function can calculate vector post optimization statistics
    01366
    01367        @sa optmode, optimize_gap_size
    01368     */
    01369     void optimize(bm::word_t* temp_block = 0,
    01370                   optmode opt_mode       = opt_compress,
    01371                   statistics* stat       = 0);
    01372
    01373     /*!
    01374        \brief Optimize sizes of GAP blocks
    01375
    01376        This method runs an analysis to find optimal GAP levels for the
    01377        specific vector. Current GAP compression algorithm uses several fixed
    01378        GAP sizes. By default bvector uses some reasonable preset.
    01379     */
    01380     void optimize_gap_size();
    01381
    01382
    01383     /*!
    01384         @brief Sets new GAP lengths table. All GAP blocks will be reallocated
    01385         to match the new scheme.
    01386
    01387         @param glevel_len - pointer on C-style array keeping GAP block sizes.
    01388     */
    01389     void set_gap_levels(const gap_word_t* glevel_len);
    01390
    01391     /*!
    01392         \brief Lexicographical comparison with a bitvector.
    01393
    01394         Function compares current bitvector with the provided argument
    01395         bit by bit and returns -1 if our bitvector less than the argument,
    01396         1 - greater, 0 - equal.
    01397     */
    01398     int compare(const bvector<Alloc>& bvect) const;
    01399
    01400     /*! @brief Allocates temporary block of memory.
    01401
    01402         Temp block can be passed to bvector functions requiring some temp memory
    01403         for their operation. (like serialize)
    01404
    01405         @note method is marked const, but it's not quite true, since
    01406         it can in some cases modify the state of the block allocator
    01407         (if it has a state). (Can be important in MT programs).
    01408
    01409         @sa free_tempblock
    01410     */
    01411     bm::word_t* allocate_tempblock() const
    01412     {
    01413         blocks_manager_type* bm =
    01414             const_cast<blocks_manager_type*>(&blockman_);
    01415         return bm->get_allocator().alloc_bit_block();
    01416     }
    01417
    01418     /*! @brief Frees temporary block of memory.
    01419
    01420         @note method is marked const, but it's not quite true, since
    01421         it can in some cases modify the state of the block allocator
    01422         (if it has a state). (Can be important in MT programs).
    01423
    01424         @sa allocate_tempblock
    01425     */
    01426     void free_tempblock(bm::word_t* block) const
    01427     {
    01428         blocks_manager_type* bm =
    01429             const_cast<blocks_manager_type*>(&blockman_);
    01430         bm->get_allocator().free_bit_block(block);
    01431     }
    01432
    01433     /**
    01434        \brief Returns enumerator pointing on the first non-zero bit.
    01435     */
    01436     enumerator first() const
    01437     {
    01438         typedef typename bvector<Alloc>::enumerator enumerator_type;
    01439         return enumerator_type(this, 0);
    01440     }
    01441
    01442     /**
    01443        \fn bvector::enumerator bvector::end() const
    01444        \brief Returns enumerator pointing on the next bit after the last.
    01445     */
    01446     enumerator end() const
    01447     {
    01448         typedef typename bvector<Alloc>::enumerator enumerator_type;
    01449         return enumerator_type(this, 1);
    01450     }
    01451
    01452
    01453     const bm::word_t* get_block(unsigned nb) const
    01454     {
    01455         return blockman_.get_block(nb);
    01456     }
    01457
    01458     void combine_operation(const bm::bvector<Alloc>& bvect,
    01459                             bm::operation            opcode);
    01460
    01461 private:
    01462
    01463     bm::id_t check_or_next(bm::id_t prev) const;
    01464
    01465     /// check if specified bit is 1, and set it to 0
    01466     /// if specified bit is 0, scan for the next 1 and returns it
    01467     /// if no 1 found returns 0
    01468     bm::id_t check_or_next_extract(bm::id_t prev);
    01469
    01470     /**
    01471         \brief Set specified bit without checking preconditions (size, etc)
    01472     */
    01473     bool set_bit_no_check(bm::id_t n, bool val);
    01474
    01475     /**
    01476         \brief AND specified bit without checking preconditions (size, etc)
    01477     */
    01478     bool and_bit_no_check(bm::id_t n, bool val);
    01479
    01480     bool set_bit_conditional_impl(bm::id_t n, bool val, bool condition);
    01481
    01482
    01483     void combine_operation_with_block(unsigned nb,
    01484                                       unsigned gap,
    01485                                       bm::word_t* blk,
    01486                                       const bm::word_t* arg_blk,
    01487                                       int arg_gap,
    01488                                       bm::operation opcode);
    01489 public:
    01490     void combine_operation_with_block(unsigned nb,
    01491                                       const bm::word_t* arg_blk,
    01492                                       int arg_gap,
    01493                                       bm::operation opcode)
    01494     {
    01495         bm::word_t* blk = const_cast<bm::word_t*>(get_block(nb));
    01496         bool gap = BM_IS_GAP(blk);
    01497         combine_operation_with_block(nb, gap, blk, arg_blk, arg_gap, opcode);
    01498     }
    01499 private:
    01500     void combine_count_operation_with_block(unsigned nb,
    01501                                             const bm::word_t* arg_blk,
    01502                                             int arg_gap,
    01503                                             bm::operation opcode)
    01504     {
    01505         const bm::word_t* blk = get_block(nb);
    01506         bool gap = BM_IS_GAP(blk);
    01507         combine_count_operation_with_block(nb, gap, blk, arg_blk, arg_gap, opcode);
    01508     }
    01509
    01510
    01511     /**
    01512        \brief Extends GAP block to the next level or converts it to bit block.
    01513        \param nb - Block's linear index.
    01514        \param blk - Blocks's pointer
    01515     */
    01516     void extend_gap_block(unsigned nb, gap_word_t* blk)
    01517     {
    01518         blockman_.extend_gap_block(nb, blk);
    01519     }
    01520
    01521     /**
    01522        \brief Set range without validity checking
    01523     */
    01524     void set_range_no_check(bm::id_t left,
    01525                             bm::id_t right,
    01526                             bool     value);
    01527 public:
    01528
    01529     const blocks_manager_type& get_blocks_manager() const
    01530     {
    01531         return blockman_;
    01532     }
    01533
    01534     blocks_manager_type& get_blocks_manager()
    01535     {
    01536         return blockman_;
    01537     }
    01538
    01539
    01540 private:
    01541
    01542 // 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_;            //!< number of 1 bits in the vector
    01546     mutable bool      count_is_valid_;   //!< actualization flag
    01547 #endif
    01548
    01549     blocks_manager_type  blockman_;         //!< bitblocks manager
    01550     strategy             new_blocks_strat_; //!< block allocation strategy
    01551     size_type            size_;             //!< size in bits
    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