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

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

Detailed Description

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

Function Documentation

◆ bit_array_compute_gaps()

template<typename T>

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

Compute number of GAPs in bit-array.

Parameters

arr	- array of BITs
len	- array length

Definition at line 3662 of file bmfunc.h.

References BMNOEXCEPT.

◆ bit_block_to_gap()

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

inline

Converts bit block to GAP.

Parameters

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

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

Definition at line 4785 of file bmfunc.h.

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

Referenced by bit_to_gap().

◆ for_each_gap_blk()

template<typename T, typename Func, typename SIZE_TYPE>

int bm::for_each_gap_blk	(	const T *	buf,
		SIZE_TYPE	offset,
		Func &	bit_functor )

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

Parameters

buf	- bit block buffer pointer
offset	- global block offset (number of bits)
bit_functor	- functor must support .add_range(offset, bits_ptr, size)

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

Definition at line 1760 of file bmalgo_impl.h.

Referenced by for_each_bit_block_range().

◆ for_each_gap_blk_range()

template<typename T, typename Func, typename SIZE_TYPE>

int bm::for_each_gap_blk_range	(	const T *BMRESTRICT	buf,
		SIZE_TYPE	offset,
		unsigned	left,
		unsigned	right,
		Func &	bit_functor )

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

Parameters

buf	- bit block buffer pointer
offset	- global block offset (number of bits)
left	- interval start [left..right]
right	- intreval end [left..right]
bit_functor	- functor must support .add_range(offset, bits_ptr, size)

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

Definition at line 1795 of file bmalgo_impl.h.

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

Referenced by for_each_bit_range_no_check().

◆ for_each_gap_dbit()

template<class T, class F>

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

Iterate gap block as delta-bits with a functor.

Definition at line 4887 of file bmfunc.h.

◆ gap_add_to_bitset() [1/2]

template<typename T>

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

Adds(OR) GAP block to bitblock.

Parameters

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

Definition at line 4074 of file bmfunc.h.

References BMNOEXCEPT, BMRESTRICT, and gap_add_to_bitset().

◆ gap_add_to_bitset() [2/2]

template<typename T>

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

Adds(OR) GAP block to bitblock.

Parameters

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

Definition at line 4039 of file bmfunc.h.

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

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

◆ gap_add_value()

template<typename T>

unsigned bm::gap_add_value	(	T *	buf,
		unsigned	pos )

Add new value to the end of GAP buffer.

Parameters

buf	- GAP buffer.
pos	- Index of bit to set.

Returns: New GAP buffer length.

Definition at line 3361 of file bmfunc.h.

References BM_ASSERT, BMNOEXCEPT, and gap_max_bits.

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

◆ gap_and_to_bitset() [1/2]

template<typename T>

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

ANDs GAP block to bitblock.

Parameters

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

Definition at line 4090 of file bmfunc.h.

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

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

◆ gap_and_to_bitset() [2/2]

template<typename T>

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

ANDs GAP block to bitblock with digest assist.

Parameters

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

Returns: new digest

Definition at line 4127 of file bmfunc.h.

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

◆ gap_any_range()

template<typename T>

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

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

Parameters

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

Returns: true if at least 1 "00010"

Definition at line 2506 of file bmfunc.h.

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

Referenced by block_any_range().

◆ gap_bit_count()

template<typename T>

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

Calculates number of bits ON in GAP buffer.

Parameters

buf	- GAP buffer pointer.
dsize	- buffer size

Returns: Number of non-zero bits.

Definition at line 2299 of file bmfunc.h.

References BMNOEXCEPT.

Referenced by gap_bit_count_unr().

◆ gap_bit_count_range()

template<typename T, bool RIGHT_END = false>

unsigned bm::gap_bit_count_range	(	const T *const	buf,
		unsigned	left,
		unsigned	right )

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

Parameters

buf	- GAP buffer pointer.
left	- leftmost bit index to start from
right	- rightmost bit index
pos	- position in the

Returns: Number of non-zero bits.

Definition at line 2393 of file bmfunc.h.

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

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

◆ gap_bit_count_range_hint()

template<typename T>

unsigned bm::gap_bit_count_range_hint	(	const T *const	buf,
		unsigned	left,
		unsigned	right,
		unsigned	hint )

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

Parameters

