BitMagic-C++
Data Structures | Functions
GAP functions

Data Structures

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

BMFORCEINLINE bool bm::gap_is_all_zero (const bm::gap_word_t *BMRESTRICT buf) BMNOEXCEPT
 Checks if GAP block is all-zero. More...
 
BMFORCEINLINE bool bm::gap_is_all_one (const bm::gap_word_t *BMRESTRICT buf) BMNOEXCEPT
 Checks if GAP block is all-one. More...
 
BMFORCEINLINE bm::gap_word_t bm::gap_length (const bm::gap_word_t *BMRESTRICT buf) BMNOEXCEPT
 Returs GAP block length. More...
 
template<typename T >
unsigned bm::gap_capacity (const T *BMRESTRICT buf, const T *BMRESTRICT glevel_len) BMNOEXCEPT
 Returs GAP block capacity. More...
 
template<typename T >
unsigned bm::gap_limit (const T *BMRESTRICT buf, const T *BMRESTRICT glevel_len) BMNOEXCEPT
 Returs GAP block capacity limit. More...
 
template<typename T >
bm::gap_level (const T *BMRESTRICT buf) BMNOEXCEPT
 Returs GAP blocks capacity level. More...
 
template<typename T >
unsigned bm::gap_find_last (const T *BMRESTRICT buf, unsigned *BMRESTRICT last) BMNOEXCEPT
 GAP block find the last set bit. More...
 
template<typename T >
unsigned bm::gap_find_first (const T *BMRESTRICT buf, unsigned *BMRESTRICT first) BMNOEXCEPT
 GAP block find the first set bit. More...
 
template<typename T >
unsigned bm::gap_test (const T *BMRESTRICT buf, unsigned pos) BMNOEXCEPT
 Tests if bit = pos is true. More...
 
template<typename T >
unsigned bm::gap_test_unr (const T *BMRESTRICT buf, const unsigned pos) BMNOEXCEPT
 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) BMNOEXCEPT
 
template<typename T >
unsigned bm::gap_bit_count (const T *buf, unsigned dsize=0) BMNOEXCEPT
 Calculates number of bits ON in GAP buffer. More...
 
template<typename T >
unsigned bm::gap_bit_count_unr (const T *buf) BMNOEXCEPT
 Calculates number of bits ON in GAP buffer. Loop unrolled version. More...
 
template<typename T >
unsigned bm::gap_bit_count_range (const T *const buf, unsigned left, unsigned right) BMNOEXCEPT
 Counts 1 bits in GAP buffer in the closed [left, right] range. More...
 
template<typename T >
bool bm::gap_is_all_one_range (const T *const BMRESTRICT buf, unsigned left, unsigned right) BMNOEXCEPT
 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 BMRESTRICT buf, unsigned left, unsigned right) BMNOEXCEPT
 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 BMRESTRICT buf, unsigned left, unsigned right) BMNOEXCEPT
 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 BMRESTRICT buf, unsigned nbit, unsigned *BMRESTRICT pos) BMNOEXCEPT
 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 BMRESTRICT buf, unsigned nbit, unsigned *BMRESTRICT pos) BMNOEXCEPT
 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 BMRESTRICT buf, unsigned nbit, unsigned *BMRESTRICT pos) BMNOEXCEPT
 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) BMNOEXCEPT
 GAP block find position for the rank. More...
 
template<typename T >
unsigned bm::gap_bit_count_to (const T *const buf, T right, bool is_corrected=false) BMNOEXCEPT
 Counts 1 bits in GAP buffer in the closed [0, right] range. More...
 
template<typename T >
int bm::gapcmp (const T *buf1, const T *buf2) BMNOEXCEPT
 Lexicographical comparison of GAP buffers. More...
 
template<typename T >
bool bm::gap_find_first_diff (const T *BMRESTRICT buf1, const T *BMRESTRICT buf2, unsigned *BMRESTRICT pos) BMNOEXCEPT
 Find first bit which is different between two GAP-blocks. More...
 
template<typename T , class F >
unsigned bm::gap_buff_any_op (const T *BMRESTRICT vect1, unsigned vect1_mask, const T *BMRESTRICT vect2, unsigned vect2_mask) BMNOEXCEPT2
 Abstract operation for GAP buffers (predicts legth) 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) BMNOEXCEPT2
 Abstract distance(similarity) operation for GAP buffers. Receives functor F as a template argument. More...
 
