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