BitMagic-C++
bmvmin.h
Go to the documentation of this file.
1#ifndef BMVMIN__H__INCLUDED__
2#define BMVMIN__H__INCLUDED__
3/*
4Copyright(c) 2002-2017 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
5
6Licensed under the Apache License, Version 2.0 (the "License");
7you may not use this file except in compliance with the License.
8You may obtain a copy of the License at
9
10 http://www.apache.org/licenses/LICENSE-2.0
11
12Unless required by applicable law or agreed to in writing, software
13distributed under the License is distributed on an "AS IS" BASIS,
14WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15See the License for the specific language governing permissions and
16limitations under the License.
17
18For 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
31namespace 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*/
46template<typename T>
47void 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*/
67template <class A, size_t N> class miniset
68{
69public:
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 :
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
169private:
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
216private:
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*/
228template<size_t N> class bvmini
229{
230public:
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
272private:
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*/
286template<class A> class bvector_mini
287{
288public:
289#ifdef BM64ADDR
290 typedef bm::id64_t size_type;
291#else
293#endif
294
295public:
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
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
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
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
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
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
478 {
479 bm::word_t* buftmp = m_buf;
480 m_buf = bvm.m_buf;
481 bvm.m_buf = buftmp;
482 }
483
484private:
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
#define BM_MINISET_ARRSIZE(x)
Definition bmvmin.h:36
#define BM_MINISET_GAPLEN
Definition bmvmin.h:35
Bitvector class with very limited functionality.
Definition bmvmin.h:287
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
unsigned mem_used() const
Definition bmvmin.h:472
size_type get_first() const
Returns index of the first ON bit.
Definition bmvmin.h:386
size_type get_next(size_type idx) const
Returns index of next bit, which is ON.
Definition bmvmin.h:409
void combine_sub(const bvector_mini &bvect)
Definition bmvmin.h:461
void swap(bvector_mini &bvm)
Definition bmvmin.h:477
const unsigned * get_buf() const
Definition bmvmin.h:471
size_type bit_count() const
Counts number of bits ON.
Definition bmvmin.h:342
bvector_mini(size_type size)
Definition bmvmin.h:296
void combine_and(const bvector_mini &bvect)
Definition bmvmin.h:431
bm::id_t size_type
Definition bmvmin.h:292
void combine_or(const bvector_mini &bvect)
Definition bmvmin.h:451
void combine_xor(const bvector_mini &bvect)
Definition bmvmin.h:441
int compare(const bvector_mini &bvect)
Comparison.
Definition bmvmin.h:355
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 set_bit(size_type pos)
Sets bit number pos to 1.
Definition bmvmin.h:326
Bitvector Bit-vector container with runtime compression of bits.
Definition bm.h:108
size_type get_next(size_type prev) const BMNOEXCEPT
Finds the number of the next bit ON.
Definition bm.h:1540
size_type get_first() const BMNOEXCEPT
find first 1 bit in vector. Function may return 0 and this requires an extra check if bit 0 is actual...
Definition bm.h:1531
Mini bit-vector for auxiliary purposes.
Definition bmvmin.h:229
unsigned mem_used() const
Definition bmvmin.h:257
void set(bm::id_t n, bool val=true)
Definition bmvmin.h:249
bvmini(int=0)
Definition bmvmin.h:232
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
bvmini(const bvmini &mset)
Definition bmvmin.h:237
void swap(bvmini &mset)
Definition bmvmin.h:262
Template class implements memory saving set functionality.
Definition bmvmin.h:68
void set(bm::id_t n, bool val=true)
Definition bmvmin.h:115
unsigned mem_used() const
Definition bmvmin.h:149
miniset(const miniset &mset)
Definition bmvmin.h:76
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
void swap(miniset &mset)
Definition bmvmin.h:158
unsigned gap_set_value(unsigned val, T *BMRESTRICT buf, unsigned pos, unsigned *BMRESTRICT is_set) BMNOEXCEPT
Sets or clears bit in the GAP buffer.
Definition bmfunc.h:2661
unsigned gap_test(const T *BMRESTRICT buf, unsigned pos) BMNOEXCEPT
Tests if bit = pos is true.
Definition bmfunc.h:1255
void gap_add_to_bitset(unsigned *BMRESTRICT dest, const T *BMRESTRICT pcurr, unsigned len) BMNOEXCEPT
Adds(OR) GAP block to bitblock.
Definition bmfunc.h:3436
void gap_convert_to_bitset(unsigned *BMRESTRICT dest, const T *BMRESTRICT buf) BMNOEXCEPT
GAP block to bitblock conversion.
Definition bmfunc.h:3859
void gap_set_all(T *buf, unsigned set_max, unsigned value) BMNOEXCEPT
Sets all bits to 0 or 1 (GAP)
Definition bmfunc.h:3933
Definition bm.h:77
unsigned int word_t
Definition bmconst.h:38
const unsigned set_word_shift
Definition bmconst.h:71
unsigned long long int id64_t
Definition bmconst.h:34
unsigned int id_t
Definition bmconst.h:37
unsigned short gap_word_t
Definition bmconst.h:77
const unsigned gap_max_bits
Definition bmconst.h:80
const unsigned set_word_mask
Definition bmconst.h:72