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