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

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

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

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

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

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

bm::gap_word_t	bm::gap_length (const bm::gap_word_t *buf) noexcept
	Returs GAP block length. More...

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

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

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

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

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

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

template<typename T >
unsigned	bm::gap_test_unr (const T *buf, const unsigned pos) noexcept
	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) noexcept

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

template<typename T >
unsigned	bm::gap_bit_count_unr (const T *buf) noexcept
	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) noexcept
	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) noexcept
	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 buf, unsigned left, unsigned right) noexcept
	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 buf, unsigned left, unsigned right) noexcept
	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 buf, unsigned left, unsigned right) noexcept
	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 buf, unsigned nbit, unsigned pos) noexcept
	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 buf, unsigned nbit, unsigned pos) noexcept
	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 buf, unsigned nbit, unsigned pos) noexcept
	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) noexcept
	GAP block find position for the rank. More...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

template<typename T >
unsigned	bm::gap_control_sum (const T *buf) noexcept
	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) noexcept
	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) noexcept
	Init gap block so it has block in it (can be whole block) More...

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

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

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

template<typename T >
unsigned	bm::gap_free_elements (const T buf, const T glevel_len) noexcept
	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 dest, const unsigned block, unsigned dest_len) noexcept
	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 dest, const T buf, unsigned dest_len, bool invert=false) noexcept
	Convert gap block into array of ints corresponding to 1 bits. More...

gap_word_t *	bm::gap_operation_and (const gap_word_t vect1, const gap_word_t vect2, gap_word_t *tmp_buf, unsigned &dsize) noexcept
	GAP AND operation. More...

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

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

gap_word_t *	bm::gap_operation_xor (const gap_word_t vect1, const gap_word_t vect2, gap_word_t *tmp_buf, unsigned &dsize) noexcept
	GAP XOR operation. More...

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

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

gap_word_t *	bm::gap_operation_or (const gap_word_t vect1, const gap_word_t vect2, gap_word_t *tmp_buf, unsigned &dsize) noexcept
	GAP OR operation. More...

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

gap_word_t *	bm::gap_operation_sub (const gap_word_t vect1, const gap_word_t vect2, gap_word_t *tmp_buf, unsigned &dsize) noexcept
	GAP SUB (AND NOT) operation. More...

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

unsigned	bm::gap_count_sub (const gap_word_t vect1, const gap_word_t vect2) noexcept
	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) noexcept
	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) noexcept
	Finds optimal gap blocks lengths. More...

template<typename T >
unsigned	bit_convert_to_gap (T dest, const unsigned src, bm::id_t bits, unsigned dest_len)
	Converts bit block to GAP. 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
	)

noexcept

Compute number of GAPs in bit-array.

Parameters

arr	- array of BITs
len	- array length

Definition at line 3662 of file bmfunc.h.

References arr, i, len, prev(), and T.

Referenced by BitCountChangeTest().

◆ bit_block_to_gap()

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

inlinenoexcept

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 bm::bit_scan_forward32(), BM_ASSERT, BMRESTRICT, len, bm::set_block_size, and val.

Referenced by bm::bit_to_gap().

◆ bit_convert_to_gap()

template<typename T >

unsigned bit_convert_to_gap	(	T *	dest,
		const unsigned *	src,
		bm::id_t	bits,
		unsigned	dest_len
	)

Converts bit block to GAP.

Parameters

dest	- Destinatio GAP buffer.
src	- Source bitblock buffer.
bits	- Number of bits to convert.
dest_len	- length of the dest. buffer.

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

Definition at line 3245 of file stress32.cpp.

References assert, bm::bvector< Alloc >::end(), len, mask, T, and val.

Referenced by GAPCheck(), and TestBlockToGAP().

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

References buf, offset, prev(), and T.

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 *	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, buf, bm::gap_bfind(), int, offset, prev(), and T.

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

References buf, i, prev(), and T.

◆ gap_add_to_bitset() [1/2]

template<typename T >

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

noexcept

Adds(OR) GAP block to bitblock.

Parameters

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

Definition at line 4074 of file bmfunc.h.

References bm::gap_add_to_bitset(), and len.

◆ gap_add_to_bitset() [2/2]

template<typename T >

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

noexcept

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, len, bm::or_bit_block(), and T.

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
	)

noexcept

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, buf, bm::gap_max_bits, memmove, and T.

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

noexcept

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, bm::sub_bit_block(), and T.

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 >

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

noexcept

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, BMRESTRICT, bm::check_zero_digest(), bm::count_leading_zeros_u64(), bm::count_trailing_zeros_u64(), bm::gap_bfind(), len, prev(), bm::set_block_digest_pos_shift, bm::sub_bit_block(), T, and bm::update_block_digest0().

