Data Structures
struct	bm::gap_len_table< T >
	Default GAP lengths table. More...

struct	bm::gap_len_table_min< T >
	Alternative GAP lengths table. Good for for memory saver mode and very sparse bitsets. More...

struct	bm::gap_len_table_nl< T >
	Non-linear size growth GAP lengths table. More...

Functions
BMFORCEINLINE bool	bm::gap_is_all_zero (const bm::gap_word_t *BMRESTRICT buf) BMNOEXCEPT
	Checks if GAP block is all-zero. More...

BMFORCEINLINE bool	bm::gap_is_all_one (const bm::gap_word_t *BMRESTRICT buf) BMNOEXCEPT
	Checks if GAP block is all-one. More...

BMFORCEINLINE bm::gap_word_t	bm::gap_length (const bm::gap_word_t *BMRESTRICT buf) BMNOEXCEPT
	Returs GAP block length. More...

template<typename T >
unsigned	bm::gap_capacity (const T BMRESTRICT buf, const T BMRESTRICT glevel_len) BMNOEXCEPT
	Returs GAP block capacity. More...

template<typename T >
unsigned	bm::gap_limit (const T BMRESTRICT buf, const T BMRESTRICT glevel_len) BMNOEXCEPT
	Returs GAP block capacity limit. More...

template<typename T >
T	bm::gap_level (const T *BMRESTRICT buf) BMNOEXCEPT
	Returs GAP blocks capacity level. More...

template<typename T >
unsigned	bm::gap_find_last (const T BMRESTRICT buf, unsigned BMRESTRICT last) BMNOEXCEPT
	GAP block find the last set bit. More...

template<typename T >
unsigned	bm::gap_find_first (const T BMRESTRICT buf, unsigned BMRESTRICT first) BMNOEXCEPT
	GAP block find the first set bit. More...

template<typename T >
unsigned	bm::gap_test (const T *BMRESTRICT buf, unsigned pos) BMNOEXCEPT
	Tests if bit = pos is true. More...

template<typename T >
unsigned	bm::gap_test_unr (const T *BMRESTRICT buf, const unsigned pos) BMNOEXCEPT
	Tests if bit = pos is true. Analog of bm::gap_test with SIMD unrolling. More...

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

template<typename T >
unsigned	bm::gap_bit_count (const T *buf, unsigned dsize=0) BMNOEXCEPT
	Calculates number of bits ON in GAP buffer. More...

template<typename T >
unsigned	bm::gap_bit_count_unr (const T *buf) BMNOEXCEPT
	Calculates number of bits ON in GAP buffer. Loop unrolled version. More...

template<typename T , 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. More...

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

template<typename T >
bool	bm::gap_is_all_one_range (const T *const BMRESTRICT buf, unsigned left, unsigned right) BMNOEXCEPT
	Test if all bits are 1 in GAP buffer in the [left, right] range. More...

template<typename T >
bool	bm::gap_any_range (const T *const BMRESTRICT buf, unsigned left, unsigned right) BMNOEXCEPT
	Test if any bits are 1 in GAP buffer in the [left, right] range. More...

template<typename T >
bool	bm::gap_is_interval (const T *const BMRESTRICT buf, unsigned left, unsigned right) BMNOEXCEPT
	Test if any bits are 1 in GAP buffer in the [left, right] range and flanked with 0s. More...

template<typename T >
bool	bm::gap_find_interval_end (const T const BMRESTRICT buf, unsigned nbit, unsigned BMRESTRICT pos) BMNOEXCEPT
	Searches for the last 1 bit in the 111 interval of a GAP block. More...

template<typename T >
bool	bm::gap_find_interval_start (const T const BMRESTRICT buf, unsigned nbit, unsigned BMRESTRICT pos) BMNOEXCEPT
	Searches for the first 1 bit in the 111 interval of a GAP block. More...

template<typename T >
bool	bm::gap_find_prev (const T const BMRESTRICT buf, unsigned nbit, unsigned BMRESTRICT pos) BMNOEXCEPT
	reverse search for the first 1 bit of a GAP block More...

template<typename T , typename SIZE_TYPE >
SIZE_TYPE	bm::gap_find_rank (const T *const block, SIZE_TYPE rank, unsigned nbit_from, unsigned &nbit_pos) BMNOEXCEPT
	GAP block find position for the rank. More...

template<typename T , bool TCORRECT = false>
unsigned	bm::gap_bit_count_to (const T *const buf, T right) BMNOEXCEPT
	Counts 1 bits in GAP buffer in the closed [0, right] range. More...

template<typename T >
int	bm::gapcmp (const T buf1, const T buf2) BMNOEXCEPT
	Lexicographical comparison of GAP buffers. More...

