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