add new ShouldRehash method to factor out common code. Fix the dtor to not

[oota-llvm.git] / include / llvm / ADT / StringMap.h

diff --git a/include/llvm/ADT/StringMap.h b/include/llvm/ADT/StringMap.h
index 243f9cd13fce7d68a98e68bd844ac0fbea74bebb..c035f8cc6d7e4844b84f2cdb691de02ca9f9c5c9 100644 (file)
--- a/include/llvm/ADT/StringMap.h
+++ b/include/llvm/ADT/StringMap.h
@@ -58,6 +58,16 @@ 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
@@ -218,8 +228,7 @@ 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 (ShouldRehash())
       RehashTable();
     return true;
   }
@@ -244,8 +253,7 @@ 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 (ShouldRehash())
       RehashTable();
     return *NewItem;
   }
@@ -258,8 +266,8 @@ public:
   
   ~StringMap() {
     for (ItemBucket *I = TheTable, *E = TheTable+NumBuckets; I != E; ++I) {
-      if (MapEntryTy *Id = static_cast<MapEntryTy*>(I->Item))
-        Id->Destroy(Allocator);
+      if (I->Item && I->Item != getTombstoneVal())
+        static_cast<MapEntryTy*>(I->Item)->Destroy(Allocator);
     }
     delete [] TheTable;
   }