ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/gclib/gclib/GBitVec.h
Revision: 144
Committed: Thu Dec 22 19:15:46 2011 UTC (7 years, 2 months ago) by gpertea
File size: 10831 byte(s)
Log Message:
added GBitVec.h; removed operator> requirement for sorted vectors; swap() is now template Gswap()

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