template<typename T >
bool	bm::gap_find_first_diff (const T BMRESTRICT buf1, const T BMRESTRICT buf2, unsigned *BMRESTRICT pos) BMNOEXCEPT
	Find first bit which is different between two GAP-blocks. More...

template<typename T , class F >
unsigned	bm::gap_buff_any_op (const T BMRESTRICT vect1, unsigned vect1_mask, const T BMRESTRICT vect2, unsigned vect2_mask) BMNOEXCEPT2
	Abstract 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) BMNOEXCEPT2
	Abstract distance(similarity) operation for GAP buffers. Receives functor F as a template argument. More...

template<typename T >
unsigned	bm::gap_set_value (unsigned val, T BMRESTRICT buf, unsigned pos, unsigned BMRESTRICT is_set) BMNOEXCEPT
	Sets or clears bit in the GAP buffer. More...

template<typename T >
unsigned	bm::gap_set_value (unsigned val, T *BMRESTRICT buf, unsigned pos) BMNOEXCEPT
	Sets or clears bit in the GAP buffer. More...

template<typename T >
unsigned	bm::gap_add_value (T *buf, unsigned pos) BMNOEXCEPT
	Add new value to the end of GAP buffer. More...

template<typename T >
bool	bm::gap_shift_r1 (T BMRESTRICT buf, unsigned co_flag, unsigned BMRESTRICT new_len) BMNOEXCEPT
	Right shift GAP block by 1 bit. More...

template<typename T >
bool	bm::gap_insert (T BMRESTRICT buf, unsigned pos, unsigned val, unsigned BMRESTRICT new_len) BMNOEXCEPT
	isnert bit into GAP compressed block More...

template<typename T >
bool	bm::gap_shift_l1 (T BMRESTRICT buf, unsigned co_flag, unsigned BMRESTRICT new_len) BMNOEXCEPT
	Left shift GAP block by 1 bit. More...

template<typename T >
unsigned	bm::gap_set_array (T buf, const T arr, unsigned len) BMNOEXCEPT
	Convert array to GAP buffer. More...

template<typename T >
unsigned	bm::bit_array_compute_gaps (const T *arr, unsigned len) BMNOEXCEPT
	Compute number of GAPs in bit-array. More...

template<typename T >
unsigned	bm::gap_block_find (const T BMRESTRICT buf, unsigned nbit, bm::id_t BMRESTRICT prev) BMNOEXCEPT
	Searches for the next 1 bit in the GAP block. More...

template<typename T >
void	bm::gap_sub_to_bitset (unsigned BMRESTRICT dest, const T BMRESTRICT pcurr) BMNOEXCEPT
	SUB (AND NOT) GAP block to bitblock. More...

template<typename T >
void	bm::gap_sub_to_bitset (unsigned BMRESTRICT dest, const T BMRESTRICT pcurr, bm::id64_t digest0) BMNOEXCEPT
	SUB (AND NOT) GAP block to bitblock with digest assist. More...

template<typename T >
void	bm::gap_xor_to_bitset (unsigned BMRESTRICT dest, const T BMRESTRICT pcurr) BMNOEXCEPT
	XOR GAP block to bitblock. More...

template<typename T >
void	bm::gap_add_to_bitset (unsigned BMRESTRICT dest, const T BMRESTRICT pcurr, unsigned len) BMNOEXCEPT
	Adds(OR) GAP block to bitblock. More...

template<typename T >
void	bm::gap_add_to_bitset (unsigned BMRESTRICT dest, const T BMRESTRICT pcurr) BMNOEXCEPT
	Adds(OR) GAP block to bitblock. More...

template<typename T >
void	bm::gap_and_to_bitset (unsigned BMRESTRICT dest, const T BMRESTRICT pcurr) BMNOEXCEPT
	ANDs GAP block to bitblock. More...

template<typename T >
void	bm::gap_and_to_bitset (unsigned BMRESTRICT dest, const T BMRESTRICT pcurr, bm::id64_t digest0) BMNOEXCEPT
	ANDs GAP block to bitblock with digest assist. More...

template<typename T >
bm::id_t	bm::gap_bitset_and_count (const unsigned BMRESTRICT block, const T BMRESTRICT pcurr) BMNOEXCEPT
	Compute bitcount of bit block AND masked by GAP block. More...

template<typename T >
bm::id_t	bm::gap_bitset_and_any (const unsigned BMRESTRICT block, const T BMRESTRICT pcurr) BMNOEXCEPT
	Bitcount test of bit block AND masked by GAP block. More...

