vs12/bm/bmblocks.h

Go to the documentation of this file.

#ifndef BM_BLOCKS__H__INCLUDED__
#define BM_BLOCKS__H__INCLUDED__
/*
Copyright(c) 2002-2010 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)

Permission is hereby granted, free of charge, to any person 
obtaining a copy of this software and associated documentation 
files (the "Software"), to deal in the Software without restriction, 
including without limitation the rights to use, copy, modify, merge, 
publish, distribute, sublicense, and/or sell copies of the Software, 
and to permit persons to whom the Software is furnished to do so, 
subject to the following conditions:

The above copyright notice and this permission notice shall be included 
in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES 
OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. 
IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, 
DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, 
ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR 
OTHER DEALINGS IN THE SOFTWARE.

For more information please visit:  http://bmagic.sourceforge.net

*/


#include "bmfwd.h"

#ifdef _MSC_VER
#pragma warning( push )
#pragma warning( disable : 4100)
#endif


namespace bm
{


template<class Alloc/*, class MS*/> 
class blocks_manager
{
public:

    typedef Alloc allocator_type;

    class bm_func_base
    {
    public:
        bm_func_base(blocks_manager& bman) : bm_(bman) {}

        void on_empty_top(unsigned /* top_block_idx*/ ) {}
        void on_empty_block(unsigned /* block_idx*/ ) {}
    private:
        bm_func_base(const bm_func_base&);
        bm_func_base& operator=(const bm_func_base&);
    protected:
        blocks_manager&  bm_;
    };


    class bm_func_base_const
    {
    public:
        bm_func_base_const(const blocks_manager& bman) : bm_(bman) {}

        void on_empty_top(unsigned /* top_block_idx*/ ) {}
        void on_empty_block(unsigned /* block_idx*/ ) {}
    private:
        bm_func_base_const(const bm_func_base_const&);
        bm_func_base_const& operator=(const bm_func_base_const&);
    protected:
        const blocks_manager&  bm_;
    };


    class block_count_base : public bm_func_base_const
    {
    protected:
        block_count_base(const blocks_manager& bm) 
            : bm_func_base_const(bm) {}

        bm::id_t block_count(const bm::word_t* block) const
        {
            return this->bm_.block_bitcount(block);
        }
    };


    class block_count_func : public block_count_base
    {
    public:
        block_count_func(const blocks_manager& bm) 
            : block_count_base(bm), count_(0) {}

        bm::id_t count() const { return count_; }

        void operator()(const bm::word_t* block)
        {
            count_ += this->block_count(block);
        }

    private:
        bm::id_t count_;
    };


    class block_count_arr_func : public block_count_base
    {
    public:
        block_count_arr_func(const blocks_manager& bm, unsigned* arr) 
            : block_count_base(bm), arr_(arr), last_idx_(0) 
        {
            arr_[0] = 0;
        }

        void operator()(const bm::word_t* block, unsigned idx)
        {
            while (++last_idx_ < idx)
            {
                arr_[last_idx_] = 0;
            }
            arr_[idx] = this->block_count(block);
            last_idx_ = idx;
        }

        unsigned last_block() const { return last_idx_; }

    private:
        unsigned*  arr_;
        unsigned   last_idx_;
    };

    class block_count_change_func : public bm_func_base_const
    {
    public:
        block_count_change_func(const blocks_manager& bm) 
            : bm_func_base_const(bm),
                count_(0),
                prev_block_border_bit_(0)
        {}

        bm::id_t block_count(const bm::word_t* block, unsigned idx)
        {
            bm::id_t count = 0;
            bm::id_t first_bit;
            
            if (IS_FULL_BLOCK(block) || (block == 0))
            {
                count = 1;
                if (idx)
                {
                    first_bit = block ? 1 : 0;
                    count -= !(prev_block_border_bit_ ^ first_bit);
                }
                prev_block_border_bit_ = block ? 1 : 0;
            }
            else
            {
                if (BM_IS_GAP(block))
                {
                    gap_word_t* gap_block = BMGAP_PTR(block);
                    count = gap_length(gap_block) - 1;
                    if (idx)
                    {
                        first_bit = gap_test(gap_block, 0);
                        count -= !(prev_block_border_bit_ ^ first_bit);
                    }
                        
                    prev_block_border_bit_ = 
                        gap_test(gap_block, gap_max_bits-1);
                }
                else // bitset
                {
                    unsigned bit_count;
                    count = bit_block_calc_count_change(block,
                                                block + bm::set_block_size,
                                                &bit_count);
                    if (idx)
                    {
                        first_bit = block[0] & 1;
                        count -= !(prev_block_border_bit_ ^ first_bit);
                    }
                    prev_block_border_bit_ = 
                        block[set_block_size-1] >> ((sizeof(block[0]) * 8) - 1);
                    
                }
            }
            return count;
        }
        
        bm::id_t count() const { return count_; }

