BitMagicC++Library
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

template<typename T >
unsigned bm::gap_test (const T *buf, unsigned pos)
 Tests if bit = pos is true. More...
 
template<typename T >
unsigned bm::gap_test_unr (const T *buf, const unsigned pos)
 Tests if bit = pos is true. Analog of bm::gap_test with SIMD unrolling. More...
 
template<typename T >
unsigned bm::gap_bit_count (const T *buf, unsigned dsize=0)
 Calculates number of bits ON in GAP buffer. More...
 
template<typename T >
unsigned bm::gap_bit_count_unr (const T *buf)
 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, T left, T right)
 Counts 1 bits in GAP buffer in the closed [left, right] range. More...
 
template<typename T >
unsigned bm::gap_bit_count_to (const T *const buf, T right)
 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)
 Lexicographical comparison of GAP buffers. 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, F f)
 Abstract distance test operation for GAP buffers. Receives functor F as a template argument. More...
 
template<typename T , class F >
unsigned bm::gap_buff_count_op (const T *vect1, const T *vect2, F f)
 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)
 Sets or clears bit in the GAP buffer. More...
 
template<typename T >
unsigned bm::gap_add_value (T *buf, unsigned pos)
 Add new value to the end of GAP buffer. More...
 
template<typename T >
unsigned bm::gap_set_array (T *buf, const T *arr, unsigned len)
 Convert array to GAP buffer. More...
 
template<typename T >
unsigned bm::bit_array_compute_gaps (const T *arr, unsigned len)
 Compute number of GAPs in bit-array. More...
 
template<typename T >
int bm::gap_find_in_block (const T *buf, unsigned nbit, bm::id_t *prev)
 Searches for the next 1 bit in the GAP block. More...
 
template<typename T >
void bm::gap_sub_to_bitset (unsigned *dest, const T *buf)
 SUB (AND NOT) GAP block to bitblock. More...
 
template<typename T >
void bm::gap_xor_to_bitset (unsigned *dest, const T *buf)
 XOR GAP block to bitblock. More...
 
template<typename T >
void bm::gap_add_to_bitset (unsigned *dest, const T *buf)
 Adds(OR) GAP block to bitblock. More...
 
template<typename T >
void bm::gap_and_to_bitset (unsigned *dest, const T *buf)
 ANDs GAP block to bitblock. More...
 
template<typename T >
bm::id_t bm::gap_bitset_and_count (const unsigned *block, const T *buf)
 Compute bitcount of bit block AND masked by GAP block. More...
 
template<typename T >
bm::id_t bm::gap_bitset_and_any (const unsigned *block, const T *buf)
 Bitcount test of bit block AND masked by GAP block. More...
 
template<typename T >
bm::id_t bm::gap_bitset_sub_count (const unsigned *block, const T *buf)
 Compute bitcount of bit block SUB masked by GAP block. More...
 
template<typename T >
bm::id_t bm::gap_bitset_sub_any (const unsigned *block, const T *buf)
 Compute bitcount test of bit block SUB masked by GAP block. More...
 
template<typename T >
bm::id_t bm::gap_bitset_xor_count (const unsigned *block, const T *buf)
 Compute bitcount of bit block XOR masked by GAP block. More...
 
template<typename T >
bm::id_t bm::gap_bitset_xor_any (const unsigned *block, const T *buf)
 Compute bitcount test of bit block XOR masked by GAP block. More...
 
template<typename T >
bm::id_t bm::gap_bitset_or_count (const unsigned *block, const T *buf)
 Compute bitcount of bit block OR masked by GAP block. More...
 
template<typename T >
bm::id_t bm::gap_bitset_or_any (const unsigned *block, const T *buf)
 Compute bitcount test of bit block OR masked by GAP block. More...
 
template<typename T >
void bm::gap_convert_to_bitset (unsigned *dest, const T *buf)
 GAP block to bitblock conversion. More...
 
template<typename T >
void bm::gap_convert_to_bitset (unsigned *dest, const T *buf, unsigned dest_len)
 GAP block to bitblock conversion. More...
 
