NCBI C++ ToolKit
bmvmin.h
Go to the documentation of this file.

Go to the SVN repository for 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 /*! @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 */
52 template <class A, size_t N> class miniset
53 {
54 public:
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 ?
96  :
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 
154 private:
155 
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 
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 
201 private:
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 */
213 template<size_t N> class bvmini
214 {
215 public:
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 
257 private:
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 */
271 template<class A> class bvector_mini
272 {
273 public:
274 #ifdef BM64ADDR
275  typedef bm::id64_t size_type;
276 #else
278 #endif
279 
280 public:
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
311  void set_bit(size_type pos)
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 
462  void swap(bvector_mini& bvm)
463  {
464  bm::word_t* buftmp = m_buf;
465  m_buf = bvm.m_buf;
466  bvm.m_buf = buftmp;
467  }
468 
469 private:
472 };
473 
474 
475 
476 } // namespace bm
477 
478 #ifdef _MSC_VER
479 #pragma warning( pop )
480 #endif
481 
482 #endif
ncbi::TMaskedQueryRegions mask
#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
size_type m_size
Definition: bmvmin.h:471
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
bm::word_t * m_buf
Definition: bmvmin.h:470
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 noexcept
Finds the number of the next bit ON.
Definition: bm.h:1609
size_type get_first() const noexcept
find first 1 bit in vector. Function may return 0 and this requires an extra check if bit 0 is actual...
Definition: bm.h:1600
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
bm::word_t m_buf[((N/32)+((N % 32) &&1))]
Definition: bmvmin.h:258
void swap(bvmini &mset)
Definition: bmvmin.h:247
Template class implements memory saving set functionality.
Definition: bmvmin.h:53
void convert_buf()
Definition: bmvmin.h:188
miniset()
Definition: bmvmin.h:56
void init_bitbuf(bm::word_t *buf)
Definition: bmvmin.h:156
void set(bm::id_t n, bool val=true)
Definition: bmvmin.h:100
unsigned mem_used() const
Definition: bmvmin.h:134
void init_gapbuf(bm::word_t *buf)
Definition: bmvmin.h:171
bm::word_t * m_buf
Buffer pointer.
Definition: bmvmin.h:202
miniset(const miniset &mset)
Definition: bmvmin.h:61
~miniset()
Definition: bmvmin.h:77
unsigned m_type
buffer type (0-bit, 1-gap)
Definition: bmvmin.h:203
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
static char tmp[3200]
Definition: utf8.c:42
unsigned gap_test(const T *buf, unsigned pos) noexcept
Tests if bit = pos is true.
Definition: bmfunc.h:1790
void gap_convert_to_bitset(unsigned *dest, const T *buf, unsigned len=0) noexcept
GAP block to bitblock conversion.
Definition: bmfunc.h:4475
unsigned gap_set_value(unsigned val, T *buf, unsigned pos, unsigned *is_set) noexcept
Sets or clears bit in the GAP buffer.
Definition: bmfunc.h:3254
void gap_set_all(T *buf, unsigned set_max, unsigned value) noexcept
Sets all bits to 0 or 1 (GAP)
Definition: bmfunc.h:4552
char * buf
int i
yy_size_t n
#include<zmmintrin.h>
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
const struct ncbi::grid::netcache::search::fields::SIZE size
const GenericPointer< typename T::ValueType > T2 value
Definition: pointer.h:1227
#define N
Definition: crc32.c:57
Modified on Sun Apr 14 05:28:05 2024 by modify_doxy.py rev. 669887