template<typename T >
bm::id_t	bm::gap_bitset_sub_count (const unsigned BMRESTRICT block, const T BMRESTRICT buf) BMNOEXCEPT
	Compute bitcount of bit block SUB masked by GAP block. More...

template<typename T >
bm::id_t	bm::gap_bitset_sub_any (const unsigned BMRESTRICT block, const T BMRESTRICT buf) BMNOEXCEPT
	Compute bitcount test of bit block SUB masked by GAP block. More...

template<typename T >
bm::id_t	bm::gap_bitset_xor_count (const unsigned BMRESTRICT block, const T BMRESTRICT buf) BMNOEXCEPT
	Compute bitcount of bit block XOR masked by GAP block. More...

template<typename T >
bm::id_t	bm::gap_bitset_xor_any (const unsigned BMRESTRICT block, const T BMRESTRICT buf) BMNOEXCEPT
	Compute bitcount test of bit block XOR masked by GAP block. More...

template<typename T >
bm::id_t	bm::gap_bitset_or_count (const unsigned BMRESTRICT block, const T BMRESTRICT buf) BMNOEXCEPT
	Compute bitcount of bit block OR masked by GAP block. More...

template<typename T >
bm::id_t	bm::gap_bitset_or_any (const unsigned BMRESTRICT block, const T BMRESTRICT buf) BMNOEXCEPT
	Compute bitcount test of bit block OR masked by GAP block. More...

template<typename T >
void	bm::gap_convert_to_bitset (unsigned BMRESTRICT dest, const T BMRESTRICT buf, unsigned len=0) BMNOEXCEPT
	GAP block to bitblock conversion. More...

template<typename T >
unsigned *	bm::gap_convert_to_bitset_smart (unsigned BMRESTRICT dest, const T BMRESTRICT buf, id_t set_max) BMNOEXCEPT
	Smart GAP block to bitblock conversion. More...

template<typename T >
unsigned	bm::gap_control_sum (const T *buf) BMNOEXCEPT
	Calculates sum of all words in GAP block. (For debugging purposes) More...

template<class T >
void	bm::gap_set_all (T *buf, unsigned set_max, unsigned value) BMNOEXCEPT
	Sets all bits to 0 or 1 (GAP) More...

template<class T >
void	bm::gap_init_range_block (T *buf, T from, T to, T value) BMNOEXCEPT
	Init gap block so it has block in it (can be whole block) More...

template<typename T >
void	bm::gap_invert (T *buf) BMNOEXCEPT
	Inverts all bits in the GAP buffer. More...

template<typename T >
void	bm::set_gap_level (T *buf, int level) BMNOEXCEPT
	Sets GAP block capacity level. More...

template<typename T >
int	bm::gap_calc_level (unsigned len, const T *glevel_len) BMNOEXCEPT
	Calculates GAP block capacity level. More...

template<typename T >
unsigned	bm::gap_free_elements (const T BMRESTRICT buf, const T BMRESTRICT glevel_len) BMNOEXCEPT
	Returns number of free elements in GAP block array. Difference between GAP block capacity on this level and actual GAP length. More...

unsigned	bm::bit_block_to_gap (gap_word_t BMRESTRICT dest, const unsigned BMRESTRICT block, unsigned dest_len) BMNOEXCEPT
	Converts bit block to GAP. More...

template<class T , class F >
void	bm::for_each_gap_dbit (const T *buf, F &func)
	Iterate gap block as delta-bits with a functor. More...

template<typename D , typename T >
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. More...

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

unsigned	bm::gap_operation_any_and (const gap_word_t BMRESTRICT vect1, const gap_word_t BMRESTRICT vect2) BMNOEXCEPT
	GAP AND operation test. More...

unsigned	bm::gap_count_and (const gap_word_t BMRESTRICT vect1, const gap_word_t BMRESTRICT vect2) BMNOEXCEPT
	GAP bitcount AND operation test. More...

gap_word_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. More...

BMFORCEINLINE unsigned	bm::gap_operation_any_xor (const gap_word_t BMRESTRICT vect1, const gap_word_t BMRESTRICT vect2) BMNOEXCEPT
	GAP XOR operation test. More...

BMFORCEINLINE unsigned	bm::gap_count_xor (const gap_word_t BMRESTRICT vect1, const gap_word_t BMRESTRICT vect2) BMNOEXCEPT
	GAP bitcount XOR operation test. More...

gap_word_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. More...

BMFORCEINLINE unsigned	bm::gap_count_or (const gap_word_t BMRESTRICT vect1, const gap_word_t BMRESTRICT vect2) BMNOEXCEPT
	GAP bitcount OR operation test. More...

gap_word_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. More...

unsigned	bm::gap_operation_any_sub (const gap_word_t BMRESTRICT vect1, const gap_word_t BMRESTRICT vect2) BMNOEXCEPT
	GAP SUB operation test. More...