template<typename T >
unsigned bm::gap_set_value (unsigned val, T *BMRESTRICT buf, unsigned pos, unsigned *BMRESTRICT is_set) BMNOEXCEPT
 Sets or clears bit in the GAP buffer. More...
 
template<typename T >
unsigned bm::gap_set_value (unsigned val, T *BMRESTRICT buf, unsigned pos) BMNOEXCEPT
 Sets or clears bit in the GAP buffer. More...
 
template<typename T >
unsigned bm::gap_add_value (T *buf, unsigned pos) BMNOEXCEPT
 Add new value to the end of GAP buffer. More...
 
template<typename T >
bool bm::gap_shift_r1 (T *BMRESTRICT buf, unsigned co_flag, unsigned *BMRESTRICT new_len) BMNOEXCEPT
 Right shift GAP block by 1 bit. More...
 
template<typename T >
bool bm::gap_shift_l1 (T *BMRESTRICT buf, unsigned co_flag, unsigned *BMRESTRICT new_len) BMNOEXCEPT
 Left shift GAP block by 1 bit. More...
 
template<typename T >
unsigned bm::gap_set_array (T *buf, const T *arr, unsigned len) BMNOEXCEPT
 Convert array to GAP buffer. More...
 
template<typename T >
unsigned bm::bit_array_compute_gaps (const T *arr, unsigned len) BMNOEXCEPT
 Compute number of GAPs in bit-array. More...
 
template<typename T >
unsigned bm::gap_block_find (const T *BMRESTRICT buf, unsigned nbit, bm::id_t *BMRESTRICT prev) BMNOEXCEPT
 Searches for the next 1 bit in the GAP block. More...
 
template<typename T >
void bm::gap_sub_to_bitset (unsigned *BMRESTRICT dest, const T *BMRESTRICT pcurr) BMNOEXCEPT
 SUB (AND NOT) GAP block to bitblock. More...
 
template<typename T >
void bm::gap_sub_to_bitset (unsigned *BMRESTRICT dest, const T *BMRESTRICT pcurr, bm::id64_t digest0) BMNOEXCEPT
 SUB (AND NOT) GAP block to bitblock with digest assist. More...
 
template<typename T >
void bm::gap_xor_to_bitset (unsigned *BMRESTRICT dest, const T *BMRESTRICT pcurr) BMNOEXCEPT
 XOR GAP block to bitblock. More...
 
template<typename T >
void bm::gap_add_to_bitset (unsigned *BMRESTRICT dest, const T *BMRESTRICT pcurr, unsigned len) BMNOEXCEPT
 Adds(OR) GAP block to bitblock. More...
 
template<typename T >
void bm::gap_add_to_bitset (unsigned *BMRESTRICT dest, const T *BMRESTRICT pcurr) BMNOEXCEPT
 Adds(OR) GAP block to bitblock. More...
 
template<typename T >
void bm::gap_and_to_bitset (unsigned *BMRESTRICT dest, const T *BMRESTRICT pcurr) BMNOEXCEPT
 ANDs GAP block to bitblock. More...
 
template<typename T >
void bm::gap_and_to_bitset (unsigned *BMRESTRICT dest, const T *BMRESTRICT pcurr, bm::id64_t digest0) BMNOEXCEPT
 ANDs GAP block to bitblock with digest assist. More...
 
template<typename T >
bm::id_t bm::gap_bitset_and_count (const unsigned *BMRESTRICT block, const T *BMRESTRICT pcurr) BMNOEXCEPT
 Compute bitcount of bit block AND masked by GAP block. More...
 
template<typename T >
bm::id_t bm::gap_bitset_and_any (const unsigned *BMRESTRICT block, const T *BMRESTRICT pcurr) BMNOEXCEPT
 Bitcount test of bit block AND masked by GAP block. More...
 
template<typename T >
bm::id_t bm::gap_bitset_sub_count (const unsigned *BMRESTRICT block, const T *BMRESTRICT buf) BMNOEXCEPT
 Compute bitcount of bit block SUB masked by GAP block. More...
 
