NCBI C++ ToolKit
Classes | Public Types | List of all members
bm::aggregator< BV > Class Template Reference

Search Toolkit Book for bm::aggregator

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

#include <util/bitset/bmaggregator.h>

+ Inheritance diagram for bm::aggregator< BV >:
+ Collaboration diagram for bm::aggregator< BV >:

Classes

struct  arena
 Temporary operations vectors. More...
 
struct  arg_groups
 Aggregator arg groups. More...
 
class  pipeline
 Pipeline vector for running a group of aggregation operations on a family of vectors. More...
 
struct  pipeline_bcache
 Block cache for pipeline execution. More...
 
struct  run_options
 Aggregation options for runtime control. More...
 
struct  tb_arena
 Alllocated blocka of scratch memory. 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_typebvector_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, truebv_vector_type
 
typedef bm::heap_vector< bvector_type *, allocator_type, truebvect_vector_type
 
typedef bm::heap_vector< size_t, allocator_type, trueindex_vector_type
 
typedef arg_groupsarg_groups_type_ptr
 
typedef bm::heap_vector< arg_groups_type_ptr, allocator_type, truearg_vector_type
 
typedef bm::heap_vector< unsigned, allocator_type, truecount_vector_type
 
typedef bm::heap_vector< size_type, allocator_type, truebv_count_vector_type
 
typedef bm::heap_vector< bm::word_t *, allocator_type, trueblockptr_vector_type
 
typedef bm::heap_vector< bm::pair< unsigned, unsigned >, allocator_type, trueblock_ij_vector_type
 

Public Member Functions

Construction and setup
 aggregator ()
 
 ~aggregator ()
 
void set_optimization (typename bvector_type::optmode opt=bvector_type::opt_compress) noexcept
 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...
 
void set_compute_count (bool count_mode) noexcept
 
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). More...
 
void reset ()
 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...
 
template<class TPipe >
void combine_and_sub (TPipe &pipe)
 Run AND-SUB: AND (groups1) AND NOT ( OR(group0)) for a pipeline. 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...
 
template<typename BII >
bool combine_and_sub_bi (BII bi)
 Aggregate added group of vectors using fused logical AND-SUB. More...
 
bool find_first_and_sub (size_type &idx)
 Aggregate added group of vectors using fused logical AND-SUB, find the first match. More...
 
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...
 
bool set_range_hint (size_type from, size_type to) noexcept
 Set search hint for the range, where results needs to be searched (experimental for internal use). More...
 
void reset_range_hint () noexcept
 Reset range hint to false. More...
 
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. More...
 
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. More...
 
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. More...
 
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. 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, size_t src_size)
 Horizontal OR aggregation (potentially slower) method. More...
 
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. More...
 
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. More...
 
Pipeline operations
int get_operation () const noexcept
 Get current operation code. More...
 
void set_operation (int op_code) noexcept
 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_typeget_target () const noexcept
 
bm::word_tget_temp_block () noexcept
 

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, trueblock_ptr_vector_type
 
typedef bm::heap_vector< const bm::gap_word_t *, allocator_type, truegap_block_ptr_vector_type
 
typedef bm::heap_vector< unsigned char, allocator_type, trueuchar_vector_type
 
arg_groups ag_
 aggregator argument groups More...
 
tb_arenatb_ar_
 data arena ptr (heap allocated) More...
 
arenaar_
 data arena ptr More...
 
allocator_pool_type pool_
 pool for operations with cyclic mem.use More...
 
bm::word_ttemp_blk_ = 0
 external temp block ptr More...
 
int operation_ = 0
 operation code (default: not defined) More...
 
operation_status operation_status_ { operation_status::op_undefined }
 
bvector_typebv_target_ = 0
 target bit-vector More...
 
unsigned top_block_size_ = 0
 operation top block (i) size More...
 
pipeline_bcachebcache_ptr_ = 0
 
bool range_set_ = false
 pipeline blocks cache ptr More...
 
size_type range_from_ = bm::id_max
 search from More...
 
size_type range_to_ = bm::id_max
 search to More...
 
