X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FSparseBitVector.h;h=e6e72413da4ed5815cb81488d728d347e7014769;hb=df7186636e51e63281bd318234b7d97f25efe491;hp=66a561323778fb898fe2da81f4ed0e741d233528;hpb=7e2c793a2b5c746344652b6579e958ee42fafdcc;p=oota-llvm.git diff --git a/include/llvm/ADT/SparseBitVector.h b/include/llvm/ADT/SparseBitVector.h index 66a56132377..e6e72413da4 100644 --- a/include/llvm/ADT/SparseBitVector.h +++ b/include/llvm/ADT/SparseBitVector.h @@ -39,12 +39,12 @@ namespace llvm { /// etc) do not perform as well in practice as a linked list with this iterator /// kept up to date. They are also significantly more memory intensive. - template struct SparseBitVectorElement : public ilist_node > { public: typedef unsigned long BitWord; + typedef unsigned size_type; enum { BITWORD_SIZE = sizeof(BitWord) * CHAR_BIT, BITWORDS_PER_ELEMENT = (ElementSize + BITWORD_SIZE - 1) / BITWORD_SIZE, @@ -120,28 +120,18 @@ public: return Bits[Idx / BITWORD_SIZE] & (1L << (Idx % BITWORD_SIZE)); } - unsigned count() const { + size_type count() const { unsigned NumBits = 0; for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) - if (sizeof(BitWord) == 4) - NumBits += CountPopulation_32(Bits[i]); - else if (sizeof(BitWord) == 8) - NumBits += CountPopulation_64(Bits[i]); - else - llvm_unreachable("Unsupported!"); + NumBits += countPopulation(Bits[i]); return NumBits; } /// find_first - Returns the index of the first set bit. int find_first() const { for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) - if (Bits[i] != 0) { - if (sizeof(BitWord) == 4) - return i * BITWORD_SIZE + CountTrailingZeros_32(Bits[i]); - if (sizeof(BitWord) == 8) - return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]); - llvm_unreachable("Unsupported!"); - } + if (Bits[i] != 0) + return i * BITWORD_SIZE + countTrailingZeros(Bits[i]); llvm_unreachable("Illegal empty element"); } @@ -160,23 +150,13 @@ public: // Mask off previous bits. Copy &= ~0UL << BitPos; - if (Copy != 0) { - if (sizeof(BitWord) == 4) - return WordPos * BITWORD_SIZE + CountTrailingZeros_32(Copy); - if (sizeof(BitWord) == 8) - return WordPos * BITWORD_SIZE + CountTrailingZeros_64(Copy); - llvm_unreachable("Unsupported!"); - } + if (Copy != 0) + return WordPos * BITWORD_SIZE + countTrailingZeros(Copy); // Check subsequent words. for (unsigned i = WordPos+1; i < BITWORDS_PER_ELEMENT; ++i) - if (Bits[i] != 0) { - if (sizeof(BitWord) == 4) - return i * BITWORD_SIZE + CountTrailingZeros_32(Bits[i]); - if (sizeof(BitWord) == 8) - return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]); - llvm_unreachable("Unsupported!"); - } + if (Bits[i] != 0) + return i * BITWORD_SIZE + countTrailingZeros(Bits[i]); return -1; } @@ -223,6 +203,7 @@ public: BecameZero = allzero; return changed; } + // Intersect this Element with the complement of RHS and return true if this // one changed. BecameZero is set to true if this element became all-zero // bits. @@ -245,6 +226,7 @@ public: BecameZero = allzero; return changed; } + // Three argument version of intersectWithComplement that intersects // RHS1 & ~RHS2 into this element void intersectWithComplement(const SparseBitVectorElement &RHS1, @@ -262,6 +244,22 @@ public: } }; +template +struct ilist_traits > + : public ilist_default_traits > { + typedef SparseBitVectorElement Element; + + Element *createSentinel() const { return static_cast(&Sentinel); } + static void destroySentinel(Element *) {} + + Element *provideInitialHead() const { return createSentinel(); } + Element *ensureHead(Element *) const { return createSentinel(); } + static void noteHead(Element *, Element *) {} + +private: + mutable ilist_half_node Sentinel; +}; + template class SparseBitVector { typedef ilist > ElementList; @@ -366,7 +364,7 @@ class SparseBitVector { AtEnd = true; return; } - // Set up for next non zero word in bitmap. + // Set up for next non-zero word in bitmap. BitNumber = Iter->index() * ElementSize; NextSetBitNumber = Iter->find_first(); BitNumber += NextSetBitNumber; @@ -411,12 +409,13 @@ class SparseBitVector { // bitmap. return AtEnd == RHS.AtEnd && RHS.BitNumber == BitNumber; } + bool operator!=(const SparseBitVectorIterator &RHS) const { return !(*this == RHS); } - SparseBitVectorIterator(): BitVector(NULL) { - } + SparseBitVectorIterator(): BitVector(nullptr) { + } SparseBitVectorIterator(const SparseBitVector *RHS, bool end = false):BitVector(RHS) { @@ -456,6 +455,9 @@ public: // Assignment SparseBitVector& operator=(const SparseBitVector& RHS) { + if (this == &RHS) + return *this; + Elements.clear(); ElementListConstIter ElementIter = RHS.Elements.begin(); @@ -562,6 +564,9 @@ public: // Union our bitmap with the RHS and return true if we changed. bool operator|=(const SparseBitVector &RHS) { + if (this == &RHS) + return false; + bool changed = false; ElementListIter Iter1 = Elements.begin(); ElementListConstIter Iter2 = RHS.Elements.begin(); @@ -590,6 +595,9 @@ public: // Intersect our bitmap with the RHS and return true if ours changed. bool operator&=(const SparseBitVector &RHS) { + if (this == &RHS) + return false; + bool changed = false; ElementListIter Iter1 = Elements.begin(); ElementListConstIter Iter2 = RHS.Elements.begin(); @@ -622,9 +630,13 @@ public: ElementListIter IterTmp = Iter1; ++Iter1; Elements.erase(IterTmp); + changed = true; } } - Elements.erase(Iter1, Elements.end()); + if (Iter1 != Elements.end()) { + Elements.erase(Iter1, Elements.end()); + changed = true; + } CurrElementIter = Elements.begin(); return changed; } @@ -632,6 +644,14 @@ public: // Intersect our bitmap with the complement of the RHS and return true // if ours changed. bool intersectWithComplement(const SparseBitVector &RHS) { + if (this == &RHS) { + if (!empty()) { + clear(); + return true; + } + return false; + } + bool changed = false; ElementListIter Iter1 = Elements.begin(); ElementListConstIter Iter2 = RHS.Elements.begin(); @@ -672,12 +692,20 @@ public: return intersectWithComplement(*RHS); } - // Three argument version of intersectWithComplement. // Result of RHS1 & ~RHS2 is stored into this bitmap. void intersectWithComplement(const SparseBitVector &RHS1, const SparseBitVector &RHS2) { + if (this == &RHS1) { + intersectWithComplement(RHS2); + return; + } else if (this == &RHS2) { + SparseBitVector RHS2Copy(RHS2); + intersectWithComplement(RHS1, RHS2Copy); + return; + } + Elements.clear(); CurrElementIter = Elements.begin(); ElementListConstIter Iter1 = RHS1.Elements.begin(); @@ -722,8 +750,6 @@ public: Elements.push_back(NewElement); ++Iter1; } - - return; } void intersectWithComplement(const SparseBitVector *RHS1, @@ -763,7 +789,7 @@ public: return false; } - // Return true if all bits set in this SparseBitVector are + // Return true iff all bits set in this SparseBitVector are // also set in RHS. bool contains(const SparseBitVector &RHS) const { SparseBitVector Result(*this); @@ -858,9 +884,6 @@ operator-(const SparseBitVector &LHS, return Result; } - - - // Dump a SparseBitVector to a stream template void dump(const SparseBitVector &LHS, raw_ostream &out) { @@ -878,4 +901,4 @@ void dump(const SparseBitVector &LHS, raw_ostream &out) { } } // end namespace llvm -#endif +#endif // LLVM_ADT_SPARSEBITVECTOR_H