LLVM API Documentation
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