buf	- GAP buffer pointer.
left	- leftmost bit index to start from
right	- rightmost bit index
pos	- position in the
hint	- position hint

Returns: Number of non-zero bits.

Definition at line 2441 of file bmfunc.h.

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

◆ gap_bit_count_unr()

template<typename T>

unsigned bm::gap_bit_count_unr ( const T * buf )

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

Parameters

buf	- GAP buffer pointer.

Returns: Number of non-zero bits.

Definition at line 2327 of file bmfunc.h.

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

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

◆ gap_bitset_and_any()

template<typename T>

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

Bitcount test of bit block AND masked by GAP block.

Parameters

block	- bitblock buffer pointer
pcurr	- GAP buffer pointer

Returns: non-zero value if AND produces any result

Definition at line 4226 of file bmfunc.h.

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

Referenced by combine_any_operation_with_block().

◆ gap_bitset_and_count()

template<typename T>

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

Compute bitcount of bit block AND masked by GAP block.

Parameters

block	- bitblock buffer pointer
pcurr	- GAP buffer pointer

Returns: bitcount - cardinality of the AND product

Definition at line 4198 of file bmfunc.h.

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

Referenced by combine_count_and_operation_with_block(), and combine_count_operation_with_block().

◆ gap_bitset_or_any()

template<typename T>

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

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

Parameters

block	- bitblock buffer pointer
buf	- GAP buffer pointer

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

Definition at line 4437 of file bmfunc.h.

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

Referenced by combine_any_operation_with_block().

◆ gap_bitset_or_count()

template<typename T>

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

Compute bitcount of bit block OR masked by GAP block.

Parameters

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

Returns: bit count of OR

Definition at line 4405 of file bmfunc.h.

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

Referenced by combine_count_operation_with_block().

◆ gap_bitset_sub_any()

template<typename T>

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

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

Parameters

block	- bitblock buffer pointer
buf	- GAP buffer pointer

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

Definition at line 4291 of file bmfunc.h.

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

Referenced by combine_any_operation_with_block().

◆ gap_bitset_sub_count()

template<typename T>

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

Compute bitcount of bit block SUB masked by GAP block.

Parameters

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

Returns: bit-count result of AND NOT operation

Definition at line 4256 of file bmfunc.h.

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

Referenced by combine_count_operation_with_block().

◆ gap_bitset_xor_any()

template<typename T>

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

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

Parameters

block	- bitblock buffer pointer
buf	- GAP buffer pointer

Returns: non-zero value if XOR returns anything

Definition at line 4367 of file bmfunc.h.

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

Referenced by combine_any_operation_with_block().

◆ gap_bitset_xor_count()

template<typename T>

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

Compute bitcount of bit block XOR masked by GAP block.

Parameters

block	- bitblock buffer pointer
buf	- GAP buffer pointer

Returns: bit count value of XOR operation

Definition at line 4329 of file bmfunc.h.

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

Referenced by combine_count_operation_with_block().

◆ gap_block_find()

template<typename T>

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

Searches for the next 1 bit in the GAP block.

Parameters

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

Returns: 0 if not found

Definition at line 3694 of file bmfunc.h.

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

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

◆ gap_buff_any_op()

template<typename T, class F>

unsigned bm::gap_buff_any_op	(	const T *BMRESTRICT	vect1,
		unsigned	vect1_mask,
		const T *BMRESTRICT	vect2,
		unsigned	vect2_mask )

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

Parameters

vect1	- operand 1 GAP encoded buffer.
vect1_mask	- XOR mask for starting bitflag for vector1 can be 0 or 1 (1 inverts the vector)
vect2	- operand 2 GAP encoded buffer.
vect2_mask	- same as vect1_mask

Note: Internal function.

Returns: non zero value if operation result returns any 1 bit

Definition at line 3019 of file bmfunc.h.

References BMNOEXCEPT2, BMRESTRICT, and gap_max_bits.

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

◆ gap_buff_count_op()

template<typename T, class F>

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

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

Parameters

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

Note: Internal function.

Definition at line 3084 of file bmfunc.h.

References BMNOEXCEPT2, and gap_max_bits.

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

◆ gap_calc_level()

template<typename T>

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

Calculates GAP block capacity level.

Parameters

len	- GAP buffer length.
glevel_len	- GAP lengths table

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

