From 414fdbdb0104fdc8c570287f94df8bb697e7b7c1 Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Wed, 30 Mar 2011 18:32:41 +0000 Subject: [PATCH] Prevent infinite growth of the DenseMap. MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit When the hash function uses object pointers all free entries eventually become tombstones as they are used at least once, regardless of the size. DenseMap cannot function with zero empty keys, so it double size to get get ridof the tombstones. However DenseMap never shrinks automatically unless it is cleared, so the net result is that certain tables grow infinitely. The solution is to make a fresh copy of the table without tombstones instead of doubling size, by simply calling grow with the current size. Patch by José Fonseca! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@128564 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/ADT/DenseMap.h | 7 +++++-- 1 file changed, 5 insertions(+), 2 deletions(-) diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h index 36e96b8c3d0..c0209d9a181 100644 --- a/include/llvm/ADT/DenseMap.h +++ b/include/llvm/ADT/DenseMap.h @@ -289,11 +289,14 @@ private: // table completely filled with tombstones, no lookup would ever succeed, // causing infinite loops in lookup. ++NumEntries; - if (NumEntries*4 >= NumBuckets*3 || - NumBuckets-(NumEntries+NumTombstones) < NumBuckets/8) { + if (NumEntries*4 >= NumBuckets*3) { this->grow(NumBuckets * 2); LookupBucketFor(Key, TheBucket); } + if (NumBuckets-(NumEntries+NumTombstones) < NumBuckets/8) { + this->grow(NumBuckets); + LookupBucketFor(Key, TheBucket); + } // If we are writing over a tombstone, remember this. if (!KeyInfoT::isEqual(TheBucket->first, getEmptyKey())) -- 2.34.1