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 true;
 134     }
 135     return false;
 136   }
 137
 138   void reset(unsigned Idx) {
 139     Bits[Idx / BITWORD_SIZE] &= ~(1L << (Idx % BITWORD_SIZE));
 140   }
 141
 142   bool test(unsigned Idx) const {
 143     return Bits[Idx / BITWORD_SIZE] & (1L << (Idx % BITWORD_SIZE));
 144   }
 145
 146   unsigned count() const {
 147     unsigned NumBits = 0;
 148     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
 149       if (sizeof(BitWord) == 4)
 150         NumBits += CountPopulation_32(Bits[i]);
 151       else if (sizeof(BitWord) == 8)
 152         NumBits += CountPopulation_64(Bits[i]);
 153       else
 154         assert(0 && "Unsupported!");
 155     return NumBits;
 156   }
 157
 158   /// find_first - Returns the index of the first set bit.
 159   int find_first() const {
 160     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
 161       if (Bits[i] != 0) {
 162         if (sizeof(BitWord) == 4)
 163           return i * BITWORD_SIZE + CountTrailingZeros_32(Bits[i]);
 164         else if (sizeof(BitWord) == 8)
 165           return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]);
 166         else
 167           assert(0 && "Unsupported!");
 168       }
 169     assert(0 && "Illegal empty element");
 170   }
 171
 172   /// find_next - Returns the index of the next set bit following the
 173   /// "Prev" bit. Returns -1 if the next set bit is not found.
 174   int find_next(unsigned Prev) const {
 175     ++Prev;
 176     if (Prev >= BITS_PER_ELEMENT)
 177       return -1;
 178
 179     unsigned WordPos = Prev / BITWORD_SIZE;
 180     unsigned BitPos = Prev % BITWORD_SIZE;
 181     BitWord Copy = Bits[WordPos];
 182     assert (WordPos <= BITWORDS_PER_ELEMENT
 183             && "Word Position outside of element");
 184
 185     // Mask off previous bits.
 186     Copy &= ~0L << BitPos;
 187
 188     if (Copy != 0) {
 189       if (sizeof(BitWord) == 4)
 190         return WordPos * BITWORD_SIZE + CountTrailingZeros_32(Copy);
 191       else if (sizeof(BitWord) == 8)
 192         return WordPos * BITWORD_SIZE + CountTrailingZeros_64(Copy);
 193       else
 194         assert(0 && "Unsupported!");
 195     }
 196
 197     // Check subsequent words.
 198     for (unsigned i = WordPos+1; i < BITWORDS_PER_ELEMENT; ++i)
 199       if (Bits[i] != 0) {
 200         if (sizeof(BitWord) == 4)
 201           return i * BITWORD_SIZE + CountTrailingZeros_32(Bits[i]);
 202         else if (sizeof(BitWord) == 8)
 203           return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]);
 204         else
 205           assert(0 && "Unsupported!");
 206       }
 207     return -1;
 208   }
 209
 210   // Union this element with RHS and return true if this one changed.
 211   bool unionWith(const SparseBitVectorElement &RHS) {
 212     bool changed = false;
 213     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
 214       BitWord old = changed ? 0 : Bits[i];
 215
 216       Bits[i] |= RHS.Bits[i];
 217       if (!changed && old != Bits[i])
 218         changed = true;
 219     }
 220     return changed;
 221   }
 222
 223   // Return true if we have any bits in common with RHS
 224   bool intersects(const SparseBitVectorElement &RHS) const {
 225     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
 226       if (RHS.Bits[i] & Bits[i])
 227         return true;
 228     }
 229     return false;
 230   }
 231
 232   // Intersect this Element with RHS and return true if this one changed.
 233   // BecameZero is set to true if this element became all-zero bits.
 234   bool intersectWith(const SparseBitVectorElement &RHS,
 235                      bool &BecameZero) {
 236     bool changed = false;
 237     bool allzero = true;
 238
 239     BecameZero = false;
 240     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
 241       BitWord old = changed ? 0 : Bits[i];
 242
 243       Bits[i] &= RHS.Bits[i];
 244       if (Bits[i] != 0)
 245         allzero = false;
 246
 247       if (!changed && old != Bits[i])
 248         changed = true;
 249     }
 250     BecameZero = allzero;
 251     return changed;
 252   }
 253   // Intersect this Element with the complement of RHS and return true if this
 254   // one changed.  BecameZero is set to true if this element became all-zero
 255   // bits.
 256   bool intersectWithComplement(const SparseBitVectorElement &RHS,
 257                                bool &BecameZero) {
 258     bool changed = false;
 259     bool allzero = true;
 260
 261     BecameZero = false;
 262     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
 263       BitWord old = changed ? 0 : Bits[i];
 264
 265       Bits[i] &= ~RHS.Bits[i];
 266       if (Bits[i] != 0)
 267         allzero = false;
 268
 269       if (!changed && old != Bits[i])
 270         changed = true;
 271     }
 272     BecameZero = allzero;
 273     return changed;
 274   }
 275   // Three argument version of intersectWithComplement that intersects
 276   // RHS1 & ~RHS2 into this element
 277   void intersectWithComplement(const SparseBitVectorElement &RHS1,
 278                                const SparseBitVectorElement &RHS2,
 279                                bool &BecameZero) {
 280     bool allzero = true;
 281
 282     BecameZero = false;
 283     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
 284       Bits[i] = RHS1.Bits[i] & ~RHS2.Bits[i];
 285       if (Bits[i] != 0)
 286         allzero = false;
 287     }
 288     BecameZero = allzero;
 289   }
 290 };
 291
 292 template <unsigned ElementSize = 128>
 293 class SparseBitVector {
 294   typedef ilist<SparseBitVectorElement<ElementSize> > ElementList;
 295   typedef typename ElementList::iterator ElementListIter;
 296   typedef typename ElementList::const_iterator ElementListConstIter;
 297   enum {
 298     BITWORD_SIZE = SparseBitVectorElement<ElementSize>::BITWORD_SIZE
 299   };
 300
 301   // Pointer to our current Element.
 302   ElementListIter CurrElementIter;
 303   ElementList Elements;
 304
 305   // This is like std::lower_bound, except we do linear searching from the
 306   // current position.
 307   ElementListIter FindLowerBound(unsigned ElementIndex) {
 308
 309     if (Elements.empty()) {
 310       CurrElementIter = Elements.begin();
 311       return Elements.begin();
 312     }
 313
 314     // Make sure our current iterator is valid.
 315     if (CurrElementIter == Elements.end())
 316       --CurrElementIter;
 317
 318     // Search from our current iterator, either backwards or forwards,
 319     // depending on what element we are looking for.
 320     ElementListIter ElementIter = CurrElementIter;
 321     if (CurrElementIter->index() == ElementIndex) {
 322       return ElementIter;
 323     } else if (CurrElementIter->index() > ElementIndex) {
 324       while (ElementIter != Elements.begin()
 325              && ElementIter->index() > ElementIndex)
 326         --ElementIter;
 327     } else {
 328       while (ElementIter != Elements.end() &&
 329              ElementIter->index() <= ElementIndex)
 330         ++ElementIter;
 331       --ElementIter;
 332     }
 333     CurrElementIter = ElementIter;
 334     return ElementIter;
 335   }
 336
 337   // Iterator to walk set bits in the bitmap.  This iterator is a lot uglier
 338   // than it would be, in order to be efficient.
 339   class SparseBitVectorIterator {
 340   private:
 341     bool AtEnd;
 342
 343     const SparseBitVector<ElementSize> *BitVector;
 344
 345     // Current element inside of bitmap.
 346     ElementListConstIter Iter;
 347
 348     // Current bit number inside of our bitmap.
 349     unsigned BitNumber;
 350
 351     // Current word number inside of our element.
 352     unsigned WordNumber;
 353
 354     // Current bits from the element.
 355     typename SparseBitVectorElement<ElementSize>::BitWord Bits;
 356
 357     // Move our iterator to the first non-zero bit in the bitmap.
 358     void AdvanceToFirstNonZero() {
 359       if (AtEnd)
 360         return;
 361       if (BitVector->Elements.empty()) {
 362         AtEnd = true;
 363         return;
 364       }
 365       Iter = BitVector->Elements.begin();
 366       BitNumber = Iter->index() * ElementSize;
 367       unsigned BitPos = Iter->find_first();
 368       BitNumber += BitPos;
 369       WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;
 370       Bits = Iter->word(WordNumber);
 371       Bits >>= BitPos % BITWORD_SIZE;
 372     }
 373
 374     // Move our iterator to the next non-zero bit.
 375     void AdvanceToNextNonZero() {
 376       if (AtEnd)
 377         return;
 378
 379       while (Bits && !(Bits & 1)) {
 380         Bits >>= 1;
 381         BitNumber += 1;
 382       }
 383
 384       // See if we ran out of Bits in this word.
 385       if (!Bits) {
 386         int NextSetBitNumber = Iter->find_next(BitNumber % ElementSize) ;
 387         // If we ran out of set bits in this element, move to next element.
 388         if (NextSetBitNumber == -1 || (BitNumber % ElementSize == 0)) {
 389           ++Iter;
 390           WordNumber = 0;
 391
 392           // We may run out of elements in the bitmap.
 393           if (Iter == BitVector->Elements.end()) {
 394             AtEnd = true;
 395             return;
 396           }
 397           // Set up for next non zero word in bitmap.
 398           BitNumber = Iter->index() * ElementSize;
 399           NextSetBitNumber = Iter->find_first();
 400           BitNumber += NextSetBitNumber;
 401           WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;
 402           Bits = Iter->word(WordNumber);
 403           Bits >>= NextSetBitNumber % BITWORD_SIZE;
 404         } else {
 405           WordNumber = (NextSetBitNumber % ElementSize) / BITWORD_SIZE;
 406           Bits = Iter->word(WordNumber);
 407           Bits >>= NextSetBitNumber % BITWORD_SIZE;
 408           BitNumber = Iter->index() * ElementSize;
 409           BitNumber += NextSetBitNumber;
 410         }
 411       }
 412     }
 413   public:
 414     // Preincrement.
 415     inline SparseBitVectorIterator& operator++() {
 416       ++BitNumber;
 417       Bits >>= 1;
 418       AdvanceToNextNonZero();
 419       return *this;
 420     }
 421
 422     // Postincrement.
 423     inline SparseBitVectorIterator operator++(int) {
 424       SparseBitVectorIterator tmp = *this;
 425       ++*this;
 426       return tmp;
 427     }
 428
 429     // Return the current set bit number.
 430     unsigned operator*() const {
 431       return BitNumber;
 432     }
 433
 434     bool operator==(const SparseBitVectorIterator &RHS) const {
 435       // If they are both at the end, ignore the rest of the fields.
 436       if (AtEnd == RHS.AtEnd)
 437         return true;
 438       // Otherwise they are the same if they have the same bit number and
 439       // bitmap.
 440       return AtEnd == RHS.AtEnd && RHS.BitNumber == BitNumber;
 441     }
 442     bool operator!=(const SparseBitVectorIterator &RHS) const {
 443       return !(*this == RHS);
 444     }
 445     SparseBitVectorIterator(): BitVector(NULL) {
 446     }
 447
 448
 449     SparseBitVectorIterator(const SparseBitVector<ElementSize> *RHS,
 450                             bool end = false):BitVector(RHS) {
 451       Iter = BitVector->Elements.begin();
 452       BitNumber = 0;
 453       Bits = 0;
 454       WordNumber = ~0;
 455       AtEnd = end;
 456       AdvanceToFirstNonZero();
 457     }
 458   };
 459 public:
 460   typedef SparseBitVectorIterator iterator;
 461
 462   SparseBitVector () {
 463     CurrElementIter = Elements.begin ();
 464   }
 465
 466   ~SparseBitVector() {
 467   }
 468
 469   // SparseBitVector copy ctor.
 470   SparseBitVector(const SparseBitVector &RHS) {
 471     ElementListConstIter ElementIter = RHS.Elements.begin();
 472     while (ElementIter != RHS.Elements.end()) {
 473       Elements.push_back(SparseBitVectorElement<ElementSize>(*ElementIter));
 474       ++ElementIter;
 475     }
 476
 477     CurrElementIter = Elements.begin ();
 478   }
 479
 480   // Test, Reset, and Set a bit in the bitmap.
 481   bool test(unsigned Idx) {
 482     if (Elements.empty())
 483       return false;
 484
 485     unsigned ElementIndex = Idx / ElementSize;
 486     ElementListIter ElementIter = FindLowerBound(ElementIndex);
 487
 488     // If we can't find an element that is supposed to contain this bit, there
 489     // is nothing more to do.
 490     if (ElementIter == Elements.end() ||
 491         ElementIter->index() != ElementIndex)
 492       return false;
 493     return ElementIter->test(Idx % ElementSize);
 494   }
 495
 496   void reset(unsigned Idx) {
 497     if (Elements.empty())
 498       return;
 499
 500     unsigned ElementIndex = Idx / ElementSize;
 501     ElementListIter ElementIter = FindLowerBound(ElementIndex);
 502
 503     // If we can't find an element that is supposed to contain this bit, there
 504     // is nothing more to do.
 505     if (ElementIter == Elements.end() ||
 506         ElementIter->index() != ElementIndex)
 507       return;
 508     ElementIter->reset(Idx % ElementSize);
 509
 510     // When the element is zeroed out, delete it.
 511     if (ElementIter->empty()) {
 512       ++CurrElementIter;
 513       Elements.erase(ElementIter);
 514     }
 515   }
 516
 517   void set(unsigned Idx) {
 518     unsigned ElementIndex = Idx / ElementSize;
 519     SparseBitVectorElement<ElementSize> *Element;
 520     ElementListIter ElementIter;
 521     if (Elements.empty()) {
 522       Element = new SparseBitVectorElement<ElementSize>(ElementIndex);
 523       ElementIter = Elements.insert(Elements.end(), Element);
 524
 525     } else {
 526       ElementIter = FindLowerBound(ElementIndex);
 527
 528       if (ElementIter == Elements.end() ||
 529           ElementIter->index() != ElementIndex) {
 530         Element = new SparseBitVectorElement<ElementSize>(ElementIndex);
 531         // Insert does insert before, and lower bound gives the one before.
 532         ElementIter = Elements.insert(++ElementIter, Element);
 533       }
 534     }
 535     ElementIter->set(Idx % ElementSize);
 536   }
 537
 538   bool test_and_set (unsigned Idx) {
 539     bool old = test(Idx);
 540     if (!old) {
 541       set(Idx);
 542       return true;
 543     }
 544     return false;
 545   }
 546
 547   bool operator!=(const SparseBitVector &RHS) {
 548     return !(*this == RHS);
 549   }
 550
 551   bool operator==(const SparseBitVector &RHS) {
 552     ElementListConstIter Iter1 = Elements.begin();
 553     ElementListConstIter Iter2 = RHS.Elements.begin();
 554
 555     while (Iter2 != RHS.Elements.end()) {
 556       if (Iter1->index() != Iter2->index()
 557           || *Iter1 != *Iter2)
 558         return false;
 559       ++Iter1;
 560       ++Iter2;
 561     }
 562     return Iter1 == Elements.end();
 563   }
 564
 565   // Union our bitmap with the RHS and return true if we changed.
 566   bool operator|=(const SparseBitVector &RHS) {
 567     bool changed = false;
 568     ElementListIter Iter1 = Elements.begin();
 569     ElementListConstIter Iter2 = RHS.Elements.begin();
 570
 571     // Check if both bitmaps are empty
 572     if (Elements.empty() && RHS.Elements.empty())
 573       return false;
 574
 575     while (Iter2 != RHS.Elements.end()) {
 576       if (Iter1 == Elements.end() || Iter1->index() > Iter2->index()) {
 577         Elements.insert(Iter1,
 578                         new SparseBitVectorElement<ElementSize>(*Iter2));
 579         ++Iter2;
 580         changed = true;
 581       } else if (Iter1->index() == Iter2->index()) {
 582         changed |= Iter1->unionWith(*Iter2);
 583         ++Iter1;
 584         ++Iter2;
 585       } else {
 586         ++Iter1;
 587       }
 588     }
 589     CurrElementIter = Elements.begin();
 590     return changed;
 591   }
 592
 593   // Intersect our bitmap with the RHS and return true if ours changed.
 594   bool operator&=(const SparseBitVector &RHS) {
 595     bool changed = false;
 596     ElementListIter Iter1 = Elements.begin();
 597     ElementListConstIter Iter2 = RHS.Elements.begin();
 598
 599     // Check if both bitmaps are empty.
 600     if (Elements.empty() && RHS.Elements.empty())
 601       return false;
 602
 603     // Loop through, intersecting as we go, erasing elements when necessary.
 604     while (Iter2 != RHS.Elements.end()) {
 605       if (Iter1 == Elements.end())
 606         return changed;
 607
 608       if (Iter1->index() > Iter2->index()) {
 609         ++Iter2;
 610       } else if (Iter1->index() == Iter2->index()) {
 611         bool BecameZero;
 612         changed |= Iter1->intersectWith(*Iter2, BecameZero);
 613         if (BecameZero) {
 614           ElementListIter IterTmp = Iter1;
 615           ++Iter1;
 616           Elements.erase(IterTmp);
 617         } else {
 618           ++Iter1;
 619         }
 620         ++Iter2;
 621       } else {
 622         ElementListIter IterTmp = Iter1;
 623         ++Iter1;
 624         Elements.erase(IterTmp);
 625       }
 626     }
 627     Elements.erase(Iter1, Elements.end());
 628     CurrElementIter = Elements.begin();
 629     return changed;
 630   }
 631
 632   // Intersect our bitmap with the complement of the RHS and return true if ours
 633   // changed.
 634   bool intersectWithComplement(const SparseBitVector &RHS) {
 635     bool changed = false;
 636     ElementListIter Iter1 = Elements.begin();
 637     ElementListConstIter Iter2 = RHS.Elements.begin();
 638
 639     // Check if they are both empty
 640     if (Elements.empty() && RHS.Elements.empty())
 641       return false;
 642
 643     // Loop through, intersecting as we go, erasing elements when necessary.
 644     while (Iter2 != RHS.Elements.end()) {
 645       if (Iter1 == Elements.end())
 646         return changed;
 647
 648       if (Iter1->index() > Iter2->index()) {
 649         ++Iter2;
 650       } else if (Iter1->index() == Iter2->index()) {
 651         bool BecameZero;
 652         changed |= Iter1->intersectWithComplement(*Iter2, BecameZero);
 653         if (BecameZero) {
 654           ElementListIter IterTmp = Iter1;
 655           ++Iter1;
 656           Elements.erase(IterTmp);
 657         } else {
 658           ++Iter1;
 659         }
 660         ++Iter2;
 661       } else {
 662         ElementListIter IterTmp = Iter1;
 663         ++Iter1;
 664         Elements.erase(IterTmp);
 665       }
 666     }
 667     CurrElementIter = Elements.begin();
 668     return changed;
 669   }
 670
 671   bool intersectWithComplement(const SparseBitVector<ElementSize> *RHS) const {
 672     return intersectWithComplement(*RHS);
 673   }
 674
 675
 676   //  Three argument version of intersectWithComplement.  Result of RHS1 & ~RHS2
 677   //  is stored into this bitmap.
 678   void intersectWithComplement(const SparseBitVector<ElementSize> &RHS1,
 679                                const SparseBitVector<ElementSize> &RHS2)
 680   {
 681     Elements.clear();
 682     ElementListConstIter Iter1 = RHS1.Elements.begin();
 683     ElementListConstIter Iter2 = RHS2.Elements.begin();
 684
 685     // Check if they are both empty.
 686     if (RHS1.empty() && RHS2.empty())
 687       return;
 688
 689     // Loop through, intersecting as we go, erasing elements when necessary.
 690     while (Iter2 != RHS2.Elements.end()) {
 691       if (Iter1 == RHS1.Elements.end())
 692         return;
 693
 694       if (Iter1->index() > Iter2->index()) {
 695         ++Iter2;
 696       } else if (Iter1->index() == Iter2->index()) {
 697         bool BecameZero = false;
 698         SparseBitVectorElement<ElementSize> *NewElement =
 699           new SparseBitVectorElement<ElementSize>(Iter1->index());
 700         NewElement->intersectWithComplement(*Iter1, *Iter2, BecameZero);
 701         if (!BecameZero) {
 702           Elements.push_back(NewElement);
 703         }
 704         else
 705           delete NewElement;
 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     // Loop through, intersecting stopping when we hit bits in common.
 744     while (Iter2 != RHS.Elements.end()) {
 745       if (Iter1 == Elements.end())
 746         return false;
 747
 748       if (Iter1->index() > Iter2->index()) {
 749         ++Iter2;
 750       } else if (Iter1->index() == Iter2->index()) {
 751         if (Iter1->intersects(*Iter2))
 752           return true;
 753         ++Iter1;
 754         ++Iter2;
 755       } else {
 756         ++Iter1;
 757       }
 758     }
 759     return false;
 760   }
 761
 762   // Return the first set bit in the bitmap.  Return -1 if no bits are set.
 763   int find_first() const {
 764     if (Elements.empty())
 765       return -1;
 766     const SparseBitVectorElement<ElementSize> &First = *(Elements.begin());
 767     return (First.index() * ElementSize) + First.find_first();
 768   }
 769
 770   // Return true if the SparseBitVector is empty
 771   bool empty() const {
 772     return Elements.empty();
 773   }
 774
 775   unsigned count() const {
 776     unsigned BitCount = 0;
 777     for (ElementListConstIter Iter = Elements.begin();
 778          Iter != Elements.end();
 779          ++Iter)
 780       BitCount += Iter->count();
 781
 782     return BitCount;
 783   }
 784   iterator begin() const {
 785     return iterator(this);
 786   }
 787
 788   iterator end() const {
 789     return iterator(this, ~0);
 790   }
 791
 792 };
 793
 794 // Convenience functions to allow Or and And without dereferencing in the user
 795 // code.
 796
 797 template <unsigned ElementSize>
 798 inline bool operator |=(SparseBitVector<ElementSize> &LHS,
 799                         const SparseBitVector<ElementSize> *RHS) {
 800   return LHS |= *RHS;
 801 }
 802
 803 template <unsigned ElementSize>
 804 inline bool operator |=(SparseBitVector<ElementSize> *LHS,
 805                         const SparseBitVector<ElementSize> &RHS) {
 806   return LHS->operator|=(RHS);
 807 }
 808
 809 template <unsigned ElementSize>
 810 inline bool operator &=(SparseBitVector<ElementSize> *LHS,
 811                         const SparseBitVector<ElementSize> &RHS) {
 812   return LHS->operator&=(RHS);
 813 }
 814
 815 template <unsigned ElementSize>
 816 inline bool operator &=(SparseBitVector<ElementSize> &LHS,
 817                         const SparseBitVector<ElementSize> *RHS) {
 818   return LHS &= (*RHS);
 819 }
 820
 821
 822 // Dump a SparseBitVector to a stream
 823 template <unsigned ElementSize>
 824 void dump(const SparseBitVector<ElementSize> &LHS, llvm::OStream &out) {
 825   out << "[ ";
 826
 827   typename SparseBitVector<ElementSize>::iterator bi;
 828   for (bi = LHS.begin(); bi != LHS.end(); ++bi) {
 829     out << *bi << " ";
 830   }
 831     out << "\n";
 832 }
 833
 834 }
 835
 836 #endif