bm.h

ncbi源码

       when it is benefitial. 
   
       \param buf - pointer on target memory area. No range checking in the
       function. It is responsibility of programmer to allocate sufficient 
       amount of memory using information from calc_stat function.

       \param temp_block - pointer on temporary memory block. Cannot be 0; 
       If you want to save memory across multiple bvectors
       allocate temporary block using allocate_tempblock and pass it to 
       serialize_const.
       (Of course serialize does not deallocate temp_block.)

       \return Size of serialization block.
       \sa calc_stat
    */
    /*
     Serialization format:
     <pre>
  
     | HEADER | BLOCKS |

     Header structure:
       BYTE : Serialization type (0x1)
       BYTE : Byte order ( 0 - Big Endian, 1 - Little Endian)
       INT16: Reserved (0)
       INT16: Reserved Flags (0)
  
     </pre>
    */
    unsigned serialize(unsigned char* buf, bm::word_t* temp_block) const
    {
        bm::encoder enc(buf, 0);
        assert(temp_block);
        gap_word_t*  gap_temp_block = (gap_word_t*) temp_block;

        // Header

        ByteOrder bo = globals<true>::byte_order();
            // g_initial_setup.get_byte_order();
        enc.put_8(1);
        enc.put_8((unsigned char)bo);

        unsigned i,j;

        // keep GAP levels information
        for (i = 0; i < bm::gap_levels; ++i)
        {
            enc.put_16(blockman_.glen()[i]);
        }

        // Blocks.

        for (i = 0; i < bm::set_total_blocks; ++i)
        {
            bm::word_t* blk = blockman_.get_block(i);

            // -----------------------------------------
            // Empty or ONE block serialization

            bool flag;
            flag = blockman_.is_block_zero(i, blk);
            if (flag)
            {
                // Look ahead for similar blocks
                for(j = i+1; j < bm::set_total_blocks; ++j)
                {
                   bm::word_t* blk_next = blockman_.get_block(j);
                   if (flag != blockman_.is_block_zero(j, blk_next))
                       break;
                }
                if (j == bm::set_total_blocks)
                {
                    enc.put_8(set_block_azero);
                    break; 
                }
                else
                {
                   unsigned nb = j - i;
                   SER_NEXT_GRP(enc, nb, set_block_1zero, 
                                         set_block_8zero, 
                                         set_block_16zero, 
                                         set_block_32zero) 
                }
                i = j - 1;
                continue;
            }
            else
            {
                flag = blockman_.is_block_one(i, blk);
                if (flag)
                {
                    // Look ahead for similar blocks
                    for(j = i+1; j < bm::set_total_blocks; ++j)
                    {
                       bm::word_t* blk_next = blockman_.get_block(j);
                       if (flag != blockman_.is_block_one(j, blk_next))
                           break;
                    }
                    if (j == bm::set_total_blocks)
                    {
                        enc.put_8(set_block_aone);
                        break;
                    }
                    else
                    {
                       unsigned nb = j - i;
                       SER_NEXT_GRP(enc, nb, set_block_1one, 
                                             set_block_8one, 
                                             set_block_16one, 
                                             set_block_32one) 
                    }
                    i = j - 1;
                    continue;
                }
            }

            // ------------------------------
            // GAP serialization

            if (BM_IS_GAP(blockman_, blk, i))
            {
                gap_word_t* gblk = BMGAP_PTR(blk);
                unsigned len = gap_length(gblk);
                enc.put_8(set_block_gap);
                for (unsigned k = 0; k < (len-1); ++k)
                {
                    enc.put_16(gblk[k]);
                }
                continue;
            }

            // -------------------------------
            // BIT BLOCK serialization
       
            // Try to reduce the size up to the reasonable limit.
    /*
            unsigned len = bm::bit_convert_to_gap(gap_temp_block, 
                                                  blk, 
                                                  bm::GAP_MAX_BITS, 
                                                  bm::GAP_EQUIV_LEN-64);
    */
            gap_word_t len;

            len = bit_convert_to_arr(gap_temp_block, 
                                     blk, 
                                     bm::gap_max_bits, 
                                     bm::gap_equiv_len-64);

            if (len)  // reduced
            {
    //            len = gap_length(gap_temp_block);
    //            enc.put_8(SET_BLOCK_GAPBIT);
    //            enc.memcpy(gap_temp_block, sizeof(gap_word_t) * (len - 1));
                enc.put_8(set_block_arrbit);
                if (sizeof(gap_word_t) == 2)
                {
                    enc.put_16(len);
                }
                else
                {
                    enc.put_32(len);
                }
                for (unsigned k = 0; k < len; ++k)
                {
                    enc.put_16(gap_temp_block[k]);
                } 
                // enc.memcpy(gap_temp_block, sizeof(gap_word_t) * len);
            }
            else
            {
                enc.put_8(set_block_bit);
                enc.memcpy(blk, sizeof(bm::word_t) * bm::set_block_size);
            }

        }

        enc.put_8(set_block_end);
        return enc.size();
    }

    /*!
        @brief Bitvector deserialization from memory.

        @param buf - pointer on memory which keeps serialized bvector
        @param temp_block - pointer on temporary block, 
                if NULL bvector allocates own.
        @return Number of bytes consumed by deserializer.

        Function desrializes bitvector from memory block containig results
        of previous serialization. Function does not remove bits 
        which are currently set. Effectively it means OR logical operation 
        between current bitset and previously serialized one.
    */
    unsigned deserialize(const unsigned char* buf, bm::word_t* temp_block=0)
    {
        bm::wordop_t* tmp_buf = 
            temp_block ? (bm::wordop_t*) temp_block 
                       : (bm::wordop_t*)blockman_.check_allocate_tempblock();

        temp_block = (word_t*)tmp_buf;

        gap_word_t   gap_temp_block[set_block_size*2+10];


        ByteOrder bo_current = globals<true>::byte_order();
        bm::decoder dec(buf);

        BMCOUNT_VALID(false);

        BM_SET_MMX_GUARD

        // Reading header

        // unsigned char stype =  
        dec.get_8();
        ByteOrder bo = (bm::ByteOrder)dec.get_8();

        assert(bo == bo_current); // TO DO: Add Byte-Order convertions here

        unsigned i;

        gap_word_t glevels[bm::gap_levels];
        // keep GAP levels information
        for (i = 0; i < bm::gap_levels; ++i)
        {
            glevels[i] = dec.get_16();
        }

        // Reading blocks

        unsigned char btype;
        unsigned nb;

        for (i = 0; i < bm::set_total_blocks; ++i)
        {
            // get the block type
        
            btype = dec.get_8();

 
            // In a few next blocks of code we simply ignoring all coming zero blocks.

            if (btype == set_block_azero || btype == set_block_end)
            {
                break;
            }

            if (btype == set_block_1zero)
            {
                continue;
            }

            if (btype == set_block_8zero)
            {
                nb = dec.get_8();
                i += nb-1;
                continue;
            }

            if (btype == set_block_16zero)
            {
                nb = dec.get_16();
                i += nb-1;
                continue;
            }

            if (btype == set_block_32zero)
            {
                nb = dec.get_32();
                i += nb-1;
                continue;
            }

            // Now it is turn of all-set blocks (111)

            if (btype == set_block_aone)
            {
                for (unsigned j = i; j < bm::set_total_blocks; ++j)
                {
                    blockman_.set_block_all_set(j);
                }
                break;
            }

            if (btype == set_block_1one)
            {
                blockman_.set_block_all_set(i);
                continue;
            }

            if (btype == set_block_8one)
            {
                BM_SET_ONE_BLOCKS(dec.get_8());
                continue;
            }

            if (btype == set_block_16one)
            {
                BM_SET_ONE_BLOCKS(dec.get_16());
                continue;
            }

            if (btype == set_block_32one)
            {
                BM_SET_ONE_BLOCKS(dec.get_32());
                continue;
            }

            bm::word_t* blk = blockman_.get_block(i);


            if (btype == set_block_bit) 
            {
                if (blk == 0)
                {
                    blk = A::alloc_bit_block();
                    blockman_.set_block(i, blk);
                    dec.memcpy(blk, sizeof(bm::word_t) * bm::set_block_size);
                    continue;                
                }

                dec.memcpy(temp_block, sizeof(bm::word_t) * bm::set_block_size);
                combine_operation_with_block(i, 
                                             temp_block, 
                                             0, BM_OR);
                continue;
            }

            if (btype == set_block_gap || btype == set_block_gapbit)
            {
                gap_word_t gap_head = 
                    sizeof(gap_word_t) == 2 ? dec.get_16() : dec.get_32();

                unsigned len = gap_length(&gap_head);
                int level = gap_calc_level(len, blockman_.glen());
                --len;
                if (level == -1)  // Too big to be GAP: convert to BIT block
                {
                    *gap_temp_block = gap_head;
                    dec.memcpy(gap_temp_block+1, (len-1) * sizeof(gap_word_t));
                    gap_temp_block[len] = gap_max_bits - 1;

                    if (blk == 0)  // block does not exist yet
                    {
                        blk = A::alloc_bit_block();
                        blockman_.set_block(i, blk);
                        gap_convert_to_bitset(blk, 
                                              gap_temp_block, 
                                              bm::set_block_size);                
                    }
                    else  // We have some data already here. Apply OR operation.
                    {
                        gap_convert_to_bitset(temp_block, 
                                              gap_temp_block, 
                                              bm::set_block_size);

                        combine_operation_with_block(i, 
                                                    temp_block, 
                                                    0, 
                                                    BM_OR);
                    }

                    continue;
                } // level == -1

                set_gap_level(&gap_head, level);
            
                if (blk == 0)
                {
                    gap_word_t* gap_blk = A::alloc_gap_block(level, blockman_.glen());
                    gap_word_t* gap_blk_ptr = BMGAP_PTR(gap_blk);
                    *gap_blk_ptr = gap_head;
                    set_gap_level(gap_blk_ptr, level);
                    blockman_.set_block(i, (bm::word_t*)gap_blk);
                    blockman_.set_block_gap(i);
                    for (unsigned k = 1; k < len; ++k) 
                    {
                         gap_blk[k] = dec.get_16();
                    }
                    gap_blk[len] = bm::gap_max_bits - 1;
                }
                else
                {
                    *gap_temp_block = gap_head;
                    for (unsigned k = 1; k < len; ++k) 
                    {
                         gap_temp_block[k] = dec.get_16();
                    }
                    gap_temp_block[len] = bm::gap_max_bits - 1;

                    combine_operation_with_block(i, 
                                                (bm::word_t*)gap_temp_block, 
                                                 1, 
                                                 BM_OR);
                }

                continue;
            }

            if (btype == set_block_arrbit)
            {
                gap_word_t len = 
                    sizeof(gap_word_t) == 2 ? dec.get_16() : dec.get_32();

                // check the block type.
                if (blockman_.is_block_gap(i))
                {
                    // Here we most probably does not want to keep
                    // the block GAP since generic bitblock offers better
                    // performance.
                    blk = blockman_.convert_gap2bitset(i);
                }
                else
                {
                    if (blk == 0)  // block does not exists yet
                    {
                        blk = A::alloc_bit_block();
                        bit_block_set(blk, 0);
                        blockman_.set_block(i, blk);
                    }
                }

                // Get the array one by one and set the bits.
                for (unsigned k = 0; k < len; ++k)
                {
                    gap_word_t bit_idx = dec.get_16();
                    or_bit_block(blk, bit_idx, 1);
                }

                continue;
            }
/*
            if (btype == set_block_gapbit)
            {
                gap_word_t gap_head = 
                    sizeof(gap_word_t) == 2 ? dec.get_16() : dec.get_32();

                unsigned len = gap_length(&gap_head)-1;

                *gap_temp_block = gap_head;
                dec.memcpy(gap_temp_block+1, (len-1) * sizeof(gap_word_t));
                gap_temp_block[len] = GAP_MAX_BITS - 1;

                if (blk == 0)  // block does not exists yet
                {
                    blk = A::alloc_bit_block();
                    blockman_.set_bloc