1 #ifndef BM__H__INCLUDED__
2 #define BM__H__INCLUDED__
30 # include <initializer_list>
37 #pragma warning( push )
38 #pragma warning( disable : 4311 4312 4127)
47 # define BM_DECLARE_TEMP_BLOCK(x) bm::bit_block_t x;
113 template<
class Alloc>
297 if (this->
bv_ != ib.bv_)
return false;
298 if (this->
position_ != ib.position_)
return false;
299 if (this->
block_ != ib.block_)
return false;
300 if (this->
block_type_ != ib.block_type_)
return false;
301 if (this->
block_idx_ != ib.block_idx_)
return false;
303 const block_descr& bd = this->
bdescr_;
304 const block_descr& ib_db = ib.bdescr_;
308 if (bd.bit_.ptr != ib_db.bit_.ptr)
return false;
309 if (bd.bit_.idx != ib_db.bit_.idx)
return false;
310 if (bd.bit_.cnt != ib_db.bit_.cnt)
return false;
311 if (bd.bit_.pos != ib_db.bit_.pos)
return false;
312 for (
unsigned i = 0;
i < bd.bit_.cnt; ++
i)
314 if (bd.bit_.bits[
i] != ib_db.bit_.bits[
i])
return false;
319 if (bd.gap_.ptr != ib_db.gap_.ptr)
return false;
320 if (bd.gap_.gap_len != ib_db.gap_.gap_len)
return false;
517 buf_ = iit.buf_; iit.buf_ = 0;
538 buf_ = ii.buf_; ii.buf_ = 0;
695 return this->
valid();
743 bit_count_ = this->
valid();
751 this->bit_count_ = 1;
758 this->bit_count_ += this->
valid();
764 counted_enumerator
tmp(*
this);
766 this->bit_count_ += this->
valid();
811 : strat(s), glevel_len(glevels)
924 void init(
unsigned top_size,
bool alloc_subs);
956 std::initializer_list<size_type>::const_iterator it_start = il.begin();
957 std::initializer_list<size_type>::const_iterator it_end = il.end();
958 for (; it_start < it_end; ++it_start)
1287 insert_iterator
inserter() {
return insert_iterator(*
this); }
1944 statistics* stat = 0);
2081 const size_type ids_size,
bool opt_flag);
2207 unsigned nbit_right,
2217 unsigned nbit_right,
2234 template<class
Alloc>
2245 template<
class Alloc>
2256 template<
class Alloc>
2267 template<
class Alloc>
2279 template<
typename Alloc>
2288 template<
typename Alloc>
2295 for (
unsigned nb = 0; nb < top_size; ++nb)
2302 template<
typename Alloc>
2339 template<
typename Alloc>
2352 template<
class Alloc>
2367 template<
typename Alloc>
2400 template<
typename Alloc>
2411 for (
unsigned i = 0;
i < top_blocks; ++
i)
2420 blk_blk = blk_root[
i];
2450 template<
typename Alloc>
2462 template<
typename Alloc>
2467 if (
size_ == new_size)
return;
2468 if (
size_ < new_size)
2485 template<
typename Alloc>
2500 template<
typename Alloc>
2540 for (
unsigned i = 0;
i < max_top_blocks; ++
i)
2566 bcount[j] = 0; sub_count[j] = 0;
2569 unsigned local_first, local_second, local_third;
2591 if (is_set) aux0 |= 1;
2594 if (is_set) aux1 |= 1;
2613 unsigned cnt = local_first + local_second + local_third;
2617 if (bv_blocks &&
cnt)
2621 sub_count[j] =
bm::id64_t(local_first | (local_second << 16)) |
2622 (aux0 << 32) | (aux1 << 48);
2635 template<
typename Alloc>
2649 #define BM_BORDER_TEST(blk, idx) bool(blk[idx >> bm::set_word_shift] & (1u << (idx & bm::set_word_mask)))
2652 #if (defined(BMSSE42OPT) || defined(BMAVX2OPT) || defined(BMAVX512OPT) || \
2653 defined(BMWASMSIMDOPT) || defined(BMNEONOPT))
2656 template<
typename Alloc>
2660 unsigned nbit_right,
2667 unsigned sub_cnt = unsigned(sub);
2668 unsigned first = sub_cnt & 0xFFFF;
2669 unsigned second = sub_cnt >> 16;
2678 unsigned cnt1, aux1(
bm::gap_word_t(sub >> 48)); (void)aux1; (void) cnt1;
2683 #if defined(BM64_SSE4) || defined(BM64_AVX2) || defined(BM64_AVX512)
2686 const unsigned cutoff_bias = 0;
2689 unsigned sub_range = rs_idx.find_sub_range(nbit_right);
2699 c = bm::bit_block_calc_count_range<true, false>(block, 0, nbit_right);
2723 bm::bit_block_calc_count_range<true, false>(block,
2730 unsigned bc_second_range =
first + second;
2734 c = bc_second_range;
2748 c = bc_second_range - c;
2753 c = bm::bit_block_calc_count_range<true, false>(
2774 c = bm::bit_block_calc_count_range<true, false>(block,
2777 c +=
first + second;
2802 c = rs_idx.count(nb);
2822 c = bm::bit_block_calc_count_range<true, false>(block,
2844 template<
typename Alloc>
2848 unsigned nbit_right,
2854 unsigned sub_cnt = unsigned(sub);
2855 unsigned first = sub_cnt & 0xFFFF;
2856 unsigned second = sub_cnt >> 16;
2865 unsigned cnt1, aux1(
bm::gap_word_t(sub >> 48)); (void)aux1; (void) cnt1;
2870 unsigned sub_choice =
2876 c = bm::bit_block_calc_count_range<true, false>(block, 0, nbit_right);
2886 c = bm::bit_block_calc_count_range<true, false>(block,
2896 c =
first + second - c;
2899 c = bm::bit_block_calc_count_range<true, false>(
2907 c = bm::bit_block_calc_count_range<true, false>(block,
2910 c +=
first + second;
2923 c = rs_idx.count(nb);
2929 c = rs_idx.count(nb) - c;
2932 c = bm::bit_block_calc_count_range<true, false>(block,
2946 #undef BM_BORDER_TEST
2950 template<
typename Alloc>
2954 unsigned nbit_right,
2986 unsigned sub_cnt = unsigned(sub);
2988 unsigned second = (sub_cnt >> 16);
2997 unsigned sub_range = rs_idx.find_sub_range(nbit_right);
3043 c =
first + second - c;
3055 c +=
first + second;
3062 c = rs_idx.count(nb);
3067 c = bm::gap_bit_count_range<bm::gap_word_t, true> (gap_block,
3086 template<
typename Alloc>
3100 if (nb_right >= rs_idx.get_total())
3102 cnt = rs_idx.count();
3105 cnt = nb_right ? rs_idx.rcount(nb_right-1) : 0;
3118 c = this->
gap_count_to(gap_block, nb_right, nbit_right, rs_idx);
3124 return cnt + nbit_right + 1;
3139 template<
typename Alloc>
3189 cnt += nb_right ? rs_idx.rcount(nb_right - 1) : 0;
3195 template<
typename Alloc>
3207 size_type cnt = nblock_right ? rs_idx.rcount(nblock_right - 1) : 0;
3219 cnt += bm::gap_bit_count_to<bm::gap_word_t, true>(
3240 template<
typename Alloc>
3256 template<
typename Alloc>
3302 if (nblock_left == nblock_right)
3312 nblock_left+1, nblock_right-1, func);
3337 template<
typename Alloc>
3360 if (nblock_left == nblock_right)
3390 if (nblock_left <= nblock_right)
3392 unsigned i_from, j_from, i_to, j_to;
3398 for (
unsigned i = i_from;
i <= i_to; ++
i)
3406 unsigned j = (
i == i_from) ? j_from : 0;
3413 }
while (++j < j_limit);
3421 template<
typename Alloc>
3443 if (nblock_left == nblock_right)
3473 if (nblock_left <= nblock_right)
3475 unsigned i_from, j_from, i_to, j_to;
3482 if (i_from >= top_size)
3484 if (i_to >= top_size)
3486 i_to = unsigned(top_size-1);
3491 for (
unsigned i = i_from;
i <= i_to; ++
i)
3499 unsigned j = (
i == i_from) ? j_from : 0;
3506 }
while (++j < j_limit);
3514 template<
typename Alloc>
3528 template<
typename Alloc>
3536 return this->
test(left);
3539 cnt_l = this->
count_to(left-1, rs_idx);
3542 cnt_r = this->
count_to(right, rs_idx);
3544 return cnt_r - cnt_l;
3549 template<
typename Alloc>
3559 for (
unsigned i = 0;
i < top_blocks; ++
i)
3601 template<
typename Alloc>
3618 if (!blk_blk)
return false;
3634 template<
typename Alloc>
3670 template<
typename Alloc>
3684 for (; nblock_left <= nblock_right; ++nblock_left)
3699 template<
typename Alloc>
3713 ::memcpy(opt_glen, st.gap_levels, bm::gap_levels * sizeof(*opt_glen));
3716 st.gap_length + st.gap_blocks,
3725 template<typename Alloc>
3743 template<
typename Alloc>
3748 unsigned bvect_top_blocks = bv.blockman_.top_block_size();
3750 if (bvect_top_blocks > top_blocks) top_blocks = bvect_top_blocks;
3752 for (
unsigned i = 0;
i < top_blocks; ++
i)
3755 const bm::word_t*
const* arg_blk_blk = bv.blockman_.get_topblock(
i);
3757 if (blk_blk == arg_blk_blk)
3767 arg_blk = arg_blk_blk ? arg_blk_blk[j] : 0;
3775 blk = blk_blk ? blk_blk[j] : 0;
3779 if (blk == arg_blk)
continue;
3784 if (!blk || !arg_blk)
3861 template<
typename Alloc>
3869 if (!top_blocks || !top_root)
3874 unsigned i_to, j_to;
3877 if (!bvect_top_blocks || !arg_top_root)
3879 bool f = this->
find(pos);
3882 if (pos > search_to)
3888 if (bvect_top_blocks > top_blocks)
3889 top_blocks = bvect_top_blocks;
3893 if (i_to < top_blocks)
3894 top_blocks = i_to+1;
3896 for (
unsigned i = 0;
i < top_blocks; ++
i)
3901 if (blk_blk == arg_blk_blk)
3945 if (pos > search_to)
3965 template<
typename Alloc>
3977 template<
typename Alloc>
3984 ::memcpy(st->gap_levels,
3987 st->max_serialize_mem = unsigned(
sizeof(
bm::id_t) * 4);
3993 blocks_mem +=
sizeof(
bm::word_t**) * top_size;
3998 for (
unsigned i = 0;
i < top_size; ++
i)
4007 blk_blk = blk_root[
i];
4014 st->ptr_sub_blocks++;
4028 st->add_gap_block(cap,
len, level);
4031 st->add_bit_block();
4037 st->max_serialize_mem += full_null_size;
4041 size_t safe_inc = st->max_serialize_mem / 10;
4042 if (!safe_inc) safe_inc = 256;
4043 st->max_serialize_mem += safe_inc;
4046 st->memory_used += unsigned(
sizeof(*
this) -
sizeof(
blockman_));
4048 st->memory_used += blocks_mem;
4057 template<
typename Alloc>
4066 for (
unsigned i = 0;
i < top_size; ++
i)
4087 template<
class Alloc>
4093 if (!ids || !ids_size)
4098 import(ids, ids_size, so);
4104 template<
class Alloc>
4116 bv_tmp.
import(ids, ids_size, so);
4134 template<
class Alloc>
4148 template<
class Alloc>
4159 bv_tmp.
import(ids, ids_size, so);
4176 template<
class Alloc>
4187 template<
class Alloc>
4198 template<
class Alloc>
4201 if (
val == condition)
return false;
4212 template<
class Alloc>
4226 template<
class Alloc>
4244 template<
class Alloc>
4264 if (nblock == nblock_end)
4291 }
while (start < size_in);
4296 template<
class Alloc>
4312 if (nblock == nblock_end)
4316 if (opt_flag && nbit == 65535)
4338 }
while (start < size_in);
4347 nblock_end +=
bool(nbit == 65535);
4353 }
while (nblock < nblock_end);
4362 template<
class Alloc>
4377 if (stop-start == 1)
4405 template<
class Alloc>
4416 unsigned nbit1, nbit2;
4437 if (block1 == block2)
4447 bool b1 = block1[nword1] & (1u << nbit1);
4448 bool b2 = block1[nword2] & (1u << nbit2);
4451 nbit1 = 1u << nbit1; nbit2 = 1u << nbit2;
4452 auto w = block1[nword1];
4453 (b2) ? w |= nbit1 : w &= ~nbit1;
4456 (b1) ? w |= nbit2 : w &= ~nbit2;
4469 if (block1 == block2)
4473 unsigned cpos1{ 0 }, cpos2{ 0 };
4474 bool b1, b2, b1real, b2real;
4478 b1 =
false; b1real =
false;
4483 b1 =
true; b1real =
false;
4505 b2 =
false; b2real =
false;
4510 b2 =
true; b2real =
false;
4537 unsigned new_len, old_len;
4538 unsigned is_set = b1;
4541 if (old_len < new_len)
4544 if (new_len > threshold)
4552 auto w = block1[nword1];
4553 (b2) ? w |= nbit1 : w &= ~nbit1;
4566 unsigned new_len, old_len;
4567 unsigned is_set = b2;
4570 if (old_len < new_len)
4573 if (new_len > threshold)
4581 auto w = block2[nword2];
4582 (b1) ? w |= nbit2 : w &= ~nbit2;
4596 template<
class Alloc>
4645 template<
class Alloc>
4651 const bool val =
true;
4673 blk[nword] |= (1u << nbit);
4679 template<
class Alloc>
4685 const bool val =
false;
4706 blk[nword] &= ~(1u << nbit);
4713 template<
class Alloc>
4718 unsigned is_set, new_len, old_len;
4721 if (old_len < new_len)
4724 if (new_len > threshold)
4732 template<
class Alloc>
4736 unsigned new_len, old_len;
4739 if (old_len < new_len)
4742 if (new_len > threshold)
4750 template<
class Alloc>
4775 is_set = ((*word) &
mask);
4783 template<
class Alloc>
4802 if (block_type == 1)
4815 bool is_set = ((*word) &
mask) != 0;
4817 if (is_set != condition)
4835 template<
class Alloc>
4854 if (block_type == 1)
4859 bool new_val =
val & old_val;
4860 if (new_val != old_val)
4874 bool is_set = ((*word) &
mask) != 0;
4876 bool new_val = is_set &
val;
4895 template<
class Alloc>
4910 template<
class Alloc>
4918 for (
unsigned i = top_blocks-1;
true; --
i)
4949 pos = base_idx + block_pos;
4967 template<
class Alloc>
4976 return this->
test(from);
4987 unsigned found_nbit;
4992 base_idx = bm::get_block_start<size_type>(i0, j0);
4993 pos = base_idx + found_nbit;
5009 for (
unsigned j = j0;
true; --j)
5032 pos = base_idx + block_pos;
5045 for (
unsigned i = i0;
true; --
i)
5075 pos = base_idx + block_pos;
5092 template<
class Alloc>
5098 for (
unsigned i = 0;
i < top_blocks; ++
i)
5114 found =
true; block_pos = 0;
5126 pos = base_idx + block_pos;
5138 template<
class Alloc>
5142 bool found =
find(in_first);
5151 in_first = in_last = 0;
5158 template<
class Alloc>
5172 unsigned bit_pos = 0;
5211 template<
class Alloc>
5223 (rs_idx.count() < rank_in))
5231 nb = rs_idx.find(rank_in);
5232 BM_ASSERT(rs_idx.rcount(nb) >= rank_in);
5234 rank_in -= rs_idx.rcount(nb-1);
5238 unsigned bit_pos = 0;
5240 for (; nb < rs_idx.get_total(); ++nb)
5248 unsigned block_bc = rs_idx.count(nb);
5249 if (rank_in <= block_bc)
5251 nbit = rs_idx.select_sub_range(nb, rank_in);
5257 rank_in -= block_bc;
5282 template<
class Alloc>
5290 (rs_idx.count() < rank_in))
5295 bool found = rs_idx.find(&rank_in, &nb, &sub_range_from);
5305 unsigned bit_pos = 0;
5309 bit_pos = sub_range_from + unsigned(rank_in) - 1;
5322 template<
class Alloc>
5363 for (;
i < top_blocks; ++
i)
5380 found =
true; block_pos = 0;
5392 prev = base_idx + block_pos;
5406 template<
class Alloc>
5422 template<
class Alloc>
5431 template<
class Alloc>
5435 bool b = this->
test(0);
5442 template<
class Alloc>
5476 goto insert_bit_check;
5484 unsigned new_block_len;
5488 if (new_block_len > threshold)
5525 if (
i >= top_blocks)
5532 blk_blk = blk_root[
i];
5544 block[0] |= carry_over;
5548 blk_blk = blk_root[
i];
5574 carry_over = 0; block = 0;
5579 if (0 != (block = blk_blk[j]))
5595 block[0] <<= (carry_over = 1);
5608 unsigned new_block_len;
5613 if (new_block_len > threshold)
5645 template<
class Alloc>
5695 if (
i >= top_blocks)
5698 blk_blk = blk_root[
i];
5710 bool carry_over = 0;
5714 carry_over = this->
test(co_idx);
5730 bool carry_over = 0;
5735 bool no_blocks = (j == 0);
5738 if (0 != (block = blk_blk[j]))
5770 unsigned new_block_len;
5775 if (new_block_len > threshold)
5791 if (carry_over && nblock)
5804 template<
class Alloc>
5815 template<
class Alloc>
5841 for (
unsigned i = 0;
i < top_blocks; ++
i)
5844 bm::word_t** blk_blk_arg = (
i < arg_top_blocks) ? blk_root_arg[
i] : 0;
5845 if (blk_blk == blk_blk_arg || !blk_blk_arg)
5847 if (!blk_blk && blk_blk_arg)
5851 blk_root[
i] = blk_root_arg[
i];
5852 blk_root_arg[
i] = 0;
5869 blk = blk_blk[j]; arg_blk = blk_blk_arg[j];
5872 if (!blk && arg_blk)
5888 template<
class Alloc>
5904 template<
class Alloc>
5936 unsigned top_blocks = (top_blocks2 > top_blocks1) ? top_blocks2 : top_blocks1;
5956 for (
unsigned i = 0;
i < top_blocks; ++
i)
5958 bm::word_t** blk_blk_arg1 = (
i < top_blocks1) ? blk_root_arg1[
i] : 0;
5959 bm::word_t** blk_blk_arg2 = (
i < top_blocks2) ? blk_root_arg2[
i] : 0;
5961 if (blk_blk_arg1 == blk_blk_arg2)
5965 blk_root[
i] = blk_blk_arg1;
5976 bool any_blocks =
false;
5980 const bm::word_t* arg_blk1 = blk_blk_arg1 ? blk_blk_arg1[j] : 0;
5981 const bm::word_t* arg_blk2 = blk_blk_arg2 ? blk_blk_arg2[j] : 0;
5982 if (arg_blk1 == arg_blk2 && !arg_blk1)
5987 any_blocks |=
bool(blk_blk[j]);
6003 template<
class Alloc>
6043 unsigned top_blocks = (top_blocks2 > top_blocks1) ? top_blocks2 : top_blocks1;
6053 for (
unsigned i = 0;
i < top_blocks; ++
i)
6055 bm::word_t** blk_blk_arg1 = (
i < top_blocks1) ? blk_root_arg1[
i] : 0;
6056 bm::word_t** blk_blk_arg2 = (
i < top_blocks2) ? blk_root_arg2[
i] : 0;
6058 if (blk_blk_arg1 == blk_blk_arg2)
6085 bool any_blocks =
false;
6090 arg_blk1 = blk_blk_arg1 ? blk_blk_arg1[j] : 0;
6091 arg_blk2 = blk_blk_arg2 ? blk_blk_arg2[j] : 0;
6093 if ((arg_blk1 == arg_blk2) &&
6100 any_blocks |=
bool(blk_blk[j]);
6116 template<
class Alloc>
6149 unsigned top_blocks = (top_blocks2 > top_blocks1) ? top_blocks2 : top_blocks1;
6159 for (
unsigned i = 0;
i < top_blocks; ++
i)
6161 bm::word_t** blk_blk_arg1 = (
i < top_blocks1) ? blk_root_arg1[
i] : 0;
6162 bm::word_t** blk_blk_arg2 = (
i < top_blocks2) ? blk_root_arg2[
i] : 0;
6164 if (blk_blk_arg1 == blk_blk_arg2)
6181 bool any_blocks =
false;
6186 arg_blk1 = blk_blk_arg1 ? blk_blk_arg1[j] : 0;
6187 arg_blk2 = blk_blk_arg2 ? blk_blk_arg2[j] : 0;
6189 if ((arg_blk1 == arg_blk2) && !arg_blk1)
6195 any_blocks |=
bool(blk_blk[j]);
6211 template<
class Alloc>
6242 unsigned top_blocks = (top_blocks2 > top_blocks1) ? top_blocks2 : top_blocks1;
6246 if (new_size < bv2.
size_)
6247 new_size = bv2.
size_;
6248 if (
size_ < new_size)
6254 for (
unsigned i = 0;
i < top_blocks; ++
i)
6256 bm::word_t** blk_blk_arg1 = (
i < top_blocks1) ? blk_root_arg1[
i] : 0;
6257 bm::word_t** blk_blk_arg2 = (
i < top_blocks2) ? blk_root_arg2[
i] : 0;
6259 if (blk_blk_arg1 == blk_blk_arg2)
6279 bool any_blocks =
false;
6289 arg_blk1 = blk_blk_arg1 ? blk_blk_arg1[j] : 0;
6290 arg_blk2 = blk_blk_arg2 ? blk_blk_arg2[j] : 0;
6292 if ((arg_blk1 == arg_blk2) && !arg_blk1)
6309 any_blocks |=
bool(blk_blk[j]);
6328 template<
class Alloc>
6367 unsigned top_blocks = (top_blocks2 > top_blocks1) ? top_blocks2 : top_blocks1;
6377 for (
unsigned i = 0;
i < top_blocks; ++
i)
6379 bm::word_t** blk_blk_arg1 = (
i < top_blocks1) ? blk_root_arg1[
i] : 0;
6380 bm::word_t** blk_blk_arg2 = (
i < top_blocks2) ? blk_root_arg2[
i] : 0;
6382 if (blk_blk_arg1 == blk_blk_arg2)
6390 bool any_blocks =
false;
6394 const bm::word_t* arg_blk1 = blk_blk_arg1 ? blk_blk_arg1[j] : 0;
6395 const bm::word_t* arg_blk2 = blk_blk_arg2 ? blk_blk_arg2[j] : 0;
6396 if ((arg_blk1 == arg_blk2) && !arg_blk1)
6402 any_blocks |=
bool(blk_blk[j]);
6419 #define BM_OR_OP(x) \
6421 blk = blk_blk[j+x]; arg_blk = blk_blk_arg[j+x]; \
6422 if (blk != arg_blk) \
6423 combine_operation_block_or(i, j+x, blk, arg_blk); \
6426 template<
class Alloc>
6442 for (
unsigned i = 0;
i < top_blocks; ++
i)
6445 bm::word_t** blk_blk_arg = (
i < arg_top_blocks) ? blk_root_arg[
i] : 0;
6446 if (blk_blk == blk_blk_arg || !blk_blk_arg)
6464 #if defined(BM64_AVX2) || defined(BM64_AVX512)
6473 #elif defined(BM64_SSE4)
6492 #define BM_XOR_OP(x) \
6494 blk = blk_blk[j+x]; arg_blk = blk_blk_arg[j+x]; \
6495 combine_operation_block_xor(i, j+x, blk, arg_blk); \
6498 template<
class Alloc>
6520 for (
unsigned i = 0;
i < top_blocks; ++
i)
6522 bm::word_t** blk_blk_arg = (
i < arg_top_blocks) ? blk_root_arg[
i] : 0;
6526 if (blk_blk == blk_blk_arg)
6556 #if defined(BM64_AVX2) || defined(BM64_AVX512)
6565 #elif defined(BM64_SSE4)
6585 #define BM_AND_OP(x) if (0 != (blk = blk_blk[j+x])) \
6587 if (0 != (arg_blk = blk_blk_arg[j+x])) \
6589 combine_operation_block_and(i, j+x, blk, arg_blk); \
6590 if (opt_mode == opt_compress) \
6591 blockman_.optimize_bit_block(i, j+x, opt_mode); \
6594 blockman_.zero_block(i, j+x); \
6597 template<
class Alloc>
6620 for (
unsigned i = 0;
i < top_blocks; ++
i)
6625 bm::word_t** blk_blk_arg = (
i < arg_top_blocks) ? blk_root_arg[
i] : 0;
6651 #if defined(BM64_AVX2) || defined(BM64_AVX512)
6660 #elif defined(BM64_SSE4)
6680 #define BM_SUB_OP(x) \
6681 if ((0 != (blk = blk_blk[j+x])) && (0 != (arg_blk = blk_blk_arg[j+x]))) \
6682 combine_operation_block_sub(i, j+x, blk, arg_blk);
6685 template<
class Alloc>
6701 for (
unsigned i = 0;
i < top_blocks; ++
i)
6704 bm::word_t** blk_blk_arg = (
i < arg_top_blocks) ? blk_root_arg[
i] : 0;
6705 if (!blk_blk || !blk_blk_arg)
6721 #if defined(BM64_AVX2) || defined(BM64_AVX512)
6730 #elif defined(BM64_SSE4)
6749 template<
class Alloc>
6764 if (arg_top_blocks > top_blocks)
6780 if (arg_top_blocks < top_blocks)
6783 top_blocks = arg_top_blocks;
6789 unsigned block_idx = 0; (void) block_idx;
6802 for (
i = 0;
i < top_blocks; ++
i)
6871 template<
class Alloc>
6897 if (is_gap1 | is_gap2)
6899 if (is_gap1 & is_gap2)
6913 arg_block = arg_blk2;
6918 arg_block = arg_blk1;
6944 template<
class Alloc>
6978 if (is_gap1 | is_gap2)
6980 if (is_gap1 & is_gap2)
6994 arg_block = arg_blk2;
6999 arg_block = arg_blk1;
7026 template<
class Alloc>
7034 if (!arg_blk1 || !arg_blk2)
7055 if (is_gap1 | is_gap2)
7057 if (is_gap1 & is_gap2)
7071 arg_block = arg_blk2;
7076 arg_block = arg_blk1;
7111 template<
class Alloc>
7121 if (!arg_blk1 || !arg_blk2)
7146 if (is_gap1 | is_gap2)
7148 if (is_gap1 & is_gap2)
7168 arg_block = arg_blk2;
7173 arg_block = arg_blk1;
7195 if (digest == digest_and)
7211 template<
class Alloc>
7234 if (is_gap1 | is_gap2)
7236 if (is_gap1 & is_gap2)
7285 template<
class Alloc>
7287 unsigned i,
unsigned j,
7364 template<
class Alloc>
7366 unsigned i,
unsigned j,
7468 template<
class Alloc>
7572 template<
class Alloc>
7599 BM_ASSERT(!(res == tmp_buf && res_len == 0));
7632 if (!dst || !arg_blk)
7636 if (ret && ret == arg_blk)
7652 template<
class Alloc>
7667 if (!blk && arg_gap)
7689 BM_ASSERT(!(res == tmp_buf && res_len == 0));
7755 if (dst == 0 && arg_blk == 0)
7789 }
while (wrd_ptr < wrd_end);
7806 if (ret && ret == arg_blk)
7829 template<
class Alloc>
7856 gap_init_range_block<gap_word_t>(tmp_gap_blk,
7868 if (nblock_left == nblock_right)
7883 if (nb_to > nblock_right)
7889 gap_init_range_block<gap_word_t>(tmp_gap_blk,
7903 template<
class Alloc>
7931 bm::gap_init_range_block<gap_word_t>(tmp_gap_blk,
7944 if (nblock_left == nblock_right)
7946 nb = nblock_left + 1;
7959 if (nb_to > nblock_right)
7964 gap_init_range_block<gap_word_t>(tmp_gap_blk,
7980 template<
class Alloc>
8003 template<
class Alloc>
8017 if (found && (
last > right))
8025 template<
class Alloc>
8049 if (found && (
last > right))
8057 template<
class Alloc>
8068 template<
class Alloc>
8072 throw std::bad_alloc();
8074 BM_THROW(BM_ERR_BADALLOC);
8082 template<
class Alloc>
8087 block_descr_type* bdescr = &(this->
bdescr_);
8112 unsigned short idx = ++(bdescr->
bit_.
idx);
8113 if (idx < bdescr->bit_.cnt)
8135 template<
class Alloc>
8141 return this->
valid();
8145 block_descr_type* bdescr = &(this->
bdescr_);
8151 unsigned short idx = ++(bdescr->
bit_.
idx);
8152 if (idx < bdescr->bit_.cnt)
8201 return this->
valid();
8208 template<
class Alloc>
8214 return this->
valid();
8217 size_type new_pos = this->
bv_->check_or_next(pos);
8230 this->
bv_->get_blocks_manager();
8239 block_descr_type* bdescr = &(this->
bdescr_);
8248 return this->
valid();
8256 bdescr->
gap_.
ptr = gptr + gpos;
8273 return this->
valid();
8286 nbit += 32 * parity;
8287 for (
unsigned i = 0;
i < bdescr->
bit_.
cnt; ++
i)
8290 return this->
valid();
8295 return this->
valid();
8300 template<
class Alloc>
8305 blocks_manager_type* bman = &(this->
bv_->blockman_);
8331 this->
block_ = blk_blk[j];
8359 template<
class Alloc>
8364 if (bdescr->bit_.cnt)
8366 bdescr->bit_.idx = 0;
8374 template<
class Alloc>
8379 for (; bdescr->bit_.ptr < block_end;)
8384 this->
position_ += bdescr->bit_.bits[0];
8395 template<
class Alloc>
8401 for (; bdescr->bit_.ptr < block_end;)
8404 #if defined(BMAVX512OPT) || defined(BMAVX2OPT) || defined(BM64OPT) || defined(BM64_SSE4)
8430 this->
position_ += bdescr->bit_.bits[0];
8443 template<
class Alloc>
8448 block_descr_type* bdescr = &(this->
bdescr_);
8455 template<
class Alloc>
8460 block_descr_type* bdescr = &(this->
bdescr_);
8462 unsigned bitval = *(bdescr->
gap_.
ptr) & 1;
8494 template<
class Alloc>
8498 const blocks_manager_type& bman = this->
bv_->blockman_;
8502 for (;
i < top_block_size; ++
i)
8510 for (++i;
i < top_block_size; ++
i)
8519 if ((
i < top_block_size) && blk_root[
i])
8530 this->
block_ = blk_blk[j];
8561 #pragma warning( pop )
static void * Alloc(size_t size)
#define BM_BORDER_TEST(blk, idx)
#define BM_DECLARE_TEMP_BLOCK(x)
Default SIMD friendly allocator.
#define VECT_XOR_ARR_2_MASK(dst, src, src_end, mask)
Constants, lookup tables and typedefs.
#define IS_FULL_BLOCK(addr)
#define IS_VALID_ADDR(addr)
#define BMSET_PTRGAP(ptr)
#define BLOCK_ADDR_SAN(addr)
#define BM_ASSERT_THROW(x, xerrcode)
#define FULL_BLOCK_FAKE_ADDR
#define FULL_SUB_BLOCK_REAL_ADDR
#define FULL_BLOCK_REAL_ADDR
Bit manipulation primitives (internal)
Rank-Select index structures.
SIMD target version definitions.
Algorithms for fast aggregation of a group of bit-vectors.
Functor detects if any bit set.
Bitcounting functor filling the block counts array.
id_type last_block() const BMNOEXCEPT
id_type count() const BMNOEXCEPT
bitvector blocks manager Embedded class managing bit-blocks on very low level. Includes number of fun...
unsigned top_block_size_
Size of the top level block array in blocks_ tree.
void set_glen(const gap_word_t *glevel_len) BMNOEXCEPT
void set_all_zero(block_idx_type nb, block_idx_type nb_to) BMNOEXCEPT
set all-Zero block pointers for [start..end]
bm::word_t *** top_blocks_
Tree of blocks.
arena * arena_
memory arena pointer
bm::word_t * check_allocate_tempblock()
unsigned find_max_top_blocks() const BMNOEXCEPT
calculate max top blocks size whithout NULL-tail
bm::word_t * deoptimize_block(block_idx_type nb)
Make sure block turns into true bit-block if it is GAP or a full block.
void return_tempblock(bm::word_t *block) BMNOEXCEPT
void set_all_set(block_idx_type nb, block_idx_type nb_to)
set all-set block pointers for [start..end]
const bm::word_t *const * get_topblock(unsigned i) const BMNOEXCEPT
Function returns top-level block in 2-level blocks array.
void destroy_arena() BMNOEXCEPT
free all arena memory
void move_from(blocks_manager &bm) BMNOEXCEPT
implementation of moving semantics
bm::gap_word_t * extend_gap_block(block_idx_type nb, gap_word_t *blk)
Extends GAP block to the next level or converts it to bit block.
void assign_gap_check(unsigned i, unsigned j, const bm::gap_word_t *res, unsigned res_len, bm::word_t *blk, gap_word_t *tmp_buf)
Attach the result of a GAP logical operation but check if it is all 000.
bm::word_t ** check_alloc_top_subblock(unsigned nblk_blk)
Allocate top sub-block if not allocated.
bm::word_t * temp_block_
Temp block.
bm::word_t *** top_blocks_root() const BMNOEXCEPT
Returns root block in the tree.
void deinit_tree() BMNOEXCEPT
const bm::word_t * get_block(block_idx_type nb, int *no_more_blocks) const BMNOEXCEPT
Returns current capacity (bits)
unsigned top_block_size() const BMNOEXCEPT
Returns size of the top block array in the tree.
void free_temp_block() BMNOEXCEPT
size_t calc_serialization_null_full() const BMNOEXCEPT
Calculate approximate memory needed to serialize big runs of 0000s and 111s (as blocks)
void free_top_subblock(unsigned nblk_blk) BMNOEXCEPT
const bm::word_t * get_block_ptr(unsigned i, unsigned j) const BMNOEXCEPT
Finds block in 2-level blocks array (unsinitized)
void assign_gap(block_idx_type nb, const bm::gap_word_t *res, unsigned res_len, bm::word_t *blk, gap_word_t *tmp_buf)
Attach the result of a GAP logical operation.
allocator_type alloc_
allocator
void init_tree()
allocate first level of descr. of blocks
allocator_type & get_allocator() BMNOEXCEPT
Returns reference on the allocator.
bool is_init() const BMNOEXCEPT
if tree of blocks already up
void swap(blocks_manager &bm) BMNOEXCEPT
Swaps content.
void deallocate_top_subblock(unsigned nblk_blk) BMNOEXCEPT
void copy_to_arena(const blocks_manager &bman)
calculate arena statistics, calculate and copy all blocks there
bm::word_t * check_allocate_block(block_idx_type nb, unsigned content_flag, int initial_block_type, int *actual_block_type, bool allow_null_ret=true)
Function checks if block is not yet allocated, allocates it and sets to all-zero or all-one bits.
void copy(const blocks_manager &blockman, block_idx_type block_from=0, block_idx_type block_to=bm::set_total_blocks)
const gap_word_t * glen() const BMNOEXCEPT
Returns current GAP level vector.
unsigned find_real_top_blocks() const BMNOEXCEPT
calculate top blocks which are not NULL and not FULL
void zero_block(block_idx_type nb) BMNOEXCEPT
Free block, make it zero pointer in the tree.
bm::word_t * deoptimize_block_no_check(bm::word_t *block, unsigned i, unsigned j)
void optimize_bit_block(unsigned i, unsigned j, int opt_mode)
Optimize bit-block at i-j position.
bm::word_t * borrow_tempblock()
void optimize_block(unsigned i, unsigned j, bm::word_t *block, bm::word_t *temp_block, int opt_mode, bv_statistics *bv_stat)
bm::word_t ** alloc_top_subblock(unsigned nblk_blk)
unsigned reserve_top_blocks(unsigned top_blocks)
Make sure blocks manager has enough blocks capacity.
bm::word_t * set_block(block_idx_type nb, bm::word_t *block)
Places new block into descriptors table, returns old block's address.
bm::word_t * convert_gap2bitset(block_idx_type nb, const gap_word_t *gap_block=0)
Converts block from type gap to conventional bitset block.
void optimize_tree(bm::word_t *temp_block, int opt_mode, bv_statistics *bv_stat)
void set_block_ptr(block_idx_type nb, bm::word_t *block)
Places new block into blocks table.
bm::word_t * clone_gap_block(const bm::gap_word_t *gap_block, bool &gap_res)
Clone GAP block from another GAP It can mutate into a bit-block if does not fit.
static bm::id_t block_bitcount(const bm::word_t *block) BMNOEXCEPT
Count number of bits ON in the block.
bm::word_t * clone_assign_block(unsigned i, unsigned j, const bm::word_t *src_block, bool invert=false)
Clone block, assign to i-j position.
void reserve(id_type max_bits)
reserve capacity for specified number of bits
void stat_correction(bv_statistics *stat) noexcept
Output iterator iterator designed to set "ON" bits based on input sequence of integers.
bulk_insert_iterator(const insert_iterator &iit)
size_type * buf_
bulk insert buffer
bulk_insert_iterator & operator++()
bm::sort_order sorted_
sort order hint
bulk_insert_iterator(const bulk_insert_iterator &iit)
bulk_insert_iterator & operator=(size_type n)
bvector_type::size_type size_type
bulk_insert_iterator & operator=(const bulk_insert_iterator &ii)
bulk_insert_iterator(bulk_insert_iterator &&iit) noexcept
bulk_insert_iterator & operator*()
size_type buf_size_
current buffer size
std::output_iterator_tag iterator_category
static size_type buf_size_max() noexcept
bulk_insert_iterator(bvector< Alloc > &bvect, bm::sort_order so=BM_UNKNOWN) noexcept
bvector_type * bvect_
target bvector
bulk_insert_iterator & operator++(int)
bulk_insert_iterator() noexcept
bvector_type * get_bvector() const noexcept
bulk_insert_iterator & operator=(bulk_insert_iterator &&ii) noexcept
bvector_type::size_type value_type
bm::bvector< Alloc > bvector_type
Constant iterator designed to enumerate "ON" bits counted_enumerator keeps bitcount,...
counted_enumerator(const enumerator &en) noexcept
counted_enumerator operator++(int)
counted_enumerator() noexcept
std::input_iterator_tag iterator_category
counted_enumerator & operator=(const enumerator &en) noexcept
counted_enumerator & go_to(size_type pos)
counted_enumerator & operator++() noexcept
size_type count() const noexcept
Number of bits ON starting from the .
Constant iterator designed to enumerate "ON" bits.
std::input_iterator_tag iterator_category
size_type value() const noexcept
Get current position (value)
static bool decode_wave(block_descr_type *bdescr) noexcept
void go_first() noexcept
Position enumerator to the first available bit.
enumerator(const bvector< Alloc > *bv) noexcept
Construct enumerator associated with a vector. Important: This construction creates unpositioned iter...
enumerator & operator++() noexcept
Advance enumerator forward to the next available bit.
bool search_in_blocks() noexcept
bool search_in_gapblock() noexcept
bool go_to(size_type pos) noexcept
go to a specific position in the bit-vector (or next)
enumerator(const bvector< Alloc > *bv, size_type pos) noexcept
Construct enumerator for bit vector.
enumerator operator++(int) noexcept
Advance enumerator forward to the next available bit. Possibly do NOT use this operator it is slower ...
size_type operator*() const noexcept
Get current position (value)
bool search_in_bitblock() noexcept
bool skip_to_rank(size_type rank) noexcept
Skip to specified relative rank.
bool decode_bit_group(block_descr_type *bdescr) noexcept
bool decode_bit_group(block_descr_type *bdescr, size_type &rank) noexcept
iterator_base::block_descr block_descr_type
bool skip(size_type rank) noexcept
Skip specified number of bits from enumeration.
bool go_up() noexcept
Advance enumerator to the next available bit.
enumerator(const bvector< Alloc > &bv, size_type pos=0) noexcept
Construct enumerator for bit vector.
Output iterator iterator designed to set "ON" bits based on input sequence of integers (bit indeces).
insert_iterator(const insert_iterator &iit)
bvector_type * get_bvector() const
insert_iterator & operator++(int)
insert_iterator(bvector< Alloc > &bvect) noexcept
insert_iterator & operator=(const insert_iterator &ii)
friend class bulk_insert_iterator
insert_iterator & operator++()
insert_iterator() noexcept
insert_iterator & operator*()
bm::bvector< Alloc > bvector_type
insert_iterator & operator=(size_type n)
std::output_iterator_tag iterator_category
Base class for all iterators.
bool operator!=(const iterator_base &it) const noexcept
bool operator<=(const iterator_base &it) const noexcept
size_type position_
Bit position (bit idx)
bool operator==(const iterator_base &it) const noexcept
bool valid() const noexcept
Checks if iterator is still valid.
unsigned block_type_
Type of block. 0-Bit, 1-GAP.
union bm::bvector::iterator_base::block_descr bdescr_
bool operator<(const iterator_base &it) const noexcept
bm::bvector< Alloc > * bv_
Pointer on parent bitvector.
bool compare_state(const iterator_base &ib) const noexcept
Compare FSMs for testing purposes.
const bm::word_t * block_
Block pointer.(NULL-invalid)
bool operator>=(const iterator_base &it) const noexcept
bool operator>(const iterator_base &it) const noexcept
void invalidate() noexcept
Turns iterator into an invalid state.
block_idx_type block_idx_
Block index.
Class reference implements an object for bit assignment.
bool operator!() const noexcept
const reference & operator=(bool value) const noexcept
reference(bvector< Alloc > &bv, size_type position) noexcept
size_type position_
Position in the parent bitvector.
const reference & operator|=(bool value) const
const reference & operator=(const reference &ref) const
reference(const reference &ref) noexcept
bvector< Alloc > & bv_
Reference variable on the parent.
bool operator==(const reference &ref) const noexcept
const reference & operator&=(bool value) const
const reference & operator^=(bool value) const
bool operator~() const noexcept
Bitvector Bit-vector container with runtime compression of bits.
bm::bvector< Alloc > & bit_or(const bm::bvector< Alloc > &bv1, const bm::bvector< Alloc > &bv2, typename bm::bvector< Alloc >::optmode opt_mode=opt_none)
3-operand OR : this := bv1 OR bv2
void import_block(const size_type *ids, block_idx_type nblock, size_type start, size_type stop)
bool test(size_type n) const noexcept
returns true if bit n is set and false is bit n is 0.
optmode
Optimization mode Every next level means additional checks (better compression vs time)
@ opt_compress
compress blocks when possible (GAP/prefix sum)
@ opt_free_01
Free unused 0 and 1 blocks.
@ opt_free_0
Free unused 0 blocks.
@ opt_none
no optimization
bool select(size_type rank, size_type &pos, const rs_index_type &rs_idx) const noexcept
select bit-vector position for the specified rank(bitcount)
void swap(size_type idx1, size_type idx2)
swap values of bits
bvector(const bvector< Alloc > &bvect, bm::finalization is_final)
Copy-constructor for mutable/immutable initialization.
void operator&=(const bvector< Alloc > &bv)
bool find_rank(size_type rank, size_type from, size_type &pos, const rs_index_type &rs_idx) const noexcept
Find bit-vector position for the specified rank(bitcount)
size_type rank_corrected(size_type n, const rs_index_type &rs_idx) const noexcept
Returns rank corrceted by the requested border value (as -1)
void clear(bool free_mem=true) noexcept
Clears every bit in the bitvector.
bool combine_operation_block_and_or(unsigned i, unsigned j, const bm::word_t *arg_blk1, const bm::word_t *arg_blk2)
void set_gap_levels(const gap_word_t *glevel_len)
Sets new GAP lengths table. All GAP blocks will be reallocated to match the new scheme.
bvector(strategy strat=BM_BIT, const gap_word_t *glevel_len=bm::gap_len_table< true >::_len, size_type bv_size=bm::id_max, const Alloc &alloc=Alloc())
Constructs bvector class.
bool get_bit(size_type n) const noexcept
returns true if bit n is set and false is bit n is 0.
strategy get_new_blocks_strat() const noexcept
Returns blocks allocation strategy.
void combine_operation_with_block(block_idx_type nb, bool gap, bm::word_t *blk, const bm::word_t *arg_blk, bool arg_gap, bm::operation opcode)
void merge(bm::bvector< Alloc > &bvect)
Merge/move content from another vector.
void clear_range_no_check(size_type left, size_type right)
Clear range without validity/bounds checking.
bvector< Alloc > & invert()
Invert/NEG all bits It should be noted, invert is affected by size() if size is set - it only inverts...
void combine_operation_block_or(unsigned i, unsigned j, bm::word_t *blk, const bm::word_t *arg_blk)
bool set_bit_and(size_type n, bool val=true)
Sets bit n using bit AND with the provided value.
allocator_type::allocator_pool_type allocator_pool_type
void init(unsigned top_size, bool alloc_subs)
Explicit post-construction initialization. Must be caled right after construction strickly before any...
void combine_operation_xor(const bm::bvector< Alloc > &bvect)
perform a set-algebra operation XOR
bool set_bit_conditional_impl(size_type n, bool val, bool condition)
bool clear_bit(size_type n)
Clears bit n.
bm::bvector< Alloc > & bit_and(const bm::bvector< Alloc > &bv1, const bm::bvector< Alloc > &bv2, typename bm::bvector< Alloc >::optmode opt_mode=opt_none)
3-operand AND : this := bv1 AND bv2
static void throw_bad_alloc()
bool insert(size_type n, bool value)
Insert bit into specified position All the vector content after insert position is shifted right.
bool combine_operation_block_or(unsigned i, unsigned j, const bm::word_t *arg_blk1, const bm::word_t *arg_blk2)
bvector & operator=(const bvector< Alloc > &bvect)
Copy assignment operator.
size_type rank(size_type n, const rs_index_type &rs_idx) const noexcept
Returns rank of specified bit position (same as count_to())
bool any() const noexcept
Returns true if any bits in this bitset are set, and otherwise returns false.
size_type check_or_next(size_type prev) const noexcept
void keep_range_no_check(size_type left, size_type right)
Clear outside the range without validity/bounds checking.
void sync_size()
Syncronize size if it got extended due to bulk import.
bvector(bvector< Alloc > &&bvect) noexcept
Move constructor.
bool test_first_block_bit(block_idx_type nb) const noexcept
Return value of first bit in the block.
bvector< Alloc > operator~() const
size_type check_or_next_extract(size_type prev)
check if specified bit is 1, and set it to 0 if specified bit is 0, scan for the next 1 and returns i...
bool find_rank(size_type rank, size_type from, size_type &pos) const noexcept
Find bit-vector position for the specified rank(bitcount)
bvector< Alloc > & set(size_type n, bool val=true)
Sets bit n if val is true, clears bit n if val is false.
void resize(size_type new_size)
Change size of the bvector.
reference operator[](size_type n)
bm::bvector< Alloc > & bit_sub(const bm::bvector< Alloc > &bv1, const bm::bvector< Alloc > &bv2, typename bm::bvector< Alloc >::optmode opt_mode=opt_none)
3-operand SUB : this := bv1 MINUS bv2 SUBtraction is also known as AND NOT
bool empty() const noexcept
Returns true if the set is empty (no bits are set, otherwise returns false) Please note that this is ...
bvector(const bvector< Alloc > &bvect)
Copy constructor.
size_type size() const noexcept
Returns bvector's capacity (number of bits it can store)
void optimize(bm::word_t *temp_block=0, optmode opt_mode=opt_compress, statistics *stat=0)
Optimize memory bitvector's memory allocation.
void set_new_blocks_strat(strategy strat)
Sets new blocks allocation strategy.
bool find_range(size_type &first, size_type &last) const noexcept
Finds dynamic range of bit-vector [first, last].
bvector(std::initializer_list< size_type > il)
Brace constructor.
void swap(bvector< Alloc > &bvect) noexcept
Exchanges content of bv and this bvector.
void fill_alloc_digest(bvector< Alloc > &bv_blocks) const
Calculate blocks digest vector (for diagnostics purposes) 1 is added if NB is a real,...
size_type count_range(size_type left, size_type right, const rs_index_type &rs_idx) const noexcept
Returns count of 1 bits in the given range [left..right] Uses rank-select index to accelerate the sea...
bool set_bit(size_type n, bool val=true)
Sets bit n.
bool find(size_type from, size_type &pos) const noexcept
Find index of 1 bit starting from position.
insert_iterator inserter()
blocks_manager< Alloc > blocks_manager_type
bool find(size_type &pos) const noexcept
Finds index of first 1 bit.
void keep_range(size_type left, size_type right)
Sets all bits to zero outside of the closed interval [left,right] Expected result: 00000....
void combine_operation_block_sub(unsigned i, unsigned j, bm::word_t *blk, const bm::word_t *arg_blk)
bool find_first_mismatch(const bvector< Alloc > &bvect, size_type &pos, size_type search_to=bm::id_max) const noexcept
Find index of first bit different between this and the agr vector.
void operator-=(const bvector< Alloc > &bv)
static size_type block_count_to(const bm::word_t *block, block_idx_type nb, unsigned nbit_right, const rs_index_type &rs_idx) noexcept
Compute rank in bit-block using rank-select index.
Alloc get_allocator() const
bool and_bit_no_check(size_type n, bool val)
AND specified bit without checking preconditions (size, etc)
bvector_size_type size_type
bvector< Alloc > & flip(size_type n)
Flips bit n.
void clear_range(size_type left, size_type right)
Sets all bits to zero in the specified closed interval [left,right] Interval must be inside the bvect...
bool combine_operation_block_and(unsigned i, unsigned j, const bm::word_t *arg_blk1, const bm::word_t *arg_blk2)
void combine_operation_and(const bm::bvector< Alloc > &bvect, optmode opt_mode)
perform a set-algebra operation AND
enumerator first() const
Returns enumerator pointing on the first non-zero bit.
bool is_ro() const noexcept
Returns true if vector is read-only.
bool combine_operation_block_sub(unsigned i, unsigned j, const bm::word_t *arg_blk1, const bm::word_t *arg_blk2)
bool find_reverse(size_type &pos) const noexcept
Finds last index of 1 bit.
strategy new_blocks_strat_
block allocation strategy
bool find_reverse(size_type from, size_type &pos) const noexcept
Reverse finds next(prev) index of 1 bit.
bool combine_operation_block_xor(unsigned i, unsigned j, const bm::word_t *arg_blk1, const bm::word_t *arg_blk2)
enumerator end() const
Returns enumerator pointing on the next bit after the last.
bvector< Alloc > & set()
Sets every bit in this bitset to 1.
bool shift_left()
Shift left by 1 bit, fill with zero return carry out.
bm::bvector< Alloc > & bit_and(const bm::bvector< Alloc > &bv, optmode opt_mode=opt_none)
2 operand logical AND
void freeze()
Turn current vector to read-only (immutable vector).
bvector< Alloc > & reset() noexcept
Clears every bit in the bitvector.
const blocks_manager_type & get_blocks_manager() const noexcept
get access to memory manager (internal) Use only if you are BitMagic library
size_type count_range_no_check(size_type left, size_type right) const noexcept
blocks_manager_type & get_blocks_manager() noexcept
get access to memory manager (internal) Use only if you are BitMagic library
void combine_operation_block_xor(unsigned i, unsigned j, bm::word_t *blk, const bm::word_t *arg_blk)
size_type recalc_count() noexcept
void optimize_gap_size()
Optimize sizes of GAP blocks.
bool set_bit_no_check(size_type n, bool val)
Set specified bit without checking preconditions (size, etc)
void init()
Explicit post-construction initialization. Must be caled to make sure safe use of *_no_check() method...
bool shift_right()
Shift right by 1 bit, fill with zero return carry out.
block_idx_type count_blocks(unsigned *arr) const noexcept
Computes bitcount values for all bvector blocks.
bvector< Alloc > & flip()
Flips all bits.
bvector< Alloc > & set_range(size_type left, size_type right, bool value=true)
Sets all bits in the specified closed interval [left,right] Interval must be inside the bvector's siz...
void set_allocator_pool(allocator_pool_type *pool_ptr) noexcept
Set allocator pool for local (non-th readed) memory cyclic(lots of alloc-free ops) opertations.
void erase(size_type n)
Erase bit in the specified position All the vector content after erase position is shifted left.
bvector & operator=(bvector< Alloc > &&bvect) noexcept
Move assignment operator.
void set(const size_type *ids, size_type ids_size, bm::sort_order so=bm::BM_UNKNOWN)
Set list of bits in this bitset to 1.
static size_type gap_count_to(const bm::gap_word_t *gap_block, block_idx_type nb, unsigned nbit_right, const rs_index_type &rs_idx, bool test_set=false) noexcept
Compute rank in GAP block using rank-select index.
size_type extract_next(size_type prev)
Finds the number of the next bit ON and sets it to 0.
size_type get_next(size_type prev) const noexcept
Finds the number of the next bit ON.
void copy_range(const bvector< Alloc > &bvect, size_type left, size_type right)
Copy all bits in the specified closed interval [left,right].
enumerator get_enumerator(size_type pos) const
Returns enumerator pointing on specified or the next available bit.
void import(const size_type *ids, size_type ids_size, bm::sort_order sorted_idx)
Import integers (set bits).
void copy_range_no_check(const bvector< Alloc > &bvect, size_type left, size_type right)
void combine_operation_or(const bm::bvector< Alloc > &bvect)
perform a set-algebra operation OR
blocks_manager_type::block_idx_type block_idx_type
void copy(const bvector< Alloc > &bvect, bm::finalization is_final)
Copy bvector from the argument bvector.
void combine_operation_block_and(unsigned i, unsigned j, bm::word_t *blk, const bm::word_t *arg_blk)
void operator^=(const bvector< Alloc > &bv)
void operator|=(const bvector< Alloc > &bv)
void clear(const size_type *ids, size_type ids_size, bm::sort_order so=bm::BM_UNKNOWN)
clear list of bits in this bitset
void import_sorted(const size_type *ids, const size_type ids_size, bool opt_flag)
Import sorted integers (set bits).
bool equal(const bvector< Alloc > &bvect) const noexcept
Equal comparison with an agr bit-vector.
void optimize_range(size_type left, size_type right, bm::word_t *temp_block, optmode opt_mode=opt_compress)
rs_index< allocator_type > rs_index_type
bvector(const bvector< Alloc > &bvect, size_type left, size_type right)
Copy constructor for range copy [left..right].
void combine_operation_sub(const bm::bvector< Alloc > &bvect)
perform a set-algebra operation MINUS (AND NOT)
void calc_stat(struct bm::bvector< Alloc >::statistics *st) const noexcept
Calculates bitvector statistics.
size_type get_first() const noexcept
find first 1 bit in vector. Function may return 0 and this requires an extra check if bit 0 is actual...
rs_index< allocator_type > blocks_count
size_type count_to_test(size_type n, const rs_index_type &rs_idx) const noexcept
popcount in [0..right] range if test(right) == true
bool set_bit_conditional(size_type n, bool val, bool condition)
Sets bit n only if current value equals the condition.
void move_from(bvector< Alloc > &bvect) noexcept
Move bvector content from another bvector.
bool is_init() const noexcept
Return true if bvector is initialized at all.
int compare(const bvector< Alloc > &bvect) const noexcept
Lexicographical comparison with a bitvector.
void build_rs_index(rs_index_type *rs_idx, bvector< Alloc > *bv_blocks=0) const
compute running total of all blocks in bit vector (rank-select index)
bool any_range(size_type left, size_type right) const noexcept
Returns true if any bits in the range are 1s (non-empty interval) Function uses closed interval [left...
void combine_operation_with_block(block_idx_type nb, const bm::word_t *arg_blk, bool arg_gap, bm::operation opcode)
bm::bvector< Alloc > & bit_xor(const bm::bvector< Alloc > &bv)
2 operand logical XOR
void clear_bit_no_check(size_type n)
Clears bit n without precondiion checks.
bool operator[](size_type n) const noexcept
void gap_block_set_no_ret(bm::gap_word_t *gap_blk, bool val, block_idx_type nblock, unsigned nbit)
set bit in GAP block with GAP block length control
bool none() const noexcept
Returns true if no bits are set, otherwise returns false.
bvector(size_type bv_size, strategy strat=BM_BIT, const gap_word_t *glevel_len=bm::gap_len_table< true >::_len, const Alloc &alloc=Alloc())
Constructs bvector class.
void combine_operation(const bm::bvector< Alloc > &bvect, bm::operation opcode)
perform a set-algebra operation by operation code
size_type count() const noexcept
population count (count of ON bits)
void keep(const size_type *ids, size_type ids_size, bm::sort_order so=bm::BM_UNKNOWN)
Keep list of bits in this bitset, others are cleared.
bm::bvector< Alloc > & bit_or_and(const bm::bvector< Alloc > &bv1, const bm::bvector< Alloc > &bv2, typename bm::bvector< Alloc >::optmode opt_mode=opt_none)
3-operand AND where result is ORed into the terget vector : this |= bv1 AND bv2 TARGET := TARGET OR (...
size_type size_
size in bits
blocks_manager_type blockman_
bitblocks manager
bm::bvector< Alloc > & bit_sub(const bm::bvector< Alloc > &bv)
2 operand logical SUB(AND NOT). Also known as MINUS.
bm::bvector< Alloc > & bit_or(const bm::bvector< Alloc > &bv)
2 operand logical OR
void forget_count() noexcept
bool gap_block_set(bm::gap_word_t *gap_blk, bool val, block_idx_type nblock, unsigned nbit)
set bit in GAP block with GAP block length control
bm::bvector< Alloc > & bit_xor(const bm::bvector< Alloc > &bv1, const bm::bvector< Alloc > &bv2, typename bm::bvector< Alloc >::optmode opt_mode=opt_none)
3-operand XOR : this := bv1 XOR bv2
void set_range_no_check(size_type left, size_type right)
Set range without validity/bounds checking.
allocator_pool_type * get_allocator_pool() noexcept
Get curent allocator pool (if set)
bool is_all_one_range(size_type left, size_type right) const noexcept
Returns true if all bits in the range are 1s (saturated interval) Function uses closed interval [left...
bool inc(size_type n)
Increment the specified element.
void set_bit_no_check(size_type n)
Set bit without checking preconditions (size, etc)
size_type count_to(size_type n, const rs_index_type &rs_idx) const noexcept
Returns count of 1 bits (population) in [0..right] range.
Deserializer for bit-vector.
Deserializer, performs logical operations between bit-vector and serialized bit-vector.
Rank-Select acceleration index.
void init() BMNOEXCEPT
init arrays to zeros
void resize(block_idx_type new_size)
reserve the capacity for block count
void resize_effective_super_blocks(size_type sb_eff)
set size of true super-blocks (not NULL and not FFFFF)
void set_full_super_block(unsigned i) BMNOEXCEPT
set FULL (all bits set super-block)
void set_null_super_block(unsigned i) BMNOEXCEPT
set empty (no bits set super-block)
void set_total(size_type t)
set total blocks
void register_super_block(unsigned i, const unsigned *bcount, const bm::id64_t *sub_count)
Add block list belonging to one super block.
static vector< string > arr
Encoding utilities for serialization (internal)
static DLIST_TYPE *DLIST_NAME() last(DLIST_LIST_TYPE *list)
static DLIST_TYPE *DLIST_NAME() prev(DLIST_LIST_TYPE *list, DLIST_TYPE *item)
bool avx2_test_all_zero_wave2(const void *ptr0, const void *ptr1)
check if 2 wave of pointers are all NULL
bool avx2_test_all_eq_wave2(const void *ptr0, const void *ptr1)
check if 2 wave of pointers are all the same (NULL or FULL)
bool avx2_test_all_zero_wave(const void *ptr)
check if wave of pointers is all NULL
bool sse42_test_all_zero_wave(const void *ptr) noexcept
check if wave of pointers is all NULL
bool sse42_test_all_zero_wave2(const void *ptr0, const void *ptr1) noexcept
check if 2 waves of pointers are all NULL
bool sse42_test_all_eq_wave2(const void *ptr0, const void *ptr1) noexcept
check if wave of 2 pointers are the same (null or FULL)
unsigned bit_find_last(const bm::word_t *block, unsigned *last) noexcept
BIT block find the last set bit (backward search)
bool bit_find_first(const bm::word_t *block, unsigned *pos) noexcept
BIT block find the first set bit.
bm::word_t * bit_operation_sub(bm::word_t *dst, const bm::word_t *src) noexcept
bitblock SUB operation.
unsigned word_bitcount64(bm::id64_t x) noexcept
bm::id64_t bit_block_xor(bm::word_t *dst, const bm::word_t *src) noexcept
Plain bitblock XOR operation. Function does not analyse availability of source and destination blocks...
bm::id_t word_bitcount(bm::id_t w) noexcept
void bit_invert(T *start) noexcept
bool bit_block_or(bm::word_t *dst, const bm::word_t *src) noexcept
Plain bitblock OR operation. Function does not analyse availability of source and destination blocks.
bm::id64_t bit_block_and(bm::word_t *dst, const bm::word_t *src) noexcept
Plain bitblock AND operation. Function does not analyse availability of source and destination blocks...
void bit_andnot_arr_ffmask(bm::word_t *dst, const bm::word_t *src) noexcept
bitblock AND NOT with constant ~0 mask operation.
bool bit_block_or_2way(bm::word_t *dst, const bm::word_t *src1, const bm::word_t *src2) noexcept
2 way (target := source1 | source2) bitblock OR operation.
unsigned bit_block_find(const bm::word_t *block, unsigned nbit, unsigned *pos) noexcept
Searches for the next 1 bit in the BIT block.
bool is_bits_one(const bm::wordop_t *start) noexcept
Returns "true" if all bits in the block are 1.
bm::id_t bit_block_calc_count_range(const bm::word_t *block, bm::word_t left, bm::word_t right) noexcept
unsigned short bitscan_wave(const bm::word_t *w_ptr, unsigned char *bits) noexcept
Unpacks word wave (Nx 32-bit words)
bm::id64_t bit_block_and_or_2way(bm::word_t *dst, const bm::word_t *src1, const bm::word_t *src2, bm::id64_t digest) noexcept
digest based bit-block AND - OR
bool bit_is_all_zero(const bm::word_t *start) noexcept
Returns "true" if all bits in the block are 0.
bool bit_block_shift_r1_unr(bm::word_t *block, bm::word_t *empty_acc, bm::word_t co_flag) noexcept
Right bit-shift of bit-block by 1 bit (loop unrolled)
void bit_block_set(bm::word_t *dst, bm::word_t value) noexcept
Bitblock memset operation.
bm::id_t bit_block_calc_count_to(const bm::word_t *block, bm::word_t right) noexcept
void bit_block_copy(bm::word_t *dst, const bm::word_t *src) noexcept
Bitblock copy operation.
bm::id64_t bit_block_and_2way(bm::word_t *dst, const bm::word_t *src1, const bm::word_t *src2, bm::id64_t digest) noexcept
digest based bit-block AND
bool bit_block_shift_l1_unr(bm::word_t *block, bm::word_t *empty_acc, bm::word_t co_flag) noexcept
Left bit-shift of bit-block by 1 bit (loop unrolled)
bm::word_t bit_block_insert(bm::word_t *block, unsigned bitpos, bool value) noexcept
insert bit into position and shift the rest right with carryover
bm::word_t * bit_operation_xor(bm::word_t *dst, const bm::word_t *src) noexcept
bitblock XOR operation.
void bit_block_erase(bm::word_t *block, unsigned bitpos, bool carry_over) noexcept
erase bit from position and shift the rest right with carryover
bm::word_t * bit_operation_and(bm::word_t *dst, const bm::word_t *src) noexcept
bitblock AND operation.
int bitcmp(const T *buf1, const T *buf2, unsigned len) noexcept
Lexicographical comparison of BIT buffers.
bm::id64_t bit_block_sub_2way(bm::word_t *dst, const bm::word_t *src1, const bm::word_t *src2, bm::id64_t digest) noexcept
digest based bitblock SUB (AND NOT) operation (3 operand)
bm::word_t * bit_operation_or(bm::word_t *dst, const bm::word_t *src) noexcept
Block OR operation. Makes analysis if block is 0 or FULL.
bm::id64_t calc_block_digest0(const bm::word_t *const block) noexcept
Compute digest for 64 non-zero areas.
bm::id64_t bit_block_xor_2way(bm::word_t *dst, const bm::word_t *src1, const bm::word_t *src2) noexcept
2 way (target := source1 ^ source2) bitblock XOR operation.
bm::id64_t bit_block_sub(bm::word_t *dst, const bm::word_t *src) noexcept
Plain bitblock SUB (AND NOT) operation. Function does not analyse availability of source and destinat...
sort_order
Sort order declaration.
bm::alloc_pool_guard< allocator_pool_type, bvector< Alloc > > mem_pool_guard
int(* bit_visitor_callback_type)(void *handle_ptr, bm::id_t bit_idx)
Callback type to visit (callback style) bits in bit-vector(s)
finalization
copy strategy
strategy
Block allocation strategies.
@ BM_SORTED
input set is sorted (ascending order)
@ BM_UNKNOWN
sort order unknown
@ READWRITE
mutable (read-write object)
@ READONLY
immutable (read-only object)
@ BM_BIT
No GAP compression strategy. All new blocks are bit blocks.
@ BM_GAP
GAP compression is ON.
unsigned gap_bit_count_range(const T *const buf, unsigned left, unsigned right) noexcept
Counts 1 bits in GAP buffer in the closed [left, right] range.
unsigned gap_limit(const T *buf, const T *glevel_len) noexcept
Returs GAP block capacity limit.
gap_word_t * gap_operation_xor(const gap_word_t *vect1, const gap_word_t *vect2, gap_word_t *tmp_buf, unsigned &dsize) noexcept
GAP XOR operation.
bool gap_shift_r1(T *buf, unsigned co_flag, unsigned *new_len) noexcept
Right shift GAP block by 1 bit.
void gap_invert(T *buf) noexcept
Inverts all bits in the GAP buffer.
void gap_add_to_bitset(unsigned *dest, const T *pcurr, unsigned len) noexcept
Adds(OR) GAP block to bitblock.
gap_word_t * gap_operation_or(const gap_word_t *vect1, const gap_word_t *vect2, gap_word_t *tmp_buf, unsigned &dsize) noexcept
GAP OR operation.
bool improve_gap_levels(const T *length, const T *length_end, T *glevel_len) noexcept
Finds optimal gap blocks lengths.
unsigned gap_test_unr(const T *buf, const unsigned pos) noexcept
Tests if bit = pos is true. Analog of bm::gap_test with SIMD unrolling.
bool gap_is_all_zero(const bm::gap_word_t *buf) noexcept
Checks if GAP block is all-zero.
void gap_convert_to_bitset(unsigned *dest, const T *buf, unsigned len=0) noexcept
GAP block to bitblock conversion.
gap_word_t * gap_operation_sub(const gap_word_t *vect1, const gap_word_t *vect2, gap_word_t *tmp_buf, unsigned &dsize) noexcept
GAP SUB (AND NOT) operation.
void gap_xor_to_bitset(unsigned *dest, const T *pcurr) noexcept
XOR GAP block to bitblock.
unsigned gap_set_value_cpos(unsigned val, T *buf, unsigned pos, unsigned *is_set, unsigned curr) noexcept
Sets or clears bit in the GAP buffer.
gap_word_t * gap_operation_and(const gap_word_t *vect1, const gap_word_t *vect2, gap_word_t *tmp_buf, unsigned &dsize) noexcept
GAP AND operation.
unsigned gap_find_first(const T *buf, unsigned *first) noexcept
GAP block find the first set bit.
unsigned gap_find_last(const T *buf, unsigned *last) noexcept
GAP block find the last set bit.
unsigned gap_capacity(const T *buf, const T *glevel_len) noexcept
Returs GAP block capacity.
T gap_level(const T *buf) noexcept
Returs GAP blocks capacity level.
unsigned gap_block_find(const T *buf, unsigned nbit, bm::id_t *prev) noexcept
Searches for the next 1 bit in the GAP block.
unsigned gap_set_value(unsigned val, T *buf, unsigned pos, unsigned *is_set) noexcept
Sets or clears bit in the GAP buffer.
bool gap_shift_l1(T *buf, unsigned co_flag, unsigned *new_len) noexcept
Left shift GAP block by 1 bit.
void gap_and_to_bitset(unsigned *dest, const T *pcurr) noexcept
ANDs GAP block to bitblock.
int gapcmp(const T *buf1, const T *buf2) noexcept
Lexicographical comparison of GAP buffers.
unsigned gap_bit_count_range_hint(const T *const buf, unsigned left, unsigned right, unsigned hint) noexcept
Counts 1 bits in GAP buffer in the closed [left, right] range using position hint to avoid bfind.
bm::gap_word_t gap_length(const bm::gap_word_t *buf) noexcept
Returs GAP block length.
void gap_sub_to_bitset(unsigned *dest, const T *pcurr) noexcept
SUB (AND NOT) GAP block to bitblock.
unsigned * gap_convert_to_bitset_smart(unsigned *dest, const T *buf, id_t set_max) noexcept
Smart GAP block to bitblock conversion.
bool gap_insert(T *buf, unsigned pos, unsigned val, unsigned *new_len) noexcept
isnert bit into GAP compressed block
unsigned int
A callback function used to compare two keys in a database.
if(yy_accept[yy_current_state])
const unsigned set_array_mask
void for_each_nzblock(T ***root, unsigned size1, F &f)
SIZE_TYPE block_find_rank(const bm::word_t *const block, SIZE_TYPE rank, unsigned nbit_from, unsigned &nbit_pos) noexcept
Find rank in block (GAP or BIT)
void xor_swap(W &x, W &y) noexcept
XOR swap two variables.
bool block_find_reverse(const bm::word_t *block, unsigned nbit_from, unsigned *found_nbit) noexcept
Reverse find 1.
const unsigned set_block_mask
bool find_not_null_ptr(const bm::word_t *const *const *arr, N start, N size, N *pos) noexcept
unsigned gap_bit_count_to(const T *const buf, T right) noexcept
bool block_any(const bm::word_t *const block) noexcept
Returns "true" if one bit is set in the block Function check for block varieties.
bvector< Alloc > operator-(const bvector< Alloc > &bv1, const bvector< Alloc > &bv2)
const unsigned set_sub_array_size
void get_block_coord(BI_TYPE nb, unsigned &i, unsigned &j) noexcept
Recalc linear bvector block index into 2D matrix coordinates.
bm::id64_t idx_arr_block_lookup_u64(const bm::id64_t *idx, bm::id64_t size, bm::id64_t nb, bm::id64_t start) noexcept
block boundaries look ahead U32
const unsigned bits_in_array
const unsigned set_total_blocks
void for_each_nzblock_range(T ***root, N top_size, N nb_from, N nb_to, F &f) noexcept
bool block_is_all_one_range(const bm::word_t *const block, unsigned left, unsigned right) noexcept
Returns "true" if all bits are 1 in the block [left, right] Function check for block varieties.
bool check_block_one(const bm::word_t *blk, bool deep_scan) noexcept
Checks if block has only 1 bits.
const unsigned set_block_size_op
const unsigned rs3_half_span
unsigned idx_arr_block_lookup_u32(const unsigned *idx, unsigned size, unsigned nb, unsigned start) noexcept
block boundaries look ahead U32
const unsigned gap_levels
gap_word_t *(* gap_operation_func_type)(const gap_word_t *, const gap_word_t *, gap_word_t *, unsigned &)
const unsigned set_word_shift
unsigned char get_nibble(const unsigned char *arr, unsigned idx) noexcept
get nibble from the array
bool for_each_nzblock_if(T ***root, BI size1, F &f) noexcept
const unsigned set_block_size
unsigned long long int id64_t
const unsigned gap_equiv_len
unsigned gap_bfind(const T *buf, unsigned pos, unsigned *is_set) noexcept
const unsigned rs3_border0_1
bvector< Alloc > operator|(const bvector< Alloc > &bv1, const bvector< Alloc > &bv2)
bool block_find_first_diff(const bm::word_t *blk, const bm::word_t *arg_blk, unsigned *pos) noexcept
Find first bit which is different between two blocks (GAP or bit)
const unsigned rs3_border1
bvector< Alloc > operator^(const bvector< Alloc > &bv1, const bvector< Alloc > &bv2)
const unsigned short set_bitscan_wave_size
Size of bit decode wave in words.
const unsigned set_array_shift
unsigned short gap_word_t
const unsigned rs3_border1_1
void(* gap_operation_to_bitset_func_type)(unsigned *, const gap_word_t *)
bm::id_t bvector_size_type
const unsigned rs3_border0
const unsigned gap_max_bits
const unsigned set_top_array_size
void set_block_bits_u64(bm::word_t *block, const bm::id64_t *idx, bm::id64_t start, bm::id64_t stop) noexcept
set bits in a bit-block using global index
const word_t all_bits_mask
const unsigned set_block_shift
void set_block_bits_u32(bm::word_t *block, const unsigned *idx, unsigned start, unsigned stop) noexcept
set bits in a bit-block using global index
const unsigned set_word_mask
const unsigned bits_in_block
bool block_any_range(const bm::word_t *const block, unsigned left, unsigned right) noexcept
Returns "true" if one bit is set in the block [left, right] Function check for block varieties.
const GenericPointer< typename T::ValueType > T2 value
double r(size_t dimension_, const Int4 *score_, const double *prob_, double theta_)
double f(double x_, const double &y_)
Allocation arena for ReadOnly vectors.
Structure with statistical information about memory allocation footprint, serialization projection,...
void reset() noexcept
Reset statisctics.
gap_word_t gap_levels[bm::gap_levels]
GAP block lengths in the bvect.
size_t max_serialize_mem
estimated maximum memory for serialization
size_t memory_used
memory usage for all blocks and service tables
allocation_policy(bm::strategy s=BM_BIT, const gap_word_t *glevels=bm::gap_len_table< true >::_len) noexcept
const gap_word_t * glevel_len
unsigned short idx
Current position in the bit list.
unsigned char bits[set_bitscan_wave_size *32]
bit list
size_type pos
Last bit position decode before.
unsigned short cnt
Number of ON bits.
const bm::word_t * ptr
Word pointer.
Information about current DGAP block.
const gap_word_t * ptr
Word pointer.
gap_word_t gap_len
Current dgap length.
Statistical information about bitset's memory allocation details.
Default GAP lengths table.
static gap_operation_to_bitset_func_type gap_op_to_bit(unsigned i)
static gap_operation_func_type gap_operation(unsigned i)
Precalculated decision table fdr interval selection.
dgap_descr gap_
DGAP block related info.
bitblock_descr bit_
BitBlock related info.
static void copy_block(deflate_state *s, uint8_t *buf, unsigned len, int header)