Bug fixes: assignment operator forgot to copy over size; copy ctor forgot to clear...

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

diff --git a/include/llvm/ADT/StringMap.h b/include/llvm/ADT/StringMap.h
index 7cc9ce7b6ce48ee9707c3052e5e5645f63b8ad30..c035f8cc6d7e4844b84f2cdb691de02ca9f9c5c9 100644 (file)
--- a/include/llvm/ADT/StringMap.h
+++ b/include/llvm/ADT/StringMap.h
@@ -52,11 +52,22 @@ protected:
   ItemBucket *TheTable;
   unsigned NumBuckets;
   unsigned NumItems;
+  unsigned NumTombstones;
   unsigned ItemSize;
 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
@@ -68,6 +79,14 @@ protected:
   /// in the map, return the bucket number of the key.  Otherwise return -1.
   /// This does not modify the map.
   int FindKey(const char *KeyStart, const char *KeyEnd) const;
+
+  /// RemoveKey - Remove the specified StringMapEntry from the table, but do not
+  /// delete it.  This aborts if the value isn't in the table.
+  void RemoveKey(StringMapEntryBase *V);
+
+  /// RemoveKey - Remove the StringMapEntry for the specified key from the
+  /// table, returning it.  If the key is not in the table, this returns null.
+  StringMapEntryBase *RemoveKey(const char *KeyStart, const char *KeyEnd);
   
 public:
   static StringMapEntryBase *getTombstoneVal() {
@@ -193,6 +212,27 @@ public:
     return const_iterator(TheTable+Bucket);
   }
   
+  /// insert - Insert the specified key/value pair into the map.  If the key
+  /// already exists in the map, return false and ignore the request, otherwise
+  /// insert it and return true.
+  bool insert(MapEntryTy *KeyValue) {
+    unsigned BucketNo =
+      LookupBucketFor(KeyValue->getKeyData(),
+                      KeyValue->getKeyData()+KeyValue->getKeyLength());
+    ItemBucket &Bucket = TheTable[BucketNo];
+    if (Bucket.Item && Bucket.Item != getTombstoneVal()) 
+      return false;  // Already exists in map.
+    
+    if (Bucket.Item == getTombstoneVal())
+      --NumTombstones;
+    Bucket.Item = KeyValue;
+    ++NumItems;
+    
+    if (ShouldRehash())
+      RehashTable();
+    return true;
+  }
+  
   /// GetOrCreateValue - Look up the specified key in the table.  If a value
   /// exists, return it.  Otherwise, default construct a value, insert it, and
   /// return.
@@ -200,26 +240,34 @@ public:
                                             const char *KeyEnd) {
     unsigned BucketNo = LookupBucketFor(KeyStart, KeyEnd);
     ItemBucket &Bucket = TheTable[BucketNo];
-    if (Bucket.Item)
+    if (Bucket.Item && Bucket.Item != getTombstoneVal())
       return *static_cast<MapEntryTy*>(Bucket.Item);
     
     MapEntryTy *NewItem = MapEntryTy::Create(KeyStart, KeyEnd, Allocator);
+    
+    if (Bucket.Item == getTombstoneVal())
+      --NumTombstones;
     ++NumItems;
     
     // Fill in the bucket for the hash table.  The FullHashValue was already
     // 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;
   }
   
+  /// remove - Remove the specified key/value pair from the map, but do not
+  /// erase it.  This aborts if the key is not in the map.
+  void remove(MapEntryTy *KeyValue) {
+    RemoveKey(KeyValue);
+  }
+  
   ~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;
   }
@@ -228,6 +276,7 @@ public:
 
 template<typename ValueTy>
 class StringMapConstIterator {
+protected:
   StringMapImpl::ItemBucket *Ptr;
 public:
   StringMapConstIterator(StringMapImpl::ItemBucket *Bucket) : Ptr(Bucket) {