From 6b943ff3a3f8617113ecbf611cf0f8957e4e19d2 Mon Sep 17 00:00:00 2001 From: Dimitry Andric Date: Mon, 2 May 2011 19:34:44 +0000 Subject: Vendor import of llvm trunk r130700: http://llvm.org/svn/llvm-project/llvm/trunk@130700 --- lib/Support/StringMap.cpp | 17 ++++++++++++++++- 1 file changed, 16 insertions(+), 1 deletion(-) (limited to 'lib/Support/StringMap.cpp') diff --git a/lib/Support/StringMap.cpp b/lib/Support/StringMap.cpp index 90ec29950262..a1ac512fa244 100644 --- a/lib/Support/StringMap.cpp +++ b/lib/Support/StringMap.cpp @@ -169,6 +169,8 @@ StringMapEntryBase *StringMapImpl::RemoveKey(StringRef Key) { TheTable[Bucket].Item = getTombstoneVal(); --NumItems; ++NumTombstones; + assert(NumItems + NumTombstones <= NumBuckets); + return Result; } @@ -177,7 +179,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)); @@ -212,4 +226,5 @@ void StringMapImpl::RehashTable() { TheTable = NewTableArray; NumBuckets = NewSize; + NumTombstones = 0; } -- cgit v1.2.3