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 1865e7f48a3f433bbeb028d57c4813fe9e61203d..c035f8cc6d7e4844b84f2cdb691de02ca9f9c5c9 100644 (file)
--- a/include/llvm/ADT/StringMap.h
+++ b/include/llvm/ADT/StringMap.h
@@ -33,14 +33,6 @@ public:
   unsigned getKeyLength() const { return StrLen; }
 };
   
-/// StringMapVisitor - Subclasses of this class may be implemented to walk all
-/// of the items in a StringMap.
-class StringMapVisitor {
-public:
-  virtual ~StringMapVisitor();
-  virtual void Visit(const char *Key, StringMapEntryBase *Value) const = 0;
-};
-
 /// StringMapImpl - This is the base class of StringMap that is shared among
 /// all of its instantiations.
 class StringMapImpl {
@@ -60,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
@@ -72,6 +75,19 @@ protected:
   /// of the string.
   unsigned LookupBucketFor(const char *KeyStart, const char *KeyEnd);
   
+  /// FindKey - Look up the bucket that contains the specified key. If it exists
+  /// 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() {
     return (StringMapEntryBase*)-1;
@@ -82,8 +98,6 @@ public:
 
   bool empty() const { return NumItems == 0; }
   unsigned size() const { return NumItems; }
-  
-  void VisitEntries(const StringMapVisitor &Visitor) const;
 };
 
 /// StringMapEntry - This is used to represent one value that is inserted into
@@ -185,11 +199,38 @@ public:
   const_iterator begin() const { return const_iterator(TheTable); }
   const_iterator end() const { return const_iterator(TheTable+NumBuckets); }
   
-  /// FindValue - Look up the specified key in the map.  If it exists, return a
-  /// pointer to the element, otherwise return null.
-  MapEntryTy *FindValue(const char *KeyStart, const char *KeyEnd) {
-    unsigned BucketNo = LookupBucketFor(KeyStart, KeyEnd);
-    return static_cast<MapEntryTy*>(TheTable[BucketNo].Item);
+  
+  iterator find(const char *KeyStart, const char *KeyEnd) {
+    int Bucket = FindKey(KeyStart, KeyEnd);
+    if (Bucket == -1) return end();
+    return iterator(TheTable+Bucket);
+  }
+
+  const_iterator find(const char *KeyStart, const char *KeyEnd) const {
+    int Bucket = FindKey(KeyStart, KeyEnd);
+    if (Bucket == -1) return end();
+    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
@@ -199,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;
   }
@@ -227,6 +276,7 @@ public:
 
 template<typename ValueTy>
 class StringMapConstIterator {
+protected:
   StringMapImpl::ItemBucket *Ptr;
 public:
   StringMapConstIterator(StringMapImpl::ItemBucket *Bucket) : Ptr(Bucket) {