◆ gap_any_range()

template<typename T >

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

noexcept

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, buf, bm::gap_bfind(), bm::gap_max_bits, and T.

Referenced by bm::block_any_range().

◆ gap_bit_count()

template<typename T >

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

noexcept

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 buf, and T.

Referenced by gap_vector::bit_count(), bm::gap_bit_count_unr(), and bm::print_stat().

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

noexcept

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, buf, bm::gap_bfind(), bm::gap_max_bits, and T.

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

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

noexcept

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, buf, bm::gap_bfind(), bm::gap_max_bits, and T.

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

◆ gap_bit_count_unr()

template<typename T >

unsigned bm::gap_bit_count_unr ( const T * buf )

noexcept

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 bm::avx2_gap_sum_arr(), BM_ASSERT, buf, cnt, bm::gap_bit_count(), i, bm::sse2_gap_sum_arr(), and T.

Referenced by bm::blocks_manager< Alloc >::block_bitcount(), bm::combine_count_operation_with_block(), bm::serializer< BV >::find_gap_best_encoding(), and bm::blocks_manager< Alloc >::is_sparse_sblock().

◆ gap_bitset_and_any()

template<typename T >

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

noexcept

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 bm::bit_block_any_range(), BM_ASSERT, count, and T.

Referenced by bm::combine_any_operation_with_block().

◆ gap_bitset_and_count()

template<typename T >

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

noexcept

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 bm::bit_block_calc_count_range(), BM_ASSERT, count, and T.

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

◆ gap_bitset_or_any()

template<typename T >

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

noexcept

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

noexcept

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 bm::bit_block_calc_count_range(), BM_ASSERT, buf, count, prev(), and T.

Referenced by bm::combine_count_operation_with_block().

◆ gap_bitset_sub_any()

template<typename T >

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

noexcept

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 bm::bit_block_any_range(), BM_ASSERT, buf, count, and T.

Referenced by bm::combine_any_operation_with_block().

◆ gap_bitset_sub_count()

template<typename T >

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

noexcept

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 bm::bit_block_calc_count_range(), BM_ASSERT, buf, count, and T.

Referenced by bm::combine_count_operation_with_block().

◆ gap_bitset_xor_any()

template<typename T >

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

noexcept

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 bm::bit_block_any_range(), BM_ASSERT, buf, count, prev(), and T.

Referenced by bm::combine_any_operation_with_block().

◆ gap_bitset_xor_count()

template<typename T >

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

noexcept

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 bm::bit_block_calc_count_range(), BM_ASSERT, buf, count, prev(), and T.

Referenced by bm::combine_count_operation_with_block().

◆ gap_block_find()

template<typename T >

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

noexcept

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, buf, bm::gap_bfind(), bm::gap_max_bits, prev(), and val.

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

◆ 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 count, bm::gap_max_bits, and T.

◆ gap_calc_level()

template<typename T >

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

noexcept

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, bm::gap_levels, and len.

Referenced by bm::blocks_manager< Alloc >::assign_gap(), bm::blocks_manager< Alloc >::clone_gap_block(), bm::iterator_deserializer< BV, SerialIterator >::deserialize(), bm::deserializer< BV, DEC >::deserialize_gap(), bm::gap_overhead(), bm::blocks_manager< Alloc >::gap_level_func::operator()(), bm::blocks_manager< Alloc >::opt_copy_bit_block(), bm::blocks_manager< Alloc >::optimize_block(), and bm::blocks_manager< Alloc >::optimize_gap_convert_bit_block().

◆ gap_capacity()

template<typename T >

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

noexcept

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

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

◆ gap_control_sum()

template<typename T >

unsigned bm::gap_control_sum ( const T * buf )

noexcept

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, buf, and T.

Referenced by gap_vector::control(), and bm::print_stat().

◆ gap_convert_to_arr()

template<typename D , typename T >

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

noexcept

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

Definition at line 4942 of file bmfunc.h.

References BMRESTRICT, buf, D, i, invert, and T.

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

◆ gap_convert_to_bitset()

template<typename T >

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

noexcept

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 bm::bit_block_set(), buf, bm::gap_add_to_bitset(), bm::gap_length(), and len.

