bm::aggregator< BV > Class Template Reference
BitMagic Library » bvector<> container » bvector<> algorithms

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 )

static protected

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

inline static protected

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

inline static protected

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 )

static protected

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 )

static protected

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

inline static protected

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

inline static protected

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 )

static protected

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 )

static protected

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

Definition at line 1994 of file bmaggregator.h.

References bm::bit_block_and(), bm::bit_block_and_2way(), bm::bit_block_and_3way(), bm::bit_block_and_5way(), bm::bit_block_copy(), bm::bit_block_init_and_2way(), bm::bit_find_first_if_1(), bm::block_init_digest0(), bm::calc_block_digest0(), bm::digest_mask(), bm::set_block_mask, bm::set_block_shift, bm::set_word_mask, bm::set_word_shift, bm::aggregator< BV >::arena::v_arg_and_blk, and bm::word_bitcount64().

Referenced by combine_and(), and combine_and_sub().

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

static protected

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 )

static protected

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