BitMagicC++Library
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 #include "bm.h"
22 #include "bmfunc.h"
23 #include "bmdef.h"
24 
25 #include "bmalgo_impl.h"
26 
27 
28 
29 namespace bm
30 {
31 
32 /**
33  @brief bit-vector visitor scanner to traverse each 1 bit using C++ visitor
34 
35  @param bv - bit vector to scan
36  @param bit_functor (should support add_bits() and add_range() methods
37 
38  \ingroup setalgo
39 */
40 template<class BV, class Func>
41 void for_each_bit(const BV& bv,
42  Func& bit_functor)
43 {
44  const typename BV::blocks_manager_type& bman = bv.get_blocks_manager();
45  bm::word_t*** blk_root = bman.top_blocks_root();
46 
47  unsigned tsize = bman.top_block_size();
48  for (unsigned i = 0; i < tsize; ++i)
49  {
50  bm::word_t** blk_blk = blk_root[i];
51  if (!blk_blk)
52  {
53  continue;
54  }
55  unsigned r = i * bm::set_array_size;
56  for (unsigned j = 0; j < bm::set_array_size; ++j)
57  {
58  const bm::word_t* block = blk_blk[j];
59  if (block)
60  {
61  unsigned nb = r + j;
62  if (BM_IS_GAP(block))
63  {
65  nb * bm::bits_in_block,
66  bit_functor);
67  }
68  else
69  {
70  // TODO: optimize FULL BLOCK ADDRESS scan
71  block = BLOCK_ADDR_SAN(block);
72 
74  bit_functor);
75  }
76  }
77  } // for j
78  } // for i
79 
80 }
81 
82 
83 /**
84  @brief bit-vector visitor scanner to traverse each 1 bit using C callback
85 
86  @param bv - bit vector to scan
87  @param handle_ptr - handle to private memory used by callback
88  @param callback_ptr - callback function
89 
90  \ingroup setalgo
91 
92  @sa bit_visitor_callback_type
93 */
94 template<class BV>
95 void visit_each_bit(const BV& bv,
96  void* handle_ptr,
97  bit_visitor_callback_type callback_ptr)
98 {
99  // private adaptor for C-style callbacks
100  struct callback_adaptor
101  {
102  callback_adaptor(void* h, bit_visitor_callback_type cb_func)
103  : handle_(h), func_(cb_func)
104  {}
105 
106  void add_bits(bm::id_t offset, const unsigned char* bits, unsigned size)
107  {
108  for (unsigned i = 0; i < size; ++i)
109  func_(handle_, offset + bits[i]);
110  }
111  void add_range(bm::id_t offset, unsigned size)
112  {
113  for (unsigned i = 0; i < size; ++i)
114  func_(handle_, offset + i);
115  }
116 
117  void* handle_;
119  };
120 
121  callback_adaptor func(handle_ptr, callback_ptr);
122  bm::for_each_bit(bv, func);
123 }
124 
125 
126 
127 } // bm
128 
129 #include "bmundef.h"
130 
131 #endif
Definition: bm.h:59
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:55
void for_each_gap_blk(const T *buf, bm::id_t offset, Func &bit_functor)
for-each visitor, calls a special visitor functor for each 1 bit range
Definition: bmalgo_impl.h:1696
unsigned int word_t
Definition: bmconst.h:35
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:41
const unsigned bits_in_block
Definition: bmconst.h:77
#define BM_IS_GAP(ptr)
Definition: bmdef.h:161
#define BMGAP_PTR(ptr)
Definition: bmdef.h:159
const unsigned set_array_size
Definition: bmconst.h:72
unsigned int id_t
Definition: bmconst.h:34
void for_each_bit_blk(const bm::word_t *block, bm::id_t offset, Func &bit_functor)
for-each visitor, calls a special visitor functor for each 1 bit group
Definition: bmalgo_impl.h:1664
#define BLOCK_ADDR_SAN(addr)
Definition: bmdef.h:133
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:95