From 65033ffc297ce5610af9eedd38dc074e02dbff9b Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Sun, 11 Feb 2007 21:07:36 +0000 Subject: [PATCH] do not allow hash table to be filled with tombstones. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@34186 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/ADT/StringMap.h | 14 ++++++++++---- 1 file changed, 10 insertions(+), 4 deletions(-) diff --git a/include/llvm/ADT/StringMap.h b/include/llvm/ADT/StringMap.h index 243f9cd13fc..0c6b76d5522 100644 --- a/include/llvm/ADT/StringMap.h +++ b/include/llvm/ADT/StringMap.h @@ -218,8 +218,11 @@ public: Bucket.Item = KeyValue; ++NumItems; - // If the hash table is now more than 3/4 full, rehash into a larger table. - if (NumItems > NumBuckets*3/4) + // 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 the table. + if (NumItems*4 > NumBuckets*3 || + NumBuckets-(NumItems+NumTombstones) < NumBuckets/8) RehashTable(); return true; } @@ -244,8 +247,11 @@ public: // filled in by LookupBucketFor. Bucket.Item = NewItem; - // If the hash table is now more than 3/4 full, rehash into a larger table. - if (NumItems > NumBuckets*3/4) + // 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 the table. + if (NumItems*4 > NumBuckets*3 || + NumBuckets-(NumItems+NumTombstones) < NumBuckets/8) RehashTable(); return *NewItem; } -- 2.34.1