lib/Support/StringMap.cpp

   1 //===--- StringMap.cpp - String Hash table map implementation -------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the StringMap class.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/ADT/StringMap.h"
  15 #include <cassert>
  16 using namespace llvm;
  17
  18 StringMapImpl::StringMapImpl(unsigned InitSize, unsigned itemSize) {
  19   ItemSize = itemSize;
  20
  21   // If a size is specified, initialize the table with that many buckets.
  22   if (InitSize) {
  23     init(InitSize);
  24     return;
  25   }
  26
  27   // Otherwise, initialize it with zero buckets to avoid the allocation.
  28   TheTable = 0;
  29   NumBuckets = 0;
  30   NumItems = 0;
  31   NumTombstones = 0;
  32 }
  33
  34 void StringMapImpl::init(unsigned InitSize) {
  35   assert((InitSize & (InitSize-1)) == 0 &&
  36          "Init Size must be a power of 2 or zero!");
  37   NumBuckets = InitSize ? InitSize : 16;
  38   NumItems = 0;
  39   NumTombstones = 0;
  40
  41   TheTable = (ItemBucket*)calloc(NumBuckets+1, sizeof(ItemBucket));
  42
  43   // Allocate one extra bucket, set it to look filled so the iterators stop at
  44   // end.
  45   TheTable[NumBuckets].Item = (StringMapEntryBase*)2;
  46 }
  47
  48
  49 /// HashString - Compute a hash code for the specified string.
  50 ///
  51 static unsigned HashString(const char *Start, const char *End) {
  52   // Bernstein hash function.
  53   unsigned int Result = 0;
  54   // TODO: investigate whether a modified bernstein hash function performs
  55   // better: http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx
  56   //   X*33+c -> X*33^c
  57   while (Start != End)
  58     Result = Result * 33 + *Start++;
  59   Result = Result + (Result >> 5);
  60   return Result;
  61 }
  62
  63 /// LookupBucketFor - Look up the bucket that the specified string should end
  64 /// up in.  If it already exists as a key in the map, the Item pointer for the
  65 /// specified bucket will be non-null.  Otherwise, it will be null.  In either
  66 /// case, the FullHashValue field of the bucket will be set to the hash value
  67 /// of the string.
  68 unsigned StringMapImpl::LookupBucketFor(const StringRef &Name) {
  69   unsigned HTSize = NumBuckets;
  70   if (HTSize == 0) {  // Hash table unallocated so far?
  71     init(16);
  72     HTSize = NumBuckets;
  73   }
  74   unsigned FullHashValue = HashString(Name.begin(), Name.end());
  75   unsigned BucketNo = FullHashValue & (HTSize-1);
  76
  77   unsigned ProbeAmt = 1;
  78   int FirstTombstone = -1;
  79   while (1) {
  80     ItemBucket &Bucket = TheTable[BucketNo];
  81     StringMapEntryBase *BucketItem = Bucket.Item;
  82     // If we found an empty bucket, this key isn't in the table yet, return it.
  83     if (BucketItem == 0) {
  84       // If we found a tombstone, we want to reuse the tombstone instead of an
  85       // empty bucket.  This reduces probing.
  86       if (FirstTombstone != -1) {
  87         TheTable[FirstTombstone].FullHashValue = FullHashValue;
  88         return FirstTombstone;
  89       }
  90
  91       Bucket.FullHashValue = FullHashValue;
  92       return BucketNo;
  93     }
  94
  95     if (BucketItem == getTombstoneVal()) {
  96       // Skip over tombstones.  However, remember the first one we see.
  97       if (FirstTombstone == -1) FirstTombstone = BucketNo;
  98     } else if (Bucket.FullHashValue == FullHashValue) {
  99       // If the full hash value matches, check deeply for a match.  The common
 100       // case here is that we are only looking at the buckets (for item info
 101       // being non-null and for the full hash value) not at the items.  This
 102       // is important for cache locality.
 103
 104       // Do the comparison like this because Name isn't necessarily
 105       // null-terminated!
 106       char *ItemStr = (char*)BucketItem+ItemSize;
 107       if (Name == StringRef(ItemStr, BucketItem->getKeyLength())) {
 108         // We found a match!
 109         return BucketNo;
 110       }
 111     }
 112
 113     // Okay, we didn't find the item.  Probe to the next bucket.
 114     BucketNo = (BucketNo+ProbeAmt) & (HTSize-1);
 115
 116     // Use quadratic probing, it has fewer clumping artifacts than linear
 117     // probing and has good cache behavior in the common case.
 118     ++ProbeAmt;
 119   }
 120 }
 121
 122
 123 /// FindKey - Look up the bucket that contains the specified key. If it exists
 124 /// in the map, return the bucket number of the key.  Otherwise return -1.
 125 /// This does not modify the map.
 126 int StringMapImpl::FindKey(const StringRef &Key) const {
 127   unsigned HTSize = NumBuckets;
 128   if (HTSize == 0) return -1;  // Really empty table?
 129   unsigned FullHashValue = HashString(Key.begin(), Key.end());
 130   unsigned BucketNo = FullHashValue & (HTSize-1);
 131
 132   unsigned ProbeAmt = 1;
 133   while (1) {
 134     ItemBucket &Bucket = TheTable[BucketNo];
 135     StringMapEntryBase *BucketItem = Bucket.Item;
 136     // If we found an empty bucket, this key isn't in the table yet, return.
 137     if (BucketItem == 0)
 138       return -1;
 139
 140     if (BucketItem == getTombstoneVal()) {
 141       // Ignore tombstones.
 142     } else if (Bucket.FullHashValue == FullHashValue) {
 143       // If the full hash value matches, check deeply for a match.  The common
 144       // case here is that we are only looking at the buckets (for item info
 145       // being non-null and for the full hash value) not at the items.  This
 146       // is important for cache locality.
 147
 148       // Do the comparison like this because NameStart isn't necessarily
 149       // null-terminated!
 150       char *ItemStr = (char*)BucketItem+ItemSize;
 151       if (Key == StringRef(ItemStr, BucketItem->getKeyLength())) {
 152         // We found a match!
 153         return BucketNo;
 154       }
 155     }
 156
 157     // Okay, we didn't find the item.  Probe to the next bucket.
 158     BucketNo = (BucketNo+ProbeAmt) & (HTSize-1);
 159
 160     // Use quadratic probing, it has fewer clumping artifacts than linear
 161     // probing and has good cache behavior in the common case.
 162     ++ProbeAmt;
 163   }
 164 }
 165
 166 /// RemoveKey - Remove the specified StringMapEntry from the table, but do not
 167 /// delete it.  This aborts if the value isn't in the table.
 168 void StringMapImpl::RemoveKey(StringMapEntryBase *V) {
 169   const char *VStr = (char*)V + ItemSize;
 170   StringMapEntryBase *V2 = RemoveKey(StringRef(VStr, V->getKeyLength()));
 171   V2 = V2;
 172   assert(V == V2 && "Didn't find key?");
 173 }
 174
 175 /// RemoveKey - Remove the StringMapEntry for the specified key from the
 176 /// table, returning it.  If the key is not in the table, this returns null.
 177 StringMapEntryBase *StringMapImpl::RemoveKey(const StringRef &Key) {
 178   int Bucket = FindKey(Key);
 179   if (Bucket == -1) return 0;
 180
 181   StringMapEntryBase *Result = TheTable[Bucket].Item;
 182   TheTable[Bucket].Item = getTombstoneVal();
 183   --NumItems;
 184   ++NumTombstones;
 185   return Result;
 186 }
 187
 188
 189
 190 /// RehashTable - Grow the table, redistributing values into the buckets with
 191 /// the appropriate mod-of-hashtable-size.
 192 void StringMapImpl::RehashTable() {
 193   unsigned NewSize = NumBuckets*2;
 194   // Allocate one extra bucket which will always be non-empty.  This allows the
 195   // iterators to stop at end.
 196   ItemBucket *NewTableArray =(ItemBucket*)calloc(NewSize+1, sizeof(ItemBucket));
 197   NewTableArray[NewSize].Item = (StringMapEntryBase*)2;
 198
 199   // Rehash all the items into their new buckets.  Luckily :) we already have
 200   // the hash values available, so we don't have to rehash any strings.
 201   for (ItemBucket *IB = TheTable, *E = TheTable+NumBuckets; IB != E; ++IB) {
 202     if (IB->Item && IB->Item != getTombstoneVal()) {
 203       // Fast case, bucket available.
 204       unsigned FullHash = IB->FullHashValue;
 205       unsigned NewBucket = FullHash & (NewSize-1);
 206       if (NewTableArray[NewBucket].Item == 0) {
 207         NewTableArray[FullHash & (NewSize-1)].Item = IB->Item;
 208         NewTableArray[FullHash & (NewSize-1)].FullHashValue = FullHash;
 209         continue;
 210       }
 211
 212       // Otherwise probe for a spot.
 213       unsigned ProbeSize = 1;
 214       do {
 215         NewBucket = (NewBucket + ProbeSize++) & (NewSize-1);
 216       } while (NewTableArray[NewBucket].Item);
 217
 218       // Finally found a slot.  Fill it in.
 219       NewTableArray[NewBucket].Item = IB->Item;
 220       NewTableArray[NewBucket].FullHashValue = FullHash;
 221     }
 222   }
 223
 224   free(TheTable);
 225
 226   TheTable = NewTableArray;
 227   NumBuckets = NewSize;
 228 }