Referenced by bm::block_find_first_diff(), bm::aggregator< BV >::cache_gap_block(), bm::blocks_manager< Alloc >::clone_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::miniset< A, N >::convert_buf(), bm::blocks_manager< Alloc >::convert_gap2bitset(), gap_vector::convert_to_bitset(), bm::blocks_manager< Alloc >::copy_bit_block(), bm::blocks_manager< Alloc >::deoptimize_block_no_check(), 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::random_subset< BV >::get_subset(), bm::blocks_manager< Alloc >::gap_level_func::operator()(), bm::blocks_manager< Alloc >::set_gap_block(), 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 *	dest,
		const T *	buf,
		id_t	set_max
	)

noexcept

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 buf, 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 *	vect1,
		const gap_word_t *	vect2
	)

inlinenoexcept

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.

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

◆ gap_count_or()

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

inlinenoexcept

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.

Referenced by bm::combine_count_operation_with_block().

◆ gap_count_sub()

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

inlinenoexcept

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.

Referenced by bm::combine_count_operation_with_block().

◆ gap_count_xor()

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

inlinenoexcept

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.

Referenced by bm::combine_count_operation_with_block().

◆ gap_find_first()

template<typename T >

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

noexcept

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, buf, first(), bm::gap_max_bits, and T.

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 *	buf1,
		const T *	buf2,
		unsigned *	pos
	)

noexcept

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, and T.

Referenced by bm::block_find_first_diff(), and TestBlockToGAP().

◆ gap_find_interval_end()

template<typename T >

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

noexcept

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

noexcept

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

noexcept

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, buf, bm::gap_max_bits, last(), and T.

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

◆ gap_find_prev()

template<typename T >

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

noexcept

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, buf, 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
	)

noexcept

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, bm::gap_bfind(), and T.

Referenced by bm::block_find_rank().

◆ gap_free_elements()

template<typename T >

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

inlinenoexcept

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 buf, bm::gap_capacity(), bm::gap_length(), and len.

◆ gap_init_range_block()

template<class T >

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

noexcept

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 bm::bits_in_block, BM_ASSERT, buf, bm::gap_set_all(), T, and rapidjson::value.

◆ gap_insert()

template<typename T >

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

noexcept

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, buf, bm::gap_bfind(), bm::gap_max_bits, bm::gap_set_value(), i, len, T, and val.

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

◆ gap_invert()

template<typename T >

void bm::gap_invert ( T * buf )

noexcept

Inverts all bits in the GAP buffer.

Parameters

buf	- GAP buffer pointer.

Definition at line 4620 of file bmfunc.h.

References buf.

Referenced by bm::blocks_manager< Alloc >::clone_assign_block(), 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()

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

inlinenoexcept

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 buf, and bm::gap_max_bits.

Referenced by bm::blocks_manager< Alloc >::assign_gap_check(), bm::check_block_one(), bm::blocks_manager< Alloc >::clone_assign_block(), bm::blocks_manager< Alloc >::gap_level_func::operator()(), and bm::blocks_manager< Alloc >::optimize_block().

◆ gap_is_all_one_range()

template<typename T >

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

noexcept

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, buf, bm::gap_bfind(), bm::gap_max_bits, and T.

Referenced by bm::block_is_all_one_range().

◆ gap_is_all_zero()

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

inlinenoexcept

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 buf, and bm::gap_max_bits.

Referenced by bm::blocks_manager< Alloc >::assign_gap_check(), bm::block_any(), bm::check_block_zero(), bm::blocks_manager< Alloc >::clone_assign_block(), bm::blocks_manager< Alloc >::clone_gap_block(), 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(), bm::gap_bitset_or_any(), bm::blocks_manager< Alloc >::gap_level_func::operator()(), bm::blocks_manager< Alloc >::block_any_func::operator()(), and bm::blocks_manager< Alloc >::optimize_block().

◆ gap_is_interval()

template<typename T >

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

noexcept

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, buf, bm::gap_bfind(), bm::gap_max_bits, and T.

Referenced by bm::block_is_interval().

◆ gap_length()

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

inlinenoexcept

Returs GAP block length.

Parameters

buf	- GAP buffer pointer.

Returns: GAP block length.

Definition at line 1603 of file bmfunc.h.

References buf.

◆ gap_level()

template<typename T >

T bm::gap_level ( const T * buf )

noexcept

Returs GAP blocks capacity level.

Parameters

buf	- GAP buffer pointer.

Returns: GAP block capacity level.

Definition at line 1649 of file bmfunc.h.

References buf, and T.

Referenced by bm::blocks_manager< Alloc >::assign_gap(), bm::bvector< Alloc >::calc_stat(), bm::blocks_manager< Alloc >::extend_gap_block(), bm::blocks_manager< Alloc >::optimize_block(), and bm::print_stat().

◆ gap_limit()

template<typename T >

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

