NCBI C++ ToolKit
Classes | Functions
GAP functions

Classes

struct  bm::gap_len_table< T >
 Default GAP lengths table. More...
 
struct  bm::gap_len_table_min< T >
 Alternative GAP lengths table. Good for for memory saver mode and very sparse bitsets. More...
 
struct  bm::gap_len_table_nl< T >
 Non-linear size growth GAP lengths table. More...
 

Functions

template<typename T , typename Func , typename SIZE_TYPE >
int bm::for_each_gap_blk (const T *buf, SIZE_TYPE offset, Func &bit_functor)
 for-each visitor, calls a special visitor functor for each 1 bit range More...
 
template<typename T , typename Func , typename SIZE_TYPE >
int bm::for_each_gap_blk_range (const T *buf, SIZE_TYPE offset, unsigned left, unsigned right, Func &bit_functor)
 for-each visitor, calls a special visitor functor for each 1 bit range More...
 
bool bm::gap_is_all_zero (const bm::gap_word_t *buf) noexcept
 Checks if GAP block is all-zero. More...
 
bool bm::gap_is_all_one (const bm::gap_word_t *buf) noexcept
 Checks if GAP block is all-one. More...
 
bm::gap_word_t bm::gap_length (const bm::gap_word_t *buf) noexcept
 Returs GAP block length. More...
 
template<typename T >
unsigned bm::gap_capacity (const T *buf, const T *glevel_len) noexcept
 Returs GAP block capacity. More...
 
template<typename T >
unsigned bm::gap_limit (const T *buf, const T *glevel_len) noexcept
 Returs GAP block capacity limit. More...
 
template<typename T >
T bm::gap_level (const T *buf) noexcept
 Returs GAP blocks capacity level. More...
 
template<typename T >
unsigned bm::gap_find_last (const T *buf, unsigned *last) noexcept
 GAP block find the last set bit. More...
 
template<typename T >
unsigned bm::gap_find_first (const T *buf, unsigned *first) noexcept
 GAP block find the first set bit. More...
 
template<typename T >
unsigned bm::gap_test (const T *buf, unsigned pos) noexcept
 Tests if bit = pos is true. More...
 
template<typename T >
unsigned bm::gap_test_unr (const T *buf, const unsigned pos) noexcept
 Tests if bit = pos is true. Analog of bm::gap_test with SIMD unrolling. More...
 
template<typename T >
void bm::gap_split (const T *buf, T *arr0, T *arr1, T &arr0_cnt, T &arr1_cnt) noexcept
 
template<typename T >
unsigned bm::gap_bit_count (const T *buf, unsigned dsize=0) noexcept
 Calculates number of bits ON in GAP buffer. More...
 
template<typename T >
unsigned bm::gap_bit_count_unr (const T *buf) noexcept
 Calculates number of bits ON in GAP buffer. Loop unrolled version. More...
 
template<typename T , bool RIGHT_END = false>
unsigned bm::gap_bit_count_range (const T *const buf, unsigned left, unsigned right) noexcept
 Counts 1 bits in GAP buffer in the closed [left, right] range. More...
 
template<typename T >
unsigned bm::gap_bit_count_range_hint (const T *const buf, unsigned left, unsigned right, unsigned hint) noexcept
 Counts 1 bits in GAP buffer in the closed [left, right] range using position hint to avoid bfind. More...
 
template<typename T >
bool bm::gap_is_all_one_range (const T *const buf, unsigned left, unsigned right) noexcept
 Test if all bits are 1 in GAP buffer in the [left, right] range. More...
 
template<typename T >
bool bm::gap_any_range (const T *const buf, unsigned left, unsigned right) noexcept
 Test if any bits are 1 in GAP buffer in the [left, right] range. More...
 
template<typename T >
bool bm::gap_is_interval (const T *const buf, unsigned left, unsigned right) noexcept
 Test if any bits are 1 in GAP buffer in the [left, right] range and flanked with 0s. More...
 
template<typename T >
bool bm::gap_find_interval_end (const T *const buf, unsigned nbit, unsigned *pos) noexcept
 Searches for the last 1 bit in the 111 interval of a GAP block. More...
 
template<typename T >
bool bm::gap_find_interval_start (const T *const buf, unsigned nbit, unsigned *pos) noexcept
 Searches for the first 1 bit in the 111 interval of a GAP block. More...
 
template<typename T >
bool bm::gap_find_prev (const T *const buf, unsigned nbit, unsigned *pos) noexcept
 reverse search for the first 1 bit of a GAP block More...
 
template<typename T , typename SIZE_TYPE >
SIZE_TYPE bm::gap_find_rank (const T *const block, SIZE_TYPE rank, unsigned nbit_from, unsigned &nbit_pos) noexcept
 GAP block find position for the rank. More...
 
template<typename T >
int bm::gapcmp (const T *buf1, const T *buf2) noexcept
 Lexicographical comparison of GAP buffers. More...
 
template<typename T >
bool bm::gap_find_first_diff (const T *buf1, const T *buf2, unsigned *pos) noexcept
 Find first bit which is different between two GAP-blocks. More...
 
template<typename T , class F >
unsigned bm::gap_buff_any_op (const T *vect1, unsigned vect1_mask, const T *vect2, unsigned vect2_mask)
 Abstract distance test operation for GAP buffers. Receives functor F as a template argument. More...
 
template<typename T , class F >
unsigned bm::gap_buff_count_op (const T *vect1, const T *vect2)
 Abstract distance(similarity) operation for GAP buffers. Receives functor F as a template argument. More...
 
template<typename T >
unsigned bm::gap_set_value_cpos (unsigned val, T *buf, unsigned pos, unsigned *is_set, unsigned curr) noexcept
 Sets or clears bit in the GAP buffer. More...
 
template<typename T >
unsigned bm::gap_set_value (unsigned val, T *buf, unsigned pos, unsigned *is_set) noexcept
 Sets or clears bit in the GAP buffer. More...
 
template<typename T >
unsigned bm::gap_set_value (unsigned val, T *buf, unsigned pos) noexcept
 Sets or clears bit in the GAP buffer. More...
 
template<typename T >
unsigned bm::gap_add_value (T *buf, unsigned pos) noexcept
 Add new value to the end of GAP buffer. More...
 
template<typename T >
bool bm::gap_shift_r1 (T *buf, unsigned co_flag, unsigned *new_len) noexcept
 Right shift GAP block by 1 bit. More...
 
template<typename T >
bool bm::gap_insert (T *buf, unsigned pos, unsigned val, unsigned *new_len) noexcept
 isnert bit into GAP compressed block More...
 
template<typename T >
bool bm::gap_shift_l1 (T *buf, unsigned co_flag, unsigned *new_len) noexcept
 Left shift GAP block by 1 bit. More...
 
template<typename T >
unsigned bm::gap_set_array (T *buf, const T *arr, unsigned len) noexcept
 Convert array to GAP buffer. More...
 
template<typename T >
unsigned bm::bit_array_compute_gaps (const T *arr, unsigned len) noexcept
 Compute number of GAPs in bit-array. More...
 
template<typename T >
unsigned bm::gap_block_find (const T *buf, unsigned nbit, bm::id_t *prev) noexcept
 Searches for the next 1 bit in the GAP block. More...
 
template<typename T >
void bm::gap_sub_to_bitset (unsigned *dest, const T *pcurr) noexcept
 SUB (AND NOT) GAP block to bitblock. More...
 
