Turi Create  4.0
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
dense_bitset.hpp
1 /* Copyright © 2017 Apple Inc. All rights reserved.
2  *
3  * Use of this source code is governed by a BSD-3-clause license that can
4  * be found in the LICENSE.txt file or at https://opensource.org/licenses/BSD-3-Clause
5  */
6 #ifndef TURI_DENSE_BITSET_HPP
7 #define TURI_DENSE_BITSET_HPP
8 
9 #include <cstdio>
10 #include <cstdlib>
11 #include <cstring>
12 #include <stdint.h>
13 #include <core/logging/logger.hpp>
14 #include <core/storage/serialization/serialization_includes.hpp>
15 #include <core/parallel/atomic_ops.hpp>
16 #include <core/util/bitops.hpp>
17 
18 namespace turi {
19 
20  /** \ingroup util
21  * Implements an atomic dense bitset
22  */
23  class dense_bitset {
24  public:
25 
26  /// Constructs a bitset of 0 length
27  dense_bitset() : array(NULL), len(0), arrlen(0) {
28  }
29 
30  /// Constructs a bitset with 'size' bits. All bits will be cleared.
31  explicit dense_bitset(size_t size) : array(NULL), len(0), arrlen(0) {
32  resize(size);
33  }
34 
35  /// Make a copy of the bitset db
37  array = NULL;
38  len = 0;
39  arrlen = 0;
40  *this = db;
41  }
42 
43  /// destructor
44  ~dense_bitset() {free(array);}
45 
46  /// Make a copy of the bitset db
47  inline dense_bitset& operator=(const dense_bitset& db) {
48  resize(db.size());
49  len = db.len;
50  arrlen = db.arrlen;
51  memcpy(array, db.array, sizeof(size_t) * arrlen);
52  return *this;
53  }
54 
55  /** Resizes the current bitset to hold n bits.
56  Existing bits will not be changed. If the array size is increased,
57  the value of the new bits are undefined.
58 
59  \Warning When shirnking, the current implementation may still leave the
60  "deleted" bits in place which will mess up the popcount.
61  */
62  inline void resize(size_t n) {
63  len = n;
64  //need len bits
65  size_t prev_arrlen = arrlen;
66  arrlen = (n / (sizeof(size_t) * 8)) + (n % (sizeof(size_t) * 8) > 0);
67  array = (size_t*)realloc(array, sizeof(size_t) * arrlen);
68  // this zeros the remainder of the block after the last bit
69  fix_trailing_bits();
70  // if we grew, we need to zero all new blocks
71  if (arrlen > prev_arrlen) {
72  // Use this version; may special case to memset, which is
73  // faster than loop.
74  std::fill(&array[prev_arrlen], &array[arrlen], 0);
75  }
76  }
77 
78  /// Sets all bits to 0
79  inline void clear() {
80  std::fill(&array[0], &array[arrlen], 0);
81  }
82 
83  inline bool empty() const {
84  for (size_t i = 0; i < arrlen; ++i) if (array[i]) return false;
85  return true;
86  }
87 
88  /// Sets all bits to 1
89  inline void fill() {
90  for (size_t i = 0;i < arrlen; ++i) array[i] = (size_t) - 1;
91  fix_trailing_bits();
92  }
93 
94  /// Prefetches the word containing the bit b
95  inline void prefetch(size_t b) const{
96  __builtin_prefetch(&(array[b / (8 * sizeof(size_t))]));
97  }
98 
99  /// Returns the value of the bit b
100  inline bool get(size_t b) const{
101  size_t arrpos, bitpos;
102  bit_to_pos(b, arrpos, bitpos);
103  return array[arrpos] & (size_t(1) << size_t(bitpos));
104  }
105 
106  //! Atomically sets the bit at position b to true returning the old value
107  inline bool set_bit(size_t b) {
108  // use CAS to set the bit
109  size_t arrpos, bitpos;
110  bit_to_pos(b, arrpos, bitpos);
111  const size_t mask(size_t(1) << size_t(bitpos));
112  return __sync_fetch_and_or(array + arrpos, mask) & mask;
113  }
114 
115  //! Atomically xors a bit with 1
116  inline bool xor_bit(size_t b) {
117  // use CAS to set the bit
118  size_t arrpos, bitpos;
119  bit_to_pos(b, arrpos, bitpos);
120  const size_t mask(size_t(1) << size_t(bitpos));
121  return __sync_fetch_and_xor(array + arrpos, mask) & mask;
122  }
123 
124  //! Returns the value of the word containing the bit b
125  inline size_t containing_word(size_t b) {
126  size_t arrpos, bitpos;
127  bit_to_pos(b, arrpos, bitpos);
128  return array[arrpos];
129  }
130 
131  //! Returns the value of the word containing the bit b
132  inline size_t get_containing_word_and_zero(size_t b) {
133  size_t arrpos, bitpos;
134  bit_to_pos(b, arrpos, bitpos);
135  return fetch_and_store(array[arrpos], size_t(0));
136  }
137 
138  /**
139  * \brief Transfers approximately b bits from another bitset to this bitset
140  *
141  * "Moves" at least b bits from the other bitset to this bitset
142  * starting from the given position.
143  * At return, b will contain the actual number of bits moved,
144  * and start will point to the end of the transfered region.
145  *
146  * Semantically what this accomplishes is something like:
147  *
148  * \code
149  * idx = start;
150  * if other.get_bit(idx) == false {
151  * idx = next true bit after idx in other (with loop around)
152  * }
153  * for(transferred = 0; transferred < b; transferred++) {
154  * other.clear_bit(idx);
155  * this->set_bit(idx);
156  * idx = next true bit after idx in other.
157  * if no more bits, return
158  * }
159  * \endcode
160  * However, the implementation here may transfer more than b bits.
161  * ( up to b + 2 * wordsize_in_bits )
162  */
164  size_t& start,
165  size_t& b) {
166  // must be identical in length
167  ASSERT_EQ(other.len, len);
168  ASSERT_EQ(other.arrlen, arrlen);
169  size_t arrpos, bitpos;
170  bit_to_pos(start, arrpos, bitpos);
171  size_t initial_arrpos = arrpos;
172  if (arrpos >= arrlen) arrpos = 0;
173  // ok. we will only look at arrpos
174  size_t transferred = 0;
175  while(transferred < b) {
176  if (other.array[arrpos] > 0) {
177  transferred += num_bits_on(other.array[arrpos]);
178  array[arrpos] |= other.array[arrpos];
179  other.array[arrpos] = 0;
180  }
181  ++arrpos;
182  if (arrpos >= other.arrlen) arrpos = 0;
183  else if (arrpos == initial_arrpos) break;
184  }
185  start = 8 * sizeof(size_t) * arrpos;
186  b = transferred;
187  }
188 
189 
190  /** Set the bit at position b to true returning the old value.
191  Unlike set_bit(), this uses a non-atomic set which is faster,
192  but is unsafe if accessed by multiple threads.
193  */
194  inline bool set_bit_unsync(size_t b) {
195  // use CAS to set the bit
196  size_t arrpos, bitpos;
197  bit_to_pos(b, arrpos, bitpos);
198  const size_t mask(size_t(1) << size_t(bitpos));
199  bool ret = array[arrpos] & mask;
200  array[arrpos] |= mask;
201  return ret;
202  }
203 
204  //! Atomically sets the state of the bit to the new value returning the old value
205  inline bool set(size_t b, bool value) {
206  if (value) return set_bit(b);
207  else return clear_bit(b);
208  }
209 
210  /** Set the state of the bit returning the old value.
211  This version uses a non-atomic set which is faster, but
212  is unsafe if accessed by multiple threads.
213  */
214  inline bool set_unsync(size_t b, bool value) {
215  if (value) return set_bit_unsync(b);
216  else return clear_bit_unsync(b);
217  }
218 
219 
220  //! Atomically set the bit at b to false returning the old value
221  inline bool clear_bit(size_t b) {
222  // use CAS to set the bit
223  size_t arrpos, bitpos;
224  bit_to_pos(b, arrpos, bitpos);
225  const size_t test_mask(size_t(1) << size_t(bitpos));
226  const size_t clear_mask(~test_mask);
227  return __sync_fetch_and_and(array + arrpos, clear_mask) & test_mask;
228  }
229 
230  /** Clears the state of the bit returning the old value.
231  This version uses a non-atomic set which is faster, but
232  is unsafe if accessed by multiple threads.
233  */
234  inline bool clear_bit_unsync(size_t b) {
235  // use CAS to set the bit
236  size_t arrpos, bitpos;
237  bit_to_pos(b, arrpos, bitpos);
238  const size_t test_mask(size_t(1) << size_t(bitpos));
239  const size_t clear_mask(~test_mask);
240  bool ret = array[arrpos] & test_mask;
241  array[arrpos] &= clear_mask;
242  return ret;
243  }
244 
245  /** Clears the word containing the bit b. This version is useful
246  * for quickly clearing an entire array when only a few bits are
247  * on.
248  *
249  * This version uses a non-atomic set which is faster, but is
250  * unsafe if accessed by multiple threads.
251  */
252  inline void clear_word_unsync(size_t b) {
253  // use CAS to set the bit
254  size_t arrpos, bitpos;
255  bit_to_pos(b, arrpos, bitpos);
256  array[arrpos] = 0;
257  }
258 
259  struct bit_pos_iterator {
260  typedef std::input_iterator_tag iterator_category;
261  typedef size_t value_type;
262  typedef size_t difference_type;
263  typedef const size_t reference;
264  typedef const size_t* pointer;
265  size_t pos;
266  const dense_bitset* db;
267  bit_pos_iterator():pos(-1),db(NULL) {}
268  bit_pos_iterator(const dense_bitset* const db, size_t pos):pos(pos),db(db) {}
269 
270  size_t operator*() const {
271  return pos;
272  }
273  size_t operator++(){
274  if (db->next_bit(pos) == false) pos = (size_t)(-1);
275  return pos;
276  }
277  size_t operator++(int){
278  size_t prevpos = pos;
279  if (db->next_bit(pos) == false) pos = (size_t)(-1);
280  return prevpos;
281  }
282  bool operator==(const bit_pos_iterator& other) const {
283  ASSERT_TRUE(db == other.db);
284  return other.pos == pos;
285  }
286  bool operator!=(const bit_pos_iterator& other) const {
287  ASSERT_TRUE(db == other.db);
288  return other.pos != pos;
289  }
290  };
291 
292  typedef bit_pos_iterator iterator;
293  typedef bit_pos_iterator const_iterator;
294 
295 
296  bit_pos_iterator begin() const {
297  size_t pos;
298  if (first_bit(pos) == false) pos = size_t(-1);
299  return bit_pos_iterator(this, pos);
300  }
301 
302  bit_pos_iterator end() const {
303  return bit_pos_iterator(this, (size_t)(-1));
304  }
305 
306  /** Returns true with b containing the position of the
307  first bit set to true.
308  If such a bit does not exist, this function returns false.
309  */
310  inline bool first_bit(size_t &b) const {
311  for (size_t i = 0; i < arrlen; ++i) {
312  if (array[i]) {
313  b = (size_t)(i * (sizeof(size_t) * 8)) + first_bit_in_block(array[i]);
314  return b < len;
315  }
316  }
317  return false;
318  }
319 
320 
321  /** Returns true with b containing the position of the
322  first bit set to false.
323  If such a bit does not exist, this function returns false.
324  */
325  inline bool first_zero_bit(size_t &b) const {
326  for (size_t i = 0; i < arrlen; ++i) {
327  if (~array[i]) {
328  b = (size_t)(i * (sizeof(size_t) * 8)) + first_bit_in_block(~array[i]);
329  return b < len;
330  }
331  }
332  return false;
333  }
334 
335  /** Where b is a bit index, this function will return in b,
336  the position of the next bit set to true, and return true.
337  If all bits after b are false, this function returns false.
338  */
339  inline bool next_bit(size_t &b) const {
340  size_t arrpos, bitpos;
341  bit_to_pos(b, arrpos, bitpos);
342  //try to find the next bit in this block
343  bitpos = next_bit_in_block(bitpos, array[arrpos]);
344  if (bitpos != 0) {
345  b = (size_t)(arrpos * (sizeof(size_t) * 8)) + bitpos;
346  return b < len;
347  }
348  else {
349  // we have to loop through the rest of the array
350  for (size_t i = arrpos + 1; i < arrlen; ++i) {
351  if (array[i]) {
352  b = (size_t)(i * (sizeof(size_t) * 8)) + first_bit_in_block(array[i]);
353  return b < len;
354  }
355  }
356  }
357  return false;
358  }
359 
360  /** Where b is a bit index, this function will return in b, the
361  position of the next bit set to false, and return true. If
362  all bits after b are true, this function returns false.
363  */
364  inline bool next_zero_bit(size_t &b) const {
365  size_t arrpos, bitpos;
366  bit_to_pos(b, arrpos, bitpos);
367  //try to find the next bit in this block
368  bitpos = next_bit_in_block(bitpos, ~(array[arrpos]));
369  size_t _b = len;
370  if (bitpos != 0) {
371  _b = (size_t)(arrpos * (sizeof(size_t) * 8)) + bitpos;
372  } else {
373  // we have to loop through the rest of the array
374  for (size_t i = arrpos + 1; i < arrlen; ++i) {
375  if (~(array[i])) {
376  _b = (size_t)(i * (sizeof(size_t) * 8)) + first_bit_in_block(~(array[i]));
377  break;
378  }
379  }
380  }
381 
382  if(_b < len) {
383  b = _b;
384  return true;
385  } else {
386  return false;
387  }
388  }
389 
390  /// Returns the number of bits in this bitset
391  inline size_t size() const {
392  return len;
393  }
394 
395  /// Serializes this bitset to an archive
396  inline void save(oarchive& oarc) const {
397  oarc <<len << arrlen;
398  if (arrlen > 0) serialize(oarc, array, arrlen*sizeof(size_t));
399  }
400 
401  /// Deserializes this bitset from an archive
402  inline void load(iarchive& iarc) {
403  if (array != NULL) free(array);
404  array = NULL;
405  iarc >> len >> arrlen;
406  if (arrlen > 0) {
407  array = (size_t*)malloc(arrlen*sizeof(size_t));
408  deserialize(iarc, array, arrlen*sizeof(size_t));
409  }
410  }
411 
412 
413  size_t popcount() const {
414  size_t ret = 0;
415  for (size_t i = 0;i < arrlen; ++i) {
416  ret += num_bits_on(array[i]);
417  }
418  return ret;
419  }
420 
421  dense_bitset operator&(const dense_bitset& other) const {
422  ASSERT_EQ(size(), other.size());
423  dense_bitset ret(size());
424  for (size_t i = 0; i < arrlen; ++i) {
425  ret.array[i] = array[i] & other.array[i];
426  }
427  return ret;
428  }
429 
430 
431  dense_bitset operator|(const dense_bitset& other) const {
432  ASSERT_EQ(size(), other.size());
433  dense_bitset ret(size());
434  for (size_t i = 0; i < arrlen; ++i) {
435  ret.array[i] = array[i] | other.array[i];
436  }
437  return ret;
438  }
439 
440  dense_bitset operator-(const dense_bitset& other) const {
441  ASSERT_EQ(size(), other.size());
442  dense_bitset ret(size());
443  for (size_t i = 0; i < arrlen; ++i) {
444  ret.array[i] = array[i] - (array[i] & other.array[i]);
445  }
446  return ret;
447  }
448 
449 
450  dense_bitset& operator&=(const dense_bitset& other) {
451  ASSERT_EQ(size(), other.size());
452  for (size_t i = 0; i < arrlen; ++i) {
453  array[i] &= other.array[i];
454  }
455  return *this;
456  }
457 
458 
459  dense_bitset& operator|=(const dense_bitset& other) {
460  ASSERT_EQ(size(), other.size());
461  for (size_t i = 0; i < arrlen; ++i) {
462  array[i] |= other.array[i];
463  }
464  return *this;
465  }
466 
467  dense_bitset& operator-=(const dense_bitset& other) {
468  ASSERT_EQ(size(), other.size());
469  for (size_t i = 0; i < arrlen; ++i) {
470  array[i] = array[i] - (array[i] & other.array[i]);
471  }
472  return *this;
473  }
474 
475  void invert() {
476  for (size_t i = 0; i < arrlen; ++i) {
477  array[i] = ~array[i];
478  }
479  fix_trailing_bits();
480  }
481 
482  inline static void bit_to_pos(size_t b, size_t& arrpos, size_t& bitpos) {
483  // the compiler better optimize this...
484  arrpos = b / (8 * sizeof(size_t));
485  bitpos = b & (8 * sizeof(size_t) - 1);
486  }
487 
488  // returns 0 on failure
489  inline size_t next_bit_in_block(const size_t& b, const size_t& block) const {
490  size_t belowselectedbit = size_t(-1) - (((size_t(1) << b) - 1)|(size_t(1)<<b));
491  size_t x = block & belowselectedbit ;
492  if (x == 0) return 0;
493  else return (size_t)n_trailing_zeros(x);
494  }
495 
496  // returns 0 on failure
497  inline size_t first_bit_in_block(const size_t& block) const{
498  if (block == 0) return 0;
499  else return (size_t)n_trailing_zeros(block);
500  }
501 
502 
503  void fix_trailing_bits() {
504  // how many bits are in the last block
505  size_t lastbits = len % (8 * sizeof(size_t));
506  if (lastbits == 0) return;
507  array[arrlen - 1] &= ((size_t(1) << lastbits) - 1);
508  }
509 
510  size_t* array;
511  size_t len;
512  size_t arrlen;
513 
514  template <int len>
515  friend class fixed_dense_bitset;
516  };
517 
518 
519 
520 
521 
522 
523 
524 
525 
526 
527 
528 
529 
530 
531 
532 
533 
534 
535 
536 
537 
538 
539 
540 
541 
542 
543  /**
544  Like bitset, but of a fixed length as defined by the template parameter
545  */
546  template <int len>
548  public:
549  /// Constructs a bitset of 0 length
551  clear();
552  }
553 
554  /// Make a copy of the bitset db
556  *this = db;
557  }
558 
559  /** Initialize this fixed dense bitset by copying
560  ceil(len/(wordlen)) words from mem
561  */
562  void initialize_from_mem(void* mem, size_t memlen) {
563  memcpy(array, mem, memlen);
564  }
565 
566  /// destructor
568 
569  /// Make a copy of the bitset db
571  memcpy(array, db.array, sizeof(size_t) * arrlen);
572  return *this;
573  }
574 
575  /// Sets all bits to 0
576  inline void clear() {
577  memset((void*)array, 0, sizeof(size_t) * arrlen);
578  }
579 
580  /// Sets all bits to 1
581  inline void fill() {
582  for (size_t i = 0;i < arrlen; ++i) array[i] = -1;
583  fix_trailing_bits();
584  }
585 
586  inline bool empty() const {
587  for (size_t i = 0; i < arrlen; ++i) if (array[i]) return false;
588  return true;
589  }
590 
591  /// Prefetches the word containing the bit b
592  inline void prefetch(size_t b) const{
593  __builtin_prefetch(&(array[b / (8 * sizeof(size_t))]));
594  }
595 
596  /// Returns the value of the bit b
597  inline bool get(size_t b) const{
598  size_t arrpos, bitpos;
599  bit_to_pos(b, arrpos, bitpos);
600  return array[arrpos] & (size_t(1) << size_t(bitpos));
601  }
602 
603  //! Atomically sets the bit at b to true returning the old value
604  inline bool set_bit(size_t b) {
605  // use CAS to set the bit
606  size_t arrpos, bitpos;
607  bit_to_pos(b, arrpos, bitpos);
608  const size_t mask(size_t(1) << size_t(bitpos));
609  return __sync_fetch_and_or(array + arrpos, mask) & mask;
610  }
611 
612 
613  //! Returns the value of the word containing the bit b
614  inline size_t containing_word(size_t b) {
615  size_t arrpos, bitpos;
616  bit_to_pos(b, arrpos, bitpos);
617  return array[arrpos];
618  }
619 
620 
621  /** Set the bit at position b to true returning the old value.
622  Unlike set_bit(), this uses a non-atomic set which is faster,
623  but is unsafe if accessed by multiple threads.
624  */
625  inline bool set_bit_unsync(size_t b) {
626  // use CAS to set the bit
627  size_t arrpos, bitpos;
628  bit_to_pos(b, arrpos, bitpos);
629  const size_t mask(size_t(1) << size_t(bitpos));
630  bool ret = array[arrpos] & mask;
631  array[arrpos] |= mask;
632  return ret;
633  }
634 
635  /** Set the state of the bit returning the old value.
636  This version uses a non-atomic set which is faster, but
637  is unsafe if accessed by multiple threads.
638  */
639  inline bool set(size_t b, bool value) {
640  if (value) return set_bit(b);
641  else return clear_bit(b);
642  }
643 
644  /** Set the state of the bit returning the old value.
645  This version uses a non-atomic set which is faster, but
646  is unsafe if accessed by multiple threads.
647  */
648  inline bool set_unsync(size_t b, bool value) {
649  size_t arrpos, bitpos;
650  bit_to_pos(b, arrpos, bitpos);
651 
652  const size_t mask(size_t(1) << size_t(bitpos));
653  bool ret = array[arrpos] & mask;
654  array[arrpos]^= (-((size_t)value) ^ array[arrpos]) & mask;
655  return ret;
656  }
657 
658 
659  //! Atomically set the bit at b to false returning the old value
660  inline bool clear_bit(size_t b) {
661  // use CAS to set the bit
662  size_t arrpos, bitpos;
663  bit_to_pos(b, arrpos, bitpos);
664  const size_t test_mask(size_t(1) << size_t(bitpos));
665  const size_t clear_mask(~test_mask);
666  return __sync_fetch_and_and(array + arrpos, clear_mask) & test_mask;
667  }
668 
669  /** Clears the state of the bit returning the old value.
670  This version uses a non-atomic set which is faster, but
671  is unsafe if accessed by multiple threads.
672  */
673  inline bool clear_bit_unsync(size_t b) {
674  // use CAS to set the bit
675  size_t arrpos, bitpos;
676  bit_to_pos(b, arrpos, bitpos);
677  const size_t test_mask(size_t(1) << size_t(bitpos));
678  const size_t clear_mask(~test_mask);
679  bool ret = array[arrpos] & test_mask;
680  array[arrpos] &= clear_mask;
681  return ret;
682  }
683 
684 
685  struct bit_pos_iterator {
686  typedef std::input_iterator_tag iterator_category;
687  typedef size_t value_type;
688  typedef size_t difference_type;
689  typedef const size_t reference;
690  typedef const size_t* pointer;
691  size_t pos;
692  const fixed_dense_bitset* db;
693  bit_pos_iterator():pos(-1),db(NULL) {}
694  bit_pos_iterator(const fixed_dense_bitset* const db, size_t pos):pos(pos),db(db) {}
695 
696  size_t operator*() const {
697  return pos;
698  }
699  size_t operator++(){
700  if (db->next_bit(pos) == false) pos = (size_t)(-1);
701  return pos;
702  }
703  size_t operator++(int){
704  size_t prevpos = pos;
705  if (db->next_bit(pos) == false) pos = (size_t)(-1);
706  return prevpos;
707  }
708  bool operator==(const bit_pos_iterator& other) const {
709  ASSERT_TRUE(db == other.db);
710  return other.pos == pos;
711  }
712  bool operator!=(const bit_pos_iterator& other) const {
713  ASSERT_TRUE(db == other.db);
714  return other.pos != pos;
715  }
716  };
717 
718  typedef bit_pos_iterator iterator;
719  typedef bit_pos_iterator const_iterator;
720 
721 
722  bit_pos_iterator begin() const {
723  size_t pos;
724  if (first_bit(pos) == false) pos = size_t(-1);
725  return bit_pos_iterator(this, pos);
726  }
727 
728  bit_pos_iterator end() const {
729  return bit_pos_iterator(this, (size_t)(-1));
730  }
731 
732  /** Returns true with b containing the position of the
733  first bit set to true.
734  If such a bit does not exist, this function returns false.
735  */
736  inline bool first_bit(size_t &b) const {
737  for (size_t i = 0; i < arrlen; ++i) {
738  if (array[i]) {
739  b = (size_t)(i * (sizeof(size_t) * 8)) + first_bit_in_block(array[i]);
740  return b < len;
741  }
742  }
743  return false;
744  }
745 
746  /** Returns true with b containing the position of the
747  first bit set to false.
748  If such a bit does not exist, this function returns false.
749  */
750  inline bool first_zero_bit(size_t &b) const {
751  for (size_t i = 0; i < arrlen; ++i) {
752  if (~array[i]) {
753  b = (size_t)(i * (sizeof(size_t) * 8)) + first_bit_in_block(~array[i]);
754  return b < len;
755  }
756  }
757  return false;
758  }
759 
760 
761 
762  /** Where b is a bit index, this function will return in b,
763  the position of the next bit set to true, and return true.
764  If all bits after b are false, this function returns false.
765  */
766  inline bool next_bit(size_t &b) const {
767  size_t arrpos, bitpos;
768  bit_to_pos(b, arrpos, bitpos);
769  //try to find the next bit in this block
770  bitpos = next_bit_in_block(bitpos, array[arrpos]);
771  if (bitpos != 0) {
772  b = (size_t)(arrpos * (sizeof(size_t) * 8)) + bitpos;
773  return b < len;
774  }
775  else {
776  // we have to loop through the rest of the array
777  for (size_t i = arrpos + 1; i < arrlen; ++i) {
778  if (array[i]) {
779  b = (size_t)(i * (sizeof(size_t) * 8)) + first_bit_in_block(array[i]);
780  return b < len;
781  }
782  }
783  }
784  return false;
785  }
786 
787  /// Returns the number of bits in this bitset
788  inline size_t size() const {
789  return len;
790  }
791 
792  /// Serializes this bitset to an archive
793  inline void save(oarchive& oarc) const {
794  //oarc <<len << arrlen;
795  //if (arrlen > 0)
796  serialize(oarc, array, arrlen*sizeof(size_t));
797  }
798 
799  /// Deserializes this bitset from an archive
800  inline void load(iarchive& iarc) {
801  /*size_t l;
802  size_t arl;
803  iarc >> l >> arl;
804  ASSERT_EQ(l, len);
805  ASSERT_EQ(arl, arrlen);*/
806  //if (arrlen > 0) {
807  deserialize(iarc, array, arrlen*sizeof(size_t));
808  //}
809  }
810 
811  size_t popcount() const {
812  size_t ret = 0;
813  for (size_t i = 0;i < arrlen; ++i) {
814  ret += __builtin_popcountll(array[i]);
815  }
816  return ret;
817  }
818 
819  fixed_dense_bitset operator&(const fixed_dense_bitset& other) const {
820  ASSERT_EQ(size(), other.size());
821  fixed_dense_bitset ret(size());
822  for (size_t i = 0; i < arrlen; ++i) {
823  ret.array[i] = array[i] & other.array[i];
824  }
825  return ret;
826  }
827 
828 
829  fixed_dense_bitset operator|(const fixed_dense_bitset& other) const {
830  ASSERT_EQ(size(), other.size());
831  fixed_dense_bitset ret(size());
832  for (size_t i = 0; i < arrlen; ++i) {
833  ret.array[i] = array[i] | other.array[i];
834  }
835  return ret;
836  }
837 
838  fixed_dense_bitset operator-(const fixed_dense_bitset& other) const {
839  ASSERT_EQ(size(), other.size());
840  fixed_dense_bitset ret(size());
841  for (size_t i = 0; i < arrlen; ++i) {
842  ret.array[i] = array[i] - (array[i] & other.array[i]);
843  }
844  return ret;
845  }
846 
847 
848  fixed_dense_bitset& operator&=(const fixed_dense_bitset& other) {
849  ASSERT_EQ(size(), other.size());
850  for (size_t i = 0; i < arrlen; ++i) {
851  array[i] &= other.array[i];
852  }
853  return *this;
854  }
855 
856 
857  fixed_dense_bitset& operator|=(const fixed_dense_bitset& other) {
858  ASSERT_EQ(size(), other.size());
859  for (size_t i = 0; i < arrlen; ++i) {
860  array[i] |= other.array[i];
861  }
862  return *this;
863  }
864 
865  fixed_dense_bitset& operator-=(const fixed_dense_bitset& other) {
866  ASSERT_EQ(size(), other.size());
867  for (size_t i = 0; i < arrlen; ++i) {
868  array[i] = array[i] - (array[i] & other.array[i]);
869  }
870  return *this;
871  }
872 
873  bool operator==(const fixed_dense_bitset& other) const {
874  ASSERT_EQ(size(), other.size());
875  ASSERT_EQ(arrlen, other.arrlen);
876  bool ret = true;
877  for (size_t i = 0; i < arrlen; ++i) {
878  ret &= (array[i] == other.array[i]);
879  }
880  return ret;
881  }
882 
883  inline static void bit_to_pos(size_t b, size_t &arrpos, size_t &bitpos) {
884  // the compiler better optimize this...
885  arrpos = b / (8 * sizeof(size_t));
886  bitpos = b & (8 * sizeof(size_t) - 1);
887  }
888 
889 
890  // returns 0 on failure
891  inline size_t next_bit_in_block(const size_t &b, const size_t &block) const {
892  size_t belowselectedbit = size_t(-1) - (((size_t(1) << b) - 1)|(size_t(1)<<b));
893  size_t x = block & belowselectedbit ;
894  if (x == 0) return 0;
895  else return (size_t)n_trailing_zeros(x);
896  }
897 
898  // returns 0 on failure
899  inline size_t first_bit_in_block(const size_t &block) const {
900  // use CAS to set the bit
901  if (block == 0) return 0;
902  else return (size_t)n_trailing_zeros(block);
903  }
904 
905  // clears the trailing bits in the last block which are not part
906  // of the actual length of the bitset
907  void fix_trailing_bits() {
908  // how many bits are in the last block
909  size_t lastbits = len % (8 * sizeof(size_t));
910  if (lastbits == 0) return;
911  array[arrlen - 1] &= ((size_t(1) << lastbits) - 1);
912  }
913 
914 
915  static const size_t arrlen;
916  size_t array[len / (sizeof(size_t) * 8) + (len % (sizeof(size_t) * 8) > 0)];
917  };
918 
919  template<int len>
920  const size_t fixed_dense_bitset<len>::arrlen = len / (sizeof(size_t) * 8) + (len % (sizeof(size_t) * 8) > 0);
921 }
922 #endif
bool set_bit(size_t b)
Atomically sets the bit at b to true returning the old value.
void save(oarchive &oarc) const
Serializes this bitset to an archive.
static unsigned int n_trailing_zeros(T v, _ENABLE_IF_UINT(T))
Definition: bitops.hpp:206
size_t size() const
Returns the number of bits in this bitset.
bool next_zero_bit(size_t &b) const
void save(oarchive &oarc) const
Serializes this bitset to an archive.
The serialization input archive object which, provided with a reference to an istream, will read from the istream, providing deserialization capabilities.
Definition: iarchive.hpp:60
bool set_bit_unsync(size_t b)
bool set_unsync(size_t b, bool value)
static unsigned int num_bits_on(T v, _ENABLE_IF_UINT(T))
Definition: bitops.hpp:154
dense_bitset & operator=(const dense_bitset &db)
Make a copy of the bitset db.
bool set_unsync(size_t b, bool value)
void initialize_from_mem(void *mem, size_t memlen)
void load(iarchive &iarc)
Deserializes this bitset from an archive.
bool clear_bit(size_t b)
Atomically set the bit at b to false returning the old value.
~fixed_dense_bitset()
destructor
void prefetch(size_t b) const
Prefetches the word containing the bit b.
void clear_word_unsync(size_t b)
void load(iarchive &iarc)
Deserializes this bitset from an archive.
size_t get_containing_word_and_zero(size_t b)
Returns the value of the word containing the bit b.
bool first_bit(size_t &b) const
bool set_bit_unsync(size_t b)
dense_bitset()
Constructs a bitset of 0 length.
void fill()
Sets all bits to 1.
void resize(size_t n)
bool first_zero_bit(size_t &b) const
dense_bitset(const dense_bitset &db)
Make a copy of the bitset db.
void clear()
Sets all bits to 0.
void fill()
Sets all bits to 1.
bool next_bit(size_t &b) const
size_t containing_word(size_t b)
Returns the value of the word containing the bit b.
#define ASSERT_TRUE(cond)
Definition: assertions.hpp:309
dense_bitset(size_t size)
Constructs a bitset with &#39;size&#39; bits. All bits will be cleared.
bool first_bit(size_t &b) const
fixed_dense_bitset(const fixed_dense_bitset< len > &db)
Make a copy of the bitset db.
fixed_dense_bitset< len > & operator=(const fixed_dense_bitset< len > &db)
Make a copy of the bitset db.
T fetch_and_store(T &a, const T &newval)
Atomically sets a to the newval, returning the old value.
Definition: atomic_ops.hpp:162
size_t size() const
Returns the number of bits in this bitset.
bool first_zero_bit(size_t &b) const
bool clear_bit_unsync(size_t b)
void prefetch(size_t b) const
Prefetches the word containing the bit b.
bool next_bit(size_t &b) const
The serialization output archive object which, provided with a reference to an ostream, will write to the ostream, providing serialization capabilities.
Definition: oarchive.hpp:80
bool set_bit(size_t b)
Atomically sets the bit at position b to true returning the old value.
size_t containing_word(size_t b)
Returns the value of the word containing the bit b.
~dense_bitset()
destructor
bool clear_bit_unsync(size_t b)
bool clear_bit(size_t b)
Atomically set the bit at b to false returning the old value.
fixed_dense_bitset()
Constructs a bitset of 0 length.
bool xor_bit(size_t b)
Atomically xors a bit with 1.
void clear()
Sets all bits to 0.
void transfer_approximate_unsafe(dense_bitset &other, size_t &start, size_t &b)
Transfers approximately b bits from another bitset to this bitset.