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.
BMFORCEINLINE bool | bm::gap_is_all_one (const bm::gap_word_t *BMRESTRICT buf) BMNOEXCEPT
| Checks if GAP block is all-one.
BMFORCEINLINE bm::gap_word_t | bm::gap_length (const bm::gap_word_t *BMRESTRICT buf) BMNOEXCEPT
| Returs GAP block length.
template<typename T>
unsigned | bm::gap_capacity (const T *BMRESTRICT buf, const T *BMRESTRICT glevel_len) BMNOEXCEPT
| Returs GAP block capacity.
template<typename T>
unsigned | bm::gap_limit (const T *BMRESTRICT buf, const T *BMRESTRICT glevel_len) BMNOEXCEPT
| Returs GAP block capacity limit.
template<typename T>
T | bm::gap_level (const T *BMRESTRICT buf) BMNOEXCEPT
| Returs GAP blocks capacity level.
template<typename T>
unsigned | bm::gap_find_last (const T *BMRESTRICT buf, unsigned *BMRESTRICT last) BMNOEXCEPT
| GAP block find the last set bit.
template<typename T>
unsigned | bm::gap_find_first (const T *BMRESTRICT buf, unsigned *BMRESTRICT first) BMNOEXCEPT
| GAP block find the first set bit.
template<typename T>
unsigned | bm::gap_test (const T *BMRESTRICT buf, unsigned pos) BMNOEXCEPT
| Tests if bit = pos is true.
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.
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.
template<typename T>
unsigned | bm::gap_bit_count_unr (const T *buf) BMNOEXCEPT
| Calculates number of bits ON in GAP buffer. Loop unrolled version.
template<typename T, bool RIGHT_END = false>
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.
template<typename T>
unsigned | bm::gap_bit_count_range_hint (const T *const buf, unsigned left, unsigned right, unsigned hint) BMNOEXCEPT
| Counts 1 bits in GAP buffer in the closed [left, right] range using position hint to avoid bfind.
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.
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.
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.
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.
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.
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
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.
template<typename T>
int | bm::gapcmp (const T *buf1, const T *buf2) BMNOEXCEPT
| Lexicographical comparison of GAP buffers.
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.
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 distance test operation for GAP buffers. Receives functor F as a template argument.
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.
template<typename T>
unsigned | bm::gap_set_value_cpos (unsigned val, T *BMRESTRICT buf, unsigned pos, unsigned *BMRESTRICT is_set, unsigned curr) BMNOEXCEPT
| Sets or clears bit in the GAP buffer.
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.
template<typename T>
unsigned | bm::gap_set_value (unsigned val, T *BMRESTRICT buf, unsigned pos) BMNOEXCEPT
| Sets or clears bit in the GAP buffer.
template<typename T>
unsigned | bm::gap_add_value (T *buf, unsigned pos) BMNOEXCEPT
| Add new value to the end of GAP buffer.
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.
template<typename T>
bool | bm::gap_insert (T *BMRESTRICT buf, unsigned pos, unsigned val, unsigned *BMRESTRICT new_len) BMNOEXCEPT
| isnert bit into GAP compressed block
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.
template<typename T>
unsigned | bm::gap_set_array (T *buf, const T *arr, unsigned len) BMNOEXCEPT
| Convert array to GAP buffer.
template<typename T>
unsigned | bm::bit_array_compute_gaps (const T *arr, unsigned len) BMNOEXCEPT
| Compute number of GAPs in bit-array.
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.
template<typename T>
void | bm::gap_sub_to_bitset (unsigned *BMRESTRICT dest, const T *BMRESTRICT pcurr) BMNOEXCEPT
| SUB (AND NOT) GAP block to bitblock.
template<typename T>
bm::id64_t | 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.
template<typename T>
void | bm::gap_xor_to_bitset (unsigned *BMRESTRICT dest, const T *BMRESTRICT pcurr) BMNOEXCEPT
| XOR GAP block to bitblock.
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.
template<typename T>
void | bm::gap_add_to_bitset (unsigned *BMRESTRICT dest, const T *BMRESTRICT pcurr) BMNOEXCEPT
| Adds(OR) GAP block to bitblock.
template<typename T>
void | bm::gap_and_to_bitset (unsigned *BMRESTRICT dest, const T *BMRESTRICT pcurr) BMNOEXCEPT
| ANDs GAP block to bitblock.
template<typename T>
bm::id64_t | 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.
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.
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.
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.
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.
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.
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.
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.
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.
template<typename T>
void | bm::gap_convert_to_bitset (unsigned *BMRESTRICT dest, const T *BMRESTRICT buf, unsigned len=0) BMNOEXCEPT
| GAP block to bitblock conversion.
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.
template<typename T>
unsigned | bm::gap_control_sum (const T *buf) BMNOEXCEPT
| Calculates sum of all words in GAP block. (For debugging purposes).
template<class T>
void | bm::gap_set_all (T *buf, unsigned set_max, unsigned value) BMNOEXCEPT
| Sets all bits to 0 or 1 (GAP).
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).
template<typename T>
void | bm::gap_invert (T *buf) BMNOEXCEPT
| Inverts all bits in the GAP buffer.
template<typename T>
void | bm::set_gap_level (T *buf, int level) BMNOEXCEPT
| Sets GAP block capacity level.
template<typename T>
int | bm::gap_calc_level (unsigned len, const T *glevel_len) BMNOEXCEPT
| Calculates GAP block capacity level.
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.
unsigned | bm::bit_block_to_gap (gap_word_t *BMRESTRICT dest, const unsigned *BMRESTRICT block, unsigned dest_len) BMNOEXCEPT
| Converts bit block to GAP.
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.
template<typename D, typename T>
D | 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.
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) BMNOEXCEPT
| GAP AND operation.
unsigned | bm::gap_operation_any_and (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2) BMNOEXCEPT
| GAP AND operation test.
unsigned | bm::gap_count_and (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2) BMNOEXCEPT
| GAP bitcount AND operation test.
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) BMNOEXCEPT
| GAP XOR operation.
BMFORCEINLINE unsigned | bm::gap_operation_any_xor (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2) BMNOEXCEPT
| GAP XOR operation test.
BMFORCEINLINE unsigned | bm::gap_count_xor (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2) BMNOEXCEPT
| GAP bitcount XOR operation test.
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) BMNOEXCEPT
| GAP OR operation.
BMFORCEINLINE unsigned | bm::gap_count_or (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2) BMNOEXCEPT
| GAP bitcount OR operation test.
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) BMNOEXCEPT
| GAP SUB (AND NOT) operation.
unsigned | bm::gap_operation_any_sub (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2) BMNOEXCEPT
| GAP SUB operation test.
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.
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).
template<typename T>
bool | bm::improve_gap_levels (const T *length, const T *length_end, T *glevel_len) BMNOEXCEPT
| Finds optimal gap blocks lengths.
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
template<typename T, typename Func, typename SIZE_TYPE>
int | 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

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