template<typename T >
bm::id64_t bm::gap_sub_to_bitset (unsigned *dest, const T *pcurr, bm::id64_t digest0) noexcept
 SUB (AND NOT) GAP block to bitblock with digest assist. More...
 
template<typename T >
void bm::gap_xor_to_bitset (unsigned *dest, const T *pcurr) noexcept
 XOR GAP block to bitblock. More...
 
template<typename T >
void bm::gap_add_to_bitset (unsigned *dest, const T *pcurr, unsigned len) noexcept
 Adds(OR) GAP block to bitblock. More...
 
template<typename T >
void bm::gap_add_to_bitset (unsigned *dest, const T *pcurr) noexcept
 Adds(OR) GAP block to bitblock. More...
 
template<typename T >
void bm::gap_and_to_bitset (unsigned *dest, const T *pcurr) noexcept
 ANDs GAP block to bitblock. More...
 
template<typename T >
bm::id64_t bm::gap_and_to_bitset (unsigned *dest, const T *pcurr, bm::id64_t digest0) noexcept
 ANDs GAP block to bitblock with digest assist. More...
 
template<typename T >
bm::id_t bm::gap_bitset_and_count (const unsigned *block, const T *pcurr) noexcept
 Compute bitcount of bit block AND masked by GAP block. More...
 
template<typename T >
bm::id_t bm::gap_bitset_and_any (const unsigned *block, const T *pcurr) noexcept
 Bitcount test of bit block AND masked by GAP block. More...
 
template<typename T >
bm::id_t bm::gap_bitset_sub_count (const unsigned *block, const T *buf) noexcept
 Compute bitcount of bit block SUB masked by GAP block. More...
 
template<typename T >
bm::id_t bm::gap_bitset_sub_any (const unsigned *block, const T *buf) noexcept
 Compute bitcount test of bit block SUB masked by GAP block. More...
 
template<typename T >
bm::id_t bm::gap_bitset_xor_count (const unsigned *block, const T *buf) noexcept
 Compute bitcount of bit block XOR masked by GAP block. More...
 
template<typename T >
bm::id_t bm::gap_bitset_xor_any (const unsigned *block, const T *buf) noexcept
 Compute bitcount test of bit block XOR masked by GAP block. More...
 
template<typename T >
bm::id_t bm::gap_bitset_or_count (const unsigned *block, const T *buf) noexcept
 Compute bitcount of bit block OR masked by GAP block. More...
 
template<typename T >
bm::id_t bm::gap_bitset_or_any (const unsigned *block, const T *buf) noexcept
 Compute bitcount test of bit block OR masked by GAP block. More...
 
template<typename T >
void bm::gap_convert_to_bitset (unsigned *dest, const T *buf, unsigned len=0) noexcept
 GAP block to bitblock conversion. More...
 
template<typename T >
unsigned * bm::gap_convert_to_bitset_smart (unsigned *dest, const T *buf, id_t set_max) noexcept
 Smart GAP block to bitblock conversion. More...
 
template<typename T >
unsigned bm::gap_control_sum (const T *buf) noexcept
 Calculates sum of all words in GAP block. (For debugging purposes) More...
 
template<class T >
void bm::gap_set_all (T *buf, unsigned set_max, unsigned value) noexcept
 Sets all bits to 0 or 1 (GAP) More...
 
template<class T >
void bm::gap_init_range_block (T *buf, T from, T to, T value) noexcept
 Init gap block so it has block in it (can be whole block) More...
 
template<typename T >
void bm::gap_invert (T *buf) noexcept
 Inverts all bits in the GAP buffer. More...
 
template<typename T >
void bm::set_gap_level (T *buf, int level) noexcept
 Sets GAP block capacity level. More...
 
template<typename T >
int bm::gap_calc_level (unsigned len, const T *glevel_len) noexcept
 Calculates GAP block capacity level. More...
 
template<typename T >
unsigned bm::gap_free_elements (const T *buf, const T *glevel_len) noexcept
 Returns number of free elements in GAP block array. Difference between GAP block capacity on this level and actual GAP length. More...
 
unsigned bm::bit_block_to_gap (gap_word_t *dest, const unsigned *block, unsigned dest_len) noexcept
 Converts bit block to GAP. More...
 
template<class T , class F >
void bm::for_each_gap_dbit (const T *buf, F &func)
 Iterate gap block as delta-bits with a functor. More...
 
template<typename D , typename T >
bm::gap_convert_to_arr (D *dest, const T *buf, unsigned dest_len, bool invert=false) noexcept
 Convert gap block into array of ints corresponding to 1 bits. More...
 
gap_word_tbm::gap_operation_and (const gap_word_t *vect1, const gap_word_t *vect2, gap_word_t *tmp_buf, unsigned &dsize) noexcept
 GAP AND operation. More...
 
unsigned bm::gap_operation_any_and (const gap_word_t *vect1, const gap_word_t *vect2) noexcept
 GAP AND operation test. More...
 
unsigned bm::gap_count_and (const gap_word_t *vect1, const gap_word_t *vect2) noexcept
 GAP bitcount AND operation test. More...
 
gap_word_tbm::gap_operation_xor (const gap_word_t *vect1, const gap_word_t *vect2, gap_word_t *tmp_buf, unsigned &dsize) noexcept
 GAP XOR operation. More...
 
unsigned bm::gap_operation_any_xor (const gap_word_t *vect1, const gap_word_t *vect2) noexcept
 GAP XOR operation test. More...
 
unsigned bm::gap_count_xor (const gap_word_t *vect1, const gap_word_t *vect2) noexcept
 GAP bitcount XOR operation test. More...
 
gap_word_tbm::gap_operation_or (const gap_word_t *vect1, const gap_word_t *vect2, gap_word_t *tmp_buf, unsigned &dsize) noexcept
 GAP OR operation. More...
 
unsigned bm::gap_count_or (const gap_word_t *vect1, const gap_word_t *vect2) noexcept
 GAP bitcount OR operation test. More...
 
gap_word_tbm::gap_operation_sub (const gap_word_t *vect1, const gap_word_t *vect2, gap_word_t *tmp_buf, unsigned &dsize) noexcept
 GAP SUB (AND NOT) operation. More...
 
unsigned bm::gap_operation_any_sub (const gap_word_t *vect1, const gap_word_t *vect2) noexcept
 GAP SUB operation test. More...
 
unsigned bm::gap_count_sub (const gap_word_t *vect1, const gap_word_t *vect2) noexcept
 GAP bitcount SUB (AND NOT) operation test. More...
 
template<typename T >
unsigned bm::gap_overhead (const T *length, const T *length_end, const T *glevel_len) noexcept
 Calculates memory overhead for number of gap blocks sharing the same memory allocation table (level lengths table). More...
 
template<typename T >
bool bm::improve_gap_levels (const T *length, const T *length_end, T *glevel_len) noexcept
 Finds optimal gap blocks lengths. More...
 
template<typename T >
unsigned bit_convert_to_gap (T *dest, const unsigned *src, bm::id_t bits, unsigned dest_len)
 Converts bit block to GAP. More...
 

Detailed Description

GAP functions implement different opereations on GAP compressed blocks (internals) and serve as a minimal building blocks.

Function Documentation

◆ bit_array_compute_gaps()

template<typename T >
unsigned bm::bit_array_compute_gaps ( const T arr,
unsigned  len 
)
noexcept

Compute number of GAPs in bit-array.