template<typename T >
unsigned * bm::gap_convert_to_bitset_smart (unsigned *dest, const T *buf, id_t set_max)
 Smart GAP block to bitblock conversion. More...
 
template<typename T >
unsigned bm::gap_control_sum (const T *buf)
 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)
 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, unsigned set_max)
 Init gap block so it has block in it (can be whole block) More...
 
template<typename T >
void bm::gap_invert (T *buf)
 Inverts all bits in the GAP buffer. More...
 
template<typename T >
bool bm::gap_is_all_zero (const T *buf, unsigned set_max)
 Temporary inverts all bits in the GAP buffer. More...
 
template<typename T >
bool bm::gap_is_all_one (const T *buf, unsigned set_max)
 Checks if GAP block is all-one. More...
 
template<typename T >
bm::gap_length (const T *buf)
 Returs GAP block length. More...
 
template<typename T >
unsigned bm::gap_capacity (const T *buf, const T *glevel_len)
 Returs GAP block capacity. More...
 
template<typename T >
unsigned bm::gap_limit (const T *buf, const T *glevel_len)
 Returs GAP block capacity limit. More...
 
template<typename T >
unsigned bm::gap_level (const T *buf)
 Returs GAP blocks capacity level. More...
 
template<typename T >
void bm::set_gap_level (T *buf, unsigned level)
 Sets GAP block capacity level. More...
 
template<typename T >
int bm::gap_calc_level (int len, const T *glevel_len)
 Calculates GAP block capacity level. More...
 
template<typename T >
unsigned bm::gap_free_elements (const T *buf, const T *glevel_len)
 Returns number of free elements in GAP block array. Difference between GAP block capacity on this level and actual GAP length. More...
 
template<typename T >
unsigned bm::bit_convert_to_gap (T *BMRESTRICT dest, const unsigned *BMRESTRICT src, bm::id_t bits, unsigned dest_len)
 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)
 Convert gap block into array of ints corresponding to 1 bits. More...
 
BMFORCEINLINE 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)
 GAP AND operation. More...
 
BMFORCEINLINE unsigned bm::gap_operation_any_and (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2)
 GAP AND operation test. More...
 
BMFORCEINLINE unsigned bm::gap_count_and (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2)
 GAP bitcount AND operation test. More...
 
BMFORCEINLINE 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)
 GAP XOR operation. More...
 
BMFORCEINLINE unsigned bm::gap_operation_any_xor (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2)
 GAP XOR operation test. More...
 
BMFORCEINLINE unsigned bm::gap_count_xor (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2)
 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)
 GAP OR operation. More...
 
BMFORCEINLINE unsigned bm::gap_count_or (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2)
 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)
 GAP SUB (AND NOT) operation. More...
 
BMFORCEINLINE unsigned bm::gap_operation_any_sub (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2)
 GAP SUB operation test. More...
 
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. More...
 
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). More...
 
template<typename T >
bool bm::improve_gap_levels (const T *length, const T *length_end, T *glevel_len)
 Finds optimal gap blocks lengths. More...
 
