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