Parameters
arr- array of BITs
len- array length

Definition at line 3662 of file bmfunc.h.

References arr, i, len, prev(), and T.

Referenced by BitCountChangeTest().

◆ bit_block_to_gap()

unsigned bm::bit_block_to_gap ( gap_word_t dest,
const unsigned *  block,
unsigned  dest_len 
)
inlinenoexcept

Converts bit block to GAP.

Parameters
dest- Destinatio GAP buffer.
block- Source bitblock buffer.
dest_len- length of the destination buffer.
Returns
New length of GAP block or 0 if conversion failed (insufficicent space).

Definition at line 4785 of file bmfunc.h.

References bm::bit_scan_forward32(), BM_ASSERT, BMRESTRICT, len, bm::set_block_size, and val.

Referenced by bm::bit_to_gap().

◆ bit_convert_to_gap()

template<typename T >
unsigned bit_convert_to_gap ( T dest,
const unsigned *  src,
bm::id_t  bits,
unsigned  dest_len 
)

Converts bit block to GAP.

Parameters
dest- Destinatio GAP buffer.
src- Source bitblock buffer.
bits- Number of bits to convert.
dest_len- length of the dest. buffer.
Returns
New length of GAP block or 0 if conversion failed (insufficicent space).

Definition at line 3245 of file stress32.cpp.

References assert, bm::bvector< Alloc >::end(), len, mask, T, and val.

Referenced by GAPCheck(), and TestBlockToGAP().

◆ for_each_gap_blk()

template<typename T , typename Func , typename SIZE_TYPE >
int bm::for_each_gap_blk ( const T buf,
SIZE_TYPE  offset,
Func &  bit_functor 
)

for-each visitor, calls a special visitor functor for each 1 bit range

Parameters
buf- bit block buffer pointer
offset- global block offset (number of bits)
bit_functor- functor must support .add_range(offset, bits_ptr, size)
Returns
- functor return code (< 0 - interrupt the processing)

Definition at line 1760 of file bmalgo_impl.h.

References buf, offset, prev(), and T.

Referenced by bm::for_each_bit_block_range().

◆ for_each_gap_blk_range()

template<typename T , typename Func , typename SIZE_TYPE >
int bm::for_each_gap_blk_range ( const T buf,
SIZE_TYPE  offset,
unsigned  left,
unsigned  right,
Func &  bit_functor 
)

for-each visitor, calls a special visitor functor for each 1 bit range

Parameters
buf- bit block buffer pointer
offset- global block offset (number of bits)
left- interval start [left..right]
right- intreval end [left..right]
bit_functor- functor must support .add_range(offset, bits_ptr, size)
Returns
- functor return code (< 0 - interrupt the processing)

Definition at line 1795 of file bmalgo_impl.h.

References bm::bits_in_block, BM_ASSERT, BMRESTRICT, buf, bm::gap_bfind(), int, offset, prev(), and T.

Referenced by bm::for_each_bit_range_no_check().

◆ for_each_gap_dbit()

template<class T , class F >
void bm::for_each_gap_dbit ( const T buf,
F func 
)

Iterate gap block as delta-bits with a functor.

Definition at line 4887 of file bmfunc.h.

References buf, i, prev(), and T.

◆ gap_add_to_bitset() [1/2]

template<typename T >
void bm::gap_add_to_bitset ( unsigned *  dest,
const T pcurr 
)
noexcept

Adds(OR) GAP block to bitblock.

Parameters
dest- bitblock buffer pointer.
pcurr- GAP buffer pointer.

Definition at line 4074 of file bmfunc.h.

References bm::gap_add_to_bitset(), and len.

◆ gap_add_to_bitset() [2/2]

template<typename T >
void bm::gap_add_to_bitset ( unsigned *  dest,
const T pcurr,
unsigned  len 
)
noexcept

◆ gap_add_value()

template<typename T >
unsigned bm::gap_add_value ( T buf,
unsigned  pos 
)
noexcept

Add new value to the end of GAP buffer.

Parameters
buf- GAP buffer.
pos- Index of bit to set.
Returns
New GAP buffer length.

Definition at line 3361 of file bmfunc.h.

References BM_ASSERT, buf, bm::gap_max_bits, memmove, and T.

Referenced by bm::deseriaizer_base< DEC, BLOCK_IDX >::read_gap_block().

◆ gap_and_to_bitset() [1/2]

template<typename T >
void bm::gap_and_to_bitset ( unsigned *  dest,
const T pcurr 
)
noexcept

ANDs GAP block to bitblock.

Parameters
dest- bitblock buffer pointer.
pcurr- GAP buffer pointer.

Definition at line 4090 of file bmfunc.h.

References BM_ASSERT, bm::sub_bit_block(), and T.

Referenced by bm::bvector< Alloc >::combine_operation_block_and(), bm::bvector< Alloc >::combine_operation_block_and_or(), bm::aggregator< BV >::process_gap_blocks_and(), and bm::aggregator< BV >::process_shift_right_and().

◆ gap_and_to_bitset() [2/2]

template<typename T >
bm::id64_t bm::gap_and_to_bitset ( unsigned *  dest,
const T pcurr,
bm::id64_t  digest0 
)
noexcept

ANDs GAP block to bitblock with digest assist.

Parameters
dest- bitblock buffer pointer.
pcurr- GAP buffer pointer.
digest0- digest of 0 strides for the destination
Returns
new digest

Definition at line 4127 of file bmfunc.h.

References BM_ASSERT, BMRESTRICT, bm::check_zero_digest(), bm::count_leading_zeros_u64(), bm::count_trailing_zeros_u64(), bm::gap_bfind(), len, prev(), bm::set_block_digest_pos_shift, bm::sub_bit_block(), T, and bm::update_block_digest0().

◆ gap_any_range()

template<typename T >
bool bm::gap_any_range ( const T *const  buf,
unsigned  left,
unsigned  right 
)
noexcept

Test if any bits are 1 in GAP buffer in the [left, right] range.

Parameters
buf- GAP buffer pointer.
left- leftmost bit index to start from
right-rightmost bit index
Returns
true if at least 1 "00010"

Definition at line 2506 of file bmfunc.h.

References BM_ASSERT, buf, bm::gap_bfind(), bm::gap_max_bits, and T.

Referenced by bm::block_any_range().

◆ gap_bit_count()

template<typename T >
unsigned bm::gap_bit_count ( const T buf,
unsigned  dsize = 0 
)
noexcept

Calculates number of bits ON in GAP buffer.

Parameters
buf- GAP buffer pointer.
dsize- buffer size
Returns
Number of non-zero bits.

Definition at line 2299 of file bmfunc.h.

References buf, and T.

Referenced by gap_vector::bit_count(), bm::gap_bit_count_unr(), and bm::print_stat().

◆ gap_bit_count_range()

template<typename T , bool RIGHT_END = false>
unsigned bm::gap_bit_count_range ( const T *const  buf,
unsigned  left,
unsigned  right 
)
noexcept

Counts 1 bits in GAP buffer in the closed [left, right] range.

Parameters
buf- GAP buffer pointer.
left- leftmost bit index to start from
right- rightmost bit index
pos- position in the
Returns
Number of non-zero bits.

Definition at line 2393 of file bmfunc.h.

References BM_ASSERT, buf, bm::gap_bfind(), bm::gap_max_bits, and T.

