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 public:
  79   explicit SparseBitVectorElement(unsigned Idx) {
  80     ElementIndex = Idx;
  81     memset(&Bits[0], 0, sizeof (BitWord) * BITWORDS_PER_ELEMENT);
  82   }
  83
  84   ~SparseBitVectorElement() {
  85   }
  86
  87   // Copy ctor.
  88   SparseBitVectorElement(const SparseBitVectorElement &RHS) {
  89     ElementIndex = RHS.ElementIndex;
  90     std::copy(&RHS.Bits[0], &RHS.Bits[BITWORDS_PER_ELEMENT], Bits);
  91   }
  92
  93   // Comparison.
  94   bool operator==(const SparseBitVectorElement &RHS) const {
  95     if (ElementIndex != RHS.ElementIndex)
  96       return false;
  97     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
  98       if (Bits[i] != RHS.Bits[i])
  99         return false;
 100     return true;
 101   }
 102
 103   bool operator!=(const SparseBitVectorElement &RHS) const {
 104     return !(*this == RHS);
 105   }
 106
 107   // Return the bits that make up word Idx in our element.
 108   BitWord word(unsigned Idx) const {
 109     assert (Idx < BITWORDS_PER_ELEMENT);
 110     return Bits[Idx];
 111   }
 112
 113   unsigned index() const {
 114     return ElementIndex;
 115   }
 116
 117   bool empty() const {
 118     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
 119       if (Bits[i])
 120         return false;
 121     return true;
 122   }
 123
 124   void set(unsigned Idx) {
 125     Bits[Idx / BITWORD_SIZE] |= 1L << (Idx % BITWORD_SIZE);
 126   }
 127
 128   bool test_and_set (unsigned Idx) {
 129     bool old = test(Idx);
 130     if (!old) {
 131       set(Idx);
 132       return true;
 133     }
 134     return false;
 135   }
 136
 137   void reset(unsigned Idx) {
 138     Bits[Idx / BITWORD_SIZE] &= ~(1L << (Idx % BITWORD_SIZE));
 139   }
 140
 141   bool test(unsigned Idx) const {
 142     return Bits[Idx / BITWORD_SIZE] & (1L << (Idx % BITWORD_SIZE));
 143   }
 144
 145   unsigned count() const {
 146     unsigned NumBits = 0;
 147     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
 148       if (sizeof(BitWord) == 4)
 149         NumBits += CountPopulation_32(Bits[i]);
 150       else if (sizeof(BitWord) == 8)
 151         NumBits += CountPopulation_64(Bits[i]);
 152       else
 153         assert(0 && "Unsupported!");
 154     return NumBits;
 155   }
 156
 157   /// find_first - Returns the index of the first set bit.
 158   int find_first() const {
 159     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
 160       if (Bits[i] != 0) {
 161         if (sizeof(BitWord) == 4)
 162           return i * BITWORD_SIZE + CountTrailingZeros_32(Bits[i]);
 163         else if (sizeof(BitWord) == 8)
 164           return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]);
 165         else
 166           assert(0 && "Unsupported!");
 167       }
 168     assert(0 && "Illegal empty element");
 169   }
 170
 171   /// find_next - Returns the index of the next set bit starting from the
 172   /// "Curr" bit. Returns -1 if the next set bit is not found.
 173   int find_next(unsigned Curr) const {
 174     if (Curr >= BITS_PER_ELEMENT)
 175       return -1;
 176
 177     unsigned WordPos = Curr / BITWORD_SIZE;
 178     unsigned BitPos = Curr % 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   // Get a hash value for this element;
 290   uint64_t getHashValue() const {
 291     uint64_t HashVal = 0;
 292     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
 293       HashVal ^= Bits[i];
 294     }
 295     return HashVal;
 296   }
 297 };
 298
 299 template <unsigned ElementSize = 128>
 300 class SparseBitVector {
 301   typedef ilist<SparseBitVectorElement<ElementSize> > ElementList;
 302   typedef typename ElementList::iterator ElementListIter;
 303   typedef typename ElementList::const_iterator ElementListConstIter;
 304   enum {
 305     BITWORD_SIZE = SparseBitVectorElement<ElementSize>::BITWORD_SIZE
 306   };
 307
 308   // Pointer to our current Element.
 309   ElementListIter CurrElementIter;
 310   ElementList Elements;
 311
 312   // This is like std::lower_bound, except we do linear searching from the
 313   // current position.
 314   ElementListIter FindLowerBound(unsigned ElementIndex) {
 315
 316     if (Elements.empty()) {
 317       CurrElementIter = Elements.begin();
 318       return Elements.begin();
 319     }
 320
 321     // Make sure our current iterator is valid.
 322     if (CurrElementIter == Elements.end())
 323       --CurrElementIter;
 324
 325     // Search from our current iterator, either backwards or forwards,
 326     // depending on what element we are looking for.
 327     ElementListIter ElementIter = CurrElementIter;
 328     if (CurrElementIter->index() == ElementIndex) {
 329       return ElementIter;
 330     } else if (CurrElementIter->index() > ElementIndex) {
 331       while (ElementIter != Elements.begin()
 332              && ElementIter->index() > ElementIndex)
 333         --ElementIter;
 334     } else {
 335       while (ElementIter != Elements.end() &&
 336              ElementIter->index() < ElementIndex)
 337         ++ElementIter;
 338     }
 339     CurrElementIter = ElementIter;
 340     return ElementIter;
 341   }
 342
 343   // Iterator to walk set bits in the bitmap.  This iterator is a lot uglier
 344   // than it would be, in order to be efficient.
 345   class SparseBitVectorIterator {
 346   private:
 347     bool AtEnd;
 348
 349     const SparseBitVector<ElementSize> *BitVector;
 350
 351     // Current element inside of bitmap.
 352     ElementListConstIter Iter;
 353
 354     // Current bit number inside of our bitmap.
 355     unsigned BitNumber;
 356
 357     // Current word number inside of our element.
 358     unsigned WordNumber;
 359
 360     // Current bits from the element.
 361     typename SparseBitVectorElement<ElementSize>::BitWord Bits;
 362
 363     // Move our iterator to the first non-zero bit in the bitmap.
 364     void AdvanceToFirstNonZero() {
 365       if (AtEnd)
 366         return;
 367       if (BitVector->Elements.empty()) {
 368         AtEnd = true;
 369         return;
 370       }
 371       Iter = BitVector->Elements.begin();
 372       BitNumber = Iter->index() * ElementSize;
 373       unsigned BitPos = Iter->find_first();
 374       BitNumber += BitPos;
 375       WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;
 376       Bits = Iter->word(WordNumber);
 377       Bits >>= BitPos % BITWORD_SIZE;
 378     }
 379
 380     // Move our iterator to the next non-zero bit.
 381     void AdvanceToNextNonZero() {
 382       if (AtEnd)
 383         return;
 384
 385       while (Bits && !(Bits & 1)) {
 386         Bits >>= 1;
 387         BitNumber += 1;
 388       }
 389
 390       // See if we ran out of Bits in this word.
 391       if (!Bits) {
 392         int NextSetBitNumber = Iter->find_next(BitNumber % ElementSize) ;
 393         // If we ran out of set bits in this element, move to next element.
 394         if (NextSetBitNumber == -1 || (BitNumber % ElementSize == 0)) {
 395           ++Iter;
 396           WordNumber = 0;
 397
 398           // We may run out of elements in the bitmap.
 399           if (Iter == BitVector->Elements.end()) {
 400             AtEnd = true;
 401             return;
 402           }
 403           // Set up for next non zero word in bitmap.
 404           BitNumber = Iter->index() * ElementSize;
 405           NextSetBitNumber = Iter->find_first();
 406           BitNumber += NextSetBitNumber;
 407           WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;
 408           Bits = Iter->word(WordNumber);
 409           Bits >>= NextSetBitNumber % BITWORD_SIZE;
 410         } else {
 411           WordNumber = (NextSetBitNumber % ElementSize) / BITWORD_SIZE;
 412           Bits = Iter->word(WordNumber);
 413           Bits >>= NextSetBitNumber % BITWORD_SIZE;
 414           BitNumber = Iter->index() * ElementSize;
 415           BitNumber += NextSetBitNumber;
 416         }
 417       }
 418     }
 419   public:
 420     // Preincrement.
 421     inline SparseBitVectorIterator& operator++() {
 422       ++BitNumber;
 423       Bits >>= 1;
 424       AdvanceToNextNonZero();
 425       return *this;
 426     }
 427
 428     // Postincrement.
 429     inline SparseBitVectorIterator operator++(int) {
 430       SparseBitVectorIterator tmp = *this;
 431       ++*this;
 432       return tmp;
 433     }
 434
 435     // Return the current set bit number.
 436     unsigned operator*() const {
 437       return BitNumber;
 438     }
 439
 440     bool operator==(const SparseBitVectorIterator &RHS) const {
 441       // If they are both at the end, ignore the rest of the fields.
 442       if (AtEnd && RHS.AtEnd)
 443         return true;
 444       // Otherwise they are the same if they have the same bit number and
 445       // bitmap.
 446       return AtEnd == RHS.AtEnd && RHS.BitNumber == BitNumber;
 447     }
 448     bool operator!=(const SparseBitVectorIterator &RHS) const {
 449       return !(*this == RHS);
 450     }
 451     SparseBitVectorIterator(): BitVector(NULL) {
 452     }
 453
 454
 455     SparseBitVectorIterator(const SparseBitVector<ElementSize> *RHS,
 456                             bool end = false):BitVector(RHS) {
 457       Iter = BitVector->Elements.begin();
 458       BitNumber = 0;
 459       Bits = 0;
 460       WordNumber = ~0;
 461       AtEnd = end;
 462       AdvanceToFirstNonZero();
 463     }
 464   };
 465 public:
 466   typedef SparseBitVectorIterator iterator;
 467
 468   SparseBitVector () {
 469     CurrElementIter = Elements.begin ();
 470   }
 471
 472   ~SparseBitVector() {
 473   }
 474
 475   // SparseBitVector copy ctor.
 476   SparseBitVector(const SparseBitVector &RHS) {
 477     ElementListConstIter ElementIter = RHS.Elements.begin();
 478     while (ElementIter != RHS.Elements.end()) {
 479       Elements.push_back(SparseBitVectorElement<ElementSize>(*ElementIter));
 480       ++ElementIter;
 481     }
 482
 483     CurrElementIter = Elements.begin ();
 484   }
 485
 486   // Test, Reset, and Set a bit in the bitmap.
 487   bool test(unsigned Idx) {
 488     if (Elements.empty())
 489       return false;
 490
 491     unsigned ElementIndex = Idx / ElementSize;
 492     ElementListIter ElementIter = FindLowerBound(ElementIndex);
 493
 494     // If we can't find an element that is supposed to contain this bit, there
 495     // is nothing more to do.
 496     if (ElementIter == Elements.end() ||
 497         ElementIter->index() != ElementIndex)
 498       return false;
 499     return ElementIter->test(Idx % ElementSize);
 500   }
 501
 502   void reset(unsigned Idx) {
 503     if (Elements.empty())
 504       return;
 505
 506     unsigned ElementIndex = Idx / ElementSize;
 507     ElementListIter ElementIter = FindLowerBound(ElementIndex);
 508
 509     // If we can't find an element that is supposed to contain this bit, there
 510     // is nothing more to do.
 511     if (ElementIter == Elements.end() ||
 512         ElementIter->index() != ElementIndex)
 513       return;
 514     ElementIter->reset(Idx % ElementSize);
 515
 516     // When the element is zeroed out, delete it.
 517     if (ElementIter->empty()) {
 518       ++CurrElementIter;
 519       Elements.erase(ElementIter);
 520     }
 521   }
 522
 523   void set(unsigned Idx) {
 524     unsigned ElementIndex = Idx / ElementSize;
 525     SparseBitVectorElement<ElementSize> *Element;
 526     ElementListIter ElementIter;
 527     if (Elements.empty()) {
 528       Element = new SparseBitVectorElement<ElementSize>(ElementIndex);
 529       ElementIter = Elements.insert(Elements.end(), Element);
 530
 531     } else {
 532       ElementIter = FindLowerBound(ElementIndex);
 533
 534       if (ElementIter == Elements.end() ||
 535           ElementIter->index() != ElementIndex) {
 536         Element = new SparseBitVectorElement<ElementSize>(ElementIndex);
 537         // We may have hit the beginning of our SparseBitVector, in which case,
 538         // we may need to insert right after this element, which requires moving
 539         // the current iterator forward one, because insert does insert before.
 540         if (ElementIter != Elements.end() &&
 541             ElementIter->index() < ElementIndex)
 542           ElementIter = Elements.insert(++ElementIter, Element);
 543         else
 544           ElementIter = Elements.insert(ElementIter, Element);
 545       }
 546     }
 547     CurrElementIter = ElementIter;
 548
 549     ElementIter->set(Idx % ElementSize);
 550   }
 551
 552   bool test_and_set (unsigned Idx) {
 553     bool old = test(Idx);
 554     if (!old) {
 555       set(Idx);
 556       return true;
 557     }
 558     return false;
 559   }
 560
 561   bool operator!=(const SparseBitVector &RHS) const {
 562     return !(*this == RHS);
 563   }
 564
 565   bool operator==(const SparseBitVector &RHS) const {
 566     ElementListConstIter Iter1 = Elements.begin();
 567     ElementListConstIter Iter2 = RHS.Elements.begin();
 568
 569     for (; Iter1 != Elements.end() && Iter2 != RHS.Elements.end();
 570          ++Iter1, ++Iter2) {
 571       if (*Iter1 != *Iter2)
 572         return false;
 573     }
 574     return Iter1 == Elements.end() && Iter2 == RHS.Elements.end();
 575   }
 576
 577   // Union our bitmap with the RHS and return true if we changed.
 578   bool operator|=(const SparseBitVector &RHS) {
 579     bool changed = false;
 580     ElementListIter Iter1 = Elements.begin();
 581     ElementListConstIter Iter2 = RHS.Elements.begin();
 582
 583     // If RHS is empty, we are done
 584     if (RHS.Elements.empty())
 585       return false;
 586
 587     while (Iter2 != RHS.Elements.end()) {
 588       if (Iter1 == Elements.end() || Iter1->index() > Iter2->index()) {
 589         Elements.insert(Iter1,
 590                         new SparseBitVectorElement<ElementSize>(*Iter2));
 591         ++Iter2;
 592         changed = true;
 593       } else if (Iter1->index() == Iter2->index()) {
 594         changed |= Iter1->unionWith(*Iter2);
 595         ++Iter1;
 596         ++Iter2;
 597       } else {
 598         ++Iter1;
 599       }
 600     }
 601     CurrElementIter = Elements.begin();
 602     return changed;
 603   }
 604
 605   // Intersect our bitmap with the RHS and return true if ours changed.
 606   bool operator&=(const SparseBitVector &RHS) {
 607     bool changed = false;
 608     ElementListIter Iter1 = Elements.begin();
 609     ElementListConstIter Iter2 = RHS.Elements.begin();
 610
 611     // Check if both bitmaps are empty.
 612     if (Elements.empty() && RHS.Elements.empty())
 613       return false;
 614
 615     // Loop through, intersecting as we go, erasing elements when necessary.
 616     while (Iter2 != RHS.Elements.end()) {
 617       if (Iter1 == Elements.end())
 618         return changed;
 619
 620       if (Iter1->index() > Iter2->index()) {
 621         ++Iter2;
 622       } else if (Iter1->index() == Iter2->index()) {
 623         bool BecameZero;
 624         changed |= Iter1->intersectWith(*Iter2, BecameZero);
 625         if (BecameZero) {
 626           ElementListIter IterTmp = Iter1;
 627           ++Iter1;
 628           Elements.erase(IterTmp);
 629         } else {
 630           ++Iter1;
 631         }
 632         ++Iter2;
 633       } else {
 634         ElementListIter IterTmp = Iter1;
 635         ++Iter1;
 636         Elements.erase(IterTmp);
 637       }
 638     }
 639     Elements.erase(Iter1, Elements.end());
 640     CurrElementIter = Elements.begin();
 641     return changed;
 642   }
 643
 644   // Intersect our bitmap with the complement of the RHS and return true if ours
 645   // changed.
 646   bool intersectWithComplement(const SparseBitVector &RHS) {
 647     bool changed = false;
 648     ElementListIter Iter1 = Elements.begin();
 649     ElementListConstIter Iter2 = RHS.Elements.begin();
 650
 651     // If either our bitmap or RHS is empty, we are done
 652     if (Elements.empty() || RHS.Elements.empty())
 653       return false;
 654
 655     // Loop through, intersecting as we go, erasing elements when necessary.
 656     while (Iter2 != RHS.Elements.end()) {
 657       if (Iter1 == Elements.end())
 658         return changed;
 659
 660       if (Iter1->index() > Iter2->index()) {
 661         ++Iter2;
 662       } else if (Iter1->index() == Iter2->index()) {
 663         bool BecameZero;
 664         changed |= Iter1->intersectWithComplement(*Iter2, BecameZero);
 665         if (BecameZero) {
 666           ElementListIter IterTmp = Iter1;
 667           ++Iter1;
 668           Elements.erase(IterTmp);
 669         } else {
 670           ++Iter1;
 671         }
 672         ++Iter2;
 673       } else {
 674         ++Iter1;
 675       }
 676     }
 677     CurrElementIter = Elements.begin();
 678     return changed;
 679   }
 680
 681   bool intersectWithComplement(const SparseBitVector<ElementSize> *RHS) const {
 682     return intersectWithComplement(*RHS);
 683   }
 684
 685
 686   //  Three argument version of intersectWithComplement.  Result of RHS1 & ~RHS2
 687   //  is stored into this bitmap.
 688   void intersectWithComplement(const SparseBitVector<ElementSize> &RHS1,
 689                                const SparseBitVector<ElementSize> &RHS2)
 690   {
 691     Elements.clear();
 692     ElementListConstIter Iter1 = RHS1.Elements.begin();
 693     ElementListConstIter Iter2 = RHS2.Elements.begin();
 694
 695     // If RHS1 is empty, we are done
 696     // If RHS2 is empty, we still have to copy RHS1
 697     if (RHS1.Elements.empty())
 698       return;
 699
 700     // Loop through, intersecting as we go, erasing elements when necessary.
 701     while (Iter2 != RHS2.Elements.end()) {
 702       if (Iter1 == RHS1.Elements.end())
 703         return;
 704
 705       if (Iter1->index() > Iter2->index()) {
 706         ++Iter2;
 707       } else if (Iter1->index() == Iter2->index()) {
 708         bool BecameZero = false;
 709         SparseBitVectorElement<ElementSize> *NewElement =
 710           new SparseBitVectorElement<ElementSize>(Iter1->index());
 711         NewElement->intersectWithComplement(*Iter1, *Iter2, BecameZero);
 712         if (!BecameZero) {
 713           Elements.push_back(NewElement);
 714         }
 715         else
 716           delete NewElement;
 717         ++Iter1;
 718         ++Iter2;
 719       } else {
 720         SparseBitVectorElement<ElementSize> *NewElement =
 721           new SparseBitVectorElement<ElementSize>(*Iter1);
 722         Elements.push_back(NewElement);
 723         ++Iter1;
 724       }
 725     }
 726
 727     // copy the remaining elements
 728     while (Iter1 != RHS1.Elements.end()) {
 729         SparseBitVectorElement<ElementSize> *NewElement =
 730           new SparseBitVectorElement<ElementSize>(*Iter1);
 731         Elements.push_back(NewElement);
 732         ++Iter1;
 733       }
 734
 735     CurrElementIter = Elements.begin();
 736     return;
 737   }
 738
 739   void intersectWithComplement(const SparseBitVector<ElementSize> *RHS1,
 740                                const SparseBitVector<ElementSize> *RHS2) {
 741     intersectWithComplement(*RHS1, *RHS2);
 742   }
 743
 744   bool intersects(const SparseBitVector<ElementSize> *RHS) const {
 745     return intersects(*RHS);
 746   }
 747
 748   // Return true if we share any bits in common with RHS
 749   bool intersects(const SparseBitVector<ElementSize> &RHS) const {
 750     ElementListConstIter Iter1 = Elements.begin();
 751     ElementListConstIter Iter2 = RHS.Elements.begin();
 752
 753     // Check if both bitmaps are empty.
 754     if (Elements.empty() && RHS.Elements.empty())
 755       return false;
 756
 757     // Loop through, intersecting stopping when we hit bits in common.
 758     while (Iter2 != RHS.Elements.end()) {
 759       if (Iter1 == Elements.end())
 760         return false;
 761
 762       if (Iter1->index() > Iter2->index()) {
 763         ++Iter2;
 764       } else if (Iter1->index() == Iter2->index()) {
 765         if (Iter1->intersects(*Iter2))
 766           return true;
 767         ++Iter1;
 768         ++Iter2;
 769       } else {
 770         ++Iter1;
 771       }
 772     }
 773     return false;
 774   }
 775
 776   // Return the first set bit in the bitmap.  Return -1 if no bits are set.
 777   int find_first() const {
 778     if (Elements.empty())
 779       return -1;
 780     const SparseBitVectorElement<ElementSize> &First = *(Elements.begin());
 781     return (First.index() * ElementSize) + First.find_first();
 782   }
 783
 784   // Return true if the SparseBitVector is empty
 785   bool empty() const {
 786     return Elements.empty();
 787   }
 788
 789   unsigned count() const {
 790     unsigned BitCount = 0;
 791     for (ElementListConstIter Iter = Elements.begin();
 792          Iter != Elements.end();
 793          ++Iter)
 794       BitCount += Iter->count();
 795
 796     return BitCount;
 797   }
 798   iterator begin() const {
 799     return iterator(this);
 800   }
 801
 802   iterator end() const {
 803     return iterator(this, ~0);
 804   }
 805
 806   // Get a hash value for this bitmap.
 807   uint64_t getHashValue() const {
 808     uint64_t HashVal = 0;
 809     for (ElementListConstIter Iter = Elements.begin();
 810          Iter != Elements.end();
 811          ++Iter) {
 812       HashVal ^= Iter->index();
 813       HashVal ^= Iter->getHashValue();
 814     }
 815     return HashVal;
 816   }
 817 };
 818
 819 // Convenience functions to allow Or and And without dereferencing in the user
 820 // code.
 821
 822 template <unsigned ElementSize>
 823 inline bool operator |=(SparseBitVector<ElementSize> &LHS,
 824                         const SparseBitVector<ElementSize> *RHS) {
 825   return LHS |= *RHS;
 826 }
 827
 828 template <unsigned ElementSize>
 829 inline bool operator |=(SparseBitVector<ElementSize> *LHS,
 830                         const SparseBitVector<ElementSize> &RHS) {
 831   return LHS->operator|=(RHS);
 832 }
 833
 834 template <unsigned ElementSize>
 835 inline bool operator &=(SparseBitVector<ElementSize> *LHS,
 836                         const SparseBitVector<ElementSize> &RHS) {
 837   return LHS->operator&=(RHS);
 838 }
 839
 840 template <unsigned ElementSize>
 841 inline bool operator &=(SparseBitVector<ElementSize> &LHS,
 842                         const SparseBitVector<ElementSize> *RHS) {
 843   return LHS &= (*RHS);
 844 }
 845
 846
 847 // Dump a SparseBitVector to a stream
 848 template <unsigned ElementSize>
 849 void dump(const SparseBitVector<ElementSize> &LHS, llvm::OStream &out) {
 850   out << "[ ";
 851
 852   typename SparseBitVector<ElementSize>::iterator bi;
 853   for (bi = LHS.begin(); bi != LHS.end(); ++bi) {
 854     out << *bi << " ";
 855   }
 856     out << " ]\n";
 857 }
 858 }
 859
 860
 861
 862 #endif