From aea4fe2862ce17acc6ce943df589ee8d5eb05adf Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Wed, 30 Mar 2011 18:32:44 +0000 Subject: Prevent infinite growth of SmallMap 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@128565 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Support/StringMap.cpp | 14 +++++++++++++- 1 file changed, 13 insertions(+), 1 deletion(-) (limited to 'lib/Support/StringMap.cpp') diff --git a/lib/Support/StringMap.cpp b/lib/Support/StringMap.cpp index 90ec299..f193aa4 100644 --- a/lib/Support/StringMap.cpp +++ b/lib/Support/StringMap.cpp @@ -177,7 +177,19 @@ StringMapEntryBase *StringMapImpl::RemoveKey(StringRef Key) { /// RehashTable - Grow the table, redistributing values into the buckets with /// the appropriate mod-of-hashtable-size. void StringMapImpl::RehashTable() { - unsigned NewSize = NumBuckets*2; + unsigned NewSize; + + // If the hash table is now more than 3/4 full, or if fewer than 1/8 of + // the buckets are empty (meaning that many are filled with tombstones), + // grow/rehash the table. + if (NumItems*4 > NumBuckets*3) { + NewSize = NumBuckets*2; + } else if (NumBuckets-(NumItems+NumTombstones) < NumBuckets/8) { + NewSize = NumBuckets; + } else { + return; + } + // Allocate one extra bucket which will always be non-empty. This allows the // iterators to stop at end. ItemBucket *NewTableArray =(ItemBucket*)calloc(NewSize+1, sizeof(ItemBucket)); -- cgit v1.1