template<typename T , typename Func >
void bm::for_each_gap_blk (const T *buf, bm::id_t offset, 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 1597 of file bmfunc.h.

◆ bit_convert_to_gap()

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

Converts bit block to GAP.

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

Definition at line 2708 of file bmfunc.h.

References BM_ASSERT, BMREGISTER, and BMRESTRICT.

Referenced by bm::serializer< bvector_type >::serialize().

◆ for_each_gap_blk()

template<typename T , typename Func >
void bm::for_each_gap_blk ( const T *  buf,
bm::id_t  offset,
Func &  bit_functor 
)

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

Parameters
block- 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 1696 of file bmalgo_impl.h.

Referenced by bm::for_each_bit().

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

◆ gap_add_to_bitset()

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

Adds(OR) GAP block to bitblock.

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

Definition at line 1932 of file bmfunc.h.

References BM_ASSERT, BMREGISTER, and bm::or_bit_block().

Referenced by bm::gap_convert_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 1452 of file bmfunc.h.

References BM_ASSERT, BMREGISTER, and bm::gap_max_bits.

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

◆ gap_and_to_bitset()

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

ANDs GAP block to bitblock.

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

Definition at line 1964 of file bmfunc.h.

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

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

References BMREGISTER.

Referenced by bm::gap_bit_count_unr().

◆ gap_bit_count_range()

template<typename T >
unsigned bm::gap_bit_count_range ( const T *const  buf,
left,
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 870 of file bmfunc.h.

References BM_ASSERT, and bm::gap_bfind().

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

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

Parameters
buf- GAP buffer pointer.
right-rightmost bit index
Returns
Number of non-zero bits.

Definition at line 911 of file bmfunc.h.

References BM_ASSERT.

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

◆ 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.
dsize- buffer size
Returns
Number of non-zero bits.

Definition at line 804 of file bmfunc.h.

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

Referenced by bm::combine_count_operation_with_block(), bm::bvector<>::combine_operation(), and bm::serializer< bvector_type >::encode_gap_block().

◆ gap_bitset_and_any()

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

Bitcount test of bit block AND masked by GAP block.

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

Definition at line 2030 of file bmfunc.h.

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

Referenced by bm::combine_any_operation_with_block().

◆ gap_bitset_and_count()

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

Compute bitcount of bit block AND masked by GAP block.

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

Definition at line 1998 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 *  block,
const T *  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 2274 of file bmfunc.h.

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

Referenced by bm::combine_any_operation_with_block().

◆ gap_bitset_or_count()

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

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

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

Referenced by bm::combine_count_operation_with_block().

◆ gap_bitset_sub_any()

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

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

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

Referenced by bm::combine_any_operation_with_block().

◆ gap_bitset_sub_count()

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

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

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

Referenced by bm::combine_count_operation_with_block().

◆ gap_bitset_xor_any()

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

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

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

Referenced by bm::combine_any_operation_with_block().

◆ gap_bitset_xor_count()

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

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

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

Referenced by bm::combine_count_operation_with_block().

◆ 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,
f 
)

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
f- operation functor.
Note
Internal function.
Returns
non zero value if operation result returns any 1 bit

Definition at line 1206 of file bmfunc.h.

References BMREGISTER, and bm::gap_max_bits.

Referenced by bm::gap_operation_any_and(), bm::gap_operation_any_sub(), and bm::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,
f 
)

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.
f- operation functor.
Note
Internal function.

Definition at line 1275 of file bmfunc.h.

References bm::gap_max_bits.

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

◆ gap_calc_level()

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

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

References BM_ASSERT, and bm::gap_levels.

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

◆ gap_capacity()

