From e10fff6f8802d6ab4045d9d0bb22e6f37e6d3d0b Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Wed, 30 Mar 2011 18:32:48 +0000 Subject: [PATCH] Prevent infinite growth of SmallPtrSet instances. MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Rehash but don't grow when full of tombstones. Patch by José Fonseca! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@128566 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/ADT/SmallPtrSet.h | 2 +- lib/Support/SmallPtrSet.cpp | 15 +++++++++------ 2 files changed, 10 insertions(+), 7 deletions(-) diff --git a/include/llvm/ADT/SmallPtrSet.h b/include/llvm/ADT/SmallPtrSet.h index ff32ba87a26..9992858d67b 100644 --- a/include/llvm/ADT/SmallPtrSet.h +++ b/include/llvm/ADT/SmallPtrSet.h @@ -133,7 +133,7 @@ private: void shrink_and_clear(); /// Grow - Allocate a larger backing store for the buckets and move it over. - void Grow(); + void Grow(unsigned NewSize); void operator=(const SmallPtrSetImpl &RHS); // DO NOT IMPLEMENT. protected: diff --git a/lib/Support/SmallPtrSet.cpp b/lib/Support/SmallPtrSet.cpp index 504e6497a3c..997ce0b74cd 100644 --- a/lib/Support/SmallPtrSet.cpp +++ b/lib/Support/SmallPtrSet.cpp @@ -52,10 +52,14 @@ bool SmallPtrSetImpl::insert_imp(const void * Ptr) { // Otherwise, hit the big set case, which will call grow. } - // If more than 3/4 of the array is full, grow. - if (NumElements*4 >= CurArraySize*3 || - CurArraySize-(NumElements+NumTombstones) < CurArraySize/8) - Grow(); + if (NumElements*4 >= CurArraySize*3) { + // If more than 3/4 of the array is full, grow. + Grow(CurArraySize < 64 ? 128 : CurArraySize*2); + } else if (CurArraySize-(NumElements+NumTombstones) < CurArraySize/8) { + // If fewer of 1/8 of the array is empty (meaning that many are filled with + // tombstones), rehash. + Grow(CurArraySize); + } // Okay, we know we have space. Find a hash bucket. const void **Bucket = const_cast(FindBucketFor(Ptr)); @@ -125,10 +129,9 @@ const void * const *SmallPtrSetImpl::FindBucketFor(const void *Ptr) const { /// Grow - Allocate a larger backing store for the buckets and move it over. /// -void SmallPtrSetImpl::Grow() { +void SmallPtrSetImpl::Grow(unsigned NewSize) { // Allocate at twice as many buckets, but at least 128. unsigned OldSize = CurArraySize; - unsigned NewSize = OldSize < 64 ? 128 : OldSize*2; const void **OldBuckets = CurArray; bool WasSmall = isSmall(); -- 2.34.1