llvm/lib/Support/StringMap.cpp

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