BitMagic-C++
|
Algorithms for fast aggregation of a group of bit-vectors. More...
#include <bmaggregator.h>
Public Types | |
enum | max_size { max_aggregator_cap = 512 } |
Maximum aggregation capacity in one pass. More... | |
enum | operation { BM_NOT_DEFINED = 0, BM_SHIFT_R_AND = 1 } |
Codes for aggregation operations which can be pipelined for efficient execution. More... | |
enum | operation_status { op_undefined = 0, op_prepared, op_in_progress, op_done } |
typedef BV | bvector_type |
typedef BV::size_type | size_type |
typedef bm::id64_t | digest_type |
typedef bvector_type::allocator_type::allocator_pool_type | allocator_pool_type |
Public Member Functions | |
Construction and setup | |
aggregator () | |
~aggregator () | |
void | set_optimization (typename bvector_type::optmode opt=bvector_type::opt_compress) |
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). More... | |
Methods to setup argument groups and run operations on groups | |
unsigned | add (const bvector_type *bv, unsigned agr_group=0) BMNOEXCEPT |
Attach source bit-vector to a argument group (0 or 1). More... | |
void | reset () BMNOEXCEPT |
Reset aggregate groups, forget all attached vectors. More... | |
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) More... | |
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) More... | |
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) More... | |
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. More... | |
bool | find_first_and_sub (size_type &idx) |
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) More... | |
void | 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). More... | |
Logical operations (C-style interface) | |
void | combine_or (bvector_type &bv_target, const bvector_type_const_ptr *bv_src, unsigned src_size) |
Aggregate group of vectors using logical OR. More... | |
void | combine_and (bvector_type &bv_target, const bvector_type_const_ptr *bv_src, unsigned src_size) |
Aggregate group of vectors using logical AND. More... | |
bool | combine_and_sub (bvector_type &bv_target, const bvector_type_const_ptr *bv_src_and, unsigned src_and_size, const bvector_type_const_ptr *bv_src_sub, unsigned src_sub_size, bool any) |
Fusion aggregate group of vectors using logical AND MINUS another set. More... | |
bool | find_first_and_sub (size_type &idx, const bvector_type_const_ptr *bv_src_and, unsigned src_and_size, const bvector_type_const_ptr *bv_src_sub, unsigned src_sub_size) |
bool | combine_shift_right_and (bvector_type &bv_target, const bvector_type_const_ptr *bv_src_and, unsigned src_and_size, bool any) |
Fusion aggregate group of vectors using SHIFT right with AND. More... | |
Horizontal Logical operations used for tests (C-style interface) | |
void | combine_or_horizontal (bvector_type &bv_target, const bvector_type_const_ptr *bv_src, unsigned src_size) |
Horizontal OR aggregation (potentially slower) method. More... | |
void | combine_and_horizontal (bvector_type &bv_target, const bvector_type_const_ptr *bv_src, unsigned src_size) |
Horizontal AND aggregation (potentially slower) method. More... | |
void | combine_and_sub_horizontal (bvector_type &bv_target, const bvector_type_const_ptr *bv_src_and, unsigned src_and_size, const bvector_type_const_ptr *bv_src_sub, unsigned src_sub_size) |
Horizontal AND-SUB aggregation (potentially slower) method. More... | |
Data Fields | |
const typedef bvector_type * | bvector_type_const_ptr |
Pipeline operations | |
typedef bvector_type::blocks_manager_type | blocks_manager_type |
typedef BV::block_idx_type | block_idx_type |
int | get_operation () const BMNOEXCEPT |
Get current operation code. More... | |
void | set_operation (int op_code) BMNOEXCEPT |
Set operation code for the aggregator. More... | |
void | stage (bm::word_t *temp_block) |
Prepare operation, create internal resources, analyse dependencies. More... | |
operation_status | run_step (unsigned i, unsigned j) |
Run a step of current arrgegation operation. More... | |
operation_status | get_operation_status () const |
const bvector_type * | get_target () const |
bm::word_t * | get_temp_block () |
void | combine_or (unsigned i, unsigned j, bvector_type &bv_target, const bvector_type_const_ptr *bv_src, unsigned src_size) |
void | combine_and (unsigned i, unsigned j, bvector_type &bv_target, const bvector_type_const_ptr *bv_src, unsigned src_size) |
digest_type | combine_and_sub (unsigned i, unsigned j, const bvector_type_const_ptr *bv_src_and, unsigned src_and_size, const bvector_type_const_ptr *bv_src_sub, unsigned src_sub_size, int *is_result_full) |
void | prepare_shift_right_and (bvector_type &bv_target, const bvector_type_const_ptr *bv_src, unsigned src_size) |
bool | combine_shift_right_and (unsigned i, unsigned j, bvector_type &bv_target, const bvector_type_const_ptr *bv_src, unsigned src_size) |
bm::word_t * | sort_input_blocks_or (const bvector_type_const_ptr *bv_src, unsigned src_size, unsigned i, unsigned j, unsigned *arg_blk_count, unsigned *arg_blk_gap_count) BMNOEXCEPT |
bm::word_t * | sort_input_blocks_and (const bvector_type_const_ptr *bv_src, unsigned src_size, unsigned i, unsigned j, unsigned *arg_blk_count, unsigned *arg_blk_gap_count) BMNOEXCEPT |
bool | process_bit_blocks_or (blocks_manager_type &bman_target, unsigned i, unsigned j, unsigned block_count) |
void | process_gap_blocks_or (unsigned block_count) |
digest_type | process_bit_blocks_and (unsigned block_count, digest_type digest) |
digest_type | process_gap_blocks_and (unsigned block_count, digest_type digest) |
bool | test_gap_blocks_and (unsigned block_count, unsigned bit_idx) |
bool | test_gap_blocks_sub (unsigned block_count, unsigned bit_idx) |
digest_type | process_bit_blocks_sub (unsigned block_count, digest_type digest) |
digest_type | process_gap_blocks_sub (unsigned block_count, digest_type digest) |
bvector_type * | check_create_target () |
static unsigned | resize_target (bvector_type &bv_target, const bvector_type_const_ptr *bv_src, unsigned src_size, bool init_clear=true) |
static unsigned | max_top_blocks (const bvector_type_const_ptr *bv_src, unsigned src_size) BMNOEXCEPT |
static unsigned | find_effective_sub_block_size (unsigned i, const bvector_type_const_ptr *bv_src, unsigned src_size, bool top_null_as_zero) BMNOEXCEPT |
static bool | any_carry_overs (const unsigned char *carry_overs, unsigned 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 |
Algorithms for fast aggregation of a group of bit-vectors.
Current implementation can aggregate up to max_aggregator_cap vectors (TODO: remove this limitation)
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 ...
Definition at line 58 of file bmaggregator.h.
typedef bvector_type::allocator_type::allocator_pool_type bm::aggregator< BV >::allocator_pool_type |
Definition at line 66 of file bmaggregator.h.
|
protected |
Definition at line 334 of file bmaggregator.h.
|
protected |
Definition at line 333 of file bmaggregator.h.
typedef BV bm::aggregator< BV >::bvector_type |
Definition at line 61 of file bmaggregator.h.
typedef bm::id64_t bm::aggregator< BV >::digest_type |
Definition at line 64 of file bmaggregator.h.
typedef BV::size_type bm::aggregator< BV >::size_type |
Definition at line 62 of file bmaggregator.h.
enum bm::aggregator::max_size |
Maximum aggregation capacity in one pass.
Enumerator | |
---|---|
max_aggregator_cap |
Definition at line 69 of file bmaggregator.h.
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 76 of file bmaggregator.h.
enum bm::aggregator::operation_status |
Enumerator | |
---|---|
op_undefined | |
op_prepared | |
op_in_progress | |
op_done |
Definition at line 82 of file bmaggregator.h.
bm::aggregator< BV >::aggregator |
Definition at line 523 of file bmaggregator.h.
bm::aggregator< BV >::~aggregator |
Definition at line 532 of file bmaggregator.h.
unsigned 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)
bv | - input bit-vector pointer to attach |
agr_group | - input argument group (0 - default, 1 - fused op) |
Definition at line 576 of file bmaggregator.h.
Referenced by DemoAND(), DemoAND_SUB(), DemoOR(), DemoSUB(), and main().
|
staticprotected |
Definition at line 1856 of file bmaggregator.h.
|
protected |
Definition at line 563 of file bmaggregator.h.
void bm::aggregator< BV >::combine_and | ( | bvector_type & | bv_target | ) |
void bm::aggregator< BV >::combine_and | ( | bvector_type & | bv_target, |
const bvector_type_const_ptr * | bv_src, | ||
unsigned | src_size | ||
) |
Aggregate group of vectors using logical AND.
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 687 of file bmaggregator.h.
|
protected |
Definition at line 997 of file bmaggregator.h.
void bm::aggregator< BV >::combine_and_horizontal | ( | bvector_type & | bv_target, |
const bvector_type_const_ptr * | bv_src, | ||
unsigned | src_size | ||
) |
Horizontal AND aggregation (potentially slower) method.
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 1618 of file bmaggregator.h.
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)
bv_target | - target vector (input is arg group 0(AND), 1(SUB) ) |
Definition at line 625 of file bmaggregator.h.
Referenced by DemoAND_SUB(), DemoSUB(), and main().
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.
bv_target | - target vector (input is arg group 0(AND), 1(SUB) ) |
any | - if true, search result will terminate of first found result |
Definition at line 635 of file bmaggregator.h.
bool bm::aggregator< BV >::combine_and_sub | ( | bvector_type & | bv_target, |
const bvector_type_const_ptr * | bv_src_and, | ||
unsigned | src_and_size, | ||
const bvector_type_const_ptr * | bv_src_sub, | ||
unsigned | src_sub_size, | ||
bool | any | ||
) |
Fusion aggregate group of vectors using logical AND MINUS another set.
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) |
Definition at line 720 of file bmaggregator.h.
|
protected |
Definition at line 1056 of file bmaggregator.h.
void bm::aggregator< BV >::combine_and_sub_horizontal | ( | bvector_type & | bv_target, |
const bvector_type_const_ptr * | bv_src_and, | ||
unsigned | src_and_size, | ||
const bvector_type_const_ptr * | bv_src_sub, | ||
unsigned | src_sub_size | ||
) |
Horizontal AND-SUB aggregation (potentially slower) method.
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 1642 of file bmaggregator.h.
void bm::aggregator< BV >::combine_or | ( | bvector_type & | bv_target | ) |
void bm::aggregator< BV >::combine_or | ( | bvector_type & | bv_target, |
const bvector_type_const_ptr * | bv_src, | ||
unsigned | src_size | ||
) |
Aggregate group of vectors using logical OR.
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 663 of file bmaggregator.h.
|
protected |
Definition at line 949 of file bmaggregator.h.
void bm::aggregator< BV >::combine_or_horizontal | ( | bvector_type & | bv_target, |
const bvector_type_const_ptr * | bv_src, | ||
unsigned | src_size | ||
) |
Horizontal OR aggregation (potentially slower) method.
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 1594 of file bmaggregator.h.
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)
bv_target | - target vector (input is arg group 0) |
Definition at line 655 of file bmaggregator.h.
bool bm::aggregator< BV >::combine_shift_right_and | ( | bvector_type & | bv_target, |
const bvector_type_const_ptr * | bv_src_and, | ||
unsigned | src_and_size, | ||
bool | any | ||
) |
Fusion aggregate group of vectors using SHIFT right with AND.
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) |
Definition at line 1677 of file bmaggregator.h.
|
protected |
Definition at line 1715 of file bmaggregator.h.
|
staticprotected |
Definition at line 901 of file bmaggregator.h.
bool bm::aggregator< BV >::find_first_and_sub | ( | size_type & | idx | ) |
Definition at line 645 of file bmaggregator.h.
bool bm::aggregator< BV >::find_first_and_sub | ( | size_type & | idx, |
const bvector_type_const_ptr * | bv_src_and, | ||
unsigned | src_and_size, | ||
const bvector_type_const_ptr * | bv_src_sub, | ||
unsigned | src_sub_size | ||
) |
Definition at line 794 of file bmaggregator.h.
|
staticprotected |
Definition at line 1846 of file bmaggregator.h.
|
inline |
Get current operation code.
Definition at line 308 of file bmaggregator.h.
|
inline |
Definition at line 324 of file bmaggregator.h.
|
inline |
Definition at line 326 of file bmaggregator.h.
Referenced by DNA_FingerprintScanner::FindCollection().
|
inline |
Definition at line 328 of file bmaggregator.h.
|
staticprotected |
Definition at line 1479 of file bmaggregator.h.
|
protected |
Definition at line 1663 of file bmaggregator.h.
|
protected |
Definition at line 1307 of file bmaggregator.h.
|
protected |
Definition at line 1238 of file bmaggregator.h.
|
protected |
Definition at line 1391 of file bmaggregator.h.
|
protected |
Definition at line 1139 of file bmaggregator.h.
|
protected |
Definition at line 1128 of file bmaggregator.h.
|
protected |
Definition at line 1173 of file bmaggregator.h.
|
staticprotected |
Definition at line 1785 of file bmaggregator.h.
void bm::aggregator< BV >::reset |
Reset aggregate groups, forget all attached vectors.
Definition at line 542 of file bmaggregator.h.
Referenced by DemoAND(), DemoAND_SUB(), DemoOR(), DemoSUB(), and main().
|
staticprotected |
Definition at line 1430 of file bmaggregator.h.
aggregator< BV >::operation_status bm::aggregator< BV >::run_step | ( | unsigned | i, |
unsigned | j | ||
) |
Run a step of current arrgegation operation.
Definition at line 1896 of file bmaggregator.h.
|
inline |
Set operation code for the aggregator.
Definition at line 311 of file bmaggregator.h.
|
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).
opt | - optimization mode (full compression by default) |
Definition at line 105 of file bmaggregator.h.
Referenced by DemoAND(), DemoAND_SUB(), DemoOR(), and DemoSUB().
void 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).
Definition at line 553 of file bmaggregator.h.
|
protected |
Definition at line 1539 of file bmaggregator.h.
|
protected |
Definition at line 1500 of file bmaggregator.h.
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 1872 of file bmaggregator.h.
|
protected |
Definition at line 1207 of file bmaggregator.h.
|
protected |
Definition at line 1221 of file bmaggregator.h.
const typedef bvector_type* bm::aggregator< BV >::bvector_type_const_ptr |
Definition at line 63 of file bmaggregator.h.