bm::gap_word_t range_gap_blk_ [5] {0,}
 temp GAP range block More...
 
bool is_single_bit_ = false
 single bit flag More...
 
unsigned single_bit_idx_ = 0
 
bvector_type::optmode opt_mode_
 perform search result optimization More...
 
bool compute_count_
 compute search result count More...
 
size_type count_
 search result count More...
 
bm::id64_t gap_cache_cnt_ = 0
 
bm::id64_t get_cache_gap_hits () const noexcept
 
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_tsort_input_blocks_or (const bvector_type_const_ptr *bv_src, size_t src_size, unsigned i, unsigned j)
 
bm::word_tsort_input_blocks_and (const bvector_type_const_ptr *bv_src, size_t src_size, unsigned i, unsigned j)
 
bm::word_tcache_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_typecheck_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) noexcept
 
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) noexcept
 
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) noexcept
 
static bool any_carry_overs (const unsigned char *carry_overs, size_t co_size) noexcept
 
static unsigned process_shift_right_and (bm::word_t *blk, const bm::word_t *arg_blk, digest_type &digest, unsigned carry_over) noexcept
 
static const bm::word_tget_arg_block (const bvector_type_const_ptr *bv_src, unsigned k, unsigned i, unsigned j) noexcept
 
static arenaconstruct_arena ()
 
static void free_arena (arena *ar) noexcept
 
static arg_groupsconstruct_arg_group ()
 
static void free_arg_group (arg_groups *arg)
 
 aggregator (const aggregator &)=delete
 
aggregatoroperator= (const aggregator &)=delete
 

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

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

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

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

Definition at line 187 of file bmaggregator.h.

◆ bv_vector_type

Definition at line 132 of file bmaggregator.h.

◆ 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

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 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() [1/2]

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

◆ ~aggregator()

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

Definition at line 928 of file bmaggregator.h.

References bm::aligned_free(), and BM_ASSERT.

◆ aggregator() [2/2]

template<typename BV >
bm::aggregator< BV >::aggregator ( const aggregator< BV > &  )
privatedelete

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

Definition at line 1013 of file bmaggregator.h.

Referenced by agg_shift_right_and(), AggregatorTest(), BvectorShiftTest(), and StressTestAggregatorShiftAND().

◆ any_carry_overs()

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

Definition at line 2683 of file bmaggregator.h.

References i.

◆ 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

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

◆ 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

Definition at line 1030 of file bmaggregator.h.

References BM_ASSERT.

Referenced by AggregatorTest(), SerializationOperation(), and StressTestAggregatorAND().

◆ 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(), and i.

◆ 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

◆ 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, i, and bm::READWRITE.

Referenced by StressTestAggregatorAND().

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

◆ 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

Definition at line 1044 of file bmaggregator.h.

References BM_ASSERT.

Referenced by AggregatorTest(), SerializationOperation(), StressTestAggregatorAND(), and StressTestAggregatorAND_SUB().

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

◆ 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, FULL_BLOCK_FAKE_ADDR, i, 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)

◆ 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

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

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

Referenced by SerializationOperation(), and StressTestAggregatorAND().

◆ 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

Definition at line 1021 of file bmaggregator.h.

References BM_ASSERT, and bm::combine_or().

Referenced by AggregatorTest(), SerializationOperation(), and StressTestAggregatorOR().

◆ 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(), and i.

◆ 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, i, and bm::set_sub_array_size.

◆ 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, i, and bm::READWRITE.

Referenced by StressTestAggregatorOR().

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

Referenced by agg_shift_right_and(), AggregatorTest(), BvectorShiftTest(), and StressTestAggregatorShiftAND().

◆ 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 bool, i, 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

◆ construct_arena()

template<typename BV >
static arena* bm::aggregator< BV >::construct_arena ( )
inlinestaticprotected

Definition at line 784 of file bmaggregator.h.

Referenced by bm::aggregator< BV >::aggregator().

◆ construct_arg_group()

template<typename BV >
static arg_groups* bm::aggregator< BV >::construct_arg_group ( )
inlinestaticprotected

Definition at line 796 of file bmaggregator.h.

◆ count()