References BMNOEXCEPT.

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

References bit_scan_forward32(), BM_ASSERT, BMNOEXCEPT, BMRESTRICT, and set_block_size.

Referenced by bit_to_gap().

## 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.

Referenced by 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 *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)

Returns
  - functor return code (< 0 - interrupt the processing)

Definition at line 1795 of file bmalgo_impl.h.

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

Referenced by 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.

## gap_add_to_bitset() [1/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 4074 of file bmfunc.h.

References BMNOEXCEPT, BMRESTRICT, and gap_add_to_bitset().

## gap_add_to_bitset() [2/2]

template<typename T>

void bm::gap_add_to_bitset | ( | unsigned *BMRESTRICT | dest,
|  | const T *BMRESTRICT | pcurr,
|  | unsigned | len )

Adds(OR) GAP block to bitblock.

Parameters

  dest | - bitblock buffer pointer.
  pcurr | - GAP buffer pointer.
  len | - gap length

Definition at line 4039 of file bmfunc.h.

References BM_ASSERT, BMNOEXCEPT, BMRESTRICT, and or_bit_block().

Referenced by bm::bvector< Alloc >::combine_operation_block_and_or(), bm::bvector< Alloc >::combine_operation_block_or(), bm::bvector< Alloc >::combine_operation_block_or(), bm::aggregator< BV >::combine_shift_right_and(), gap_add_to_bitset(), gap_convert_to_bitset(), bm::aggregator< BV >::process_gap_blocks_or(), and bm::deseriaizer_base< DEC, BLOCK_IDX >::read_bic_gap().

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

