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