diff options
Diffstat (limited to 'include/llvm')
-rw-r--r-- | include/llvm/ADT/DenseMap.h | 10 | ||||
-rw-r--r-- | include/llvm/ADT/SparseBitVector.h | 39 |
2 files changed, 35 insertions, 14 deletions
diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h index 0b9cddf..78d8f83 100644 --- a/include/llvm/ADT/DenseMap.h +++ b/include/llvm/ADT/DenseMap.h @@ -99,6 +99,9 @@ public: bool empty() const { return NumEntries == 0; } unsigned size() const { return NumEntries; } + + /// Grow the densemap so that it has at least Size buckets. Does not shrink + void resize(size_t Size) { grow(Size); } void clear() { // If the capacity of the array is huge, and the # elements used is small, @@ -228,7 +231,7 @@ private: // causing infinite loops in lookup. if (NumEntries*4 >= NumBuckets*3 || NumBuckets-(NumEntries+NumTombstones) < NumBuckets/8) { - this->grow(); + this->grow(NumBuckets * 2); LookupBucketFor(Key, TheBucket); } ++NumEntries; @@ -310,12 +313,13 @@ private: new (&Buckets[i].first) KeyT(EmptyKey); } - void grow() { + void grow(unsigned AtLeast) { unsigned OldNumBuckets = NumBuckets; BucketT *OldBuckets = Buckets; // Double the number of buckets. - NumBuckets <<= 1; + while (NumBuckets <= AtLeast) + NumBuckets <<= 1; NumTombstones = 0; Buckets = reinterpret_cast<BucketT*>(new char[sizeof(BucketT)*NumBuckets]); 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 |