template<typename T >
bm::id_t bm::gap_bitset_sub_any (const unsigned *BMRESTRICT block, const T *BMRESTRICT buf) BMNOEXCEPT
 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 *BMRESTRICT block, const T *BMRESTRICT buf) BMNOEXCEPT
 Compute bitcount of bit block XOR masked by GAP block. More...
 
template<typename T >
bm::id_t bm::gap_bitset_xor_any (const unsigned *BMRESTRICT block, const T *BMRESTRICT buf) BMNOEXCEPT
 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 *BMRESTRICT block, const T *BMRESTRICT buf) BMNOEXCEPT
 Compute bitcount of bit block OR masked by GAP block. More...
 
template<typename T >
bm::id_t bm::gap_bitset_or_any (const unsigned *BMRESTRICT block, const T *BMRESTRICT buf) BMNOEXCEPT
 Compute bitcount test of bit block OR masked by GAP block. More...
 
template<typename T >
void bm::gap_convert_to_bitset (unsigned *BMRESTRICT dest, const T *BMRESTRICT buf) BMNOEXCEPT
 GAP block to bitblock conversion. More...
 
template<typename T >
unsigned * bm::gap_convert_to_bitset_smart (unsigned *BMRESTRICT dest, const T *BMRESTRICT buf, id_t set_max) BMNOEXCEPT
 Smart GAP block to bitblock conversion. More...
 
template<typename T >
unsigned bm::gap_control_sum (const T *buf) BMNOEXCEPT
 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) BMNOEXCEPT
 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) BMNOEXCEPT
 Init gap block so it has block in it (can be whole block) More...
 
template<typename T >
void bm::gap_invert (T *buf) BMNOEXCEPT
 Inverts all bits in the GAP buffer. More...
 
template<typename T >
void bm::set_gap_level (T *buf, int level) BMNOEXCEPT
 Sets GAP block capacity level. More...
 
template<typename T >
int bm::gap_calc_level (unsigned len, const T *glevel_len) BMNOEXCEPT
 Calculates GAP block capacity level. More...
 
template<typename T >
unsigned bm::gap_free_elements (const T *BMRESTRICT buf, const T *BMRESTRICT glevel_len) BMNOEXCEPT
 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 *BMRESTRICT dest, const unsigned *BMRESTRICT block, unsigned dest_len) BMNOEXCEPT
 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 *BMRESTRICT dest, const T *BMRESTRICT buf, unsigned dest_len, bool invert=false) BMNOEXCEPT
 Convert gap block into array of ints corresponding to 1 bits. More...
 
gap_word_tbm::gap_operation_and (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2, gap_word_t *BMRESTRICT tmp_buf, unsigned &dsize) BMNOEXCEPT
 GAP AND operation. More...
 
unsigned bm::gap_operation_any_and (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2) BMNOEXCEPT
 GAP AND operation test. More...
 
unsigned bm::gap_count_and (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2) BMNOEXCEPT
 GAP bitcount AND operation test. More...
 
gap_word_tbm::gap_operation_xor (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2, gap_word_t *BMRESTRICT tmp_buf, unsigned &dsize) BMNOEXCEPT
 GAP XOR operation. More...
 
BMFORCEINLINE unsigned bm::gap_operation_any_xor (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2) BMNOEXCEPT
 GAP XOR operation test. More...
 
BMFORCEINLINE unsigned bm::gap_count_xor (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2) BMNOEXCEPT
 GAP bitcount XOR operation test. More...
 
gap_word_tbm::gap_operation_or (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2, gap_word_t *BMRESTRICT tmp_buf, unsigned &dsize) BMNOEXCEPT
 GAP OR operation. More...
 
BMFORCEINLINE unsigned bm::gap_count_or (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2) BMNOEXCEPT
 GAP bitcount OR operation test. More...
 
gap_word_tbm::gap_operation_sub (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2, gap_word_t *BMRESTRICT tmp_buf, unsigned &dsize) BMNOEXCEPT
 GAP SUB (AND NOT) operation. More...
 
unsigned bm::gap_operation_any_sub (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2) BMNOEXCEPT
 GAP SUB operation test. More...
 
BMFORCEINLINE unsigned bm::gap_count_sub (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2) BMNOEXCEPT
 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) BMNOEXCEPT
 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) BMNOEXCEPT
 Finds optimal gap blocks lengths. More...
 