Referenced by bm::bvector< Alloc >::build_rs_index(), gap_vector::count_range(), bm::bvector< Alloc >::count_range_no_check(), and bm::bvector< Alloc >::gap_count_to().

◆ gap_bit_count_range_hint()

template<typename T >
unsigned bm::gap_bit_count_range_hint ( const T *const  buf,
unsigned  left,
unsigned  right,
unsigned  hint 
)
noexcept

Counts 1 bits in GAP buffer in the closed [left, right] range using position hint to avoid bfind.

Parameters
buf- GAP buffer pointer.
left- leftmost bit index to start from
right- rightmost bit index
pos- position in the
hint- position hint
Returns
Number of non-zero bits.

Definition at line 2441 of file bmfunc.h.

References BM_ASSERT, buf, bm::gap_bfind(), bm::gap_max_bits, and T.

Referenced by bm::bvector< Alloc >::gap_count_to().

◆ gap_bit_count_unr()

template<typename T >
unsigned bm::gap_bit_count_unr ( const T buf)
noexcept

Calculates number of bits ON in GAP buffer. Loop unrolled version.

Parameters
buf- GAP buffer pointer.
Returns
Number of non-zero bits.

Definition at line 2327 of file bmfunc.h.

References bm::avx2_gap_sum_arr(), BM_ASSERT, buf, cnt, bm::gap_bit_count(), i, bm::sse2_gap_sum_arr(), and T.

Referenced by bm::blocks_manager< Alloc >::block_bitcount(), bm::combine_count_operation_with_block(), bm::serializer< BV >::find_gap_best_encoding(), and bm::blocks_manager< Alloc >::is_sparse_sblock().

◆ gap_bitset_and_any()

template<typename T >
bm::id_t bm::gap_bitset_and_any ( const unsigned *  block,
const T pcurr 
)
noexcept

Bitcount test of bit block AND masked by GAP block.

Parameters
block- bitblock buffer pointer
pcurr- GAP buffer pointer
Returns
non-zero value if AND produces any result

Definition at line 4226 of file bmfunc.h.

References bm::bit_block_any_range(), BM_ASSERT, and T.

Referenced by bm::combine_any_operation_with_block().

◆ gap_bitset_and_count()

template<typename T >
bm::id_t bm::gap_bitset_and_count ( const unsigned *  block,
const T pcurr 
)
noexcept

Compute bitcount of bit block AND masked by GAP block.

Parameters
block- bitblock buffer pointer
pcurr- GAP buffer pointer
Returns
bitcount - cardinality of the AND product

Definition at line 4198 of file bmfunc.h.

References bm::bit_block_calc_count_range(), BM_ASSERT, and T.

Referenced by bm::combine_count_and_operation_with_block(), and bm::combine_count_operation_with_block().

◆ gap_bitset_or_any()

template<typename T >
bm::id_t bm::gap_bitset_or_any ( const unsigned *  block,
const T buf 
)
noexcept

Compute bitcount test of bit block OR masked by GAP block.

Parameters
block- bitblock buffer pointer
buf- GAP buffer pointer
Returns
non zero value if union (OR) returns anything

Definition at line 4437 of file bmfunc.h.

References b, bm::bit_is_all_zero(), buf, and bm::gap_is_all_zero().

Referenced by bm::combine_any_operation_with_block().

◆ gap_bitset_or_count()

template<typename T >
bm::id_t bm::gap_bitset_or_count ( const unsigned *  block,
const T buf 
)
noexcept

Compute bitcount of bit block OR masked by GAP block.

Parameters
block- bitblock buffer pointer.
buf- GAP buffer pointer.
Returns
bit count of OR

Definition at line 4405 of file bmfunc.h.

References bm::bit_block_calc_count_range(), BM_ASSERT, buf, prev(), and T.

Referenced by bm::combine_count_operation_with_block().

◆ gap_bitset_sub_any()

template<typename T >
bm::id_t bm::gap_bitset_sub_any ( const unsigned *  block,
const T buf 
)
noexcept

Compute bitcount test of bit block SUB masked by GAP block.

Parameters
block- bitblock buffer pointer
buf- GAP buffer pointer
Returns
non-zero value if AND NOT produces any 1 bits

Definition at line 4291 of file bmfunc.h.

References bm::bit_block_any_range(), BM_ASSERT, buf, and T.

Referenced by bm::combine_any_operation_with_block().

◆ gap_bitset_sub_count()

template<typename T >
bm::id_t bm::gap_bitset_sub_count ( const unsigned *  block,
const T buf 
)
noexcept

Compute bitcount of bit block SUB masked by GAP block.

Parameters
block- bitblock buffer pointer.
buf- GAP buffer pointer.
Returns
bit-count result of AND NOT operation

Definition at line 4256 of file bmfunc.h.

References bm::bit_block_calc_count_range(), BM_ASSERT, buf, and T.

Referenced by bm::combine_count_operation_with_block().

◆ gap_bitset_xor_any()

template<typename T >
bm::id_t bm::gap_bitset_xor_any ( const unsigned *  block,
const T buf 
)
noexcept

Compute bitcount test of bit block XOR masked by GAP block.

Parameters
block- bitblock buffer pointer
buf- GAP buffer pointer
Returns
non-zero value if XOR returns anything

Definition at line 4367 of file bmfunc.h.

References bm::bit_block_any_range(), BM_ASSERT, buf, prev(), and T.

Referenced by bm::combine_any_operation_with_block().

◆ gap_bitset_xor_count()

template<typename T >
bm::id_t bm::gap_bitset_xor_count ( const unsigned *  block,
const T buf 
)
noexcept

Compute bitcount of bit block XOR masked by GAP block.

Parameters
block- bitblock buffer pointer
buf- GAP buffer pointer
Returns
bit count value of XOR operation

Definition at line 4329 of file bmfunc.h.

References bm::bit_block_calc_count_range(), BM_ASSERT, buf, prev(), and T.

Referenced by bm::combine_count_operation_with_block().

◆ gap_block_find()

template<typename T >
unsigned bm::gap_block_find ( const T buf,
unsigned  nbit,
bm::id_t prev 
)
noexcept

Searches for the next 1 bit in the GAP block.

Parameters
buf- GAP buffer
nbit- bit index to start checking from.
prev- returns previously checked value
Returns
0 if not found

Definition at line 3694 of file bmfunc.h.

References BM_ASSERT, buf, bm::gap_bfind(), bm::gap_max_bits, prev(), and val.

Referenced by bm::bvector< Alloc >::check_or_next().

◆ gap_buff_any_op()

template<typename T , class F >
unsigned bm::gap_buff_any_op ( const T vect1,
unsigned  vect1_mask,
const T vect2,
unsigned  vect2_mask 
)

Abstract distance test operation for GAP buffers. Receives functor F as a template argument.

Parameters
vect1- operand 1 GAP encoded buffer.
vect1_mask- XOR mask for starting bitflag for vector1 can be 0 or 1 (1 inverts the vector)
vect2- operand 2 GAP encoded buffer.
vect2_mask- same as vect1_mask
Note
Internal function.
Returns
non zero value if operation result returns any 1 bit

Definition at line 3019 of file bmfunc.h.

References bm::gap_max_bits, and T.

◆ gap_buff_count_op()

template<typename T , class F >
unsigned bm::gap_buff_count_op ( const T vect1,
const T vect2 
)

Abstract distance(similarity) operation for GAP buffers. Receives functor F as a template argument.

Parameters
vect1- operand 1 GAP encoded buffer.
vect2- operand 2 GAP encoded buffer.
Note
Internal function.

