9 #include "assert_helpers.h"
10 #include "threading.h"
13 * Given a words array and a size, allocate a new, larger array, moving
14 * data from the old to the new array, and set all newly-allocated
15 * words to 0. Return the new, larger array, which can be substituted
16 * for the old one. The new array is larger than the old by about 50%.
18 static inline uint32_t*
19 bitsetRealloc(uint32_t& sz, uint32_t* words, const char *errmsg = NULL) {
22 sz += (sz >> 1) + 31; // Add 50% more elements, plus a bit
23 sz &= ~31; // Make sure it's 32-aligned
25 sz = 1024; // Start off at 1024 bits to avoid many expansions
28 assert_eq(0, (sz & 31));
31 newwords = new uint32_t[sz >> 5 /* convert to words */];
32 } catch(std::bad_alloc& ba) {
34 // Output given error message
40 // Move old values into new array
41 memcpy(newwords, words, oldsz >> 3 /* convert to bytes */);
43 // Initialize all new words to 0
44 memset(newwords + (oldsz >> 5 /*convert to words*/), 0,
45 (sz - oldsz) >> 3 /* convert to bytes */);
46 return newwords; // return new array
50 * A simple synchronized bitset class.
56 * Allocate enough words to accommodate 'sz' bits. Output the given
57 * error message and quit if allocation fails.
59 SyncBitset(uint32_t sz, const char *errmsg = NULL) : _errmsg(errmsg) {
61 uint32_t nwords = (sz >> 5)+1; // divide by 32 and add 1
63 _words = new uint32_t[nwords];
64 } catch(std::bad_alloc& ba) {
70 assert(_words != NULL);
71 memset(_words, 0, nwords * 4 /* words to bytes */);
72 _sz = nwords << 5 /* words to bits */;
76 * Free memory for words.
83 * Test whether the given bit is set in an unsynchronized manner.
85 bool testUnsync(uint32_t i) {
87 return ((_words[i >> 5] >> (i & 0x1f)) & 1) != 0;
93 * Test whether the given bit is set in a synchronized manner.
95 bool test(uint32_t i) {
104 * Set a bit in the vector that hasn't been set before. Assert if
105 * it has been set. Uses synchronization.
107 void set(uint32_t i) {
110 // Slow path: bitset needs to be expanded before the
111 // specified bit can be set
112 ASSERT_ONLY(uint32_t oldsz = _sz);
114 assert_gt(_sz, oldsz);
118 assert(((_words[i >> 5] >> (i & 0x1f)) & 1) == 0);
119 _words[i >> 5] |= (1 << (i & 0x1f));
120 assert(((_words[i >> 5] >> (i & 0x1f)) & 1) == 1);
125 * Set a bit in the vector that might have already been set. Uses
128 void setOver(uint32_t i) {
131 // Slow path: bitset needs to be expanded before the
132 // specified bit can be set
133 ASSERT_ONLY(uint32_t oldsz = _sz);
135 assert_gt(_sz, oldsz);
139 _words[i >> 5] |= (1 << (i & 0x1f));
140 assert(((_words[i >> 5] >> (i & 0x1f)) & 1) == 1);
148 * Expand the size of the _words array by 50% to accommodate more
152 uint32_t *newwords = bitsetRealloc(_sz, _words, _errmsg);
153 delete[] _words; // delete old array
154 _words = newwords; // install new array
157 const char *_errmsg; // error message if an allocation fails
158 uint32_t _sz; // size as # of bits
159 MUTEX_T _lock; // mutex
160 uint32_t *_words; // storage
164 * A simple unsynchronized bitset class.
169 Bitset(uint32_t sz, const char *errmsg = NULL) : _errmsg(errmsg) {
170 uint32_t nwords = (sz >> 5)+1;
172 _words = new uint32_t[nwords];
173 } catch(std::bad_alloc& ba) {
174 if(_errmsg != NULL) {
175 std::cerr << _errmsg;
179 assert(_words != NULL);
180 memset(_words, 0, nwords * 4);
185 Bitset(const Bitset& o) : _words(NULL) {
194 * Test whether the given bit is set.
196 bool test(uint32_t i) const {
199 ret = ((_words[i >> 5] >> (i & 0x1f)) & 1) != 0;
205 * Set a bit in the vector that hasn't been set before. Assert if
208 void set(uint32_t i) {
210 // Slow path: bitset needs to be expanded before the
211 // specified bit can be set
212 ASSERT_ONLY(uint32_t oldsz = _sz);
214 assert_gt(_sz, oldsz);
217 assert(((_words[i >> 5] >> (i & 0x1f)) & 1) == 0);
219 _words[i >> 5] |= (1 << (i & 0x1f));
220 assert(((_words[i >> 5] >> (i & 0x1f)) & 1) == 1);
224 * Set a bit in the vector that might have already been set.
226 void setOver(uint32_t i) {
228 // Slow path: bitset needs to be expanded before the
229 // specified bit can be set
230 ASSERT_ONLY(uint32_t oldsz = _sz);
232 assert_gt(_sz, oldsz);
235 if(((_words[i >> 5] >> (i & 0x1f)) & 1) == 0) _cnt++;
236 _words[i >> 5] |= (1 << (i & 0x1f));
237 assert(((_words[i >> 5] >> (i & 0x1f)) & 1) == 1);
241 * Unset all entries. Don't adjust size.
244 for(size_t i = 0; i < ((_sz+31)>>5); i++) {
251 * Return the number of set bits.
253 uint32_t count() const {
258 * Return true iff no bits are set.
265 * Deep copy from given Bitset to this one.
267 Bitset& operator=(const Bitset& o) {
271 if(_words != NULL) delete[] _words;
272 _words = new uint32_t[(_sz+31)>>5];
273 for(size_t i = 0; i < (_sz+31)>>5; i++) {
274 _words[i] = o._words[i];
282 * Expand the size of the _words array by 50% to accommodate more
286 uint32_t *newwords = bitsetRealloc(_sz, _words, _errmsg);
287 delete[] _words; // delete old array
288 _words = newwords; // install new array
291 uint32_t _cnt; // number of set bits
292 const char *_errmsg; // error message if an allocation fails
293 uint32_t _sz; // size as # of bits
294 uint32_t *_words; // storage
298 * A simple fixed-length unsynchronized bitset class.
304 FixedBitset() : _cnt(0), _size(0) {
305 memset(_words, 0, ((LEN>>5)+1) * 4);
312 memset(_words, 0, ((LEN>>5)+1) * 4);
316 * Return true iff the bit at offset i has been set.
318 bool test(uint32_t i) const {
321 ret = ((_words[i >> 5] >> (i & 0x1f)) & 1) != 0;
326 * Set the bit at offset i. Assert if the bit was already set.
328 void set(uint32_t i) {
331 assert(((_words[i >> 5] >> (i & 0x1f)) & 1) == 0);
332 _words[i >> 5] |= (1 << (i & 0x1f));
337 assert(((_words[i >> 5] >> (i & 0x1f)) & 1) == 1);
341 * Set the bit at offset i. Do not assert if the bit was already
344 void setOver(uint32_t i) {
347 _words[i >> 5] |= (1 << (i & 0x1f));
352 assert(((_words[i >> 5] >> (i & 0x1f)) & 1) == 1);
355 uint32_t count() const { return _cnt; }
356 uint32_t size() const { return _size; }
359 * Return true iff this FixedBitset has the same bits set as
360 * FixedBitset 'that'.
362 bool operator== (const FixedBitset<LEN>& that) const {
363 for(uint32_t i = 0; i < (LEN>>5)+1; i++) {
364 if(_words[i] != that._words[i]) {
372 * Return true iff this FixedBitset does not have the same bits set
373 * as FixedBitset 'that'.
375 bool operator!= (const FixedBitset<LEN>& that) const {
376 for(uint32_t i = 0; i < (LEN>>5)+1; i++) {
377 if(_words[i] != that._words[i]) {
385 * Return a string-ized version of this FixedBitset.
387 std::string str() const {
388 std::ostringstream oss;
389 for(int i = (int)size()-1; i >= 0; i--) {
390 oss << (test(i)? "1" : "0");
398 uint32_t _words[(LEN>>5)+1]; // storage
402 * A simple fixed-length unsynchronized bitset class.
407 FixedBitset2(uint32_t len) : len_(len), _cnt(0), _size(0) {
408 _words = new uint32_t[((len_ >> 5)+1)];
409 memset(_words, 0, ((len_ >> 5)+1) * 4);
412 ~FixedBitset2() { delete[] _words; }
418 memset(_words, 0, ((len_ >> 5)+1) * 4);
424 * Return true iff the bit at offset i has been set.
426 bool test(uint32_t i) const {
429 ret = ((_words[i >> 5] >> (i & 0x1f)) & 1) != 0;
434 * Set the bit at offset i. Assert if the bit was already set.
436 void set(uint32_t i) {
439 assert(((_words[i >> 5] >> (i & 0x1f)) & 1) == 0);
440 _words[i >> 5] |= (1 << (i & 0x1f));
445 assert(((_words[i >> 5] >> (i & 0x1f)) & 1) == 1);
449 * Clear the bit at offset i. Assert if the bit was not already set.
451 void clear(uint32_t i) {
454 assert(((_words[i >> 5] >> (i & 0x1f)) & 1) == 1);
455 _words[i >> 5] &= ~(1 << (i & 0x1f));
460 assert(((_words[i >> 5] >> (i & 0x1f)) & 1) == 0);
464 * Set the bit at offset i. Do not assert if the bit was already
467 void setOver(uint32_t i) {
470 if(((_words[i >> 5] >> (i & 0x1f)) & 1) == 0) {
471 _words[i >> 5] |= (1 << (i & 0x1f));
477 assert(((_words[i >> 5] >> (i & 0x1f)) & 1) == 1);
480 uint32_t count() const { return _cnt; }
481 uint32_t size() const { return _size; }
484 * Return true iff this FixedBitset has the same bits set as
485 * FixedBitset 'that'.
487 bool operator== (const FixedBitset2& that) const {
488 for(uint32_t i = 0; i < (len_>>5)+1; i++) {
489 if(_words[i] != that._words[i]) {
497 * Return true iff this FixedBitset does not have the same bits set
498 * as FixedBitset 'that'.
500 bool operator!= (const FixedBitset2& that) const {
501 for(uint32_t i = 0; i < (len_>>5)+1; i++) {
502 if(_words[i] != that._words[i]) {
510 * Return a string-ized version of this FixedBitset.
512 std::string str() const {
513 std::ostringstream oss;
514 for(int i = (int)size()-1; i >= 0; i--) {
515 oss << (test(i)? "1" : "0");
524 uint32_t *_words; // storage
527 #endif /* BITSET_H_ */