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 (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 (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 (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     // See if the first bitmap element is the same in both.  This is only
 552     // possible if they are the same bitmap.
 553     if (Iter1 != Elements.end() && Iter2 != RHS.Elements.end())
 554       if (*Iter1 == *Iter2)
 555         return false;
 556
 557     while (Iter2 != RHS.Elements.end()) {
 558       if (Iter1 == Elements.end() || Iter1->index() > Iter2->index()) {
 559         Elements.insert(Iter1,
 560                         new SparseBitVectorElement<ElementSize>(*Iter2));
 561         ++Iter2;
 562         changed = true;
 563       } else if (Iter1->index() == Iter2->index()) {
 564         changed |= Iter1->unionWith(*Iter2);
 565         ++Iter1;
 566         ++Iter2;
 567       } else {
 568         ++Iter1;
 569       }
 570     }
 571     CurrElementIter = Elements.begin();
 572     return changed;
 573   }
 574
 575   // Intersect our bitmap with the RHS and return true if ours changed.
 576   bool operator&=(const SparseBitVector &RHS) {
 577     bool changed = false;
 578     ElementListIter Iter1 = Elements.begin();
 579     ElementListConstIter Iter2 = RHS.Elements.begin();
 580
 581     // Check if both bitmaps are empty.
 582     if (Elements.empty() && RHS.Elements.empty())
 583       return false;
 584
 585     // See if the first bitmap element is the same in both.  This is only
 586     // possible if they are the same bitmap.
 587     if (Iter1 != Elements.end() && Iter2 != RHS.Elements.end())
 588       if (*Iter1 == *Iter2)
 589         return false;
 590
 591     // Loop through, intersecting as we go, erasing elements when necessary.
 592     while (Iter2 != RHS.Elements.end()) {
 593       if (Iter1 == Elements.end())
 594         return changed;
 595
 596       if (Iter1->index() > Iter2->index()) {
 597         ++Iter2;
 598       } else if (Iter1->index() == Iter2->index()) {
 599         bool BecameZero;
 600         changed |= Iter1->intersectWith(*Iter2, BecameZero);
 601         if (BecameZero) {
 602           ElementListIter IterTmp = Iter1;
 603           Elements.erase(IterTmp);
 604         }
 605         ++Iter1;
 606         ++Iter2;
 607       } else {
 608         ElementListIter IterTmp = Iter1;
 609         ++Iter1;
 610         Elements.erase(IterTmp);
 611       }
 612     }
 613     Elements.erase(Iter1, Elements.end());
 614     CurrElementIter = Elements.begin();
 615     return changed;
 616   }
 617
 618   // Intersect our bitmap with the complement of the RHS and return true if ours
 619   // changed.
 620   bool intersectWithComplement(const SparseBitVector &RHS) {
 621     bool changed = false;
 622     ElementListIter Iter1 = Elements.begin();
 623     ElementListConstIter Iter2 = RHS.Elements.begin();
 624
 625     // Check if they are both empty
 626     if (Elements.empty() && RHS.Elements.empty())
 627       return false;
 628
 629     // See if the first bitmap element is the same in both.  This is only
 630     // possible if they are the same bitmap.
 631     if (Iter1 != Elements.end() && Iter2 != RHS.Elements.end())
 632       if (*Iter1 == *Iter2) {
 633         Elements.clear();
 634         return true;
 635       }
 636
 637     // Loop through, intersecting as we go, erasing elements when necessary.
 638     while (Iter2 != RHS.Elements.end()) {
 639       if (Iter1 == Elements.end())
 640         return changed;
 641
 642       if (Iter1->index() > Iter2->index()) {
 643         ++Iter2;
 644       } else if (Iter1->index() == Iter2->index()) {
 645         bool BecameZero;
 646         changed |= Iter1->intersectWithComplement(*Iter2, BecameZero);
 647         if (BecameZero) {
 648           ElementListIter IterTmp = Iter1;
 649           Elements.erase(IterTmp);
 650         }
 651         ++Iter1;
 652         ++Iter2;
 653       } else {
 654         ElementListIter IterTmp = Iter1;
 655         ++Iter1;
 656         Elements.erase(IterTmp);
 657       }
 658     }
 659     CurrElementIter = Elements.begin();
 660     return changed;
 661   }
 662
 663   bool intersectWithComplement(const SparseBitVector<ElementSize> *RHS) const {
 664     return intersectWithComplement(*RHS);
 665   }
 666
 667
 668   //  Three argument version of intersectWithComplement.  Result of RHS1 & ~RHS2
 669   //  is stored into this bitmap.
 670   void intersectWithComplement(const SparseBitVector<ElementSize> &RHS1,
 671                                const SparseBitVector<ElementSize> &RHS2)
 672   {
 673     Elements.clear();
 674     ElementListConstIter Iter1 = RHS1.Elements.begin();
 675     ElementListConstIter Iter2 = RHS2.Elements.begin();
 676
 677     // Check if they are both empty.
 678     if (RHS1.empty() && RHS2.empty())
 679       return;
 680
 681     // See if the first bitmap element is the same in both.  This is only
 682     // possible if they are the same bitmap.
 683     if (Iter1 != RHS1.Elements.end() && Iter2 != RHS2.Elements.end())
 684       if (*Iter1 == *Iter2) {
 685         return;
 686       }
 687
 688     // Loop through, intersecting as we go, erasing elements when necessary.
 689     while (Iter2 != RHS2.Elements.end()) {
 690       if (Iter1 == RHS1.Elements.end())
 691         return;
 692
 693       if (Iter1->index() > Iter2->index()) {
 694         ++Iter2;
 695       } else if (Iter1->index() == Iter2->index()) {
 696         bool BecameZero = false;
 697         SparseBitVectorElement<ElementSize> *NewElement =
 698           new SparseBitVectorElement<ElementSize>(Iter1->index());
 699         NewElement->intersectWithComplement(*Iter1, *Iter2, BecameZero);
 700         if (!BecameZero) {
 701           Elements.push_back(NewElement);
 702         }
 703         else
 704           delete NewElement;
 705
 706         ++Iter1;
 707         ++Iter2;
 708       } else {
 709         ++Iter1;
 710       }
 711     }
 712
 713     // copy the remaining elements
 714     while (Iter1 != RHS1.Elements.end()) {
 715         SparseBitVectorElement<ElementSize> *NewElement =
 716           new SparseBitVectorElement<ElementSize>(*Iter1);
 717         Elements.push_back(NewElement);
 718         ++Iter1;
 719       }
 720
 721     CurrElementIter = Elements.begin();
 722     return;
 723   }
 724
 725   void intersectWithComplement(const SparseBitVector<ElementSize> *RHS1,
 726                                const SparseBitVector<ElementSize> *RHS2) {
 727     intersectWithComplement(*RHS1, *RHS2);
 728   }
 729
 730   bool intersects(const SparseBitVector<ElementSize> *RHS) const {
 731     return intersects(*RHS);
 732   }
 733
 734   // Return true if we share any bits in common with RHS
 735   bool intersects(const SparseBitVector<ElementSize> &RHS) const {
 736     ElementListConstIter Iter1 = Elements.begin();
 737     ElementListConstIter Iter2 = RHS.Elements.begin();
 738
 739     // Check if both bitmaps are empty.
 740     if (Elements.empty() && RHS.Elements.empty())
 741       return false;
 742
 743     // See if the first bitmap element is the same in both.  This is only
 744     // possible if they are the same bitmap.
 745     if (Iter1 != Elements.end() && Iter2 != RHS.Elements.end())
 746       if (*Iter1 == *Iter2) {
 747         return true;
 748       }
 749
 750     // Loop through, intersecting stopping when we hit bits in common.
 751     while (Iter2 != RHS.Elements.end()) {
 752       if (Iter1 == Elements.end())
 753         return false;
 754
 755       if (Iter1->index() > Iter2->index()) {
 756         ++Iter2;
 757       } else if (Iter1->index() == Iter2->index()) {
 758         if (Iter1->intersects(*Iter2))
 759           return true;
 760         ++Iter1;
 761         ++Iter2;
 762       } else {
 763         ++Iter1;
 764       }
 765     }
 766     return false;
 767   }
 768
 769   // Return the first set bit in the bitmap.  Return -1 if no bits are set.
 770   int find_first() const {
 771     if (Elements.empty())
 772       return -1;
 773     const SparseBitVectorElement<ElementSize> &First = *(Elements.begin());
 774     return (First.index() * ElementSize) + First.find_first();
 775   }
 776
 777   // Return true if the SparseBitVector is empty
 778   bool empty() const {
 779     return Elements.empty();
 780   }
 781
 782   unsigned count() const {
 783     unsigned BitCount = 0;
 784     for (ElementListConstIter Iter = Elements.begin();
 785          Iter != Elements.end();
 786          ++Iter)
 787       BitCount += Iter->count();
 788
 789     return BitCount;
 790   }
 791   iterator begin() const {
 792     return iterator(this);
 793   }
 794
 795   iterator end() const {
 796     return iterator(this, ~0);
 797   }
 798
 799   // Dump our bits to stderr
 800   void dump(llvm::OStream &out) const {
 801     out << "[ ";
 802     for (iterator bi = begin();
 803          bi != end();
 804          ++bi) {
 805       out << *bi << " ";
 806     }
 807     out << std::endl;
 808   }
 809 };
 810
 811 // Convenience functions to allow Or and And without dereferencing in the user
 812 // code.
 813
 814 template <unsigned ElementSize>
 815 inline bool operator |=(SparseBitVector<ElementSize> &LHS,
 816                         const SparseBitVector<ElementSize> *RHS) {
 817   return LHS |= *RHS;
 818 }
 819
 820 template <unsigned ElementSize>
 821 inline bool operator |=(SparseBitVector<ElementSize> *LHS,
 822                         const SparseBitVector<ElementSize> &RHS) {
 823   return LHS->operator|=(RHS);
 824 }
 825
 826 template <unsigned ElementSize>
 827 inline bool operator &=(SparseBitVector<ElementSize> *LHS,
 828                         const SparseBitVector<ElementSize> &RHS) {
 829   return LHS->operator&=(RHS);
 830 }
 831
 832 template <unsigned ElementSize>
 833 inline bool operator &=(SparseBitVector<ElementSize> &LHS,
 834                         const SparseBitVector<ElementSize> *RHS) {
 835   return LHS &= (*RHS);
 836 }
 837
 838 }
 839
 840 #endif