dlvhex  2.5.0
vs12/bm/bmblocks.h
Go to the documentation of this file.
00001 #ifndef BM_BLOCKS__H__INCLUDED__
00002 #define BM_BLOCKS__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 #include "bmfwd.h"
00031 
00032 #ifdef _MSC_VER
00033 #pragma warning( push )
00034 #pragma warning( disable : 4100)
00035 #endif
00036 
00037 
00038 namespace bm
00039 {
00040 
00041 
00050 template<class Alloc/*, class MS*/> 
00051 class blocks_manager
00052 {
00053 public:
00054 
00055     typedef Alloc allocator_type;
00056 
00058     class bm_func_base
00059     {
00060     public:
00061         bm_func_base(blocks_manager& bman) : bm_(bman) {}
00062 
00063         void on_empty_top(unsigned /* top_block_idx*/ ) {}
00064         void on_empty_block(unsigned /* block_idx*/ ) {}
00065     private:
00066         bm_func_base(const bm_func_base&);
00067         bm_func_base& operator=(const bm_func_base&);
00068     protected:
00069         blocks_manager&  bm_;
00070     };
00071 
00072 
00074     class bm_func_base_const
00075     {
00076     public:
00077         bm_func_base_const(const blocks_manager& bman) : bm_(bman) {}
00078 
00079         void on_empty_top(unsigned /* top_block_idx*/ ) {}
00080         void on_empty_block(unsigned /* block_idx*/ ) {}
00081     private:
00082         bm_func_base_const(const bm_func_base_const&);
00083         bm_func_base_const& operator=(const bm_func_base_const&);
00084     protected:
00085         const blocks_manager&  bm_;
00086     };
00087 
00088 
00090     class block_count_base : public bm_func_base_const
00091     {
00092     protected:
00093         block_count_base(const blocks_manager& bm) 
00094             : bm_func_base_const(bm) {}
00095 
00096         bm::id_t block_count(const bm::word_t* block) const
00097         {
00098             return this->bm_.block_bitcount(block);
00099         }
00100     };
00101 
00102 
00104     class block_count_func : public block_count_base
00105     {
00106     public:
00107         block_count_func(const blocks_manager& bm) 
00108             : block_count_base(bm), count_(0) {}
00109 
00110         bm::id_t count() const { return count_; }
00111 
00112         void operator()(const bm::word_t* block)
00113         {
00114             count_ += this->block_count(block);
00115         }
00116 
00117     private:
00118         bm::id_t count_;
00119     };
00120 
00121 
00123     class block_count_arr_func : public block_count_base
00124     {
00125     public:
00126         block_count_arr_func(const blocks_manager& bm, unsigned* arr) 
00127             : block_count_base(bm), arr_(arr), last_idx_(0) 
00128         {
00129             arr_[0] = 0;
00130         }
00131 
00132         void operator()(const bm::word_t* block, unsigned idx)
00133         {
00134             while (++last_idx_ < idx)
00135             {
00136                 arr_[last_idx_] = 0;
00137             }
00138             arr_[idx] = this->block_count(block);
00139             last_idx_ = idx;
00140         }
00141 
00142         unsigned last_block() const { return last_idx_; }
00143 
00144     private:
00145         unsigned*  arr_;
00146         unsigned   last_idx_;
00147     };
00148 
00150     class block_count_change_func : public bm_func_base_const
00151     {
00152     public:
00153         block_count_change_func(const blocks_manager& bm) 
00154             : bm_func_base_const(bm),
00155                 count_(0),
00156                 prev_block_border_bit_(0)
00157         {}
00158 
00159         bm::id_t block_count(const bm::word_t* block, unsigned idx)
00160         {
00161             bm::id_t count = 0;
00162             bm::id_t first_bit;
00163             
00164             if (IS_FULL_BLOCK(block) || (block == 0))
00165             {
00166                 count = 1;
00167                 if (idx)
00168                 {
00169                     first_bit = block ? 1 : 0;
00170                     count -= !(prev_block_border_bit_ ^ first_bit);
00171                 }
00172                 prev_block_border_bit_ = block ? 1 : 0;
00173             }
00174             else
00175             {
00176                 if (BM_IS_GAP(block))
00177                 {
00178                     gap_word_t* gap_block = BMGAP_PTR(block);
00179                     count = gap_length(gap_block) - 1;
00180                     if (idx)
00181                     {
00182                         first_bit = gap_test(gap_block, 0);
00183                         count -= !(prev_block_border_bit_ ^ first_bit);
00184                     }
00185                         
00186                     prev_block_border_bit_ = 
00187                         gap_test(gap_block, gap_max_bits-1);
00188                 }
00189                 else // bitset
00190                 {
00191                     unsigned bit_count;
00192                     count = bit_block_calc_count_change(block,
00193                                                 block + bm::set_block_size,
00194                                                 &bit_count);
00195                     if (idx)
00196                     {
00197                         first_bit = block[0] & 1;
00198                         count -= !(prev_block_border_bit_ ^ first_bit);
00199                     }
00200                     prev_block_border_bit_ = 
00201                         block[set_block_size-1] >> ((sizeof(block[0]) * 8) - 1);
00202                     
00203                 }
00204             }
00205             return count;
00206         }
00207         
00208         bm::id_t count() const { return count_; }
00209 
00210         void operator()(const bm::word_t* block, unsigned idx)
00211         {
00212             count_ += block_count(block, idx);
00213         }
00214 
00215     private:
00216         bm::id_t   count_;
00217         bm::id_t   prev_block_border_bit_;
00218     };
00219 
00220 
00222     class block_any_func : public bm_func_base_const
00223     {
00224     public:
00225         block_any_func(const blocks_manager& bm) 
00226             : bm_func_base_const(bm) 
00227         {}
00228 
00229         bool operator()(const bm::word_t* block, unsigned idx)
00230         {
00231             if (IS_FULL_BLOCK(block)) return true;
00232 
00233             if (BM_IS_GAP(block)) // gap block
00234             {
00235                 if (!gap_is_all_zero(BMGAP_PTR(block), bm::gap_max_bits))
00236                 {
00237                     return true;
00238                 }
00239             }
00240             else  // bitset
00241             {
00242                 bm::wordop_t* blk1 = (wordop_t*)block;
00243                 bm::wordop_t* blk2 = 
00244                     (wordop_t*)(block + bm::set_block_size);
00245                 if (!bit_is_all_zero(blk1, blk2))
00246                 {
00247                     return true;
00248                 }
00249             }
00250             return false;
00251         }
00252     };
00253 
00255     class gap_level_func : public bm_func_base
00256     {
00257     public:
00258         gap_level_func(blocks_manager& bm, const gap_word_t* glevel_len)
00259             : bm_func_base(bm),
00260                 glevel_len_(glevel_len)
00261         {
00262             BM_ASSERT(glevel_len);
00263         }
00264 
00265         void operator()(bm::word_t* block, unsigned idx)
00266         {
00267             blocks_manager& bman = this->bm_;
00268             
00269             if (!BM_IS_GAP(block))
00270                 return;
00271 
00272             gap_word_t* gap_blk = BMGAP_PTR(block);
00273 
00274             // TODO: Use the same code as in the optimize functor
00275             if (gap_is_all_zero(gap_blk, bm::gap_max_bits))
00276             {
00277                 bman.set_block_ptr(idx, 0);
00278                 goto free_block;
00279             }
00280             else 
00281             if (gap_is_all_one(gap_blk, bm::gap_max_bits))
00282             {
00283                 bman.set_block_ptr(idx, FULL_BLOCK_ADDR);
00284             free_block:
00285                 bman.get_allocator().free_gap_block(gap_blk, 
00286                                                     bman.glen());
00287                 bman.set_block_bit(idx);
00288                 return;
00289             }
00290 
00291             unsigned len = gap_length(gap_blk);
00292             int level = gap_calc_level(len, glevel_len_);
00293             if (level == -1)
00294             {
00295                 bm::word_t* blk = 
00296                     bman.get_allocator().alloc_bit_block();
00297                 bman.set_block_ptr(idx, blk);
00298                 bman.set_block_bit(idx);
00299                 gap_convert_to_bitset(blk, gap_blk);
00300             }
00301             else
00302             {
00303                 gap_word_t* gap_blk_new = 
00304                     bman.allocate_gap_block(level, gap_blk, glevel_len_);
00305 
00306                 bm::word_t* p = (bm::word_t*) gap_blk_new;
00307                 BMSET_PTRGAP(p);
00308                 bman.set_block_ptr(idx, p);
00309             }
00310             bman.get_allocator().free_gap_block(gap_blk, bman.glen());
00311         }
00312 
00313     private:
00314         const gap_word_t* glevel_len_;
00315     };
00316 
00317 
00319     class block_opt_func : public bm_func_base
00320     {
00321     public:
00322         block_opt_func(blocks_manager& bm, 
00323                         bm::word_t*     temp_block,
00324                         int             opt_mode,
00325                         bv_statistics*  bv_stat=0) 
00326             : bm_func_base(bm),
00327               temp_block_(temp_block),
00328               opt_mode_(opt_mode),
00329               stat_(bv_stat),
00330               empty_(0)
00331         {
00332             BM_ASSERT(temp_block);
00333         }
00334 
00335         void on_empty_top(unsigned i)
00336         {
00337             bm::word_t*** blk_root = this->bm_.get_rootblock();
00338             bm::word_t** blk_blk = blk_root[i];
00339             if (blk_blk) 
00340             {
00341                 this->bm_.get_allocator().free_ptr(blk_blk);
00342                 blk_root[i] = 0;
00343             }
00344             if (stat_)
00345             {
00346                 stat_->max_serialize_mem += sizeof(unsigned) + 1;
00347             }
00348         }
00349         void on_empty_block(unsigned /* block_idx*/ ) { ++empty_; }
00350 
00351         void operator()(bm::word_t* block, unsigned idx)
00352         {
00353             blocks_manager& bman = this->bm_;
00354             if (IS_FULL_BLOCK(block)) 
00355             {
00356                 ++empty_;
00357                 return;
00358             }
00359 
00360             if (stat_) 
00361             {
00362                 stat_->max_serialize_mem += empty_ << 2;
00363                 empty_ = 0;
00364             }
00365 
00366             gap_word_t* gap_blk;
00367             if (BM_IS_GAP(block)) // gap block
00368             {
00369                 gap_blk = BMGAP_PTR(block);
00370                 // check if block is empty (or all 1)
00371                 if (gap_is_all_zero(gap_blk, bm::gap_max_bits))
00372                 {
00373                     bman.set_block_ptr(idx, 0);
00374                     this->free_block(gap_blk, idx);
00375                     ++empty_;
00376                 }
00377                 else 
00378                 if (gap_is_all_one(gap_blk, bm::gap_max_bits))
00379                 {
00380                     bman.set_block_ptr(idx, FULL_BLOCK_ADDR);
00381                     this->free_block(gap_blk, idx);
00382                     ++empty_;
00383                 }
00384                 else
00385                 {
00386                     // regular gap block - compute statistics
00387                     if (stat_)
00388                     {
00389                         stat_->add_gap_block(
00390                                     bm::gap_capacity(gap_blk, bman.glen()),
00391                                     bm::gap_length(gap_blk));
00392                     }
00393                 }
00394             }
00395             else // bit block
00396             {
00397                 if (opt_mode_ < 3) // free_01 optimization
00398                 {  
00399                     bm::wordop_t* blk1 = (wordop_t*)block;
00400                     bm::wordop_t* blk2 = 
00401                         (wordop_t*)(block + bm::set_block_size);
00402                 
00403                     bool b = bit_is_all_zero(blk1, blk2);
00404                     if (b)
00405                     {
00406                         bman.get_allocator().free_bit_block(block);
00407                         bman.set_block_ptr(idx, 0);
00408                         ++empty_;
00409                     } 
00410                     else
00411                     if (opt_mode_ == 2) // check if it is all 1 block
00412                     {
00413                         b = is_bits_one(blk1, blk2);
00414                         if (b) 
00415                         {
00416                             bman.get_allocator().free_bit_block(block);
00417                             bman.set_block_ptr(idx, FULL_BLOCK_ADDR);
00418                             ++empty_;
00419                         }
00420                     }
00421 
00422                     if (!b && stat_)
00423                         stat_->add_bit_block();
00424 
00425                     return;
00426                 }
00427             
00428                 // try to compress
00429             
00430                 gap_word_t* tmp_gap_blk = (gap_word_t*)temp_block_;
00431                 *tmp_gap_blk = bm::gap_max_level << 1;
00432 
00433                 unsigned threashold = bman.glen(bm::gap_max_level)-4;
00434 
00435                 unsigned len = bit_convert_to_gap(tmp_gap_blk, 
00436                                                     block, 
00437                                                     bm::gap_max_bits, 
00438                                                     threashold);
00439                 if (len)    // compression successful                
00440                 {                
00441                     bman.get_allocator().free_bit_block(block);
00442 
00443                     // check if new gap block can be eliminated
00444                     if (gap_is_all_zero(tmp_gap_blk, bm::gap_max_bits))
00445                     {
00446                         bman.set_block_ptr(idx, 0);
00447                         ++empty_;
00448                     }
00449                     else if (gap_is_all_one(tmp_gap_blk, bm::gap_max_bits))
00450                     {
00451                         bman.set_block_ptr(idx, FULL_BLOCK_ADDR);
00452                         ++empty_;
00453                     }
00454                     else
00455                     {
00456                         int level = bm::gap_calc_level(len, bman.glen());
00457 
00458                         gap_blk = 
00459                             bman.allocate_gap_block(level, tmp_gap_blk);
00460                         bman.set_block_ptr(idx, (bm::word_t*)gap_blk);
00461                         bman.set_block_gap(idx);
00462                         if (stat_)
00463                         {
00464                             stat_->add_gap_block(
00465                                     bm::gap_capacity(gap_blk, bman.glen()),
00466                                     bm::gap_length(gap_blk));
00467                         }
00468                     }
00469                 }  
00470                 else  // non-compressable bit-block
00471                 {
00472                     if (stat_)
00473                         stat_->add_bit_block();
00474                 }
00475             }
00476         }
00477     private:
00478         void free_block(gap_word_t* gap_blk, unsigned idx)
00479         {
00480             this->bm_.get_allocator().free_gap_block(gap_blk,
00481                                                      this->bm_.glen());
00482             this->bm_.set_block_bit(idx);
00483         }
00484 
00485     private:
00486         bm::word_t*         temp_block_;
00487         int                 opt_mode_;
00488         bv_statistics*      stat_;
00489         unsigned            empty_;
00490     };
00491 
00493     class block_invert_func : public bm_func_base
00494     {
00495     public:
00496         block_invert_func(blocks_manager& bm) 
00497             : bm_func_base(bm) {}
00498 
00499         void operator()(bm::word_t* block, unsigned idx)
00500         {
00501             if (!block)
00502             {
00503                 this->bm_.set_block(idx, FULL_BLOCK_ADDR);
00504             }
00505             else
00506             if (IS_FULL_BLOCK(block))
00507             {
00508                 this->bm_.set_block_ptr(idx, 0);
00509             }
00510             else
00511             {
00512                 if (BM_IS_GAP(block)) // gap block
00513                 {
00514                     gap_invert(BMGAP_PTR(block));
00515                 }
00516                 else  // bit block
00517                 {
00518                     bm::wordop_t* wrd_ptr = (wordop_t*) block;
00519                     bm::wordop_t* wrd_end = 
00520                             (wordop_t*) (block + bm::set_block_size);
00521                     bit_invert(wrd_ptr, wrd_end);
00522                 }
00523             }
00524 
00525         }
00526     };
00527 
00529     class block_zero_func : public bm_func_base
00530     {
00531     public:
00532         block_zero_func(blocks_manager& bm) 
00533         : bm_func_base(bm)
00534         {}
00535 
00536         void operator()(bm::word_t* block, unsigned idx)
00537         {
00538             if (BM_IS_GAP(block))
00539                 gap_set_all(BMGAP_PTR(block), bm::gap_max_bits, 0);
00540             else  // BIT block
00541             {
00542                 if (IS_FULL_BLOCK(block))
00543                     this->bm_.set_block_ptr(idx, 0);
00544                 else
00545                     bit_block_set(block, 0);
00546             }
00547         }
00548     };
00549 
00551     class block_one_func : public bm_func_base
00552     {
00553     public:
00554         block_one_func(blocks_manager& bm) : bm_func_base(bm) {}
00555 
00556         void operator()(bm::word_t* block, unsigned idx)
00557         {
00558             if (!IS_FULL_BLOCK(block))
00559             {
00560                 this->bm_.set_block_all_set(idx);
00561             }
00562         }
00563     };
00564 
00566     class block_free_func : public bm_func_base
00567     {
00568     public:
00569         block_free_func(blocks_manager& bm) : bm_func_base(bm) {}
00570 
00571         void operator()(bm::word_t* block)//, unsigned idx)
00572         {
00573             blocks_manager& bman = this->bm_;
00574             if (BM_IS_GAP(block)) // gap block
00575             {
00576                 bman.get_allocator().free_gap_block(BMGAP_PTR(block),
00577                                                     bman.glen());
00578             }
00579             else
00580             {
00581                 bman.get_allocator().free_bit_block(block);
00582             }
00583         }
00584     };
00585 
00587     class block_copy_func : public bm_func_base
00588     {
00589     public:
00590         block_copy_func(blocks_manager&        bm_target, 
00591                         const blocks_manager&  bm_src) 
00592             : bm_func_base(bm_target), 
00593               bm_src_(bm_src) 
00594         {}
00595 
00596         void operator()(bm::word_t* block, unsigned idx)
00597         {
00598             bm::word_t* new_blk;            
00599             blocks_manager& bman = this->bm_;
00600 
00601             bool is_gap = BM_IS_GAP(block);
00602             if (is_gap)
00603             {
00604                 bm::gap_word_t* gap_block = BMGAP_PTR(block); 
00605                 unsigned level = gap_level(gap_block);
00606                 new_blk = (bm::word_t*)
00607                     bman.get_allocator().alloc_gap_block(level, 
00608                                                         bman.glen());
00609                 int len = gap_length(BMGAP_PTR(block));
00610                 ::memcpy(new_blk, gap_block, len * sizeof(gap_word_t));
00611             }
00612             else
00613             {
00614                 new_blk = block;
00615                 if (!IS_FULL_BLOCK(block))
00616                 {
00617                     new_blk = bman.get_allocator().alloc_bit_block();
00618                     bit_block_copy(new_blk, block);
00619                 }
00620             }
00621             bman.set_block(idx, new_blk, is_gap);
00622         }
00623 
00624     private:
00625         block_copy_func(const block_copy_func&);
00626         block_copy_func& operator=(const block_copy_func&);
00627     private:
00628         const blocks_manager&  bm_src_;
00629     };
00630 
00631 
00632 public:
00633 
00634     blocks_manager(const gap_word_t* glevel_len, 
00635                     bm::id_t          max_bits,
00636                     const Alloc&      alloc = Alloc())
00637         : temp_block_(0),
00638           alloc_(alloc)
00639     {
00640         ::memcpy(glevel_len_, glevel_len, sizeof(glevel_len_));
00641         blocks_ = 0;
00642         top_block_size_ = effective_top_block_size_ = 0;
00643         if (max_bits) 
00644         {
00645             top_block_size_ = compute_top_block_size(max_bits);
00646             init_tree();
00647         } 
00648         volatile const char* vp = _copyright<true>::_p;
00649         char c = *vp;
00650         c = 0;
00651     }
00652 
00653     blocks_manager(const blocks_manager& blockman)
00654         : blocks_(0),
00655             top_block_size_(blockman.top_block_size_),
00656             effective_top_block_size_(blockman.effective_top_block_size_),
00657         #ifdef BM_DISBALE_BIT_IN_PTR
00658             gap_flags_(blockman.gap_flags_),
00659         #endif
00660             temp_block_(0),
00661             alloc_(blockman.alloc_)
00662     {
00663         ::memcpy(glevel_len_, blockman.glevel_len_, sizeof(glevel_len_));
00664 
00665         init_tree();
00666 
00667         blocks_manager* bm = 
00668             const_cast<blocks_manager*>(&blockman);
00669 
00670         word_t*** blk_root = bm->blocks_root();
00671 
00672         block_copy_func copy_func(*this, blockman);
00673         for_each_nzblock(blk_root, top_block_size_, copy_func);
00674     }
00675 
00676     ~blocks_manager()
00677     {
00678         alloc_.free_bit_block(temp_block_);
00679         deinit_tree();
00680     }
00681 
00682     void free_ptr(bm::word_t** ptr)
00683     {
00684         if (ptr) alloc_.free_ptr(ptr);
00685     }
00686 
00692     unsigned compute_top_block_size(bm::id_t bits_to_store)
00693     {
00694         if (bits_to_store == bm::id_max)  // working in full-range mode
00695         {
00696             return bm::set_array_size;
00697         }
00698 
00699         unsigned top_block_size = 
00700             bits_to_store / (bm::set_block_size * sizeof(bm::word_t) * 
00701                                                 bm::set_array_size * 8);
00702         return top_block_size + (top_block_size < bm::set_array_size);
00703     }
00704 
00708     bm::id_t capacity() const
00709     {
00710         // arithmetic overflow protection...
00711         return top_block_size_ == bm::set_array_size ? bm::id_max :
00712             top_block_size_ * bm::set_array_size * bm::bits_in_block;
00713     }
00714 
00720     bm::word_t* get_block(unsigned nb) const
00721     {
00722         unsigned block_idx = nb >> bm::set_array_shift;
00723         if (block_idx >= top_block_size_)
00724         {
00725             return 0;
00726         }
00727         bm::word_t** blk_blk = blocks_[block_idx];
00728         return blk_blk ? blk_blk[nb & bm::set_array_mask] : 0;
00729     }
00730 
00740     bm::word_t* get_block(unsigned nb, int* no_more_blocks) const
00741     {
00742         unsigned block_idx = nb >> bm::set_array_shift;
00743         if (block_idx >= top_block_size_)
00744         {
00745             *no_more_blocks = 1;
00746             return 0;
00747         }
00748         *no_more_blocks = 0;
00749         bm::word_t** blk_blk = blocks_[block_idx];
00750         return blk_blk ? blk_blk[nb & bm::set_array_mask] : 0;
00751     }
00752 
00756     void get_block_coord(unsigned nb, unsigned* i, unsigned* j) const
00757     {
00758         BM_ASSERT(i);
00759         BM_ASSERT(j);
00760 
00761         *i = nb >> bm::set_array_shift; // top block address
00762         *j = nb &  bm::set_array_mask;  // address in sub-block
00763     }
00764 
00771     unsigned find_next_nz_block(unsigned nb, bool deep_scan = true) const
00772     {
00773         unsigned i,j;
00774         get_block_coord(nb, &i, &j);
00775         for (;i < effective_top_block_size_; ++i) 
00776         { 
00777             bm::word_t** blk_blk = blocks_[i];
00778             if (blk_blk)
00779             {
00780                unsigned r = i * bm::set_array_size;
00781                do
00782                {
00783                    if (blk_blk[j] && !is_block_zero(r + j, blk_blk[j], deep_scan)) 
00784                        return r + j;
00785                    ++j;
00786                } while (j < bm::set_array_size);
00787             }
00788             j = 0;
00789         } // for i
00790 
00791         return bm::set_total_blocks;
00792     }
00793 
00800     const bm::word_t* get_block(unsigned i, unsigned j) const
00801     {
00802         if (i >= top_block_size_) return 0;
00803         const bm::word_t* const* blk_blk = blocks_[i];
00804         return (blk_blk == 0) ? 0 : blk_blk[j];
00805     }
00806 
00812     const bm::word_t* const * get_topblock(unsigned i) const
00813     {
00814         return (i >= top_block_size_) ? 0 : blocks_[i];
00815     }
00816 
00820     bm::word_t*** get_rootblock() const
00821     {
00822         blocks_manager* bm = 
00823             const_cast<blocks_manager*>(this);
00824         return bm->blocks_root();
00825     }
00826 
00827     void free_block(bm::word_t* block)
00828     {
00829         if (BM_IS_GAP(block))
00830         {
00831             alloc_.free_gap_block(BMGAP_PTR(block), glevel_len_);
00832         }
00833         else
00834         {
00835             alloc_.free_bit_block(block);
00836         }
00837     }
00838 
00839     void set_block_all_set(unsigned nb)
00840     {
00841         bm::word_t* block = 
00842             set_block(nb, const_cast<bm::word_t*>(FULL_BLOCK_ADDR));
00843         free_block(block);
00844     }
00845 
00849     bm::word_t* alloc_bit_block(unsigned nb)
00850     {
00851         bm::word_t* block = this->get_allocator().alloc_bit_block();
00852         bm::word_t* old_block = set_block(nb, block);
00853         if (IS_VALID_ADDR(old_block))
00854         {
00855             free_block(old_block);
00856         }
00857         return block;
00858     }
00859 
00863     bm::word_t* make_bit_block(unsigned nb)
00864     {
00865         bm::word_t* block = this->alloc_bit_block(nb);
00866         bit_block_set(block, 0);
00867         return block;
00868     }
00869 
00874     bm::word_t* copy_bit_block(unsigned          nb, 
00875                                const bm::word_t* block_src, int is_src_gap)
00876     {
00877         if (block_src == 0)
00878         {
00879             zero_block(nb);
00880             return 0;
00881         }
00882         bm::word_t* block = alloc_bit_block(nb);
00883         if (is_src_gap)
00884         {
00885             gap_word_t* gap_block = BMGAP_PTR(block_src);
00886             gap_convert_to_bitset(block, gap_block);
00887         }
00888         else
00889         {            
00890             bit_block_copy(block, block_src);
00891         }
00892         return block;
00893     }
00894 
00899     bm::word_t* copy_block(unsigned idx, const blocks_manager& bm_src)
00900     {
00901         const bm::word_t* block = bm_src.get_block(idx);
00902         if (block == 0)
00903         {
00904             zero_block(idx);
00905             return 0;
00906         }
00907         bm::word_t* new_blk = 0;
00908         bool is_gap = BM_IS_GAP(block);
00909 
00910         if (is_gap)
00911         {
00912             bm::gap_word_t* gap_block = BMGAP_PTR(block); 
00913             unsigned level = gap_level(gap_block);
00914             new_blk = (bm::word_t*)
00915                 get_allocator().alloc_gap_block(level, glen());
00916             int len = gap_length(BMGAP_PTR(block));
00917             ::memcpy(new_blk, gap_block, len * sizeof(gap_word_t));
00918             set_gap_level(new_blk, level);
00919         }
00920         else
00921         {
00922             if (IS_FULL_BLOCK(block))
00923             {
00924                 new_blk = FULL_BLOCK_ADDR;
00925             }
00926             else
00927             {
00928                 new_blk = get_allocator().alloc_bit_block();
00929                 bit_block_copy(new_blk, block);
00930             }
00931         }
00932         set_block(idx, new_blk, is_gap);
00933         return new_blk;
00934     }
00935 
00936 
00946     bm::word_t* check_allocate_block(unsigned nb, 
00947                                      unsigned content_flag,
00948                                      int      initial_block_type,
00949                                      int*     actual_block_type,
00950                                      bool     allow_null_ret=true)
00951     {
00952         bm::word_t* block = this->get_block(nb);
00953 
00954         if (!IS_VALID_ADDR(block)) // NULL block or ALLSET
00955         {
00956             // if we wanted ALLSET and requested block is ALLSET return NULL
00957             unsigned block_flag = IS_FULL_BLOCK(block);
00958             *actual_block_type = initial_block_type;
00959             if (block_flag == content_flag && allow_null_ret)
00960             {
00961                 return 0; // it means nothing to do for the caller
00962             }
00963 
00964             if (initial_block_type == 0) // bitset requested
00965             {
00966                 block = alloc_.alloc_bit_block();
00967                 // initialize block depending on its previous status
00968                 bit_block_set(block, block_flag ? 0xFF : 0);
00969                 set_block(nb, block, false /*bit*/);
00970             }
00971             else // gap block requested
00972             {
00973                 bm::gap_word_t* gap_block = allocate_gap_block(0);
00974                 gap_set_all(gap_block, bm::gap_max_bits, block_flag);
00975                 set_block(nb, (bm::word_t*)gap_block, true/*gap*/);
00976                 return (bm::word_t*)gap_block;
00977             }
00978         }
00979         else // block already exists
00980         {
00981             *actual_block_type = BM_IS_GAP(block);
00982         }
00983 
00984         return block;
00985     }
00986 
00990     void set_all_zero(bool free_mem)
00991     {        
00992         if (free_mem)
00993         {
00994             // TODO: optimization of top-level realloc
00995             deinit_tree();
00996             init_tree();
00997         }
00998         else
00999         {
01000             block_zero_func zero_func(*this);
01001             unsigned top_size = this->effective_top_block_size();
01002             for_each_nzblock(blocks_, top_size,  zero_func);
01003         }
01004     }
01005 
01008     void set_all_one()
01009     {
01010         block_one_func func(*this);
01011         for_each_block(blocks_, top_block_size_, 
01012                                 bm::set_array_size, func);
01013     }
01014 
01019     bm::word_t* set_block(unsigned nb, bm::word_t* block)
01020     {
01021         register unsigned nblk_blk = nb >> bm::set_array_shift;
01022 
01023         // auto-resize the top block array
01024         if (nblk_blk >= top_block_size_)
01025             reserve_top_blocks(nblk_blk + 1);
01026         if (nblk_blk >= effective_top_block_size_)
01027             effective_top_block_size_ = nblk_blk + 1;
01028 
01029         // If first level array not yet allocated, allocate it and
01030         // assign block to it
01031         if (blocks_[nblk_blk] == 0) 
01032         {
01033             blocks_[nblk_blk] = (bm::word_t**)alloc_.alloc_ptr();
01034             ::memset(blocks_[nblk_blk], 0, 
01035                 bm::set_array_size * sizeof(bm::word_t*));
01036         }
01037 
01038         // NOTE: block will be replaced without freeing
01039         unsigned j = nb & bm::set_array_mask;
01040         bm::word_t* old_block = blocks_[nblk_blk][j];
01041         blocks_[nblk_blk][j] = block;
01042 
01043         return old_block;
01044     }
01045 
01046 
01050     bm::word_t* set_gap_block(unsigned      nb,
01051                           const gap_word_t* gap_block_src,
01052                           int               level)
01053     {
01054         if (level == -1)
01055         {
01056             bm::word_t* blk = get_allocator().alloc_bit_block();
01057             set_block(nb, blk);
01058             gap_convert_to_bitset(blk, gap_block_src);
01059             return blk;
01060         }
01061         else
01062         {
01063             gap_word_t* gap_blk = get_allocator().alloc_gap_block(
01064                                                          level, this->glen());
01065             gap_word_t* gap_blk_ptr = BMGAP_PTR(gap_blk);
01066             ::memcpy(gap_blk_ptr, gap_block_src, 
01067                                   gap_length(gap_block_src) * sizeof(gap_word_t));
01068             set_gap_level(gap_blk_ptr, level);
01069             set_block(nb, (bm::word_t*)gap_blk, true /*GAP*/);
01070             return (bm::word_t*)gap_blk;
01071         }
01072     }
01073 
01078     bm::word_t* set_block(unsigned nb, bm::word_t* block, bool gap)
01079     {
01080         if (block)
01081         {
01082             block = 
01083                 (bm::word_t*) (gap ? BMPTR_SETBIT0(block) : BMPTR_CLEARBIT0(block));
01084         }
01085 
01086         // top block index
01087         register unsigned nblk_blk = nb >> bm::set_array_shift;
01088 
01089         // auto-resize the top block array
01090         if (nblk_blk >= top_block_size_)
01091             reserve_top_blocks(nblk_blk + 1);
01092         if (nblk_blk >= effective_top_block_size_)
01093             effective_top_block_size_ = nblk_blk + 1;
01094 
01095         // If first level array not yet allocated, allocate it and
01096         // assign block to it
01097         if (blocks_[nblk_blk] == 0) 
01098         {
01099             blocks_[nblk_blk] = (bm::word_t**)alloc_.alloc_ptr();
01100             ::memset(blocks_[nblk_blk], 0, 
01101                 bm::set_array_size * sizeof(bm::word_t*));
01102         }
01103 
01104         // NOTE: block will be replaced without freeing
01105         unsigned j = nb & bm::set_array_mask;
01106         bm::word_t* old_block = blocks_[nblk_blk][j];
01107         blocks_[nblk_blk][j] = block; 
01108 
01109         return old_block;
01110     }
01111 
01115     void set_block_ptr(unsigned nb, bm::word_t* block)
01116     {
01117         BM_ASSERT((nb >> bm::set_array_shift) < effective_top_block_size_);
01118         blocks_[nb >> bm::set_array_shift][nb & bm::set_array_mask] = block;
01119     }
01120         
01129     bm::word_t* convert_gap2bitset(unsigned nb, 
01130                                    const gap_word_t* gap_block=0, 
01131                                    unsigned gap_len=0)
01132     {
01133         bm::word_t* block = this->get_block(nb);
01134         if (gap_block == 0)
01135         {
01136             gap_block = BMGAP_PTR(block);
01137         }
01138 
01139         BM_ASSERT(IS_VALID_ADDR((bm::word_t*)gap_block));
01140 
01141         bm::word_t* new_block = alloc_.alloc_bit_block();
01142         gap_convert_to_bitset_l(new_block, gap_block, gap_len);
01143 
01144         // new block will replace the old one(no deletion)
01145         //set_block_ptr(nb, new_block); 
01146         if (block)
01147         {
01148             set_block_ptr(nb, new_block); 
01149             alloc_.free_gap_block(BMGAP_PTR(block), glen());
01150         }
01151         else
01152         {
01153             set_block(nb, new_block); 
01154         }
01155 
01156         return new_block;
01157     }
01158 
01162     bm::word_t* deoptimize_block(unsigned nb)
01163     {
01164         bm::word_t* block = this->get_block(nb);
01165         if (BM_IS_GAP(block))
01166         {
01167             return convert_gap2bitset(nb);
01168         }
01169         if (IS_FULL_BLOCK(block)) 
01170         {
01171             bm::word_t* new_block = get_allocator().alloc_bit_block();
01172             bit_block_copy(new_block, block);
01173             set_block(nb, new_block);
01174             return new_block;
01175         }
01176         return block;
01177     }
01178 
01182     bm::word_t* zero_block(unsigned nb)
01183     {
01184         bm::word_t* block = this->get_block(nb);
01185         if (!block) return block;
01186         free_block(block);
01187         set_block(nb, 0);
01188         return 0;
01189     }
01190 
01194     bm::word_t* zero_block(unsigned i, unsigned j)
01195     {
01196         bm::word_t** blk_blk = blocks_[i];
01197         bm::word_t* block = blk_blk[j];
01198         blk_blk[j] = 0;
01199 
01200         free_block(block);
01201 
01202         return 0;
01203     }
01204 
01205 
01209     bm::id_t block_bitcount(const bm::word_t* block) const
01210     { 
01211         if (!block) return 0;
01212         id_t count;
01213 
01214         if (BM_IS_GAP(block))
01215         {
01216             count = gap_bit_count(BMGAP_PTR(block));
01217         }
01218         else // bitset
01219         {
01220             count = (IS_FULL_BLOCK(block)) ? bm::bits_in_block
01221                 : bit_block_calc_count(block, block + bm::set_block_size);
01222         }
01223         return count;
01224     }
01225 
01233     bm::gap_word_t* extend_gap_block(unsigned nb, gap_word_t* blk)
01234     {
01235         unsigned level = bm::gap_level(blk);
01236         unsigned len = bm::gap_length(blk);
01237         if (level == bm::gap_max_level || len >= gap_max_buff_len)
01238         {
01239             convert_gap2bitset(nb);
01240         }
01241         else
01242         {
01243             bm::gap_word_t* new_gap_blk = allocate_gap_block(++level, blk);
01244             bm::word_t* new_blk = (bm::word_t*)new_gap_blk;
01245 
01246             BMSET_PTRGAP(new_blk);
01247 
01248             set_block_ptr(nb, new_blk);
01249             alloc_.free_gap_block(blk, glen());
01250 
01251             return new_gap_blk;
01252         }
01253         return 0;
01254     }
01255 
01256     bool is_block_gap(unsigned nb) const 
01257     {
01258         bm::word_t* block = get_block(nb);
01259         return BMPTR_TESTBIT0(block) != 0;
01260     }
01261 
01262     void set_block_bit(unsigned nb) 
01263     { 
01264         bm::word_t* block = get_block(nb);
01265         block = (bm::word_t*) BMPTR_CLEARBIT0(block);
01266         set_block_ptr(nb, block);
01267     }
01268 
01269     void set_block_gap(unsigned nb) 
01270     {
01271         bm::word_t* block = get_block(nb);
01272         block = (bm::word_t*)BMPTR_SETBIT0(block);
01273         set_block_ptr(nb, block);
01274     }
01275 
01285     bool is_block_zero(unsigned          nb, 
01286                        const bm::word_t* blk, 
01287                        bool              deep_scan = true) const
01288     {
01289         if (blk == 0) return true;
01290 
01291         if (BM_IS_GAP(blk))
01292         {
01293             gap_word_t* b = BMGAP_PTR(blk);
01294             return gap_is_all_zero(b, bm::gap_max_bits);
01295         }
01296 
01297         if (!deep_scan) 
01298             return false; // block exists - presume it has bits
01299 
01300         // BIT
01301         for (unsigned i = 0; i <  bm::set_block_size; ++i)
01302         {
01303             if (blk[i] != 0)
01304                 return false;
01305         }
01306         return true;
01307     }
01308 
01317     bool is_block_one(unsigned          nb, 
01318                       const bm::word_t* blk,
01319                       bool              deep_scan = true) const
01320     {
01321         if (blk == 0) return false;
01322 
01323         if (BM_IS_GAP(blk))
01324         {
01325             gap_word_t* b = BMGAP_PTR(blk);
01326             return gap_is_all_one(b, bm::gap_max_bits);
01327         }
01328 
01329         // BIT block
01330         if (IS_FULL_BLOCK(blk))
01331         {
01332             return true;
01333         }
01334         if (!deep_scan) 
01335             return false; // block exists - presume it has 0 bits
01336 
01337         return is_bits_one((wordop_t*)blk, 
01338                            (wordop_t*)(blk + bm::set_block_size));
01339     }
01340 
01342     bm::word_t* check_allocate_tempblock()
01343     {
01344         return temp_block_ ? temp_block_ 
01345                             : (temp_block_ = alloc_.alloc_bit_block());
01346     }
01347 
01349     void set_glen(const gap_word_t* glevel_len)
01350     {
01351         ::memcpy(glevel_len_, glevel_len, sizeof(glevel_len_));
01352     }
01353 
01354 
01355     bm::gap_word_t* allocate_gap_block(unsigned level, 
01356                                        const gap_word_t* src = 0,
01357                                        const gap_word_t* glevel_len = 0)
01358     {
01359         if (!glevel_len)
01360             glevel_len = glevel_len_;
01361         gap_word_t* ptr = alloc_.alloc_gap_block(level, glevel_len);
01362         if (src)
01363         {
01364             unsigned len = gap_length(src);
01365             ::memcpy(ptr, src, len * sizeof(gap_word_t));
01366             // Reconstruct the mask word using the new level code.
01367             *ptr = (gap_word_t)(((len-1) << 3) | (level << 1) | (*src & 1));
01368         }
01369         else
01370         {
01371             *ptr = (gap_word_t)(level << 1);
01372         }
01373         return ptr;
01374     }
01375 
01376     unsigned mem_used() const
01377     {
01378         unsigned mem_used = sizeof(*this);
01379         mem_used += temp_block_ ? sizeof(word_t) * bm::set_block_size : 0;
01380         mem_used += sizeof(bm::word_t**) * top_block_size_;
01381 
01382         for (unsigned i = 0; i < top_block_size_; ++i)
01383         {
01384             mem_used += blocks_[i] ? sizeof(void*) * bm::set_array_size : 0;
01385         }
01386 
01387         return mem_used;
01388     }
01389 
01392     bool is_subblock_null(unsigned nsub) const
01393     {
01394         return blocks_[nsub] == NULL;
01395     }
01396 
01397 
01398     bm::word_t***  blocks_root()
01399     {
01400         return blocks_;
01401     }
01402 
01405     const gap_word_t* glen() const
01406     {
01407         return glevel_len_;
01408     }
01409 
01413     unsigned glen(unsigned level) const
01414     {
01415         return glevel_len_[level];
01416     }
01417 
01421     void swap(blocks_manager& bm)
01422     {
01423         BM_ASSERT(this != &bm);
01424 
01425         word_t*** btmp = blocks_;
01426         blocks_ = bm.blocks_;
01427         bm.blocks_ = btmp;
01428 
01429         xor_swap(this->top_block_size_, bm.top_block_size_);
01430         xor_swap(this->effective_top_block_size_, bm.effective_top_block_size_);
01431 
01432         BM_ASSERT(sizeof(glevel_len_) / sizeof(glevel_len_[0]) 
01433                                     == bm::gap_levels); // paranoiya check
01434         for (unsigned i = 0; i < bm::gap_levels; ++i)
01435         {
01436             xor_swap(glevel_len_[i], bm.glevel_len_[i]);
01437         }
01438     }
01439 
01442     unsigned top_block_size() const
01443     {
01444         return top_block_size_;
01445     }
01446 
01450     unsigned effective_top_block_size() const
01451     {
01452         return effective_top_block_size_;
01453     }
01454 
01458     void reserve(unsigned max_bits)
01459     {
01460         if (max_bits) 
01461         {
01462             unsigned b = compute_top_block_size(max_bits);
01463             reserve_top_blocks(b);
01464         }
01465     }
01466 
01470     void reserve_top_blocks(unsigned top_blocks) 
01471     {
01472         BM_ASSERT(top_blocks <= bm::set_array_size);
01473         if (top_blocks <= top_block_size_) return; // nothing to do
01474         bm::word_t*** new_blocks = 
01475             (bm::word_t***)alloc_.alloc_ptr(top_blocks);
01476 
01477         for (unsigned i = 0; i < top_block_size_; ++i)
01478         {
01479             new_blocks[i] = blocks_[i];
01480         }
01481         for (unsigned j = top_block_size_; j < top_blocks; ++j)
01482         {
01483             new_blocks[j] = 0;
01484         }
01485         alloc_.free_ptr(blocks_, top_block_size_);
01486         blocks_ = new_blocks;
01487         top_block_size_ = top_blocks;
01488     }
01489     
01492     allocator_type& get_allocator() { return alloc_; }
01493 
01496     allocator_type get_allocator() const { return alloc_; }
01497 
01498 private:
01499 
01500     void operator =(const blocks_manager&);
01501 
01502     void deinit_tree()
01503     {
01504         if (blocks_ == 0) return;
01505         unsigned top_size = this->effective_top_block_size();
01506         block_free_func  free_func(*this);
01507         for_each_nzblock2(blocks_, top_size, free_func);
01508         free_top_block();
01509         alloc_.free_ptr(blocks_, top_block_size_);
01510         blocks_ = 0;
01511     }
01512 
01513     void free_top_block()
01514     {
01515         for(unsigned i = 0; i < top_block_size_; ++i)
01516         {
01517             bm::word_t** blk_blk = blocks_[i];
01518             if (blk_blk) 
01519             {
01520                 alloc_.free_ptr(blk_blk); blocks_[i] = 0;
01521             }
01522         }
01523     }
01524 
01526     void init_tree()
01527     {
01528         if (top_block_size_)
01529         {
01530             blocks_ = (bm::word_t***) alloc_.alloc_ptr(top_block_size_); 
01531             ::memset(blocks_, 0, top_block_size_ * sizeof(bm::word_t**));
01532         }
01533         else
01534         {
01535             blocks_ = 0;
01536         }
01537         effective_top_block_size_ = 1;
01538     }
01539 
01540 private:
01542     bm::word_t***                          blocks_;
01544     unsigned                               top_block_size_;
01546     unsigned                               effective_top_block_size_;
01548     bm::word_t*                            temp_block_; 
01550     gap_word_t                             glevel_len_[bm::gap_levels];
01552     allocator_type                         alloc_;
01553 };
01554 
01559 template<class BlocksManager>
01560 class bit_block_guard
01561 {
01562 public:
01563     bit_block_guard(BlocksManager& bman, bm::word_t* blk=0) 
01564         : bman_(bman), 
01565           block_(blk)
01566     {}
01567     ~bit_block_guard()
01568     {
01569         bman_.get_allocator().free_bit_block(block_, 3);
01570     }
01571     void attach(bm::word_t* blk)
01572     {
01573         bman_.get_allocator().free_bit_block(block_);
01574         block_ = blk;
01575     }
01576     bm::word_t* allocate()
01577     {
01578         attach(bman_.get_allocator().alloc_bit_block(3));
01579         return block_;
01580     }
01581     bm::word_t* get() { return block_; }
01582 
01583 private:
01584     bit_block_guard(const bit_block_guard&);
01585     bit_block_guard& operator=(const bit_block_guard&);
01586 private:
01587     BlocksManager& bman_;
01588     bm::word_t*    block_;
01589 };
01590 
01591 
01592 }
01593 
01594 #ifdef _MSC_VER
01595 #pragma warning( pop )
01596 #endif
01597 
01598 #endif
01599