References BM_ASSERT, BMNOEXCEPT, and gap_max_bits.

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

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, BMNOEXCEPT, BMRESTRICT, and sub_bit_block().

Referenced by bm::bvector< Alloc >::combine_operation_block_and(), 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 *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

Returns
  new digest

Definition at line 4127 of file bmfunc.h.

References BM_ASSERT, BMNOEXCEPT, BMRESTRICT, check_zero_digest(), count_leading_zeros_u64(), count_trailing_zeros_u64(), gap_bfind(), set_block_digest_pos_shift, sub_bit_block(), and update_block_digest0().

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

References BM_ASSERT, BMNOEXCEPT, BMRESTRICT, gap_bfind(), and gap_max_bits.

Referenced by 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 2299 of file bmfunc.h.

References BMNOEXCEPT.

Referenced by gap_bit_count_unr().

## 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 )

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, BMNOEXCEPT, gap_bfind(), and gap_max_bits.

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

## 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 )

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, BMNOEXCEPT, gap_bfind(), and gap_max_bits.

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

References avx2_gap_sum_arr(), BM_ASSERT, BMNOEXCEPT, gap_bit_count(), and sse2_gap_sum_arr().

Referenced by combine_count_operation_with_block(), and bm::serializer< BV >::find_gap_best_encoding().

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

References bit_block_any_range(), BM_ASSERT, BMNOEXCEPT, and BMRESTRICT.

Referenced by 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 4198 of file bmfunc.h.

References bit_block_calc_count_range(), BM_ASSERT, BMNOEXCEPT, and BMRESTRICT.

Referenced by combine_count_and_operation_with_block(), and 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 4437 of file bmfunc.h.

References bit_is_all_zero(), BMNOEXCEPT, BMRESTRICT, and gap_is_all_zero().

Referenced by 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 4405 of file bmfunc.h.

References bit_block_calc_count_range(), BM_ASSERT, BMNOEXCEPT, and BMRESTRICT.

Referenced by 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 4291 of file bmfunc.h.

References bit_block_any_range(), BM_ASSERT, BMNOEXCEPT, and BMRESTRICT.

Referenced by 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 4256 of file bmfunc.h.

References bit_block_calc_count_range(), BM_ASSERT, BMNOEXCEPT, and BMRESTRICT.

Referenced by 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 4367 of file bmfunc.h.

References bit_block_any_range(), BM_ASSERT, BMNOEXCEPT, and BMRESTRICT.

Referenced by 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 4329 of file bmfunc.h.

References bit_block_calc_count_range(), BM_ASSERT, BMNOEXCEPT, and BMRESTRICT.

Referenced by 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 3694 of file bmfunc.h.

References BM_ASSERT, BMNOEXCEPT, BMRESTRICT, gap_bfind(), and gap_max_bits.

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 *BMRESTRICT | vect1,
|  | unsigned | vect1_mask,
|  | const T *BMRESTRICT | 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 BMNOEXCEPT2, BMRESTRICT, and gap_max_bits.

Referenced by gap_operation_any_and(), gap_operation_any_sub(), and gap_operation_any_xor().

## 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 BMNOEXCEPT2, and gap_max_bits.

Referenced by gap_count_and(), gap_count_or(), gap_count_sub(), and gap_count_xor().

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

References BM_ASSERT, BMNOEXCEPT, and gap_levels.

Referenced by bm::iterator_deserializer< BV, SerialIterator >::deserialize(), bm::deserializer< BV, DEC >::deserialize_gap(), and 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 1619 of file bmfunc.h.