        void operator()(const bm::word_t* block, unsigned idx)
        {
            count_ += block_count(block, idx);
        }

    private:
        bm::id_t   count_;
        bm::id_t   prev_block_border_bit_;
    };


    class block_any_func : public bm_func_base_const
    {
    public:
        block_any_func(const blocks_manager& bm) 
            : bm_func_base_const(bm) 
        {}

        bool operator()(const bm::word_t* block, unsigned idx)
        {
            if (IS_FULL_BLOCK(block)) return true;

            if (BM_IS_GAP(block)) // gap block
            {
                if (!gap_is_all_zero(BMGAP_PTR(block), bm::gap_max_bits))
                {
                    return true;
                }
            }
            else  // bitset
            {
                bm::wordop_t* blk1 = (wordop_t*)block;
                bm::wordop_t* blk2 = 
                    (wordop_t*)(block + bm::set_block_size);
                if (!bit_is_all_zero(blk1, blk2))
                {
                    return true;
                }
            }
            return false;
        }
    };

    class gap_level_func : public bm_func_base
    {
    public:
        gap_level_func(blocks_manager& bm, const gap_word_t* glevel_len)
            : bm_func_base(bm),
                glevel_len_(glevel_len)
        {
            BM_ASSERT(glevel_len);
        }

        void operator()(bm::word_t* block, unsigned idx)
        {
            blocks_manager& bman = this->bm_;
            
            if (!BM_IS_GAP(block))
                return;

            gap_word_t* gap_blk = BMGAP_PTR(block);

            // TODO: Use the same code as in the optimize functor
            if (gap_is_all_zero(gap_blk, bm::gap_max_bits))
            {
                bman.set_block_ptr(idx, 0);
                goto free_block;
            }
            else 
            if (gap_is_all_one(gap_blk, bm::gap_max_bits))
            {
                bman.set_block_ptr(idx, FULL_BLOCK_ADDR);
            free_block:
                bman.get_allocator().free_gap_block(gap_blk, 
                                                    bman.glen());
                bman.set_block_bit(idx);
                return;
            }

            unsigned len = gap_length(gap_blk);
            int level = gap_calc_level(len, glevel_len_);
            if (level == -1)
            {
                bm::word_t* blk = 
                    bman.get_allocator().alloc_bit_block();
                bman.set_block_ptr(idx, blk);
                bman.set_block_bit(idx);
                gap_convert_to_bitset(blk, gap_blk);
            }
            else
            {
                gap_word_t* gap_blk_new = 
                    bman.allocate_gap_block(level, gap_blk, glevel_len_);

                bm::word_t* p = (bm::word_t*) gap_blk_new;
                BMSET_PTRGAP(p);
                bman.set_block_ptr(idx, p);
            }
            bman.get_allocator().free_gap_block(gap_blk, bman.glen());
        }

    private:
        const gap_word_t* glevel_len_;
    };


    class block_opt_func : public bm_func_base
    {
    public:
        block_opt_func(blocks_manager& bm, 
                        bm::word_t*     temp_block,
                        int             opt_mode,
                        bv_statistics*  bv_stat=0) 
            : bm_func_base(bm),
              temp_block_(temp_block),
              opt_mode_(opt_mode),
              stat_(bv_stat),
              empty_(0)
        {
            BM_ASSERT(temp_block);
        }

        void on_empty_top(unsigned i)
        {
            bm::word_t*** blk_root = this->bm_.get_rootblock();
            bm::word_t** blk_blk = blk_root[i];
            if (blk_blk) 
            {
                this->bm_.get_allocator().free_ptr(blk_blk);
                blk_root[i] = 0;
            }
            if (stat_)
            {
                stat_->max_serialize_mem += sizeof(unsigned) + 1;
            }
        }
        void on_empty_block(unsigned /* block_idx*/ ) { ++empty_; }

