diff options
| -rw-r--r-- | include/llvm/ADT/DenseMap.h | 2 | ||||
| -rw-r--r-- | include/llvm/ADT/SmallPtrSet.h | 10 | ||||
| -rw-r--r-- | lib/Support/SmallPtrSet.cpp | 18 |
3 files changed, 28 insertions, 2 deletions
diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h index 78caba52a5..8b25a82e6a 100644 --- a/include/llvm/ADT/DenseMap.h +++ b/include/llvm/ADT/DenseMap.h @@ -91,6 +91,8 @@ public: unsigned size() const { return NumEntries; } void clear() { + // If the capacity of the array is huge, and the # elements used is small, + // shrink the array. if (NumEntries * 4 < NumBuckets && NumBuckets > 64) { shrink_and_clear(); return; diff --git a/include/llvm/ADT/SmallPtrSet.h b/include/llvm/ADT/SmallPtrSet.h index e39a4fe706..2ff7de448f 100644 --- a/include/llvm/ADT/SmallPtrSet.h +++ b/include/llvm/ADT/SmallPtrSet.h @@ -80,6 +80,11 @@ public: } void clear() { + // If the capacity of the array is huge, and the # elements used is small, + // shrink the array. + if (!isSmall() && NumElements*4 < CurArraySize && CurArraySize > 32) + return shrink_and_clear(); + // Fill the array with empty markers. memset(CurArray, -1, CurArraySize*sizeof(void*)); NumElements = 0; @@ -103,8 +108,8 @@ public: bool count(void * const Ptr) const { if (isSmall()) { // Linear search for the item. - for (const void *const *APtr = SmallArray, *const *E = SmallArray+NumElements; - APtr != E; ++APtr) + for (const void *const *APtr = SmallArray, + *const *E = SmallArray+NumElements; APtr != E; ++APtr) if (*APtr == Ptr) return true; return false; @@ -121,6 +126,7 @@ private: return ((uintptr_t)Ptr >> 4) & (CurArraySize-1); } const void * const *FindBucketFor(const void *Ptr) const; + void shrink_and_clear(); /// Grow - Allocate a larger backing store for the buckets and move it over. void Grow(); diff --git a/lib/Support/SmallPtrSet.cpp b/lib/Support/SmallPtrSet.cpp index 1507059f38..ba00d90365 100644 --- a/lib/Support/SmallPtrSet.cpp +++ b/lib/Support/SmallPtrSet.cpp @@ -18,6 +18,24 @@ using namespace llvm; +void SmallPtrSetImpl::shrink_and_clear() { + assert(!isSmall() && "Can't shrink a small set!"); + free(CurArray); + + // Reduce the number of buckets. + CurArraySize = NumElements > 16 ? 1 << (Log2_32_Ceil(NumElements) + 1) : 32; + NumElements = NumTombstones = 0; + + // Install the new array. Clear all the buckets to empty. + CurArray = (const void**)malloc(sizeof(void*) * (CurArraySize+1)); + assert(CurArray && "Failed to allocate memory?"); + memset(CurArray, -1, CurArraySize*sizeof(void*)); + + // The end pointer, always valid, is set to a valid element to help the + // iterator. + CurArray[CurArraySize] = 0; +} + bool SmallPtrSetImpl::insert(const void * Ptr) { if (isSmall()) { // Check to see if it is already in the set. |