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         }
 409       }
 410     }
 411   public:
 412     // Preincrement.
 413     inline SparseBitVectorIterator& operator++() {
 414       ++BitNumber;
 415       Bits >>= 1;
 416       AdvanceToNextNonZero();
 417       return *this;
 418     }
 419
 420     // Postincrement.
 421     inline SparseBitVectorIterator operator++(int) {
 422       SparseBitVectorIterator tmp = *this;
 423       ++*this;
 424       return tmp;
 425     }
 426
 427     // Return the current set bit number.
 428     unsigned operator*() const {
 429       return BitNumber;
 430     }
 431
 432     bool operator==(const SparseBitVectorIterator &RHS) const {
 433       // If they are both at the end, ignore the rest of the fields.
 434       if (AtEnd == RHS.AtEnd)
 435         return true;
 436       // Otherwise they are the same if they have the same bit number and
 437       // bitmap.
 438       return AtEnd == RHS.AtEnd && RHS.BitNumber == BitNumber;
 439     }
 440     bool operator!=(const SparseBitVectorIterator &RHS) const {
 441       return !(*this == RHS);
 442     }
 443     SparseBitVectorIterator(): BitVector(NULL) {
 444     }
 445
 446
 447     SparseBitVectorIterator(const SparseBitVector<ElementSize> *RHS,
 448                             bool end = false):BitVector(RHS) {
 449       Iter = BitVector->Elements.begin();
 450       BitNumber = 0;
 451       Bits = 0;
 452       WordNumber = ~0;
 453       AtEnd = end;
 454       AdvanceToFirstNonZero();
 455     }
 456   };
 457 public:
 458   typedef SparseBitVectorIterator iterator;
 459
 460   SparseBitVector () {
 461     CurrElementIter = Elements.begin ();
 462   }
 463
 464   ~SparseBitVector() {
 465   }
 466
 467   // SparseBitVector copy ctor.
 468   SparseBitVector(const SparseBitVector &RHS) {
 469     ElementListConstIter ElementIter = RHS.Elements.begin();
 470     while (ElementIter != RHS.Elements.end()) {
 471       Elements.push_back(SparseBitVectorElement<ElementSize>(*ElementIter));
 472       ++ElementIter;
 473     }
 474
 475     CurrElementIter = Elements.begin ();
 476   }
 477
 478   // Test, Reset, and Set a bit in the bitmap.
 479   bool test(unsigned Idx) {
 480     if (Elements.empty())
 481       return false;
 482
 483     unsigned ElementIndex = Idx / ElementSize;
 484     ElementListIter ElementIter = FindLowerBound(ElementIndex);
 485
 486     // If we can't find an element that is supposed to contain this bit, there
 487     // is nothing more to do.
 488     if (ElementIter == Elements.end() ||
 489         ElementIter->index() != ElementIndex)
 490       return false;
 491     return ElementIter->test(Idx % ElementSize);
 492   }
 493
 494   void reset(unsigned Idx) {
 495     if (Elements.empty())
 496       return;
 497
 498     unsigned ElementIndex = Idx / ElementSize;
 499     ElementListIter ElementIter = FindLowerBound(ElementIndex);
 500
 501     // If we can't find an element that is supposed to contain this bit, there
 502     // is nothing more to do.
 503     if (ElementIter == Elements.end() ||
 504         ElementIter->index() != ElementIndex)
 505       return;
 506     ElementIter->reset(Idx % ElementSize);
 507
 508     // When the element is zeroed out, delete it.
 509     if (ElementIter->empty()) {
 510       ++CurrElementIter;
 511       Elements.erase(ElementIter);
 512     }
 513   }
 514
 515   void set(unsigned Idx) {
 516     unsigned ElementIndex = Idx / ElementSize;
 517     SparseBitVectorElement<ElementSize> *Element;
 518     ElementListIter ElementIter;
 519     if (Elements.empty()) {
 520       Element = new SparseBitVectorElement<ElementSize>(ElementIndex);
 521       ElementIter = Elements.insert(Elements.end(), Element);
 522
 523     } else {
 524       ElementIter = FindLowerBound(ElementIndex);
 525
 526       if (ElementIter == Elements.end() ||
 527           ElementIter->index() != ElementIndex) {
 528         Element = new SparseBitVectorElement<ElementSize>(ElementIndex);
 529         // Insert does insert before, and lower bound gives the one before.
 530         ElementIter = Elements.insert(++ElementIter, Element);
 531       }
 532     }
 533     ElementIter->set(Idx % ElementSize);
 534   }
 535
 536   bool test_and_set (unsigned Idx) {
 537     bool old = test(Idx);
 538     if (!old) {
 539       set(Idx);
 540       return true;
 541     }
 542     return false;
 543   }
 544
 545   bool operator!=(const SparseBitVector &RHS) {
 546     return !(*this == RHS);
 547   }
 548
 549   bool operator==(const SparseBitVector &RHS) {
 550     ElementListConstIter Iter1 = Elements.begin();
 551     ElementListConstIter Iter2 = RHS.Elements.begin();
 552
 553     while (Iter2 != RHS.Elements.end()) {
 554       if (Iter1->index() != Iter2->index()
 555           || *Iter1 != *Iter2)
 556         return false;
 557       ++Iter1;
 558       ++Iter2;
 559     }
 560     return Iter1 == Elements.end();
 561   }
 562
 563   // Union our bitmap with the RHS and return true if we changed.
 564   bool operator|=(const SparseBitVector &RHS) {
 565     bool changed = false;
 566     ElementListIter Iter1 = Elements.begin();
 567     ElementListConstIter Iter2 = RHS.Elements.begin();
 568
 569     // Check if both bitmaps are empty
 570     if (Elements.empty() && RHS.Elements.empty())
 571       return false;
 572
 573     while (Iter2 != RHS.Elements.end()) {
 574       if (Iter1 == Elements.end() || Iter1->index() > Iter2->index()) {
 575         Elements.insert(Iter1,
 576                         new SparseBitVectorElement<ElementSize>(*Iter2));
 577         ++Iter2;
 578         changed = true;
 579       } else if (Iter1->index() == Iter2->index()) {
 580         changed |= Iter1->unionWith(*Iter2);
 581         ++Iter1;
 582         ++Iter2;
 583       } else {
 584         ++Iter1;
 585       }
 586     }
 587     CurrElementIter = Elements.begin();
 588     return changed;
 589   }
 590
 591   // Intersect our bitmap with the RHS and return true if ours changed.
 592   bool operator&=(const SparseBitVector &RHS) {
 593     bool changed = false;
 594     ElementListIter Iter1 = Elements.begin();
 595     ElementListConstIter Iter2 = RHS.Elements.begin();
 596
 597     // Check if both bitmaps are empty.
 598     if (Elements.empty() && RHS.Elements.empty())
 599       return false;
 600
 601     // Loop through, intersecting as we go, erasing elements when necessary.
 602     while (Iter2 != RHS.Elements.end()) {
 603       if (Iter1 == Elements.end())
 604         return changed;
 605
 606       if (Iter1->index() > Iter2->index()) {
 607         ++Iter2;
 608       } else if (Iter1->index() == Iter2->index()) {
 609         bool BecameZero;
 610         changed |= Iter1->intersectWith(*Iter2, BecameZero);
 611         if (BecameZero) {
 612           ElementListIter IterTmp = Iter1;
 613           ++Iter1;
 614           Elements.erase(IterTmp);
 615         } else {
 616           ++Iter1;
 617         }
 618         ++Iter2;
 619       } else {
 620         ElementListIter IterTmp = Iter1;
 621         ++Iter1;
 622         Elements.erase(IterTmp);
 623       }
 624     }
 625     Elements.erase(Iter1, Elements.end());
 626     CurrElementIter = Elements.begin();
 627     return changed;
 628   }
 629
 630   // Intersect our bitmap with the complement of the RHS and return true if ours
 631   // changed.
 632   bool intersectWithComplement(const SparseBitVector &RHS) {
 633     bool changed = false;
 634     ElementListIter Iter1 = Elements.begin();
 635     ElementListConstIter Iter2 = RHS.Elements.begin();
 636
 637     // Check if they are both empty
 638     if (Elements.empty() && RHS.Elements.empty())
 639       return false;
 640
 641     // Loop through, intersecting as we go, erasing elements when necessary.
 642     while (Iter2 != RHS.Elements.end()) {
 643       if (Iter1 == Elements.end())
 644         return changed;
 645
 646       if (Iter1->index() > Iter2->index()) {
 647         ++Iter2;
 648       } else if (Iter1->index() == Iter2->index()) {
 649         bool BecameZero;
 650         changed |= Iter1->intersectWithComplement(*Iter2, BecameZero);
 651         if (BecameZero) {
 652           ElementListIter IterTmp = Iter1;
 653           ++Iter1;
 654           Elements.erase(IterTmp);
 655         } else {
 656           ++Iter1;
 657         }
 658         ++Iter2;
 659       } else {
 660         ElementListIter IterTmp = Iter1;
 661         ++Iter1;
 662         Elements.erase(IterTmp);
 663       }
 664     }
 665     CurrElementIter = Elements.begin();
 666     return changed;
 667   }
 668
 669   bool intersectWithComplement(const SparseBitVector<ElementSize> *RHS) const {
 670     return intersectWithComplement(*RHS);
 671   }
 672
 673
 674   //  Three argument version of intersectWithComplement.  Result of RHS1 & ~RHS2
 675   //  is stored into this bitmap.
 676   void intersectWithComplement(const SparseBitVector<ElementSize> &RHS1,
 677                                const SparseBitVector<ElementSize> &RHS2)
 678   {
 679     Elements.clear();
 680     ElementListConstIter Iter1 = RHS1.Elements.begin();
 681     ElementListConstIter Iter2 = RHS2.Elements.begin();
 682
 683     // Check if they are both empty.
 684     if (RHS1.empty() && RHS2.empty())
 685       return;
 686
 687     // Loop through, intersecting as we go, erasing elements when necessary.
 688     while (Iter2 != RHS2.Elements.end()) {
 689       if (Iter1 == RHS1.Elements.end())
 690         return;
 691
 692       if (Iter1->index() > Iter2->index()) {
 693         ++Iter2;
 694       } else if (Iter1->index() == Iter2->index()) {
 695         bool BecameZero = false;
 696         SparseBitVectorElement<ElementSize> *NewElement =
 697           new SparseBitVectorElement<ElementSize>(Iter1->index());
 698         NewElement->intersectWithComplement(*Iter1, *Iter2, BecameZero);
 699         if (!BecameZero) {
 700           Elements.push_back(NewElement);
 701         }
 702         else
 703           delete NewElement;
 704         ++Iter1;
 705         ++Iter2;
 706       } else {
 707         ++Iter1;
 708       }
 709     }
 710
 711     // copy the remaining elements
 712     while (Iter1 != RHS1.Elements.end()) {
 713         SparseBitVectorElement<ElementSize> *NewElement =
 714           new SparseBitVectorElement<ElementSize>(*Iter1);
 715         Elements.push_back(NewElement);
 716         ++Iter1;
 717       }
 718
 719     CurrElementIter = Elements.begin();
 720     return;
 721   }
 722
 723   void intersectWithComplement(const SparseBitVector<ElementSize> *RHS1,
 724                                const SparseBitVector<ElementSize> *RHS2) {
 725     intersectWithComplement(*RHS1, *RHS2);
 726   }
 727
 728   bool intersects(const SparseBitVector<ElementSize> *RHS) const {
 729     return intersects(*RHS);
 730   }
 731
 732   // Return true if we share any bits in common with RHS
 733   bool intersects(const SparseBitVector<ElementSize> &RHS) const {
 734     ElementListConstIter Iter1 = Elements.begin();
 735     ElementListConstIter Iter2 = RHS.Elements.begin();
 736
 737     // Check if both bitmaps are empty.
 738     if (Elements.empty() && RHS.Elements.empty())
 739       return false;
 740
 741     // Loop through, intersecting stopping when we hit bits in common.
 742     while (Iter2 != RHS.Elements.end()) {
 743       if (Iter1 == Elements.end())
 744         return false;
 745
 746       if (Iter1->index() > Iter2->index()) {
 747         ++Iter2;
 748       } else if (Iter1->index() == Iter2->index()) {
 749         if (Iter1->intersects(*Iter2))
 750           return true;
 751         ++Iter1;
 752         ++Iter2;
 753       } else {
 754         ++Iter1;
 755       }
 756     }
 757     return false;
 758   }
 759
 760   // Return the first set bit in the bitmap.  Return -1 if no bits are set.
 761   int find_first() const {
 762     if (Elements.empty())
 763       return -1;
 764     const SparseBitVectorElement<ElementSize> &First = *(Elements.begin());
 765     return (First.index() * ElementSize) + First.find_first();
 766   }
 767
 768   // Return true if the SparseBitVector is empty
 769   bool empty() const {
 770     return Elements.empty();
 771   }
 772
 773   unsigned count() const {
 774     unsigned BitCount = 0;
 775     for (ElementListConstIter Iter = Elements.begin();
 776          Iter != Elements.end();
 777          ++Iter)
 778       BitCount += Iter->count();
 779
 780     return BitCount;
 781   }
 782   iterator begin() const {
 783     return iterator(this);
 784   }
 785
 786   iterator end() const {
 787     return iterator(this, ~0);
 788   }
 789
 790 };
 791
 792 // Convenience functions to allow Or and And without dereferencing in the user
 793 // code.
 794
 795 template <unsigned ElementSize>
 796 inline bool operator |=(SparseBitVector<ElementSize> &LHS,
 797                         const SparseBitVector<ElementSize> *RHS) {
 798   return LHS |= *RHS;
 799 }
 800
 801 template <unsigned ElementSize>
 802 inline bool operator |=(SparseBitVector<ElementSize> *LHS,
 803                         const SparseBitVector<ElementSize> &RHS) {
 804   return LHS->operator|=(RHS);
 805 }
 806
 807 template <unsigned ElementSize>
 808 inline bool operator &=(SparseBitVector<ElementSize> *LHS,
 809                         const SparseBitVector<ElementSize> &RHS) {
 810   return LHS->operator&=(RHS);
 811 }
 812
 813 template <unsigned ElementSize>
 814 inline bool operator &=(SparseBitVector<ElementSize> &LHS,
 815                         const SparseBitVector<ElementSize> *RHS) {
 816   return LHS &= (*RHS);
 817 }
 818
 819
 820 // Dump a SparseBitVector to a stream
 821 template <unsigned ElementSize>
 822 void dump(const SparseBitVector<ElementSize> &LHS, llvm::OStream &out) {
 823   out << "[ ";
 824
 825   typename SparseBitVector<ElementSize>::iterator bi;
 826   for (bi = LHS.begin(); bi != LHS.end(); ++bi) {
 827     out << *bi << " ";
 828   }
 829     out << "\n";
 830 }
 831
 832 }
 833
 834 #endif