        void operator()(bm::word_t* block, unsigned idx)
        {
            blocks_manager& bman = this->bm_;
            if (IS_FULL_BLOCK(block)) 
            {
                ++empty_;
                return;
            }

            if (stat_) 
            {
                stat_->max_serialize_mem += empty_ << 2;
                empty_ = 0;
            }

            gap_word_t* gap_blk;
            if (BM_IS_GAP(block)) // gap block
            {
                gap_blk = BMGAP_PTR(block);
                // check if block is empty (or all 1)
                if (gap_is_all_zero(gap_blk, bm::gap_max_bits))
                {
                    bman.set_block_ptr(idx, 0);
                    this->free_block(gap_blk, idx);
                    ++empty_;
                }
                else 
                if (gap_is_all_one(gap_blk, bm::gap_max_bits))
                {
                    bman.set_block_ptr(idx, FULL_BLOCK_ADDR);
                    this->free_block(gap_blk, idx);
                    ++empty_;
                }
                else
                {
                    // regular gap block - compute statistics
                    if (stat_)
                    {
                        stat_->add_gap_block(
                                    bm::gap_capacity(gap_blk, bman.glen()),
                                    bm::gap_length(gap_blk));
                    }
                }
            }
            else // bit block
            {
                if (opt_mode_ < 3) // free_01 optimization
                {  
                    bm::wordop_t* blk1 = (wordop_t*)block;
                    bm::wordop_t* blk2 = 
                        (wordop_t*)(block + bm::set_block_size);
                
                    bool b = bit_is_all_zero(blk1, blk2);
                    if (b)
                    {
                        bman.get_allocator().free_bit_block(block);
                        bman.set_block_ptr(idx, 0);
                        ++empty_;
                    } 
                    else
                    if (opt_mode_ == 2) // check if it is all 1 block
                    {
                        b = is_bits_one(blk1, blk2);
                        if (b) 
                        {
                            bman.get_allocator().free_bit_block(block);
                            bman.set_block_ptr(idx, FULL_BLOCK_ADDR);
                            ++empty_;
                        }
                    }

                    if (!b && stat_)
                        stat_->add_bit_block();

                    return;
                }
            
                // try to compress
            
                gap_word_t* tmp_gap_blk = (gap_word_t*)temp_block_;
                *tmp_gap_blk = bm::gap_max_level << 1;

                unsigned threashold = bman.glen(bm::gap_max_level)-4;

                unsigned len = bit_convert_to_gap(tmp_gap_blk, 
                                                    block, 
                                                    bm::gap_max_bits, 
                                                    threashold);
                if (len)    // compression successful                
                {                
                    bman.get_allocator().free_bit_block(block);

                    // check if new gap block can be eliminated
                    if (gap_is_all_zero(tmp_gap_blk, bm::gap_max_bits))
                    {
                        bman.set_block_ptr(idx, 0);
                        ++empty_;
                    }
                    else if (gap_is_all_one(tmp_gap_blk, bm::gap_max_bits))
                    {
                        bman.set_block_ptr(idx, FULL_BLOCK_ADDR);
                        ++empty_;
                    }
                    else
                    {
                        int level = bm::gap_calc_level(len, bman.glen());

                        gap_blk = 
                            bman.allocate_gap_block(level, tmp_gap_blk);
                        bman.set_block_ptr(idx, (bm::word_t*)gap_blk);
                        bman.set_block_gap(idx);
                        if (stat_)
                        {
                            stat_->add_gap_block(
                                    bm::gap_capacity(gap_blk, bman.glen()),
                                    bm::gap_length(gap_blk));
                        }
                    }
                }  
                else  // non-compressable bit-block
                {
                    if (stat_)
                        stat_->add_bit_block();
                }
            }
        }
    private:
        void free_block(gap_word_t* gap_blk, unsigned idx)
        {
            this->bm_.get_allocator().free_gap_block(gap_blk,
                                                     this->bm_.glen());
            this->bm_.set_block_bit(idx);
        }

    private:
        bm::word_t*         temp_block_;
        int                 opt_mode_;
        bv_statistics*      stat_;
        unsigned            empty_;
    };

    class block_invert_func : public bm_func_base
    {
    public:
        block_invert_func(blocks_manager& bm) 
            : bm_func_base(bm) {}

        void operator()(bm::word_t* block, unsigned idx)
        {
            if (!block)
            {
                this->bm_.set_block(idx, FULL_BLOCK_ADDR);
            }
            else
            if (IS_FULL_BLOCK(block))
            {
                this->bm_.set_block_ptr(idx, 0);
            }
            else
            {
                if (BM_IS_GAP(block)) // gap block
                {
                    gap_invert(BMGAP_PTR(block));
                }
                else  // bit block
                {
                    bm::wordop_t* wrd_ptr = (wordop_t*) block;
                    bm::wordop_t* wrd_end = 
                            (wordop_t*) (block + bm::set_block_size);
                    bit_invert(wrd_ptr, wrd_end);
                }
            }

        }
    };

    class block_zero_func : public bm_func_base
    {
    public:
        block_zero_func(blocks_manager& bm) 
        : bm_func_base(bm)
        {}

        void operator()(bm::word_t* block, unsigned idx)
        {
            if (BM_IS_GAP(block))
                gap_set_all(BMGAP_PTR(block), bm::gap_max_bits, 0);
            else  // BIT block
            {
                if (IS_FULL_BLOCK(block))
                    this->bm_.set_block_ptr(idx, 0);
                else
                    bit_block_set(block, 0);
            }
        }
    };

    class block_one_func : public bm_func_base
    {
    public:
        block_one_func(blocks_manager& bm) : bm_func_base(bm) {}

        void operator()(bm::word_t* block, unsigned idx)
        {
            if (!IS_FULL_BLOCK(block))
            {
                this->bm_.set_block_all_set(idx);
            }
        }
    };

    class block_free_func : public bm_func_base
    {
    public:
        block_free_func(blocks_manager& bm) : bm_func_base(bm) {}

