ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/gclib/gclib/GBitVec.h
Revision: 179
Committed: Thu Feb 16 16:23:45 2012 UTC (7 years, 2 months ago) by gpertea
File size: 13095 byte(s)
Log Message:
moved bit handling inlines from GBase to GBitVec

Line File contents
1 #ifndef __GBITVEC_H__
2 #define __GBITVEC_H__
3 #include "GBase.h"
4 //this code is lifted from LLVM (llvm.org, BitVector.h)
5
6 /// bitCount_32 - this function counts the number of set bits in a value.
7 /// Ex. CountPopulation(0xF000F000) = 8
8 /// Returns 0 if the word is zero.
9 inline uint bitCount_32(uint32_t Value) {
10 #if __GNUC__ >= 4
11 return __builtin_popcount(Value);
12 #else
13 uint32_t v = Value - ((Value >> 1) & 0x55555555);
14 v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
15 return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
16 #endif
17 }
18
19 /// bitCount_64 - this function counts the number of set bits in a value,
20 /// (64 bit edition.)
21 inline uint bitCount_64(uint64_t Value) {
22 #if __GNUC__ >= 4
23 return __builtin_popcountll(Value);
24 #else
25 uint64_t v = Value - ((Value >> 1) & 0x5555555555555555ULL);
26 v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL);
27 v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
28 return uint((uint64_t)(v * 0x0101010101010101ULL) >> 56);
29 #endif
30 }
31
32 /// CountTrailingZeros_32 - this function performs the platform optimal form of
33 /// counting the number of zeros from the least significant bit to the first one
34 /// bit. Ex. CountTrailingZeros_32(0xFF00FF00) == 8.
35 /// Returns 32 if the word is zero.
36 inline unsigned bitCountTrailingZeros_32(uint32_t Value) {
37 #if __GNUC__ >= 4
38 return Value ? __builtin_ctz(Value) : 32;
39 #else
40 static const unsigned Mod37BitPosition[] = {
41 32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13,
42 4, 7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9,
43 5, 20, 8, 19, 18
44 };
45 return Mod37BitPosition[(-Value & Value) % 37];
46 #endif
47 }
48
49 // CountTrailingZeros_64 - This function performs the platform optimal form
50 /// of counting the number of zeros from the least significant bit to the first
51 /// one bit (64 bit edition.)
52 /// Returns 64 if the word is zero.
53 inline unsigned bitCountTrailingZeros_64(uint64_t Value) {
54 #if __GNUC__ >= 4
55 return Value ? __builtin_ctzll(Value) : 64;
56 #else
57 static const unsigned Mod67Position[] = {
58 64, 0, 1, 39, 2, 15, 40, 23, 3, 12, 16, 59, 41, 19, 24, 54,
59 4, 64, 13, 10, 17, 62, 60, 28, 42, 30, 20, 51, 25, 44, 55,
60 47, 5, 32, 65, 38, 14, 22, 11, 58, 18, 53, 63, 9, 61, 27,
61 29, 50, 43, 46, 31, 37, 21, 57, 52, 8, 26, 49, 45, 36, 56,
62 7, 48, 35, 6, 34, 33, 0
63 };
64 return Mod67Position[(-Value & Value) % 67];
65 #endif
66 }
67
68 class GBitVec {
69 typedef unsigned long BitWord;
70
71 enum { BITWORD_SIZE = (uint)sizeof(BitWord) * CHAR_BIT };
72
73 BitWord *fBits; // Actual bits.
74 uint Size; // Size of GBitVec in bits.
75 uint Capacity; // Size of allocated memory in BitWord.
76
77 public:
78 // Encapsulation of a single bit.
79 class GBitRef {
80 friend class GBitVec;
81 BitWord *WordRef;
82 uint BitPos;
83 GBitRef(); // Undefined
84 public:
85 GBitRef(GBitVec &b, uint Idx) {
86 WordRef = &b.fBits[Idx / BITWORD_SIZE];
87 BitPos = Idx % BITWORD_SIZE;
88 }
89
90 ~GBitRef() {}
91
92 GBitRef &operator=(GBitRef t) {
93 *this = bool(t);
94 return *this;
95 }
96
97 GBitRef& operator=(bool t) {
98 if (t)
99 *WordRef |= 1L << BitPos;
100 else
101 *WordRef &= ~(1L << BitPos);
102 return *this;
103 }
104
105 operator bool() const {
106 return ((*WordRef) & (1L << BitPos)) ? true : false;
107 }
108 };
109
110
111 /// GBitVec default ctor - Creates an empty GBitVec.
112 GBitVec() : Size(0), Capacity(0) {
113 fBits = 0;
114 }
115
116 /// GBitVec ctor - Creates a GBitVec of specified number of bits. All
117 /// bits are initialized to the specified value.
118 explicit GBitVec(uint s, bool value = false) : Size(s) {
119 Capacity = NumBitWords(s);
120 //fBits = (BitWord *)std::malloc(Capacity * sizeof(BitWord));
121 GMALLOC(fBits, Capacity * sizeof(BitWord));
122 init_words(fBits, Capacity, value);
123 if (value)
124 clear_unused_bits();
125 }
126
127 /// GBitVec copy ctor.
128 GBitVec(const GBitVec &RHS) : Size(RHS.size()) {
129 if (Size == 0) {
130 fBits = 0;
131 Capacity = 0;
132 return;
133 }
134
135 Capacity = NumBitWords(RHS.size());
136 //fBits = (BitWord *)std::malloc(Capacity * sizeof(BitWord));
137 GMALLOC(fBits, Capacity * sizeof(BitWord));
138 memcpy(fBits, RHS.fBits, Capacity * sizeof(BitWord));
139 }
140
141 ~GBitVec() {
142 GFREE(fBits);
143 }
144
145 /// empty - Tests whether there are no bits in this GBitVec.
146 bool empty() const { return Size == 0; }
147
148 /// size - Returns the number of bits in this GBitVec.
149 uint size() const { return Size; }
150
151
152 void bitSizeError() {
153 GError("Error at GBitVec: unsupported BitWord size (%d)!\n",
154 sizeof(BitWord));
155 }
156 /// count - Returns the number of bits which are set.
157 uint count() {
158 uint NumBits = 0;
159 for (uint i = 0; i < NumBitWords(size()); ++i)
160 if (sizeof(BitWord) == 4)
161 NumBits += bitCount_32((uint32_t)fBits[i]);
162 else if (sizeof(BitWord) == 8)
163 NumBits += bitCount_64(fBits[i]);
164 else
165 bitSizeError();
166 return NumBits;
167 }
168
169 /// any - Returns true if any bit is set.
170 bool any() {
171 for (uint i = 0; i < NumBitWords(size()); ++i)
172 if (fBits[i] != 0)
173 return true;
174 return false;
175 }
176
177 /// all - Returns true if all bits are set.
178 bool all() {
179 // TODO: Optimize this.
180 return count() == size();
181 }
182
183 /// none - Returns true if none of the bits are set.
184 bool none() {
185 return !any();
186 }
187
188 /// find_first - Returns the index of the first set bit, -1 if none
189 /// of the bits are set.
190 int find_first() {
191 for (uint i = 0; i < NumBitWords(size()); ++i)
192 if (fBits[i] != 0) {
193 if (sizeof(BitWord) == 4)
194 return i * BITWORD_SIZE + bitCountTrailingZeros_32((uint32_t)fBits[i]);
195 else if (sizeof(BitWord) == 8)
196 return i * BITWORD_SIZE + bitCountTrailingZeros_64(fBits[i]);
197 else
198 bitSizeError();
199 }
200 return -1;
201 }
202
203 /// find_next - Returns the index of the next set bit following the
204 /// "Prev" bit. Returns -1 if the next set bit is not found.
205 int find_next(uint Prev) {
206 ++Prev;
207 if (Prev >= Size)
208 return -1;
209
210 uint WordPos = Prev / BITWORD_SIZE;
211 uint BitPos = Prev % BITWORD_SIZE;
212 BitWord Copy = fBits[WordPos];
213 // Mask off previous bits.
214 Copy &= ~0L << BitPos;
215
216 if (Copy != 0) {
217 if (sizeof(BitWord) == 4)
218 return WordPos * BITWORD_SIZE + bitCountTrailingZeros_32((uint32_t)Copy);
219 else if (sizeof(BitWord) == 8)
220 return WordPos * BITWORD_SIZE + bitCountTrailingZeros_64(Copy);
221 else
222 bitSizeError();
223 }
224
225 // Check subsequent words.
226 for (uint i = WordPos+1; i < NumBitWords(size()); ++i)
227 if (fBits[i] != 0) {
228 if (sizeof(BitWord) == 4)
229 return i * BITWORD_SIZE + bitCountTrailingZeros_32((uint32_t)fBits[i]);
230 else if (sizeof(BitWord) == 8)
231 return i * BITWORD_SIZE + bitCountTrailingZeros_64(fBits[i]);
232 else
233 bitSizeError();
234 }
235 return -1;
236 }
237
238 /// clear - Clear all bits.
239 void clear() {
240 Size = 0;
241 }
242
243 /// resize - Grow or shrink the GBitVec.
244 void resize(uint N, bool value = false) {
245 if (N > Capacity * BITWORD_SIZE) {
246 uint OldCapacity = Capacity;
247 grow(N);
248 init_words(&fBits[OldCapacity], (Capacity-OldCapacity), value);
249 }
250
251 // Set any old unused bits that are now included in the GBitVec. This
252 // may set bits that are not included in the new vector, but we will clear
253 // them back out below.
254 if (N > Size)
255 set_unused_bits(value);
256
257 // Update the size, and clear out any bits that are now unused
258 uint OldSize = Size;
259 Size = N;
260 if (value || N < OldSize)
261 clear_unused_bits();
262 }
263
264 void reserve(uint N) {
265 if (N > Capacity * BITWORD_SIZE)
266 grow(N);
267 }
268
269 // Set, reset, flip
270 GBitVec &set() {
271 init_words(fBits, Capacity, true);
272 clear_unused_bits();
273 return *this;
274 }
275
276 GBitVec &set(uint Idx) {
277 fBits[Idx / BITWORD_SIZE] |= 1L << (Idx % BITWORD_SIZE);
278 return *this;
279 }
280
281 GBitVec &reset() {
282 init_words(fBits, Capacity, false);
283 return *this;
284 }
285
286 GBitVec &reset(uint Idx) {
287 fBits[Idx / BITWORD_SIZE] &= ~(1L << (Idx % BITWORD_SIZE));
288 return *this;
289 }
290
291 GBitVec &flip() {
292 for (uint i = 0; i < NumBitWords(size()); ++i)
293 fBits[i] = ~fBits[i];
294 clear_unused_bits();
295 return *this;
296 }
297
298 GBitVec &flip(uint Idx) {
299 fBits[Idx / BITWORD_SIZE] ^= 1L << (Idx % BITWORD_SIZE);
300 return *this;
301 }
302
303 // No argument flip.
304 GBitVec operator~() const {
305 return GBitVec(*this).flip();
306 }
307
308 inline static void indexCheck(uint vIdx, uint vSize) {
309 if (vIdx >= vSize)
310 GError("Error at GBitVec: index %d out of bounds (size %d)\n",
311 (int)vIdx, vSize);
312 }
313
314 // Indexing.
315 GBitRef operator[](uint Idx) {
316 //assert (Idx < Size && "Out-of-bounds Bit access.");
317 indexCheck(Idx, Size);
318 return GBitRef(*this, Idx);
319 }
320
321 bool operator[](uint Idx) const {
322 indexCheck(Idx, Size);
323 BitWord Mask = 1L << (Idx % BITWORD_SIZE);
324 return (fBits[Idx / BITWORD_SIZE] & Mask) != 0;
325 }
326
327 bool test(uint Idx) const {
328 return (*this)[Idx];
329 }
330
331 // Comparison operators.
332 bool operator==(const GBitVec &RHS) const {
333 uint ThisWords = NumBitWords(size());
334 uint RHSWords = NumBitWords(RHS.size());
335 uint i;
336 for (i = 0; i != GMIN(ThisWords, RHSWords); ++i)
337 if (fBits[i] != RHS.fBits[i])
338 return false;
339
340 // Verify that any extra words are all zeros.
341 if (i != ThisWords) {
342 for (; i != ThisWords; ++i)
343 if (fBits[i])
344 return false;
345 } else if (i != RHSWords) {
346 for (; i != RHSWords; ++i)
347 if (RHS.fBits[i])
348 return false;
349 }
350 return true;
351 }
352
353 bool operator!=(const GBitVec &RHS) const {
354 return !(*this == RHS);
355 }
356
357 // Intersection, union, disjoint union.
358 GBitVec &operator&=(const GBitVec &RHS) {
359 uint ThisWords = NumBitWords(size());
360 uint RHSWords = NumBitWords(RHS.size());
361 uint i;
362 for (i = 0; i != GMIN(ThisWords, RHSWords); ++i)
363 fBits[i] &= RHS.fBits[i];
364
365 // Any bits that are just in this GBitVec become zero, because they aren't
366 // in the RHS bit vector. Any words only in RHS are ignored because they
367 // are already zero in the LHS.
368 for (; i != ThisWords; ++i)
369 fBits[i] = 0;
370
371 return *this;
372 }
373
374 GBitVec &operator|=(const GBitVec &RHS) {
375 if (size() < RHS.size())
376 resize(RHS.size());
377 for (size_t i = 0, e = NumBitWords(RHS.size()); i != e; ++i)
378 fBits[i] |= RHS.fBits[i];
379 return *this;
380 }
381
382 GBitVec &operator^=(const GBitVec &RHS) {
383 if (size() < RHS.size())
384 resize(RHS.size());
385 for (size_t i = 0, e = NumBitWords(RHS.size()); i != e; ++i)
386 fBits[i] ^= RHS.fBits[i];
387 return *this;
388 }
389
390 // Assignment operator.
391 const GBitVec &operator=(const GBitVec &RHS) {
392 if (this == &RHS) return *this;
393
394 Size = RHS.size();
395 uint RHSWords = NumBitWords(Size);
396 if (Size <= Capacity * BITWORD_SIZE) {
397 if (Size)
398 memcpy(fBits, RHS.fBits, RHSWords * sizeof(BitWord));
399 clear_unused_bits();
400 return *this;
401 }
402
403 // Grow the GBitVec to have enough elements.
404 Capacity = RHSWords;
405 //BitWord *NewBits = (BitWord *)std::malloc(Capacity * sizeof(BitWord));
406 BitWord *NewBits = NULL;
407 GMALLOC(NewBits, Capacity * sizeof(BitWord));
408 memcpy(NewBits, RHS.fBits, Capacity * sizeof(BitWord));
409
410 // Destroy the old bits.
411 GFREE(fBits);
412 fBits = NewBits;
413
414 return *this;
415 }
416
417 void swap(GBitVec &RHS) {
418 Gswap(fBits, RHS.fBits);
419 Gswap(Size, RHS.Size);
420 Gswap(Capacity, RHS.Capacity);
421 }
422
423 private:
424 uint NumBitWords(uint S) const {
425 return (S + BITWORD_SIZE-1) / BITWORD_SIZE;
426 }
427
428 // Set the unused bits in the high words.
429 void set_unused_bits(bool value = true) {
430 // Set high words first.
431 uint UsedWords = NumBitWords(Size);
432 if (Capacity > UsedWords)
433 init_words(&fBits[UsedWords], (Capacity-UsedWords), value);
434
435 // Then set any stray high bits of the last used word.
436 uint ExtraBits = Size % BITWORD_SIZE;
437 if (ExtraBits) {
438 fBits[UsedWords-1] &= ~(~0L << ExtraBits);
439 fBits[UsedWords-1] |= (0 - (BitWord)value) << ExtraBits;
440 }
441 }
442
443 // Clear the unused bits in the high words.
444 void clear_unused_bits() {
445 set_unused_bits(false);
446 }
447
448 void grow(uint NewSize) {
449 Capacity = GMAX(NumBitWords(NewSize), Capacity * 2);
450 //fBits = (BitWord *)std::realloc(fBits, Capacity * sizeof(BitWord));
451 GREALLOC(fBits, Capacity * sizeof(BitWord));
452 clear_unused_bits();
453 }
454
455 void init_words(BitWord *B, uint NumWords, bool value) {
456 memset(B, 0 - (int)value, NumWords*sizeof(BitWord));
457 }
458 };
459
460
461 inline GBitVec operator&(const GBitVec &LHS, const GBitVec &RHS) {
462 GBitVec Result(LHS);
463 Result &= RHS;
464 return Result;
465 }
466
467 inline GBitVec operator|(const GBitVec &LHS, const GBitVec &RHS) {
468 GBitVec Result(LHS);
469 Result |= RHS;
470 return Result;
471 }
472
473 inline GBitVec operator^(const GBitVec &LHS, const GBitVec &RHS) {
474 GBitVec Result(LHS);
475 Result ^= RHS;
476 return Result;
477 }
478
479 inline void Gswap(GBitVec &LHS, GBitVec &RHS) {
480 LHS.swap(RHS);
481 }
482
483 #endif