Definition at line 4661 of file bmfunc.h.

References BM_ASSERT, BMNOEXCEPT, and gap_levels.

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

◆ gap_capacity()

template<typename T>

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

Returs GAP block capacity.

Parameters

buf	- GAP buffer pointer
glevel_len	- pointer on GAP header word

Returns: GAP block capacity.

Definition at line 1619 of file bmfunc.h.

References BMNOEXCEPT, and BMRESTRICT.

Referenced by bm::bvector< Alloc >::calc_stat(), bm::mem_alloc< block_allocator, ptr_allocator, standard_alloc_pool >::free_gap_block(), and gap_free_elements().

◆ gap_control_sum()

template<typename T>

unsigned bm::gap_control_sum ( const T * buf )

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

Note: For debugging and testing ONLY.

Parameters

buf	- GAP buffer pointer.

Returns: Sum of all words.

Definition at line 4521 of file bmfunc.h.

References BM_ASSERT, and BMNOEXCEPT.

◆ gap_convert_to_arr()

template<typename D, typename T>

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

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

Definition at line 4942 of file bmfunc.h.

References BMNOEXCEPT, and BMRESTRICT.

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

◆ gap_convert_to_bitset()

template<typename T>

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

GAP block to bitblock conversion.

Parameters

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

Definition at line 4475 of file bmfunc.h.

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

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

◆ gap_convert_to_bitset_smart()

template<typename T>

unsigned * bm::gap_convert_to_bitset_smart	(	unsigned *BMRESTRICT	dest,
		const T *BMRESTRICT	buf,
		id_t	set_max )

Smart GAP block to bitblock conversion.

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

Parameters

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

Definition at line 4500 of file bmfunc.h.

References BMNOEXCEPT, BMRESTRICT, FULL_BLOCK_REAL_ADDR, and gap_convert_to_bitset().

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

◆ gap_count_and()

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

inline

GAP bitcount AND operation test.

Parameters

vect1	- operand 1
vect2	- operand 2

Returns: bitcount of vect1 AND vect2

Definition at line 6560 of file bmfunc.h.

References BMNOEXCEPT, BMRESTRICT, and gap_buff_count_op().

Referenced by combine_count_and_operation_with_block(), and combine_count_operation_with_block().

◆ gap_count_or()

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

GAP bitcount OR operation test.

Parameters

vect1	- operand 1
vect2	- operand 2

Returns: bitcount of vect1 OR vect2

Definition at line 6686 of file bmfunc.h.

References BMNOEXCEPT, BMRESTRICT, and gap_buff_count_op().

Referenced by combine_count_operation_with_block().

◆ gap_count_sub()

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

GAP bitcount SUB (AND NOT) operation test.

Parameters

vect1	- operand 1
vect2	- operand 2

Returns: bitcount of vect1 SUB (AND NOT) vect2

Definition at line 6757 of file bmfunc.h.

References BMNOEXCEPT, BMRESTRICT, and gap_buff_count_op().

Referenced by combine_count_operation_with_block().

◆ gap_count_xor()

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

GAP bitcount XOR operation test.

Parameters

vect1	- operand 1
vect2	- operand 2

Returns: bitcount of vect1 XOR vect2

Definition at line 6641 of file bmfunc.h.

References BMNOEXCEPT, BMRESTRICT, and gap_buff_count_op().

Referenced by combine_count_operation_with_block().

◆ gap_find_first()

template<typename T>

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

GAP block find the first set bit.

Parameters

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

Returns: 0 if 1 bit was NOT found

Definition at line 1698 of file bmfunc.h.

References BM_ASSERT, BMNOEXCEPT, BMRESTRICT, and gap_max_bits.

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

◆ gap_find_first_diff()

template<typename T>

bool bm::gap_find_first_diff	(	const T *BMRESTRICT	buf1,
		const T *BMRESTRICT	buf2,
		unsigned *BMRESTRICT	pos )

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

Parameters

buf1	- block 1
buf2	- block 2
pos	- out - position of difference (undefined if blocks are equal)

Returns: true if difference was found

Definition at line 2904 of file bmfunc.h.

References BM_ASSERT, BMNOEXCEPT, and BMRESTRICT.

Referenced by block_find_first_diff().

◆ gap_find_interval_end()

template<typename T>

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

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

