Algorithms for fast aggregation of a group of bit-vectors. More...

#include <bmaggregator.h>

Inheritance diagram for bm::aggregator< BV >:

[legend]

Data Structures
struct	arg_groups
	Aggregator arg groups. More...
struct	pipeline_bcache
	Block cache for pipeline execution. More...
struct	run_options
	Aggregation options for runtime control. More...
class	pipeline
	Pipeline vector for running a group of aggregation operations on a family of vectors. More...
struct	arena
	Temporary operations vectors. More...

Public Types
enum	operation { BM_NOT_DEFINED = 0 , BM_SHIFT_R_AND = 1 }
	Codes for aggregation operations which can be pipelined for efficient execution. More...
enum class	operation_status { op_undefined = 0 , op_prepared , op_in_progress , op_done }
typedef BV	bvector_type
typedef BV::size_type	size_type
typedef BV::allocator_type	allocator_type
typedef const bvector_type *	bvector_type_const_ptr
typedef bm::id64_t	digest_type
typedef bvector_type::allocator_type::allocator_pool_type	allocator_pool_type
typedef bm::heap_vector< bvector_type_const_ptr, allocator_type, true >	bv_vector_type
typedef bm::heap_vector< bvector_type *, allocator_type, true >	bvect_vector_type
typedef bm::heap_vector< size_t, allocator_type, true >	index_vector_type
typedef arg_groups *	arg_groups_type_ptr
typedef bm::heap_vector< arg_groups_type_ptr, allocator_type, true >	arg_vector_type
typedef bm::heap_vector< unsigned, allocator_type, true >	count_vector_type
typedef bm::heap_vector< size_type, allocator_type, true >	bv_count_vector_type
typedef bm::heap_vector< bm::word_t *, allocator_type, true >	blockptr_vector_type
typedef bm::heap_vector< bm::pair< unsigned, unsigned >, allocator_type, true >	block_ij_vector_type

Public Member Functions
Construction and setup
	aggregator ()
	~aggregator ()
void	set_optimization (typename bvector_type::optmode opt=bvector_type::opt_compress) BMNOEXCEPT
	set on-the-fly bit-block compression By default aggregator does not try to optimize result, but in some cases it can be quite a lot faster than calling bvector<>::optimize() later (because block data sits in CPU cache).
void	set_compute_count (bool count_mode) BMNOEXCEPT
Methods to setup argument groups and run operations on groups
size_t	add (const bvector_type *bv, unsigned agr_group=0)
	Attach source bit-vector to a argument group (0 or 1).
void	reset ()
	Reset aggregate groups, forget all attached vectors.
void	combine_or (bvector_type &bv_target)
	Aggregate added group of vectors using logical OR Operation does NOT perform an explicit reset of arg group(s).
void	combine_and (bvector_type &bv_target)
	Aggregate added group of vectors using logical AND Operation does NOT perform an explicit reset of arg group(s).
bool	combine_and_sub (bvector_type &bv_target)
	Aggregate added group of vectors using fused logical AND-SUB Operation does NOT perform an explicit reset of arg group(s).
template<class TPipe>
void	combine_and_sub (TPipe &pipe)
	Run AND-SUB: AND (groups1) AND NOT ( OR(group0)) for a pipeline.
bool	combine_and_sub (bvector_type &bv_target, bool any)
	Aggregate added group of vectors using fused logical AND-SUB Operation does NOT perform an explicit reset of arg group(s) Operation can terminate early if anything was found.
template<typename BII>
bool	combine_and_sub_bi (BII bi)
	Aggregate added group of vectors using fused logical AND-SUB.
bool	find_first_and_sub (size_type &idx)
	Aggregate added group of vectors using fused logical AND-SUB, find the first match.
void	combine_shift_right_and (bvector_type &bv_target)
	Aggregate added group of vectors using SHIFT-RIGHT and logical AND Operation does NOT perform an explicit reset of arg group(s).
bool	set_range_hint (size_type from, size_type to) BMNOEXCEPT
	Set search hint for the range, where results needs to be searched (experimental for internal use).
void	reset_range_hint () BMNOEXCEPT
	Reset range hint to false.
size_type	count () const
Logical operations (C-style interface)
void	combine_or (bvector_type &bv_target, const bvector_type_const_ptr *bv_src, size_t src_size)
	Aggregate group of vectors using logical OR.
void	combine_and (bvector_type &bv_target, const bvector_type_const_ptr *bv_src, size_t src_size)
	Aggregate group of vectors using logical AND.
bool	combine_and_sub (bvector_type &bv_target, const bvector_type_const_ptr bv_src_and, size_t src_and_size, const bvector_type_const_ptr bv_src_sub, size_t src_sub_size, bool any)
	Fusion aggregate group of vectors using logical AND MINUS another set.
template<typename BII>
bool	combine_and_sub (BII bi, const bvector_type_const_ptr bv_src_and, size_t src_and_size, const bvector_type_const_ptr bv_src_sub, size_t src_sub_size)
bool	find_first_and_sub (size_type &idx, const bvector_type_const_ptr bv_src_and, size_t src_and_size, const bvector_type_const_ptr bv_src_sub, size_t src_sub_size)
bool	combine_shift_right_and (bvector_type &bv_target, const bvector_type_const_ptr *bv_src_and, size_t src_and_size, bool any)
	Fusion aggregate group of vectors using SHIFT right with AND.
Horizontal Logical operations used for tests (C-style interface)
void	combine_or_horizontal (bvector_type &bv_target, const bvector_type_const_ptr *bv_src, size_t src_size)
	Horizontal OR aggregation (potentially slower) method.
void	combine_and_horizontal (bvector_type &bv_target, const bvector_type_const_ptr *bv_src, size_t src_size)
	Horizontal AND aggregation (potentially slower) method.
