GraphChi 0.1

- Main Page
- Namespaces
- Classes
- Files

- File List
- File Members

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