bm.h

ncbi源码

    /*!
        \brief Inverts all bits.
    */
    bvector<A, MS>& invert()
    {
        BMCOUNT_VALID(false)
        BM_SET_MMX_GUARD

        bm::word_t*** blk_root = blockman_.get_rootblock();
        typename blocks_manager::block_invert_func func(blockman_);    
        for_each_block(blk_root, blockman_.top_block_size(),
                                 bm::set_array_size, func);
        set(bm::id_max, false);
        return *this;
    }


    /*!
       \brief returns true if bit n is set and false is bit n is 0. 
       \param n - Index of the bit to check.
       \return Bit value (1 or 0)
    */
    bool get_bit(bm::id_t n) const
    {    
        BM_ASSERT(n < bm::id_max);

        // calculate logical block number
        unsigned nblock = unsigned(n >>  bm::set_block_shift); 

        const bm::word_t* block = blockman_.get_block(nblock);

        if (block)
        {
            // calculate word number in block and bit
            unsigned nbit = unsigned(n & bm::set_block_mask); 
            unsigned is_set;

            if (BM_IS_GAP(blockman_, block, nblock))
            {
                is_set = gap_test(BMGAP_PTR(block), nbit);
            }
            else 
            {
                unsigned nword  = unsigned(nbit >> bm::set_word_shift); 
                nbit &= bm::set_word_mask;

                is_set = (block[nword] & (((bm::word_t)1) << nbit));
            }
            return is_set != 0;
        }
        return false;
    }

    /*!
       \brief returns true if bit n is set and false is bit n is 0. 
       \param n - Index of the bit to check.
       \return Bit value (1 or 0)
    */
    bool test(bm::id_t n) const 
    { 
        return get_bit(n); 
    }

    /*!
       \brief Returns true if any bits in this bitset are set, and otherwise returns false.
       \return true if any bit is set
    */
    bool any() const
    {
    #ifdef BMCOUNTOPT
        if (count_is_valid_ && count_) return true;
    #endif
        
        bm::word_t*** blk_root = blockman_.get_rootblock();
        typename blocks_manager::block_any_func func(blockman_);
        return for_each_nzblock_if(blk_root, blockman_.top_block_size(),
                                             bm::set_array_size, func);
    }

    /*!
        \brief Returns true if no bits are set, otherwise returns false.
    */
    bool none() const
    {
        return !any();
    }

    /*!
       \brief Flips bit n
       \return *this
    */
    bvector<A, MS>& flip(bm::id_t n) 
    {
        set(n, !get_bit(n));
        return *this;
    }

    /*!
       \brief Flips all bits
       \return *this
    */
    bvector<A, MS>& flip() 
    {
        return invert();
    }

    /*! \brief Exchanges content of bv and this bitvector.
    */
    void swap(bvector<A, MS>& bv)
    {
        blockman_.swap(bv.blockman_);
#ifdef BMCOUNTOPT
        BMCOUNT_VALID(false)
        bv.recalc_count();
#endif
    }


    /*!
       \fn bm::id_t bvector::get_first() const
       \brief Gets number of first bit which is ON.
       \return Index of the first 1 bit.
       \sa get_next
    */
    bm::id_t get_first() const { return check_or_next(0); }

    /*!
       \fn bm::id_t bvector::get_next(bm::id_t prev) const
       \brief Finds the number of the next bit ON.
       \param prev - Index of the previously found bit. 
       \return Index of the next bit which is ON or 0 if not found.
       \sa get_first
    */
    bm::id_t get_next(bm::id_t prev) const
    {
        return (++prev == bm::id_max) ? 0 : check_or_next(prev);
    }

    /*!
       @brief Calculates bitvector statistics.

       @param st - pointer on statistics structure to be filled in. 

       Function fills statistics structure containing information about how 
       this vector uses memory and estimation of max. amount of memory 
       bvector needs to serialize itself.

       @sa statistics
    */
    void calc_stat(struct statistics* st) const;

    /*!
       \brief Logical OR operation.
       \param vect - Argument vector.
    */
    bm::bvector<A, MS>& bit_or(const  bm::bvector<A, MS>& vect)
    {
        BMCOUNT_VALID(false);
        combine_operation(vect, BM_OR);
        return *this;
    }

    /*!
       \brief Logical AND operation.
       \param vect - Argument vector.
    */
    bm::bvector<A, MS>& bit_and(const bm::bvector<A, MS>& vect)
    {
        BMCOUNT_VALID(false);
        combine_operation(vect, BM_AND);
        return *this;
    }

    /*!
       \brief Logical XOR operation.
       \param vect - Argument vector.
    */
    bm::bvector<A, MS>& bit_xor(const bm::bvector<A, MS>& vect)
    {
        BMCOUNT_VALID(false);
        combine_operation(vect, BM_XOR);
        return *this;
    }

    /*!
       \brief Logical SUB operation.
       \param vect - Argument vector.
    */
    bm::bvector<A, MS>& bit_sub(const bm::bvector<A, MS>& vect)
    {
        BMCOUNT_VALID(false);
        combine_operation(vect, BM_SUB);
        return *this;
    }


    /*!
       \brief Sets new blocks allocation strategy.
       \param strat - Strategy code 0 - bitblocks allocation only.
                      1 - Blocks mutation mode (adaptive algorithm)
    */
    void set_new_blocks_strat(strategy strat) 
    { 
        new_blocks_strat_ = strat; 
    }

    /*!
       \brief Returns blocks allocation strategy.
       \return - Strategy code 0 - bitblocks allocation only.
                 1 - Blocks mutation mode (adaptive algorithm)
       \sa set_new_blocks_strat
    */
    strategy  get_new_blocks_strat() const 
    { 
        return new_blocks_strat_; 
    }

    void stat(unsigned blocks=0) const;

    /*!
       \brief Optimize memory bitvector's memory allocation.
   
       Function analyze all blocks in the bitvector, compresses blocks 
       with a regular structure, frees some memory. This function is recommended
       after a bulk modification of the bitvector using set_bit, clear_bit or
       logical operations.
    */
    void optimize(bm::word_t* temp_block=0)
    {
        bm::word_t*** blk_root = blockman_.blocks_root();

        if (!temp_block)
            temp_block = blockman_.check_allocate_tempblock();

        typename 
          blocks_manager::block_opt_func  opt_func(blockman_, temp_block);
        for_each_nzblock(blk_root, blockman_.top_block_size(),
                                   bm::set_array_size, opt_func);
    }

    
    void optimize_gap_size()
    {
        struct bvector<A, MS>::statistics st;
        calc_stat(&st);

        if (!st.gap_blocks)
            return;

        gap_word_t opt_glen[bm::gap_levels];
        ::memcpy(opt_glen, st.gap_levels, bm::gap_levels * sizeof(*opt_glen));

        improve_gap_levels(st.gap_length, 
                                st.gap_length + st.gap_blocks, 
                                opt_glen);
        
        set_gap_levels(opt_glen);
    }


    /*!
        @brief Sets new GAP lengths table. All GAP blocks will be reallocated 
        to match the new scheme.

        @param glevel_len - pointer on C-style array keeping GAP block sizes. 
    */
    void set_gap_levels(const gap_word_t* glevel_len)
    {
        bm::word_t*** blk_root = blockman_.blocks_root();

        typename 
            blocks_manager::gap_level_func  gl_func(blockman_, glevel_len);

        for_each_nzblock(blk_root, blockman_.top_block_size(),
                                   bm::set_array_size, gl_func);

        blockman_.set_glen(glevel_len);
    }

    /*!
        \brief Lexicographical comparison with a bitvector.

        Function compares current bitvector with the provided argument 
        bit by bit and returns -1 if our bitvector less than the argument, 
        1 - greater, 0 - equal.
    */
    int compare(const bvector<A, MS>& bvect) const
    {
        int res;
        unsigned bn = 0;

        for (unsigned i = 0; i < blockman_.top_block_size(); ++i)
        {
            const bm::word_t* const* blk_blk = blockman_.get_topblock(i);
            const bm::word_t* const* arg_blk_blk = 
                                   bvect.blockman_.get_topblock(i);

            if (blk_blk == arg_blk_blk) 
            {
                bn += bm::set_array_size;
                continue;
            }

            for (unsigned j = 0; j < bm::set_array_size; ++j, ++bn)
            {
                const bm::word_t* arg_blk = 
                                    arg_blk_blk ? arg_blk_blk[j] : 0;
                const bm::word_t* blk = blk_blk ? blk_blk[j] : 0;

                if (blk == arg_blk) continue;

                // If one block is zero we check if the other one has at least 
                // one bit ON

                if (!blk || !arg_blk)  
                {
                    const bm::word_t*  pblk;
                    bool is_gap;

                    if (blk)
                    {
                        pblk = blk;
                        res = 1;
                        is_gap = BM_IS_GAP((*this), blk, bn);
                    }
                    else
                    {
                        pblk = arg_blk;
                        res = -1;
                        is_gap = BM_IS_GAP(bvect, arg_blk, bn);
                    }

                    if (is_gap)
                    {
                        if (!gap_is_all_zero(BMGAP_PTR(pblk), bm::gap_max_bits))
                        {
                            return res;
                        }
                    }
                    else
                    {
                        bm::wordop_t* blk1 = (wordop_t*)pblk;
                        bm::wordop_t* blk2 = 
                            (wordop_t*)(pblk + bm::set_block_size);
                        if (!bit_is_all_zero(blk1, blk2))
                        {
                            return res;
                        }
                    }

                    continue;
                }

                bool arg_gap = BM_IS_GAP(bvect, arg_blk, bn);
                bool gap = BM_IS_GAP((*this), blk, bn);

                if (arg_gap != gap)
                {
                    bm::wordop_t temp_blk[bm::set_block_size_op]; 
                    bm::wordop_t* blk1;
                    bm::wordop_t* blk2;

                    if (gap)
                    {
                        gap_convert_to_bitset((bm::word_t*)temp_blk, 
                                              BMGAP_PTR(blk), 
                                              bm::set_block_size);

                        blk1 = (bm::wordop_t*)temp_blk;
                        blk2 = (bm::wordop_t*)arg_blk;
                    }
                    else
                    {
                        gap_convert_to_bitset((bm::word_t*)temp_blk, 
                                              BMGAP_PTR(arg_blk), 
                                              bm::set_block_size);

                        blk1 = (bm::wordop_t*)blk;
                        blk2 = (bm::wordop_t*)temp_blk;

                    }                        
                    res = bitcmp(blk1, blk2, bm::set_block_size_op);  

                }
                else
                {
                    if (gap)
                    {
                        res = gapcmp(BMGAP_PTR(blk), BMGAP_PTR(arg_blk));
                    }
                    else
                    {
                        res = bitcmp((bm::wordop_t*)blk, 
                                     (bm::wordop_t*)arg_blk, 
                                      bm::set_block_size_op);
                    }
                }

                if (res != 0)
                {
                    return res;
                }
            

            } // for j

        } // for i

        return 0;
    }


    /*! @brief Allocates temporary block of memory. 

        Temp block can be passed to bvector functions requiring some temp memory
        for their operation. (like serialize)

        @sa free_tempblock
    */
    static bm::word_t* allocate_tempblock()
    {
        return A::alloc_bit_block();
    }

    /*! @brief Frees temporary block of memory. 
        @sa allocate_tempblock
    */
    static void free_tempblock(bm::word_t* block)
    {
        A::free_bit_block(block);
    }

    /*!
       @brief Serilizes bitvector into memory.
       Allocates temporary memory block for bvector.
       @sa serialize_const
    */
    unsigned serialize(unsigned char* buf)
    {
        return serialize(buf, blockman_.check_allocate_tempblock());
    }

    /*!
       \brief Serilizes bitvector into memory.
  
       Function serializes content of the bitvector into memory.
       Serialization adaptively uses compression(variation of GAP encoding)