template<typename T , typename Func , typename SIZE_TYPE >
void 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 >
void bm::for_each_gap_blk_range (const T *BMRESTRICT 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...
 

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 
)

Compute number of GAPs in bit-array.

Parameters
arr- array of BITs
len- array length

Definition at line 3466 of file bmfunc.h.

◆ bit_block_to_gap()

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

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 4568 of file bmfunc.h.

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

Referenced by bm::bit_to_gap().

◆ for_each_gap_blk()

template<typename T , typename Func , typename SIZE_TYPE >
void 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)

Definition at line 1674 of file bmalgo_impl.h.

Referenced by bm::for_each_bit_block_range().

◆ for_each_gap_blk_range()

template<typename T , typename Func , typename SIZE_TYPE >
void bm::for_each_gap_blk_range ( const T *BMRESTRICT  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)

Definition at line 1705 of file bmalgo_impl.h.

References bm::bits_in_block, BM_ASSERT, BMRESTRICT, and bm::gap_bfind().

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 4670 of file bmfunc.h.

◆ gap_add_to_bitset() [1/2]

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

◆ gap_add_to_bitset() [2/2]

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

Adds(OR) GAP block to bitblock.

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

Definition at line 3872 of file bmfunc.h.

References bm::gap_add_to_bitset().

◆ gap_add_value()

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

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 3227 of file bmfunc.h.

References BM_ASSERT, and bm::gap_max_bits.

Referenced by bm::deseriaizer_base< bm::decoder, BV::block_idx_type >::read_gap_block().

◆ gap_and_to_bitset() [1/2]

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

ANDs GAP block to bitblock.

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

Definition at line 3888 of file bmfunc.h.

References BM_ASSERT, and bm::sub_bit_block().

Referenced by bm::bvector<>::combine_operation(), bm::aggregator< bvector_type >::process_gap_blocks_and(), and bm::aggregator< bvector_type >::process_shift_right_and().

◆ gap_and_to_bitset() [2/2]

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

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

Definition at line 3923 of file bmfunc.h.

References BM_ASSERT, bm::check_zero_digest(), bm::count_leading_zeros_u64(), bm::count_trailing_zeros_u64(), bm::set_block_digest_pos_shift, and bm::sub_bit_block().

◆ gap_any_range()

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

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 2314 of file bmfunc.h.

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

Referenced by bm::block_any_range().

◆ gap_bit_count()

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

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 2154 of file bmfunc.h.

Referenced by bm::gap_bit_count_unr().

◆ gap_bit_count_range()

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

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
Returns
Number of non-zero bits.

Definition at line 2248 of file bmfunc.h.

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

Referenced by bm::bvector<>::build_rs_index(), bm::bvector<>::count_range(), and bm::bvector<>::count_to().

◆ gap_bit_count_to()

template<typename T >
unsigned bm::gap_bit_count_to ( const T *const  buf,
right,
bool  is_corrected = false 
)

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

Parameters
buf- GAP buffer pointer.
right-rightmost bit index
is_corrected- if true the result will be rank corrected if right bit == true count=count-1
Returns
Number of non-zero bits

Definition at line 2514 of file bmfunc.h.

References BM_ASSERT.

Referenced by bm::bvector<>::count_to(), bm::bvector<>::count_to_test(), and bm::bvector<>::rank_corrected().

◆ gap_bit_count_unr()

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

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 2182 of file bmfunc.h.

References bm::avx2_gap_sum_arr(), BM_ASSERT, bm::gap_bit_count(), and bm::sse2_gap_sum_arr().

Referenced by bm::combine_count_operation_with_block(), bm::serializer< bvector_type >::find_gap_best_encoding(), bm::xor_scanner< bvector_type >::search_best_xor_gap(), and bm::serializer< bvector_type >::serialize().

◆ gap_bitset_and_any()

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

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 4013 of file bmfunc.h.

References bm::bit_block_any_range(), and BM_ASSERT.

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 *BMRESTRICT  block,
const T *BMRESTRICT  pcurr 
)

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 3985 of file bmfunc.h.

References bm::bit_block_calc_count_range(), and BM_ASSERT.

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 *BMRESTRICT  block,
const T *BMRESTRICT  buf 
)

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 4224 of file bmfunc.h.