Definition at line 3084 of file bmfunc.h.

References bm::gap_max_bits, and T.

◆ gap_calc_level()

template<typename T >
int bm::gap_calc_level ( unsigned  len,
const T glevel_len 
)
noexcept

◆ gap_capacity()

template<typename T >
unsigned bm::gap_capacity ( const T buf,
const T glevel_len 
)
noexcept

Returs GAP block capacity.

Parameters
buf- GAP buffer pointer
glevel_len- pointer on GAP header word
Returns
GAP block capacity.

Definition at line 1619 of file bmfunc.h.

References buf.

Referenced by bm::bvector< Alloc >::calc_stat(), bm::mem_alloc< BA, PA, APool >::free_gap_block(), bm::gap_free_elements(), and bm::blocks_manager< Alloc >::optimize_block().

◆ gap_control_sum()

template<typename T >
unsigned bm::gap_control_sum ( const T buf)
noexcept

Calculates sum of all words in GAP block. (For debugging purposes)

Note
For debugging and testing ONLY.
Parameters
buf- GAP buffer pointer.
Returns
Sum of all words.

Definition at line 4521 of file bmfunc.h.

References BM_ASSERT, buf, and T.

Referenced by gap_vector::control(), and bm::print_stat().

◆ gap_convert_to_arr()

template<typename D , typename T >
D bm::gap_convert_to_arr ( D *  dest,
const T buf,
unsigned  dest_len,
bool  invert = false 
)
noexcept

Convert gap block into array of ints corresponding to 1 bits.

Definition at line 4942 of file bmfunc.h.

References BMRESTRICT, buf, i, invert, and T.

Referenced by bm::serializer< BV >::encode_gap_block(), and bm::random_subset< BV >::get_subset().

◆ gap_convert_to_bitset()

template<typename T >
void bm::gap_convert_to_bitset ( unsigned *  dest,
const T buf,
unsigned  len = 0 
)
noexcept

◆ gap_convert_to_bitset_smart()

template<typename T >
unsigned* bm::gap_convert_to_bitset_smart ( unsigned *  dest,
const T buf,
id_t  set_max 
)
noexcept

Smart GAP block to bitblock conversion.

Checks if GAP block is ALL-ZERO or ALL-ON. In those cases returns pointer on special static bitblocks.

Parameters
dest- bitblock buffer pointer.
buf- GAP buffer pointer.
set_max- max possible bitset length

Definition at line 4500 of file bmfunc.h.

References buf, FULL_BLOCK_REAL_ADDR, and bm::gap_convert_to_bitset().

Referenced by bm::bvector< Alloc >::combine_operation_block_sub(), and bm::bvector< Alloc >::combine_operation_with_block().

◆ gap_count_and()

unsigned bm::gap_count_and ( const gap_word_t vect1,
const gap_word_t vect2 
)
inlinenoexcept

GAP bitcount AND operation test.

Parameters
vect1- operand 1
vect2- operand 2
Returns
bitcount of vect1 AND vect2

Definition at line 6560 of file bmfunc.h.

Referenced by bm::combine_count_and_operation_with_block(), and bm::combine_count_operation_with_block().

◆ gap_count_or()

unsigned bm::gap_count_or ( const gap_word_t vect1,
const gap_word_t vect2 
)
inlinenoexcept

GAP bitcount OR operation test.

Parameters
vect1- operand 1
vect2- operand 2
Returns
bitcount of vect1 OR vect2

Definition at line 6686 of file bmfunc.h.

Referenced by bm::combine_count_operation_with_block().

◆ gap_count_sub()

unsigned bm::gap_count_sub ( const gap_word_t vect1,
const gap_word_t vect2 
)
inlinenoexcept

GAP bitcount SUB (AND NOT) operation test.

Parameters
vect1- operand 1
vect2- operand 2
Returns
bitcount of vect1 SUB (AND NOT) vect2

Definition at line 6757 of file bmfunc.h.

Referenced by bm::combine_count_operation_with_block().

◆ gap_count_xor()

unsigned bm::gap_count_xor ( const gap_word_t vect1,
const gap_word_t vect2 
)
inlinenoexcept

GAP bitcount XOR operation test.

Parameters
vect1- operand 1
vect2- operand 2
Returns
bitcount of vect1 XOR vect2

Definition at line 6641 of file bmfunc.h.

Referenced by bm::combine_count_operation_with_block().

◆ gap_find_first()

template<typename T >
unsigned bm::gap_find_first ( const T buf,
unsigned *  first 
)
noexcept

GAP block find the first set bit.

Parameters
buf- GAP buffer pointer.
first- index of the first 1 bit
Returns
0 if 1 bit was NOT found

Definition at line 1698 of file bmfunc.h.

References BM_ASSERT, buf, first(), bm::gap_max_bits, and T.

Referenced by bm::block_find_first_diff(), bm::bvector< Alloc >::check_or_next(), and bm::bvector< Alloc >::find().

◆ gap_find_first_diff()

template<typename T >
bool bm::gap_find_first_diff ( const T buf1,
const T buf2,
unsigned *  pos 
)
noexcept

Find first bit which is different between two GAP-blocks.

Parameters
buf1- block 1
buf2- block 2
pos- out - position of difference (undefined if blocks are equal)
Returns
true if difference was found

Definition at line 2904 of file bmfunc.h.

References BM_ASSERT, and T.

Referenced by bm::block_find_first_diff(), and TestBlockToGAP().

◆ gap_find_interval_end()

template<typename T >
bool bm::gap_find_interval_end ( const T *const  buf,
unsigned  nbit,
unsigned *  pos 
)
noexcept

Searches for the last 1 bit in the 111 interval of a GAP block.

Parameters
buf- BIT block buffer
nbit- bit index to start checking from
pos- [out] found value
Returns
false if not found

Definition at line 2564 of file bmfunc.h.

References BM_ASSERT, buf, bm::gap_bfind(), and bm::gap_max_bits.

Referenced by bm::block_find_interval_end().

◆ gap_find_interval_start()

template<typename T >
bool bm::gap_find_interval_start ( const T *const  buf,
unsigned  nbit,
unsigned *  pos 
)
noexcept

Searches for the first 1 bit in the 111 interval of a GAP block.

Parameters
buf- GAP block buffer
nbit- bit index to start checking from
pos- [out] found value
Returns
false if not found

Definition at line 2589 of file bmfunc.h.

References BM_ASSERT, buf, bm::gap_bfind(), and bm::gap_max_bits.

Referenced by bm::block_find_interval_start().

◆ gap_find_last()

template<typename T >
unsigned bm::gap_find_last ( const T buf,
unsigned *  last 
)
noexcept

GAP block find the last set bit.

Parameters
buf- GAP buffer pointer.
last- index of the last 1 bit
Returns
0 if 1 bit was NOT found

Definition at line 1667 of file bmfunc.h.

References BM_ASSERT, buf, bm::gap_max_bits, last(), and T.

Referenced by bm::bvector< Alloc >::find_reverse(), and gap_vector::get_last().

◆ gap_find_prev()

template<typename T >
bool bm::gap_find_prev ( const T *const  buf,
unsigned  nbit,
unsigned *  pos 
)
noexcept

reverse search for the first 1 bit of a GAP block

Parameters
buf- GAP block buffer
nbit- bit index to start checking from
pos- [out] found value
Returns
false if not found

