diff options
author | Jakob Stoklund Olesen <stoklund@2pi.dk> | 2011-03-30 18:32:44 +0000 |
---|---|---|
committer | Jakob Stoklund Olesen <stoklund@2pi.dk> | 2011-03-30 18:32:44 +0000 |
commit | aea4fe2862ce17acc6ce943df589ee8d5eb05adf (patch) | |
tree | 20475d051ea65b71edd9690bc4092388cc64fbef | |
parent | 414fdbdb0104fdc8c570287f94df8bb697e7b7c1 (diff) | |
download | llvm-aea4fe2862ce17acc6ce943df589ee8d5eb05adf.tar.gz llvm-aea4fe2862ce17acc6ce943df589ee8d5eb05adf.tar.bz2 llvm-aea4fe2862ce17acc6ce943df589ee8d5eb05adf.tar.xz |
Prevent infinite growth of SmallMap instances.
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
-rw-r--r-- | include/llvm/ADT/StringMap.h | 16 | ||||
-rw-r--r-- | lib/Support/StringMap.cpp | 14 |
2 files changed, 15 insertions, 15 deletions
diff --git a/include/llvm/ADT/StringMap.h b/include/llvm/ADT/StringMap.h index bad0e6f513..f3d6b9f484 100644 --- a/include/llvm/ADT/StringMap.h +++ b/include/llvm/ADT/StringMap.h @@ -81,16 +81,6 @@ protected: StringMapImpl(unsigned InitSize, unsigned ItemSize); void RehashTable(); - /// ShouldRehash - Return true if the table should be rehashed after a new - /// element was recently inserted. - bool ShouldRehash() const { - // 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. - return NumItems*4 > NumBuckets*3 || - NumBuckets-(NumItems+NumTombstones) < NumBuckets/8; - } - /// LookupBucketFor - Look up the bucket that the specified string should end /// up in. If it already exists as a key in the map, the Item pointer for the /// specified bucket will be non-null. Otherwise, it will be null. In either @@ -340,8 +330,7 @@ public: Bucket.Item = KeyValue; ++NumItems; - if (ShouldRehash()) - RehashTable(); + RehashTable(); return true; } @@ -383,8 +372,7 @@ public: // filled in by LookupBucketFor. Bucket.Item = NewItem; - if (ShouldRehash()) - RehashTable(); + RehashTable(); return *NewItem; } diff --git a/lib/Support/StringMap.cpp b/lib/Support/StringMap.cpp index 90ec299502..f193aa42a4 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)); |