259 lines · 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-exception6//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 18using namespace llvm;19 20/// Returns the number of buckets to allocate to ensure that the DenseMap can21/// accommodate \p NumEntries without need to grow().22static 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 31static 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 at36 // end.37 Table[NewNumBuckets] = (StringMapEntryBase *)2;38 return Table;39}40 41static inline unsigned *getHashTable(StringMapEntryBase **TheTable,42 unsigned NumBuckets) {43 return reinterpret_cast<unsigned *>(TheTable + NumBuckets + 1);44}45 46uint32_t StringMapImpl::hash(StringRef Key) { return xxh3_64bits(Key); }47 48StringMapImpl::StringMapImpl(unsigned InitSize, unsigned itemSize)49 : ItemSize(itemSize) {50 // If a size is specified, initialize the table with that many buckets.51 if (InitSize) {52 // The table will grow when the number of entries reach 3/4 of the number of53 // buckets. To guarantee that "InitSize" number of entries can be inserted54 // in the table without growing, we allocate just what is needed here.55 init(getMinBucketToReserveForEntries(InitSize));56 }57}58 59void StringMapImpl::init(unsigned InitSize) {60 assert((InitSize & (InitSize - 1)) == 0 &&61 "Init Size must be a power of 2 or zero!");62 63 unsigned NewNumBuckets = InitSize ? InitSize : 16;64 NumItems = 0;65 NumTombstones = 0;66 67 TheTable = createTable(NewNumBuckets);68 69 // Set the member only if TheTable was successfully allocated70 NumBuckets = NewNumBuckets;71}72 73/// LookupBucketFor - Look up the bucket that the specified string should end74/// up in. If it already exists as a key in the map, the Item pointer for the75/// specified bucket will be non-null. Otherwise, it will be null. In either76/// case, the FullHashValue field of the bucket will be set to the hash value77/// of the string.78unsigned StringMapImpl::LookupBucketFor(StringRef Name,79 uint32_t FullHashValue) {80#ifdef EXPENSIVE_CHECKS81 assert(FullHashValue == hash(Name));82#endif83 // Hash table unallocated so far?84 if (NumBuckets == 0)85 init(16);86 if constexpr (shouldReverseIterate())87 FullHashValue = ~FullHashValue;88 unsigned BucketNo = FullHashValue & (NumBuckets - 1);89 unsigned *HashTable = getHashTable(TheTable, NumBuckets);90 91 unsigned ProbeAmt = 1;92 int FirstTombstone = -1;93 while (true) {94 StringMapEntryBase *BucketItem = TheTable[BucketNo];95 // If we found an empty bucket, this key isn't in the table yet, return it.96 if (LLVM_LIKELY(!BucketItem)) {97 // If we found a tombstone, we want to reuse the tombstone instead of an98 // empty bucket. This reduces probing.99 if (FirstTombstone != -1) {100 HashTable[FirstTombstone] = FullHashValue;101 return FirstTombstone;102 }103 104 HashTable[BucketNo] = FullHashValue;105 return BucketNo;106 }107 108 if (BucketItem == getTombstoneVal()) {109 // Skip over tombstones. However, remember the first one we see.110 if (FirstTombstone == -1)111 FirstTombstone = BucketNo;112 } else if (LLVM_LIKELY(HashTable[BucketNo] == FullHashValue)) {113 // If the full hash value matches, check deeply for a match. The common114 // case here is that we are only looking at the buckets (for item info115 // being non-null and for the full hash value) not at the items. This116 // is important for cache locality.117 118 // Do the comparison like this because Name isn't necessarily119 // null-terminated!120 char *ItemStr = (char *)BucketItem + ItemSize;121 if (Name == StringRef(ItemStr, BucketItem->getKeyLength())) {122 // We found a match!123 return BucketNo;124 }125 }126 127 // Okay, we didn't find the item. Probe to the next bucket.128 BucketNo = (BucketNo + ProbeAmt) & (NumBuckets - 1);129 130 // Use quadratic probing, it has fewer clumping artifacts than linear131 // probing and has good cache behavior in the common case.132 ++ProbeAmt;133 }134}135 136/// FindKey - Look up the bucket that contains the specified key. If it exists137/// in the map, return the bucket number of the key. Otherwise return -1.138/// This does not modify the map.139int StringMapImpl::FindKey(StringRef Key, uint32_t FullHashValue) const {140 if (NumBuckets == 0)141 return -1; // Really empty table?142#ifdef EXPENSIVE_CHECKS143 assert(FullHashValue == hash(Key));144#endif145 if constexpr (shouldReverseIterate())146 FullHashValue = ~FullHashValue;147 unsigned BucketNo = FullHashValue & (NumBuckets - 1);148 unsigned *HashTable = getHashTable(TheTable, NumBuckets);149 150 unsigned ProbeAmt = 1;151 while (true) {152 StringMapEntryBase *BucketItem = TheTable[BucketNo];153 // If we found an empty bucket, this key isn't in the table yet, return.154 if (LLVM_LIKELY(!BucketItem))155 return -1;156 157 if (BucketItem == getTombstoneVal()) {158 // Ignore tombstones.159 } else if (LLVM_LIKELY(HashTable[BucketNo] == FullHashValue)) {160 // If the full hash value matches, check deeply for a match. The common161 // case here is that we are only looking at the buckets (for item info162 // being non-null and for the full hash value) not at the items. This163 // is important for cache locality.164 165 // Do the comparison like this because NameStart isn't necessarily166 // null-terminated!167 char *ItemStr = (char *)BucketItem + ItemSize;168 if (Key == StringRef(ItemStr, BucketItem->getKeyLength())) {169 // We found a match!170 return BucketNo;171 }172 }173 174 // Okay, we didn't find the item. Probe to the next bucket.175 BucketNo = (BucketNo + ProbeAmt) & (NumBuckets - 1);176 177 // Use quadratic probing, it has fewer clumping artifacts than linear178 // probing and has good cache behavior in the common case.179 ++ProbeAmt;180 }181}182 183/// RemoveKey - Remove the specified StringMapEntry from the table, but do not184/// delete it. This aborts if the value isn't in the table.185void StringMapImpl::RemoveKey(StringMapEntryBase *V) {186 const char *VStr = (char *)V + ItemSize;187 StringMapEntryBase *V2 = RemoveKey(StringRef(VStr, V->getKeyLength()));188 (void)V2;189 assert(V == V2 && "Didn't find key?");190}191 192/// RemoveKey - Remove the StringMapEntry for the specified key from the193/// table, returning it. If the key is not in the table, this returns null.194StringMapEntryBase *StringMapImpl::RemoveKey(StringRef Key) {195 int Bucket = FindKey(Key);196 if (Bucket == -1)197 return nullptr;198 199 StringMapEntryBase *Result = TheTable[Bucket];200 TheTable[Bucket] = getTombstoneVal();201 --NumItems;202 ++NumTombstones;203 assert(NumItems + NumTombstones <= NumBuckets);204 205 return Result;206}207 208/// RehashTable - Grow the table, redistributing values into the buckets with209/// the appropriate mod-of-hashtable-size.210unsigned StringMapImpl::RehashTable(unsigned BucketNo) {211 unsigned NewSize;212 // If the hash table is now more than 3/4 full, or if fewer than 1/8 of213 // the buckets are empty (meaning that many are filled with tombstones),214 // grow/rehash the table.215 if (LLVM_UNLIKELY(NumItems * 4 > NumBuckets * 3)) {216 NewSize = NumBuckets * 2;217 } else if (LLVM_UNLIKELY(NumBuckets - (NumItems + NumTombstones) <=218 NumBuckets / 8)) {219 NewSize = NumBuckets;220 } else {221 return BucketNo;222 }223 224 unsigned NewBucketNo = BucketNo;225 auto **NewTableArray = createTable(NewSize);226 unsigned *NewHashArray = getHashTable(NewTableArray, NewSize);227 unsigned *HashTable = getHashTable(TheTable, NumBuckets);228 229 // Rehash all the items into their new buckets. Luckily :) we already have230 // the hash values available, so we don't have to rehash any strings.231 for (unsigned I = 0, E = NumBuckets; I != E; ++I) {232 StringMapEntryBase *Bucket = TheTable[I];233 if (Bucket && Bucket != getTombstoneVal()) {234 // If the bucket is not available, probe for a spot.235 unsigned FullHash = HashTable[I];236 unsigned NewBucket = FullHash & (NewSize - 1);237 if (NewTableArray[NewBucket]) {238 unsigned ProbeSize = 1;239 do {240 NewBucket = (NewBucket + ProbeSize++) & (NewSize - 1);241 } while (NewTableArray[NewBucket]);242 }243 244 // Finally found a slot. Fill it in.245 NewTableArray[NewBucket] = Bucket;246 NewHashArray[NewBucket] = FullHash;247 if (I == BucketNo)248 NewBucketNo = NewBucket;249 }250 }251 252 free(TheTable);253 254 TheTable = NewTableArray;255 NumBuckets = NewSize;256 NumTombstones = 0;257 return NewBucketNo;258}259