References bm::bit_is_all_zero(), 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 *BMRESTRICT  block,
const T *BMRESTRICT  buf 
)

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 4192 of file bmfunc.h.

References bm::bit_block_calc_count_range(), and BM_ASSERT.

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 *BMRESTRICT  block,
const T *BMRESTRICT  buf 
)

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 4078 of file bmfunc.h.

References bm::bit_block_any_range(), and BM_ASSERT.

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 *BMRESTRICT  block,
const T *BMRESTRICT  buf 
)

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 4043 of file bmfunc.h.

References bm::bit_block_calc_count_range(), and BM_ASSERT.

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 *BMRESTRICT  block,
const T *BMRESTRICT  buf 
)

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 4154 of file bmfunc.h.

References bm::bit_block_any_range(), and BM_ASSERT.

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 *BMRESTRICT  block,
const T *BMRESTRICT  buf 
)

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 4116 of file bmfunc.h.

References bm::bit_block_calc_count_range(), and BM_ASSERT.

Referenced by bm::combine_count_operation_with_block().

◆ gap_block_find()

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

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 3498 of file bmfunc.h.

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

Referenced by bm::bvector<>::select().

◆ gap_buff_any_op()

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

Abstract operation for GAP buffers (predicts legth) Receives functor F as a template argument.

Parameters
vect1- operand 1 GAP encoded buffer.
vect2- operand 2 GAP encoded buffer.
dlen- destination length after the operation
limit- maximum target length limit, returns false if limit is reached
Returns
true if operation would be successfull or false if limit reached
Note
Internal function.

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 2914 of file bmfunc.h.

References bm::gap_max_bits.

◆ 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 2979 of file bmfunc.h.

References bm::gap_max_bits.

◆ gap_calc_level()

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

Calculates GAP block capacity level.

Parameters
len- GAP buffer length.
glevel_len- GAP lengths table
Returns
GAP block capacity level. -1 if block does not fit any level.

Definition at line 4444 of file bmfunc.h.

References BM_ASSERT, and bm::gap_levels.

Referenced by bm::iterator_deserializer< BV, bm::serial_stream_iterator >::deserialize(), bm::deserializer< BV, bm::decoder >::deserialize_gap(), and bm::gap_overhead().

◆ gap_capacity()

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

Returs GAP block capacity.

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

Definition at line 1495 of file bmfunc.h.

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

◆ gap_control_sum()

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

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 4304 of file bmfunc.h.

References BM_ASSERT.

◆ gap_convert_to_arr()

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

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

Definition at line 4725 of file bmfunc.h.

References BMFORCEINLINE, and BMRESTRICT.

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

◆ gap_convert_to_bitset()

template<typename T >
void bm::gap_convert_to_bitset ( unsigned *BMRESTRICT  dest,
const T *BMRESTRICT  buf 
)

◆ gap_convert_to_bitset_smart()

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

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 4283 of file bmfunc.h.

References FULL_BLOCK_REAL_ADDR, and bm::gap_convert_to_bitset().

Referenced by bm::bvector<>::combine_operation().

◆ gap_count_and()

unsigned bm::gap_count_and ( const gap_word_t *BMRESTRICT  vect1,
const gap_word_t *BMRESTRICT  vect2 
)
inline

GAP bitcount AND operation test.

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

Definition at line 6276 of file bmfunc.h.

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

◆ gap_count_or()

BMFORCEINLINE unsigned bm::gap_count_or ( const gap_word_t *BMRESTRICT  vect1,
const gap_word_t *BMRESTRICT  vect2 
)

GAP bitcount OR operation test.

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

Definition at line 6402 of file bmfunc.h.

Referenced by bm::combine_count_operation_with_block().

◆ gap_count_sub()

BMFORCEINLINE unsigned bm::gap_count_sub ( const gap_word_t *BMRESTRICT  vect1,
const gap_word_t *BMRESTRICT  vect2 
)

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 6473 of file bmfunc.h.

Referenced by bm::combine_count_operation_with_block().

◆ gap_count_xor()

BMFORCEINLINE unsigned bm::gap_count_xor ( const gap_word_t *BMRESTRICT  vect1,
const gap_word_t *BMRESTRICT  vect2 
)

GAP bitcount XOR operation test.

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