        void operator()(bm::word_t* block)//, unsigned idx)
        {
            blocks_manager& bman = this->bm_;
            if (BM_IS_GAP(block)) // gap block
            {
                bman.get_allocator().free_gap_block(BMGAP_PTR(block),
                                                    bman.glen());
            }
            else
            {
                bman.get_allocator().free_bit_block(block);
            }
        }
    };

    class block_copy_func : public bm_func_base
    {
    public:
        block_copy_func(blocks_manager&        bm_target, 
                        const blocks_manager&  bm_src) 
            : bm_func_base(bm_target), 
              bm_src_(bm_src) 
        {}

        void operator()(bm::word_t* block, unsigned idx)
        {
            bm::word_t* new_blk;            
            blocks_manager& bman = this->bm_;

            bool is_gap = BM_IS_GAP(block);
            if (is_gap)
            {
                bm::gap_word_t* gap_block = BMGAP_PTR(block); 
                unsigned level = gap_level(gap_block);
                new_blk = (bm::word_t*)
                    bman.get_allocator().alloc_gap_block(level, 
                                                        bman.glen());
                int len = gap_length(BMGAP_PTR(block));
                ::memcpy(new_blk, gap_block, len * sizeof(gap_word_t));
            }
            else
            {
                new_blk = block;
                if (!IS_FULL_BLOCK(block))
                {
                    new_blk = bman.get_allocator().alloc_bit_block();
                    bit_block_copy(new_blk, block);
                }
            }
            bman.set_block(idx, new_blk, is_gap);
        }

    private:
        block_copy_func(const block_copy_func&);
        block_copy_func& operator=(const block_copy_func&);
    private:
        const blocks_manager&  bm_src_;
    };


public:

    blocks_manager(const gap_word_t* glevel_len, 
                    bm::id_t          max_bits,
                    const Alloc&      alloc = Alloc())
        : temp_block_(0),
          alloc_(alloc)
    {
        ::memcpy(glevel_len_, glevel_len, sizeof(glevel_len_));
        blocks_ = 0;
        top_block_size_ = effective_top_block_size_ = 0;
        if (max_bits) 
        {
            top_block_size_ = compute_top_block_size(max_bits);
            init_tree();
        } 
        volatile const char* vp = _copyright<true>::_p;
        char c = *vp;
        c = 0;
    }

    blocks_manager(const blocks_manager& blockman)
        : blocks_(0),
            top_block_size_(blockman.top_block_size_),
            effective_top_block_size_(blockman.effective_top_block_size_),
        #ifdef BM_DISBALE_BIT_IN_PTR
            gap_flags_(blockman.gap_flags_),
        #endif
            temp_block_(0),
            alloc_(blockman.alloc_)
    {
        ::memcpy(glevel_len_, blockman.glevel_len_, sizeof(glevel_len_));

        init_tree();

        blocks_manager* bm = 
            const_cast<blocks_manager*>(&blockman);

        word_t*** blk_root = bm->blocks_root();

        block_copy_func copy_func(*this, blockman);
        for_each_nzblock(blk_root, top_block_size_, copy_func);
    }

    ~blocks_manager()
    {
        alloc_.free_bit_block(temp_block_);
        deinit_tree();
    }

    void free_ptr(bm::word_t** ptr)
    {
        if (ptr) alloc_.free_ptr(ptr);
    }

    unsigned compute_top_block_size(bm::id_t bits_to_store)
    {
        if (bits_to_store == bm::id_max)  // working in full-range mode
        {
            return bm::set_array_size;
        }

        unsigned top_block_size = 
            bits_to_store / (bm::set_block_size * sizeof(bm::word_t) * 
                                                bm::set_array_size * 8);
        return top_block_size + (top_block_size < bm::set_array_size);
    }

    bm::id_t capacity() const
    {
        // arithmetic overflow protection...
        return top_block_size_ == bm::set_array_size ? bm::id_max :
            top_block_size_ * bm::set_array_size * bm::bits_in_block;
    }

    bm::word_t* get_block(unsigned nb) const
    {
        unsigned block_idx = nb >> bm::set_array_shift;
        if (block_idx >= top_block_size_)
        {
            return 0;
        }
        bm::word_t** blk_blk = blocks_[block_idx];
        return blk_blk ? blk_blk[nb & bm::set_array_mask] : 0;
    }

    bm::word_t* get_block(unsigned nb, int* no_more_blocks) const
    {
        unsigned block_idx = nb >> bm::set_array_shift;
        if (block_idx >= top_block_size_)
        {
            *no_more_blocks = 1;
            return 0;
        }
        *no_more_blocks = 0;
        bm::word_t** blk_blk = blocks_[block_idx];
        return blk_blk ? blk_blk[nb & bm::set_array_mask] : 0;
    }

    void get_block_coord(unsigned nb, unsigned* i, unsigned* j) const
    {
        BM_ASSERT(i);
        BM_ASSERT(j);

        *i = nb >> bm::set_array_shift; // top block address
        *j = nb &  bm::set_array_mask;  // address in sub-block
    }

