From e10fff6f8802d6ab4045d9d0bb22e6f37e6d3d0b Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Wed, 30 Mar 2011 18:32:48 +0000 Subject: Prevent infinite growth of SmallPtrSet instances. MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 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 --- lib/Support/SmallPtrSet.cpp | 15 +++++++++------ 1 file changed, 9 insertions(+), 6 deletions(-) (limited to 'lib/Support/SmallPtrSet.cpp') diff --git a/lib/Support/SmallPtrSet.cpp b/lib/Support/SmallPtrSet.cpp index 504e6497a3..997ce0b74c 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(); -- cgit v1.2.3-18-g5258