StringMap.cpp revision aea4fe2862ce17acc6ce943df589ee8d5eb05adf
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> 17using namespace llvm; 18 19StringMapImpl::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 35void 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. 55unsigned 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. 113int 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. 155void 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. 164StringMapEntryBase *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 return Result; 173} 174 175 176 177/// RehashTable - Grow the table, redistributing values into the buckets with 178/// the appropriate mod-of-hashtable-size. 179void StringMapImpl::RehashTable() { 180 unsigned NewSize; 181 182 // If the hash table is now more than 3/4 full, or if fewer than 1/8 of 183 // the buckets are empty (meaning that many are filled with tombstones), 184 // grow/rehash the table. 185 if (NumItems*4 > NumBuckets*3) { 186 NewSize = NumBuckets*2; 187 } else if (NumBuckets-(NumItems+NumTombstones) < NumBuckets/8) { 188 NewSize = NumBuckets; 189 } else { 190 return; 191 } 192 193 // Allocate one extra bucket which will always be non-empty. This allows the 194 // iterators to stop at end. 195 ItemBucket *NewTableArray =(ItemBucket*)calloc(NewSize+1, sizeof(ItemBucket)); 196 NewTableArray[NewSize].Item = (StringMapEntryBase*)2; 197 198 // Rehash all the items into their new buckets. Luckily :) we already have 199 // the hash values available, so we don't have to rehash any strings. 200 for (ItemBucket *IB = TheTable, *E = TheTable+NumBuckets; IB != E; ++IB) { 201 if (IB->Item && IB->Item != getTombstoneVal()) { 202 // Fast case, bucket available. 203 unsigned FullHash = IB->FullHashValue; 204 unsigned NewBucket = FullHash & (NewSize-1); 205 if (NewTableArray[NewBucket].Item == 0) { 206 NewTableArray[FullHash & (NewSize-1)].Item = IB->Item; 207 NewTableArray[FullHash & (NewSize-1)].FullHashValue = FullHash; 208 continue; 209 } 210 211 // Otherwise probe for a spot. 212 unsigned ProbeSize = 1; 213 do { 214 NewBucket = (NewBucket + ProbeSize++) & (NewSize-1); 215 } while (NewTableArray[NewBucket].Item); 216 217 // Finally found a slot. Fill it in. 218 NewTableArray[NewBucket].Item = IB->Item; 219 NewTableArray[NewBucket].FullHashValue = FullHash; 220 } 221 } 222 223 free(TheTable); 224 225 TheTable = NewTableArray; 226 NumBuckets = NewSize; 227} 228