BitMagic-C++
bmvmin.h
Go to the documentation of this file.
1 #ifndef BMVMIN__H__INCLUDED__
2 #define BMVMIN__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 bmvmin.h
22  \brief Mini bitset for testing and utility purposes (internal)
23 */
24 
25 
26 #ifdef _MSC_VER
27 #pragma warning( push )
28 #pragma warning( disable : 4100)
29 #endif
30 
31 namespace bm
32 {
33 
34 
35 #define BM_MINISET_GAPLEN (bm::gap_len_table<true>::_len[0])
36 #define BM_MINISET_ARRSIZE(x) ((x / 32) + ( (x % 32) && 1 ))
37 
38 /*!
39  \brief GAP block to bitblock conversion.
40  \param dest - bitblock buffer pointer.
41  \param buf - GAP buffer pointer.
42  \param dest_len - length/size of the destination buffer.
43 
44  @internal
45 */
46 template<typename T>
47 void gap_convert_to_bitset(unsigned* dest, const T* buf, unsigned dest_len)
48 {
49  ::memset(dest, 0, dest_len * sizeof(unsigned));
50  bm::gap_add_to_bitset(dest, buf);
51 }
52 
53 
54 /*! @defgroup mset Small sets functionality (intrenal)
55  * @internal
56  * @ingroup bmagic
57  * @{
58  */
59 
60 
61 /*!
62  @brief Template class implements memory saving set functionality
63  @ingroup mset
64  @sa bvmini
65  @internal
66 */
67 template <class A, size_t N> class miniset
68 {
69 public:
70 
72  : m_buf(0),
73  m_type(1)
74  {}
75 
76  miniset(const miniset& mset)
77  {
78  if (mset.m_buf)
79  {
80  if (mset.m_type)
81  init_gapbuf(mset.m_buf);
82  else
83  init_bitbuf(mset.m_buf);
84  }
85  else
86  {
87  m_type = mset.m_type;
88  m_buf = 0;
89  }
90  }
91 
93  {
94  if (m_buf)
95  {
96  A::deallocate(m_buf, m_type ?
97  (BM_MINISET_GAPLEN / (sizeof(bm::word_t) / sizeof(bm::gap_word_t)))
98  :
99  (BM_MINISET_ARRSIZE(N)));
100  }
101  }
102 
103  /// Checks if bit pos 1 or 0. Returns 0 if 0 and non zero otherwise.
104  unsigned test(bm::id_t n) const
105  {
106  return
107  !m_buf ? 0
108  :
109  m_type ?
110  gap_test((gap_word_t*)m_buf, n)
111  :
112  m_buf[n>>bm::set_word_shift] & (1<<(n & bm::set_word_mask));
113  }
114 
115  void set(bm::id_t n, bool val=true)
116  {
117  if (m_type == 0)
118  {
119  if (!m_buf)
120  {
121  if (!val) return;
122  init_bitbuf(0);
123  }
124 
125  unsigned nword = n >> bm::set_word_shift;
126  unsigned mask = unsigned(1) << (n & bm::set_word_mask);
127 
128  val ? (m_buf[nword] |= mask) : (m_buf[nword] &= ~mask);
129  }
130  else
131  {
132  if (!m_buf)
133  {
134  if (!val) return;
135  init_gapbuf(0);
136  }
137 
138  unsigned is_set;
139  unsigned new_block_len =
140  gap_set_value(val, (gap_word_t*)m_buf, n, &is_set);
141 
142  if (new_block_len > unsigned(BM_MINISET_GAPLEN-4))
143  {
144  convert_buf();
145  }
146  }
147  }
148 
149  unsigned mem_used() const
150  {
151  return sizeof(*this) +
152  (m_buf ?
153  (m_type ? (BM_MINISET_GAPLEN * sizeof(gap_word_t))
154  : (BM_MINISET_ARRSIZE(N) * sizeof(bm::word_t)))
155  : 0);
156  }
157 
158  void swap(miniset& mset)
159  {
160  bm::word_t* buftmp = m_buf;
161  m_buf = mset.m_buf;
162  mset.m_buf = buftmp;
163  unsigned typetmp = m_type;
164  m_type = mset.m_type;
165  mset.m_type = typetmp;
166  }
167 
168 
169 private:
170 
171  void init_bitbuf(bm::word_t* buf)
172  {
173  unsigned arr_size = BM_MINISET_ARRSIZE(N);
174  m_buf = A::allocate(arr_size, 0);
175  if (buf)
176  {
177  ::memcpy(m_buf, buf, arr_size * sizeof(bm::word_t));
178  }
179  else
180  {
181  ::memset(m_buf, 0, arr_size * sizeof(bm::word_t));
182  }
183  m_type = 0;
184  }
185 
186  void init_gapbuf(bm::word_t* buf)
187  {
188  unsigned arr_size =
189  unsigned(BM_MINISET_GAPLEN / (sizeof(bm::word_t) / sizeof(bm::gap_word_t)));
190  m_buf = A::allocate(arr_size, 0);
191  if (buf)
192  {
193  ::memcpy(m_buf, buf, arr_size * sizeof(bm::word_t));
194  }
195  else
196  {
197  *m_buf = 0;
199  }
200  m_type = 1;
201  }
202 
203  void convert_buf()
204  {
205  unsigned arr_size = BM_MINISET_ARRSIZE(N);
206  bm::word_t* buf = A::allocate(arr_size, 0);
207 
208  gap_convert_to_bitset(buf, (gap_word_t*) m_buf, arr_size);
209  arr_size =
210  unsigned(BM_MINISET_GAPLEN / (sizeof(bm::word_t) / sizeof(bm::gap_word_t)));
211  A::deallocate(m_buf, arr_size);
212  m_buf = buf;
213  m_type = 0;
214  }
215 
216 private:
217  bm::word_t* m_buf; //!< Buffer pointer
218  unsigned m_type; //!< buffer type (0-bit, 1-gap)
219 };
220 
221 
222 /*!
223  @brief Mini bit-vector for auxiliary purposes
224  @ingroup mset
225  @sa miniset
226  @internal
227 */
228 template<size_t N> class bvmini
229 {
230 public:
231 
232  bvmini(int = 0)
233  {
234  ::memset(m_buf, 0, sizeof(m_buf));
235  }
236 
237  bvmini(const bvmini& mset)
238  {
239  ::memcpy(m_buf, mset.m_buf, sizeof(m_buf));
240  }
241 
242 
243  /// Checks if bit pos 1 or 0. Returns 0 if 0 and non zero otherwise.
244  unsigned test(bm::id_t n) const
245  {
246  return m_buf[n>>bm::set_word_shift] & (1<<(n & bm::set_word_mask));
247  }
248 
249  void set(bm::id_t n, bool val=true)
250  {
251  unsigned nword = n >> bm::set_word_shift;
252  unsigned mask = unsigned(1) << (n & bm::set_word_mask);
253 
254  val ? (m_buf[nword] |= mask) : (m_buf[nword] &= ~mask);
255  }
256 
257  unsigned mem_used() const
258  {
259  return sizeof(*this);
260  }
261 
262  void swap(bvmini& mset)
263  {
264  for (unsigned i = 0; i < BM_MINISET_ARRSIZE(N); ++i)
265  {
266  bm::word_t tmp = m_buf[i];
267  m_buf[i] = mset.m_buf[i];
268  mset.m_buf[i] = tmp;
269  }
270  }
271 
272 private:
273  bm::word_t m_buf[BM_MINISET_ARRSIZE(N)];
274 };
275 
276 
277 /*!@} */
278 
279 /*!
280  @brief Bitvector class with very limited functionality.
281 
282  Class implements simple bitset and used for internal
283  and testing purposes.
284  @internal
285 */
286 template<class A> class bvector_mini
287 {
288 public:
289 #ifdef BM64ADDR
290  typedef bm::id64_t size_type;
291 #else
293 #endif
294 
295 public:
296  bvector_mini(size_type size)
297  : m_buf(0),
298  m_size(size)
299  {
300  size_type arr_size = (size / 32) + 1;
301  m_buf = A::allocate(arr_size, 0);
302  ::memset(m_buf, 0, arr_size * sizeof(unsigned));
303  }
305  : m_size(bvect.m_size)
306  {
307  size_type arr_size = (m_size / 32) + 1;
308  m_buf = A::allocate(arr_size, 0);
309  ::memcpy(m_buf, bvect.m_buf, arr_size * sizeof(unsigned));
310  }
311 
313  {
314  A::deallocate(m_buf, (m_size / 32) + 1);
315  }
316 
317  /// Checks if bit pos 1 or 0. Returns 0 if 0 and non zero otherwise.
318  int is_bit_true(size_type pos) const
319  {
320  unsigned char mask = (unsigned char)((char)0x1 << (pos & 7));
321  unsigned char* offs = (unsigned char*)m_buf + (pos >> 3);
322  return (*offs) & mask;
323  }
324 
325  /// Sets bit number pos to 1
326  void set_bit(size_type pos)
327  {
328  unsigned char mask = (unsigned char)(0x1 << (pos & 7));
329  unsigned char* offs = (unsigned char*)m_buf + (pos >> 3);
330  *offs |= mask;
331  }
332 
333  /// Sets bit number pos to 0
334  void clear_bit(size_type pos)
335  {
336  unsigned char mask = (unsigned char)(0x1 << (pos & 7));
337  unsigned char* offs = (unsigned char*)m_buf + (pos >> 3);
338  *offs &= (unsigned char)~mask;
339  }
340 
341  /// Counts number of bits ON
342  size_type bit_count() const
343  {
344  size_type count = 0;
345  const unsigned* end = m_buf + (m_size / 32)+1;
346  for (unsigned* start = m_buf; start < end; ++start)
347  {
348  unsigned value = *start;
349  for (count += (value!=0); value &= value - 1; ++count);
350  }
351  return count;
352  }
353 
354  /// Comparison.
356  {
357  size_type cnt1 = bit_count();
358  size_type cnt2 = bvect.bit_count();
359  if (!cnt1 && !cnt2) return 0;
360  size_type cnt_min = cnt1 < cnt2 ? cnt1 : cnt2;
361  if (!cnt_min) return cnt1 ? 1 : -1;
362 
363  size_type idx1 = get_first();
364  size_type idx2 = bvect.get_first();
365 
366  for (size_type i = 0; i < cnt_min; ++i)
367  {
368  if (idx1 != idx2)
369  {
370  return idx1 < idx2 ? 1 : -1;
371  }
372  idx1 = get_next(idx1);
373  idx2 = bvect.get_next(idx2);
374  }
375  if (idx1 != idx2)
376  {
377  if (!idx1) return -1;
378  if (!idx2) return 1;
379  return idx1 < idx2 ? 1 : -1;
380  }
381  return 0;
382  }
383 
384 
385  /// Returns index of the first ON bit
386  size_type get_first() const
387  {
388  size_type pos = 0;
389  const unsigned char* ptr = (unsigned char*) m_buf;
390  for (unsigned i = 0; i < ((m_size/8)+1); ++i)
391  {
392  unsigned char w = ptr[i];
393  if (w != 0)
394  {
395  while ((w & 1u) == 0)
396  {
397  w = (unsigned char)(w >> 1u);
398  ++pos;
399  }
400  return pos;
401  }
402  pos = size_type(pos + sizeof(unsigned char) * 8u);
403  }
404  return 0;
405  }
406 
407 
408  /// Returns index of next bit, which is ON
409  size_type get_next(size_type idx) const
410  {
411  size_type i;
412  for (i = idx+1; i < m_size; ++i)
413  {
414  unsigned char* offs = (unsigned char*)m_buf + (i >> 3);
415  if (*offs)
416  {
417  unsigned char mask = (unsigned char)((char)0x1 << (i & 7));
418  if (*offs & mask)
419  {
420  return i;
421  }
422  }
423  else
424  {
425  i += 7;
426  }
427  }
428  return 0;
429  }
430 
432  {
433  const unsigned* end = m_buf + (m_size / 32)+1;
434  const unsigned* src = bvect.get_buf();
435  for (unsigned* start = m_buf; start < end; ++start)
436  {
437  *start &= *src++;
438  }
439  }
440 
442  {
443  const unsigned* end = m_buf + (m_size / 32)+1;
444  const unsigned* src = bvect.get_buf();
445  for (unsigned* start = m_buf; start < end; ++start)
446  {
447  *start ^= *src++;
448  }
449  }
450 
452  {
453  const unsigned* end = m_buf + (m_size / 32)+1;
454  const unsigned* src = bvect.get_buf();
455  for (unsigned* start = m_buf; start < end; ++start)
456  {
457  *start |= *src++;
458  }
459  }
460 
462  {
463  const unsigned* end = m_buf + (m_size / 32)+1;
464  const unsigned* src = bvect.get_buf();
465  for (unsigned* start = m_buf; start < end; ++start)
466  {
467  *start &= ~(*src++);
468  }
469  }
470 
471  const unsigned* get_buf() const { return m_buf; }
472  unsigned mem_used() const
473  {
474  return unsigned(sizeof(bvector_mini) + (m_size / 32) + 1);
475  }
476 
477  void swap(bvector_mini& bvm)
478  {
479  bm::word_t* buftmp = m_buf;
480  m_buf = bvm.m_buf;
481  bvm.m_buf = buftmp;
482  }
483 
484 private:
485  bm::word_t* m_buf;
486  size_type m_size;
487 };
488 
489 
490 
491 } // namespace bm
492 
493 #ifdef _MSC_VER
494 #pragma warning( pop )
495 #endif
496 
497 #endif
Bitvector Bit-vector container with runtime compression of bits.
Definition: bm.h:107
bvector_mini(const bvector_mini &bvect)
Definition: bmvmin.h:304
void clear_bit(size_type pos)
Sets bit number pos to 0.
Definition: bmvmin.h:334
void gap_add_to_bitset(unsigned *dest, const T *pcurr, unsigned len)
Adds(OR) GAP block to bitblock.
Definition: bmfunc.h:3098
const unsigned set_word_shift
Definition: bmconst.h:70
const unsigned * get_buf() const
Definition: bmvmin.h:471
bm::id_t size_type
Definition: bmvmin.h:292
void combine_sub(const bvector_mini &bvect)
Definition: bmvmin.h:461
unsigned gap_set_value(unsigned val, T *BMRESTRICT buf, unsigned pos, unsigned *BMRESTRICT is_set)
Sets or clears bit in the GAP buffer.
Definition: bmfunc.h:2391
void gap_set_all(T *buf, unsigned set_max, unsigned value)
Sets all bits to 0 or 1 (GAP)
Definition: bmfunc.h:3583
bvmini(int=0)
Definition: bmvmin.h:232
unsigned long long int id64_t
Definition: bmconst.h:34
Definition: bm.h:76
miniset()
Definition: bmvmin.h:71
unsigned mem_used() const
Definition: bmvmin.h:257
void gap_convert_to_bitset(unsigned *dest, const T *buf)
GAP block to bitblock conversion.
Definition: bmfunc.h:3510
size_type get_first() const
Returns index of the first ON bit.
Definition: bmvmin.h:386
void combine_or(const bvector_mini &bvect)
Definition: bmvmin.h:451
int compare(const bvector_mini &bvect)
Comparison.
Definition: bmvmin.h:355
unsigned gap_test(const T *buf, unsigned pos)
Tests if bit = pos is true.
Definition: bmfunc.h:1213
unsigned int word_t
Definition: bmconst.h:38
int is_bit_true(size_type pos) const
Checks if bit pos 1 or 0. Returns 0 if 0 and non zero otherwise.
Definition: bmvmin.h:318
void set_bit(size_type pos)
Sets bit number pos to 1.
Definition: bmvmin.h:326
void combine_and(const bvector_mini &bvect)
Definition: bmvmin.h:431
void swap(bvmini &mset)
Definition: bmvmin.h:262
size_type bit_count() const
Counts number of bits ON.
Definition: bmvmin.h:342
miniset(const miniset &mset)
Definition: bmvmin.h:76
unsigned short gap_word_t
Definition: bmconst.h:76
~miniset()
Definition: bmvmin.h:92
bvmini(const bvmini &mset)
Definition: bmvmin.h:237
void swap(miniset &mset)
Definition: bmvmin.h:158
Template class implements memory saving set functionality.
Definition: bmvmin.h:67
unsigned mem_used() const
Definition: bmvmin.h:149
const unsigned gap_max_bits
Definition: bmconst.h:79
unsigned test(bm::id_t n) const
Checks if bit pos 1 or 0. Returns 0 if 0 and non zero otherwise.
Definition: bmvmin.h:244
#define BM_MINISET_GAPLEN
Definition: bmvmin.h:35
void combine_xor(const bvector_mini &bvect)
Definition: bmvmin.h:441
size_type get_next(size_type idx) const
Returns index of next bit, which is ON.
Definition: bmvmin.h:409
const unsigned set_word_mask
Definition: bmconst.h:71
unsigned mem_used() const
Definition: bmvmin.h:472
unsigned int id_t
Definition: bmconst.h:37
unsigned test(bm::id_t n) const
Checks if bit pos 1 or 0. Returns 0 if 0 and non zero otherwise.
Definition: bmvmin.h:104
#define BM_MINISET_ARRSIZE(x)
Definition: bmvmin.h:36
bvector_mini(size_type size)
Definition: bmvmin.h:296
Mini bit-vector for auxiliary purposes.
Definition: bmvmin.h:228
void swap(bvector_mini &bvm)
Definition: bmvmin.h:477
Bitvector class with very limited functionality.
Definition: bmvmin.h:286