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, 9 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 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
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