Imported Debian patch 0.12.7-3
[bowtie.git] / bitset.h
1 #ifndef BITSET_H_
2 #define BITSET_H_
3
4 #include <iostream>
5 #include <sstream>
6 #include <stdint.h>
7 #include <string.h>
8 #include <stdexcept>
9 #include "assert_helpers.h"
10 #include "threading.h"
11
12 /**
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%.
17  */
18 static inline uint32_t*
19 bitsetRealloc(uint32_t& sz, uint32_t* words, const char *errmsg = NULL) {
20         uint32_t oldsz = sz;
21         if(sz > 0) {
22                 sz += (sz >> 1) + 31; // Add 50% more elements, plus a bit
23                 sz &= ~31;            // Make sure it's 32-aligned
24         } else {
25                 sz = 1024; // Start off at 1024 bits to avoid many expansions
26         }
27         assert_gt(sz, oldsz);
28         assert_eq(0, (sz & 31));
29         uint32_t *newwords;
30         try {
31                 newwords = new uint32_t[sz >> 5 /* convert to words */];
32         } catch(std::bad_alloc& ba) {
33                 if(errmsg != NULL) {
34                         // Output given error message
35                         std::cerr << errmsg;
36                 }
37                 throw 1;
38         }
39         if(oldsz > 0) {
40                 // Move old values into new array
41                 memcpy(newwords, words, oldsz >> 3 /* convert to bytes */);
42         }
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
47 }
48
49 /**
50  * A simple synchronized bitset class.
51  */
52 class SyncBitset {
53
54 public:
55         /**
56          * Allocate enough words to accommodate 'sz' bits.  Output the given
57          * error message and quit if allocation fails.
58          */
59         SyncBitset(uint32_t sz, const char *errmsg = NULL) : _errmsg(errmsg) {
60                 MUTEX_INIT(_lock);
61                 uint32_t nwords = (sz >> 5)+1; // divide by 32 and add 1
62                 try {
63                         _words = new uint32_t[nwords];
64                 } catch(std::bad_alloc& ba) {
65                         if(_errmsg != NULL) {
66                                 std::cerr << _errmsg;
67                         }
68                         throw 1;
69                 }
70                 assert(_words != NULL);
71                 memset(_words, 0, nwords * 4 /* words to bytes */);
72                 _sz = nwords << 5 /* words to bits */;
73         }
74
75         /**
76          * Free memory for words.
77          */
78         ~SyncBitset() {
79                 delete[] _words;
80         }
81
82         /**
83          * Test whether the given bit is set in an unsynchronized manner.
84          */
85         bool testUnsync(uint32_t i) {
86                 if(i < _sz) {
87                         return ((_words[i >> 5] >> (i & 0x1f)) & 1) != 0;
88                 }
89                 return false;
90         }
91
92         /**
93          * Test whether the given bit is set in a synchronized manner.
94          */
95         bool test(uint32_t i) {
96                 bool ret;
97                 MUTEX_LOCK(_lock);
98                 ret = testUnsync(i);
99                 MUTEX_UNLOCK(_lock);
100                 return ret;
101         }
102
103         /**
104          * Set a bit in the vector that hasn't been set before.  Assert if
105          * it has been set.  Uses synchronization.
106          */
107         void set(uint32_t i) {
108                 MUTEX_LOCK(_lock);
109                 while(i >= _sz) {
110                         // Slow path: bitset needs to be expanded before the
111                         // specified bit can be set
112                         ASSERT_ONLY(uint32_t oldsz = _sz);
113                         expand();
114                         assert_gt(_sz, oldsz);
115                 }
116                 // Fast path
117                 assert_lt(i, _sz);
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);
121                 MUTEX_UNLOCK(_lock);
122         }
123
124         /**
125          * Set a bit in the vector that might have already been set.  Uses
126          * synchronization.
127          */
128         void setOver(uint32_t i) {
129                 MUTEX_LOCK(_lock);
130                 while(i >= _sz) {
131                         // Slow path: bitset needs to be expanded before the
132                         // specified bit can be set
133                         ASSERT_ONLY(uint32_t oldsz = _sz);
134                         expand();
135                         assert_gt(_sz, oldsz);
136                 }
137                 // Fast path
138                 assert_lt(i, _sz);
139                 _words[i >> 5] |= (1 << (i & 0x1f));
140                 assert(((_words[i >> 5] >> (i & 0x1f)) & 1) == 1);
141                 MUTEX_UNLOCK(_lock);
142         }
143
144
145 private:
146
147         /**
148          * Expand the size of the _words array by 50% to accommodate more
149          * bits.
150          */
151         void expand() {
152                 uint32_t *newwords = bitsetRealloc(_sz, _words, _errmsg);
153                 delete[] _words;   // delete old array
154                 _words = newwords; // install new array
155         }
156
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
161 };
162
163 /**
164  * A simple unsynchronized bitset class.
165  */
166 class Bitset {
167
168 public:
169         Bitset(uint32_t sz, const char *errmsg = NULL) : _errmsg(errmsg) {
170                 uint32_t nwords = (sz >> 5)+1;
171                 try {
172                         _words = new uint32_t[nwords];
173                 } catch(std::bad_alloc& ba) {
174                         if(_errmsg != NULL) {
175                                 std::cerr << _errmsg;
176                         }
177                         throw 1;
178                 }
179                 assert(_words != NULL);
180                 memset(_words, 0, nwords * 4);
181                 _sz = nwords << 5;
182                 _cnt = 0;
183         }
184
185         Bitset(const Bitset& o) : _words(NULL) {
186                 this->operator=(o);
187         }
188
189         ~Bitset() {
190                 delete[] _words;
191         }
192
193         /**
194          * Test whether the given bit is set.
195          */
196         bool test(uint32_t i) const {
197                 bool ret = false;
198                 if(i < _sz) {
199                         ret = ((_words[i >> 5] >> (i & 0x1f)) & 1) != 0;
200                 }
201                 return ret;
202         }
203
204         /**
205          * Set a bit in the vector that hasn't been set before.  Assert if
206          * it has been set.
207          */
208         void set(uint32_t i) {
209                 while(i >= _sz) {
210                         // Slow path: bitset needs to be expanded before the
211                         // specified bit can be set
212                         ASSERT_ONLY(uint32_t oldsz = _sz);
213                         expand();
214                         assert_gt(_sz, oldsz);
215                 }
216                 // Fast path
217                 assert(((_words[i >> 5] >> (i & 0x1f)) & 1) == 0);
218                 _cnt++;
219                 _words[i >> 5] |= (1 << (i & 0x1f));
220                 assert(((_words[i >> 5] >> (i & 0x1f)) & 1) == 1);
221         }
222
223         /**
224          * Set a bit in the vector that might have already been set.
225          */
226         void setOver(uint32_t i) {
227                 while(i >= _sz) {
228                         // Slow path: bitset needs to be expanded before the
229                         // specified bit can be set
230                         ASSERT_ONLY(uint32_t oldsz = _sz);
231                         expand();
232                         assert_gt(_sz, oldsz);
233                 }
234                 // Fast path
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);
238         }
239
240         /**
241          * Unset all entries.  Don't adjust size.
242          */
243         void clear() {
244                 for(size_t i = 0; i < ((_sz+31)>>5); i++) {
245                         _words[i] = 0;
246                 }
247                 _cnt = 0;
248         }
249
250         /**
251          * Return the number of set bits.
252          */
253         uint32_t count() const {
254                 return _cnt;
255         }
256
257         /**
258          * Return true iff no bits are set.
259          */
260         bool empty() const {
261                 return _cnt == 0;
262         }
263
264         /**
265          * Deep copy from given Bitset to this one.
266          */
267         Bitset& operator=(const Bitset& o) {
268                 _errmsg = o._errmsg;
269                 _sz = o._sz;
270                 _cnt = o._cnt;
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];
275                 }
276                 return *this;
277         }
278
279 private:
280
281         /**
282          * Expand the size of the _words array by 50% to accommodate more
283          * bits.
284          */
285         void expand() {
286                 uint32_t *newwords = bitsetRealloc(_sz, _words, _errmsg);
287                 delete[] _words;   // delete old array
288                 _words = newwords; // install new array
289         }
290
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
295 };
296
297 /**
298  * A simple fixed-length unsynchronized bitset class.
299  */
300 template<int LEN>
301 class FixedBitset {
302
303 public:
304         FixedBitset() : _cnt(0), _size(0) {
305                 memset(_words, 0, ((LEN>>5)+1) * 4);
306         }
307
308         /**
309          * Unset all bits.
310          */
311         void clear() {
312                 memset(_words, 0, ((LEN>>5)+1) * 4);
313         }
314
315         /**
316          * Return true iff the bit at offset i has been set.
317          */
318         bool test(uint32_t i) const {
319                 bool ret = false;
320                 assert_lt(i, LEN);
321                 ret = ((_words[i >> 5] >> (i & 0x1f)) & 1) != 0;
322                 return ret;
323         }
324
325         /**
326          * Set the bit at offset i.  Assert if the bit was already set.
327          */
328         void set(uint32_t i) {
329                 // Fast path
330                 assert_lt(i, LEN);
331                 assert(((_words[i >> 5] >> (i & 0x1f)) & 1) == 0);
332                 _words[i >> 5] |= (1 << (i & 0x1f));
333                 _cnt++;
334                 if(i >= _size) {
335                         _size = i+1;
336                 }
337                 assert(((_words[i >> 5] >> (i & 0x1f)) & 1) == 1);
338         }
339
340         /**
341          * Set the bit at offset i.  Do not assert if the bit was already
342          * set.
343          */
344         void setOver(uint32_t i) {
345                 // Fast path
346                 assert_lt(i, LEN);
347                 _words[i >> 5] |= (1 << (i & 0x1f));
348                 _cnt++;
349                 if(i >= _size) {
350                         _size = i+1;
351                 }
352                 assert(((_words[i >> 5] >> (i & 0x1f)) & 1) == 1);
353         }
354
355         uint32_t count() const { return _cnt; }
356         uint32_t size() const  { return _size; }
357
358         /**
359          * Return true iff this FixedBitset has the same bits set as
360          * FixedBitset 'that'.
361          */
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]) {
365                                 return false;
366                         }
367                 }
368                 return true;
369         }
370
371         /**
372          * Return true iff this FixedBitset does not have the same bits set
373          * as FixedBitset 'that'.
374          */
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]) {
378                                 return true;
379                         }
380                 }
381                 return false;
382         }
383
384         /**
385          * Return a string-ized version of this FixedBitset.
386          */
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");
391                 }
392                 return oss.str();
393         }
394
395 private:
396         uint32_t _cnt;
397         uint32_t _size;
398         uint32_t _words[(LEN>>5)+1]; // storage
399 };
400
401 /**
402  * A simple fixed-length unsynchronized bitset class.
403  */
404 class FixedBitset2 {
405
406 public:
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);
410         }
411
412         ~FixedBitset2() { delete[] _words; }
413
414         /**
415          * Unset all bits.
416          */
417         void clear() {
418                 memset(_words, 0, ((len_ >> 5)+1) * 4);
419                 _cnt = 0;
420                 _size = 0;
421         }
422
423         /**
424          * Return true iff the bit at offset i has been set.
425          */
426         bool test(uint32_t i) const {
427                 bool ret = false;
428                 assert_lt(i, len_);
429                 ret = ((_words[i >> 5] >> (i & 0x1f)) & 1) != 0;
430                 return ret;
431         }
432
433         /**
434          * Set the bit at offset i.  Assert if the bit was already set.
435          */
436         void set(uint32_t i) {
437                 // Fast path
438                 assert_lt(i, len_);
439                 assert(((_words[i >> 5] >> (i & 0x1f)) & 1) == 0);
440                 _words[i >> 5] |= (1 << (i & 0x1f));
441                 _cnt++;
442                 if(i >= _size) {
443                         _size = i+1;
444                 }
445                 assert(((_words[i >> 5] >> (i & 0x1f)) & 1) == 1);
446         }
447
448         /**
449          * Clear the bit at offset i.  Assert if the bit was not already set.
450          */
451         void clear(uint32_t i) {
452                 // Fast path
453                 assert_lt(i, len_);
454                 assert(((_words[i >> 5] >> (i & 0x1f)) & 1) == 1);
455                 _words[i >> 5] &= ~(1 << (i & 0x1f));
456                 _cnt--;
457                 if(i >= _size) {
458                         _size = i+1;
459                 }
460                 assert(((_words[i >> 5] >> (i & 0x1f)) & 1) == 0);
461         }
462
463         /**
464          * Set the bit at offset i.  Do not assert if the bit was already
465          * set.
466          */
467         void setOver(uint32_t i) {
468                 // Fast path
469                 assert_lt(i, len_);
470                 if(((_words[i >> 5] >> (i & 0x1f)) & 1) == 0) {
471                         _words[i >> 5] |= (1 << (i & 0x1f));
472                         _cnt++;
473                 }
474                 if(i >= _size) {
475                         _size = i+1;
476                 }
477                 assert(((_words[i >> 5] >> (i & 0x1f)) & 1) == 1);
478         }
479
480         uint32_t count() const { return _cnt; }
481         uint32_t size() const  { return _size; }
482
483         /**
484          * Return true iff this FixedBitset has the same bits set as
485          * FixedBitset 'that'.
486          */
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]) {
490                                 return false;
491                         }
492                 }
493                 return true;
494         }
495
496         /**
497          * Return true iff this FixedBitset does not have the same bits set
498          * as FixedBitset 'that'.
499          */
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]) {
503                                 return true;
504                         }
505                 }
506                 return false;
507         }
508
509         /**
510          * Return a string-ized version of this FixedBitset.
511          */
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");
516                 }
517                 return oss.str();
518         }
519
520 private:
521         const uint32_t len_;
522         uint32_t _cnt;
523         uint32_t _size;
524         uint32_t *_words; // storage
525 };
526
527 #endif /* BITSET_H_ */