BitMagic-C++
bmalgo.h
Go to the documentation of this file.
1 #ifndef BMALGO__H__INCLUDED__
2 #define BMALGO__H__INCLUDED__
3 /*
4 Copyright(c) 2002-2017 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
5 
6 Licensed under the Apache License, Version 2.0 (the "License");
7 you may not use this file except in compliance with the License.
8 You may obtain a copy of the License at
9 
10  http://www.apache.org/licenses/LICENSE-2.0
11 
12 Unless required by applicable law or agreed to in writing, software
13 distributed under the License is distributed on an "AS IS" BASIS,
14 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 See the License for the specific language governing permissions and
16 limitations under the License.
17 
18 For more information please visit: http://bitmagic.io
19 */
20 
21 /*! \file bmalgo.h
22  \brief Algorithms for bvector<> (main include)
23 */
24 
25 #ifndef BM__H__INCLUDED__
26 // BitMagic utility headers do not include main "bm.h" declaration
27 // #include "bm.h" or "bm64.h" explicitly
28 # error missing include (bm.h or bm64.h)
29 #endif
30 
31 #include "bmfunc.h"
32 #include "bmdef.h"
33 
34 #include "bmalgo_impl.h"
35 
36 
37 
38 namespace bm
39 {
40 
41 /*!
42  \brief Computes bitcount of AND operation of two bitsets
43  \param bv1 - Argument bit-vector.
44  \param bv2 - Argument bit-vector.
45  \return bitcount of the result
46  \ingroup setalgo
47 */
48 template<class BV>
49 typename BV::size_type count_and(const BV& bv1, const BV& bv2) BMNOEXCEPT
50 {
51  return bm::distance_and_operation(bv1, bv2);
52 }
53 
54 /*!
55  \brief Computes if there is any bit in AND operation of two bitsets
56  \param bv1 - Argument bit-vector.
57  \param bv2 - Argument bit-vector.
58  \return non zero value if there is any bit
59  \ingroup setalgo
60 */
61 template<class BV>
62 typename BV::size_type any_and(const BV& bv1, const BV& bv2) BMNOEXCEPT
63 {
65 
66  distance_operation_any(bv1, bv2, &dmd, &dmd + 1);
67  return dmd.result;
68 }
69 
70 
71 
72 /*!
73  \brief Computes bitcount of XOR operation of two bitsets
74  \param bv1 - Argument bit-vector.
75  \param bv2 - Argument bit-vector.
76  \return bitcount of the result
77  \ingroup setalgo
78 */
79 template<class BV>
81 count_xor(const BV& bv1, const BV& bv2) BMNOEXCEPT
82 {
84 
85  distance_operation(bv1, bv2, &dmd, &dmd + 1);
86  return dmd.result;
87 }
88 
89 /*!
90  \brief Computes if there is any bit in XOR operation of two bitsets
91  \param bv1 - Argument bit-vector.
92  \param bv2 - Argument bit-vector.
93  \return non zero value if there is any bit
94  \ingroup setalgo
95 */
96 template<class BV>
97 typename BV::size_type any_xor(const BV& bv1, const BV& bv2) BMNOEXCEPT
98 {
100 
101  distance_operation_any(bv1, bv2, &dmd, &dmd + 1);
102  return dmd.result;
103 }
104 
105 
106 
107 /*!
108  \brief Computes bitcount of SUB operation of two bitsets
109  \param bv1 - Argument bit-vector.
110  \param bv2 - Argument bit-vector.
111  \return bitcount of the result
112  \ingroup setalgo
113 */
114 template<class BV>
115 typename BV::size_type count_sub(const BV& bv1, const BV& bv2) BMNOEXCEPT
116 {
118 
119  distance_operation(bv1, bv2, &dmd, &dmd + 1);
120  return dmd.result;
121 }
122 
123 
124 /*!
125  \brief Computes if there is any bit in SUB operation of two bitsets
126  \param bv1 - Argument bit-vector.
127  \param bv2 - Argument bit-vector.
128  \return non zero value if there is any bit
129  \ingroup setalgo
130 */
131 template<class BV>
132 typename BV::size_type any_sub(const BV& bv1, const BV& bv2) BMNOEXCEPT
133 {
135 
136  distance_operation_any(bv1, bv2, &dmd, &dmd + 1);
137  return dmd.result;
138 }
139 
140 
141 /*!
142  \brief Computes bitcount of OR operation of two bitsets
143  \param bv1 - Argument bit-vector.
144  \param bv2 - Argument bit-vector.
145  \return bitcount of the result
146  \ingroup setalgo
147 */
148 template<class BV>
149 typename BV::size_type count_or(const BV& bv1, const BV& bv2) BMNOEXCEPT
150 {
152 
153  distance_operation(bv1, bv2, &dmd, &dmd + 1);
154  return dmd.result;
155 }
156 
157 /*!
158  \brief Computes if there is any bit in OR operation of two bitsets
159  \param bv1 - Argument bit-vector.
160  \param bv2 - Argument bit-vector.
161  \return non zero value if there is any bit
162  \ingroup setalgo
163 */
164 template<class BV>
165 typename BV::size_type any_or(const BV& bv1, const BV& bv2) BMNOEXCEPT
166 {
168 
169  distance_operation_any(bv1, bv2, &dmd, &dmd + 1);
170  return dmd.result;
171 }
172 
173 
174 
175 #define BM_SCANNER_OP(x) \
176 if (0 != (block = blk_blk[j+x])) \
177 { \
178  if (BM_IS_GAP(block)) \
179  { \
180  bm::for_each_gap_blk(BMGAP_PTR(block), (r+j+x)*bm::bits_in_block,\
181  bit_functor); \
182  } \
183  else \
184  { \
185  bm::for_each_bit_blk(block, (r+j+x)*bm::bits_in_block,bit_functor); \
186  } \
187 }
188 
189 
190 /**
191  @brief bit-vector visitor scanner to traverse each 1 bit using C++ visitor
192 
193  @param bv - bit vector to scan
194  @param bit_functor - visitor: should support add_bits(), add_range()
195 
196  \ingroup setalgo
197  @sa for_each_bit_range visit_each_bit
198 */
199 template<class BV, class Func>
200 void for_each_bit(const BV& bv,
201  Func& bit_functor)
202 {
203  typedef typename BV::size_type size_type;
204 
205  const typename BV::blocks_manager_type& bman = bv.get_blocks_manager();
206  bm::word_t*** blk_root = bman.top_blocks_root();
207 
208  if (!blk_root)
209  return;
210 
211  unsigned tsize = bman.top_block_size();
212  for (unsigned i = 0; i < tsize; ++i)
213  {
214  bm::word_t** blk_blk = blk_root[i];
215  if (!blk_blk)
216  continue;
217 
218  if ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR)
219  blk_blk = FULL_SUB_BLOCK_REAL_ADDR;
220 
221  const bm::word_t* block;
222  size_type r = size_type(i) * bm::set_sub_array_size;
223  unsigned j = 0;
224  do
225  {
226  #ifdef BM64_AVX2
227  if (!avx2_test_all_zero_wave(blk_blk + j))
228  {
229  BM_SCANNER_OP(0)
230  BM_SCANNER_OP(1)
231  BM_SCANNER_OP(2)
232  BM_SCANNER_OP(3)
233  }
234  j += 4;
235  #elif defined(BM64_SSE4)
236  if (!sse42_test_all_zero_wave(blk_blk + j))
237  {
238  BM_SCANNER_OP(0)
239  BM_SCANNER_OP(1)
240  }
241  j += 2;
242  #else
243  BM_SCANNER_OP(0)
244  ++j;
245  #endif
246 
247  } while (j < bm::set_sub_array_size);
248 
249  } // for i
250 }
251 
252 /**
253  @brief bit-vector range visitor to traverse each 1 bit
254 
255  @param bv - bit vector to scan
256  @param right - start of closed interval [from..to]
257  @param left - end of close interval [from..to]
258  @param bit_functor - visitor: should support add_bits(), add_range()
259 
260  \ingroup setalgo
261  @sa for_each_bit
262 */
263 template<class BV, class Func>
264 void for_each_bit_range(const BV& bv,
265  typename BV::size_type left,
266  typename BV::size_type right,
267  Func& bit_functor)
268 {
269  if (left > right)
270  bm::xor_swap(left, right);
271  if (right == bm::id_max)
272  --right;
273  BM_ASSERT(left < bm::id_max && right < bm::id_max);
274 
275  bm::for_each_bit_range_no_check(bv, left, right, bit_functor);
276 }
277 
278 
279 #undef BM_SCANNER_OP
280 
281 
282 /// private adaptor for C-style callbacks
283 ///
284 /// @internal
285 ///
286 template <class VCBT, class size_type>
288 {
290 
292  : handle_(h), func_(cb_func)
293  {}
294 
295  void add_bits(size_type offset, const unsigned char* bits, unsigned size)
296  {
297  for (unsigned i = 0; i < size; ++i)
298  func_(handle_, offset + bits[i]);
299  }
300  void add_range(size_type offset, size_type size)
301  {
302  for (size_type i = 0; i < size; ++i)
303  func_(handle_, offset + i);
304  }
305 
306  void* handle_;
308 };
309 
310 
311 /// Functor for bit-copy (for testing)
312 ///
313 /// @internal
314 ///
315 template <class BV>
317 {
318  typedef typename BV::size_type size_type;
319 
321  : bv_(bv)
322  {
323  bv_.init();
324  }
325 
326  void add_bits(size_type offset, const unsigned char* bits, unsigned size)
327  {
328  BM_ASSERT(size);
329  for (unsigned i = 0; i < size; ++i)
330  bv_.set_bit_no_check(offset + bits[i]);
331  }
332  void add_range(size_type offset, size_type size)
333  {
334  BM_ASSERT(size);
335  bv_.set_range(offset, offset + size - 1);
336  }
337 
338  BV& bv_;
340 };
341 
342 
343 
344 /**
345  @brief bvector visitor scanner to traverse each 1 bit using C callback
346 
347  @param bv - bit vector to scan
348  @param handle_ptr - handle to private memory used by callback
349  @param callback_ptr - callback function
350 
351  \ingroup setalgo
352 
353  @sa bit_visitor_callback_type
354 */
355 template<class BV>
356 void visit_each_bit(const BV& bv,
357  void* handle_ptr,
358  bit_visitor_callback_type callback_ptr)
359 {
360  typedef typename BV::size_type size_type;
362  func(handle_ptr, callback_ptr);
363  bm::for_each_bit(bv, func);
364 }
365 
366 /**
367  @brief bvector visitor scanner to traverse each bits in range (C callback)
368 
369  @param bv - bit vector to scan
370  @param left - from [left..right]
371  @param right - to [left..right]
372  @param handle_ptr - handle to private memory used by callback
373  @param callback_ptr - callback function
374 
375  \ingroup setalgo
376 
377  @sa bit_visitor_callback_type for_each_bit
378 */
379 template<class BV>
380 void visit_each_bit_range(const BV& bv,
381  typename BV::size_type left,
382  typename BV::size_type right,
383  void* handle_ptr,
384  bit_visitor_callback_type callback_ptr)
385 {
386  typedef typename BV::size_type size_type;
388  func(handle_ptr, callback_ptr);
389  bm::for_each_bit_range(bv, left, right, func);
390 }
391 
392 /**
393  @brief Algorithm to identify bit-vector ranges (splits) for the rank
394 
395  Rank range split algorithm walks the bit-vector to create list of
396  non-overlapping ranges [s1..e1],[s2..e2]...[sN...eN] with requested
397  (rank) number of 1 bits. All ranges should be the same popcount weight,
398  except the last one, which may have less.
399  Scan is progressing from left to right so result ranges will be
400  naturally sorted.
401 
402  @param bv - bit vector to perform the range split scan
403  @param rank - requested number of bits in each range
404  if 0 it will create single range [first..last]
405  to cover the whole bv
406  @param target_v - [out] STL(or STL-like) vector of pairs to keep pairs results
407 
408  \ingroup setalgo
409  */
410 template<typename BV, typename PairVect>
411 void rank_range_split(const BV& bv,
412  typename BV::size_type rank,
413  PairVect& target_v)
414 {
415  target_v.resize(0);
416  typename BV::size_type first, last, pos;
417  bool found = bv.find_range(first, last);
418  if (!found) // empty bit-vector
419  return;
420 
421  if (!rank) // if rank is not defined, include the whole vector [first..last]
422  {
423  typename PairVect::value_type pv;
424  pv.first = first; pv.second = last;
425  target_v.push_back(pv);
426  return;
427  }
428 
429  while (1)
430  {
431  typename PairVect::value_type pv;
432  found = bv.find_rank(rank, first, pos);
433  if (found)
434  {
435  pv.first = first; pv.second = pos;
436  target_v.push_back(pv);
437  if (pos >= last)
438  break;
439  first = pos + 1;
440  continue;
441  }
442  // insufficient rank (last range)
443  found = bv.any_range(first, last);
444  if (found)
445  {
446  pv.first = first; pv.second = last;
447  target_v.push_back(pv);
448  }
449  break;
450  } // while
451 
452 }
453 
454 
455 
456 /**
457  Algorithms for rank compression of bit-vector
458 
459  1. Source vector (bv_src) is a subset of index vector (bv_idx)
460  2. As a subset it can be collapsed using bit-rank method, where each position
461  in the source vector is defined by population count (range)
462  [0..index_position] (count_range())
463  As a result all integer set of source vector gets re-mapped in
464  accord with the index vector.
465 
466  \ingroup setalgo
467 */
468 template<typename BV>
470 {
471 public:
472  typedef BV bvector_type;
473  typedef typename BV::size_type size_type;
474  typedef typename BV::rs_index_type rs_index_type;
476  {
478  };
479 public:
480 
481  /**
482  Rank decompression
483  */
484  void decompress(BV& bv_target, const BV& bv_idx, const BV& bv_src);
485 
486  /**
487  Rank compression algorithm based on two palallel iterators/enumerators
488  set of source vector gets re-mapped in accord with the index/rank vector.
489 
490  \param bv_target - target bit-vector
491  \param bv_idx - index (rank) vector used for address recalculation
492  \param bv_src - source vector for re-mapping
493  */
494  void compress(BV& bv_target, const BV& bv_idx, const BV& bv_src);
495 
496  /**
497  \brief Source vector priority + index based rank
498 
499  @sa compress
500  */
501  void compress_by_source(BV& bv_target,
502  const BV& bv_idx,
503  const rs_index_type& bc_idx,
504  const BV& bv_src);
505 };
506 
507 
508 // ------------------------------------------------------------------------
509 //
510 // ------------------------------------------------------------------------
511 
512 
513 template<class BV>
514 void rank_compressor<BV>::compress(BV& bv_target,
515  const BV& bv_idx,
516  const BV& bv_src)
517 {
518  bv_target.clear();
519  bv_target.init();
520 
521  if (&bv_idx == &bv_src)
522  {
523  bv_target = bv_src;
524  return;
525  }
526  size_type ibuffer[n_buffer_cap];
527  size_type b_size;
528 
529  typedef typename BV::enumerator enumerator_t;
530  enumerator_t en_s = bv_src.first();
531  enumerator_t en_i = bv_idx.first();
532 
533  size_type r_idx = b_size = 0;
534  size_type i, s;
535 
536  for (; en_i.valid(); )
537  {
538  if (!en_s.valid())
539  break;
540  i = *en_i; s = *en_s;
541 
542  BM_ASSERT(s >= i);
543  BM_ASSERT(bv_idx.test(i));
544 
545  if (i == s)
546  {
547  ibuffer[b_size++] = r_idx++;
548  if (b_size == n_buffer_cap)
549  {
550  bv_target.set(ibuffer, b_size, bm::BM_SORTED);
551  b_size = 0;
552  }
553  ++en_i; ++en_s;
554  continue;
555  }
556  BM_ASSERT(s > i);
557 
558  size_type dist = s - i;
559  if (dist >= 64) // sufficiently far away, jump
560  {
561  size_type r_dist = bv_idx.count_range(i + 1, s);
562  r_idx += r_dist;
563  en_i.go_to(s);
564  BM_ASSERT(en_i.valid());
565  }
566  else // small distance, iterate to close the gap
567  {
568  for (; s > i; ++r_idx)
569  {
570  ++en_i;
571  i = *en_i;
572  } // for
573  BM_ASSERT(en_i.valid());
574  }
575  } // for
576 
577  if (b_size)
578  {
579  bv_target.set(ibuffer, b_size, bm::BM_SORTED);
580  }
581 
582 }
583 
584 // ------------------------------------------------------------------------
585 
586 template<class BV>
588  const BV& bv_idx,
589  const BV& bv_src)
590 {
591  bv_target.clear();
592  bv_target.init();
593 
594  if (&bv_idx == &bv_src)
595  {
596  bv_target = bv_src;
597  return;
598  }
599 
600  size_type r_idx, i, s, b_size;
601  size_type ibuffer[n_buffer_cap];
602 
603  b_size = r_idx = 0;
604 
605  typedef typename BV::enumerator enumerator_t;
606  enumerator_t en_s = bv_src.first();
607  enumerator_t en_i = bv_idx.first();
608  for (; en_i.valid(); )
609  {
610  if (!en_s.valid())
611  break;
612  s = *en_s;
613  i = *en_i;
614  if (s == r_idx)
615  {
616  ibuffer[b_size++] = i;
617  if (b_size == n_buffer_cap)
618  {
619  bv_target.set(ibuffer, b_size, bm::BM_SORTED);
620  b_size = 0;
621  }
622  ++en_i; ++en_s; ++r_idx;
623  continue;
624  }
625  // source is "faster" than index, need to re-align
626  BM_ASSERT(s > r_idx);
627  size_type rank = s - r_idx + 1u;
628  size_type new_pos = 0;
629 
630  if (rank < 256)
631  {
632  en_i.skip(s - r_idx);
633  BM_ASSERT(en_i.valid());
634  new_pos = *en_i;
635  }
636  else
637  {
638  bv_idx.find_rank(rank, i, new_pos);
639  BM_ASSERT(new_pos);
640  en_i.go_to(new_pos);
641  BM_ASSERT(en_i.valid());
642  }
643 
644  r_idx = s;
645  ibuffer[b_size++] = new_pos;
646  if (b_size == n_buffer_cap)
647  {
648  bv_target.set(ibuffer, b_size, bm::BM_SORTED);
649  b_size = 0;
650  }
651  ++en_i; ++en_s; ++r_idx;
652 
653  } // for en
654 
655  if (b_size)
656  {
657  bv_target.set(ibuffer, b_size, bm::BM_SORTED);
658  }
659 }
660 
661 // ------------------------------------------------------------------------
662 
663 template<class BV>
665  const BV& bv_idx,
666  const rs_index_type& bc_idx,
667  const BV& bv_src)
668 {
669  /// Rank compressor visitor (functor)
670  /// @internal
671  struct visitor_func
672  {
673  visitor_func(bvector_type& bv_out,
674  const bvector_type& bv_index,
675  const rs_index_type& bc_index)
676  : bv_target_(bv_out),
677  bv_index_(bv_index),
678  bc_index_(bc_index)
679  {}
680 
681  void add_bits(size_type arr_offset, const unsigned char* bits, unsigned bits_size)
682  {
683  for (unsigned i = 0; i < bits_size; ++i)
684  {
685  size_type idx = arr_offset + bits[i];
686  BM_ASSERT(bv_index_.test(idx));
687 
688  size_type r_idx = bv_index_.count_to(idx, bc_index_) - 1;
689  bv_target_.set_bit_no_check(r_idx);
690  }
691  }
692  void add_range(size_type arr_offset, size_type sz)
693  {
694  for (size_type i = 0; i < sz; ++i)
695  {
696  size_type idx = i + arr_offset;
697  BM_ASSERT(bv_index_.test(idx));
698 
699  size_type r_idx = bv_index_.count_to(idx, bc_index_) - 1;
700  bv_target_.set_bit_no_check(r_idx);
701  }
702  }
703 
704  bvector_type& bv_target_;
705  const bvector_type& bv_index_;
706  const rs_index_type& bc_index_;
707  };
708  // ------------------------------------
709 
710  bv_target.clear();
711  bv_target.init();
712 
713  if (&bv_idx == &bv_src)
714  {
715  bv_target = bv_src;
716  return;
717  }
718  visitor_func func(bv_target, bv_idx, bc_idx);
719  bm::for_each_bit(bv_src, func);
720 }
721 
722 
723 
724 
725 } // bm
726 
727 #include "bmundef.h"
728 
729 #endif
bm::rank_compressor< bvector_type >::buffer_cap
buffer_cap
Definition: bmalgo.h:475
bm::rank_compressor::decompress
void decompress(BV &bv_target, const BV &bv_idx, const BV &bv_src)
Rank decompression.
Definition: bmalgo.h:587
bm::bit_vitor_callback_adaptor::add_bits
void add_bits(size_type offset, const unsigned char *bits, unsigned size)
Definition: bmalgo.h:295
bm::for_each_bit_range
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
Definition: bmalgo.h:264
bm::rank_compressor::size_type
BV::size_type size_type
Definition: bmalgo.h:473
bmfunc.h
Bit manipulation primitives (internal)
bm::distance_operation_any
void distance_operation_any(const BV &bv1, const BV &bv2, distance_metric_descriptor *dmit, distance_metric_descriptor *dmit_end) BMNOEXCEPT
Distance screening template function.
Definition: bmalgo_impl.h:858
bm::distance_metric_descriptor
Distance metric descriptor, holds metric code and result.
Definition: bmalgo_impl.h:87
bm::bit_vistor_copy_functor::func_
bit_visitor_callback_type func_
Definition: bmalgo.h:339
FULL_SUB_BLOCK_REAL_ADDR
#define FULL_SUB_BLOCK_REAL_ADDR
Definition: bmdef.h:150
bv_index
Definition: xsample01.cpp:132
BM_SCANNER_OP
#define BM_SCANNER_OP(x)
Definition: bmalgo.h:175
bm::bit_vistor_copy_functor::bit_vistor_copy_functor
bit_vistor_copy_functor(BV &bv)
Definition: bmalgo.h:320
bm::rank_compressor::compress
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...
Definition: bmalgo.h:514
bm::BM_SORTED
@ BM_SORTED
input set is sorted (ascending order)
Definition: bmconst.h:191
bm::bit_vitor_callback_adaptor::func_
bit_visitor_callback_type func_
Definition: bmalgo.h:307
bm::bit_vistor_copy_functor::size_type
BV::size_type size_type
Definition: bmalgo.h:318
bm::bit_vitor_callback_adaptor::add_range
void add_range(size_type offset, size_type size)
Definition: bmalgo.h:300
bm::bit_vistor_copy_functor::add_bits
void add_bits(size_type offset, const unsigned char *bits, unsigned size)
Definition: bmalgo.h:326
bm::set_sub_array_size
const unsigned set_sub_array_size
Definition: bmconst.h:94
bm::bit_vitor_callback_adaptor::handle_
void * handle_
Definition: bmalgo.h:306
bm::COUNT_OR
@ COUNT_OR
(A | B).count()
Definition: bmalgo_impl.h:61
bmundef.h
pre-processor un-defines to avoid global space pollution (internal)
bm::bit_vitor_callback_adaptor
private adaptor for C-style callbacks
Definition: bmalgo.h:287
bm::id_max
const unsigned id_max
Definition: bmconst.h:108
bm::distance_metric_descriptor::result
size_type result
Definition: bmalgo_impl.h:96
bm::xor_swap
void xor_swap(W &x, W &y) BMNOEXCEPT
XOR swap two scalar variables.
Definition: bmfunc.h:911
bm::rank_compressor
Algorithms for rank compression of bit-vector.
Definition: bmalgo.h:469
bm::rank_compressor::rs_index_type
BV::rs_index_type rs_index_type
Definition: bmalgo.h:474
BMNOEXCEPT
#define BMNOEXCEPT
Definition: bmdef.h:79
bm::any_xor
BV::size_type any_xor(const BV &bv1, const BV &bv2) BMNOEXCEPT
Computes if there is any bit in XOR operation of two bitsets.
Definition: bmalgo.h:97
FULL_BLOCK_FAKE_ADDR
#define FULL_BLOCK_FAKE_ADDR
Definition: bmdef.h:149
bm::COUNT_SUB_AB
@ COUNT_SUB_AB
(A - B).count()
Definition: bmalgo_impl.h:62
bm::rank_compressor::compress_by_source
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.
Definition: bmalgo.h:664
bm::bit_vistor_copy_functor::add_range
void add_range(size_type offset, size_type size)
Definition: bmalgo.h:332
BM_ASSERT
#define BM_ASSERT
Definition: bmdef.h:130
bm::count_sub
BV::size_type count_sub(const BV &bv1, const BV &bv2) BMNOEXCEPT
Computes bitcount of SUB operation of two bitsets.
Definition: bmalgo.h:115
bm::bit_vitor_callback_adaptor::bit_vitor_callback_adaptor
bit_vitor_callback_adaptor(void *h, bit_visitor_callback_type cb_func)
Definition: bmalgo.h:291
bmdef.h
Definitions(internal)
bm::bit_vistor_copy_functor::bv_
BV & bv_
Definition: bmalgo.h:338
bm::bit_vistor_copy_functor
Functor for bit-copy (for testing)
Definition: bmalgo.h:316
bm::bit_vitor_callback_adaptor::bit_visitor_callback_type
VCBT bit_visitor_callback_type
Definition: bmalgo.h:289
bm::any_and
BV::size_type any_and(const BV &bv1, const BV &bv2) BMNOEXCEPT
Computes if there is any bit in AND operation of two bitsets.
Definition: bmalgo.h:62
bm::count_xor
bm::distance_metric_descriptor::size_type count_xor(const BV &bv1, const BV &bv2) BMNOEXCEPT
Computes bitcount of XOR operation of two bitsets.
Definition: bmalgo.h:81
bm::for_each_bit
void for_each_bit(const BV &bv, Func &bit_functor)
bit-vector visitor scanner to traverse each 1 bit using C++ visitor
Definition: bmalgo.h:200
bm::count_and
BV::size_type count_and(const BV &bv1, const BV &bv2) BMNOEXCEPT
Computes bitcount of AND operation of two bitsets.
Definition: bmalgo.h:49
bmalgo_impl.h
Algorithms for bvector<>
bm::visit_each_bit
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
Definition: bmalgo.h:356
bm::visit_each_bit_range
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)
Definition: bmalgo.h:380
bm
Definition: bm.h:76
bm::rank_compressor::bvector_type
BV bvector_type
Definition: bmalgo.h:472
bm::any_sub
BV::size_type any_sub(const BV &bv1, const BV &bv2) BMNOEXCEPT
Computes if there is any bit in SUB operation of two bitsets.
Definition: bmalgo.h:132
bm::distance_operation
void distance_operation(const BV &bv1, const BV &bv2, distance_metric_descriptor *dmit, distance_metric_descriptor *dmit_end) BMNOEXCEPT
Distance computing template function.
Definition: bmalgo_impl.h:702
bm::COUNT_XOR
@ COUNT_XOR
(A ^ B).count()
Definition: bmalgo_impl.h:60
bm::count_or
BV::size_type count_or(const BV &bv1, const BV &bv2) BMNOEXCEPT
Computes bitcount of OR operation of two bitsets.
Definition: bmalgo.h:149
bm::word_t
unsigned int word_t
Definition: bmconst.h:38
bm::rank_compressor::n_buffer_cap
@ n_buffer_cap
Definition: bmalgo.h:477
bm::distance_metric_descriptor::size_type
bm::id_t size_type
Definition: bmalgo_impl.h:92
bm::COUNT_AND
@ COUNT_AND
(A & B).count()
Definition: bmalgo_impl.h:59
bit_visitor_callback_type
int(* bit_visitor_callback_type)(void *handle_ptr, bm::id_t bit_idx)
Callback type to visit (callback style) bits in bit-vector(s)
Definition: bm.h:71
bm::rank_range_split
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.
Definition: bmalgo.h:411
bm::distance_and_operation
BV::size_type distance_and_operation(const BV &bv1, const BV &bv2) BMNOEXCEPT
Distance AND computing template function.
Definition: bmalgo_impl.h:789
bm::any_or
BV::size_type any_or(const BV &bv1, const BV &bv2) BMNOEXCEPT
Computes if there is any bit in OR operation of two bitsets.
Definition: bmalgo.h:165
bm::sse42_test_all_zero_wave
BMFORCEINLINE bool sse42_test_all_zero_wave(const void *ptr)
check if wave of pointers is all NULL
Definition: bmsse4.h:595
bm::for_each_bit_range_no_check
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.
Definition: bmalgo_impl.h:1825