Definition at line 6357 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 *BMRESTRICT  buf,
unsigned *BMRESTRICT  first 
)

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 1574 of file bmfunc.h.

References BM_ASSERT, and bm::gap_max_bits.

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

◆ gap_find_first_diff()

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

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 2725 of file bmfunc.h.

References BM_ASSERT.

Referenced by bm::block_find_first_diff().

◆ gap_find_interval_end()

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

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 2372 of file bmfunc.h.

References BM_ASSERT, 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 BMRESTRICT  buf,
unsigned  nbit,
unsigned *BMRESTRICT  pos 
)

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 2397 of file bmfunc.h.

References BM_ASSERT, 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 *BMRESTRICT  buf,
unsigned *BMRESTRICT  last 
)

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 1543 of file bmfunc.h.

References BM_ASSERT, and bm::gap_max_bits.

Referenced by bm::bvector<>::find_reverse().

◆ gap_find_prev()

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

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 2425 of file bmfunc.h.

References BM_ASSERT, 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 
)

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 2462 of file bmfunc.h.

References BM_ASSERT, and bm::gap_bfind().

Referenced by bm::block_find_rank().

◆ gap_free_elements()

template<typename T >
unsigned bm::gap_free_elements ( const T *BMRESTRICT  buf,
const T *BMRESTRICT  glevel_len 
)
inline

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 4465 of file bmfunc.h.

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

◆ gap_init_range_block()

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

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 4353 of file bmfunc.h.

References bm::bits_in_block, BM_ASSERT, and bm::gap_set_all().

◆ gap_invert()

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

◆ gap_is_all_one()

BMFORCEINLINE bool bm::gap_is_all_one ( const bm::gap_word_t *BMRESTRICT  buf)

Checks if GAP block is all-one.

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

Definition at line 1466 of file bmfunc.h.

References BMFORCEINLINE, and bm::gap_max_bits.

Referenced by bm::check_block_one().

◆ gap_is_all_one_range()

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

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 2291 of file bmfunc.h.

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

Referenced by bm::block_is_all_one_range().

◆ gap_is_all_zero()

BMFORCEINLINE bool bm::gap_is_all_zero ( const bm::gap_word_t *BMRESTRICT  buf)

Checks if GAP block is all-zero.

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

Definition at line 1453 of file bmfunc.h.

References BMFORCEINLINE, and bm::gap_max_bits.

Referenced by bm::block_any(), bm::check_block_zero(), bm::combine_any_operation_with_block(), bm::bvector<>::combine_operation(), bm::bvector<>::compare(), bm::bvector<>::erase(), and bm::gap_bitset_or_any().

◆ gap_is_interval()

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

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 2343 of file bmfunc.h.

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

Referenced by bm::block_is_interval().

◆ gap_length()

BMFORCEINLINE bm::gap_word_t bm::gap_length ( const bm::gap_word_t *BMRESTRICT  buf)

◆ gap_level()

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

Returs GAP blocks capacity level.

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

Definition at line 1525 of file bmfunc.h.

◆ gap_limit()

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

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 1511 of file bmfunc.h.

Referenced by bm::combine_or(), bm::combine_sub(), bm::combine_xor(), bm::bvector<>::erase(), bm::bvector<>::insert(), and bm::bvector<>::set_bit_no_check().

◆ gap_operation_and()

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

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 6234 of file bmfunc.h.

Referenced by bm::operation_functions< T >::bit_operation_count(), and bm::bvector<>::combine_operation().

◆ gap_operation_any_and()

unsigned bm::gap_operation_any_and ( const gap_word_t *BMRESTRICT  vect1,
const gap_word_t *BMRESTRICT  vect2 
)
inline

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 6259 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 *BMRESTRICT  vect1,
const gap_word_t *BMRESTRICT  vect2 
)
inline

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 6454 of file bmfunc.h.

References BMFORCEINLINE.

Referenced by bm::combine_any_operation_with_block().

◆ gap_operation_any_xor()

BMFORCEINLINE unsigned bm::gap_operation_any_xor ( const gap_word_t *BMRESTRICT  vect1,
const gap_word_t *BMRESTRICT  vect2 
)

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 6341 of file bmfunc.h.

References BMFORCEINLINE.

Referenced by bm::combine_any_operation_with_block().

