include/llvm/ADT/SparseBitVector.h

   1 //===- llvm/ADT/SparseBitVector.h - Efficient Sparse BitVector -*- C++ -*- ===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Daniel Berlin and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines the SparseBitVector class.  See the doxygen comment for
  11 // SparseBitVector for more details on the algorithm used.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef LLVM_ADT_SPARSEBITVECTOR_H
  16 #define LLVM_ADT_SPARSEBITVECTOR_H
  17
  18 #include <cassert>
  19 #include <cstring>
  20 #include <list>
  21 #include <algorithm>
  22 #include "llvm/Support/DataTypes.h"
  23 #include "llvm/ADT/STLExtras.h"
  24 #include "llvm/Support/MathExtras.h"
  25
  26 namespace llvm {
  27
  28 /// SparseBitVector is an implementation of a bitvector that is sparse by only
  29 /// storing the elements that have non-zero bits set.  In order to make this
  30 /// fast for the most common cases, SparseBitVector is implemented as a linked
  31 /// list of SparseBitVectorElements.  We maintain a pointer to the last
  32 /// SparseBitVectorElement accessed (in the form of a list iterator), in order
  33 /// to make multiple in-order test/set constant time after the first one is
  34 /// executed.  Note that using vectors to store SparseBitVectorElement's does
  35 /// not work out very well because it causes insertion in the middle to take
  36 /// enormous amounts of time with a large amount of bits.  Other structures that
  37 /// have better worst cases for insertion in the middle (various balanced trees,
  38 /// etc) do not perform as well in practice as a linked list with this iterator
  39 /// kept up to date.  They are also significantly more memory intensive.
  40
  41
  42 template <unsigned ElementSize = 128>
  43 struct SparseBitVectorElement {
  44 public:
  45   typedef unsigned long BitWord;
  46   enum {
  47     BITWORD_SIZE = sizeof(BitWord) * 8,
  48     BITWORDS_PER_ELEMENT = (ElementSize + BITWORD_SIZE - 1) / BITWORD_SIZE,
  49     BITS_PER_ELEMENT = ElementSize
  50   };
  51 private:
  52   // Index of Element in terms of where first bit starts.
  53   unsigned ElementIndex;
  54   BitWord Bits[BITWORDS_PER_ELEMENT];
  55   SparseBitVectorElement();
  56 public:
  57   explicit SparseBitVectorElement(unsigned Idx) {
  58     ElementIndex = Idx;
  59     memset(&Bits[0], 0, sizeof (BitWord) * BITWORDS_PER_ELEMENT);
  60   }
  61
  62   ~SparseBitVectorElement() {
  63   }
  64
  65   // Copy ctor.
  66   SparseBitVectorElement(const SparseBitVectorElement &RHS) {
  67     ElementIndex = RHS.ElementIndex;
  68     std::copy(&RHS.Bits[0], &RHS.Bits[BITWORDS_PER_ELEMENT], Bits);
  69   }
  70
  71   // Comparison.
  72   bool operator==(const SparseBitVectorElement &RHS) const {
  73     if (ElementIndex != RHS.ElementIndex)
  74       return false;
  75     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
  76       if (Bits[i] != RHS.Bits[i])
  77         return false;
  78     return true;
  79   }
  80
  81   bool operator!=(const SparseBitVectorElement &RHS) const {
  82     return !(*this == RHS);
  83   }
  84
  85   // Return the bits that make up word Idx in our element.
  86   BitWord word(unsigned Idx) const {
  87     assert (Idx < BITWORDS_PER_ELEMENT);
  88     return Bits[Idx];
  89   }
  90
  91   unsigned index() const {
  92     return ElementIndex;
  93   }
  94
  95   bool empty() const {
  96     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
  97       if (Bits[i])
  98         return false;
  99     return true;
 100   }
 101
 102   void set(unsigned Idx) {
 103     Bits[Idx / BITWORD_SIZE] |= 1L << (Idx % BITWORD_SIZE);
 104   }
 105
 106   bool test_and_set (unsigned Idx) {
 107     bool old = test(Idx);
 108     if (!old)
 109       set(Idx);
 110     return !old;
 111   }
 112
 113   void reset(unsigned Idx) {
 114     Bits[Idx / BITWORD_SIZE] &= ~(1L << (Idx % BITWORD_SIZE));
 115   }
 116
 117   bool test(unsigned Idx) const {
 118     return Bits[Idx / BITWORD_SIZE] & (1L << (Idx % BITWORD_SIZE));
 119   }
 120
 121   unsigned count() const {
 122     unsigned NumBits = 0;
 123     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
 124       if (sizeof(BitWord) == 4)
 125         NumBits += CountPopulation_32(Bits[i]);
 126       else if (sizeof(BitWord) == 8)
 127         NumBits += CountPopulation_64(Bits[i]);
 128       else
 129         assert(0 && "Unsupported!");
 130     return NumBits;
 131   }
 132
 133   /// find_first - Returns the index of the first set bit.
 134   int find_first() const {
 135     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
 136       if (Bits[i] != 0) {
 137         if (sizeof(BitWord) == 4)
 138           return i * BITWORD_SIZE + CountTrailingZeros_32(Bits[i]);
 139         else if (sizeof(BitWord) == 8)
 140           return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]);
 141         else
 142           assert(0 && "Unsupported!");
 143       }
 144     assert(0 && "Illegal empty element");
 145   }
 146
 147   /// find_next - Returns the index of the next set bit following the
 148   /// "Prev" bit. Returns -1 if the next set bit is not found.
 149   int find_next(unsigned Prev) const {
 150     ++Prev;
 151     if (Prev >= BITS_PER_ELEMENT)
 152       return -1;
 153
 154     unsigned WordPos = Prev / BITWORD_SIZE;
 155     unsigned BitPos = Prev % BITWORD_SIZE;
 156     BitWord Copy = Bits[WordPos];
 157     assert (WordPos <= BITWORDS_PER_ELEMENT
 158             && "Word Position outside of element");
 159
 160     // Mask off previous bits.
 161     Copy &= ~0L << BitPos;
 162
 163     if (Copy != 0) {
 164       if (sizeof(BitWord) == 4)
 165         return WordPos * BITWORD_SIZE + CountTrailingZeros_32(Copy);
 166       else if (sizeof(BitWord) == 8)
 167         return WordPos * BITWORD_SIZE + CountTrailingZeros_64(Copy);
 168       else
 169         assert(0 && "Unsupported!");
 170     }
 171
 172     // Check subsequent words.
 173     for (unsigned i = WordPos+1; i < BITWORDS_PER_ELEMENT; ++i)
 174       if (Bits[i] != 0) {
 175         if (sizeof(BitWord) == 4)
 176           return i * BITWORD_SIZE + CountTrailingZeros_32(Bits[i]);
 177         else if (sizeof(BitWord) == 8)
 178           return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]);
 179         else
 180           assert(0 && "Unsupported!");
 181       }
 182     return -1;
 183   }
 184
 185   // Union this element with RHS and return true if this one changed.
 186   bool unionWith(const SparseBitVectorElement &RHS) {
 187     bool changed = false;
 188     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
 189       BitWord old = changed ? 0 : Bits[i];
 190
 191       Bits[i] |= RHS.Bits[i];
 192       if (old != Bits[i])
 193         changed = true;
 194     }
 195     return changed;
 196   }
 197
 198   // Intersect this Element with RHS and return true if this one changed.
 199   // BecameZero is set to true if this element became all-zero bits.
 200   bool intersectWith(const SparseBitVectorElement &RHS,
 201                      bool &BecameZero) {
 202     bool changed = false;
 203     bool allzero = true;
 204
 205     BecameZero = false;
 206     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
 207       BitWord old = changed ? 0 : Bits[i];
 208
 209       Bits[i] &= RHS.Bits[i];
 210       if (Bits[i] != 0)
 211         allzero = false;
 212
 213       if (old != Bits[i])
 214         changed = true;
 215     }
 216     BecameZero = !allzero;
 217     return changed;
 218   }
 219 };
 220
 221 template <unsigned ElementSize = 128>
 222 class SparseBitVector {
 223   typedef std::list<SparseBitVectorElement<ElementSize> *> ElementList;
 224   typedef typename ElementList::iterator ElementListIter;
 225   typedef typename ElementList::const_iterator ElementListConstIter;
 226   enum {
 227     BITWORD_SIZE = SparseBitVectorElement<ElementSize>::BITWORD_SIZE
 228   };
 229
 230   // Pointer to our current Element.
 231   ElementListIter CurrElementIter;
 232   ElementList Elements;
 233
 234   // This is like std::lower_bound, except we do linear searching from the
 235   // current position.
 236   ElementListIter FindLowerBound(unsigned ElementIndex) {
 237
 238     if (Elements.empty()) {
 239       CurrElementIter = Elements.begin();
 240       return Elements.begin();
 241     }
 242
 243     // Make sure our current iterator is valid.
 244     if (CurrElementIter == Elements.end())
 245       --CurrElementIter;
 246
 247     // Search from our current iterator, either backwards or forwards,
 248     // depending on what element we are looking for.
 249     ElementListIter ElementIter = CurrElementIter;
 250     if ((*CurrElementIter)->index() == ElementIndex) {
 251       return ElementIter;
 252     } else if ((*CurrElementIter)->index() > ElementIndex) {
 253       while (ElementIter != Elements.begin()
 254              && (*ElementIter)->index() > ElementIndex)
 255         --ElementIter;
 256     } else {
 257       while (ElementIter != Elements.end() &&
 258              (*ElementIter)->index() <= ElementIndex)
 259         ++ElementIter;
 260       --ElementIter;
 261     }
 262     CurrElementIter = ElementIter;
 263     return ElementIter;
 264   }
 265
 266   // Iterator to walk set bits in the bitmap.  This iterator is a lot uglier
 267   // than it would be, in order to be efficient.
 268   struct SparseBitVectorIterator {
 269   private:
 270     bool AtEnd;
 271
 272     SparseBitVector<ElementSize> &BitVector;
 273
 274     // Current element inside of bitmap.
 275     ElementListConstIter Iter;
 276
 277     // Current bit number inside of our bitmap.
 278     unsigned BitNumber;
 279
 280     // Current word number inside of our element.
 281     unsigned WordNumber;
 282
 283     // Current bits from the element.
 284     typename SparseBitVectorElement<ElementSize>::BitWord Bits;
 285
 286     // Move our iterator to the first non-zero bit in the bitmap.
 287     void AdvanceToFirstNonZero() {
 288       if (AtEnd)
 289         return;
 290       if (BitVector.Elements.empty()) {
 291         AtEnd = true;
 292         return;
 293       }
 294       Iter = BitVector.Elements.begin();
 295       BitNumber = (*Iter)->index() * ElementSize;
 296       unsigned BitPos = (*Iter)->find_first();
 297       BitNumber += BitPos;
 298       WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;
 299       Bits = (*Iter)->word(WordNumber);
 300       Bits >>= BitPos % BITWORD_SIZE;
 301     }
 302
 303     // Move our iterator to the next non-zero bit.
 304     void AdvanceToNextNonZero() {
 305       if (AtEnd)
 306         return;
 307
 308       while (Bits && !(Bits & 1)) {
 309         Bits >>= 1;
 310         BitNumber += 1;
 311       }
 312
 313       // See if we ran out of Bits in this word.
 314       if (!Bits) {
 315         int NextSetBitNumber = (*Iter)->find_next(BitNumber % ElementSize) ;
 316         // If we ran out of set bits in this element, move to next element.
 317         if (NextSetBitNumber == -1 || (BitNumber % ElementSize == 0)) {
 318           Iter++;
 319           WordNumber = 0;
 320
 321           // We may run out of elements in the bitmap.
 322           if (Iter == BitVector.Elements.end()) {
 323             AtEnd = true;
 324             return;
 325           }
 326           // Set up for next non zero word in bitmap.
 327           BitNumber = (*Iter)->index() * ElementSize;
 328           NextSetBitNumber = (*Iter)->find_first();
 329           BitNumber += NextSetBitNumber;
 330           WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;
 331           Bits = (*Iter)->word(WordNumber);
 332           Bits >>= NextSetBitNumber % BITWORD_SIZE;
 333         } else {
 334           WordNumber = (NextSetBitNumber % ElementSize) / BITWORD_SIZE;
 335           Bits = (*Iter)->word(WordNumber);
 336           Bits >>= NextSetBitNumber % BITWORD_SIZE;
 337         }
 338       }
 339     }
 340   public:
 341     // Preincrement.
 342     inline SparseBitVectorIterator& operator++() {
 343       BitNumber++;
 344       Bits >>= 1;
 345       AdvanceToNextNonZero();
 346       return *this;
 347     }
 348
 349     // Postincrement.
 350     inline SparseBitVectorIterator operator++(int) {
 351       SparseBitVectorIterator tmp = *this;
 352       ++*this;
 353       return tmp;
 354     }
 355
 356     // Return the current set bit number.
 357     unsigned operator*() const {
 358       return BitNumber;
 359     }
 360
 361     bool operator==(const SparseBitVectorIterator &RHS) const {
 362       // If they are both at the end, ignore the rest of the fields.
 363       if (AtEnd == RHS.AtEnd)
 364         return true;
 365       // Otherwise they are the same if they have the same bit number and
 366       // bitmap.
 367       return AtEnd == RHS.AtEnd && RHS.BitNumber == BitNumber;
 368     }
 369     bool operator!=(const SparseBitVectorIterator &RHS) const {
 370       return !(*this == RHS);
 371     }
 372
 373     explicit SparseBitVectorIterator(SparseBitVector<ElementSize> &RHS,
 374                                      bool end = false):BitVector(RHS) {
 375       Iter = BitVector.Elements.begin();
 376       BitNumber = 0;
 377       Bits = 0;
 378       WordNumber = ~0;
 379       AtEnd = end;
 380       AdvanceToFirstNonZero();
 381     }
 382   };
 383 public:
 384   typedef SparseBitVectorIterator iterator;
 385   typedef const SparseBitVectorIterator const_iterator;
 386
 387   SparseBitVector () {
 388     CurrElementIter = Elements.begin ();
 389   }
 390
 391   ~SparseBitVector() {
 392     for_each(Elements.begin(), Elements.end(),
 393              deleter<SparseBitVectorElement<ElementSize> >);
 394   }
 395
 396   // SparseBitVector copy ctor.
 397   SparseBitVector(const SparseBitVector &RHS) {
 398     ElementListConstIter ElementIter = RHS.Elements.begin();
 399     while (ElementIter != RHS.Elements.end()) {
 400       SparseBitVectorElement<ElementSize> *ElementCopy;
 401       ElementCopy = new SparseBitVectorElement<ElementSize>(*(*ElementIter));
 402       Elements.push_back(ElementCopy);
 403     }
 404
 405     CurrElementIter = Elements.begin ();
 406   }
 407
 408   // Test, Reset, and Set a bit in the bitmap.
 409   bool test(unsigned Idx) {
 410     if (Elements.empty())
 411       return false;
 412
 413     unsigned ElementIndex = Idx / ElementSize;
 414     ElementListIter ElementIter = FindLowerBound(ElementIndex);
 415
 416     // If we can't find an element that is supposed to contain this bit, there
 417     // is nothing more to do.
 418     if (ElementIter == Elements.end() ||
 419         (*ElementIter)->index() != ElementIndex)
 420       return false;
 421     return (*ElementIter)->test(Idx % ElementSize);
 422   }
 423
 424   void reset(unsigned Idx) {
 425     if (Elements.empty())
 426       return;
 427
 428     unsigned ElementIndex = Idx / ElementSize;
 429     ElementListIter ElementIter = FindLowerBound(ElementIndex);
 430
 431     // If we can't find an element that is supposed to contain this bit, there
 432     // is nothing more to do.
 433     if (ElementIter == Elements.end() ||
 434         (*ElementIter)->index() != ElementIndex)
 435       return;
 436     (*ElementIter)->reset(Idx % ElementSize);
 437
 438     // When the element is zeroed out, delete it.
 439     if ((*ElementIter)->empty()) {
 440       delete (*ElementIter);
 441       ++CurrElementIter;
 442       Elements.erase(ElementIter);
 443     }
 444   }
 445
 446   void set(unsigned Idx) {
 447     SparseBitVectorElement<ElementSize> *Element;
 448     unsigned ElementIndex = Idx / ElementSize;
 449
 450     if (Elements.empty()) {
 451       Element = new SparseBitVectorElement<ElementSize>(ElementIndex);
 452       Elements.push_back(Element);
 453     } else {
 454       ElementListIter ElementIter = FindLowerBound(ElementIndex);
 455
 456       if (ElementIter != Elements.end() &&
 457           (*ElementIter)->index() == ElementIndex)
 458         Element = *ElementIter;
 459       else {
 460         Element = new SparseBitVectorElement<ElementSize>(ElementIndex);
 461         // Insert does insert before, and lower bound gives the one before.
 462         Elements.insert(++ElementIter, Element);
 463       }
 464     }
 465     Element->set(Idx % ElementSize);
 466   }
 467
 468   // Union our bitmap with the RHS and return true if we changed.
 469   bool operator|=(const SparseBitVector &RHS) {
 470     bool changed = false;
 471     ElementListIter Iter1 = Elements.begin();
 472     ElementListConstIter Iter2 = RHS.Elements.begin();
 473
 474     // IE They may both be end
 475     if (Iter1 == Iter2)
 476       return false;
 477
 478     // See if the first bitmap element is the same in both.  This is only
 479     // possible if they are the same bitmap.
 480     if (Iter1 != Elements.end() && Iter2 != RHS.Elements.end())
 481       if (*Iter1 == *Iter2)
 482         return false;
 483
 484     while (Iter2 != RHS.Elements.end()) {
 485       if (Iter1 == Elements.end() || (*Iter1)->index() > (*Iter2)->index()) {
 486         SparseBitVectorElement<ElementSize> *NewElem;
 487
 488         NewElem = new SparseBitVectorElement<ElementSize>(*(*Iter2));
 489         Elements.insert(Iter1, NewElem);
 490         Iter2++;
 491         changed = true;
 492       } else if ((*Iter1)->index() == (*Iter2)->index()) {
 493         changed |= (*Iter1)->unionWith(*(*Iter2));
 494         Iter1++;
 495         Iter2++;
 496       } else {
 497         Iter1++;
 498       }
 499     }
 500     CurrElementIter = Elements.begin();
 501     return changed;
 502   }
 503
 504   // Intersect our bitmap with the RHS and return true if ours changed.
 505   bool operator&=(const SparseBitVector &RHS) {
 506     bool changed = false;
 507     ElementListIter Iter1 = Elements.begin();
 508     ElementListConstIter Iter2 = RHS.Elements.begin();
 509
 510     // IE They may both be end.
 511     if (Iter1 == Iter2)
 512       return false;
 513
 514     // See if the first bitmap element is the same in both.  This is only
 515     // possible if they are the same bitmap.
 516     if (Iter1 != Elements.end() && Iter2 != RHS.Elements.end())
 517       if (*Iter1 == *Iter2)
 518         return false;
 519
 520     // Loop through, intersecting as we go, erasing elements when necessary.
 521     while (Iter2 != RHS.Elements.end()) {
 522       if (Iter1 == Elements.end())
 523         return changed;
 524
 525       if ((*Iter1)->index() > (*Iter2)->index()) {
 526         Iter2++;
 527       } else if ((*Iter1)->index() == (*Iter2)->index()) {
 528         bool BecameZero;
 529         changed |= (*Iter1)->intersectWith(*(*Iter2), BecameZero);
 530         if (BecameZero) {
 531           ElementListIter IterTmp = Iter1;
 532           delete *IterTmp;
 533           Elements.erase(IterTmp);
 534           Iter1++;
 535         } else {
 536           Iter1++;
 537         }
 538         Iter2++;
 539       } else {
 540         ElementListIter IterTmp = Iter1;
 541         Iter1++;
 542         delete *IterTmp;
 543         Elements.erase(IterTmp);
 544       }
 545     }
 546     CurrElementIter = Elements.begin();
 547     return changed;
 548   }
 549
 550   iterator begin() const {
 551     return iterator(*this);
 552   }
 553
 554   iterator end() const {
 555     return iterator(*this, ~0);
 556   }
 557 };
 558 }
 559
 560 #endif