template<typename T >
unsigned bm::gap_capacity ( const T *  buf,
const T *  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 2578 of file bmfunc.h.

Referenced by bm::bvector<>::calc_stat(), bm::mem_alloc< BA, PA >::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 2402 of file bmfunc.h.

References BM_ASSERT, and BMREGISTER.

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

References BMREGISTER, and BMRESTRICT.

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

◆ gap_convert_to_bitset() [1/2]

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

◆ gap_convert_to_bitset() [2/2]

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

GAP block to bitblock conversion.

Parameters
dest- bitblock buffer pointer.
buf- GAP buffer pointer.
dest_len- length/size of the destination buffer.

Definition at line 2359 of file bmfunc.h.

References bm::gap_add_to_bitset().

◆ gap_convert_to_bitset_smart()

template<typename T >
unsigned* bm::gap_convert_to_bitset_smart ( unsigned *  dest,
const T *  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 2380 of file bmfunc.h.

References FULL_BLOCK_REAL_ADDR, and bm::gap_convert_to_bitset().

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

◆ gap_count_and()

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

GAP bitcount AND operation test.

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

Definition at line 3545 of file bmfunc.h.

References bm::and_op(), BMFORCEINLINE, and bm::gap_buff_count_op().

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

References bm::gap_buff_count_op(), and bm::or_op().

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

References bm::gap_buff_count_op(), and bm::sub_op().

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

References bm::gap_buff_count_op(), and bm::xor_op().

Referenced by bm::combine_count_operation_with_block().

◆ gap_find_in_block()

template<typename T >
int bm::gap_find_in_block ( const T *  buf,
unsigned  nbit,
bm::id_t 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

Definition at line 1627 of file bmfunc.h.

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

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

◆ gap_free_elements()

template<typename T >
unsigned bm::gap_free_elements ( const T *  buf,
const T *  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 2657 of file bmfunc.h.

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

◆ gap_init_range_block()

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

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
set_max- max possible bitset length

Definition at line 2455 of file bmfunc.h.

References BM_ASSERT, and bm::gap_set_all().

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

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

◆ gap_is_all_one()

template<typename T >
bool bm::gap_is_all_one ( const T *  buf,
unsigned  set_max 
)

Checks if GAP block is all-one.

Parameters
buf- GAP buffer pointer.
set_max- max possible bitset length
Returns
true if all-one.

Definition at line 2551 of file bmfunc.h.

◆ gap_is_all_zero()

template<typename T >
bool bm::gap_is_all_zero ( const T *  buf,
unsigned  set_max 
)

Temporary inverts all bits in the GAP buffer.

In this function const-ness of the buffer means nothing. Calling this function again restores the status of the buffer.

Parameters
buf- GAP buffer pointer. (Buffer IS changed)

Checks if GAP block is all-zero.

Parameters
buf- GAP buffer pointer.
set_max- max possible bitset length
Returns
true if all-zero.

Definition at line 2537 of file bmfunc.h.

Referenced by bm::combine_any_operation_with_block(), bm::bvector<>::combine_operation(), and bm::bvector<>::compare().

◆ gap_length()

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

◆ gap_level()

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

Returs GAP blocks capacity level.

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

Definition at line 2606 of file bmfunc.h.

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

◆ gap_limit()

template<typename T >
unsigned bm::gap_limit ( const T *  buf,
const T *  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 2593 of file bmfunc.h.

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

◆ gap_operation_and()

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

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

References bm::and_op(), BMFORCEINLINE, and bm::gap_buff_op().

Referenced by bm::operation_functions< T >::bit_operation_count().

◆ gap_operation_any_and()

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

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

References bm::and_op(), BMFORCEINLINE, and bm::gap_buff_any_op().

Referenced by bm::combine_any_operation_with_block().

◆ gap_operation_any_sub()

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

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

References bm::and_op(), BMFORCEINLINE, and bm::gap_buff_any_op().

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.

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

References BMFORCEINLINE, bm::gap_buff_any_op(), and bm::xor_op().

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

References bm::and_op(), BMFORCEINLINE, bm::gap_buff_op(), and bm::gap_invert().

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

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

References bm::and_op(), BMFORCEINLINE, and bm::gap_buff_op().

Referenced by bm::operation_functions< T >::bit_operation_count().

◆ gap_operation_xor()

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

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

References BMFORCEINLINE, bm::gap_buff_op(), and bm::xor_op().

Referenced by bm::operation_functions< T >::bit_operation_count().

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

References BM_ASSERT.

Referenced by bm::gap_init_range_block(), bm::deseriaizer_base< DEC >::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 1537 of file bmfunc.h.

References bm::gap_max_bits.

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

◆ gap_set_value()

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

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

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

◆ gap_sub_to_bitset()

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

SUB (AND NOT) GAP block to bitblock.

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

Definition at line 1868 of file bmfunc.h.

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

◆ gap_test()

template<typename T >
unsigned bm::gap_test ( const T *  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 481 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 *  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 525 of file bmfunc.h.

References BM_ASSERT, bm::gap_max_bits, bm::gap_test(), bm::sse2_gap_find(), and bm::sse4_gap_find().

Referenced by bm::combine_sub(), bm::combine_xor(), bm::bvector<>::count_to_test(), bm::sparse_vector< unsigned, bm::bvector<> >::extract_range(), bm::sparse_vector< unsigned, bm::bvector<> >::get(), bm::bvector<>::get_bit(), and bm::bvector<>::set_bit_no_check().

◆ gap_xor_to_bitset()

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

XOR GAP block to bitblock.

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

Definition at line 1900 of file bmfunc.h.

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

◆ 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 1057 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 5133 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,
unsigned  level 
)

Sets GAP block capacity level.

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

Definition at line 2620 of file bmfunc.h.

References BM_ASSERT, and bm::gap_levels.

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