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 #define BM_SCANNER_OP(x) \
42  if (0 != (block = blk_blk[j+x])) \
43  { \
44  if (BM_IS_GAP(block)) \
45  { \
46  bm::for_each_gap_blk(BMGAP_PTR(block), (r+j+x)*bm::bits_in_block,\
47  bit_functor); \
48  } \
49  else \
50  { \
51  bm::for_each_bit_blk(block, (r+j+x)*bm::bits_in_block,bit_functor); \
52  } \
53  }
54 
55 
56 /**
57  @brief bit-vector visitor scanner to traverse each 1 bit using C++ visitor
58 
59  @param bv - bit vector to scan
60  @param bit_functor (should support add_bits() and add_range() methods
61 
62  \ingroup setalgo
63 */
64 template<class BV, class Func>
65 void for_each_bit(const BV& bv,
66  Func& bit_functor)
67 {
68  typedef typename BV::size_type size_type;
69 
70  const typename BV::blocks_manager_type& bman = bv.get_blocks_manager();
71  bm::word_t*** blk_root = bman.top_blocks_root();
72 
73  if (!blk_root)
74  return;
75 
76  unsigned tsize = bman.top_block_size();
77  for (unsigned i = 0; i < tsize; ++i)
78  {
79  bm::word_t** blk_blk = blk_root[i];
80  if (!blk_blk)
81  continue;
82 
83  if ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR)
84  blk_blk = FULL_SUB_BLOCK_REAL_ADDR;
85 
86  const bm::word_t* block;
87  size_type r = size_type(i) * bm::set_sub_array_size;
88  unsigned j = 0;
89  do
90  {
91  #ifdef BM64_AVX2
92  if (!avx2_test_all_zero_wave(blk_blk + j))
93  {
94  BM_SCANNER_OP(0)
95  BM_SCANNER_OP(1)
96  BM_SCANNER_OP(2)
97  BM_SCANNER_OP(3)
98  }
99  j += 4;
100  #elif defined(BM64_SSE4)
101  if (!sse42_test_all_zero_wave(blk_blk + j))
102  {
103  BM_SCANNER_OP(0)
104  BM_SCANNER_OP(1)
105  }
106  j += 2;
107  #else
108  BM_SCANNER_OP(0)
109  ++j;
110  #endif
111 
112  } while (j < bm::set_sub_array_size);
113 
114  } // for i
115 }
116 
117 #undef BM_SCANNER_OP
118 
119 /**
120  @brief bit-vector visitor scanner to traverse each 1 bit using C callback
121 
122  @param bv - bit vector to scan
123  @param handle_ptr - handle to private memory used by callback
124  @param callback_ptr - callback function
125 
126  \ingroup setalgo
127 
128  @sa bit_visitor_callback_type
129 */
130 template<class BV>
131 void visit_each_bit(const BV& bv,
132  void* handle_ptr,
133  bit_visitor_callback_type callback_ptr)
134 {
135  typedef typename BV::size_type size_type;
136  // private adaptor for C-style callbacks
137  struct callback_adaptor
138  {
139  callback_adaptor(void* h, bit_visitor_callback_type cb_func)
140  : handle_(h), func_(cb_func)
141  {}
142 
143  void add_bits(size_type offset, const unsigned char* bits, unsigned size)
144  {
145  for (unsigned i = 0; i < size; ++i)
146  func_(handle_, offset + bits[i]);
147  }
148  void add_range(size_type offset, unsigned size)
149  {
150  for (unsigned i = 0; i < size; ++i)
151  func_(handle_, offset + i);
152  }
153 
154  void* handle_;
156  };
157 
158  callback_adaptor func(handle_ptr, callback_ptr);
159  bm::for_each_bit(bv, func);
160 }
161 
162 
163 /**
164  Algorithms for rank compression of bit-vector
165 
166  1. Source vector (bv_src) is a subset of index vector (bv_idx)
167  2. As a subset it can be collapsed using bit-rank method, where each position
168  in the source vector is defined by population count (range) [0..index_position] (count_range())
169  As a result all integer set of source vector gets re-mapped in
170  accord with the index vector.
171 
172  \ingroup setalgo
173 */
174 template<typename BV>
176 {
177 public:
178  typedef BV bvector_type;
179  typedef typename BV::size_type size_type;
180  typedef typename BV::rs_index_type rs_index_type;
182  {
183  n_buffer_cap = 1024
184  };
185 public:
186 
187  /**
188  Rank decompression
189  */
190  void decompress(BV& bv_target, const BV& bv_idx, const BV& bv_src);
191 
192  /**
193  Rank compression algorithm based on two palallel iterators/enumerators set of source
194  vector gets re-mapped in accord with the index/rank vector.
195 
196  \param bv_target - target bit-vector
197  \param bv_idx - index (rank) vector used for address recalculation
198  \param bv_src - source vector for re-mapping
199  */
200  void compress(BV& bv_target, const BV& bv_idx, const BV& bv_src);
201 
202  /**
203  \brief Source vector priority + index based rank
204 
205  @sa compress
206  */
207  void compress_by_source(BV& bv_target,
208  const BV& bv_idx,
209  const rs_index_type& bc_idx,
210  const BV& bv_src);
211 };
212 
213 
214 // ------------------------------------------------------------------------
215 //
216 // ------------------------------------------------------------------------
217 
218 
219 template<class BV>
220 void rank_compressor<BV>::compress(BV& bv_target,
221  const BV& bv_idx,
222  const BV& bv_src)
223 {
224  bv_target.clear();
225  bv_target.init();
226 
227  if (&bv_idx == &bv_src)
228  {
229  bv_target = bv_src;
230  return;
231  }
232  size_type ibuffer[n_buffer_cap];
233  size_type b_size;
234 
235  typedef typename BV::enumerator enumerator_t;
236  enumerator_t en_s = bv_src.first();
237  enumerator_t en_i = bv_idx.first();
238 
239  size_type r_idx = b_size = 0;
240  size_type i, s;
241 
242  for (; en_i.valid(); )
243  {
244  if (!en_s.valid())
245  break;
246  i = *en_i; s = *en_s;
247 
248  BM_ASSERT(s >= i);
249  BM_ASSERT(bv_idx.test(i));
250 
251  if (i == s)
252  {
253  ibuffer[b_size++] = r_idx++;
254  if (b_size == n_buffer_cap)
255  {
256  bm::combine_or(bv_target, ibuffer+0, ibuffer+b_size);
257  b_size ^= b_size; // = 0
258  }
259  ++en_i; ++en_s;
260  continue;
261  }
262  BM_ASSERT(s > i);
263 
264  size_type dist = s - i;
265  if (dist >= 64) // sufficiently far away, jump
266  {
267  size_type r_dist = bv_idx.count_range(i + 1, s);
268  r_idx += r_dist;
269  en_i.go_to(s);
270  BM_ASSERT(en_i.valid());
271  }
272  else // small distance, iterate to close the gap
273  {
274  for (; s > i; ++r_idx)
275  {
276  ++en_i;
277  i = *en_i;
278  } // for
279  BM_ASSERT(en_i.valid());
280  }
281  } // for
282 
283  if (b_size)
284  {
285  bm::combine_or(bv_target, ibuffer+0, ibuffer+b_size);
286  }
287 
288 }
289 
290 // ------------------------------------------------------------------------
291 
292 
293 template<class BV>
295  const BV& bv_idx,
296  const BV& bv_src)
297 {
298  bv_target.clear();
299  bv_target.init();
300 
301  if (&bv_idx == &bv_src)
302  {
303  bv_target = bv_src;
304  return;
305  }
306 
307  size_type r_idx, i, s, b_size;
308  size_type ibuffer[n_buffer_cap];
309 
310  b_size = r_idx = 0;
311 
312  typedef typename BV::enumerator enumerator_t;
313  enumerator_t en_s = bv_src.first();
314  enumerator_t en_i = bv_idx.first();
315  for (; en_i.valid(); )
316  {
317  if (!en_s.valid())
318  break;
319  s = *en_s;
320  i = *en_i;
321  if (s == r_idx)
322  {
323  ibuffer[b_size++] = i;
324  if (b_size == n_buffer_cap)
325  {
326  bm::combine_or(bv_target, ibuffer+0, ibuffer+b_size);
327  b_size ^= b_size; // = 0
328  }
329  ++en_i; ++en_s; ++r_idx;
330  continue;
331  }
332  // source is "faster" than index, need to re-align
333  BM_ASSERT(s > r_idx);
334  size_type rank = s - r_idx + 1u;
335  size_type new_pos = 0;
336 
337  if (rank < 256)
338  {
339  en_i.skip(s - r_idx);
340  BM_ASSERT(en_i.valid());
341  new_pos = *en_i;
342  }
343  else
344  {
345  bv_idx.find_rank(rank, i, new_pos);
346  BM_ASSERT(new_pos);
347  en_i.go_to(new_pos);
348  BM_ASSERT(en_i.valid());
349  }
350 
351  r_idx = s;
352  ibuffer[b_size++] = new_pos;
353  if (b_size == n_buffer_cap)
354  {
355  bm::combine_or(bv_target, ibuffer+0, ibuffer+b_size);
356  b_size ^= b_size; // = 0
357  }
358  ++en_i; ++en_s; ++r_idx;
359 
360  } // for en
361 
362  if (b_size)
363  {
364  bm::combine_or(bv_target, ibuffer+0, ibuffer+b_size);
365  }
366 }
367 
368 // ------------------------------------------------------------------------
369 
370 template<class BV>
372  const BV& bv_idx,
373  const rs_index_type& bc_idx,
374  const BV& bv_src)
375 {
376  /// Rank compressor visitor (functor)
377  /// @internal
378  struct visitor_func
379  {
380  visitor_func(bvector_type& bv_out,
381  const bvector_type& bv_index,
382  const rs_index_type& bc_index)
383  : bv_target_(bv_out),
384  bv_index_(bv_index),
385  bc_index_(bc_index)
386  {}
387 
388  void add_bits(size_type arr_offset, const unsigned char* bits, unsigned bits_size)
389  {
390  for (unsigned i = 0; i < bits_size; ++i)
391  {
392  size_type idx = arr_offset + bits[i];
393  BM_ASSERT(bv_index_.test(idx));
394 
395  size_type r_idx = bv_index_.count_to(idx, bc_index_) - 1;
396  bv_target_.set_bit_no_check(r_idx);
397  }
398  }
399  void add_range(size_type arr_offset, size_type sz)
400  {
401  for (size_type i = 0; i < sz; ++i)
402  {
403  size_type idx = i + arr_offset;
404  BM_ASSERT(bv_index_.test(idx));
405 
406  size_type r_idx = bv_index_.count_to(idx, bc_index_) - 1;
407  bv_target_.set_bit_no_check(r_idx);
408  }
409  }
410 
411  bvector_type& bv_target_;
412  const bvector_type& bv_index_;
413  const rs_index_type& bc_index_;
414  };
415  // ------------------------------------
416 
417  bv_target.clear();
418  bv_target.init();
419 
420  if (&bv_idx == &bv_src)
421  {
422  bv_target = bv_src;
423  return;
424  }
425  visitor_func func(bv_target, bv_idx, bc_idx);
426  bm::for_each_bit(bv_src, func);
427 }
428 
429 
430 
431 } // bm
432 
433 #include "bmundef.h"
434 
435 #endif
BV::rs_index_type rs_index_type
Definition: bmalgo.h:180
const unsigned set_sub_array_size
Definition: bmconst.h:91
#define FULL_SUB_BLOCK_REAL_ADDR
Definition: bmdef.h:137
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:371
Definition: bm.h:76
Algorithms for rank compression of bit-vector.
Definition: bmalgo.h:175
pre-processor un-defines to avoid global space pollution (internal)
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
void combine_or(BV &bv, It first, It last)
OR Combine bitvector and the iterable sequence.
Definition: bmalgo_impl.h:1148
BMFORCEINLINE bool sse42_test_all_zero_wave(const void *ptr)
check if wave of pointers is all NULL
Definition: bmsse4.h:584
#define BM_SCANNER_OP(x)
Definition: bmalgo.h:41
unsigned int word_t
Definition: bmconst.h:38
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:65
Algorithms for bvector<>
void decompress(BV &bv_target, const BV &bv_idx, const BV &bv_src)
Rank decompression.
Definition: bmalgo.h:294
BV::size_type size_type
Definition: bmalgo.h:179
Bit manipulation primitives (internal)
Definitions(internal)
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:220
#define BM_ASSERT
Definition: bmdef.h:117
#define FULL_BLOCK_FAKE_ADDR
Definition: bmdef.h:136
void visit_each_bit(const BV &bv, void *handle_ptr, bit_visitor_callback_type callback_ptr)
bit-vector visitor scanner to traverse each 1 bit using C callback
Definition: bmalgo.h:131