LLVM  mainline
SparseBitVector.h
Go to the documentation of this file.
00001 //===- llvm/ADT/SparseBitVector.h - Efficient Sparse BitVector -*- C++ -*- ===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file defines the SparseBitVector class.  See the doxygen comment for
00011 // SparseBitVector for more details on the algorithm used.
00012 //
00013 //===----------------------------------------------------------------------===//
00014 
00015 #ifndef LLVM_ADT_SPARSEBITVECTOR_H
00016 #define LLVM_ADT_SPARSEBITVECTOR_H
00017 
00018 #include "llvm/ADT/ilist.h"
00019 #include "llvm/ADT/ilist_node.h"
00020 #include "llvm/Support/DataTypes.h"
00021 #include "llvm/Support/ErrorHandling.h"
00022 #include "llvm/Support/MathExtras.h"
00023 #include "llvm/Support/raw_ostream.h"
00024 #include <cassert>
00025 #include <climits>
00026 
00027 namespace llvm {
00028 
00029 /// SparseBitVector is an implementation of a bitvector that is sparse by only
00030 /// storing the elements that have non-zero bits set.  In order to make this
00031 /// fast for the most common cases, SparseBitVector is implemented as a linked
00032 /// list of SparseBitVectorElements.  We maintain a pointer to the last
00033 /// SparseBitVectorElement accessed (in the form of a list iterator), in order
00034 /// to make multiple in-order test/set constant time after the first one is
00035 /// executed.  Note that using vectors to store SparseBitVectorElement's does
00036 /// not work out very well because it causes insertion in the middle to take
00037 /// enormous amounts of time with a large amount of bits.  Other structures that
00038 /// have better worst cases for insertion in the middle (various balanced trees,
00039 /// etc) do not perform as well in practice as a linked list with this iterator
00040 /// kept up to date.  They are also significantly more memory intensive.
00041 
00042 template <unsigned ElementSize = 128>
00043 struct SparseBitVectorElement
00044   : public ilist_node<SparseBitVectorElement<ElementSize> > {
00045 public:
00046   typedef unsigned long BitWord;
00047   typedef unsigned size_type;
00048   enum {
00049     BITWORD_SIZE = sizeof(BitWord) * CHAR_BIT,
00050     BITWORDS_PER_ELEMENT = (ElementSize + BITWORD_SIZE - 1) / BITWORD_SIZE,
00051     BITS_PER_ELEMENT = ElementSize
00052   };
00053 
00054 private:
00055   // Index of Element in terms of where first bit starts.
00056   unsigned ElementIndex;
00057   BitWord Bits[BITWORDS_PER_ELEMENT];
00058   // Needed for sentinels
00059   friend struct ilist_sentinel_traits<SparseBitVectorElement>;
00060   SparseBitVectorElement() {
00061     ElementIndex = ~0U;
00062     memset(&Bits[0], 0, sizeof (BitWord) * BITWORDS_PER_ELEMENT);
00063   }
00064 
00065 public:
00066   explicit SparseBitVectorElement(unsigned Idx) {
00067     ElementIndex = Idx;
00068     memset(&Bits[0], 0, sizeof (BitWord) * BITWORDS_PER_ELEMENT);
00069   }
00070 
00071   // Comparison.
00072   bool operator==(const SparseBitVectorElement &RHS) const {
00073     if (ElementIndex != RHS.ElementIndex)
00074       return false;
00075     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
00076       if (Bits[i] != RHS.Bits[i])
00077         return false;
00078     return true;
00079   }
00080 
00081   bool operator!=(const SparseBitVectorElement &RHS) const {
00082     return !(*this == RHS);
00083   }
00084 
00085   // Return the bits that make up word Idx in our element.
00086   BitWord word(unsigned Idx) const {
00087     assert (Idx < BITWORDS_PER_ELEMENT);
00088     return Bits[Idx];
00089   }
00090 
00091   unsigned index() const {
00092     return ElementIndex;
00093   }
00094 
00095   bool empty() const {
00096     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
00097       if (Bits[i])
00098         return false;
00099     return true;
00100   }
00101 
00102   void set(unsigned Idx) {
00103     Bits[Idx / BITWORD_SIZE] |= 1L << (Idx % BITWORD_SIZE);
00104   }
00105 
00106   bool test_and_set (unsigned Idx) {
00107     bool old = test(Idx);
00108     if (!old) {
00109       set(Idx);
00110       return true;
00111     }
00112     return false;
00113   }
00114 
00115   void reset(unsigned Idx) {
00116     Bits[Idx / BITWORD_SIZE] &= ~(1L << (Idx % BITWORD_SIZE));
00117   }
00118 
00119   bool test(unsigned Idx) const {
00120     return Bits[Idx / BITWORD_SIZE] & (1L << (Idx % BITWORD_SIZE));
00121   }
00122 
00123   size_type count() const {
00124     unsigned NumBits = 0;
00125     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
00126       NumBits += countPopulation(Bits[i]);
00127     return NumBits;
00128   }
00129 
00130   /// find_first - Returns the index of the first set bit.
00131   int find_first() const {
00132     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
00133       if (Bits[i] != 0)
00134         return i * BITWORD_SIZE + countTrailingZeros(Bits[i]);
00135     llvm_unreachable("Illegal empty element");
00136   }
00137 
00138   /// find_next - Returns the index of the next set bit starting from the
00139   /// "Curr" bit. Returns -1 if the next set bit is not found.
00140   int find_next(unsigned Curr) const {
00141     if (Curr >= BITS_PER_ELEMENT)
00142       return -1;
00143 
00144     unsigned WordPos = Curr / BITWORD_SIZE;
00145     unsigned BitPos = Curr % BITWORD_SIZE;
00146     BitWord Copy = Bits[WordPos];
00147     assert (WordPos <= BITWORDS_PER_ELEMENT
00148             && "Word Position outside of element");
00149 
00150     // Mask off previous bits.
00151     Copy &= ~0UL << BitPos;
00152 
00153     if (Copy != 0)
00154       return WordPos * BITWORD_SIZE + countTrailingZeros(Copy);
00155 
00156     // Check subsequent words.
00157     for (unsigned i = WordPos+1; i < BITWORDS_PER_ELEMENT; ++i)
00158       if (Bits[i] != 0)
00159         return i * BITWORD_SIZE + countTrailingZeros(Bits[i]);
00160     return -1;
00161   }
00162 
00163   // Union this element with RHS and return true if this one changed.
00164   bool unionWith(const SparseBitVectorElement &RHS) {
00165     bool changed = false;
00166     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
00167       BitWord old = changed ? 0 : Bits[i];
00168 
00169       Bits[i] |= RHS.Bits[i];
00170       if (!changed && old != Bits[i])
00171         changed = true;
00172     }
00173     return changed;
00174   }
00175 
00176   // Return true if we have any bits in common with RHS
00177   bool intersects(const SparseBitVectorElement &RHS) const {
00178     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
00179       if (RHS.Bits[i] & Bits[i])
00180         return true;
00181     }
00182     return false;
00183   }
00184 
00185   // Intersect this Element with RHS and return true if this one changed.
00186   // BecameZero is set to true if this element became all-zero bits.
00187   bool intersectWith(const SparseBitVectorElement &RHS,
00188                      bool &BecameZero) {
00189     bool changed = false;
00190     bool allzero = true;
00191 
00192     BecameZero = false;
00193     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
00194       BitWord old = changed ? 0 : Bits[i];
00195 
00196       Bits[i] &= RHS.Bits[i];
00197       if (Bits[i] != 0)
00198         allzero = false;
00199 
00200       if (!changed && old != Bits[i])
00201         changed = true;
00202     }
00203     BecameZero = allzero;
00204     return changed;
00205   }
00206 
00207   // Intersect this Element with the complement of RHS and return true if this
00208   // one changed.  BecameZero is set to true if this element became all-zero
00209   // bits.
00210   bool intersectWithComplement(const SparseBitVectorElement &RHS,
00211                                bool &BecameZero) {
00212     bool changed = false;
00213     bool allzero = true;
00214 
00215     BecameZero = false;
00216     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
00217       BitWord old = changed ? 0 : Bits[i];
00218 
00219       Bits[i] &= ~RHS.Bits[i];
00220       if (Bits[i] != 0)
00221         allzero = false;
00222 
00223       if (!changed && old != Bits[i])
00224         changed = true;
00225     }
00226     BecameZero = allzero;
00227     return changed;
00228   }
00229 
00230   // Three argument version of intersectWithComplement that intersects
00231   // RHS1 & ~RHS2 into this element
00232   void intersectWithComplement(const SparseBitVectorElement &RHS1,
00233                                const SparseBitVectorElement &RHS2,
00234                                bool &BecameZero) {
00235     bool allzero = true;
00236 
00237     BecameZero = false;
00238     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
00239       Bits[i] = RHS1.Bits[i] & ~RHS2.Bits[i];
00240       if (Bits[i] != 0)
00241         allzero = false;
00242     }
00243     BecameZero = allzero;
00244   }
00245 };
00246 
00247 template <unsigned ElementSize>
00248 struct ilist_traits<SparseBitVectorElement<ElementSize> >
00249   : public ilist_default_traits<SparseBitVectorElement<ElementSize> > {
00250   typedef SparseBitVectorElement<ElementSize> Element;
00251 
00252   Element *createSentinel() const { return static_cast<Element *>(&Sentinel); }
00253   static void destroySentinel(Element *) {}
00254 
00255   Element *provideInitialHead() const { return createSentinel(); }
00256   Element *ensureHead(Element *) const { return createSentinel(); }
00257   static void noteHead(Element *, Element *) {}
00258 
00259 private:
00260   mutable ilist_half_node<Element> Sentinel;
00261 };
00262 
00263 template <unsigned ElementSize = 128>
00264 class SparseBitVector {
00265   typedef ilist<SparseBitVectorElement<ElementSize> > ElementList;
00266   typedef typename ElementList::iterator ElementListIter;
00267   typedef typename ElementList::const_iterator ElementListConstIter;
00268   enum {
00269     BITWORD_SIZE = SparseBitVectorElement<ElementSize>::BITWORD_SIZE
00270   };
00271 
00272   // Pointer to our current Element.
00273   ElementListIter CurrElementIter;
00274   ElementList Elements;
00275 
00276   // This is like std::lower_bound, except we do linear searching from the
00277   // current position.
00278   ElementListIter FindLowerBound(unsigned ElementIndex) {
00279 
00280     if (Elements.empty()) {
00281       CurrElementIter = Elements.begin();
00282       return Elements.begin();
00283     }
00284 
00285     // Make sure our current iterator is valid.
00286     if (CurrElementIter == Elements.end())
00287       --CurrElementIter;
00288 
00289     // Search from our current iterator, either backwards or forwards,
00290     // depending on what element we are looking for.
00291     ElementListIter ElementIter = CurrElementIter;
00292     if (CurrElementIter->index() == ElementIndex) {
00293       return ElementIter;
00294     } else if (CurrElementIter->index() > ElementIndex) {
00295       while (ElementIter != Elements.begin()
00296              && ElementIter->index() > ElementIndex)
00297         --ElementIter;
00298     } else {
00299       while (ElementIter != Elements.end() &&
00300              ElementIter->index() < ElementIndex)
00301         ++ElementIter;
00302     }
00303     CurrElementIter = ElementIter;
00304     return ElementIter;
00305   }
00306 
00307   // Iterator to walk set bits in the bitmap.  This iterator is a lot uglier
00308   // than it would be, in order to be efficient.
00309   class SparseBitVectorIterator {
00310   private:
00311     bool AtEnd;
00312 
00313     const SparseBitVector<ElementSize> *BitVector;
00314 
00315     // Current element inside of bitmap.
00316     ElementListConstIter Iter;
00317 
00318     // Current bit number inside of our bitmap.
00319     unsigned BitNumber;
00320 
00321     // Current word number inside of our element.
00322     unsigned WordNumber;
00323 
00324     // Current bits from the element.
00325     typename SparseBitVectorElement<ElementSize>::BitWord Bits;
00326 
00327     // Move our iterator to the first non-zero bit in the bitmap.
00328     void AdvanceToFirstNonZero() {
00329       if (AtEnd)
00330         return;
00331       if (BitVector->Elements.empty()) {
00332         AtEnd = true;
00333         return;
00334       }
00335       Iter = BitVector->Elements.begin();
00336       BitNumber = Iter->index() * ElementSize;
00337       unsigned BitPos = Iter->find_first();
00338       BitNumber += BitPos;
00339       WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;
00340       Bits = Iter->word(WordNumber);
00341       Bits >>= BitPos % BITWORD_SIZE;
00342     }
00343 
00344     // Move our iterator to the next non-zero bit.
00345     void AdvanceToNextNonZero() {
00346       if (AtEnd)
00347         return;
00348 
00349       while (Bits && !(Bits & 1)) {
00350         Bits >>= 1;
00351         BitNumber += 1;
00352       }
00353 
00354       // See if we ran out of Bits in this word.
00355       if (!Bits) {
00356         int NextSetBitNumber = Iter->find_next(BitNumber % ElementSize) ;
00357         // If we ran out of set bits in this element, move to next element.
00358         if (NextSetBitNumber == -1 || (BitNumber % ElementSize == 0)) {
00359           ++Iter;
00360           WordNumber = 0;
00361 
00362           // We may run out of elements in the bitmap.
00363           if (Iter == BitVector->Elements.end()) {
00364             AtEnd = true;
00365             return;
00366           }
00367           // Set up for next non-zero word in bitmap.
00368           BitNumber = Iter->index() * ElementSize;
00369           NextSetBitNumber = Iter->find_first();
00370           BitNumber += NextSetBitNumber;
00371           WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;
00372           Bits = Iter->word(WordNumber);
00373           Bits >>= NextSetBitNumber % BITWORD_SIZE;
00374         } else {
00375           WordNumber = (NextSetBitNumber % ElementSize) / BITWORD_SIZE;
00376           Bits = Iter->word(WordNumber);
00377           Bits >>= NextSetBitNumber % BITWORD_SIZE;
00378           BitNumber = Iter->index() * ElementSize;
00379           BitNumber += NextSetBitNumber;
00380         }
00381       }
00382     }
00383   public:
00384     // Preincrement.
00385     inline SparseBitVectorIterator& operator++() {
00386       ++BitNumber;
00387       Bits >>= 1;
00388       AdvanceToNextNonZero();
00389       return *this;
00390     }
00391 
00392     // Postincrement.
00393     inline SparseBitVectorIterator operator++(int) {
00394       SparseBitVectorIterator tmp = *this;
00395       ++*this;
00396       return tmp;
00397     }
00398 
00399     // Return the current set bit number.
00400     unsigned operator*() const {
00401       return BitNumber;
00402     }
00403 
00404     bool operator==(const SparseBitVectorIterator &RHS) const {
00405       // If they are both at the end, ignore the rest of the fields.
00406       if (AtEnd && RHS.AtEnd)
00407         return true;
00408       // Otherwise they are the same if they have the same bit number and
00409       // bitmap.
00410       return AtEnd == RHS.AtEnd && RHS.BitNumber == BitNumber;
00411     }
00412 
00413     bool operator!=(const SparseBitVectorIterator &RHS) const {
00414       return !(*this == RHS);
00415     }
00416 
00417     SparseBitVectorIterator(): BitVector(nullptr) {
00418     }
00419 
00420     SparseBitVectorIterator(const SparseBitVector<ElementSize> *RHS,
00421                             bool end = false):BitVector(RHS) {
00422       Iter = BitVector->Elements.begin();
00423       BitNumber = 0;
00424       Bits = 0;
00425       WordNumber = ~0;
00426       AtEnd = end;
00427       AdvanceToFirstNonZero();
00428     }
00429   };
00430 public:
00431   typedef SparseBitVectorIterator iterator;
00432 
00433   SparseBitVector () {
00434     CurrElementIter = Elements.begin ();
00435   }
00436 
00437   ~SparseBitVector() {
00438   }
00439 
00440   // SparseBitVector copy ctor.
00441   SparseBitVector(const SparseBitVector &RHS) {
00442     ElementListConstIter ElementIter = RHS.Elements.begin();
00443     while (ElementIter != RHS.Elements.end()) {
00444       Elements.push_back(SparseBitVectorElement<ElementSize>(*ElementIter));
00445       ++ElementIter;
00446     }
00447 
00448     CurrElementIter = Elements.begin ();
00449   }
00450 
00451   // Clear.
00452   void clear() {
00453     Elements.clear();
00454   }
00455 
00456   // Assignment
00457   SparseBitVector& operator=(const SparseBitVector& RHS) {
00458     if (this == &RHS)
00459       return *this;
00460 
00461     Elements.clear();
00462 
00463     ElementListConstIter ElementIter = RHS.Elements.begin();
00464     while (ElementIter != RHS.Elements.end()) {
00465       Elements.push_back(SparseBitVectorElement<ElementSize>(*ElementIter));
00466       ++ElementIter;
00467     }
00468 
00469     CurrElementIter = Elements.begin ();
00470 
00471     return *this;
00472   }
00473 
00474   // Test, Reset, and Set a bit in the bitmap.
00475   bool test(unsigned Idx) {
00476     if (Elements.empty())
00477       return false;
00478 
00479     unsigned ElementIndex = Idx / ElementSize;
00480     ElementListIter ElementIter = FindLowerBound(ElementIndex);
00481 
00482     // If we can't find an element that is supposed to contain this bit, there
00483     // is nothing more to do.
00484     if (ElementIter == Elements.end() ||
00485         ElementIter->index() != ElementIndex)
00486       return false;
00487     return ElementIter->test(Idx % ElementSize);
00488   }
00489 
00490   void reset(unsigned Idx) {
00491     if (Elements.empty())
00492       return;
00493 
00494     unsigned ElementIndex = Idx / ElementSize;
00495     ElementListIter ElementIter = FindLowerBound(ElementIndex);
00496 
00497     // If we can't find an element that is supposed to contain this bit, there
00498     // is nothing more to do.
00499     if (ElementIter == Elements.end() ||
00500         ElementIter->index() != ElementIndex)
00501       return;
00502     ElementIter->reset(Idx % ElementSize);
00503 
00504     // When the element is zeroed out, delete it.
00505     if (ElementIter->empty()) {
00506       ++CurrElementIter;
00507       Elements.erase(ElementIter);
00508     }
00509   }
00510 
00511   void set(unsigned Idx) {
00512     unsigned ElementIndex = Idx / ElementSize;
00513     SparseBitVectorElement<ElementSize> *Element;
00514     ElementListIter ElementIter;
00515     if (Elements.empty()) {
00516       Element = new SparseBitVectorElement<ElementSize>(ElementIndex);
00517       ElementIter = Elements.insert(Elements.end(), Element);
00518 
00519     } else {
00520       ElementIter = FindLowerBound(ElementIndex);
00521 
00522       if (ElementIter == Elements.end() ||
00523           ElementIter->index() != ElementIndex) {
00524         Element = new SparseBitVectorElement<ElementSize>(ElementIndex);
00525         // We may have hit the beginning of our SparseBitVector, in which case,
00526         // we may need to insert right after this element, which requires moving
00527         // the current iterator forward one, because insert does insert before.
00528         if (ElementIter != Elements.end() &&
00529             ElementIter->index() < ElementIndex)
00530           ElementIter = Elements.insert(++ElementIter, Element);
00531         else
00532           ElementIter = Elements.insert(ElementIter, Element);
00533       }
00534     }
00535     CurrElementIter = ElementIter;
00536 
00537     ElementIter->set(Idx % ElementSize);
00538   }
00539 
00540   bool test_and_set (unsigned Idx) {
00541     bool old = test(Idx);
00542     if (!old) {
00543       set(Idx);
00544       return true;
00545     }
00546     return false;
00547   }
00548 
00549   bool operator!=(const SparseBitVector &RHS) const {
00550     return !(*this == RHS);
00551   }
00552 
00553   bool operator==(const SparseBitVector &RHS) const {
00554     ElementListConstIter Iter1 = Elements.begin();
00555     ElementListConstIter Iter2 = RHS.Elements.begin();
00556 
00557     for (; Iter1 != Elements.end() && Iter2 != RHS.Elements.end();
00558          ++Iter1, ++Iter2) {
00559       if (*Iter1 != *Iter2)
00560         return false;
00561     }
00562     return Iter1 == Elements.end() && Iter2 == RHS.Elements.end();
00563   }
00564 
00565   // Union our bitmap with the RHS and return true if we changed.
00566   bool operator|=(const SparseBitVector &RHS) {
00567     if (this == &RHS)
00568       return false;
00569 
00570     bool changed = false;
00571     ElementListIter Iter1 = Elements.begin();
00572     ElementListConstIter Iter2 = RHS.Elements.begin();
00573 
00574     // If RHS is empty, we are done
00575     if (RHS.Elements.empty())
00576       return false;
00577 
00578     while (Iter2 != RHS.Elements.end()) {
00579       if (Iter1 == Elements.end() || Iter1->index() > Iter2->index()) {
00580         Elements.insert(Iter1,
00581                         new SparseBitVectorElement<ElementSize>(*Iter2));
00582         ++Iter2;
00583         changed = true;
00584       } else if (Iter1->index() == Iter2->index()) {
00585         changed |= Iter1->unionWith(*Iter2);
00586         ++Iter1;
00587         ++Iter2;
00588       } else {
00589         ++Iter1;
00590       }
00591     }
00592     CurrElementIter = Elements.begin();
00593     return changed;
00594   }
00595 
00596   // Intersect our bitmap with the RHS and return true if ours changed.
00597   bool operator&=(const SparseBitVector &RHS) {
00598     if (this == &RHS)
00599       return false;
00600 
00601     bool changed = false;
00602     ElementListIter Iter1 = Elements.begin();
00603     ElementListConstIter Iter2 = RHS.Elements.begin();
00604 
00605     // Check if both bitmaps are empty.
00606     if (Elements.empty() && RHS.Elements.empty())
00607       return false;
00608 
00609     // Loop through, intersecting as we go, erasing elements when necessary.
00610     while (Iter2 != RHS.Elements.end()) {
00611       if (Iter1 == Elements.end()) {
00612         CurrElementIter = Elements.begin();
00613         return changed;
00614       }
00615 
00616       if (Iter1->index() > Iter2->index()) {
00617         ++Iter2;
00618       } else if (Iter1->index() == Iter2->index()) {
00619         bool BecameZero;
00620         changed |= Iter1->intersectWith(*Iter2, BecameZero);
00621         if (BecameZero) {
00622           ElementListIter IterTmp = Iter1;
00623           ++Iter1;
00624           Elements.erase(IterTmp);
00625         } else {
00626           ++Iter1;
00627         }
00628         ++Iter2;
00629       } else {
00630         ElementListIter IterTmp = Iter1;
00631         ++Iter1;
00632         Elements.erase(IterTmp);
00633         changed = true;
00634       }
00635     }
00636     if (Iter1 != Elements.end()) {
00637       Elements.erase(Iter1, Elements.end());
00638       changed = true;
00639     }
00640     CurrElementIter = Elements.begin();
00641     return changed;
00642   }
00643 
00644   // Intersect our bitmap with the complement of the RHS and return true
00645   // if ours changed.
00646   bool intersectWithComplement(const SparseBitVector &RHS) {
00647     if (this == &RHS) {
00648       if (!empty()) {
00649         clear();
00650         return true;
00651       }
00652       return false;
00653     }
00654 
00655     bool changed = false;
00656     ElementListIter Iter1 = Elements.begin();
00657     ElementListConstIter Iter2 = RHS.Elements.begin();
00658 
00659     // If either our bitmap or RHS is empty, we are done
00660     if (Elements.empty() || RHS.Elements.empty())
00661       return false;
00662 
00663     // Loop through, intersecting as we go, erasing elements when necessary.
00664     while (Iter2 != RHS.Elements.end()) {
00665       if (Iter1 == Elements.end()) {
00666         CurrElementIter = Elements.begin();
00667         return changed;
00668       }
00669 
00670       if (Iter1->index() > Iter2->index()) {
00671         ++Iter2;
00672       } else if (Iter1->index() == Iter2->index()) {
00673         bool BecameZero;
00674         changed |= Iter1->intersectWithComplement(*Iter2, BecameZero);
00675         if (BecameZero) {
00676           ElementListIter IterTmp = Iter1;
00677           ++Iter1;
00678           Elements.erase(IterTmp);
00679         } else {
00680           ++Iter1;
00681         }
00682         ++Iter2;
00683       } else {
00684         ++Iter1;
00685       }
00686     }
00687     CurrElementIter = Elements.begin();
00688     return changed;
00689   }
00690 
00691   bool intersectWithComplement(const SparseBitVector<ElementSize> *RHS) const {
00692     return intersectWithComplement(*RHS);
00693   }
00694 
00695   //  Three argument version of intersectWithComplement.
00696   //  Result of RHS1 & ~RHS2 is stored into this bitmap.
00697   void intersectWithComplement(const SparseBitVector<ElementSize> &RHS1,
00698                                const SparseBitVector<ElementSize> &RHS2)
00699   {
00700     if (this == &RHS1) {
00701       intersectWithComplement(RHS2);
00702       return;
00703     } else if (this == &RHS2) {
00704       SparseBitVector RHS2Copy(RHS2);
00705       intersectWithComplement(RHS1, RHS2Copy);
00706       return;
00707     }
00708 
00709     Elements.clear();
00710     CurrElementIter = Elements.begin();
00711     ElementListConstIter Iter1 = RHS1.Elements.begin();
00712     ElementListConstIter Iter2 = RHS2.Elements.begin();
00713 
00714     // If RHS1 is empty, we are done
00715     // If RHS2 is empty, we still have to copy RHS1
00716     if (RHS1.Elements.empty())
00717       return;
00718 
00719     // Loop through, intersecting as we go, erasing elements when necessary.
00720     while (Iter2 != RHS2.Elements.end()) {
00721       if (Iter1 == RHS1.Elements.end())
00722         return;
00723 
00724       if (Iter1->index() > Iter2->index()) {
00725         ++Iter2;
00726       } else if (Iter1->index() == Iter2->index()) {
00727         bool BecameZero = false;
00728         SparseBitVectorElement<ElementSize> *NewElement =
00729           new SparseBitVectorElement<ElementSize>(Iter1->index());
00730         NewElement->intersectWithComplement(*Iter1, *Iter2, BecameZero);
00731         if (!BecameZero) {
00732           Elements.push_back(NewElement);
00733         }
00734         else
00735           delete NewElement;
00736         ++Iter1;
00737         ++Iter2;
00738       } else {
00739         SparseBitVectorElement<ElementSize> *NewElement =
00740           new SparseBitVectorElement<ElementSize>(*Iter1);
00741         Elements.push_back(NewElement);
00742         ++Iter1;
00743       }
00744     }
00745 
00746     // copy the remaining elements
00747     while (Iter1 != RHS1.Elements.end()) {
00748         SparseBitVectorElement<ElementSize> *NewElement =
00749           new SparseBitVectorElement<ElementSize>(*Iter1);
00750         Elements.push_back(NewElement);
00751         ++Iter1;
00752       }
00753   }
00754 
00755   void intersectWithComplement(const SparseBitVector<ElementSize> *RHS1,
00756                                const SparseBitVector<ElementSize> *RHS2) {
00757     intersectWithComplement(*RHS1, *RHS2);
00758   }
00759 
00760   bool intersects(const SparseBitVector<ElementSize> *RHS) const {
00761     return intersects(*RHS);
00762   }
00763 
00764   // Return true if we share any bits in common with RHS
00765   bool intersects(const SparseBitVector<ElementSize> &RHS) const {
00766     ElementListConstIter Iter1 = Elements.begin();
00767     ElementListConstIter Iter2 = RHS.Elements.begin();
00768 
00769     // Check if both bitmaps are empty.
00770     if (Elements.empty() && RHS.Elements.empty())
00771       return false;
00772 
00773     // Loop through, intersecting stopping when we hit bits in common.
00774     while (Iter2 != RHS.Elements.end()) {
00775       if (Iter1 == Elements.end())
00776         return false;
00777 
00778       if (Iter1->index() > Iter2->index()) {
00779         ++Iter2;
00780       } else if (Iter1->index() == Iter2->index()) {
00781         if (Iter1->intersects(*Iter2))
00782           return true;
00783         ++Iter1;
00784         ++Iter2;
00785       } else {
00786         ++Iter1;
00787       }
00788     }
00789     return false;
00790   }
00791 
00792   // Return true iff all bits set in this SparseBitVector are
00793   // also set in RHS.
00794   bool contains(const SparseBitVector<ElementSize> &RHS) const {
00795     SparseBitVector<ElementSize> Result(*this);
00796     Result &= RHS;
00797     return (Result == RHS);
00798   }
00799 
00800   // Return the first set bit in the bitmap.  Return -1 if no bits are set.
00801   int find_first() const {
00802     if (Elements.empty())
00803       return -1;
00804     const SparseBitVectorElement<ElementSize> &First = *(Elements.begin());
00805     return (First.index() * ElementSize) + First.find_first();
00806   }
00807 
00808   // Return true if the SparseBitVector is empty
00809   bool empty() const {
00810     return Elements.empty();
00811   }
00812 
00813   unsigned count() const {
00814     unsigned BitCount = 0;
00815     for (ElementListConstIter Iter = Elements.begin();
00816          Iter != Elements.end();
00817          ++Iter)
00818       BitCount += Iter->count();
00819 
00820     return BitCount;
00821   }
00822   iterator begin() const {
00823     return iterator(this);
00824   }
00825 
00826   iterator end() const {
00827     return iterator(this, true);
00828   }
00829 };
00830 
00831 // Convenience functions to allow Or and And without dereferencing in the user
00832 // code.
00833 
00834 template <unsigned ElementSize>
00835 inline bool operator |=(SparseBitVector<ElementSize> &LHS,
00836                         const SparseBitVector<ElementSize> *RHS) {
00837   return LHS |= *RHS;
00838 }
00839 
00840 template <unsigned ElementSize>
00841 inline bool operator |=(SparseBitVector<ElementSize> *LHS,
00842                         const SparseBitVector<ElementSize> &RHS) {
00843   return LHS->operator|=(RHS);
00844 }
00845 
00846 template <unsigned ElementSize>
00847 inline bool operator &=(SparseBitVector<ElementSize> *LHS,
00848                         const SparseBitVector<ElementSize> &RHS) {
00849   return LHS->operator&=(RHS);
00850 }
00851 
00852 template <unsigned ElementSize>
00853 inline bool operator &=(SparseBitVector<ElementSize> &LHS,
00854                         const SparseBitVector<ElementSize> *RHS) {
00855   return LHS &= *RHS;
00856 }
00857 
00858 // Convenience functions for infix union, intersection, difference operators.
00859 
00860 template <unsigned ElementSize>
00861 inline SparseBitVector<ElementSize>
00862 operator|(const SparseBitVector<ElementSize> &LHS,
00863           const SparseBitVector<ElementSize> &RHS) {
00864   SparseBitVector<ElementSize> Result(LHS);
00865   Result |= RHS;
00866   return Result;
00867 }
00868 
00869 template <unsigned ElementSize>
00870 inline SparseBitVector<ElementSize>
00871 operator&(const SparseBitVector<ElementSize> &LHS,
00872           const SparseBitVector<ElementSize> &RHS) {
00873   SparseBitVector<ElementSize> Result(LHS);
00874   Result &= RHS;
00875   return Result;
00876 }
00877 
00878 template <unsigned ElementSize>
00879 inline SparseBitVector<ElementSize>
00880 operator-(const SparseBitVector<ElementSize> &LHS,
00881           const SparseBitVector<ElementSize> &RHS) {
00882   SparseBitVector<ElementSize> Result;
00883   Result.intersectWithComplement(LHS, RHS);
00884   return Result;
00885 }
00886 
00887 // Dump a SparseBitVector to a stream
00888 template <unsigned ElementSize>
00889 void dump(const SparseBitVector<ElementSize> &LHS, raw_ostream &out) {
00890   out << "[";
00891 
00892   typename SparseBitVector<ElementSize>::iterator bi = LHS.begin(),
00893     be = LHS.end();
00894   if (bi != be) {
00895     out << *bi;
00896     for (++bi; bi != be; ++bi) {
00897       out << " " << *bi;
00898     }
00899   }
00900   out << "]\n";
00901 }
00902 } // end namespace llvm
00903 
00904 #endif // LLVM_ADT_SPARSEBITVECTOR_H