X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FSparseBitVector.h;h=306e92832f0b0fd43b64e4f2dd6bdf83c3f483d4;hb=6cd738f33934a93b114d7dd9e4291f87f445c5c4;hp=72627b195c578456ee731ea8861daebd0278c34e;hpb=b9cfbd94abb23ec8646b9b10aa4ac3d1cbf4461e;p=oota-llvm.git diff --git a/include/llvm/ADT/SparseBitVector.h b/include/llvm/ADT/SparseBitVector.h index 72627b195c5..306e92832f0 100644 --- a/include/llvm/ADT/SparseBitVector.h +++ b/include/llvm/ADT/SparseBitVector.h @@ -15,13 +15,14 @@ #ifndef LLVM_ADT_SPARSEBITVECTOR_H #define LLVM_ADT_SPARSEBITVECTOR_H -#include -#include -#include +#include "llvm/ADT/ilist.h" +#include "llvm/ADT/ilist_node.h" #include "llvm/Support/DataTypes.h" -#include "llvm/ADT/STLExtras.h" +#include "llvm/Support/ErrorHandling.h" #include "llvm/Support/MathExtras.h" -#include "llvm/ADT/ilist.h" +#include "llvm/Support/raw_ostream.h" +#include +#include namespace llvm { @@ -41,7 +42,7 @@ namespace llvm { template struct SparseBitVectorElement - : ilist_node > { + : public ilist_node > { public: typedef unsigned long BitWord; enum { @@ -55,7 +56,7 @@ private: unsigned ElementIndex; BitWord Bits[BITWORDS_PER_ELEMENT]; // Needed for sentinels - friend class ilist_sentinel_traits; + friend struct ilist_sentinel_traits; SparseBitVectorElement() { ElementIndex = ~0U; memset(&Bits[0], 0, sizeof (BitWord) * BITWORDS_PER_ELEMENT); @@ -127,7 +128,7 @@ public: else if (sizeof(BitWord) == 8) NumBits += CountPopulation_64(Bits[i]); else - assert(0 && "Unsupported!"); + llvm_unreachable("Unsupported!"); return NumBits; } @@ -137,13 +138,11 @@ public: if (Bits[i] != 0) { if (sizeof(BitWord) == 4) return i * BITWORD_SIZE + CountTrailingZeros_32(Bits[i]); - else if (sizeof(BitWord) == 8) + if (sizeof(BitWord) == 8) return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]); - else - assert(0 && "Unsupported!"); + llvm_unreachable("Unsupported!"); } - assert(0 && "Illegal empty element"); - return 0; // Not reached + llvm_unreachable("Illegal empty element"); } /// find_next - Returns the index of the next set bit starting from the @@ -159,15 +158,14 @@ public: && "Word Position outside of element"); // Mask off previous bits. - Copy &= ~0L << BitPos; + Copy &= ~0UL << BitPos; if (Copy != 0) { if (sizeof(BitWord) == 4) return WordPos * BITWORD_SIZE + CountTrailingZeros_32(Copy); - else if (sizeof(BitWord) == 8) + if (sizeof(BitWord) == 8) return WordPos * BITWORD_SIZE + CountTrailingZeros_64(Copy); - else - assert(0 && "Unsupported!"); + llvm_unreachable("Unsupported!"); } // Check subsequent words. @@ -175,10 +173,9 @@ public: if (Bits[i] != 0) { if (sizeof(BitWord) == 4) return i * BITWORD_SIZE + CountTrailingZeros_32(Bits[i]); - else if (sizeof(BitWord) == 8) + if (sizeof(BitWord) == 8) return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]); - else - assert(0 && "Unsupported!"); + llvm_unreachable("Unsupported!"); } return -1; } @@ -263,15 +260,22 @@ public: } BecameZero = allzero; } +}; - // Get a hash value for this element; - uint64_t getHashValue() const { - uint64_t HashVal = 0; - for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) { - HashVal ^= Bits[i]; - } - return HashVal; - } +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 @@ -812,18 +816,6 @@ public: iterator end() const { return iterator(this, true); } - - // Get a hash value for this bitmap. - uint64_t getHashValue() const { - uint64_t HashVal = 0; - for (ElementListConstIter Iter = Elements.begin(); - Iter != Elements.end(); - ++Iter) { - HashVal ^= Iter->index(); - HashVal ^= Iter->getHashValue(); - } - return HashVal; - } }; // Convenience functions to allow Or and And without dereferencing in the user @@ -887,14 +879,18 @@ operator-(const SparseBitVector &LHS, // Dump a SparseBitVector to a stream template -void dump(const SparseBitVector &LHS, llvm::OStream &out) { - out << "[ "; - - typename SparseBitVector::iterator bi; - for (bi = LHS.begin(); bi != LHS.end(); ++bi) { - out << *bi << " "; +void dump(const SparseBitVector &LHS, raw_ostream &out) { + out << "["; + + typename SparseBitVector::iterator bi = LHS.begin(), + be = LHS.end(); + if (bi != be) { + out << *bi; + for (++bi; bi != be; ++bi) { + out << " " << *bi; + } } - out << " ]\n"; + out << "]\n"; } } // end namespace llvm