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