Definition at line 2617 of file bmfunc.h.

References BM_ASSERT, buf, bm::gap_bfind(), and bm::gap_max_bits.

Referenced by bm::block_find_reverse().

◆ gap_find_rank()

template<typename T , typename SIZE_TYPE >
SIZE_TYPE bm::gap_find_rank ( const T *const  block,
SIZE_TYPE  rank,
unsigned  nbit_from,
unsigned &  nbit_pos 
)
noexcept

GAP block find position for the rank.

Parameters
block- bit block buffer pointer
rank- rank to find (must be > 0)
nbit_from- start bit position in block
nbit_pos- found position
Returns
0 if position with rank was found, or the remaining rank (rank - population count)

Definition at line 2654 of file bmfunc.h.

References BM_ASSERT, bm::gap_bfind(), and T.

Referenced by bm::block_find_rank().

◆ gap_free_elements()

template<typename T >
unsigned bm::gap_free_elements ( const T buf,
const T glevel_len 
)
inlinenoexcept

Returns number of free elements in GAP block array. Difference between GAP block capacity on this level and actual GAP length.

Parameters
buf- GAP buffer pointer
glevel_len- GAP lengths table
Returns
Number of free GAP elements

Definition at line 4682 of file bmfunc.h.

References buf, bm::gap_capacity(), bm::gap_length(), and len.

◆ gap_init_range_block()

template<class T >
void bm::gap_init_range_block ( T buf,
T  from,
T  to,
T  value 
)
noexcept

Init gap block so it has block in it (can be whole block)

Parameters
buf- GAP buffer pointer.
from- one block start
to- one block end
value- (block value)1 or 0

Definition at line 4570 of file bmfunc.h.

References bm::bits_in_block, BM_ASSERT, buf, bm::gap_set_all(), T, and value.

◆ gap_insert()

template<typename T >
bool bm::gap_insert ( T buf,
unsigned  pos,
unsigned  val,
unsigned *  new_len 
)
noexcept

isnert bit into GAP compressed block

Parameters
buf- block pointer
pos- insert position
value- (0 or 1) - value to set
new_len- output length of the GAP block after the operation
Returns
carry over bit (1 or 0)

Definition at line 3484 of file bmfunc.h.

References BM_ASSERT, buf, bm::gap_bfind(), bm::gap_max_bits, bm::gap_set_value(), i, len, T, and val.

Referenced by bm::bvector< Alloc >::insert().

◆ gap_invert()

template<typename T >
void bm::gap_invert ( T buf)
noexcept

◆ gap_is_all_one()

bool bm::gap_is_all_one ( const bm::gap_word_t buf)
inlinenoexcept

Checks if GAP block is all-one.

Parameters
buf- GAP buffer pointer.
Returns
true if all-one.

Definition at line 1590 of file bmfunc.h.

References buf, and bm::gap_max_bits.

Referenced by bm::blocks_manager< Alloc >::assign_gap_check(), bm::check_block_one(), bm::blocks_manager< Alloc >::clone_assign_block(), bm::blocks_manager< Alloc >::gap_level_func::operator()(), and bm::blocks_manager< Alloc >::optimize_block().

◆ gap_is_all_one_range()

template<typename T >
bool bm::gap_is_all_one_range ( const T *const  buf,
unsigned  left,
unsigned  right 
)
noexcept

Test if all bits are 1 in GAP buffer in the [left, right] range.

Parameters
buf- GAP buffer pointer.
left- leftmost bit index to start from
right-rightmost bit index
Returns
true if all bits are "11111"

Definition at line 2483 of file bmfunc.h.

References BM_ASSERT, buf, bm::gap_bfind(), bm::gap_max_bits, and T.

Referenced by bm::block_is_all_one_range().

◆ gap_is_all_zero()

bool bm::gap_is_all_zero ( const bm::gap_word_t buf)
inlinenoexcept

◆ gap_is_interval()

template<typename T >
bool bm::gap_is_interval ( const T *const  buf,
unsigned  left,
unsigned  right 
)
noexcept

Test if any bits are 1 in GAP buffer in the [left, right] range and flanked with 0s.

Parameters
buf- GAP buffer pointer.
left- leftmost bit index to start from
right-rightmost bit index
Returns
true if "011110"

Definition at line 2535 of file bmfunc.h.

References BM_ASSERT, buf, bm::gap_bfind(), bm::gap_max_bits, and T.

Referenced by bm::block_is_interval().

◆ gap_length()

bm::gap_word_t bm::gap_length ( const bm::gap_word_t buf)
inlinenoexcept

Returs GAP block length.

Parameters
buf- GAP buffer pointer.
Returns
GAP block length.

Definition at line 1603 of file bmfunc.h.

References buf.

Referenced by AddInsertWithGaps(), bm::blocks_manager< Alloc >::allocate_gap_block(), BitCountChangeTest(), bm::blocks_manager< Alloc >::block_count_change_func::block_count(), bm::blocks_manager< Alloc >::calc_arena_stat(), bm::bvector< Alloc >::calc_stat(), bm::blocks_manager< Alloc >::clone_gap_block(), gap_vector::combine_and(), gap_vector::combine_or(), gap_vector::combine_sub(), gap_vector::combine_xor(), bm::xor_scanner< BV >::compute_sim_model(), gap_vector::control(), bm::blocks_manager< Alloc >::copy_to_arena(), CGapsEditor::CreateGap(), bm::xor_scanner< BV >::deoptimize_gap_blocks(), bm::iterator_deserializer< BV, SerialIterator >::deserialize(), bm::deserializer< BV, DEC >::deserialize_gap(), bm::blocks_manager< Alloc >::extend_gap_block(), bm::serializer< BV >::find_gap_best_encoding(), bm::serializer< BV >::gamma_gap_block(), bm::bvector< Alloc >::gap_block_set(), bm::bvector< Alloc >::gap_block_set_no_ret(), bm::gap_convert_to_bitset(), bm::gap_free_elements(), bm::serializer< BV >::interpolated_encode_gap_block(), bm::blocks_manager< Alloc >::is_sparse_sblock(), CFeatureTableReader::MakeGap(), bm::blocks_manager< Alloc >::gap_level_func::operator()(), bm::blocks_manager< Alloc >::optimize_block(), print_gap(), bm::print_stat(), bm::deseriaizer_base< DEC, BLOCK_IDX >::read_gap_block(), s_NewGapItem(), bm::xor_scanner< BV >::search_best_xor_mask(), bm::blocks_manager< Alloc >::set_gap_block(), bm::bvector< Alloc >::swap(), CCdsGlyph::x_DrawProtSeqWithMapping(), and CFeatGlyph::x_DrawRNAProductSequence().

◆ gap_level()

template<typename T >
T bm::gap_level ( const T buf)
noexcept

Returs GAP blocks capacity level.

Parameters
buf- GAP buffer pointer.
Returns
GAP block capacity level.

Definition at line 1649 of file bmfunc.h.

References buf, and T.

Referenced by bm::blocks_manager< Alloc >::assign_gap(), bm::bvector< Alloc >::calc_stat(), bm::blocks_manager< Alloc >::extend_gap_block(), bm::blocks_manager< Alloc >::optimize_block(), and bm::print_stat().

◆ gap_limit()

template<typename T >
unsigned bm::gap_limit ( const T buf,
const T glevel_len 
)
noexcept

Returs GAP block capacity limit.

