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 ret = bm::for_each_gap_blk(BMGAP_PTR(block), (r+j+x)*bm::bits_in_block,\
185 ret = bm::for_each_bit_blk(block, (r+j+x)*bm::bits_in_block,bit_functor); \
187 if (ret < 0) return ret; \
201template<
class BV,
class Func>
205 typedef typename BV::size_type size_type;
207 const typename BV::blocks_manager_type& bman = bv.get_blocks_manager();
208 bm::word_t*** blk_root = bman.top_blocks_root();
213 unsigned tsize = bman.top_block_size();
214 for (
unsigned i = 0; i < tsize; ++i)
237 #elif defined(BM64_SSE4)
265template<
class BV,
class Func>
267 typename BV::size_type left,
268 typename BV::size_type right,
305 for (
unsigned i = 0; i < size; ++i)
306 bv_.set_bit_no_check(offset + bits[i]);
312 bv_.set_range(offset, offset + size - 1);
340 typedef typename BV::size_type size_type;
342 func(handle_ptr, callback_ptr);
363 typename BV::size_type left,
364 typename BV::size_type right,
368 typedef typename BV::size_type size_type;
370 func(handle_ptr, callback_ptr);
393template<
typename BV,
typename PairVect>
395 typename BV::size_type rank,
399 typename BV::size_type first, last, pos;
400 bool found = bv.find_range(first, last);
406 typename PairVect::value_type pv;
407 pv.first = first; pv.second = last;
408 target_v.push_back(pv);
414 typename PairVect::value_type pv;
415 found = bv.find_rank(rank, first, pos);
418 pv.first = first; pv.second = pos;
419 target_v.push_back(pv);
426 found = bv.any_range(first, last);
429 pv.first = first; pv.second = last;
430 target_v.push_back(pv);
467 void decompress(BV& bv_target,
const BV& bv_idx,
const BV& bv_src);
477 void compress(BV& bv_target,
const BV& bv_idx,
const BV& bv_src);
504 if (&bv_idx == &bv_src)
512 typedef typename BV::enumerator enumerator_t;
513 enumerator_t en_s = bv_src.first();
514 enumerator_t en_i = bv_idx.first();
519 for (; en_i.valid(); )
523 i = *en_i; s = *en_s;
530 ibuffer[b_size++] = r_idx++;
531 if (b_size == n_buffer_cap)
544 size_type r_dist = bv_idx.count_range(i + 1, s);
551 for (; s > i; ++r_idx)
577 if (&bv_idx == &bv_src)
588 typedef typename BV::enumerator enumerator_t;
589 enumerator_t en_s = bv_src.first();
590 enumerator_t en_i = bv_idx.first();
591 for (; en_i.valid(); )
599 ibuffer[b_size++] = i;
600 if (b_size == n_buffer_cap)
605 ++en_i; ++en_s; ++r_idx;
615 en_i.skip(s - r_idx);
621 bv_idx.find_rank(rank, i, new_pos);
628 ibuffer[b_size++] = new_pos;
629 if (b_size == n_buffer_cap)
634 ++en_i; ++en_s; ++r_idx;
659 : bv_target_(bv_out),
664 int add_bits(
size_type arr_offset,
const unsigned char* bits,
unsigned bits_size)
666 for (
unsigned i = 0; i < bits_size; ++i)
671 size_type r_idx = bv_index_.count_to(idx, bc_index_) - 1;
672 bv_target_.set_bit_no_check(r_idx);
683 size_type r_idx = bv_index_.count_to(idx, bc_index_) - 1;
684 bv_target_.set_bit_no_check(r_idx);
698 if (&bv_idx == &bv_src)
703 visitor_func func(bv_target, bv_idx, bc_idx);
#define FULL_BLOCK_FAKE_ADDR
#define FULL_SUB_BLOCK_REAL_ADDR
Bit manipulation primitives (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 avx2_test_all_zero_wave(const void *ptr)
check if wave of pointers is all NULL
BMFORCEINLINE bool sse42_test_all_zero_wave(const void *ptr) BMNOEXCEPT
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 rank_range_split(const BV &bv, typename BV::size_type rank, PairVect &target_v)
Algorithm to identify bit-vector ranges (splits) for the rank.
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.
int 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
int 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.
int 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
int for_each_bit(const BV &bv, Func &bit_functor)
bit-vector visitor scanner to traverse each 1 bit using C++ visitor
bm::distance_metric_descriptor::size_type count_xor(const BV &bv1, const BV &bv2) BMNOEXCEPT
Computes bitcount of XOR operation of two bitsets.
int 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.
const unsigned set_sub_array_size
BMFORCEINLINE void xor_swap(W &x, W &y) BMNOEXCEPT
XOR swap two variables.
functor-adaptor for C-style callbacks
Functor for bit-copy (for testing)
bit_vistor_copy_functor(BV &bv)
bit_visitor_callback_type func_
int add_bits(size_type offset, const unsigned char *bits, unsigned size)
int add_range(size_type offset, size_type size)
Distance metric descriptor, holds metric code and result.