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_ */