Parameters
buf- GAP buffer pointer.
glevel_len- GAP lengths table (gap_len_table)
Returns
GAP block limit.

Definition at line 1635 of file bmfunc.h.

References buf.

Referenced by bm::combine_or(), bm::combine_sub(), bm::combine_xor(), bm::bvector< Alloc >::erase(), bm::bvector< Alloc >::gap_block_set(), bm::bvector< Alloc >::gap_block_set_no_ret(), bm::bvector< Alloc >::insert(), and bm::bvector< Alloc >::swap().

◆ gap_operation_and()

gap_word_t* bm::gap_operation_and ( const gap_word_t vect1,
const gap_word_t vect2,
gap_word_t tmp_buf,
unsigned &  dsize 
)
inlinenoexcept

GAP AND operation.

Function performs AND logical operation on gap vectors. If possible function put the result into vect1 and returns this pointer. Otherwise result is put into tmp_buf, which should be twice of the vector size.

Parameters
vect1- operand 1
vect2- operand 2
tmp_buf- pointer on temporary buffer
dsize- out size of the destination
Returns
Result pointer (tmp_buf OR vect1)

Definition at line 6518 of file bmfunc.h.

Referenced by gap_vector::combine_and(), bm::bvector< Alloc >::combine_operation_block_and(), and bm::bvector< Alloc >::combine_operation_block_and_or().

◆ gap_operation_any_and()

unsigned bm::gap_operation_any_and ( const gap_word_t vect1,
const gap_word_t vect2 
)
inlinenoexcept

GAP AND operation test.

Function performs AND logical operation on gap vectors. If possible function put the result into vect1 and returns this pointer. Otherwise result is put into tmp_buf, which should be twice of the vector size.

Parameters
vect1- operand 1
vect2- operand 2
Returns
non zero value if operation returns any 1 bit

Definition at line 6543 of file bmfunc.h.

Referenced by bm::combine_any_operation_with_block().

◆ gap_operation_any_sub()

unsigned bm::gap_operation_any_sub ( const gap_word_t vect1,
const gap_word_t vect2 
)
inlinenoexcept

GAP SUB operation test.

Function performs AND logical operation on gap vectors. If possible function put the result into vect1 and returns this pointer. Otherwise result is put into tmp_buf, which should be twice of the vector size.

Parameters
vect1- operand 1
vect2- operand 2
Returns
non zero value if operation returns any 1 bit

Definition at line 6738 of file bmfunc.h.

Referenced by bm::combine_any_operation_with_block().

◆ gap_operation_any_xor()

unsigned bm::gap_operation_any_xor ( const gap_word_t vect1,
const gap_word_t vect2 
)
inlinenoexcept

GAP XOR operation test.

Light weight gap_operation_xor for len prediction

Function performs AND logical operation on gap vectors. If possible function put the result into vect1 and returns this pointer. Otherwise result is put into tmp_buf, which should be twice of the vector size.

Parameters
vect1- operand 1
vect2- operand 2
Returns
non zero value if operation returns any 1 bit

Definition at line 6625 of file bmfunc.h.

Referenced by bm::combine_any_operation_with_block().

◆ gap_operation_or()

gap_word_t* bm::gap_operation_or ( const gap_word_t vect1,
const gap_word_t vect2,
gap_word_t tmp_buf,
unsigned &  dsize 
)
inlinenoexcept

GAP OR operation.

Function performs OR logical oparation on gap vectors. If possible function put the result into vect1 and returns this pointer. Otherwise result is put into tmp_buf, which should be twice of the vector size.

Parameters
vect1- operand 1
vect2- operand 2
tmp_buf- pointer on temporary buffer
dsize- out destination size
Returns
Result pointer (tmp_buf)

Definition at line 6666 of file bmfunc.h.

References bm::gap_invert().

Referenced by bm::combine_any_operation_with_block(), bm::bvector< Alloc >::combine_operation_block_or(), and gap_vector::combine_or().

◆ gap_operation_sub()

gap_word_t* bm::gap_operation_sub ( const gap_word_t vect1,
const gap_word_t vect2,
gap_word_t tmp_buf,
unsigned &  dsize 
)
inlinenoexcept

GAP SUB (AND NOT) operation.

Function performs SUB logical operation on gap vectors. If possible function put the result into vect1 and returns this pointer. Otherwise result is put into tmp_buf, which should be twice of the vector size.

Parameters
vect1- operand 1
vect2- operand 2
tmp_buf- pointer on temporary buffer
dsize- out destination size
Returns
Result pointer (tmp_buf)

Definition at line 6712 of file bmfunc.h.

Referenced by bm::bvector< Alloc >::combine_operation_block_sub(), and gap_vector::combine_sub().

◆ gap_operation_xor()

gap_word_t* bm::gap_operation_xor ( const gap_word_t vect1,
const gap_word_t vect2,
gap_word_t tmp_buf,
unsigned &  dsize 
)
inlinenoexcept

GAP XOR operation.

Function performs XOR logical operation on gap vectors. If possible function put the result into vect1 and returns this pointer. Otherwise result is put into tmp_buf, which should be twice of the vector size.

Parameters
vect1- operand 1
vect2- operand 2
tmp_buf- pointer on temporary buffer
dsize- out destination size
Returns
Result pointer (tmp_buf)

Definition at line 6585 of file bmfunc.h.

Referenced by bm::bvector< Alloc >::combine_operation_block_xor(), gap_vector::combine_xor(), and bm::deserializer< BV, DEC >::xor_decode().

◆ gap_overhead()

template<typename T >
unsigned bm::gap_overhead ( const T length,
const T length_end,
const T glevel_len 
)
noexcept

Calculates memory overhead for number of gap blocks sharing the same memory allocation table (level lengths table).

Definition at line 9143 of file bmfunc.h.

References BM_ASSERT, bm::gap_calc_level(), bm::gap_levels, and len.

Referenced by bm::improve_gap_levels().

◆ gap_set_all()

template<class T >
void bm::gap_set_all ( T buf,
unsigned  set_max,
unsigned  value 
)
noexcept

Sets all bits to 0 or 1 (GAP)

Parameters
buf- GAP buffer pointer.
set_max- max possible bitset length
value- value to set

Definition at line 4552 of file bmfunc.h.

References BM_ASSERT, buf, T, and value.

Referenced by BitCountChangeTest(), bm::blocks_manager< Alloc >::check_allocate_block(), bm::gap_init_range_block(), bm::miniset< A, N >::init_gapbuf(), and bm::deseriaizer_base< DEC, BLOCK_IDX >::read_gap_block().

◆ gap_set_array()

template<typename T >
unsigned bm::gap_set_array ( T buf,
const T arr,
unsigned  len 
)
noexcept

Convert array to GAP buffer.

Parameters
buf- GAP buffer.
arr- array of values to set
len- length of the array
Returns
New GAP buffer length.

Definition at line 3601 of file bmfunc.h.

References arr, BM_ASSERT, buf, bm::gap_max_bits, i, len, prev(), and T.

Referenced by BitCountChangeTest(), bm::deserializer< BV, DEC >::deserialize_gap(), and bm::deseriaizer_base< DEC, BLOCK_IDX >::read_gap_block().

◆ gap_set_value() [1/2]

template<typename T >
unsigned bm::gap_set_value ( unsigned  val,
T buf,
unsigned  pos 
)
noexcept

Sets or clears bit in the GAP buffer.

Parameters
val- new bit value
buf- GAP buffer.
pos- Index of bit to set.
Returns
New GAP buffer length.

