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