    unsigned find_next_nz_block(unsigned nb, bool deep_scan = true) const
    {
        unsigned i,j;
        get_block_coord(nb, &i, &j);
        for (;i < effective_top_block_size_; ++i) 
        { 
            bm::word_t** blk_blk = blocks_[i];
            if (blk_blk)
            {
               unsigned r = i * bm::set_array_size;
               do
               {
                   if (blk_blk[j] && !is_block_zero(r + j, blk_blk[j], deep_scan)) 
                       return r + j;
                   ++j;
               } while (j < bm::set_array_size);
            }
            j = 0;
        } // for i

        return bm::set_total_blocks;
    }

    const bm::word_t* get_block(unsigned i, unsigned j) const
    {
        if (i >= top_block_size_) return 0;
        const bm::word_t* const* blk_blk = blocks_[i];
        return (blk_blk == 0) ? 0 : blk_blk[j];
    }

    const bm::word_t* const * get_topblock(unsigned i) const
    {
        return (i >= top_block_size_) ? 0 : blocks_[i];
    }

    bm::word_t*** get_rootblock() const
    {
        blocks_manager* bm = 
            const_cast<blocks_manager*>(this);
        return bm->blocks_root();
    }

    void free_block(bm::word_t* block)
    {
        if (BM_IS_GAP(block))
        {
            alloc_.free_gap_block(BMGAP_PTR(block), glevel_len_);
        }
        else
        {
            alloc_.free_bit_block(block);
        }
    }

    void set_block_all_set(unsigned nb)
    {
        bm::word_t* block = 
            set_block(nb, const_cast<bm::word_t*>(FULL_BLOCK_ADDR));
        free_block(block);
    }

    bm::word_t* alloc_bit_block(unsigned nb)
    {
        bm::word_t* block = this->get_allocator().alloc_bit_block();
        bm::word_t* old_block = set_block(nb, block);
        if (IS_VALID_ADDR(old_block))
        {
            free_block(old_block);
        }
        return block;
    }

    bm::word_t* make_bit_block(unsigned nb)
    {
        bm::word_t* block = this->alloc_bit_block(nb);
        bit_block_set(block, 0);
        return block;
    }

    bm::word_t* copy_bit_block(unsigned          nb, 
                               const bm::word_t* block_src, int is_src_gap)
    {
        if (block_src == 0)
        {
            zero_block(nb);
            return 0;
        }
        bm::word_t* block = alloc_bit_block(nb);
        if (is_src_gap)
        {
            gap_word_t* gap_block = BMGAP_PTR(block_src);
            gap_convert_to_bitset(block, gap_block);
        }
        else
        {            
            bit_block_copy(block, block_src);
        }
        return block;
    }

    bm::word_t* copy_block(unsigned idx, const blocks_manager& bm_src)
    {
        const bm::word_t* block = bm_src.get_block(idx);
        if (block == 0)
        {
            zero_block(idx);
            return 0;
        }
        bm::word_t* new_blk = 0;
        bool is_gap = BM_IS_GAP(block);

        if (is_gap)
        {
            bm::gap_word_t* gap_block = BMGAP_PTR(block); 
            unsigned level = gap_level(gap_block);
            new_blk = (bm::word_t*)
                get_allocator().alloc_gap_block(level, glen());
            int len = gap_length(BMGAP_PTR(block));
            ::memcpy(new_blk, gap_block, len * sizeof(gap_word_t));
            set_gap_level(new_blk, level);
        }
        else
        {
            if (IS_FULL_BLOCK(block))
            {
                new_blk = FULL_BLOCK_ADDR;
            }
            else
            {
                new_blk = get_allocator().alloc_bit_block();
                bit_block_copy(new_blk, block);
            }
        }
        set_block(idx, new_blk, is_gap);
        return new_blk;
    }


    bm::word_t* check_allocate_block(unsigned nb, 
                                     unsigned content_flag,
                                     int      initial_block_type,
                                     int*     actual_block_type,
                                     bool     allow_null_ret=true)
    {
        bm::word_t* block = this->get_block(nb);

        if (!IS_VALID_ADDR(block)) // NULL block or ALLSET
        {
            // if we wanted ALLSET and requested block is ALLSET return NULL
            unsigned block_flag = IS_FULL_BLOCK(block);
            *actual_block_type = initial_block_type;
            if (block_flag == content_flag && allow_null_ret)
            {
                return 0; // it means nothing to do for the caller
            }

            if (initial_block_type == 0) // bitset requested
            {
                block = alloc_.alloc_bit_block();
                // initialize block depending on its previous status
                bit_block_set(block, block_flag ? 0xFF : 0);
                set_block(nb, block, false /*bit*/);
            }
            else // gap block requested
            {
                bm::gap_word_t* gap_block = allocate_gap_block(0);
                gap_set_all(gap_block, bm::gap_max_bits, block_flag);
                set_block(nb, (bm::word_t*)gap_block, true/*gap*/);
                return (bm::word_t*)gap_block;
            }
        }
        else // block already exists
        {
            *actual_block_type = BM_IS_GAP(block);
        }

        return block;
    }

