X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FSupport%2FStringMap.cpp;h=90ec299502629b5c0f47e91fd165c30e18b71477;hb=a75ce9f5d2236d93c117e861e60e6f3f748c9555;hp=02d42b9b49bb3b7d24aafbbd0ec0aa24e80d7a4c;hpb=b5bb9f5b5cfe89f4b7626671f4923d50f8d4cd6a;p=oota-llvm.git

diff --git a/lib/Support/StringMap.cpp b/lib/Support/StringMap.cpp
index 02d42b9b49b..90ec2995026 100644
--- a/lib/Support/StringMap.cpp
+++ b/lib/Support/StringMap.cpp
@@ -2,8 +2,8 @@
 //
 //                     The LLVM Compiler Infrastructure
 //
-// This file was developed by Chris Lattner and is distributed under
-// the University of Illinois Open Source License. See LICENSE.TXT for details.
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
@@ -12,18 +12,34 @@
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/StringMap.h"
+#include "llvm/ADT/StringExtras.h"
 #include <cassert>
 using namespace llvm;
 
 StringMapImpl::StringMapImpl(unsigned InitSize, unsigned itemSize) {
+  ItemSize = itemSize;
+  
+  // If a size is specified, initialize the table with that many buckets.
+  if (InitSize) {
+    init(InitSize);
+    return;
+  }
+  
+  // Otherwise, initialize it with zero buckets to avoid the allocation.
+  TheTable = 0;
+  NumBuckets = 0;
+  NumItems = 0;
+  NumTombstones = 0;
+}
+
+void StringMapImpl::init(unsigned InitSize) {
   assert((InitSize & (InitSize-1)) == 0 &&
          "Init Size must be a power of 2 or zero!");
-  NumBuckets = InitSize ? InitSize : 512;
-  ItemSize = itemSize;
+  NumBuckets = InitSize ? InitSize : 16;
   NumItems = 0;
+  NumTombstones = 0;
   
-  TheTable = new ItemBucket[NumBuckets+1]();
-  memset(TheTable, 0, NumBuckets*sizeof(ItemBucket));
+  TheTable = (ItemBucket*)calloc(NumBuckets+1, sizeof(ItemBucket));
   
   // Allocate one extra bucket, set it to look filled so the iterators stop at
   // end.
@@ -31,52 +47,51 @@ StringMapImpl::StringMapImpl(unsigned InitSize, unsigned itemSize) {
 }
 
 
-/// HashString - Compute a hash code for the specified string.
-///
-static unsigned HashString(const char *Start, const char *End) {
-  // Bernstein hash function.
-  unsigned int Result = 0;
-  // TODO: investigate whether a modified bernstein hash function performs
-  // better: http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx
-  //   X*33+c -> X*33^c
-  while (Start != End)
-    Result = Result * 33 + *Start++;
-  Result = Result + (Result >> 5);
-  return Result;
-}
-
 /// 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
 /// case, the FullHashValue field of the bucket will be set to the hash value
 /// of the string.
-unsigned StringMapImpl::LookupBucketFor(const char *NameStart,
-                                         const char *NameEnd) {
+unsigned StringMapImpl::LookupBucketFor(StringRef Name) {
   unsigned HTSize = NumBuckets;
-  unsigned FullHashValue = HashString(NameStart, NameEnd);
+  if (HTSize == 0) {  // Hash table unallocated so far?
+    init(16);
+    HTSize = NumBuckets;
+  }
+  unsigned FullHashValue = HashString(Name);
   unsigned BucketNo = FullHashValue & (HTSize-1);
   
   unsigned ProbeAmt = 1;
+  int FirstTombstone = -1;
   while (1) {
     ItemBucket &Bucket = TheTable[BucketNo];
     StringMapEntryBase *BucketItem = Bucket.Item;
     // If we found an empty bucket, this key isn't in the table yet, return it.
     if (BucketItem == 0) {
+      // If we found a tombstone, we want to reuse the tombstone instead of an
+      // empty bucket.  This reduces probing.
+      if (FirstTombstone != -1) {
+        TheTable[FirstTombstone].FullHashValue = FullHashValue;
+        return FirstTombstone;
+      }
+      
       Bucket.FullHashValue = FullHashValue;
       return BucketNo;
     }
     
-    // If the full hash value matches, check deeply for a match.  The common
-    // case here is that we are only looking at the buckets (for item info
-    // being non-null and for the full hash value) not at the items.  This
-    // is important for cache locality.
-    if (Bucket.FullHashValue == FullHashValue) {
-      // Do the comparison like this because NameStart isn't necessarily
+    if (BucketItem == getTombstoneVal()) {
+      // Skip over tombstones.  However, remember the first one we see.
+      if (FirstTombstone == -1) FirstTombstone = BucketNo;
+    } else if (Bucket.FullHashValue == FullHashValue) {
+      // If the full hash value matches, check deeply for a match.  The common
+      // case here is that we are only looking at the buckets (for item info
+      // being non-null and for the full hash value) not at the items.  This
+      // is important for cache locality.
+      
+      // Do the comparison like this because Name isn't necessarily
       // null-terminated!
       char *ItemStr = (char*)BucketItem+ItemSize;
-      unsigned ItemStrLen = BucketItem->getKeyLength();
-      if (unsigned(NameEnd-NameStart) == ItemStrLen &&
-          memcmp(ItemStr, NameStart, ItemStrLen) == 0) {
+      if (Name == StringRef(ItemStr, BucketItem->getKeyLength())) {
         // We found a match!
         return BucketNo;
       }
@@ -95,9 +110,10 @@ unsigned StringMapImpl::LookupBucketFor(const char *NameStart,
 /// 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 StringMapImpl::FindKey(const char *KeyStart, const char *KeyEnd) const {
+int StringMapImpl::FindKey(StringRef Key) const {
   unsigned HTSize = NumBuckets;
-  unsigned FullHashValue = HashString(KeyStart, KeyEnd);
+  if (HTSize == 0) return -1;  // Really empty table?
+  unsigned FullHashValue = HashString(Key);
   unsigned BucketNo = FullHashValue & (HTSize-1);
   
   unsigned ProbeAmt = 1;
@@ -108,17 +124,18 @@ int StringMapImpl::FindKey(const char *KeyStart, const char *KeyEnd) const {
     if (BucketItem == 0)
       return -1;
     
-    // If the full hash value matches, check deeply for a match.  The common
-    // case here is that we are only looking at the buckets (for item info
-    // being non-null and for the full hash value) not at the items.  This
-    // is important for cache locality.
-    if (Bucket.FullHashValue == FullHashValue) {
+    if (BucketItem == getTombstoneVal()) {
+      // Ignore tombstones.
+    } else if (Bucket.FullHashValue == FullHashValue) {
+      // If the full hash value matches, check deeply for a match.  The common
+      // case here is that we are only looking at the buckets (for item info
+      // being non-null and for the full hash value) not at the items.  This
+      // is important for cache locality.
+      
       // Do the comparison like this because NameStart isn't necessarily
       // null-terminated!
       char *ItemStr = (char*)BucketItem+ItemSize;
-      unsigned ItemStrLen = BucketItem->getKeyLength();
-      if (unsigned(KeyEnd-KeyStart) == ItemStrLen &&
-          memcmp(ItemStr, KeyStart, ItemStrLen) == 0) {
+      if (Key == StringRef(ItemStr, BucketItem->getKeyLength())) {
         // We found a match!
         return BucketNo;
       }
@@ -133,6 +150,29 @@ int StringMapImpl::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 StringMapImpl::RemoveKey(StringMapEntryBase *V) {
+  const char *VStr = (char*)V + ItemSize;
+  StringMapEntryBase *V2 = RemoveKey(StringRef(VStr, V->getKeyLength()));
+  (void)V2;
+  assert(V == V2 && "Didn't find key?");
+}
+
+/// 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 *StringMapImpl::RemoveKey(StringRef Key) {
+  int Bucket = FindKey(Key);
+  if (Bucket == -1) return 0;
+  
+  StringMapEntryBase *Result = TheTable[Bucket].Item;
+  TheTable[Bucket].Item = getTombstoneVal();
+  --NumItems;
+  ++NumTombstones;
+  return Result;
+}
+
+
 
 /// RehashTable - Grow the table, redistributing values into the buckets with
 /// the appropriate mod-of-hashtable-size.
@@ -140,14 +180,13 @@ void StringMapImpl::RehashTable() {
   unsigned NewSize = NumBuckets*2;
   // Allocate one extra bucket which will always be non-empty.  This allows the
   // iterators to stop at end.
-  ItemBucket *NewTableArray = new ItemBucket[NewSize+1]();
-  memset(NewTableArray, 0, NewSize*sizeof(ItemBucket));
+  ItemBucket *NewTableArray =(ItemBucket*)calloc(NewSize+1, sizeof(ItemBucket));
   NewTableArray[NewSize].Item = (StringMapEntryBase*)2;
   
   // Rehash all the items into their new buckets.  Luckily :) we already have
   // the hash values available, so we don't have to rehash any strings.
   for (ItemBucket *IB = TheTable, *E = TheTable+NumBuckets; IB != E; ++IB) {
-    if (IB->Item) {
+    if (IB->Item && IB->Item != getTombstoneVal()) {
       // Fast case, bucket available.
       unsigned FullHash = IB->FullHashValue;
       unsigned NewBucket = FullHash & (NewSize-1);
@@ -157,6 +196,7 @@ void StringMapImpl::RehashTable() {
         continue;
       }
       
+      // Otherwise probe for a spot.
       unsigned ProbeSize = 1;
       do {
         NewBucket = (NewBucket + ProbeSize++) & (NewSize-1);
@@ -168,7 +208,7 @@ void StringMapImpl::RehashTable() {
     }
   }
   
-  delete[] TheTable;
+  free(TheTable);
   
   TheTable = NewTableArray;
   NumBuckets = NewSize;