Parameters

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

Returns: false if not found

Definition at line 2564 of file bmfunc.h.

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

Referenced by block_find_interval_end().

◆ gap_find_interval_start()

template<typename T>

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

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

Parameters

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

Returns: false if not found

Definition at line 2589 of file bmfunc.h.

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

Referenced by block_find_interval_start().

◆ gap_find_last()

template<typename T>

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

GAP block find the last set bit.

Parameters

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

Returns: 0 if 1 bit was NOT found

Definition at line 1667 of file bmfunc.h.

References BM_ASSERT, BMNOEXCEPT, BMRESTRICT, and gap_max_bits.

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

◆ gap_find_prev()

template<typename T>

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

reverse search for the first 1 bit of a GAP block

Parameters

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

Returns: false if not found

Definition at line 2617 of file bmfunc.h.

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

Referenced by block_find_reverse().

◆ gap_find_rank()

template<typename T, typename SIZE_TYPE>

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

GAP block find position for the rank.

Parameters

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

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

Definition at line 2654 of file bmfunc.h.

References BM_ASSERT, BMNOEXCEPT, and gap_bfind().

Referenced by block_find_rank().

◆ gap_free_elements()

template<typename T>

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

inline

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

Parameters

buf	- GAP buffer pointer
glevel_len	- GAP lengths table

Returns: Number of free GAP elements

Definition at line 4682 of file bmfunc.h.

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

◆ gap_init_range_block()

template<class T>

void bm::gap_init_range_block	(	T *	buf,
		T	from,
		T	to,
		T	value )

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

Parameters

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

Definition at line 4570 of file bmfunc.h.

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

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

◆ gap_insert()

template<typename T>

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

isnert bit into GAP compressed block

Parameters

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

Returns: carry over bit (1 or 0)

Definition at line 3484 of file bmfunc.h.

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

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

◆ gap_invert()

template<typename T>

void bm::gap_invert ( T * buf )

Inverts all bits in the GAP buffer.

Parameters

buf	- GAP buffer pointer.

Definition at line 4620 of file bmfunc.h.

References BMNOEXCEPT.

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

◆ gap_is_all_one()

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

Checks if GAP block is all-one.

Parameters

buf	- GAP buffer pointer.

Returns: true if all-one.

Definition at line 1590 of file bmfunc.h.

References BMNOEXCEPT, BMRESTRICT, and gap_max_bits.

Referenced by check_block_one().

◆ gap_is_all_one_range()

template<typename T>

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

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

Parameters

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

Returns: true if all bits are "11111"

Definition at line 2483 of file bmfunc.h.

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

Referenced by block_is_all_one_range().

◆ gap_is_all_zero()

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

Checks if GAP block is all-zero.

Parameters

buf	- GAP buffer pointer.

Returns: true if all-zero.

Definition at line 1577 of file bmfunc.h.

References BMNOEXCEPT, BMRESTRICT, and gap_max_bits.

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

◆ gap_is_interval()

template<typename T>

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

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

Parameters

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

Returns: true if "011110"

Definition at line 2535 of file bmfunc.h.

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

Referenced by block_is_interval().

◆ gap_length()

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

Returs GAP block length.

Parameters

buf	- GAP buffer pointer.

Returns: GAP block length.

Definition at line 1603 of file bmfunc.h.

References BMNOEXCEPT, and BMRESTRICT.

Referenced by bm::bvector< Alloc >::calc_stat(), bm::xor_scanner< BV >::compute_sim_model(), bm::xor_scanner< BV >::deoptimize_gap_blocks(), bm::iterator_deserializer< BV, SerialIterator >::deserialize(), bm::deserializer< BV, DEC >::deserialize_gap(), bm::serializer< BV >::find_gap_best_encoding(), bm::serializer< BV >::gamma_gap_block(), bm::bvector< Alloc >::gap_block_set(), bm::bvector< Alloc >::gap_block_set_no_ret(), gap_convert_to_bitset(), gap_free_elements(), bm::serializer< BV >::interpolated_encode_gap_block(), bm::deseriaizer_base< DEC, BLOCK_IDX >::read_gap_block(), bm::xor_scanner< BV >::search_best_xor_mask(), and bm::bvector< Alloc >::swap().

◆ gap_level()

template<typename T>