    void set_all_zero(bool free_mem)
    {        
        if (free_mem)
        {
            // TODO: optimization of top-level realloc
            deinit_tree();
            init_tree();
        }
        else
        {
            block_zero_func zero_func(*this);
            unsigned top_size = this->effective_top_block_size();
            for_each_nzblock(blocks_, top_size,  zero_func);
        }
    }

    void set_all_one()
    {
        block_one_func func(*this);
        for_each_block(blocks_, top_block_size_, 
                                bm::set_array_size, func);
    }

    bm::word_t* set_block(unsigned nb, bm::word_t* block)
    {
        register unsigned nblk_blk = nb >> bm::set_array_shift;

        // auto-resize the top block array
        if (nblk_blk >= top_block_size_)
            reserve_top_blocks(nblk_blk + 1);
        if (nblk_blk >= effective_top_block_size_)
            effective_top_block_size_ = nblk_blk + 1;

        // If first level array not yet allocated, allocate it and
        // assign block to it
        if (blocks_[nblk_blk] == 0) 
        {
            blocks_[nblk_blk] = (bm::word_t**)alloc_.alloc_ptr();
            ::memset(blocks_[nblk_blk], 0, 
                bm::set_array_size * sizeof(bm::word_t*));
        }

        // NOTE: block will be replaced without freeing
        unsigned j = nb & bm::set_array_mask;
        bm::word_t* old_block = blocks_[nblk_blk][j];
        blocks_[nblk_blk][j] = block;

        return old_block;
    }


    bm::word_t* set_gap_block(unsigned      nb,
                          const gap_word_t* gap_block_src,
                          int               level)
    {
        if (level == -1)
        {
            bm::word_t* blk = get_allocator().alloc_bit_block();
            set_block(nb, blk);
            gap_convert_to_bitset(blk, gap_block_src);
            return blk;
        }
        else
        {
            gap_word_t* gap_blk = get_allocator().alloc_gap_block(
                                                         level, this->glen());
            gap_word_t* gap_blk_ptr = BMGAP_PTR(gap_blk);
            ::memcpy(gap_blk_ptr, gap_block_src, 
                                  gap_length(gap_block_src) * sizeof(gap_word_t));
            set_gap_level(gap_blk_ptr, level);
            set_block(nb, (bm::word_t*)gap_blk, true /*GAP*/);
            return (bm::word_t*)gap_blk;
        }
    }

    bm::word_t* set_block(unsigned nb, bm::word_t* block, bool gap)
    {
        if (block)
        {
            block = 
                (bm::word_t*) (gap ? BMPTR_SETBIT0(block) : BMPTR_CLEARBIT0(block));
        }

        // top block index
        register unsigned nblk_blk = nb >> bm::set_array_shift;

        // auto-resize the top block array
        if (nblk_blk >= top_block_size_)
            reserve_top_blocks(nblk_blk + 1);
        if (nblk_blk >= effective_top_block_size_)
            effective_top_block_size_ = nblk_blk + 1;

        // If first level array not yet allocated, allocate it and
        // assign block to it
        if (blocks_[nblk_blk] == 0) 
        {
            blocks_[nblk_blk] = (bm::word_t**)alloc_.alloc_ptr();
            ::memset(blocks_[nblk_blk], 0, 
                bm::set_array_size * sizeof(bm::word_t*));
        }

        // NOTE: block will be replaced without freeing
        unsigned j = nb & bm::set_array_mask;
        bm::word_t* old_block = blocks_[nblk_blk][j];
        blocks_[nblk_blk][j] = block; 

        return old_block;
    }

    void set_block_ptr(unsigned nb, bm::word_t* block)
    {
        BM_ASSERT((nb >> bm::set_array_shift) < effective_top_block_size_);
        blocks_[nb >> bm::set_array_shift][nb & bm::set_array_mask] = block;
    }
        
    bm::word_t* convert_gap2bitset(unsigned nb, 
                                   const gap_word_t* gap_block=0, 
                                   unsigned gap_len=0)
    {
        bm::word_t* block = this->get_block(nb);
        if (gap_block == 0)
        {
            gap_block = BMGAP_PTR(block);
        }

        BM_ASSERT(IS_VALID_ADDR((bm::word_t*)gap_block));

        bm::word_t* new_block = alloc_.alloc_bit_block();
        gap_convert_to_bitset_l(new_block, gap_block, gap_len);

        // new block will replace the old one(no deletion)
        //set_block_ptr(nb, new_block); 
        if (block)
        {
            set_block_ptr(nb, new_block); 
            alloc_.free_gap_block(BMGAP_PTR(block), glen());
        }
        else
        {
            set_block(nb, new_block); 
        }

        return new_block;
    }