References BMNOEXCEPT, and BMRESTRICT.

Referenced by bm::bvector< Alloc >::calc_stat(), bm::mem_alloc< block_allocator, ptr_allocator, standard_alloc_pool >::free_gap_block(), and 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 4521 of file bmfunc.h.

References BM_ASSERT, and BMNOEXCEPT.

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

References BMNOEXCEPT, and BMRESTRICT.

Referenced by bm::serializer< BV >::encode_gap_block().

## gap_convert_to_bitset()

template<typename T>

void bm::gap_convert_to_bitset | ( | unsigned *BMRESTRICT | dest,
|  | const T *BMRESTRICT | buf,
|  | unsigned | len = 0 )

GAP block to bitblock conversion.

Parameters

  dest | - bitblock buffer pointer.
  buf | - GAP buffer pointer.
  len | - GAP length

Definition at line 4475 of file bmfunc.h.

References bit_block_set(), BMNOEXCEPT, BMRESTRICT, gap_add_to_bitset(), and gap_length().

Referenced by block_find_first_diff(), bm::aggregator< BV >::cache_gap_block(), combine_any_operation_with_block(), combine_count_operation_with_block(), bm::bvector< Alloc >::combine_operation_block_sub(), bm::bvector< Alloc >::compare(), bm::xor_scanner< BV >::deoptimize_gap_blocks(), bm::iterator_deserializer< BV, SerialIterator >::deserialize(), bm::deserializer< BV, DEC >::deserialize_gap(), gap_convert_to_bitset_smart(), bm::deserializer< BV, DEC >::xor_decode(), bm::deserializer< BV, DEC >::xor_decode_chain(), and bm::serializer< BV >::xor_tmp_product().

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

References BMNOEXCEPT, BMRESTRICT, FULL_BLOCK_REAL_ADDR, and 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 *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 6560 of file bmfunc.h.

References BMNOEXCEPT, BMRESTRICT, and gap_buff_count_op().

Referenced by combine_count_and_operation_with_block(), and 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 6686 of file bmfunc.h.

References BMNOEXCEPT, BMRESTRICT, and gap_buff_count_op().

Referenced by 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 6757 of file bmfunc.h.

References BMNOEXCEPT, BMRESTRICT, and gap_buff_count_op().

Referenced by 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 6641 of file bmfunc.h.

References BMNOEXCEPT, BMRESTRICT, and gap_buff_count_op().

Referenced by 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 1698 of file bmfunc.h.

References BM_ASSERT, BMNOEXCEPT, BMRESTRICT, and gap_max_bits.

Referenced by 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 *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 2904 of file bmfunc.h.

References BM_ASSERT, BMNOEXCEPT, and BMRESTRICT.

Referenced by 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 2564 of file bmfunc.h.

References BM_ASSERT, BMNOEXCEPT, BMRESTRICT, gap_bfind(), and gap_max_bits.

Referenced by 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 2589 of file bmfunc.h.

References BM_ASSERT, BMNOEXCEPT, BMRESTRICT, gap_bfind(), and gap_max_bits.

Referenced by 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 1667 of file bmfunc.h.

References BM_ASSERT, BMNOEXCEPT, BMRESTRICT, and gap_max_bits.

Referenced by bm::bvector< Alloc >::find_reverse(), and bm::bvector< Alloc >::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 2617 of file bmfunc.h.

References BM_ASSERT, BMNOEXCEPT, BMRESTRICT, gap_bfind(), and gap_max_bits.

Referenced by 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 2654 of file bmfunc.h.

References BM_ASSERT, BMNOEXCEPT, and gap_bfind().

Referenced by 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 4682 of file bmfunc.h.

References BMNOEXCEPT, BMRESTRICT, gap_capacity(), and gap_length().

## gap_init_range_block()

template<class T>

