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