noexcept

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

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(), bm::bvector< Alloc >::insert(), and bm::bvector< Alloc >::swap().

◆ gap_operation_and()

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

inlinenoexcept

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.

Referenced by gap_vector::combine_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 *	vect1,
		const gap_word_t *	vect2
	)

inlinenoexcept

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.

Referenced by bm::combine_any_operation_with_block().

◆ gap_operation_any_sub()

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

inlinenoexcept

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.

Referenced by bm::combine_any_operation_with_block().

◆ gap_operation_any_xor()

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

inlinenoexcept

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.

Referenced by bm::combine_any_operation_with_block().

◆ gap_operation_or()

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

inlinenoexcept

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

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

◆ gap_operation_sub()

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

inlinenoexcept

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.

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

◆ gap_operation_xor()

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

inlinenoexcept

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.

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

noexcept

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, bm::gap_calc_level(), bm::gap_levels, and len.

Referenced by bm::improve_gap_levels().

◆ gap_set_all()

template<class T >

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

noexcept

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, buf, T, and rapidjson::value.

Referenced by BitCountChangeTest(), bm::blocks_manager< Alloc >::check_allocate_block(), bm::gap_init_range_block(), bm::miniset< A, N >::init_gapbuf(), 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
	)

noexcept

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 arr, BM_ASSERT, buf, bm::gap_max_bits, i, len, prev(), and T.

Referenced by BitCountChangeTest(), 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 *	buf,
		unsigned	pos
	)

noexcept

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, buf, bm::gap_bfind(), bm::gap_max_bits, memmove, T, and val.

◆ gap_set_value() [2/2]

template<typename T >

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

noexcept

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, buf, bm::gap_bfind(), bm::gap_max_bits, bm::gap_set_value_cpos(), and val.

Referenced by BitCountChangeTest(), gap_vector::clear_bit(), 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(), bm::miniset< A, N >::set(), and gap_vector::set_bit().

◆ gap_set_value_cpos()

template<typename T >

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

noexcept

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 buf, bm::gap_max_bits, memmove, T, and val.

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

◆ gap_shift_l1()

template<typename T >

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

noexcept

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, buf, bm::gap_max_bits, bm::gap_set_value(), i, and len.

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

◆ gap_shift_r1()

template<typename T >

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

noexcept

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, buf, bm::gap_max_bits, bm::gap_set_value(), i, len, and T.

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
	)

noexcept

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 buf, delta(), len, prev(), and T.

◆ gap_sub_to_bitset() [1/2]

template<typename T >

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

noexcept

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, bm::sub_bit_block(), and T.

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 >

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

noexcept

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, BMRESTRICT, bm::check_zero_digest(), bm::count_leading_zeros_u64(), bm::count_trailing_zeros_u64(), bm::gap_bfind(), len, prev(), bm::set_block_digest_pos_shift, bm::sub_bit_block(), T, and bm::update_block_digest0().

◆ gap_test()

template<typename T >

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

noexcept

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, buf, and bm::gap_max_bits.

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

◆ gap_test_unr()

template<typename T >

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

noexcept

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, buf, bm::gap_max_bits, bm::gap_test(), and VECT_GAP_TEST.

Referenced by bm::bvector< Alloc >::and_bit_no_check(), bm::blocks_manager< Alloc >::block_count_change_func::block_count(), bm::aggregator< BV >::combine_and_sub(), bm::combine_sub(), bm::combine_xor(), bm::sparse_vector< Val, BV >::extract_range(), bm::bvector< Alloc >::gap_count_to(), 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(), gap_vector::is_bit_true(), 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 *	dest,
		const T *	pcurr
	)

noexcept

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, T, 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
	)

noexcept

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

Referenced by BitCountChangeTest(), CheckGap2DGap(), bm::bvector< Alloc >::compare(), gap_vector::compare(), and TestBlockToGAP().

◆ improve_gap_levels()

template<typename T >

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

noexcept

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, bm::gap_levels, bm::gap_max_buff_len, bm::gap_overhead(), i, opt_len, T, and val.

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

◆ set_gap_level()

template<typename T >

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

noexcept

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, buf, bm::gap_levels, and T.

Referenced by bm::blocks_manager< Alloc >::assign_gap(), bm::blocks_manager< Alloc >::clone_gap_block(), bm::iterator_deserializer< BV, SerialIterator >::deserialize(), bm::deserializer< BV, DEC >::deserialize_gap(), and bm::blocks_manager< Alloc >::set_gap_block().

Classes

Functions

Detailed Description

Function Documentation

◆ bit_array_compute_gaps()

◆ bit_block_to_gap()

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