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 <algorithm>
  21 #include "llvm/Support/DataTypes.h"
  22 #include "llvm/ADT/STLExtras.h"
  23 #include "llvm/Support/MathExtras.h"
  24 #include "llvm/ADT/ilist"
  25 namespace llvm {
  26
  27 /// SparseBitVector is an implementation of a bitvector that is sparse by only
  28 /// storing the elements that have non-zero bits set.  In order to make this
  29 /// fast for the most common cases, SparseBitVector is implemented as a linked
  30 /// list of SparseBitVectorElements.  We maintain a pointer to the last
  31 /// SparseBitVectorElement accessed (in the form of a list iterator), in order
  32 /// to make multiple in-order test/set constant time after the first one is
  33 /// executed.  Note that using vectors to store SparseBitVectorElement's does
  34 /// not work out very well because it causes insertion in the middle to take
  35 /// enormous amounts of time with a large amount of bits.  Other structures that
  36 /// have better worst cases for insertion in the middle (various balanced trees,
  37 /// etc) do not perform as well in practice as a linked list with this iterator
  38 /// kept up to date.  They are also significantly more memory intensive.
  39
  40
  41 template <unsigned ElementSize = 128>
  42 struct SparseBitVectorElement {
  43 public:
  44   typedef unsigned long BitWord;
  45   enum {
  46     BITWORD_SIZE = sizeof(BitWord) * 8,
  47     BITWORDS_PER_ELEMENT = (ElementSize + BITWORD_SIZE - 1) / BITWORD_SIZE,
  48     BITS_PER_ELEMENT = ElementSize
  49   };
  50
  51   SparseBitVectorElement<ElementSize> *getNext() const {
  52     return Next;
  53   }
  54   SparseBitVectorElement<ElementSize> *getPrev() const {
  55     return Prev;
  56   }
  57
  58   void setNext(SparseBitVectorElement<ElementSize> *RHS) {
  59     Next = RHS;
  60   }
  61   void setPrev(SparseBitVectorElement<ElementSize> *RHS) {
  62     Prev = RHS;
  63   }
  64
  65 private:
  66   SparseBitVectorElement<ElementSize> *Next;
  67   SparseBitVectorElement<ElementSize> *Prev;
  68   // Index of Element in terms of where first bit starts.
  69   unsigned ElementIndex;
  70   BitWord Bits[BITWORDS_PER_ELEMENT];
  71   // Needed for sentinels
  72   SparseBitVectorElement() {
  73     ElementIndex = ~0UL;
  74     memset(&Bits[0], 0, sizeof (BitWord) * BITWORDS_PER_ELEMENT);
  75   }
  76
  77   friend struct ilist_traits<SparseBitVectorElement<ElementSize> >;
  78
  79 public:
  80   explicit SparseBitVectorElement(unsigned Idx) {
  81     ElementIndex = Idx;
  82     memset(&Bits[0], 0, sizeof (BitWord) * BITWORDS_PER_ELEMENT);
  83   }
  84
  85   ~SparseBitVectorElement() {
  86   }
  87
  88   // Copy ctor.
  89   SparseBitVectorElement(const SparseBitVectorElement &RHS) {
  90     ElementIndex = RHS.ElementIndex;
  91     std::copy(&RHS.Bits[0], &RHS.Bits[BITWORDS_PER_ELEMENT], Bits);
  92   }
  93
  94   // Comparison.
  95   bool operator==(const SparseBitVectorElement &RHS) const {
  96     if (ElementIndex != RHS.ElementIndex)
  97       return false;
  98     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
  99       if (Bits[i] != RHS.Bits[i])
 100         return false;
 101     return true;
 102   }
 103
 104   bool operator!=(const SparseBitVectorElement &RHS) const {
 105     return !(*this == RHS);
 106   }
 107
 108   // Return the bits that make up word Idx in our element.
 109   BitWord word(unsigned Idx) const {
 110     assert (Idx < BITWORDS_PER_ELEMENT);
 111     return Bits[Idx];
 112   }
 113
 114   unsigned index() const {
 115     return ElementIndex;
 116   }
 117
 118   bool empty() const {
 119     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
 120       if (Bits[i])
 121         return false;
 122     return true;
 123   }
 124
 125   void set(unsigned Idx) {
 126     Bits[Idx / BITWORD_SIZE] |= 1L << (Idx % BITWORD_SIZE);
 127   }
 128
 129   bool test_and_set (unsigned Idx) {
 130     bool old = test(Idx);
 131     if (!old)
 132       set(Idx);
 133     return !old;
 134   }
 135
 136   void reset(unsigned Idx) {
 137     Bits[Idx / BITWORD_SIZE] &= ~(1L << (Idx % BITWORD_SIZE));
 138   }
 139
 140   bool test(unsigned Idx) const {
 141     return Bits[Idx / BITWORD_SIZE] & (1L << (Idx % BITWORD_SIZE));
 142   }
 143
 144   unsigned count() const {
 145     unsigned NumBits = 0;
 146     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
 147       if (sizeof(BitWord) == 4)
 148         NumBits += CountPopulation_32(Bits[i]);
 149       else if (sizeof(BitWord) == 8)
 150         NumBits += CountPopulation_64(Bits[i]);
 151       else
 152         assert(0 && "Unsupported!");
 153     return NumBits;
 154   }
 155
 156   /// find_first - Returns the index of the first set bit.
 157   int find_first() const {
 158     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
 159       if (Bits[i] != 0) {
 160         if (sizeof(BitWord) == 4)
 161           return i * BITWORD_SIZE + CountTrailingZeros_32(Bits[i]);
 162         else if (sizeof(BitWord) == 8)
 163           return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]);
 164         else
 165           assert(0 && "Unsupported!");
 166       }
 167     assert(0 && "Illegal empty element");
 168   }
 169
 170   /// find_next - Returns the index of the next set bit following the
 171   /// "Prev" bit. Returns -1 if the next set bit is not found.
 172   int find_next(unsigned Prev) const {
 173     ++Prev;
 174     if (Prev >= BITS_PER_ELEMENT)
 175       return -1;
 176
 177     unsigned WordPos = Prev / BITWORD_SIZE;
 178     unsigned BitPos = Prev % BITWORD_SIZE;
 179     BitWord Copy = Bits[WordPos];
 180     assert (WordPos <= BITWORDS_PER_ELEMENT
 181             && "Word Position outside of element");
 182
 183     // Mask off previous bits.
 184     Copy &= ~0L << BitPos;
 185
 186     if (Copy != 0) {
 187       if (sizeof(BitWord) == 4)
 188         return WordPos * BITWORD_SIZE + CountTrailingZeros_32(Copy);
 189       else if (sizeof(BitWord) == 8)
 190         return WordPos * BITWORD_SIZE + CountTrailingZeros_64(Copy);
 191       else
 192         assert(0 && "Unsupported!");
 193     }
 194
 195     // Check subsequent words.
 196     for (unsigned i = WordPos+1; i < BITWORDS_PER_ELEMENT; ++i)
 197       if (Bits[i] != 0) {
 198         if (sizeof(BitWord) == 4)
 199           return i * BITWORD_SIZE + CountTrailingZeros_32(Bits[i]);
 200         else if (sizeof(BitWord) == 8)
 201           return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]);
 202         else
 203           assert(0 && "Unsupported!");
 204       }
 205     return -1;
 206   }
 207
 208   // Union this element with RHS and return true if this one changed.
 209   bool unionWith(const SparseBitVectorElement &RHS) {
 210     bool changed = false;
 211     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
 212       BitWord old = changed ? 0 : Bits[i];
 213
 214       Bits[i] |= RHS.Bits[i];
 215       if (!changed && old != Bits[i])
 216         changed = true;
 217     }
 218     return changed;
 219   }
 220
 221   // Return true if we have any bits in common with RHS
 222   bool intersects(const SparseBitVectorElement &RHS) const {
 223     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
 224       if (RHS.Bits[i] & Bits[i])
 225         return true;
 226     }
 227     return false;
 228   }
 229
 230   // Intersect this Element with RHS and return true if this one changed.
 231   // BecameZero is set to true if this element became all-zero bits.
 232   bool intersectWith(const SparseBitVectorElement &RHS,
 233                      bool &BecameZero) {
 234     bool changed = false;
 235     bool allzero = true;
 236
 237     BecameZero = false;
 238     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
 239       BitWord old = changed ? 0 : Bits[i];
 240
 241       Bits[i] &= RHS.Bits[i];
 242       if (Bits[i] != 0)
 243         allzero = false;
 244
 245       if (!changed && old != Bits[i])
 246         changed = true;
 247     }
 248     BecameZero = allzero;
 249     return changed;
 250   }
 251   // Intersect this Element with the complement of RHS and return true if this
 252   // one changed.  BecameZero is set to true if this element became all-zero
 253   // bits.
 254   bool intersectWithComplement(const SparseBitVectorElement &RHS,
 255                                bool &BecameZero) {
 256     bool changed = false;
 257     bool allzero = true;
 258
 259     BecameZero = false;
 260     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
 261       BitWord old = changed ? 0 : Bits[i];
 262
 263       Bits[i] &= ~RHS.Bits[i];
 264       if (Bits[i] != 0)
 265         allzero = false;
 266
 267       if (!changed && old != Bits[i])
 268         changed = true;
 269     }
 270     BecameZero = allzero;
 271     return changed;
 272   }
 273   // Three argument version of intersectWithComplement that intersects
 274   // RHS1 & ~RHS2 into this element
 275   void intersectWithComplement(const SparseBitVectorElement &RHS1,
 276                                const SparseBitVectorElement &RHS2,
 277                                bool &BecameZero) {
 278     bool allzero = true;
 279
 280     BecameZero = false;
 281     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
 282       Bits[i] = RHS1.Bits[i] & ~RHS2.Bits[i];
 283       if (Bits[i] != 0)
 284         allzero = false;
 285     }
 286     BecameZero = allzero;
 287   }
 288 };
 289
 290 template <unsigned ElementSize = 128>
 291 class SparseBitVector {
 292   typedef ilist<SparseBitVectorElement<ElementSize> > ElementList;
 293   typedef typename ElementList::iterator ElementListIter;
 294   typedef typename ElementList::const_iterator ElementListConstIter;
 295   enum {
 296     BITWORD_SIZE = SparseBitVectorElement<ElementSize>::BITWORD_SIZE
 297   };
 298
 299   // Pointer to our current Element.
 300   ElementListIter CurrElementIter;
 301   ElementList Elements;
 302
 303   // This is like std::lower_bound, except we do linear searching from the
 304   // current position.
 305   ElementListIter FindLowerBound(unsigned ElementIndex) {
 306
 307     if (Elements.empty()) {
 308       CurrElementIter = Elements.begin();
 309       return Elements.begin();
 310     }
 311
 312     // Make sure our current iterator is valid.
 313     if (CurrElementIter == Elements.end())
 314       --CurrElementIter;
 315
 316     // Search from our current iterator, either backwards or forwards,
 317     // depending on what element we are looking for.
 318     ElementListIter ElementIter = CurrElementIter;
 319     if (CurrElementIter->index() == ElementIndex) {
 320       return ElementIter;
 321     } else if (CurrElementIter->index() > ElementIndex) {
 322       while (ElementIter != Elements.begin()
 323              && ElementIter->index() > ElementIndex)
 324         --ElementIter;
 325     } else {
 326       while (ElementIter != Elements.end() &&
 327              ElementIter->index() <= ElementIndex)
 328         ++ElementIter;
 329       --ElementIter;
 330     }
 331     CurrElementIter = ElementIter;
 332     return ElementIter;
 333   }
 334
 335   // Iterator to walk set bits in the bitmap.  This iterator is a lot uglier
 336   // than it would be, in order to be efficient.
 337   class SparseBitVectorIterator {
 338   private:
 339     bool AtEnd;
 340
 341     const SparseBitVector<ElementSize> *BitVector;
 342
 343     // Current element inside of bitmap.
 344     ElementListConstIter Iter;
 345
 346     // Current bit number inside of our bitmap.
 347     unsigned BitNumber;
 348
 349     // Current word number inside of our element.
 350     unsigned WordNumber;
 351
 352     // Current bits from the element.
 353     typename SparseBitVectorElement<ElementSize>::BitWord Bits;
 354
 355     // Move our iterator to the first non-zero bit in the bitmap.
 356     void AdvanceToFirstNonZero() {
 357       if (AtEnd)
 358         return;
 359       if (BitVector->Elements.empty()) {
 360         AtEnd = true;
 361         return;
 362       }
 363       Iter = BitVector->Elements.begin();
 364       BitNumber = Iter->index() * ElementSize;
 365       unsigned BitPos = Iter->find_first();
 366       BitNumber += BitPos;
 367       WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;
 368       Bits = Iter->word(WordNumber);
 369       Bits >>= BitPos % BITWORD_SIZE;
 370     }
 371
 372     // Move our iterator to the next non-zero bit.
 373     void AdvanceToNextNonZero() {
 374       if (AtEnd)
 375         return;
 376
 377       while (Bits && !(Bits & 1)) {
 378         Bits >>= 1;
 379         BitNumber += 1;
 380       }
 381
 382       // See if we ran out of Bits in this word.
 383       if (!Bits) {
 384         int NextSetBitNumber = Iter->find_next(BitNumber % ElementSize) ;
 385         // If we ran out of set bits in this element, move to next element.
 386         if (NextSetBitNumber == -1 || (BitNumber % ElementSize == 0)) {
 387           ++Iter;
 388           WordNumber = 0;
 389
 390           // We may run out of elements in the bitmap.
 391           if (Iter == BitVector->Elements.end()) {
 392             AtEnd = true;
 393             return;
 394           }
 395           // Set up for next non zero word in bitmap.
 396           BitNumber = Iter->index() * ElementSize;
 397           NextSetBitNumber = Iter->find_first();
 398           BitNumber += NextSetBitNumber;
 399           WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;
 400           Bits = Iter->word(WordNumber);
 401           Bits >>= NextSetBitNumber % BITWORD_SIZE;
 402         } else {
 403           WordNumber = (NextSetBitNumber % ElementSize) / BITWORD_SIZE;
 404           Bits = Iter->word(WordNumber);
 405           Bits >>= NextSetBitNumber % BITWORD_SIZE;
 406         }
 407       }
 408     }
 409   public:
 410     // Preincrement.
 411     inline SparseBitVectorIterator& operator++() {
 412       ++BitNumber;
 413       Bits >>= 1;
 414       AdvanceToNextNonZero();
 415       return *this;
 416     }
 417
 418     // Postincrement.
 419     inline SparseBitVectorIterator operator++(int) {
 420       SparseBitVectorIterator tmp = *this;
 421       ++*this;
 422       return tmp;
 423     }
 424
 425     // Return the current set bit number.
 426     unsigned operator*() const {
 427       return BitNumber;
 428     }
 429
 430     bool operator==(const SparseBitVectorIterator &RHS) const {
 431       // If they are both at the end, ignore the rest of the fields.
 432       if (AtEnd == RHS.AtEnd)
 433         return true;
 434       // Otherwise they are the same if they have the same bit number and
 435       // bitmap.
 436       return AtEnd == RHS.AtEnd && RHS.BitNumber == BitNumber;
 437     }
 438     bool operator!=(const SparseBitVectorIterator &RHS) const {
 439       return !(*this == RHS);
 440     }
 441     SparseBitVectorIterator(): BitVector(NULL) {
 442     }
 443
 444
 445     SparseBitVectorIterator(const SparseBitVector<ElementSize> *RHS,
 446                             bool end = false):BitVector(RHS) {
 447       Iter = BitVector->Elements.begin();
 448       BitNumber = 0;
 449       Bits = 0;
 450       WordNumber = ~0;
 451       AtEnd = end;
 452       AdvanceToFirstNonZero();
 453     }
 454   };
 455 public:
 456   typedef SparseBitVectorIterator iterator;
 457
 458   SparseBitVector () {
 459     CurrElementIter = Elements.begin ();
 460   }
 461
 462   ~SparseBitVector() {
 463   }
 464
 465   // SparseBitVector copy ctor.
 466   SparseBitVector(const SparseBitVector &RHS) {
 467     ElementListConstIter ElementIter = RHS.Elements.begin();
 468     while (ElementIter != RHS.Elements.end()) {
 469       Elements.push_back(SparseBitVectorElement<ElementSize>(*ElementIter));
 470       ++ElementIter;
 471     }
 472
 473     CurrElementIter = Elements.begin ();
 474   }
 475
 476   // Test, Reset, and Set a bit in the bitmap.
 477   bool test(unsigned Idx) {
 478     if (Elements.empty())
 479       return false;
 480
 481     unsigned ElementIndex = Idx / ElementSize;
 482     ElementListIter ElementIter = FindLowerBound(ElementIndex);
 483
 484     // If we can't find an element that is supposed to contain this bit, there
 485     // is nothing more to do.
 486     if (ElementIter == Elements.end() ||
 487         ElementIter->index() != ElementIndex)
 488       return false;
 489     return ElementIter->test(Idx % ElementSize);
 490   }
 491
 492   void reset(unsigned Idx) {
 493     if (Elements.empty())
 494       return;
 495
 496     unsigned ElementIndex = Idx / ElementSize;
 497     ElementListIter ElementIter = FindLowerBound(ElementIndex);
 498
 499     // If we can't find an element that is supposed to contain this bit, there
 500     // is nothing more to do.
 501     if (ElementIter == Elements.end() ||
 502         ElementIter->index() != ElementIndex)
 503       return;
 504     ElementIter->reset(Idx % ElementSize);
 505
 506     // When the element is zeroed out, delete it.
 507     if (ElementIter->empty()) {
 508       ++CurrElementIter;
 509       Elements.erase(ElementIter);
 510     }
 511   }
 512
 513   void set(unsigned Idx) {
 514     unsigned ElementIndex = Idx / ElementSize;
 515     SparseBitVectorElement<ElementSize> *Element;
 516     ElementListIter ElementIter;
 517     if (Elements.empty()) {
 518       Element = new SparseBitVectorElement<ElementSize>(ElementIndex);
 519       ElementIter = Elements.insert(Elements.end(), Element);
 520
 521     } else {
 522       ElementIter = FindLowerBound(ElementIndex);
 523
 524       if (ElementIter == Elements.end() ||
 525           ElementIter->index() != ElementIndex) {
 526         Element = new SparseBitVectorElement<ElementSize>(ElementIndex);
 527         // Insert does insert before, and lower bound gives the one before.
 528         ElementIter = Elements.insert(++ElementIter, Element);
 529       }
 530     }
 531     ElementIter->set(Idx % ElementSize);
 532   }
 533
 534   bool test_and_set (unsigned Idx) {
 535     bool old = test(Idx);
 536     if (!old)
 537       set(Idx);
 538     return !old;
 539   }
 540
 541   // Union our bitmap with the RHS and return true if we changed.
 542   bool operator|=(const SparseBitVector &RHS) {
 543     bool changed = false;
 544     ElementListIter Iter1 = Elements.begin();
 545     ElementListConstIter Iter2 = RHS.Elements.begin();
 546
 547     // Check if both bitmaps are empty
 548     if (Elements.empty() && RHS.Elements.empty())
 549       return false;
 550
 551     while (Iter2 != RHS.Elements.end()) {
 552       if (Iter1 == Elements.end() || Iter1->index() > Iter2->index()) {
 553         Elements.insert(Iter1,
 554                         new SparseBitVectorElement<ElementSize>(*Iter2));
 555         ++Iter2;
 556         changed = true;
 557       } else if (Iter1->index() == Iter2->index()) {
 558         changed |= Iter1->unionWith(*Iter2);
 559         ++Iter1;
 560         ++Iter2;
 561       } else {
 562         ++Iter1;
 563       }
 564     }
 565     CurrElementIter = Elements.begin();
 566     return changed;
 567   }
 568
 569   // Intersect our bitmap with the RHS and return true if ours changed.
 570   bool operator&=(const SparseBitVector &RHS) {
 571     bool changed = false;
 572     ElementListIter Iter1 = Elements.begin();
 573     ElementListConstIter Iter2 = RHS.Elements.begin();
 574
 575     // Check if both bitmaps are empty.
 576     if (Elements.empty() && RHS.Elements.empty())
 577       return false;
 578
 579     // Loop through, intersecting as we go, erasing elements when necessary.
 580     while (Iter2 != RHS.Elements.end()) {
 581       if (Iter1 == Elements.end())
 582         return changed;
 583
 584       if (Iter1->index() > Iter2->index()) {
 585         ++Iter2;
 586       } else if (Iter1->index() == Iter2->index()) {
 587         bool BecameZero;
 588         changed |= Iter1->intersectWith(*Iter2, BecameZero);
 589         if (BecameZero) {
 590           ElementListIter IterTmp = Iter1;
 591           ++Iter1;
 592           Elements.erase(IterTmp);
 593         } else {
 594           ++Iter1;
 595         }
 596         ++Iter2;
 597       } else {
 598         ElementListIter IterTmp = Iter1;
 599         ++Iter1;
 600         Elements.erase(IterTmp);
 601       }
 602     }
 603     Elements.erase(Iter1, Elements.end());
 604     CurrElementIter = Elements.begin();
 605     return changed;
 606   }
 607
 608   // Intersect our bitmap with the complement of the RHS and return true if ours
 609   // changed.
 610   bool intersectWithComplement(const SparseBitVector &RHS) {
 611     bool changed = false;
 612     ElementListIter Iter1 = Elements.begin();
 613     ElementListConstIter Iter2 = RHS.Elements.begin();
 614
 615     // Check if they are both empty
 616     if (Elements.empty() && RHS.Elements.empty())
 617       return false;
 618
 619     // Loop through, intersecting as we go, erasing elements when necessary.
 620     while (Iter2 != RHS.Elements.end()) {
 621       if (Iter1 == Elements.end())
 622         return changed;
 623
 624       if (Iter1->index() > Iter2->index()) {
 625         ++Iter2;
 626       } else if (Iter1->index() == Iter2->index()) {
 627         bool BecameZero;
 628         changed |= Iter1->intersectWithComplement(*Iter2, BecameZero);
 629         if (BecameZero) {
 630           ElementListIter IterTmp = Iter1;
 631           ++Iter1;
 632           Elements.erase(IterTmp);
 633         } else {
 634           ++Iter1;
 635         }
 636         ++Iter2;
 637       } else {
 638         ElementListIter IterTmp = Iter1;
 639         ++Iter1;
 640         Elements.erase(IterTmp);
 641       }
 642     }
 643     CurrElementIter = Elements.begin();
 644     return changed;
 645   }
 646
 647   bool intersectWithComplement(const SparseBitVector<ElementSize> *RHS) const {
 648     return intersectWithComplement(*RHS);
 649   }
 650
 651
 652   //  Three argument version of intersectWithComplement.  Result of RHS1 & ~RHS2
 653   //  is stored into this bitmap.
 654   void intersectWithComplement(const SparseBitVector<ElementSize> &RHS1,
 655                                const SparseBitVector<ElementSize> &RHS2)
 656   {
 657     Elements.clear();
 658     ElementListConstIter Iter1 = RHS1.Elements.begin();
 659     ElementListConstIter Iter2 = RHS2.Elements.begin();
 660
 661     // Check if they are both empty.
 662     if (RHS1.empty() && RHS2.empty())
 663       return;
 664
 665     // Loop through, intersecting as we go, erasing elements when necessary.
 666     while (Iter2 != RHS2.Elements.end()) {
 667       if (Iter1 == RHS1.Elements.end())
 668         return;
 669
 670       if (Iter1->index() > Iter2->index()) {
 671         ++Iter2;
 672       } else if (Iter1->index() == Iter2->index()) {
 673         bool BecameZero = false;
 674         SparseBitVectorElement<ElementSize> *NewElement =
 675           new SparseBitVectorElement<ElementSize>(Iter1->index());
 676         NewElement->intersectWithComplement(*Iter1, *Iter2, BecameZero);
 677         if (!BecameZero) {
 678           Elements.push_back(NewElement);
 679         }
 680         else
 681           delete NewElement;
 682         ++Iter1;
 683         ++Iter2;
 684       } else {
 685         ++Iter1;
 686       }
 687     }
 688
 689     // copy the remaining elements
 690     while (Iter1 != RHS1.Elements.end()) {
 691         SparseBitVectorElement<ElementSize> *NewElement =
 692           new SparseBitVectorElement<ElementSize>(*Iter1);
 693         Elements.push_back(NewElement);
 694         ++Iter1;
 695       }
 696
 697     CurrElementIter = Elements.begin();
 698     return;
 699   }
 700
 701   void intersectWithComplement(const SparseBitVector<ElementSize> *RHS1,
 702                                const SparseBitVector<ElementSize> *RHS2) {
 703     intersectWithComplement(*RHS1, *RHS2);
 704   }
 705
 706   bool intersects(const SparseBitVector<ElementSize> *RHS) const {
 707     return intersects(*RHS);
 708   }
 709
 710   // Return true if we share any bits in common with RHS
 711   bool intersects(const SparseBitVector<ElementSize> &RHS) const {
 712     ElementListConstIter Iter1 = Elements.begin();
 713     ElementListConstIter Iter2 = RHS.Elements.begin();
 714
 715     // Check if both bitmaps are empty.
 716     if (Elements.empty() && RHS.Elements.empty())
 717       return false;
 718
 719     // Loop through, intersecting stopping when we hit bits in common.
 720     while (Iter2 != RHS.Elements.end()) {
 721       if (Iter1 == Elements.end())
 722         return false;
 723
 724       if (Iter1->index() > Iter2->index()) {
 725         ++Iter2;
 726       } else if (Iter1->index() == Iter2->index()) {
 727         if (Iter1->intersects(*Iter2))
 728           return true;
 729         ++Iter1;
 730         ++Iter2;
 731       } else {
 732         ++Iter1;
 733       }
 734     }
 735     return false;
 736   }
 737
 738   // Return the first set bit in the bitmap.  Return -1 if no bits are set.
 739   int find_first() const {
 740     if (Elements.empty())
 741       return -1;
 742     const SparseBitVectorElement<ElementSize> &First = *(Elements.begin());
 743     return (First.index() * ElementSize) + First.find_first();
 744   }
 745
 746   // Return true if the SparseBitVector is empty
 747   bool empty() const {
 748     return Elements.empty();
 749   }
 750
 751   unsigned count() const {
 752     unsigned BitCount = 0;
 753     for (ElementListConstIter Iter = Elements.begin();
 754          Iter != Elements.end();
 755          ++Iter)
 756       BitCount += Iter->count();
 757
 758     return BitCount;
 759   }
 760   iterator begin() const {
 761     return iterator(this);
 762   }
 763
 764   iterator end() const {
 765     return iterator(this, ~0);
 766   }
 767
 768 };
 769
 770 // Convenience functions to allow Or and And without dereferencing in the user
 771 // code.
 772
 773 template <unsigned ElementSize>
 774 inline bool operator |=(SparseBitVector<ElementSize> &LHS,
 775                         const SparseBitVector<ElementSize> *RHS) {
 776   return LHS |= *RHS;
 777 }
 778
 779 template <unsigned ElementSize>
 780 inline bool operator |=(SparseBitVector<ElementSize> *LHS,
 781                         const SparseBitVector<ElementSize> &RHS) {
 782   return LHS->operator|=(RHS);
 783 }
 784
 785 template <unsigned ElementSize>
 786 inline bool operator &=(SparseBitVector<ElementSize> *LHS,
 787                         const SparseBitVector<ElementSize> &RHS) {
 788   return LHS->operator&=(RHS);
 789 }
 790
 791 template <unsigned ElementSize>
 792 inline bool operator &=(SparseBitVector<ElementSize> &LHS,
 793                         const SparseBitVector<ElementSize> *RHS) {
 794   return LHS &= (*RHS);
 795 }
 796
 797
 798 // Dump a SparseBitVector to a stream
 799 template <unsigned ElementSize>
 800 void dump(const SparseBitVector<ElementSize> &LHS, llvm::OStream &out) {
 801   out << "[ ";
 802
 803   typename SparseBitVector<ElementSize>::iterator bi;
 804   for (bi = LHS.begin(); bi != LHS.end(); ++bi) {
 805     out << *bi << " ";
 806   }
 807     out << "\n";
 808 }
 809
 810 }
 811
 812 #endif