template<typename BV >
size_type bm::aggregator< BV >::count ( ) const
inline

Definition at line 488 of file bmaggregator.h.

Referenced by BvectorShiftTest(), and StressTestAggregatorShiftAND().

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

Definition at line 1557 of file bmaggregator.h.

References BM_ASSERT, FULL_BLOCK_FAKE_ADDR, i, and bm::set_sub_array_size.

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

Definition at line 1605 of file bmaggregator.h.

References i.

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

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

◆ free_arena()

template<typename BV >
static void bm::aggregator< BV >::free_arena ( arena ar)
inlinestaticprotectednoexcept

Definition at line 789 of file bmaggregator.h.

◆ free_arg_group()

template<typename BV >
static void bm::aggregator< BV >::free_arg_group ( arg_groups arg)
inlinestaticprotected

Definition at line 802 of file bmaggregator.h.

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

Definition at line 2673 of file bmaggregator.h.

References i.

◆ get_cache_gap_hits()

template<typename BV >
bm::id64_t bm::aggregator< BV >::get_cache_gap_hits ( ) const
inlinenoexcept

Definition at line 634 of file bmaggregator.h.

Referenced by AggregatorTest().

◆ get_operation()

template<typename BV >
int bm::aggregator< BV >::get_operation ( ) const
inlinenoexcept

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
inlinenoexcept

Definition at line 624 of file bmaggregator.h.

◆ get_temp_block()

template<typename BV >
bm::word_t* bm::aggregator< BV >::get_temp_block ( )
inlinenoexcept

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

Definition at line 2257 of file bmaggregator.h.

References i.

◆ operator=()

template<typename BV >
aggregator& bm::aggregator< BV >::operator= ( const aggregator< BV > &  )
privatedelete

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

◆ 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

◆ 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

◆ 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

◆ process_gap_blocks_or()

template<typename BV >
void bm::aggregator< BV >::process_gap_blocks_or ( const arena ar)
protected

◆ 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

◆ process_shift_right_and()

template<typename BV >
unsigned bm::aggregator< BV >::process_shift_right_and ( bm::word_t blk,
const bm::word_t arg_blk,
digest_type digest,
unsigned  carry_over 
)
staticprotectednoexcept

◆ reset()

template<typename BV >
void bm::aggregator< BV >::reset

Reset aggregate groups, forget all attached vectors.

Definition at line 941 of file bmaggregator.h.

Referenced by agg_shift_right_and(), AggregatorTest(), and StressTestAggregatorShiftAND().

◆ reset_range_hint()

template<typename BV >
void bm::aggregator< BV >::reset_range_hint
noexcept

Reset range hint to false.

Definition at line 962 of file bmaggregator.h.

References bm::id_max.

◆ reset_vars()

template<typename BV >
void bm::aggregator< BV >::reset_vars
protected

Definition at line 950 of file bmaggregator.h.

◆ 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, i, and ncbi::grid::netcache::search::fields::size.

◆ 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 BM_ASSERT, i, and bm::set_sub_array_size.

◆ set_compute_count()

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

Definition at line 363 of file bmaggregator.h.

Referenced by AggregatorTest(), BvectorShiftTest(), and StressTestAggregatorShiftAND().

◆ set_operation()

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

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

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)

Definition at line 359 of file bmaggregator.h.

Referenced by AggregatorTest(), SerializationOperation(), StressTestAggregatorAND(), StressTestAggregatorOR(), and StressTestAggregatorShiftAND().

◆ set_range_hint()

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

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 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, FULL_BLOCK_REAL_ADDR, and i.

◆ 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, FULL_BLOCK_FAKE_ADDR, and i.

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

◆ 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 b, bm::gap_test_unr(), and i.

◆ 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 b, bm::gap_test_unr(), and i.

Member Data Documentation

◆ ag_

template<typename BV >
arg_groups bm::aggregator< BV >::ag_
private

aggregator argument groups

Definition at line 824 of file bmaggregator.h.

◆ ar_

template<typename BV >
arena* bm::aggregator< BV >::ar_
private

data arena ptr

Definition at line 826 of file bmaggregator.h.

