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