void	combine_and_sub_horizontal (bvector_type &bv_target, const bvector_type_const_ptr bv_src_and, size_t src_and_size, const bvector_type_const_ptr bv_src_sub, size_t src_sub_size)
	Horizontal AND-SUB aggregation (potentially slower) method.
Pipeline operations
int	get_operation () const BMNOEXCEPT
	Get current operation code.
void	set_operation (int op_code) BMNOEXCEPT
	Set operation code for the aggregator.
void	stage (bm::word_t *temp_block)
	Prepare operation, create internal resources, analyse dependencies.
operation_status	run_step (unsigned i, unsigned j)
	Run a step of current arrgegation operation.
operation_status	get_operation_status () const
const bvector_type *	get_target () const BMNOEXCEPT
bm::word_t *	get_temp_block () BMNOEXCEPT

Execition metrics and telemetry
typedef bvector_type::blocks_manager_type	blocks_manager_type
typedef BV::block_idx_type	block_idx_type
typedef bm::heap_vector< const bm::word_t *, allocator_type, true >	block_ptr_vector_type
typedef bm::heap_vector< const bm::gap_word_t *, allocator_type, true >	gap_block_ptr_vector_type
typedef bm::heap_vector< unsigned char, allocator_type, true >	uchar_vector_type
bm::id64_t	get_cache_gap_hits () const BMNOEXCEPT
void	reset_vars ()
void	combine_or (unsigned i, unsigned j, bvector_type &bv_target, const bvector_type_const_ptr *bv_src, size_t src_size)
void	combine_and (unsigned i, unsigned j, bvector_type &bv_target, const bvector_type_const_ptr *bv_src, size_t src_size)
digest_type	combine_and_sub (unsigned i, unsigned j, const bvector_type_const_ptr bv_src_and, size_t src_and_size, const bvector_type_const_ptr bv_src_sub, size_t src_sub_size, int *is_result_full, bool find_all)
void	prepare_shift_right_and (bvector_type &bv_target, const bvector_type_const_ptr *bv_src, size_t src_size)
bool	combine_shift_right_and (unsigned i, unsigned j, bvector_type &bv_target, const bvector_type_const_ptr *bv_src, size_t src_size)
bm::word_t *	sort_input_blocks_or (const bvector_type_const_ptr *bv_src, size_t src_size, unsigned i, unsigned j)
bm::word_t *	sort_input_blocks_and (const bvector_type_const_ptr *bv_src, size_t src_size, unsigned i, unsigned j)
bm::word_t *	cache_gap_block (const bm::word_t arg_blk, const size_t src_idx, size_t k, unsigned i, unsigned j)
bool	process_bit_blocks_or (blocks_manager_type &bman_target, unsigned i, unsigned j, const arena &ar)
void	process_gap_blocks_or (const arena &ar)
digest_type	process_bit_blocks_and (const arena &ar, digest_type digest, bool find_all)
digest_type	process_gap_blocks_and (const arena &ar, digest_type digest)
bool	test_gap_blocks_and (size_t block_count, unsigned bit_idx)
bool	test_gap_blocks_sub (size_t block_count, unsigned bit_idx)
digest_type	process_bit_blocks_sub (const arena &ar, digest_type digest)
digest_type	process_gap_blocks_sub (const arena &ar, digest_type digest)
bvector_type *	check_create_target ()
static unsigned	resize_target (bvector_type &bv_target, const bvector_type_const_ptr *bv_src, size_t src_size, bool init_clear=true)
static unsigned	max_top_blocks (const bvector_type_const_ptr *bv_src, size_t src_size) BMNOEXCEPT
static unsigned	find_effective_sub_block_size (unsigned i, const bvector_type_const_ptr *bv_src, size_t src_size, bool top_null_as_zero) BMNOEXCEPT
static unsigned	find_effective_sub_block_size (unsigned i, const bvector_type_const_ptr bv_src1, size_t src_size1, const bvector_type_const_ptr bv_src2, size_t src_size2) BMNOEXCEPT
static bool	any_carry_overs (const unsigned char *carry_overs, size_t co_size) BMNOEXCEPT
static unsigned	process_shift_right_and (bm::word_t BMRESTRICT blk, const bm::word_t BMRESTRICT arg_blk, digest_type &BMRESTRICT digest, unsigned carry_over) BMNOEXCEPT
static const bm::word_t *	get_arg_block (const bvector_type_const_ptr *bv_src, unsigned k, unsigned i, unsigned j) BMNOEXCEPT
static arena *	construct_arena ()
static void	free_arena (arena *ar) BMNOEXCEPT
static arg_groups *	construct_arg_group ()
static void	free_arg_group (arg_groups *arg)

Detailed Description

template<typename BV>
class bm::aggregator< BV >

Algorithms for fast aggregation of a group of bit-vectors.

Algorithms of this class use cache locality optimizations and efficient on cases, wehen we need to apply the same logical operation (aggregate) more than 2x vectors.

TARGET = BV1 or BV2 or BV3 or BV4 ...

Aggregator supports OR, AND and AND-MINUS (AND-SUB) operations

Examples: bvsetalgebra.cpp, sample16.cpp, and xsample04.cpp.

Definition at line 121 of file bmaggregator.h.

Member Typedef Documentation

◆ allocator_pool_type

template<typename BV>

typedef bvector_type::allocator_type::allocator_pool_type bm::aggregator< BV >::allocator_pool_type

Definition at line 130 of file bmaggregator.h.

◆ allocator_type

template<typename BV>

typedef BV::allocator_type bm::aggregator< BV >::allocator_type

Definition at line 126 of file bmaggregator.h.

◆ arg_groups_type_ptr

template<typename BV>

typedef arg_groups* bm::aggregator< BV >::arg_groups_type_ptr

Definition at line 181 of file bmaggregator.h.

◆ arg_vector_type

template<typename BV>

typedef bm::heap_vector<arg_groups_type_ptr, allocator_type, true> bm::aggregator< BV >::arg_vector_type