Referenced by bm::aggregator< BV >::aggregator().

◆ bcache_ptr_

template<typename BV >
pipeline_bcache* bm::aggregator< BV >::bcache_ptr_ = 0
private

Definition at line 834 of file bmaggregator.h.

◆ bv_target_

template<typename BV >
bvector_type* bm::aggregator< BV >::bv_target_ = 0
private

target bit-vector

Definition at line 832 of file bmaggregator.h.

Referenced by bm::aggregator< bvector_type >::get_target().

◆ compute_count_

template<typename BV >
bool bm::aggregator< BV >::compute_count_
private

compute search result count

Definition at line 849 of file bmaggregator.h.

Referenced by bm::aggregator< bvector_type >::set_compute_count().

◆ count_

template<typename BV >
size_type bm::aggregator< BV >::count_
private

search result count

Definition at line 850 of file bmaggregator.h.

Referenced by bm::aggregator< bvector_type >::count(), and bm::aggregator< bvector_type >::set_compute_count().

◆ gap_cache_cnt_

template<typename BV >
bm::id64_t bm::aggregator< BV >::gap_cache_cnt_ = 0
private

Definition at line 853 of file bmaggregator.h.

Referenced by bm::aggregator< bvector_type >::get_cache_gap_hits().

◆ is_single_bit_

template<typename BV >
bool bm::aggregator< BV >::is_single_bit_ = false
private

single bit flag

Definition at line 843 of file bmaggregator.h.

◆ operation_

template<typename BV >
int bm::aggregator< BV >::operation_ = 0
private

operation code (default: not defined)

Definition at line 830 of file bmaggregator.h.

Referenced by bm::aggregator< bvector_type >::get_operation(), and bm::aggregator< bvector_type >::set_operation().

◆ operation_status_

template<typename BV >
operation_status bm::aggregator< BV >::operation_status_ { operation_status::op_undefined }
private

◆ opt_mode_

template<typename BV >
bvector_type::optmode bm::aggregator< BV >::opt_mode_
private

perform search result optimization

Definition at line 848 of file bmaggregator.h.

Referenced by bm::aggregator< bvector_type >::set_optimization().

◆ pool_

template<typename BV >
allocator_pool_type bm::aggregator< BV >::pool_
private

pool for operations with cyclic mem.use

Definition at line 827 of file bmaggregator.h.

◆ range_from_

template<typename BV >
size_type bm::aggregator< BV >::range_from_ = bm::id_max
private

search from

Definition at line 838 of file bmaggregator.h.

◆ range_gap_blk_

template<typename BV >
bm::gap_word_t bm::aggregator< BV >::range_gap_blk_[5] {0,}
private

temp GAP range block

Definition at line 840 of file bmaggregator.h.

◆ range_set_

template<typename BV >
bool bm::aggregator< BV >::range_set_ = false
private

pipeline blocks cache ptr

range flag

Definition at line 837 of file bmaggregator.h.

◆ range_to_

template<typename BV >
size_type bm::aggregator< BV >::range_to_ = bm::id_max
private

search to

Definition at line 839 of file bmaggregator.h.

◆ single_bit_idx_

template<typename BV >
unsigned bm::aggregator< BV >::single_bit_idx_ = 0
private

Definition at line 844 of file bmaggregator.h.

◆ tb_ar_

template<typename BV >
tb_arena* bm::aggregator< BV >::tb_ar_
private

data arena ptr (heap allocated)

Definition at line 825 of file bmaggregator.h.

Referenced by bm::aggregator< BV >::aggregator(), and bm::aggregator< bvector_type >::get_temp_block().

◆ temp_blk_

template<typename BV >
bm::word_t* bm::aggregator< BV >::temp_blk_ = 0
private

external temp block ptr

Definition at line 829 of file bmaggregator.h.

◆ top_block_size_

template<typename BV >
unsigned bm::aggregator< BV >::top_block_size_ = 0
private

operation top block (i) size

Definition at line 833 of file bmaggregator.h.


The documentation for this class was generated from the following file:
Modified on Fri Apr 12 17:19:34 2024 by modify_doxy.py rev. 669887