diff options
author | Daniel Berlin <dberlin@dberlin.org> | 2007-09-24 19:45:49 +0000 |
---|---|---|
committer | Daniel Berlin <dberlin@dberlin.org> | 2007-09-24 19:45:49 +0000 |
commit | d81ccc2806b2c8a498d16f1a547d0cc9c00d602d (patch) | |
tree | 95400ab1d7b0337d79d0faad1406168e13b960d0 /include/llvm/ADT/SparseBitVector.h | |
parent | 6b5766e27c402741b81725fc3bbc3ee234098194 (diff) | |
download | external_llvm-d81ccc2806b2c8a498d16f1a547d0cc9c00d602d.zip external_llvm-d81ccc2806b2c8a498d16f1a547d0cc9c00d602d.tar.gz external_llvm-d81ccc2806b2c8a498d16f1a547d0cc9c00d602d.tar.bz2 |
Implement offline variable substitution in order to reduce memory
and time usage.
Fixup operator == to make this work, and add a resize method to DenseMap
so we can resize our hashtable once we know how big it should be.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42269 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'include/llvm/ADT/SparseBitVector.h')
-rw-r--r-- | include/llvm/ADT/SparseBitVector.h | 39 |
1 files changed, 28 insertions, 11 deletions
diff --git a/include/llvm/ADT/SparseBitVector.h b/include/llvm/ADT/SparseBitVector.h index 6462688..9743970 100644 --- a/include/llvm/ADT/SparseBitVector.h +++ b/include/llvm/ADT/SparseBitVector.h @@ -75,7 +75,6 @@ private: } friend struct ilist_traits<SparseBitVectorElement<ElementSize> >; - public: explicit SparseBitVectorElement(unsigned Idx) { ElementIndex = Idx; @@ -287,6 +286,14 @@ 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 <unsigned ElementSize = 128> @@ -544,22 +551,20 @@ public: return false; } - bool operator!=(const SparseBitVector &RHS) { + bool operator!=(const SparseBitVector &RHS) const { return !(*this == RHS); } - bool operator==(const SparseBitVector &RHS) { + bool operator==(const SparseBitVector &RHS) const { ElementListConstIter Iter1 = Elements.begin(); ElementListConstIter Iter2 = RHS.Elements.begin(); - while (Iter2 != RHS.Elements.end()) { - if (Iter1->index() != Iter2->index() - || *Iter1 != *Iter2) + for (; Iter1 != Elements.end() && Iter2 != RHS.Elements.end(); + ++Iter1, ++Iter2) { + if (*Iter1 != *Iter2) return false; - ++Iter1; - ++Iter2; } - return Iter1 == Elements.end(); + return Iter1 == Elements.end() && Iter2 == RHS.Elements.end(); } // Union our bitmap with the RHS and return true if we changed. @@ -789,6 +794,17 @@ public: return iterator(this, ~0); } + // 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 @@ -828,9 +844,10 @@ void dump(const SparseBitVector<ElementSize> &LHS, llvm::OStream &out) { for (bi = LHS.begin(); bi != LHS.end(); ++bi) { out << *bi << " "; } - out << "\n"; + out << " ]\n"; } - } + + #endif |