1#ifndef BMALGO__H__INCLUDED__
2#define BMALGO__H__INCLUDED__
25#ifndef BM__H__INCLUDED__
28# error missing include (bm.h or bm64.h)
175#define BM_SCANNER_OP(x) \
176if (0 != (block = blk_blk[j+x])) \
178 if (BM_IS_GAP(block)) \
180 bm::for_each_gap_blk(BMGAP_PTR(block), (r+j+x)*bm::bits_in_block,\
185 bm::for_each_bit_blk(block, (r+j+x)*bm::bits_in_block,bit_functor); \
199template<
class BV,
class Func>
203 typedef typename BV::size_type size_type;
205 const typename BV::blocks_manager_type& bman = bv.get_blocks_manager();
206 bm::word_t*** blk_root = bman.top_blocks_root();
211 unsigned tsize = bman.top_block_size();
212 for (
unsigned i = 0; i < tsize; ++i)
227 if (!avx2_test_all_zero_wave(blk_blk + j))
235 #elif defined(BM64_SSE4)
263template<
class BV,
class Func>
265 typename BV::size_type left,
266 typename BV::size_type right,
286template <
class VCBT,
class size_type>
295 void add_bits(size_type offset,
const unsigned char* bits,
unsigned size)
297 for (
unsigned i = 0; i < size; ++i)
302 for (size_type i = 0; i < size; ++i)
329 for (
unsigned i = 0; i < size; ++i)
330 bv_.set_bit_no_check(offset + bits[i]);
335 bv_.set_range(offset, offset + size - 1);
360 typedef typename BV::size_type size_type;
362 func(handle_ptr, callback_ptr);
381 typename BV::size_type left,
382 typename BV::size_type right,
386 typedef typename BV::size_type size_type;
388 func(handle_ptr, callback_ptr);
422 void decompress(BV& bv_target,
const BV& bv_idx,
const BV& bv_src);
432 void compress(BV& bv_target,
const BV& bv_idx,
const BV& bv_src);
459 if (&bv_idx == &bv_src)
467 typedef typename BV::enumerator enumerator_t;
468 enumerator_t en_s = bv_src.first();
469 enumerator_t en_i = bv_idx.first();
474 for (; en_i.valid(); )
478 i = *en_i; s = *en_s;
485 ibuffer[b_size++] = r_idx++;
486 if (b_size == n_buffer_cap)
499 size_type r_dist = bv_idx.count_range(i + 1, s);
506 for (; s > i; ++r_idx)
532 if (&bv_idx == &bv_src)
543 typedef typename BV::enumerator enumerator_t;
544 enumerator_t en_s = bv_src.first();
545 enumerator_t en_i = bv_idx.first();
546 for (; en_i.valid(); )
554 ibuffer[b_size++] = i;
555 if (b_size == n_buffer_cap)
560 ++en_i; ++en_s; ++r_idx;
570 en_i.skip(s - r_idx);
576 bv_idx.find_rank(rank, i, new_pos);
583 ibuffer[b_size++] = new_pos;
584 if (b_size == n_buffer_cap)
589 ++en_i; ++en_s; ++r_idx;
614 : bv_target_(bv_out),
619 void add_bits(
size_type arr_offset,
const unsigned char* bits,
unsigned bits_size)
621 for (
unsigned i = 0; i < bits_size; ++i)
626 size_type r_idx = bv_index_.count_to(idx, bc_index_) - 1;
627 bv_target_.set_bit_no_check(r_idx);
637 size_type r_idx = bv_index_.count_to(idx, bc_index_) - 1;
638 bv_target_.set_bit_no_check(r_idx);
651 if (&bv_idx == &bv_src)
656 visitor_func func(bv_target, bv_idx, bc_idx);
#define FULL_BLOCK_FAKE_ADDR
#define FULL_SUB_BLOCK_REAL_ADDR
Bit manipulation primitives (internal)
pre-processor un-defines to avoid global space pollution (internal)
Algorithms for rank compression of bit-vector.
void decompress(BV &bv_target, const BV &bv_idx, const BV &bv_src)
Rank decompression.
void compress_by_source(BV &bv_target, const BV &bv_idx, const rs_index_type &bc_idx, const BV &bv_src)
Source vector priority + index based rank.
void compress(BV &bv_target, const BV &bv_idx, const BV &bv_src)
Rank compression algorithm based on two palallel iterators/enumerators set of source vector gets re-m...
BV::rs_index_type rs_index_type
BMFORCEINLINE bool sse42_test_all_zero_wave(const void *ptr)
check if wave of pointers is all NULL
int(* bit_visitor_callback_type)(void *handle_ptr, bm::id_t bit_idx)
Callback type to visit (callback style) bits in bit-vector(s)
@ BM_SORTED
input set is sorted (ascending order)
void distance_operation(const BV &bv1, const BV &bv2, distance_metric_descriptor *dmit, distance_metric_descriptor *dmit_end) BMNOEXCEPT
Distance computing template function.
void distance_operation_any(const BV &bv1, const BV &bv2, distance_metric_descriptor *dmit, distance_metric_descriptor *dmit_end) BMNOEXCEPT
Distance screening template function.
BV::size_type distance_and_operation(const BV &bv1, const BV &bv2) BMNOEXCEPT
Distance AND computing template function.
@ COUNT_XOR
(A ^ B).count()
@ COUNT_SUB_AB
(A - B).count()
@ COUNT_AND
(A & B).count()
@ COUNT_OR
(A | B).count()
void for_each_bit_range(const BV &bv, typename BV::size_type left, typename BV::size_type right, Func &bit_functor)
bit-vector range visitor to traverse each 1 bit
BV::size_type any_or(const BV &bv1, const BV &bv2) BMNOEXCEPT
Computes if there is any bit in OR operation of two bitsets.
BV::size_type any_xor(const BV &bv1, const BV &bv2) BMNOEXCEPT
Computes if there is any bit in XOR operation of two bitsets.
void visit_each_bit(const BV &bv, void *handle_ptr, bit_visitor_callback_type callback_ptr)
bvector visitor scanner to traverse each 1 bit using C callback
void visit_each_bit_range(const BV &bv, typename BV::size_type left, typename BV::size_type right, void *handle_ptr, bit_visitor_callback_type callback_ptr)
bvector visitor scanner to traverse each bits in range (C callback)
BV::size_type count_and(const BV &bv1, const BV &bv2) BMNOEXCEPT
Computes bitcount of AND operation of two bitsets.
BV::size_type count_or(const BV &bv1, const BV &bv2) BMNOEXCEPT
Computes bitcount of OR operation of two bitsets.
BV::size_type any_and(const BV &bv1, const BV &bv2) BMNOEXCEPT
Computes if there is any bit in AND operation of two bitsets.
BV::size_type count_sub(const BV &bv1, const BV &bv2) BMNOEXCEPT
Computes bitcount of SUB operation of two bitsets.
BV::size_type any_sub(const BV &bv1, const BV &bv2) BMNOEXCEPT
Computes if there is any bit in SUB operation of two bitsets.
bm::distance_metric_descriptor::size_type count_xor(const BV &bv1, const BV &bv2) BMNOEXCEPT
Computes bitcount of XOR operation of two bitsets.
void for_each_bit(const BV &bv, Func &bit_functor)
bit-vector visitor scanner to traverse each 1 bit using C++ visitor
void xor_swap(W &x, W &y) BMNOEXCEPT
XOR swap two scalar variables.
const unsigned set_sub_array_size
void for_each_bit_range_no_check(const BV &bv, typename BV::size_type left, typename BV::size_type right, Func &bit_functor)
Implementation of for_each_bit_range without boilerplave checks.
Functor for bit-copy (for testing)
void add_bits(size_type offset, const unsigned char *bits, unsigned size)
bit_vistor_copy_functor(BV &bv)
bit_visitor_callback_type func_
void add_range(size_type offset, size_type size)
private adaptor for C-style callbacks
VCBT bit_visitor_callback_type
bit_visitor_callback_type func_
void add_range(size_type offset, size_type size)
bit_vitor_callback_adaptor(void *h, bit_visitor_callback_type cb_func)
void add_bits(size_type offset, const unsigned char *bits, unsigned size)
Distance metric descriptor, holds metric code and result.