Definition at line 183 of file bmaggregator.h.

◆ block_idx_type

template<typename BV>

typedef BV::block_idx_type bm::aggregator< BV >::block_idx_type

protected

Definition at line 639 of file bmaggregator.h.

◆ block_ij_vector_type

template<typename BV>

typedef bm::heap_vector<bm::pair<unsigned, unsigned>, allocator_type, true> bm::aggregator< BV >::block_ij_vector_type

Definition at line 191 of file bmaggregator.h.

◆ block_ptr_vector_type

template<typename BV>

typedef bm::heap_vector<const bm::word_t*, allocator_type, true> bm::aggregator< BV >::block_ptr_vector_type

protected

Definition at line 641 of file bmaggregator.h.

◆ blockptr_vector_type

template<typename BV>

typedef bm::heap_vector<bm::word_t*, allocator_type, true> bm::aggregator< BV >::blockptr_vector_type

Definition at line 189 of file bmaggregator.h.

◆ blocks_manager_type

template<typename BV>

typedef bvector_type::blocks_manager_type bm::aggregator< BV >::blocks_manager_type

protected

Definition at line 638 of file bmaggregator.h.

◆ bv_count_vector_type

template<typename BV>

typedef bm::heap_vector<size_type, allocator_type, true> bm::aggregator< BV >::bv_count_vector_type

Definition at line 187 of file bmaggregator.h.

◆ bv_vector_type

template<typename BV>

typedef bm::heap_vector<bvector_type_const_ptr, allocator_type, true> bm::aggregator< BV >::bv_vector_type

Definition at line 132 of file bmaggregator.h.

◆ bvect_vector_type

template<typename BV>

typedef bm::heap_vector<bvector_type*, allocator_type, true> bm::aggregator< BV >::bvect_vector_type

Definition at line 134 of file bmaggregator.h.

◆ bvector_type

template<typename BV>

typedef BV bm::aggregator< BV >::bvector_type

Definition at line 124 of file bmaggregator.h.

◆ bvector_type_const_ptr

template<typename BV>

typedef const bvector_type* bm::aggregator< BV >::bvector_type_const_ptr

Definition at line 127 of file bmaggregator.h.

◆ count_vector_type

template<typename BV>

typedef bm::heap_vector<unsigned, allocator_type, true> bm::aggregator< BV >::count_vector_type

Definition at line 185 of file bmaggregator.h.

◆ digest_type

template<typename BV>

typedef bm::id64_t bm::aggregator< BV >::digest_type

Definition at line 128 of file bmaggregator.h.

◆ gap_block_ptr_vector_type

template<typename BV>

typedef bm::heap_vector<const bm::gap_word_t*, allocator_type, true> bm::aggregator< BV >::gap_block_ptr_vector_type

protected

Definition at line 643 of file bmaggregator.h.

◆ index_vector_type

template<typename BV>

typedef bm::heap_vector<size_t, allocator_type, true> bm::aggregator< BV >::index_vector_type

Definition at line 136 of file bmaggregator.h.

◆ size_type

template<typename BV>

typedef BV::size_type bm::aggregator< BV >::size_type

Definition at line 125 of file bmaggregator.h.

◆ uchar_vector_type

template<typename BV>

typedef bm::heap_vector<unsigned char, allocator_type, true> bm::aggregator< BV >::uchar_vector_type

protected

Definition at line 645 of file bmaggregator.h.

Member Enumeration Documentation

◆ operation

template<typename BV>

enum bm::aggregator::operation

Codes for aggregation operations which can be pipelined for efficient execution.

Enumerator
BM_NOT_DEFINED
BM_SHIFT_R_AND

Definition at line 141 of file bmaggregator.h.

◆ operation_status

template<typename BV>

enum class bm::aggregator::operation_status

strong

Enumerator
op_undefined
op_prepared
op_in_progress
op_done

Definition at line 147 of file bmaggregator.h.

Constructor & Destructor Documentation

◆ aggregator()

template<typename BV>

bm::aggregator< BV >::aggregator ( )

Definition at line 916 of file bmaggregator.h.

References bm::aligned_new_malloc(), and construct_arena().

◆ ~aggregator()

template<typename BV>

bm::aggregator< BV >::~aggregator ( )

Definition at line 928 of file bmaggregator.h.

References bm::aligned_free(), BM_ASSERT, and free_arena().

Member Function Documentation

◆ add()

template<typename BV>

size_t bm::aggregator< BV >::add	(	const bvector_type *	bv,
		unsigned	agr_group = 0 )

Attach source bit-vector to a argument group (0 or 1).

Arg group 1 used for fused operations like (AND-SUB)

Parameters

bv	- input bit-vector pointer to attach
agr_group	- input argument group (0 - default, 1 - fused op)

Returns: current arg group size (0 if vector was not added (empty))

See also: reset

Examples: bvsetalgebra.cpp, and sample16.cpp.

Definition at line 1013 of file bmaggregator.h.

Referenced by DemoAND(), DemoAND_OR(), DemoAND_SUB(), DemoOR(), DemoSUB(), and main().

◆ any_carry_overs()

template<typename BV>

bool bm::aggregator< BV >::any_carry_overs	(	const unsigned char *	carry_overs,
		size_t	co_size )

staticprotected

Definition at line 2683 of file bmaggregator.h.

References BMNOEXCEPT.

Referenced by combine_shift_right_and(), and run_step().

◆ cache_gap_block()

template<typename BV>

bm::word_t * bm::aggregator< BV >::cache_gap_block	(	const bm::word_t *	arg_blk,
		const size_t *	src_idx,
		size_t	k,
		unsigned	i,
		unsigned	j )

protected

Definition at line 2371 of file bmaggregator.h.

References bm::aligned_new_malloc(), BM_ASSERT, BMGAP_PTR, bm::pair< First, Second >::first, bm::gap_convert_to_bitset(), bm::pair< First, Second >::second, and bm::set_block_size.