T bm::gap_level ( const T *BMRESTRICT buf )

Returs GAP blocks capacity level.

Parameters

buf	- GAP buffer pointer.

Returns: GAP block capacity level.

Definition at line 1649 of file bmfunc.h.

References BMNOEXCEPT, and BMRESTRICT.

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

◆ gap_limit()

template<typename T>

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

Returs GAP block capacity limit.

Parameters

buf	- GAP buffer pointer.
glevel_len	- GAP lengths table (gap_len_table)

Returns: GAP block limit.

Definition at line 1635 of file bmfunc.h.

References BMNOEXCEPT, and BMRESTRICT.

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

◆ gap_operation_and()

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

inline

GAP AND operation.

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

Parameters

vect1	- operand 1
vect2	- operand 2
tmp_buf	- pointer on temporary buffer
dsize	- out size of the destination

Returns: Result pointer (tmp_buf OR vect1)

Definition at line 6518 of file bmfunc.h.

References BMNOEXCEPT, BMRESTRICT, and gap_buff_op().

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

◆ gap_operation_any_and()

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

inline

GAP AND operation test.

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

Parameters

vect1	- operand 1
vect2	- operand 2

Returns: non zero value if operation returns any 1 bit

Definition at line 6543 of file bmfunc.h.

References BMNOEXCEPT, BMRESTRICT, and gap_buff_any_op().

Referenced by combine_any_operation_with_block().

◆ gap_operation_any_sub()

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

inline

GAP SUB operation test.

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

Parameters

vect1	- operand 1
vect2	- operand 2

Returns: non zero value if operation returns any 1 bit

Definition at line 6738 of file bmfunc.h.

References BMNOEXCEPT, BMRESTRICT, and gap_buff_any_op().

Referenced by combine_any_operation_with_block().

◆ gap_operation_any_xor()

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

GAP XOR operation test.

Light weight gap_operation_xor for len prediction

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

Parameters

vect1	- operand 1
vect2	- operand 2

Returns: non zero value if operation returns any 1 bit

Definition at line 6625 of file bmfunc.h.

References BMNOEXCEPT, BMRESTRICT, and gap_buff_any_op().

Referenced by combine_any_operation_with_block().

◆ gap_operation_or()

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

inline

GAP OR operation.

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

Parameters

vect1	- operand 1
vect2	- operand 2
tmp_buf	- pointer on temporary buffer
dsize	- out destination size

Returns: Result pointer (tmp_buf)

Definition at line 6666 of file bmfunc.h.

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

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

◆ gap_operation_sub()

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

inline

GAP SUB (AND NOT) operation.

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

Parameters

vect1	- operand 1
vect2	- operand 2
tmp_buf	- pointer on temporary buffer
dsize	- out destination size

Returns: Result pointer (tmp_buf)

Definition at line 6712 of file bmfunc.h.

References BMNOEXCEPT, BMRESTRICT, and gap_buff_op().

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

◆ gap_operation_xor()

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

inline

GAP XOR operation.

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

Parameters

vect1	- operand 1
vect2	- operand 2
tmp_buf	- pointer on temporary buffer
dsize	- out destination size

Returns: Result pointer (tmp_buf)

Definition at line 6585 of file bmfunc.h.

References BMNOEXCEPT, BMRESTRICT, and gap_buff_op().

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

◆ gap_overhead()

template<typename T>

unsigned bm::gap_overhead	(	const T *	length,
		const T *	length_end,
		const T *	glevel_len )

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

Definition at line 9143 of file bmfunc.h.

References BM_ASSERT, BMNOEXCEPT, gap_calc_level(), and gap_levels.

Referenced by improve_gap_levels().

◆ gap_set_all()

template<class T>

void bm::gap_set_all	(	T *	buf,
		unsigned	set_max,
		unsigned	value )

Sets all bits to 0 or 1 (GAP).

Parameters

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

Definition at line 4552 of file bmfunc.h.

References BM_ASSERT, and BMNOEXCEPT.

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

◆ gap_set_array()

template<typename T>

unsigned bm::gap_set_array	(	T *	buf,
		const T *	arr,
		unsigned	len )

Convert array to GAP buffer.

Parameters

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

Returns: New GAP buffer length.

Definition at line 3601 of file bmfunc.h.

