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