contrib/llvm/include/llvm/ADT/SparseBitVector.h

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