void bm::gap_init_range_block | ( | T * | buf,
|  | T | from,
|  | T | to,
|  | T | 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 4570 of file bmfunc.h.

References bits_in_block, BM_ASSERT, BMNOEXCEPT, and gap_set_all().

Referenced by bm::bvector< Alloc >::clear_range_no_check(), bm::aggregator< BV >::set_range_hint(), and bm::bvector< Alloc >::set_range_no_check().

## gap_insert()

template<typename T>

bool bm::gap_insert | ( | T *BMRESTRICT | buf,
|  | unsigned | pos,
|  | unsigned | val,
|  | unsigned *BMRESTRICT | new_len )

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, BMNOEXCEPT, BMRESTRICT, gap_bfind(), gap_max_bits, and gap_set_value().

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

## gap_invert()

template<typename T>

void bm::gap_invert | ( | T * | buf | ) |

Inverts all bits in the GAP buffer.

Parameters

  buf | - GAP buffer pointer.

Definition at line 4620 of file bmfunc.h.

References BMNOEXCEPT.

Referenced by bm::bvector< Alloc >::combine_operation_block_xor(), bm::deserializer< BV, DEC >::deserialize_gap(), gap_operation_or(), bm::bvector< Alloc >::invert(), and bm::deseriaizer_base< DEC, BLOCK_IDX >::read_gap_block().

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

References BMNOEXCEPT, BMRESTRICT, and gap_max_bits.

Referenced by 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 2483 of file bmfunc.h.

References BM_ASSERT, BMNOEXCEPT, BMRESTRICT, gap_bfind(), and gap_max_bits.

Referenced by 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 1577 of file bmfunc.h.

References BMNOEXCEPT, BMRESTRICT, and gap_max_bits.

Referenced by block_any(), check_block_zero(), combine_any_operation_with_block(), bm::bvector< Alloc >::combine_operation_block_and(), bm::bvector< Alloc >::combine_operation_with_block(), bm::bvector< Alloc >::compare(), bm::bvector< Alloc >::erase(), and 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 2535 of file bmfunc.h.

References BM_ASSERT, BMNOEXCEPT, BMRESTRICT, gap_bfind(), and gap_max_bits.

Referenced by block_is_interval().

## gap_length()

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

Returs GAP block length.

Parameters

  buf | - GAP buffer pointer.

Returns
  GAP block length.

Definition at line 1603 of file bmfunc.h.

References BMNOEXCEPT, and BMRESTRICT.

Referenced by bm::bvector< Alloc >::calc_stat(), bm::xor_scanner< BV >::compute_sim_model(), bm::xor_scanner< BV >::deoptimize_gap_blocks(), bm::iterator_deserializer< BV, SerialIterator >::deserialize(), bm::deserializer< BV, DEC >::deserialize_gap(), 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(), gap_convert_to_bitset(), gap_free_elements(), bm::serializer< BV >::interpolated_encode_gap_block(), bm::deseriaizer_base< DEC, BLOCK_IDX >::read_gap_block(), bm::xor_scanner< BV >::search_best_xor_mask(), and bm::bvector< Alloc >::swap().

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

References BMNOEXCEPT, and BMRESTRICT.

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

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

References BMNOEXCEPT, and BMRESTRICT.

Referenced by combine_or(), combine_sub(), 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 *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 6518 of file bmfunc.h.

References BMNOEXCEPT, BMRESTRICT, and gap_buff_op().

Referenced by bm::bvector< Alloc >::combine_operation_block_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 *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 6543 of file bmfunc.h.

References BMNOEXCEPT, BMRESTRICT, and gap_buff_any_op().

Referenced by 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 6738 of file bmfunc.h.

References BMNOEXCEPT, BMRESTRICT, and gap_buff_any_op().

Referenced by 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 6625 of file bmfunc.h.

References BMNOEXCEPT, BMRESTRICT, and gap_buff_any_op().

Referenced by 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 6666 of file bmfunc.h.

References BMNOEXCEPT, BMRESTRICT, gap_buff_op(), and gap_invert().

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

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

References BMNOEXCEPT, BMRESTRICT, and gap_buff_op().

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

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

References BMNOEXCEPT, BMRESTRICT, and gap_buff_op().

Referenced by bm::bvector< Alloc >::combine_operation_block_xor(), bm::bvector< Alloc >::combine_operation_block_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 )

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, BMNOEXCEPT, gap_calc_level(), and gap_levels.