◆ check_create_target()

template<typename BV>

aggregator< BV >::bvector_type * bm::aggregator< BV >::check_create_target ( )

protected

Definition at line 1000 of file bmaggregator.h.

Referenced by stage().

◆ combine_and() [1/3]

template<typename BV>

void bm::aggregator< BV >::combine_and ( bvector_type & bv_target )

Aggregate added group of vectors using logical AND Operation does NOT perform an explicit reset of arg group(s).

Parameters

bv_target - target vector (input is arg group 0)

See also: add, reset

Examples: bvsetalgebra.cpp, and sample16.cpp.

Definition at line 1030 of file bmaggregator.h.

References BM_ASSERT, and combine_and_sub().

Referenced by DemoAND(), and main().

◆ combine_and() [2/3]

template<typename BV>

void bm::aggregator< BV >::combine_and	(	bvector_type &	bv_target,
		const bvector_type_const_ptr *	bv_src,
		size_t	src_size )

Aggregate group of vectors using logical AND.

Parameters

bv_target	- target vector
bv_src	- array of pointers on bit-vector aggregate arguments
src_size	- size of bv_src (how many vectors to aggregate)

Definition at line 1127 of file bmaggregator.h.

References BM_ASSERT, bm::combine_and(), find_effective_sub_block_size(), and resize_target().

◆ combine_and() [3/3]

template<typename BV>

void bm::aggregator< BV >::combine_and	(	unsigned	i,
		unsigned	j,
		bvector_type &	bv_target,
		const bvector_type_const_ptr *	bv_src,
		size_t	src_size )

protected

Definition at line 1668 of file bmaggregator.h.

References BM_ASSERT, FULL_BLOCK_FAKE_ADDR, FULL_BLOCK_REAL_ADDR, process_bit_blocks_and(), process_gap_blocks_and(), bm::set_sub_array_size, and sort_input_blocks_and().

◆ combine_and_horizontal()

template<typename BV>

void bm::aggregator< BV >::combine_and_horizontal	(	bvector_type &	bv_target,
		const bvector_type_const_ptr *	bv_src,
		size_t	src_size )

Horizontal AND aggregation (potentially slower) method.

Parameters

bv_target	- target vector
bv_src	- array of pointers on bit-vector aggregate arguments
src_size	- size of bv_src (how many vectors to aggregate)

Definition at line 2431 of file bmaggregator.h.

References BM_ASSERT, and bm::READWRITE.

Referenced by combine_and_sub_horizontal().

◆ combine_and_sub() [1/6]

template<typename BV>

template<typename BII>

bool bm::aggregator< BV >::combine_and_sub	(	BII	bi,
		const bvector_type_const_ptr *	bv_src_and,
		size_t	src_and_size,
		const bvector_type_const_ptr *	bv_src_sub,
		size_t	src_sub_size )

Definition at line 1225 of file bmaggregator.h.

References bm::bits_in_block, BM_ASSERT, combine_and_sub(), find_effective_sub_block_size(), bm::for_each_bit_blk(), and bm::set_sub_array_size.

◆ combine_and_sub() [2/6]

template<typename BV>

bool bm::aggregator< BV >::combine_and_sub ( bvector_type & bv_target )

Aggregate added group of vectors using fused logical AND-SUB Operation does NOT perform an explicit reset of arg group(s).

Parameters

bv_target - target vector (input is arg group 0(AND), 1(SUB) )

Returns: true if anything was found

See also: add, reset

Examples: bvsetalgebra.cpp, and sample16.cpp.

Definition at line 1044 of file bmaggregator.h.

References BM_ASSERT, and combine_and_sub().

Referenced by combine_and(), combine_and_sub(), combine_and_sub(), combine_and_sub(), combine_and_sub(), combine_and_sub(), combine_and_sub_bi(), DemoAND_OR(), DemoAND_SUB(), DemoSUB(), find_first_and_sub(), and main().

◆ combine_and_sub() [3/6]

template<typename BV>

bool bm::aggregator< BV >::combine_and_sub	(	bvector_type &	bv_target,
		bool	any )

Aggregate added group of vectors using fused logical AND-SUB Operation does NOT perform an explicit reset of arg group(s) Operation can terminate early if anything was found.

Parameters

bv_target	- target vector (input is arg group 0(AND), 1(SUB) )
any	- if true, search result will terminate of first found result

Returns: true if anything was found

See also: add, reset, find_first_and_sub

Definition at line 1056 of file bmaggregator.h.

References BM_ASSERT, and combine_and_sub().

◆ combine_and_sub() [4/6]

template<typename BV>

bool bm::aggregator< BV >::combine_and_sub	(	bvector_type &	bv_target,
		const bvector_type_const_ptr *	bv_src_and,
		size_t	src_and_size,
		const bvector_type_const_ptr *	bv_src_sub,
		size_t	src_sub_size,
		bool	any )

Fusion aggregate group of vectors using logical AND MINUS another set.

Parameters

bv_target	- target vector
bv_src_and	- array of pointers on bit-vectors for AND
src_and_size	- size of AND group
bv_src_sub	- array of pointers on bit-vectors for SUBstract
src_sub_size	- size of SUB group
any	- flag if caller needs any results asap (incomplete results)

Returns: true when found

Definition at line 1162 of file bmaggregator.h.

References BM_ASSERT, combine_and_sub(), find_effective_sub_block_size(), FULL_BLOCK_FAKE_ADDR, bm::bvector< Alloc >::opt_compress, resize_target(), and bm::set_sub_array_size.

◆ combine_and_sub() [5/6]

template<typename BV>

template<class TPipe>

void bm::aggregator< BV >::combine_and_sub ( TPipe & pipe )

Run AND-SUB: AND (groups1) AND NOT ( OR(group0)) for a pipeline.

Parameters