    bm::word_t* deoptimize_block(unsigned nb)
    {
        bm::word_t* block = this->get_block(nb);
        if (BM_IS_GAP(block))
        {
            return convert_gap2bitset(nb);
        }
        if (IS_FULL_BLOCK(block)) 
        {
            bm::word_t* new_block = get_allocator().alloc_bit_block();
            bit_block_copy(new_block, block);
            set_block(nb, new_block);
            return new_block;
        }
        return block;
    }

    bm::word_t* zero_block(unsigned nb)
    {
        bm::word_t* block = this->get_block(nb);
        if (!block) return block;
        free_block(block);
        set_block(nb, 0);
        return 0;
    }

    bm::word_t* zero_block(unsigned i, unsigned j)
    {
        bm::word_t** blk_blk = blocks_[i];
        bm::word_t* block = blk_blk[j];
        blk_blk[j] = 0;

        free_block(block);

        return 0;
    }


    bm::id_t block_bitcount(const bm::word_t* block) const
    { 
        if (!block) return 0;
        id_t count;

        if (BM_IS_GAP(block))
        {
            count = gap_bit_count(BMGAP_PTR(block));
        }
        else // bitset
        {
            count = (IS_FULL_BLOCK(block)) ? bm::bits_in_block
                : bit_block_calc_count(block, block + bm::set_block_size);
        }
        return count;
    }

    bm::gap_word_t* extend_gap_block(unsigned nb, gap_word_t* blk)
    {
        unsigned level = bm::gap_level(blk);
        unsigned len = bm::gap_length(blk);
        if (level == bm::gap_max_level || len >= gap_max_buff_len)
        {
            convert_gap2bitset(nb);
        }
        else
        {
            bm::gap_word_t* new_gap_blk = allocate_gap_block(++level, blk);
            bm::word_t* new_blk = (bm::word_t*)new_gap_blk;

            BMSET_PTRGAP(new_blk);

            set_block_ptr(nb, new_blk);
            alloc_.free_gap_block(blk, glen());

            return new_gap_blk;
        }
        return 0;
    }

    bool is_block_gap(unsigned nb) const 
    {
        bm::word_t* block = get_block(nb);
        return BMPTR_TESTBIT0(block) != 0;
    }

    void set_block_bit(unsigned nb) 
    { 
        bm::word_t* block = get_block(nb);
        block = (bm::word_t*) BMPTR_CLEARBIT0(block);
        set_block_ptr(nb, block);
    }

    void set_block_gap(unsigned nb) 
    {
        bm::word_t* block = get_block(nb);
        block = (bm::word_t*)BMPTR_SETBIT0(block);
        set_block_ptr(nb, block);
    }

    bool is_block_zero(unsigned          nb, 
                       const bm::word_t* blk, 
                       bool              deep_scan = true) const
    {
        if (blk == 0) return true;

        if (BM_IS_GAP(blk))
        {
            gap_word_t* b = BMGAP_PTR(blk);
            return gap_is_all_zero(b, bm::gap_max_bits);
        }

        if (!deep_scan) 
            return false; // block exists - presume it has bits

        // BIT
        for (unsigned i = 0; i <  bm::set_block_size; ++i)
        {
            if (blk[i] != 0)
                return false;
        }
        return true;
    }

    bool is_block_one(unsigned          nb, 
                      const bm::word_t* blk,
                      bool              deep_scan = true) const
    {
        if (blk == 0) return false;

        if (BM_IS_GAP(blk))
        {
            gap_word_t* b = BMGAP_PTR(blk);
            return gap_is_all_one(b, bm::gap_max_bits);
        }

        // BIT block
        if (IS_FULL_BLOCK(blk))
        {
            return true;
        }
        if (!deep_scan) 
            return false; // block exists - presume it has 0 bits

        return is_bits_one((wordop_t*)blk, 
                           (wordop_t*)(blk + bm::set_block_size));
    }

    bm::word_t* check_allocate_tempblock()
    {
        return temp_block_ ? temp_block_ 
                            : (temp_block_ = alloc_.alloc_bit_block());
    }

    void set_glen(const gap_word_t* glevel_len)
    {
        ::memcpy(glevel_len_, glevel_len, sizeof(glevel_len_));
    }


    bm::gap_word_t* allocate_gap_block(unsigned level, 
                                       const gap_word_t* src = 0,
                                       const gap_word_t* glevel_len = 0)
    {
        if (!glevel_len)
            glevel_len = glevel_len_;
        gap_word_t* ptr = alloc_.alloc_gap_block(level, glevel_len);
        if (src)
        {
            unsigned len = gap_length(src);
            ::memcpy(ptr, src, len * sizeof(gap_word_t));
            // Reconstruct the mask word using the new level code.
            *ptr = (gap_word_t)(((len-1) << 3) | (level << 1) | (*src & 1));
        }
        else
        {
            *ptr = (gap_word_t)(level << 1);
        }
        return ptr;
    }