Referenced by 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 4552 of file bmfunc.h.

References BM_ASSERT, and BMNOEXCEPT.

Referenced by gap_init_range_block(), 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 )

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 BM_ASSERT, BMNOEXCEPT, and gap_max_bits.

Referenced by 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 *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 3281 of file bmfunc.h.

References BM_ASSERT, BMNOEXCEPT, BMRESTRICT, gap_bfind(), and gap_max_bits.

## gap_set_value() [2/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 3254 of file bmfunc.h.

References BM_ASSERT, BMNOEXCEPT, BMRESTRICT, gap_bfind(), gap_max_bits, and gap_set_value_cpos().

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

## gap_set_value_cpos()

template<typename T>

unsigned bm::gap_set_value_cpos | ( | unsigned | val,
|  | T *BMRESTRICT | buf,
|  | unsigned | pos,
|  | unsigned *BMRESTRICT | is_set,
|  | unsigned | curr )

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 BMNOEXCEPT, BMRESTRICT, and gap_max_bits.

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

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

References BM_ASSERT, BMNOEXCEPT, BMRESTRICT, gap_max_bits, and gap_set_value().

Referenced by bm::bvector< Alloc >::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 3431 of file bmfunc.h.

References BM_ASSERT, BMNOEXCEPT, BMRESTRICT, gap_max_bits, and gap_set_value().

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 )

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 BMNOEXCEPT.

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

References BM_ASSERT, BMNOEXCEPT, BMRESTRICT, and sub_bit_block().

Referenced by bm::bvector< Alloc >::combine_operation_block_sub(), 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 *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

Returns
  new digest

Definition at line 3943 of file bmfunc.h.

References BM_ASSERT, BMNOEXCEPT, BMRESTRICT, check_zero_digest(), count_leading_zeros_u64(), count_trailing_zeros_u64(), gap_bfind(), set_block_digest_pos_shift, sub_bit_block(), and update_block_digest0().

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

References BM_ASSERT, BMNOEXCEPT, BMRESTRICT, and gap_max_bits.

Referenced by 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 )

Tests if bit = pos is true. Analog of bm::gap_test with SIMD unrolling.

Parameters

  buf | - GAP buffer pointer.
  pos | - index of the element.

Returns
  true if position is in "1" gap

Definition at line 1833 of file bmfunc.h.

References BM_ASSERT, BMNOEXCEPT, BMRESTRICT, gap_max_bits, gap_test(), and VECT_GAP_TEST.

Referenced by bm::bvector< Alloc >::and_bit_no_check(), bm::aggregator< BV >::combine_and_sub(), combine_sub(), combine_xor(), bm::sparse_vector< Val, BV >::extract_range(), bm::sparse_vector< Val, BV >::gather(), bm::bvector< Alloc >::get_bit(), bm::basic_bmatrix< BV >::get_half_octet(), bm::basic_bmatrix< BV >::get_octet(), bm::bvector< Alloc >::inc(), bm::aggregator< BV >::process_gap_blocks_and(), bm::aggregator< BV >::process_gap_blocks_sub(), bm::bvector< Alloc >::swap(), bm::aggregator< BV >::test_gap_blocks_and(), and bm::aggregator< BV >::test_gap_blocks_sub().

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

References BM_ASSERT, BMNOEXCEPT, BMRESTRICT, and xor_bit_block().

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

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

References BMNOEXCEPT.

Referenced by bm::bvector< Alloc >::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 9170 of file bmfunc.h.

References BM_ASSERT, BMNOEXCEPT, gap_levels, gap_max_buff_len, and gap_overhead().

Referenced by bm::bvector< Alloc >::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.
  level | new GAP block capacity level.

Definition at line 4639 of file bmfunc.h.

References BM_ASSERT, BMNOEXCEPT, and gap_levels.

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