pipe	- pipeline to run (should be prepared, filled and complete

Definition at line 1292 of file bmaggregator.h.

References bm::aggregator< BV >::arg_groups::arg_bv0, bm::aggregator< BV >::arg_groups::arg_bv1, bm::bit_block_count(), BM_ASSERT, bm::BM_GAP, combine_and_sub(), FULL_BLOCK_FAKE_ADDR, bm::gap_max_bits, bm::get_block_coord(), bm::bvector< Alloc >::opt_compress, reset_vars(), bm::set_block_shift, and bm::set_sub_array_size.

◆ combine_and_sub() [6/6]

template<typename BV>

aggregator< BV >::digest_type bm::aggregator< BV >::combine_and_sub	(	unsigned	i,
		unsigned	j,
		const bvector_type_const_ptr *	bv_src_and,
		size_t	src_and_size,
		const bvector_type_const_ptr *	bv_src_sub,
		size_t	src_sub_size,
		int *	is_result_full,
		bool	find_all )

protected

Definition at line 1720 of file bmaggregator.h.

References BM_ASSERT, FULL_BLOCK_FAKE_ADDR, FULL_BLOCK_REAL_ADDR, bm::gap_test_unr(), process_bit_blocks_and(), process_bit_blocks_sub(), process_gap_blocks_and(), process_gap_blocks_sub(), sort_input_blocks_and(), sort_input_blocks_or(), and bm::word_bitcount64().

◆ combine_and_sub_bi()

template<typename BV>

template<typename BII>

bool bm::aggregator< BV >::combine_and_sub_bi ( BII bi )

Aggregate added group of vectors using fused logical AND-SUB.

search traget is back_inserter

Definition at line 1068 of file bmaggregator.h.

References combine_and_sub().

◆ combine_and_sub_horizontal()

template<typename BV>

void bm::aggregator< BV >::combine_and_sub_horizontal	(	bvector_type &	bv_target,
		const bvector_type_const_ptr *	bv_src_and,
		size_t	src_and_size,
		const bvector_type_const_ptr *	bv_src_sub,
		size_t	src_sub_size )

Horizontal AND-SUB aggregation (potentially slower) method.

Parameters

bv_target	- target vector
bv_src_and	- array of pointers on bit-vector to AND aggregate
src_and_size	- size of bv_src_and
bv_src_sub	- array of pointers on bit-vector to SUB aggregate
src_sub_size	- size of bv_src_sub

Definition at line 2456 of file bmaggregator.h.

References BM_ASSERT, and combine_and_horizontal().

◆ combine_or() [1/3]

template<typename BV>

void bm::aggregator< BV >::combine_or ( bvector_type & bv_target )

Aggregate added group of vectors using logical OR Operation does NOT perform an explicit reset of arg group(s).

Parameters

bv_target - target vector (input is arg group 0)

See also: add, reset

Examples: bvsetalgebra.cpp, and sample16.cpp.

Definition at line 1021 of file bmaggregator.h.

References BM_ASSERT, and bm::combine_or().

Referenced by DemoOR(), and main().

◆ combine_or() [2/3]

template<typename BV>

void bm::aggregator< BV >::combine_or	(	bvector_type &	bv_target,
		const bvector_type_const_ptr *	bv_src,
		size_t	src_size )

Aggregate group of vectors using logical OR.

Parameters

bv_target	- target vector
bv_src	- array of pointers on bit-vector aggregate arguments
src_size	- size of bv_src (how many vectors to aggregate)

Definition at line 1101 of file bmaggregator.h.

References BM_ASSERT, bm::combine_or(), find_effective_sub_block_size(), and resize_target().

◆ combine_or() [3/3]

template<typename BV>

void bm::aggregator< BV >::combine_or	(	unsigned	i,
		unsigned	j,
		bvector_type &	bv_target,
		const bvector_type_const_ptr *	bv_src,
		size_t	src_size )

protected

Definition at line 1626 of file bmaggregator.h.

References BM_ASSERT, FULL_BLOCK_FAKE_ADDR, process_bit_blocks_or(), process_gap_blocks_or(), bm::set_sub_array_size, and sort_input_blocks_or().

◆ combine_or_horizontal()

template<typename BV>

void bm::aggregator< BV >::combine_or_horizontal	(	bvector_type &	bv_target,
		const bvector_type_const_ptr *	bv_src,
		size_t	src_size )

Horizontal OR aggregation (potentially slower) method.

Parameters

bv_target	- target vector
bv_src	- array of pointers on bit-vector aggregate arguments
src_size	- size of bv_src (how many vectors to aggregate)

Definition at line 2407 of file bmaggregator.h.

References BM_ASSERT, and bm::READWRITE.

◆ combine_shift_right_and() [1/3]

template<typename BV>

void bm::aggregator< BV >::combine_shift_right_and ( bvector_type & bv_target )

Aggregate added group of vectors using SHIFT-RIGHT and logical AND Operation does NOT perform an explicit reset of arg group(s).

Parameters

bv_target - target vector (input is arg group 0)

Returns: bool if anything was found

See also: add, reset

Definition at line 1089 of file bmaggregator.h.

References BM_ASSERT, and combine_shift_right_and().

Referenced by combine_shift_right_and(), combine_shift_right_and(), and run_step().

◆ combine_shift_right_and() [2/3]

template<typename BV>

bool bm::aggregator< BV >::combine_shift_right_and	(	bvector_type &	bv_target,
		const bvector_type_const_ptr *	bv_src_and,
		size_t	src_and_size,
		bool	any )

Fusion aggregate group of vectors using SHIFT right with AND.

Parameters

bv_target	- target vector
bv_src_and	- array of pointers on bit-vectors for AND masking
src_and_size	- size of AND group
any	- flag if caller needs any results asap (incomplete results)

Returns: true when found

Definition at line 2493 of file bmaggregator.h.

References any_carry_overs(), combine_shift_right_and(), prepare_shift_right_and(), bm::set_sub_array_size, and bm::set_top_array_size.

◆ combine_shift_right_and() [3/3]

template<typename BV>

bool bm::aggregator< BV >::combine_shift_right_and	(	unsigned	i,
		unsigned	j,
		bvector_type &	bv_target,
		const bvector_type_const_ptr *	bv_src,
		size_t	src_size )

protected

Definition at line 2533 of file bmaggregator.h.

References bm::bit_block_copy(), bm::bit_block_count(), bm::bit_block_set(), bm::bit_is_all_zero(), BM_ASSERT, BM_IS_GAP, BMGAP_PTR, bm::gap_add_to_bitset(), get_arg_block(), and process_shift_right_and().

◆ construct_arena()

template<typename BV>

arena * bm::aggregator< BV >::construct_arena ( )

inlinestaticprotected

Definition at line 784 of file bmaggregator.h.

Referenced by aggregator().

◆ construct_arg_group()

template<typename BV>

arg_groups * bm::aggregator< BV >::construct_arg_group ( )

inlinestaticprotected

Definition at line 796 of file bmaggregator.h.

Referenced by bm::aggregator< BV >::pipeline< Opt >::add().

◆ count()

template<typename BV>

size_type bm::aggregator< BV >::count ( ) const

inline

Definition at line 488 of file bmaggregator.h.

◆ find_effective_sub_block_size() [1/2]

template<typename BV>

unsigned bm::aggregator< BV >::find_effective_sub_block_size	(	unsigned	i,
		const bvector_type_const_ptr *	bv_src,
		size_t	src_size,
		bool	top_null_as_zero )

staticprotected

Definition at line 1557 of file bmaggregator.h.

References BM_ASSERT, BMNOEXCEPT, FULL_BLOCK_FAKE_ADDR, max_size, and bm::set_sub_array_size.

Referenced by combine_and(), combine_and_sub(), combine_and_sub(), combine_or(), find_effective_sub_block_size(), and find_first_and_sub().

◆ find_effective_sub_block_size() [2/2]

template<typename BV>

unsigned bm::aggregator< BV >::find_effective_sub_block_size	(	unsigned	i,
		const bvector_type_const_ptr *	bv_src1,
		size_t	src_size1,
		const bvector_type_const_ptr *	bv_src2,
		size_t	src_size2 )

staticprotected

Definition at line 1605 of file bmaggregator.h.

References BMNOEXCEPT, and find_effective_sub_block_size().

◆ find_first_and_sub() [1/2]

template<typename BV>

bool bm::aggregator< BV >::find_first_and_sub ( size_type & idx )

Aggregate added group of vectors using fused logical AND-SUB, find the first match.

Parameters

idx	- [out] index of the first occurence

Returns: true if anything was found

See also: combine_and_sub

Definition at line 1079 of file bmaggregator.h.

References find_first_and_sub().

Referenced by find_first_and_sub().

◆ find_first_and_sub() [2/2]

template<typename BV>

bool bm::aggregator< BV >::find_first_and_sub	(	size_type &	idx,
		const bvector_type_const_ptr *	bv_src_and,
		size_t	src_and_size,
		const bvector_type_const_ptr *	bv_src_sub,
		size_t	src_sub_size )

Definition at line 1458 of file bmaggregator.h.

References bm::bit_find_first(), bm::block_to_global_index(), BM_ASSERT, combine_and_sub(), find_effective_sub_block_size(), max_top_blocks(), bm::set_array_mask, bm::set_array_shift, bm::set_block_shift, and bm::set_sub_array_size.

◆ free_arena()

template<typename BV>

void bm::aggregator< BV >::free_arena ( arena * ar )

inlinestaticprotected

Definition at line 789 of file bmaggregator.h.

Referenced by ~aggregator().

◆ free_arg_group()

template<typename BV>

void bm::aggregator< BV >::free_arg_group ( arg_groups * arg )

inlinestaticprotected

Definition at line 802 of file bmaggregator.h.

Referenced by bm::aggregator< BV >::pipeline< Opt >::~pipeline().

◆ get_arg_block()

template<typename BV>

const bm::word_t * bm::aggregator< BV >::get_arg_block	(	const bvector_type_const_ptr *	bv_src,
		unsigned	k,
		unsigned	i,
		unsigned	j )

staticprotected

Definition at line 2673 of file bmaggregator.h.

References BMNOEXCEPT.

Referenced by combine_shift_right_and().

◆ get_cache_gap_hits()

template<typename BV>

bm::id64_t bm::aggregator< BV >::get_cache_gap_hits ( ) const

inline

Definition at line 634 of file bmaggregator.h.

◆ get_operation()

template<typename BV>

int bm::aggregator< BV >::get_operation ( ) const

inline

Get current operation code.

Definition at line 606 of file bmaggregator.h.

◆ get_operation_status()

template<typename BV>

operation_status bm::aggregator< BV >::get_operation_status ( ) const

inline

Definition at line 622 of file bmaggregator.h.

◆ get_target()

template<typename BV>

const bvector_type * bm::aggregator< BV >::get_target ( ) const

inline

Definition at line 624 of file bmaggregator.h.

Referenced by DNA_FingerprintScanner< bm::bvector<> >::FindCollection().

◆ get_temp_block()

template<typename BV>

bm::word_t * bm::aggregator< BV >::get_temp_block ( )

inline

Definition at line 626 of file bmaggregator.h.

◆ max_top_blocks()

template<typename BV>

unsigned bm::aggregator< BV >::max_top_blocks	(	const bvector_type_const_ptr *	bv_src,
		size_t	src_size )

staticprotected

Definition at line 2257 of file bmaggregator.h.

References BMNOEXCEPT.

Referenced by bm::aggregator< BV >::pipeline< Opt >::complete(), and find_first_and_sub().

◆ prepare_shift_right_and()

template<typename BV>

void bm::aggregator< BV >::prepare_shift_right_and	(	bvector_type &	bv_target,
		const bvector_type_const_ptr *	bv_src,
		size_t	src_size )

protected

Definition at line 2478 of file bmaggregator.h.

References resize_target().

Referenced by combine_shift_right_and(), and stage().

◆ process_bit_blocks_and()

template<typename BV>

aggregator< BV >::digest_type bm::aggregator< BV >::process_bit_blocks_and	(	const arena &	ar,
		digest_type	digest,
		bool	find_all )

protected

◆ process_bit_blocks_or()

template<typename BV>

bool bm::aggregator< BV >::process_bit_blocks_or	(	blocks_manager_type &	bman_target,
		unsigned	i,
		unsigned	j,
		const arena &	ar )

protected

Definition at line 1924 of file bmaggregator.h.

References bm::bit_block_copy(), bm::bit_block_or(), bm::bit_block_or_3way(), bm::bit_block_or_5way(), bm::bit_block_set(), BM_ASSERT, FULL_BLOCK_FAKE_ADDR, bm::is_bits_one(), and bm::aggregator< BV >::arena::v_arg_or_blk.

Referenced by combine_or().

◆ process_bit_blocks_sub()

template<typename BV>

aggregator< BV >::digest_type bm::aggregator< BV >::process_bit_blocks_sub	(	const arena &	ar,
		digest_type	digest )

protected

Definition at line 2125 of file bmaggregator.h.

References bm::bit_block_sub(), bm::bit_block_sub_3way(), bm::bit_block_sub_5way(), bm::bit_find_first_if_1(), bm::set_word_mask, bm::set_word_shift, bm::aggregator< BV >::arena::v_arg_or_blk, and bm::word_bitcount64().

Referenced by combine_and_sub().

◆ process_gap_blocks_and()

template<typename BV>

aggregator< BV >::digest_type bm::aggregator< BV >::process_gap_blocks_and	(	const arena &	ar,
		digest_type	digest )

protected

Definition at line 1820 of file bmaggregator.h.

References bm::bit_find_first_if_1(), bm::bit_is_all_zero(), BM_ASSERT, bm::gap_and_to_bitset(), bm::gap_test_unr(), bm::aggregator< BV >::arena::v_arg_and_blk_gap, and bm::word_bitcount64().

Referenced by combine_and(), and combine_and_sub().

◆ process_gap_blocks_or()

template<typename BV>

void bm::aggregator< BV >::process_gap_blocks_or ( const arena & ar )

protected

Definition at line 1808 of file bmaggregator.h.

References bm::gap_add_to_bitset(), and bm::aggregator< BV >::arena::v_arg_or_blk_gap.

Referenced by combine_or().

◆ process_gap_blocks_sub()

template<typename BV>

aggregator< BV >::digest_type bm::aggregator< BV >::process_gap_blocks_sub	(	const arena &	ar,
		digest_type	digest )

protected

Definition at line 1854 of file bmaggregator.h.

References bm::bit_find_first_if_1(), bm::bit_is_all_zero(), BM_ASSERT, bm::gap_sub_to_bitset(), bm::gap_test_unr(), bm::aggregator< BV >::arena::v_arg_or_blk_gap, and bm::word_bitcount64().

Referenced by combine_and_sub().

◆ process_shift_right_and()

template<typename BV>

unsigned bm::aggregator< BV >::process_shift_right_and	(	bm::word_t *BMRESTRICT	blk,
		const bm::word_t *BMRESTRICT	arg_blk,
		digest_type &BMRESTRICT	digest,
		unsigned	carry_over )

staticprotected

Returns: carry over

Definition at line 2612 of file bmaggregator.h.

References bm::bit_block_set(), bm::bit_block_shift_r1_and_unr(), BM_ASSERT, BM_IS_GAP, BMGAP_PTR, BMNOEXCEPT, BMRESTRICT, bm::calc_block_digest0(), FULL_BLOCK_REAL_ADDR, bm::gap_and_to_bitset(), and bm::set_block_size.

Referenced by combine_shift_right_and().

◆ reset()

template<typename BV>

void bm::aggregator< BV >::reset ( )

Reset aggregate groups, forget all attached vectors.

Examples: bvsetalgebra.cpp, and sample16.cpp.

Definition at line 941 of file bmaggregator.h.

References reset_range_hint(), and reset_vars().

Referenced by DemoAND(), DemoAND_SUB(), DemoOR(), DemoSUB(), and main().

◆ reset_range_hint()

template<typename BV>

void bm::aggregator< BV >::reset_range_hint ( )

Reset range hint to false.

Definition at line 962 of file bmaggregator.h.

References BMNOEXCEPT, and bm::id_max.

Referenced by reset().

◆ reset_vars()

template<typename BV>

void bm::aggregator< BV >::reset_vars ( )

protected

Definition at line 950 of file bmaggregator.h.

References op_undefined.

Referenced by combine_and_sub(), and reset().

◆ resize_target()

template<typename BV>

unsigned bm::aggregator< BV >::resize_target	(	bvector_type &	bv_target,
		const bvector_type_const_ptr *	bv_src,
		size_t	src_size,
		bool	init_clear = true )

staticprotected

Definition at line 2210 of file bmaggregator.h.

References BM_ASSERT.

Referenced by combine_and(), combine_and_sub(), combine_or(), and prepare_shift_right_and().

◆ run_step()

template<typename BV>

aggregator< BV >::operation_status bm::aggregator< BV >::run_step	(	unsigned	i,
		unsigned	j )

Run a step of current arrgegation operation.

Definition at line 2720 of file bmaggregator.h.

References any_carry_overs(), BM_ASSERT, BM_NOT_DEFINED, BM_SHIFT_R_AND, combine_shift_right_and(), op_done, op_in_progress, op_prepared, and bm::set_sub_array_size.

◆ set_compute_count()

template<typename BV>

void bm::aggregator< BV >::set_compute_count ( bool count_mode )

inline

Definition at line 363 of file bmaggregator.h.

◆ set_operation()

template<typename BV>

void bm::aggregator< BV >::set_operation ( int op_code )

inline

Set operation code for the aggregator.

Definition at line 609 of file bmaggregator.h.

◆ set_optimization()

template<typename BV>

void bm::aggregator< BV >::set_optimization ( typename bvector_type::optmode opt = bvector_type::opt_compress )

inline

set on-the-fly bit-block compression By default aggregator does not try to optimize result, but in some cases it can be quite a lot faster than calling bvector<>::optimize() later (because block data sits in CPU cache).

Parameters

opt	- optimization mode (full compression by default)

Examples: bvsetalgebra.cpp.

Definition at line 359 of file bmaggregator.h.

Referenced by DemoAND(), DemoAND_SUB(), DemoOR(), and DemoSUB().

◆ set_range_hint()

template<typename BV>

bool bm::aggregator< BV >::set_range_hint	(	size_type	from,
		size_type	to )

Set search hint for the range, where results needs to be searched (experimental for internal use).

Returns: true if range is one-block bound

Definition at line 974 of file bmaggregator.h.

References BMNOEXCEPT, bm::gap_init_range_block(), bm::set_block_mask, and bm::set_block_shift.

◆ sort_input_blocks_and()

template<typename BV>

bm::word_t * bm::aggregator< BV >::sort_input_blocks_and	(	const bvector_type_const_ptr *	bv_src,
		size_t	src_size,
		unsigned	i,
		unsigned	j )

protected

Definition at line 2315 of file bmaggregator.h.

References BM_ASSERT, BM_IS_GAP, BMGAP_PTR, FULL_BLOCK_FAKE_ADDR, and FULL_BLOCK_REAL_ADDR.

Referenced by combine_and(), and combine_and_sub().

◆ sort_input_blocks_or()

template<typename BV>

bm::word_t * bm::aggregator< BV >::sort_input_blocks_or	(	const bvector_type_const_ptr *	bv_src,
		size_t	src_size,
		unsigned	i,
		unsigned	j )

protected

Definition at line 2278 of file bmaggregator.h.

References BM_IS_GAP, BMGAP_PTR, and FULL_BLOCK_FAKE_ADDR.

Referenced by combine_and_sub(), and combine_or().

◆ stage()

template<typename BV>

void bm::aggregator< BV >::stage ( bm::word_t * temp_block )

Prepare operation, create internal resources, analyse dependencies.

Prerequisites are: that operation is set and all argument vectors are added

Definition at line 2696 of file bmaggregator.h.

References BM_ASSERT, BM_NOT_DEFINED, BM_SHIFT_R_AND, check_create_target(), op_prepared, and prepare_shift_right_and().

◆ test_gap_blocks_and()

template<typename BV>

bool bm::aggregator< BV >::test_gap_blocks_and	(	size_t	block_count,
		unsigned	bit_idx )

protected

Definition at line 1895 of file bmaggregator.h.

References bm::gap_test_unr().

◆ test_gap_blocks_sub()

template<typename BV>

bool bm::aggregator< BV >::test_gap_blocks_sub	(	size_t	block_count,
		unsigned	bit_idx )

protected

Definition at line 1907 of file bmaggregator.h.

References bm::gap_test_unr().

The documentation for this class was generated from the following file:

bmaggregator.h

Data Structures

Public Types

Public Member Functions

Execition metrics and telemetry

Detailed Description

Member Typedef Documentation

◆ allocator_pool_type

◆ allocator_type

◆ arg_groups_type_ptr

◆ arg_vector_type

◆ block_idx_type

◆ block_ij_vector_type

◆ block_ptr_vector_type

◆ blockptr_vector_type

◆ blocks_manager_type

◆ bv_count_vector_type

◆ bv_vector_type

◆ bvect_vector_type

◆ bvector_type

◆ bvector_type_const_ptr

◆ count_vector_type

◆ digest_type

◆ gap_block_ptr_vector_type

◆ index_vector_type

◆ size_type

◆ uchar_vector_type

Member Enumeration Documentation

◆ operation

◆ operation_status

Constructor & Destructor Documentation

◆ aggregator()

◆ ~aggregator()

Member Function Documentation

◆ add()

◆ any_carry_overs()

◆ cache_gap_block()

◆ check_create_target()

◆ combine_and() [1/3]

◆ combine_and() [2/3]

◆ combine_and() [3/3]

◆ combine_and_horizontal()

◆ combine_and_sub() [1/6]

◆ combine_and_sub() [2/6]

◆ combine_and_sub() [3/6]

◆ combine_and_sub() [4/6]

◆ combine_and_sub() [5/6]

◆ combine_and_sub() [6/6]

◆ combine_and_sub_bi()

◆ combine_and_sub_horizontal()

◆ combine_or() [1/3]

◆ combine_or() [2/3]

◆ combine_or() [3/3]

◆ combine_or_horizontal()

◆ combine_shift_right_and() [1/3]

◆ combine_shift_right_and() [2/3]

◆ combine_shift_right_and() [3/3]

◆ construct_arena()

◆ construct_arg_group()

◆ count()

◆ find_effective_sub_block_size() [1/2]

◆ find_effective_sub_block_size() [2/2]

◆ find_first_and_sub() [1/2]

◆ find_first_and_sub() [2/2]

◆ free_arena()

◆ free_arg_group()

◆ get_arg_block()

◆ get_cache_gap_hits()

◆ get_operation()

◆ get_operation_status()

◆ get_target()

◆ get_temp_block()

◆ max_top_blocks()

◆ prepare_shift_right_and()

◆ process_bit_blocks_and()

◆ process_bit_blocks_or()

◆ process_bit_blocks_sub()

◆ process_gap_blocks_and()

◆ process_gap_blocks_or()

◆ process_gap_blocks_sub()

◆ process_shift_right_and()