BMFORCEINLINE unsigned	bm::gap_count_sub (const gap_word_t BMRESTRICT vect1, const gap_word_t BMRESTRICT vect2) BMNOEXCEPT
	GAP bitcount SUB (AND NOT) operation test. More...

template<typename T >
unsigned	bm::gap_overhead (const T length, const T length_end, const T *glevel_len) BMNOEXCEPT
	Calculates memory overhead for number of gap blocks sharing the same memory allocation table (level lengths table). More...

template<typename T >
bool	bm::improve_gap_levels (const T length, const T length_end, T *glevel_len) BMNOEXCEPT
	Finds optimal gap blocks lengths. More...

template<typename T , typename Func , typename SIZE_TYPE >
int	bm::for_each_gap_blk (const T *buf, SIZE_TYPE offset, Func &bit_functor)
	for-each visitor, calls a special visitor functor for each 1 bit range More...

template<typename T , typename Func , typename SIZE_TYPE >
int	bm::for_each_gap_blk_range (const T *BMRESTRICT buf, SIZE_TYPE offset, unsigned left, unsigned right, Func &bit_functor)
	for-each visitor, calls a special visitor functor for each 1 bit range More...

Detailed Description

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

Function Documentation

◆ bit_array_compute_gaps()

template<typename T >

unsigned bm::bit_array_compute_gaps	(	const T *	arr,
		unsigned	len
	)

Compute number of GAPs in bit-array.

Parameters

arr	- array of BITs
len	- array length

Definition at line 3644 of file bmfunc.h.

◆ bit_block_to_gap()

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

inline

Converts bit block to GAP.

Parameters

dest	- Destinatio GAP buffer.
block	- Source bitblock buffer.
dest_len	- length of the destination buffer.

Returns: New length of GAP block or 0 if conversion failed (insufficicent space).

Definition at line 4751 of file bmfunc.h.

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

Referenced by bm::bit_to_gap().

◆ for_each_gap_blk()

template<typename T , typename Func , typename SIZE_TYPE >

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 bm::for_each_bit_block_range().

◆ for_each_gap_blk_range()

template<typename T , typename Func , typename SIZE_TYPE >