References BM_ASSERT, BMNOEXCEPT, and gap_max_bits.

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

◆ gap_set_value() [1/2]

template<typename T>

unsigned bm::gap_set_value	(	unsigned	val,
		T *BMRESTRICT	buf,
		unsigned	pos )

Sets or clears bit in the GAP buffer.

Parameters

val	- new bit value
buf	- GAP buffer.
pos	- Index of bit to set.

Returns: New GAP buffer length.

Definition at line 3281 of file bmfunc.h.

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

◆ gap_set_value() [2/2]

template<typename T>

unsigned bm::gap_set_value	(	unsigned	val,
		T *BMRESTRICT	buf,
		unsigned	pos,
		unsigned *BMRESTRICT	is_set )

Sets or clears bit in the GAP buffer.

Parameters

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

Returns: New GAP buffer length.

Definition at line 3254 of file bmfunc.h.

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

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

◆ gap_set_value_cpos()

template<typename T>

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

Sets or clears bit in the GAP buffer.

Parameters

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

Returns: New GAP buffer length.

Definition at line 3168 of file bmfunc.h.

References BMNOEXCEPT, BMRESTRICT, and gap_max_bits.

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

◆ gap_shift_l1()

template<typename T>

bool bm::gap_shift_l1	(	T *BMRESTRICT	buf,
		unsigned	co_flag,
		unsigned *BMRESTRICT	new_len )

Left shift GAP block by 1 bit.

Parameters

buf	- block pointer
co_flag	- carry over from the previous block
new_len	- new length of the block

Returns: carry over bit (1 or 0)

Definition at line 3540 of file bmfunc.h.

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

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

◆ gap_shift_r1()

template<typename T>

bool bm::gap_shift_r1	(	T *BMRESTRICT	buf,
		unsigned	co_flag,
		unsigned *BMRESTRICT	new_len )

Right shift GAP block by 1 bit.

Parameters

buf	- block pointer
co_flag	- carry over from the previous block
new_len	- output length of the GAP block after the operation

Returns: carry over bit (1 or 0)

Definition at line 3431 of file bmfunc.h.

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

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

◆ gap_split()

template<typename T>

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

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

Parameters

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

Definition at line 2239 of file bmfunc.h.

References BMNOEXCEPT.

◆ gap_sub_to_bitset() [1/2]

template<typename T>

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

SUB (AND NOT) GAP block to bitblock.

Parameters

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

Definition at line 3912 of file bmfunc.h.

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

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

◆ gap_sub_to_bitset() [2/2]

template<typename T>

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

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

Parameters

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

Returns: new digest

Definition at line 3943 of file bmfunc.h.

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

◆ gap_test()

template<typename T>

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

Tests if bit = pos is true.

Parameters

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

Returns: true if position is in "1" gap

Definition at line 1790 of file bmfunc.h.

References BM_ASSERT, BMNOEXCEPT, BMRESTRICT, and gap_max_bits.

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

◆ gap_test_unr()

template<typename T>

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

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

Parameters

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

Returns: true if position is in "1" gap

Definition at line 1833 of file bmfunc.h.

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

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

◆ gap_xor_to_bitset()

template<typename T>

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

XOR GAP block to bitblock.

Parameters

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

Definition at line 4011 of file bmfunc.h.

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

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

◆ gapcmp()

template<typename T>

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

Lexicographical comparison of GAP buffers.

Parameters

buf1	- First GAP buffer pointer.
buf2	- Second GAP buffer pointer.

Returns: <0 - less, =0 - equal, >0 - greater.

Definition at line 2848 of file bmfunc.h.

References BMNOEXCEPT.

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

◆ improve_gap_levels()

template<typename T>

bool bm::improve_gap_levels	(	const T *	length,
		const T *	length_end,
		T *	glevel_len )

Finds optimal gap blocks lengths.

Parameters

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

Definition at line 9170 of file bmfunc.h.

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

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

◆ set_gap_level()

template<typename T>

void bm::set_gap_level	(	T *	buf,
		int	level )

Sets GAP block capacity level.

Parameters

buf	- GAP buffer pointer.
level	new GAP block capacity level.

Definition at line 4639 of file bmfunc.h.

References BM_ASSERT, BMNOEXCEPT, and gap_levels.

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

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_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_set_value_cpos()

◆ 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()