◆ gap_operation_or()

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

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 6382 of file bmfunc.h.

References BMFORCEINLINE, and bm::gap_invert().

Referenced by bm::operation_functions< T >::bit_operation_count(), bm::combine_any_operation_with_block(), and bm::bvector<>::combine_operation().

◆ gap_operation_sub()

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

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 6428 of file bmfunc.h.

Referenced by bm::operation_functions< T >::bit_operation_count(), and bm::bvector<>::combine_operation().

◆ gap_operation_xor()

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

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 6301 of file bmfunc.h.

References BMFORCEINLINE.

Referenced by bm::operation_functions< T >::bit_operation_count(), bm::bvector<>::combine_operation(), bm::xor_scanner< bvector_type >::search_best_xor_gap(), bm::serializer< bvector_type >::serialize(), and bm::deserializer< BV, bm::decoder >::xor_decode().

◆ gap_overhead()

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

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

Definition at line 8501 of file bmfunc.h.

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

Referenced by bm::improve_gap_levels().

◆ gap_set_all()

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

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 4335 of file bmfunc.h.

References BM_ASSERT.

Referenced by bm::gap_init_range_block(), bm::deseriaizer_base< bm::decoder, BV::block_idx_type >::read_gap_block(), and bm::miniset< A, N >::swap().

◆ gap_set_array()

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

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 3405 of file bmfunc.h.

References BM_ASSERT, and bm::gap_max_bits.

Referenced by bm::deserializer< BV, bm::decoder >::deserialize_gap(), and bm::deseriaizer_base< bm::decoder, BV::block_idx_type >::read_gap_block().

◆ gap_set_value() [1/2]

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

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 3061 of file bmfunc.h.

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

Referenced by bm::combine_or(), bm::combine_sub(), bm::combine_xor(), bm::gap_shift_l1(), bm::gap_shift_r1(), bm::miniset< A, N >::set(), and bm::bvector<>::set_bit_no_check().

◆ gap_set_value() [2/2]

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

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 3147 of file bmfunc.h.

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

◆ gap_shift_l1()

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

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 3346 of file bmfunc.h.

References BM_ASSERT, bm::gap_max_bits, and bm::gap_set_value().

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

◆ gap_shift_r1()

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

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 3297 of file bmfunc.h.

References BM_ASSERT, bm::gap_max_bits, and bm::gap_set_value().

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

◆ gap_split()

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

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 2094 of file bmfunc.h.

◆ gap_sub_to_bitset() [1/2]

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

SUB (AND NOT) GAP block to bitblock.

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

Definition at line 3722 of file bmfunc.h.

References BM_ASSERT, and bm::sub_bit_block().

Referenced by bm::bvector<>::combine_operation(), and bm::aggregator< bvector_type >::process_gap_blocks_sub().

◆ gap_sub_to_bitset() [2/2]

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

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

Definition at line 3751 of file bmfunc.h.

References BM_ASSERT, bm::check_zero_digest(), bm::count_leading_zeros_u64(), bm::count_trailing_zeros_u64(), bm::set_block_digest_pos_shift, and bm::sub_bit_block().

◆ gap_test()

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

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 1636 of file bmfunc.h.

References BM_ASSERT, and bm::gap_max_bits.

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

◆ gap_test_unr()

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

◆ gap_xor_to_bitset()

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

XOR GAP block to bitblock.

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

Definition at line 3810 of file bmfunc.h.

References BM_ASSERT, and bm::xor_bit_block().

Referenced by bm::bvector<>::combine_operation().

◆ gapcmp()

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

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 2669 of file bmfunc.h.

Referenced by bm::bvector<>::compare().

◆ improve_gap_levels()

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

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 8528 of file bmfunc.h.

References BM_ASSERT, bm::gap_levels, bm::gap_max_buff_len, and bm::gap_overhead().

Referenced by bm::bvector<>::optimize_gap_size().

◆ set_gap_level()

template<typename T >
void bm::set_gap_level ( T *  buf,
int  level 
)

Sets GAP block capacity level.

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

Definition at line 4422 of file bmfunc.h.

References BM_ASSERT, and bm::gap_levels.

Referenced by bm::iterator_deserializer< BV, bm::serial_stream_iterator >::deserialize(), and bm::deserializer< BV, bm::decoder >::deserialize_gap().