[LLVMdev] [PATCH 4/5] Reset StringMap's NumTombstones on clears and rehashes.

[jfonseca at vmware.com]

From: José Fonseca <jfonseca at vmware.com>

StringMap was not properly updating NumTombstones after a clear or rehash.

This was not fatal until now because the table was growing faster than
NumTombstones could, but with the previous change of preventing infinite
growth of the table the invariant (NumItems + NumTombstones <= NumBuckets)
stopped being observed, causing infinite loops in certain situations.
---
 include/llvm/ADT/StringMap.h |    3 +++
 lib/Support/StringMap.cpp    |    3 +++
 2 files changed, 6 insertions(+), 0 deletions(-)

diff --git a/include/llvm/ADT/StringMap.h b/include/llvm/ADT/StringMap.h
index f3d6b9f..907c72d 100644
--- a/include/llvm/ADT/StringMap.h
+++ b/include/llvm/ADT/StringMap.h
@@ -329,6 +329,7 @@ public:
       --NumTombstones;
     Bucket.Item = KeyValue;
     ++NumItems;
+    assert(NumItems + NumTombstones <= NumBuckets);
 
     RehashTable();
     return true;
@@ -348,6 +349,7 @@ public:
     }
 
     NumItems = 0;
+    NumTombstones = 0;
   }
 
   /// GetOrCreateValue - Look up the specified key in the table.  If a value
@@ -367,6 +369,7 @@ public:
     if (Bucket.Item == getTombstoneVal())
       --NumTombstones;
     ++NumItems;
+    assert(NumItems + NumTombstones <= NumBuckets);
 
     // Fill in the bucket for the hash table.  The FullHashValue was already
     // filled in by LookupBucketFor.
diff --git a/lib/Support/StringMap.cpp b/lib/Support/StringMap.cpp
index f193aa4..a1ac512 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;
 }
 
@@ -224,4 +226,5 @@ void StringMapImpl::RehashTable() {
   
   TheTable = NewTableArray;
   NumBuckets = NewSize;
+  NumTombstones = 0;
 }
-- 
1.7.4.1