LLVM API Documentation

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