Go to the documentation of this file. 1 #ifndef BMALGO_IMPL__H__INCLUDED__
2 #define BMALGO_IMPL__H__INCLUDED__
26 #pragma warning( push )
27 #pragma warning( disable : 4311 4312 4127)
309 dmd.
result += (*gfunc)(blk, arg_blk);
637 return unsigned(dmd.
result);
707 const typename BV::blocks_manager_type& bman1 = bv1.get_blocks_manager();
708 const typename BV::blocks_manager_type& bman2 = bv2.get_blocks_manager();
710 bool is_all_and =
true;
713 bm::word_t*** blk_root = bman1.top_blocks_root();
714 typename BV::size_type block_idx = 0;
720 unsigned top_block_size = bman1.top_block_size();
721 unsigned ebs2 = bman2.top_block_size();
723 if (ebs2 > top_block_size)
726 top_size = top_block_size;
728 for (i = 0; i < top_size; ++i)
730 bm::word_t** blk_blk = (blk_root && (i < top_block_size)) ? blk_root[i] : 0;
739 const bm::word_t*
const* bvbb = bman2.get_topblock(i);
749 arg_blk = bman2.get_block(i, j);
761 blk = bman1.get_block(i, j);
762 if (blk == 0 && is_all_and)
765 arg_blk = bman2.get_block(i, j);
792 const typename BV::blocks_manager_type& bman1 = bv1.get_blocks_manager();
793 const typename BV::blocks_manager_type& bman2 = bv2.get_blocks_manager();
795 if (!bman1.is_init() || !bman2.is_init())
798 bm::word_t*** blk_root = bman1.top_blocks_root();
799 bm::word_t*** blk_root_arg = bman2.top_blocks_root();
800 typename BV::size_type count = 0;
802 unsigned top_block_size =
803 bm::min_value(bman1.top_block_size(),bman2.top_block_size());
805 for (
unsigned i = 0; i < top_block_size; ++i)
809 if ((blk_blk = blk_root[i]) == 0 || (blk_blk_arg= blk_root_arg[i]) == 0)
819 (blk_blk[j] && blk_blk_arg[j]) ?
822 (blk_blk[j+1] && blk_blk_arg[j+1]) ?
825 (blk_blk[j+2] && blk_blk_arg[j+2]) ?
828 (blk_blk[j+3] && blk_blk_arg[j+3]) ?
863 const typename BV::blocks_manager_type& bman1 = bv1.get_blocks_manager();
864 const typename BV::blocks_manager_type& bman2 = bv2.get_blocks_manager();
866 bool is_all_and =
true;
869 bm::word_t*** blk_root = bman1.top_blocks_root();
870 unsigned block_idx = 0;
878 unsigned top_block_size = bman1.top_block_size();
879 unsigned ebs2 = bman2.top_block_size();
881 if (ebs2 > top_block_size)
884 top_size = top_block_size;
886 for (i = 0; i < top_size; ++i)
888 bm::word_t** blk_blk = (blk_root && (i < top_block_size)) ? blk_root[i] : 0;
898 const bm::word_t*
const* bvbb = bman2.get_topblock(i);
910 arg_blk = bman2.get_block(i, j);
920 bool all_resolved =
false;
926 all_resolved =
false;
930 }
while (it < dmit_end);
940 blk = bman1.get_block(i, j);
941 if (blk == 0 && is_all_and)
944 arg_blk = bman2.get_block(i, j);
946 if (blk == 0 && arg_blk == 0)
957 bool all_resolved =
true;
963 all_resolved =
false;
967 }
while (it < dmit_end);
986 typename BV::size_type
count_and(
const BV& bv1,
const BV& bv2)
999 typename BV::size_type
any_and(
const BV& bv1,
const BV& bv2)
1034 typename BV::size_type
any_xor(
const BV& bv1,
const BV& bv2)
1052 typename BV::size_type
count_sub(
const BV& bv1,
const BV& bv2)
1069 typename BV::size_type
any_sub(
const BV& bv1,
const BV& bv2)
1086 typename BV::size_type
count_or(
const BV& bv1,
const BV& bv2)
1102 typename BV::size_type
any_or(
const BV& bv1,
const BV& bv2)
1115 template<
typename It,
typename SIZE_TYPE>
1118 SIZE_TYPE m = *max_id;
1120 for (right = first; right != last; ++right)
1122 SIZE_TYPE v = SIZE_TYPE(*right);
1147 template<
class BV,
class It>
1150 typedef typename BV::size_type size_type;
1151 typename BV::blocks_manager_type& bman = bv.get_blocks_manager();
1152 if (!bman.is_init())
1155 size_type max_id = 0;
1157 while (first < last)
1161 if (max_id >= bv.size())
1164 bv.resize(max_id + 1);
1173 bman.check_allocate_block(nblock,
1175 bv.get_new_blocks_strat(),
1180 if (block_type == 1)
1185 for (; first < right; ++first)
1190 unsigned new_block_len =
1192 if (new_block_len > threshold)
1194 bman.extend_gap_block(nblock, gap_blk);
1202 for (; first < right; ++first)
1204 size_type pos = *first;
1208 blk[nword] |= (1u << nbit);
1228 template<
class BV,
class It>
1231 typename BV::blocks_manager_type& bman = bv.get_blocks_manager();
1232 if (!bman.is_init())
1235 typename BV::size_type max_id = 0;
1237 while (first < last)
1242 if (max_id >= bv.size())
1245 bv.resize(max_id + 1);
1254 bman.check_allocate_block(nblock,
1256 bv.get_new_blocks_strat(),
1261 if (block_type == 1)
1266 for (; first < right; ++first)
1275 unsigned new_block_len =
1277 if (new_block_len > threshold)
1279 bman.extend_gap_block(nblock, gap_blk);
1287 for (; first < right; ++first)
1292 blk[nword] ^= (1u << nbit);
1315 template<
class BV,
class It>
1318 typename BV::blocks_manager_type& bman = bv.get_blocks_manager();
1319 if (!bman.is_init())
1322 typename BV::size_type max_id = 0;
1324 while (first < last)
1329 if (max_id >= bv.size())
1332 bv.resize(max_id + 1);
1341 bman.check_allocate_block(nblock,
1343 bv.get_new_blocks_strat(),
1349 if (block_type == 1)
1354 for (; first < right; ++first)
1363 unsigned new_block_len =
1365 if (new_block_len > threshold)
1367 bman.extend_gap_block(nblock, gap_blk);
1375 for (; first < right; ++first)
1400 template<
class BV,
class It>
1403 typename BV::size_type prev = 0;
1404 for ( ;first < last; ++first)
1406 typename BV::size_type
id = *first;
1408 bv.set_bit_and(
id,
true);
1411 bv.set_range(prev,
id-1,
false);
1432 template<
class BV,
class It>
1459 const typename BV::blocks_manager_type& bman = bv.get_blocks_manager();
1461 if (!bman.is_init())
1464 bm::word_t*** blk_root = bman.top_blocks_root();
1465 typename BV::blocks_manager_type::block_count_change_func func(bman);
1466 typename BV::blocks_manager_type::block_idx_type st = 0;
1469 return func.count();
1486 template<
typename BV,
class It>
1489 typename BV::blocks_manager_type& bman = bv.get_blocks_manager();
1490 if (!bman.is_init())
1493 unsigned inp_word_size =
sizeof(*first);
1494 size_t array_size = size_t(last - first);
1495 size_t bit_cnt = array_size * inp_word_size * 8;
1500 if (bit_cnt >= bv.size())
1503 bv.set_range((
typename BV::size_type)bit_cnt, bv.size() - 1,
false);
1504 switch (inp_word_size)
1508 size_t word_cnt = array_size / 4;
1512 bman.check_allocate_block(i,
1517 if (block_type == 1)
1519 blk = bman.deoptimize_block(i);
1528 tmp = b1 | (b2 << 8u) | (b3 << 16u) | (b4 << 24u);
1530 }
while (wrd_ptr < wrd_end);
1535 size_t to_convert = size_t(last - first);
1536 for (
size_t j = 0; j < to_convert / 4; ++j)
1540 tmp = b1 | (b2 << 8u) | (b3 << 16u) | (b4 << 24u);
1545 if (first == last)
break;
1547 if (first == last)
break;
1549 if (first == last)
break;
1551 if (first == last)
break;
1556 if (first == last)
break;
1562 size_t word_cnt = array_size / 2;
1566 bman.check_allocate_block(i,
1572 blk = bman.deoptimize_block(i);
1579 tmp = b1 | (b2 << 16);
1581 }
while (wrd_ptr < wrd_end);
1586 size_t to_convert = size_t(last - first);
1587 for (
unsigned j = 0; j < to_convert / 2; ++j)
1590 tmp = b1 | (b2 << 16u);
1595 if (first == last)
break;
1597 if (first == last)
break;
1602 if (first == last)
break;
1608 size_t word_cnt = array_size;
1612 bman.check_allocate_block(i,
1617 if (block_type == 1)
1618 blk = bman.deoptimize_block(i);
1626 }
while (wrd_ptr < wrd_end);
1633 if (first == last)
break;
1638 if (first == last)
break;
1659 template<
typename Func,
typename SIZE_TYPE>
1670 SIZE_TYPE offs = offset;
1677 bit_functor.add_bits(offs, bits, cnt);
1680 }
while (block < block_end);
1694 template<
typename T,
typename Func,
typename SIZE_TYPE>
1698 const T* pcurr = buf + 1;
1699 const T* pend = buf + (*buf >> 3);
1703 bit_functor.add_range(offset, *pcurr + 1);
1706 for (++pcurr; pcurr <= pend; pcurr += 2)
1708 T prev = *(pcurr-1);
1709 bit_functor.add_range(offset + prev + 1, *pcurr - prev);
1717 #pragma warning( pop )
#define BM_VECT_ALIGN_ATTR
void for_each_gap_blk(const T *buf, SIZE_TYPE offset, Func &bit_functor)
for-each visitor, calls a special visitor functor for each 1 bit range
void combine_and(BV &bv, It first, It last)
AND Combine bitvector and the iterable sequence.
Distance metric descriptor, holds metric code and result.
const unsigned set_block_size
void for_each_bit_blk(const bm::word_t *block, SIZE_TYPE offset, Func &bit_functor)
for-each visitor, calls a special visitor functor for each 1 bit group
const unsigned set_total_blocks
#define FULL_SUB_BLOCK_REAL_ADDR
bm::id_t bit_operation_and_count(const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2)
Performs bitblock AND operation and calculates bitcount of the result.
BMFORCEINLINE unsigned gap_count_and(const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2)
GAP bitcount AND operation test.
void combine_count_operation_with_block(const bm::word_t *blk, const bm::word_t *arg_blk, distance_metric_descriptor *dmit, distance_metric_descriptor *dmit_end)
Internal function computes different distance metrics.
BV::size_type any_sub(const BV &bv1, const BV &bv2)
Computes if there is any bit in SUB operation of two bitsets.
bm::id_t bit_operation_sub_count(const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2)
Performs bitblock SUB operation and calculates bitcount of the result.
BV::size_type any_or(const BV &bv1, const BV &bv2)
Computes if there is any bit in OR operation of two bitsets.
bm::id_t bit_operation_xor_any(const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2)
Performs bitblock XOR operation test.
BMFORCEINLINE bool gap_is_all_zero(const bm::gap_word_t *buf)
Checks if GAP block is all-zero.
distance_metric_descriptor()
BMFORCEINLINE unsigned gap_count_or(const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2)
GAP bitcount OR operation test.
unsigned long long int id64_t
BV::size_type any_xor(const BV &bv1, const BV &bv2)
Computes if there is any bit in XOR operation of two bitsets.
bm::id_t bit_block_count(const bm::word_t *block)
Bitcount for bit block.
const unsigned set_word_shift
void distance_operation_any(const BV &bv1, const BV &bv2, distance_metric_descriptor *dmit, distance_metric_descriptor *dmit_end)
Distance screening template function.
const unsigned set_sub_array_size
void gap_convert_to_bitset(unsigned *dest, const T *buf)
GAP block to bitblock conversion.
bm::id_t gap_bitset_xor_any(const unsigned *block, const T *buf)
Compute bitcount test of bit block XOR masked by GAP block.
const unsigned short set_bitscan_wave_size
T min_value(T v1, T v2)
Get minimum of 2 values.
BV::size_type count_intervals(const BV &bv)
Compute number of bit intervals (GAPs) in the bitvector.
@ COUNT_OR
(A | B).count()
bm::id_t gap_bitset_and_any(const unsigned *block, const T *pcurr)
Bitcount test of bit block AND masked by GAP block.
BMFORCEINLINE unsigned gap_operation_any_sub(const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2)
GAP SUB operation test.
unsigned gap_set_value(unsigned val, T *BMRESTRICT buf, unsigned pos, unsigned *BMRESTRICT is_set)
Sets or clears bit in the GAP buffer.
const unsigned set_block_mask
void export_array(BV &bv, It first, It last)
Export bitset from an array of binary data representing the bit vector.
void distance_operation(const BV &bv1, const BV &bv2, distance_metric_descriptor *dmit, distance_metric_descriptor *dmit_end)
Distance computing template function.
bm::distance_metric_descriptor::size_type count_xor(const BV &bv1, const BV &bv2)
Computes bitcount of XOR operation of two bitsets.
void combine_and_sorted(BV &bv, It first, It last)
AND Combine bitvector and the iterable sequence.
@ BM_BIT
No GAP compression strategy. All new blocks are bit blocks.
bm::id_t gap_bitset_sub_any(const unsigned *block, const T *buf)
Compute bitcount test of bit block SUB masked by GAP block.
unsigned short bitscan_wave(const bm::word_t *w_ptr, unsigned char *bits)
Unpacks word wave (Nx 32-bit words)
BMFORCEINLINE unsigned gap_count_xor(const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2)
GAP bitcount XOR operation test.
unsigned gap_test_unr(const T *buf, const unsigned pos)
Tests if bit = pos is true. Analog of bm::gap_test with SIMD unrolling.
gap_word_t * gap_operation_or(const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2, gap_word_t *BMRESTRICT tmp_buf, unsigned &dsize)
GAP OR operation.
#define FULL_BLOCK_FAKE_ADDR
bm::id_t gap_bitset_and_count(const unsigned *block, const T *pcurr)
Compute bitcount of bit block AND masked by GAP block.
bool bit_is_all_zero(const bm::word_t *BMRESTRICT start)
Returns "true" if all bits in the block are 0.
unsigned short gap_word_t
@ COUNT_SUB_AB
(A - B).count()
set_operation
Codes of set operations.
BV::size_type any_and(const BV &bv1, const BV &bv2)
Computes if there is any bit in AND operation of two bitsets.
BMFORCEINLINE unsigned gap_operation_any_and(const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2)
GAP AND operation test.
bm::id_t gap_bitset_xor_count(const unsigned *block, const T *buf)
Compute bitcount of bit block XOR masked by GAP block.
bm::id_t bit_operation_sub_any(const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2)
Performs bitblock test of SUB operation.
It block_range_scan(It first, It last, SIZE_TYPE nblock, SIZE_TYPE *max_id)
Internal algorithms scans the input for the block range limit.
const unsigned gap_max_bits
void combine_or(BV &bv, It first, It last)
OR Combine bitvector and the iterable sequence.
bm::id_t gap_bitset_or_any(const unsigned *block, const T *buf)
Compute bitcount test of bit block OR masked by GAP block.
void distance_stage(const distance_metric_descriptor *dmit, const distance_metric_descriptor *dmit_end, bool *is_all_and)
Staging function for distance operation.
Bit manipulation primitives (internal)
void combine_any_operation_with_block(const bm::word_t *blk, unsigned gap, const bm::word_t *arg_blk, unsigned arg_gap, distance_metric_descriptor *dmit, distance_metric_descriptor *dmit_end)
Internal function computes different existense of distance metric.
bm::id_t gap_bitset_sub_count(const unsigned *block, const T *buf)
Compute bitcount of bit block SUB masked by GAP block.
const unsigned set_block_shift
bm::id_t(* bit_operation_count_func_type)(const bm::word_t *BMRESTRICT, const bm::word_t *BMRESTRICT)
unsigned combine_count_and_operation_with_block(const bm::word_t *blk, const bm::word_t *arg_blk)
Internal function computes AND distance.
#define IS_FULL_BLOCK(addr)
bool is_const_set_operation(set_operation op)
Returns true if set operation is constant (bitcount)
BV::size_type distance_and_operation(const BV &bv1, const BV &bv2)
Distance AND computing template function.
BMFORCEINLINE unsigned gap_operation_any_xor(const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2)
GAP XOR operation test.
distance_metric operation2metric(set_operation op)
Convert set operation into compatible distance metric.
@ COUNT_XOR
(A ^ B).count()
BV::size_type count_and(const BV &bv1, const BV &bv2)
Computes bitcount of AND operation of two bitsets.
BV::size_type count_or(const BV &bv1, const BV &bv2)
Computes bitcount of OR operation of two bitsets.
BMFORCEINLINE unsigned gap_count_sub(const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2)
GAP bitcount SUB (AND NOT) operation test.
distance_metric_descriptor(distance_metric m)
const unsigned set_word_mask
void combine_xor(BV &bv, It first, It last)
XOR Combine bitvector and the iterable sequence.
#define BLOCK_ADDR_SAN(addr)
@ COUNT_SUB_BA
(B - A).count()
void reset()
Sets metric result to 0.
void for_each_block(T ***root, unsigned size1, F &f, BLOCK_IDX start)
@ COUNT_AND
(A & B).count()
bm::id_t gap_bitset_or_count(const unsigned *block, const T *buf)
Compute bitcount of bit block OR masked by GAP block.
bm::id_t bit_operation_or_any(const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2)
Performs bitblock OR operation test.
BV::size_type count_sub(const BV &bv1, const BV &bv2)
Computes bitcount of SUB operation of two bitsets.
bm::id_t bit_operation_and_any(const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2)
Performs bitblock AND operation test.
void combine_sub(BV &bv, It first, It last)
SUB Combine bitvector and the iterable sequence.
unsigned gap_bit_count_unr(const T *buf)
Calculates number of bits ON in GAP buffer. Loop unrolled version.
unsigned gap_limit(const T *buf, const T *glevel_len)
Returs GAP block capacity limit.
distance_metric
Distance metrics codes defined for vectors A and B.
const unsigned gap_max_buff_len
static bit_operation_count_func_type bit_operation_count(unsigned i)