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