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