ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/gclib/gclib/GBitVec.h
Revision: 310
Committed: Fri Mar 22 20:06:27 2013 UTC (6 years, 1 month ago) by gpertea
File size: 13177 byte(s)
Log Message:
sync with igm repo

Line User Rev File contents
1 gpertea 144 #ifndef __GBITVEC_H__
2     #define __GBITVEC_H__
3     #include "GBase.h"
4     //this code is lifted from LLVM (llvm.org, BitVector.h)
5    
6 gpertea 179 /// 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 gpertea 144
19 gpertea 179 /// 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 gpertea 144 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 gpertea 286 /// clear - Clear all bits; does NOT release memory
239 gpertea 144 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 gpertea 310 register uint i;
336     uint imax=GMIN(ThisWords, RHSWords);
337     for (i = 0; i != imax; ++i)
338 gpertea 144 if (fBits[i] != RHS.fBits[i])
339     return false;
340    
341     // Verify that any extra words are all zeros.
342     if (i != ThisWords) {
343     for (; i != ThisWords; ++i)
344     if (fBits[i])
345     return false;
346     } else if (i != RHSWords) {
347     for (; i != RHSWords; ++i)
348     if (RHS.fBits[i])
349     return false;
350     }
351     return true;
352     }
353    
354     bool operator!=(const GBitVec &RHS) const {
355     return !(*this == RHS);
356     }
357    
358     // Intersection, union, disjoint union.
359     GBitVec &operator&=(const GBitVec &RHS) {
360     uint ThisWords = NumBitWords(size());
361     uint RHSWords = NumBitWords(RHS.size());
362 gpertea 310 register uint i;
363     uint imax=GMIN(ThisWords, RHSWords);
364     for (i = 0; i != imax; ++i)
365 gpertea 144 fBits[i] &= RHS.fBits[i];
366    
367     // Any bits that are just in this GBitVec become zero, because they aren't
368     // in the RHS bit vector. Any words only in RHS are ignored because they
369     // are already zero in the LHS.
370     for (; i != ThisWords; ++i)
371     fBits[i] = 0;
372    
373     return *this;
374     }
375    
376     GBitVec &operator|=(const GBitVec &RHS) {
377     if (size() < RHS.size())
378     resize(RHS.size());
379     for (size_t i = 0, e = NumBitWords(RHS.size()); i != e; ++i)
380     fBits[i] |= RHS.fBits[i];
381     return *this;
382     }
383    
384     GBitVec &operator^=(const GBitVec &RHS) {
385     if (size() < RHS.size())
386     resize(RHS.size());
387     for (size_t i = 0, e = NumBitWords(RHS.size()); i != e; ++i)
388     fBits[i] ^= RHS.fBits[i];
389     return *this;
390     }
391    
392     // Assignment operator.
393     const GBitVec &operator=(const GBitVec &RHS) {
394     if (this == &RHS) return *this;
395    
396     Size = RHS.size();
397     uint RHSWords = NumBitWords(Size);
398     if (Size <= Capacity * BITWORD_SIZE) {
399     if (Size)
400     memcpy(fBits, RHS.fBits, RHSWords * sizeof(BitWord));
401     clear_unused_bits();
402     return *this;
403     }
404    
405     // Grow the GBitVec to have enough elements.
406     Capacity = RHSWords;
407     //BitWord *NewBits = (BitWord *)std::malloc(Capacity * sizeof(BitWord));
408     BitWord *NewBits = NULL;
409     GMALLOC(NewBits, Capacity * sizeof(BitWord));
410     memcpy(NewBits, RHS.fBits, Capacity * sizeof(BitWord));
411    
412     // Destroy the old bits.
413     GFREE(fBits);
414     fBits = NewBits;
415    
416     return *this;
417     }
418    
419     void swap(GBitVec &RHS) {
420     Gswap(fBits, RHS.fBits);
421     Gswap(Size, RHS.Size);
422     Gswap(Capacity, RHS.Capacity);
423     }
424    
425     private:
426     uint NumBitWords(uint S) const {
427     return (S + BITWORD_SIZE-1) / BITWORD_SIZE;
428     }
429    
430     // Set the unused bits in the high words.
431     void set_unused_bits(bool value = true) {
432     // Set high words first.
433     uint UsedWords = NumBitWords(Size);
434     if (Capacity > UsedWords)
435     init_words(&fBits[UsedWords], (Capacity-UsedWords), value);
436    
437     // Then set any stray high bits of the last used word.
438     uint ExtraBits = Size % BITWORD_SIZE;
439     if (ExtraBits) {
440     fBits[UsedWords-1] &= ~(~0L << ExtraBits);
441     fBits[UsedWords-1] |= (0 - (BitWord)value) << ExtraBits;
442     }
443     }
444    
445     // Clear the unused bits in the high words.
446     void clear_unused_bits() {
447     set_unused_bits(false);
448     }
449    
450     void grow(uint NewSize) {
451     Capacity = GMAX(NumBitWords(NewSize), Capacity * 2);
452     //fBits = (BitWord *)std::realloc(fBits, Capacity * sizeof(BitWord));
453     GREALLOC(fBits, Capacity * sizeof(BitWord));
454     clear_unused_bits();
455     }
456    
457     void init_words(BitWord *B, uint NumWords, bool value) {
458     memset(B, 0 - (int)value, NumWords*sizeof(BitWord));
459     }
460     };
461    
462    
463     inline GBitVec operator&(const GBitVec &LHS, const GBitVec &RHS) {
464     GBitVec Result(LHS);
465     Result &= RHS;
466     return Result;
467     }
468    
469     inline GBitVec operator|(const GBitVec &LHS, const GBitVec &RHS) {
470     GBitVec Result(LHS);
471     Result |= RHS;
472     return Result;
473     }
474    
475     inline GBitVec operator^(const GBitVec &LHS, const GBitVec &RHS) {
476     GBitVec Result(LHS);
477     Result ^= RHS;
478     return Result;
479     }
480    
481     inline void Gswap(GBitVec &LHS, GBitVec &RHS) {
482     LHS.swap(RHS);
483     }
484    
485     #endif