Definition at line 3281 of file bmfunc.h.

References BM_ASSERT, buf, bm::gap_bfind(), bm::gap_max_bits, memmove, T, and val.

◆ gap_set_value() [2/2]

template<typename T >
unsigned bm::gap_set_value ( unsigned  val,
T buf,
unsigned  pos,
unsigned *  is_set 
)
noexcept

Sets or clears bit in the GAP buffer.

Parameters
val- new bit value
buf- GAP buffer.
pos- Index of bit to set.
is_set- (OUT) flag if bit was actually set.
Returns
New GAP buffer length.

Definition at line 3254 of file bmfunc.h.

References BM_ASSERT, buf, bm::gap_bfind(), bm::gap_max_bits, bm::gap_set_value_cpos(), and val.

Referenced by BitCountChangeTest(), gap_vector::clear_bit(), bm::combine_or(), bm::combine_sub(), bm::combine_xor(), bm::bvector< Alloc >::gap_block_set(), bm::bvector< Alloc >::gap_block_set_no_ret(), bm::gap_insert(), bm::gap_shift_l1(), bm::gap_shift_r1(), bm::miniset< A, N >::set(), and gap_vector::set_bit().

◆ gap_set_value_cpos()

template<typename T >
unsigned bm::gap_set_value_cpos ( unsigned  val,
T buf,
unsigned  pos,
unsigned *  is_set,
unsigned  curr 
)
noexcept

Sets or clears bit in the GAP buffer.

Parameters
val- new bit value
buf- GAP buffer.
pos- Index of bit to set.
is_set- (OUT) flag if bit was actually set.
curr- (pos) position index
Returns
New GAP buffer length.

Definition at line 3168 of file bmfunc.h.

References buf, bm::gap_max_bits, memmove, T, and val.

Referenced by bm::gap_set_value(), and bm::bvector< Alloc >::swap().

◆ gap_shift_l1()

template<typename T >
bool bm::gap_shift_l1 ( T buf,
unsigned  co_flag,
unsigned *  new_len 
)
noexcept

Left shift GAP block by 1 bit.

Parameters
buf- block pointer
co_flag- carry over from the previous block
new_len- new length of the block
Returns
carry over bit (1 or 0)

Definition at line 3540 of file bmfunc.h.

References BM_ASSERT, buf, bm::gap_max_bits, bm::gap_set_value(), i, and len.

Referenced by bm::bvector< Alloc >::erase().

◆ gap_shift_r1()

template<typename T >
bool bm::gap_shift_r1 ( T buf,
unsigned  co_flag,
unsigned *  new_len 
)
noexcept

Right shift GAP block by 1 bit.

Parameters
buf- block pointer
co_flag- carry over from the previous block
new_len- output length of the GAP block after the operation
Returns
carry over bit (1 or 0)

Definition at line 3431 of file bmfunc.h.

References BM_ASSERT, buf, bm::gap_max_bits, bm::gap_set_value(), i, len, and T.

Referenced by bm::bvector< Alloc >::insert().

◆ gap_split()

template<typename T >
void bm::gap_split ( const T buf,
T arr0,
T arr1,
T arr0_cnt,
T arr1_cnt 
)
noexcept

Extract short (len=1) exceptions from the GAP block

Parameters
buf- GAP buffer to split
arr0- [OUT] list of isolates 0 positions (clear list)
arr1- [OUT] list of isolated 1 positions (set list)
arr0_cnt- [OUT] arr0 size
arr1_cnt-

Definition at line 2239 of file bmfunc.h.

References buf, delta(), len, prev(), and T.

◆ gap_sub_to_bitset() [1/2]

template<typename T >
void bm::gap_sub_to_bitset ( unsigned *  dest,
const T pcurr 
)
noexcept

SUB (AND NOT) GAP block to bitblock.

Parameters
dest- bitblock buffer pointer.
pcurr- GAP buffer pointer.

Definition at line 3912 of file bmfunc.h.

References BM_ASSERT, bm::sub_bit_block(), and T.

Referenced by bm::bvector< Alloc >::combine_operation_block_sub(), and bm::aggregator< BV >::process_gap_blocks_sub().

◆ gap_sub_to_bitset() [2/2]

template<typename T >
bm::id64_t bm::gap_sub_to_bitset ( unsigned *  dest,
const T pcurr,
bm::id64_t  digest0 
)
noexcept

SUB (AND NOT) GAP block to bitblock with digest assist.

Parameters
dest- bitblock buffer pointer.
pcurr- GAP buffer pointer.
digest0- digest of 0 strides inside bit block
Returns
new digest

Definition at line 3943 of file bmfunc.h.

References BM_ASSERT, BMRESTRICT, bm::check_zero_digest(), bm::count_leading_zeros_u64(), bm::count_trailing_zeros_u64(), bm::gap_bfind(), len, prev(), bm::set_block_digest_pos_shift, bm::sub_bit_block(), T, and bm::update_block_digest0().

◆ gap_test()

template<typename T >
unsigned bm::gap_test ( const T buf,
unsigned  pos 
)
noexcept

Tests if bit = pos is true.

Parameters
buf- GAP buffer pointer.
pos- index of the element.
Returns
true if position is in "1" gap

Definition at line 1790 of file bmfunc.h.

References BM_ASSERT, buf, and bm::gap_max_bits.

Referenced by bm::gap_test_unr(), gap_vector::is_bit_true(), and bm::miniset< A, N >::test().

◆ gap_test_unr()

template<typename T >
unsigned bm::gap_test_unr ( const T buf,
const unsigned  pos 
)
noexcept

◆ gap_xor_to_bitset()

template<typename T >
void bm::gap_xor_to_bitset ( unsigned *  dest,
const T pcurr 
)
noexcept

XOR GAP block to bitblock.

Parameters
dest- bitblock buffer pointer.
pcurr- GAP buffer pointer.

Definition at line 4011 of file bmfunc.h.

References BM_ASSERT, T, and bm::xor_bit_block().

Referenced by bm::bvector< Alloc >::combine_operation_block_xor().

◆ gapcmp()

template<typename T >
int bm::gapcmp ( const T buf1,
const T buf2 
)
noexcept

Lexicographical comparison of GAP buffers.

Parameters
buf1- First GAP buffer pointer.
buf2- Second GAP buffer pointer.
Returns
<0 - less, =0 - equal, >0 - greater.

Definition at line 2848 of file bmfunc.h.

References T.

Referenced by BitCountChangeTest(), CheckGap2DGap(), bm::bvector< Alloc >::compare(), gap_vector::compare(), and TestBlockToGAP().

◆ improve_gap_levels()

template<typename T >
bool bm::improve_gap_levels ( const T length,
const T length_end,
T glevel_len 
)
noexcept

Finds optimal gap blocks lengths.

Parameters
length- first element of GAP lengths array
length_end- end of the GAP lengths array
glevel_len- destination GAP lengths array

Definition at line 9170 of file bmfunc.h.

References BM_ASSERT, bm::gap_levels, bm::gap_max_buff_len, bm::gap_overhead(), i, opt_len, T, and val.

Referenced by OptimGAPTest(), and bm::bvector< Alloc >::optimize_gap_size().

◆ set_gap_level()

template<typename T >
void bm::set_gap_level ( T buf,
int  level 
)
noexcept
Modified on Sat Mar 02 10:58:36 2024 by modify_doxy.py rev. 669887