int bm::for_each_gap_blk_range	(	const T *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 bm::bits_in_block, BM_ASSERT, BMRESTRICT, and bm::gap_bfind().

Referenced by bm::for_each_bit_range_no_check().

◆ for_each_gap_dbit()

template<class T , class F >

void bm::for_each_gap_dbit	(	const T *	buf,
		F &	func
	)

Iterate gap block as delta-bits with a functor.

Definition at line 4853 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 4051 of file bmfunc.h.

References bm::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 4016 of file bmfunc.h.

References BM_ASSERT, and bm::or_bit_block().

Referenced by bm::bvector< Alloc >::combine_operation_block_and_or(), bm::bvector< Alloc >::combine_operation_block_or(), bm::aggregator< BV >::combine_shift_right_and(), bm::gap_add_to_bitset(), bm::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 3343 of file bmfunc.h.

References BM_ASSERT, and bm::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 4067 of file bmfunc.h.

References BM_ASSERT, and bm::sub_bit_block().

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

◆ gap_and_to_bitset() [2/2]

template<typename T >

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

ANDs GAP block to bitblock with digest assist.

Parameters

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

Definition at line 4102 of file bmfunc.h.

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

◆ gap_any_range()

template<typename T >

bool bm::gap_any_range	(	const T *const BMRESTRICT	buf,
		unsigned	left,
		unsigned	right
	)

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

Parameters

buf	- GAP buffer pointer.
left	- leftmost bit index to start from
right-	rightmost bit index

Returns: true if at least 1 "00010"

Definition at line 2466 of file bmfunc.h.

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

Referenced by bm::block_any_range().

◆ gap_bit_count()

template<typename T >

unsigned bm::gap_bit_count	(	const T *	buf,
		unsigned	dsize = `0`
	)

Calculates number of bits ON in GAP buffer.

Parameters

buf	- GAP buffer pointer.
dsize	- buffer size

Returns: Number of non-zero bits.

Definition at line 2259 of file bmfunc.h.

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

References BM_ASSERT, bm::gap_bfind(), and bm::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 2401 of file bmfunc.h.

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

◆ gap_bit_count_to()

template<typename T , bool TCORRECT = false>

unsigned bm::gap_bit_count_to	(	const T *const	buf,
		T	right
	)

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

Parameters

buf	- GAP buffer pointer.
right-	rightmost bit index
is_corrected	- if true the result will be rank corrected if right bit == true count=count-1

Returns: Number of non-zero bits

Definition at line 2703 of file bmfunc.h.

References BM_ASSERT, and bm::gap_max_bits.

Referenced by bm::bvector< Alloc >::build_rs_index(), bm::bvector< Alloc >::count_range_no_check(), and bm::bvector< Alloc >::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.

Returns: Number of non-zero bits.

Definition at line 2287 of file bmfunc.h.

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

Referenced by bm::combine_count_operation_with_block(), 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 4192 of file bmfunc.h.

References bm::bit_block_any_range(), and BM_ASSERT.

Referenced by bm::combine_any_operation_with_block().

◆ gap_bitset_and_count()

template<typename T >

bm::id_t bm::gap_bitset_and_count	(	const unsigned *BMRESTRICT	block,
		const T *BMRESTRICT	pcurr
	)

Compute bitcount of bit block AND masked by GAP block.

Parameters

block	- bitblock buffer pointer
pcurr	- GAP buffer pointer

Returns: bitcount - cardinality of the AND product

Definition at line 4164 of file bmfunc.h.

References bm::bit_block_calc_count_range(), and BM_ASSERT.

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

◆ gap_bitset_or_any()

template<typename T >

bm::id_t bm::gap_bitset_or_any	(	const unsigned *BMRESTRICT	block,
		const T *BMRESTRICT	buf
	)

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

Parameters

block	- bitblock buffer pointer
buf	- GAP buffer pointer

Returns: non zero value if union (OR) returns anything

Definition at line 4403 of file bmfunc.h.

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

Referenced by bm::combine_any_operation_with_block().

◆ gap_bitset_or_count()

template<typename T >

bm::id_t bm::gap_bitset_or_count	(	const unsigned *BMRESTRICT	block,
		const T *BMRESTRICT	buf
	)

Compute bitcount of bit block OR masked by GAP block.

Parameters

block	- bitblock buffer pointer.
buf	- GAP buffer pointer.

Returns: bit count of OR

Definition at line 4371 of file bmfunc.h.

References bm::bit_block_calc_count_range(), and BM_ASSERT.

Referenced by bm::combine_count_operation_with_block().

◆ gap_bitset_sub_any()

template<typename T >

bm::id_t bm::gap_bitset_sub_any	(	const unsigned *BMRESTRICT	block,
		const T *BMRESTRICT	buf
	)

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

Parameters

block	- bitblock buffer pointer
buf	- GAP buffer pointer

Returns: non-zero value if AND NOT produces any 1 bits

Definition at line 4257 of file bmfunc.h.

References bm::bit_block_any_range(), and BM_ASSERT.

Referenced by bm::combine_any_operation_with_block().

◆ gap_bitset_sub_count()

template<typename T >

bm::id_t bm::gap_bitset_sub_count	(	const unsigned *BMRESTRICT	block,
		const T *BMRESTRICT	buf
	)

Compute bitcount of bit block SUB masked by GAP block.

Parameters

block	- bitblock buffer pointer.
buf	- GAP buffer pointer.

Returns: bit-count result of AND NOT operation

Definition at line 4222 of file bmfunc.h.

References bm::bit_block_calc_count_range(), and BM_ASSERT.

Referenced by bm::combine_count_operation_with_block().

◆ gap_bitset_xor_any()

template<typename T >

bm::id_t bm::gap_bitset_xor_any	(	const unsigned *BMRESTRICT	block,
		const T *BMRESTRICT	buf
	)

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

Parameters

block	- bitblock buffer pointer
buf	- GAP buffer pointer

Returns: non-zero value if XOR returns anything

Definition at line 4333 of file bmfunc.h.

References bm::bit_block_any_range(), and BM_ASSERT.

Referenced by bm::combine_any_operation_with_block().

◆ gap_bitset_xor_count()

template<typename T >

bm::id_t bm::gap_bitset_xor_count	(	const unsigned *BMRESTRICT	block,
		const T *BMRESTRICT	buf
	)

Compute bitcount of bit block XOR masked by GAP block.

Parameters

block	- bitblock buffer pointer
buf	- GAP buffer pointer

Returns: bit count value of XOR operation

Definition at line 4295 of file bmfunc.h.

References bm::bit_block_calc_count_range(), and BM_ASSERT.

Referenced by bm::combine_count_operation_with_block().

◆ gap_block_find()

template<typename T >

unsigned bm::gap_block_find	(	const T *BMRESTRICT	buf,
		unsigned	nbit,
		bm::id_t *BMRESTRICT	prev
	)

Searches for the next 1 bit in the GAP block.

Parameters

buf	- GAP buffer
nbit	- bit index to start checking from.
prev	- returns previously checked value

Returns: 0 if not found

Definition at line 3676 of file bmfunc.h.

References BM_ASSERT, bm::gap_bfind(), and bm::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 3026 of file bmfunc.h.

References bm::gap_max_bits.

◆ gap_buff_count_op()

template<typename T , class F >

unsigned bm::gap_buff_count_op	(	const T *	vect1,
		const T *	vect2
	)

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

Parameters

vect1	- operand 1 GAP encoded buffer.
vect2	- operand 2 GAP encoded buffer.

Note: Internal function.

Definition at line 3091 of file bmfunc.h.

References bm::gap_max_bits.

◆ gap_calc_level()

template<typename T >

int bm::gap_calc_level	(	unsigned	len,
		const T *	glevel_len
	)

Calculates GAP block capacity level.

Parameters

len	- GAP buffer length.
glevel_len	- GAP lengths table

Returns: GAP block capacity level. -1 if block does not fit any level.

Definition at line 4627 of file bmfunc.h.

References BM_ASSERT, and bm::gap_levels.

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

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

◆ gap_control_sum()

template<typename T >

unsigned bm::gap_control_sum ( const T * buf )

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

Note: For debugging and testing ONLY.

Parameters

buf	- GAP buffer pointer.

Returns: Sum of all words.

Definition at line 4487 of file bmfunc.h.

References BM_ASSERT.

◆ gap_convert_to_arr()

template<typename D , typename T >

D bm::gap_convert_to_arr	(	D *BMRESTRICT	dest,
		const T *BMRESTRICT	buf,
		unsigned	dest_len,
		bool	invert = `false`
	)

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

Definition at line 4908 of file bmfunc.h.

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

References bm::bit_block_set(), bm::gap_add_to_bitset(), and bm::gap_length().

Referenced by bm::block_find_first_diff(), bm::aggregator< BV >::cache_gap_block(), bm::combine_any_operation_with_block(), bm::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(), bm::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 4466 of file bmfunc.h.

References FULL_BLOCK_REAL_ADDR, and bm::gap_convert_to_bitset().

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

◆ gap_count_and()

unsigned bm::gap_count_and	(	const gap_word_t *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 6526 of file bmfunc.h.

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

◆ gap_count_or()

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

GAP bitcount OR operation test.

Parameters

vect1	- operand 1
vect2	- operand 2

Returns: bitcount of vect1 OR vect2

Definition at line 6652 of file bmfunc.h.

Referenced by bm::combine_count_operation_with_block().

◆ gap_count_sub()

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

GAP bitcount SUB (AND NOT) operation test.

Parameters

vect1	- operand 1
vect2	- operand 2

Returns: bitcount of vect1 SUB (AND NOT) vect2

Definition at line 6723 of file bmfunc.h.

Referenced by bm::combine_count_operation_with_block().

◆ gap_count_xor()

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

GAP bitcount XOR operation test.

Parameters

vect1	- operand 1
vect2	- operand 2

Returns: bitcount of vect1 XOR vect2

Definition at line 6607 of file bmfunc.h.

Referenced by bm::combine_count_operation_with_block().

◆ gap_find_first()

template<typename T >

unsigned bm::gap_find_first	(	const T *BMRESTRICT	buf,
		unsigned *BMRESTRICT	first
	)

GAP block find the first set bit.

Parameters

buf	- GAP buffer pointer.
first	- index of the first 1 bit

Returns: 0 if 1 bit was NOT found

Definition at line 1670 of file bmfunc.h.

References BM_ASSERT, and bm::gap_max_bits.

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

◆ gap_find_first_diff()

template<typename T >

bool bm::gap_find_first_diff	(	const T *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 2911 of file bmfunc.h.

References BM_ASSERT.

Referenced by bm::block_find_first_diff().

◆ gap_find_interval_end()

template<typename T >

bool bm::gap_find_interval_end	(	const T *const BMRESTRICT	buf,
		unsigned	nbit,
		unsigned *BMRESTRICT	pos
	)

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

Parameters

buf	- BIT block buffer
nbit	- bit index to start checking from
pos	- [out] found value

Returns: false if not found

Definition at line 2524 of file bmfunc.h.

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

Referenced by bm::block_find_interval_end().

◆ gap_find_interval_start()

template<typename T >

bool bm::gap_find_interval_start	(	const T *const BMRESTRICT	buf,
		unsigned	nbit,
		unsigned *BMRESTRICT	pos
	)

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

Parameters

buf	- GAP block buffer
nbit	- bit index to start checking from
pos	- [out] found value

Returns: false if not found

Definition at line 2549 of file bmfunc.h.

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

Referenced by bm::block_find_interval_start().

◆ gap_find_last()

template<typename T >

unsigned bm::gap_find_last	(	const T *BMRESTRICT	buf,
		unsigned *BMRESTRICT	last
	)

GAP block find the last set bit.

Parameters

buf	- GAP buffer pointer.
last	- index of the last 1 bit

Returns: 0 if 1 bit was NOT found

Definition at line 1639 of file bmfunc.h.

References BM_ASSERT, and bm::gap_max_bits.

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

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

Referenced by bm::block_find_reverse().

◆ gap_find_rank()

template<typename T , typename SIZE_TYPE >

SIZE_TYPE bm::gap_find_rank	(	const T *const	block,
		SIZE_TYPE	rank,
		unsigned	nbit_from,
		unsigned &	nbit_pos
	)

GAP block find position for the rank.

Parameters

block	- bit block buffer pointer
rank	- rank to find (must be > 0)
nbit_from	- start bit position in block
nbit_pos	- found position

Returns: 0 if position with rank was found, or the remaining rank (rank - population count)

Definition at line 2614 of file bmfunc.h.

References BM_ASSERT, and bm::gap_bfind().

Referenced by bm::block_find_rank().

◆ gap_free_elements()

template<typename T >

unsigned bm::gap_free_elements	(	const T *BMRESTRICT	buf,
		const T *BMRESTRICT	glevel_len
	)

inline

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

Parameters

buf	- GAP buffer pointer
glevel_len	- GAP lengths table

Returns: Number of free GAP elements

Definition at line 4648 of file bmfunc.h.

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

◆ gap_init_range_block()

template<class T >

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

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

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

References BM_ASSERT, bm::gap_bfind(), bm::gap_max_bits, and bm::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 4586 of file bmfunc.h.

Referenced by bm::bvector< Alloc >::combine_operation_block_xor(), bm::deserializer< BV, DEC >::deserialize_gap(), bm::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 1562 of file bmfunc.h.

References bm::gap_max_bits.

Referenced by bm::check_block_one().

◆ gap_is_all_one_range()

template<typename T >

bool bm::gap_is_all_one_range	(	const T *const BMRESTRICT	buf,
		unsigned	left,
		unsigned	right
	)

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

Parameters

buf	- GAP buffer pointer.
left	- leftmost bit index to start from
right-	rightmost bit index

Returns: true if all bits are "11111"

Definition at line 2443 of file bmfunc.h.

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

Referenced by bm::block_is_all_one_range().

◆ gap_is_all_zero()

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

Checks if GAP block is all-zero.

Parameters

buf	- GAP buffer pointer.

Returns: true if all-zero.

Definition at line 1549 of file bmfunc.h.

References bm::gap_max_bits.

Referenced by bm::block_any(), bm::check_block_zero(), bm::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 bm::gap_bitset_or_any().

◆ gap_is_interval()

template<typename T >

bool bm::gap_is_interval	(	const T *const BMRESTRICT	buf,
		unsigned	left,
		unsigned	right
	)

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

Parameters

buf	- GAP buffer pointer.
left	- leftmost bit index to start from
right-	rightmost bit index

Returns: true if "011110"

Definition at line 2495 of file bmfunc.h.

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

Referenced by bm::block_is_interval().

◆ gap_length()

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

Returs GAP block length.

Parameters

buf	- GAP buffer pointer.

Returns: GAP block length.

Definition at line 1575 of file bmfunc.h.

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(), bm::gap_convert_to_bitset(), bm::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::aggregator< BV >::sort_input_blocks_and().

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

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

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

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

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

Referenced by bm::combine_any_operation_with_block().

◆ gap_operation_any_sub()

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

inline

GAP SUB operation test.

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

Parameters

vect1	- operand 1
vect2	- operand 2

Returns: non zero value if operation returns any 1 bit

Definition at line 6704 of file bmfunc.h.

Referenced by bm::combine_any_operation_with_block().

◆ gap_operation_any_xor()

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

GAP XOR operation test.

Light weight gap_operation_xor for len prediction

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

Parameters

vect1	- operand 1
vect2	- operand 2

Returns: non zero value if operation returns any 1 bit

Definition at line 6591 of file bmfunc.h.

Referenced by bm::combine_any_operation_with_block().

◆ gap_operation_or()

gap_word_t* bm::gap_operation_or	(	const gap_word_t *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 6632 of file bmfunc.h.

References bm::gap_invert().

Referenced by bm::combine_any_operation_with_block(), 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 6678 of file bmfunc.h.

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

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

References BM_ASSERT.

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

References BM_ASSERT, and bm::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 3263 of file bmfunc.h.

References BM_ASSERT, bm::gap_bfind(), and bm::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 3173 of file bmfunc.h.

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

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

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

References BM_ASSERT, bm::gap_max_bits, and bm::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 3413 of file bmfunc.h.

References BM_ASSERT, bm::gap_max_bits, and bm::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 2199 of file bmfunc.h.

◆ gap_sub_to_bitset() [1/2]

template<typename T >

void bm::gap_sub_to_bitset	(	unsigned *BMRESTRICT	dest,
		const T *BMRESTRICT	pcurr
	)

SUB (AND NOT) GAP block to bitblock.

Parameters

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

Definition at line 3900 of file bmfunc.h.

References BM_ASSERT, and bm::sub_bit_block().

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

◆ gap_sub_to_bitset() [2/2]

template<typename T >

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

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

Parameters

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

Definition at line 3929 of file bmfunc.h.

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

◆ gap_test()

template<typename T >

unsigned bm::gap_test	(	const T *BMRESTRICT	buf,
		unsigned	pos
	)

Tests if bit = pos is true.

Parameters

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

Returns: true if position is in "1" gap

Definition at line 1741 of file bmfunc.h.

References BM_ASSERT, and bm::gap_max_bits.

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

◆ gap_test_unr()

template<typename T >

unsigned bm::gap_test_unr	(	const T *BMRESTRICT	buf,
		const unsigned	pos
	)

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

References bm::avx2_gap_test(), BM_ASSERT, bm::gap_max_bits, bm::gap_test(), bm::sse2_gap_test(), and bm::sse42_gap_test().

Referenced by bm::bvector< Alloc >::and_bit_no_check(), bm::combine_sub(), bm::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::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 3988 of file bmfunc.h.

References BM_ASSERT, and bm::xor_bit_block().

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

◆ gapcmp()

template<typename T >

int bm::gapcmp	(	const T *	buf1,
		const T *	buf2
	)

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

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

References BM_ASSERT, bm::gap_levels, bm::gap_max_buff_len, and bm::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 4605 of file bmfunc.h.

References BM_ASSERT, and bm::gap_levels.

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

Data Structures

Functions

Detailed Description

Function Documentation

◆ bit_array_compute_gaps()

◆ bit_block_to_gap()

◆ for_each_gap_blk()

◆ for_each_gap_blk_range()

◆ for_each_gap_dbit()

◆ gap_add_to_bitset() [1/2]

◆ gap_add_to_bitset() [2/2]

◆ gap_add_value()

◆ gap_and_to_bitset() [1/2]

◆ gap_and_to_bitset() [2/2]

◆ gap_any_range()

◆ gap_bit_count()

◆ gap_bit_count_range()

◆ gap_bit_count_range_hint()

◆ gap_bit_count_to()

◆ gap_bit_count_unr()

◆ gap_bitset_and_any()

◆ gap_bitset_and_count()

◆ gap_bitset_or_any()

◆ gap_bitset_or_count()

◆ gap_bitset_sub_any()

◆ gap_bitset_sub_count()

◆ gap_bitset_xor_any()

◆ gap_bitset_xor_count()

◆ gap_block_find()

◆ gap_buff_any_op()

◆ gap_buff_count_op()

◆ gap_calc_level()

◆ gap_capacity()

◆ gap_control_sum()

◆ gap_convert_to_arr()

◆ gap_convert_to_bitset()

◆ gap_convert_to_bitset_smart()

◆ gap_count_and()

◆ gap_count_or()

◆ gap_count_sub()

◆ gap_count_xor()

◆ gap_find_first()

◆ gap_find_first_diff()

◆ gap_find_interval_end()

◆ gap_find_interval_start()

◆ gap_find_last()

◆ gap_find_prev()

◆ gap_find_rank()

◆ gap_free_elements()

◆ gap_init_range_block()

◆ gap_insert()

◆ gap_invert()

◆ gap_is_all_one()

◆ gap_is_all_one_range()

◆ gap_is_all_zero()

◆ gap_is_interval()

◆ gap_length()

◆ gap_level()

◆ gap_limit()

◆ gap_operation_and()

◆ gap_operation_any_and()

◆ gap_operation_any_sub()

◆ gap_operation_any_xor()

◆ gap_operation_or()

◆ gap_operation_sub()

◆ gap_operation_xor()

◆ gap_overhead()

◆ gap_set_all()

◆ gap_set_array()

◆ gap_set_value() [1/2]

◆ gap_set_value() [2/2]

◆ gap_shift_l1()

◆ gap_shift_r1()

◆ gap_split()

◆ gap_sub_to_bitset() [1/2]

◆ gap_sub_to_bitset() [2/2]

◆ gap_test()

◆ gap_test_unr()

◆ gap_xor_to_bitset()

◆ gapcmp()