    unsigned mem_used() const
    {
        unsigned mem_used = sizeof(*this);
        mem_used += temp_block_ ? sizeof(word_t) * bm::set_block_size : 0;
        mem_used += sizeof(bm::word_t**) * top_block_size_;

        for (unsigned i = 0; i < top_block_size_; ++i)
        {
            mem_used += blocks_[i] ? sizeof(void*) * bm::set_array_size : 0;
        }

        return mem_used;
    }

    bool is_subblock_null(unsigned nsub) const
    {
        return blocks_[nsub] == NULL;
    }


    bm::word_t***  blocks_root()
    {
        return blocks_;
    }

    const gap_word_t* glen() const
    {
        return glevel_len_;
    }

    unsigned glen(unsigned level) const
    {
        return glevel_len_[level];
    }

    void swap(blocks_manager& bm)
    {
        BM_ASSERT(this != &bm);

        word_t*** btmp = blocks_;
        blocks_ = bm.blocks_;
        bm.blocks_ = btmp;

        xor_swap(this->top_block_size_, bm.top_block_size_);
        xor_swap(this->effective_top_block_size_, bm.effective_top_block_size_);

        BM_ASSERT(sizeof(glevel_len_) / sizeof(glevel_len_[0]) 
                                    == bm::gap_levels); // paranoiya check
        for (unsigned i = 0; i < bm::gap_levels; ++i)
        {
            xor_swap(glevel_len_[i], bm.glevel_len_[i]);
        }
    }

    unsigned top_block_size() const
    {
        return top_block_size_;
    }

    unsigned effective_top_block_size() const
    {
        return effective_top_block_size_;
    }

    void reserve(unsigned max_bits)
    {
        if (max_bits) 
        {
            unsigned b = compute_top_block_size(max_bits);
            reserve_top_blocks(b);
        }
    }

    void reserve_top_blocks(unsigned top_blocks) 
    {
        BM_ASSERT(top_blocks <= bm::set_array_size);
        if (top_blocks <= top_block_size_) return; // nothing to do
        bm::word_t*** new_blocks = 
            (bm::word_t***)alloc_.alloc_ptr(top_blocks);

        for (unsigned i = 0; i < top_block_size_; ++i)
        {
            new_blocks[i] = blocks_[i];
        }
        for (unsigned j = top_block_size_; j < top_blocks; ++j)
        {
            new_blocks[j] = 0;
        }
        alloc_.free_ptr(blocks_, top_block_size_);
        blocks_ = new_blocks;
        top_block_size_ = top_blocks;
    }
    
    allocator_type& get_allocator() { return alloc_; }

    allocator_type get_allocator() const { return alloc_; }

private:

    void operator =(const blocks_manager&);

    void deinit_tree()
    {
        if (blocks_ == 0) return;
        unsigned top_size = this->effective_top_block_size();
        block_free_func  free_func(*this);
        for_each_nzblock2(blocks_, top_size, free_func);
        free_top_block();
        alloc_.free_ptr(blocks_, top_block_size_);
        blocks_ = 0;
    }

    void free_top_block()
    {
        for(unsigned i = 0; i < top_block_size_; ++i)
        {
            bm::word_t** blk_blk = blocks_[i];
            if (blk_blk) 
            {
                alloc_.free_ptr(blk_blk); blocks_[i] = 0;
            }
        }
    }

    void init_tree()
    {
        if (top_block_size_)
        {
            blocks_ = (bm::word_t***) alloc_.alloc_ptr(top_block_size_); 
            ::memset(blocks_, 0, top_block_size_ * sizeof(bm::word_t**));
        }
        else
        {
            blocks_ = 0;
        }
        effective_top_block_size_ = 1;
    }

private:
    bm::word_t***                          blocks_;
    unsigned                               top_block_size_;
    unsigned                               effective_top_block_size_;
    bm::word_t*                            temp_block_; 
    gap_word_t                             glevel_len_[bm::gap_levels];
    allocator_type                         alloc_;
};

template<class BlocksManager>
class bit_block_guard
{
public:
    bit_block_guard(BlocksManager& bman, bm::word_t* blk=0) 
        : bman_(bman), 
          block_(blk)
    {}
    ~bit_block_guard()
    {
        bman_.get_allocator().free_bit_block(block_, 3);
    }
    void attach(bm::word_t* blk)
    {
        bman_.get_allocator().free_bit_block(block_);
        block_ = blk;
    }
    bm::word_t* allocate()
    {
        attach(bman_.get_allocator().alloc_bit_block(3));
        return block_;
    }
    bm::word_t* get() { return block_; }

private:
    bit_block_guard(const bit_block_guard&);
    bit_block_guard& operator=(const bit_block_guard&);
private:
    BlocksManager& bman_;
    bm::word_t*    block_;
};


}

#ifdef _MSC_VER
#pragma warning( pop )
#endif

#endif