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