GraphChi  0.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Macros
dense_bitset.hpp
1 
2 // NOTE, copied from GraphLab v 0.5
3 
4 #ifndef DENSE_BITSET_HPP
5 #define DENSE_BITSET_HPP
6 #include <cstdio>
7 #include <cstdlib>
8 #include <stdint.h>
9 
10 namespace graphchi {
11  class dense_bitset {
12  public:
13  dense_bitset() : array(NULL), len(0) {
14  generate_bit_masks();
15  }
16 
17  dense_bitset(size_t size) : array(NULL), len(size) {
18  resize(size);
19  clear();
20  generate_bit_masks();
21  }
22 
23 
24  virtual ~dense_bitset() {free(array);}
25 
26  void resize(size_t n) {
27  len = n;
28  //need len bits
29  arrlen = n / (8*sizeof(size_t)) + 1;
30  array = (size_t*)realloc(array, sizeof(size_t) * arrlen);
31  }
32 
33  void clear() {
34  for (size_t i = 0;i < arrlen; ++i) array[i] = 0;
35  }
36 
37  void setall() {
38  memset(array, 0xff, arrlen * sizeof(size_t));
39  }
40 
41  inline bool get(uint32_t b) const{
42  uint32_t arrpos, bitpos;
43  bit_to_pos(b, arrpos, bitpos);
44  return array[arrpos] & (size_t(1) << size_t(bitpos));
45  }
46 
48  inline bool set_bit(uint32_t b) {
49  // use CAS to set the bit
50  uint32_t arrpos, bitpos;
51  bit_to_pos(b, arrpos, bitpos);
52  const size_t mask(size_t(1) << size_t(bitpos));
53  return __sync_fetch_and_or(array + arrpos, mask) & mask;
54  }
55 
57  inline bool set(uint32_t b, bool value) {
58  if (value) return set_bit(b);
59  else return clear_bit(b);
60  }
61 
63  inline bool clear_bit(uint32_t b) {
64  // use CAS to set the bit
65  uint32_t arrpos, bitpos;
66  bit_to_pos(b, arrpos, bitpos);
67  const size_t test_mask(size_t(1) << size_t(bitpos));
68  const size_t clear_mask(~test_mask);
69  return __sync_fetch_and_and(array + arrpos, clear_mask) & test_mask;
70  }
71 
72  inline void clear_bits(uint32_t fromb, uint32_t tob) { // tob is inclusive
73  // Careful with alignment
74  const size_t bitsperword = sizeof(size_t)*8;
75  while((fromb%bitsperword != 0)) {
76  clear_bit(fromb);
77  if (fromb>=tob) return;
78  fromb++;
79  }
80 
81  while((tob%bitsperword != 0)) {
82  clear_bit(tob);
83  if(tob<=fromb) return;
84  tob--;
85  }
86  clear_bit(tob);
87 
88  uint32_t from_arrpos = fromb / (8 * (int) sizeof(size_t));
89  uint32_t to_arrpos = tob / (8 * (int) sizeof(size_t));
90  memset(&array[from_arrpos], 0, (to_arrpos-from_arrpos) * (int) sizeof(size_t));
91  }
92 
93 
94  inline size_t size() const {
95  return len;
96  }
97 
98  private:
99 
100 
101  inline static void bit_to_pos(uint32_t b, uint32_t &arrpos, uint32_t &bitpos) {
102  // the compiler better optimize this...
103  arrpos = b / (8 * (int)sizeof(size_t));
104  bitpos = b & (8 * (int)sizeof(size_t) - 1);
105  }
106 
107  void generate_bit_masks() {
108  below_selectedbit[0] = size_t(-2);
109  for (size_t i = 0;i < 8 * sizeof(size_t) ; ++i) {
110  selectbit[i] = size_t(1) << i;
111  notselectbit[i] = ~selectbit[i];
112  if (i > 0) below_selectedbit[i] = below_selectedbit[i-1] - selectbit[i];
113  }
114  }
115 
116  // returns 0 on failure
117  inline size_t next_bit_in_block(const uint32_t &b, const size_t &block) {
118  // use CAS to set the bit
119  size_t x = block & below_selectedbit[b] ;
120  if (x == 0) return 0;
121  else return __builtin_ctzl(x);
122  }
123 
124  // returns 0 on failure
125  inline size_t first_bit_in_block(const size_t &block) {
126  // use CAS to set the bit
127  if (block == 0) return 0;
128  else return __builtin_ctzl(block);
129  }
130 
131  size_t* array;
132  size_t len;
133  size_t arrlen;
134  // selectbit[i] has a bit in the i'th position
135  size_t selectbit[8 * sizeof(size_t)];
136  size_t notselectbit[8 * sizeof(size_t)];
137  size_t below_selectedbit[8 * sizeof(size_t)];
138  };
139 
140 }
141 #endif