1 //===--- StringMap.cpp - String Hash table map implementation -------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the StringMap class.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/ADT/StringMap.h"
15 #include "llvm/ADT/StringExtras.h"
19 StringMapImpl::StringMapImpl(unsigned InitSize, unsigned itemSize) {
22 // If a size is specified, initialize the table with that many buckets.
28 // Otherwise, initialize it with zero buckets to avoid the allocation.
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;
42 TheTable = (StringMapEntryBase **)calloc(NumBuckets+1,
43 sizeof(StringMapEntryBase **) +
46 // Allocate one extra bucket, set it to look filled so the iterators stop at
48 TheTable[NumBuckets] = (StringMapEntryBase*)2;
52 /// LookupBucketFor - Look up the bucket that the specified string should end
53 /// up in. If it already exists as a key in the map, the Item pointer for the
54 /// specified bucket will be non-null. Otherwise, it will be null. In either
55 /// case, the FullHashValue field of the bucket will be set to the hash value
57 unsigned StringMapImpl::LookupBucketFor(StringRef Name) {
58 unsigned HTSize = NumBuckets;
59 if (HTSize == 0) { // Hash table unallocated so far?
63 unsigned FullHashValue = HashString(Name);
64 unsigned BucketNo = FullHashValue & (HTSize-1);
65 unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1);
67 unsigned ProbeAmt = 1;
68 int FirstTombstone = -1;
70 StringMapEntryBase *BucketItem = TheTable[BucketNo];
71 // If we found an empty bucket, this key isn't in the table yet, return it.
72 if (BucketItem == 0) {
73 // If we found a tombstone, we want to reuse the tombstone instead of an
74 // empty bucket. This reduces probing.
75 if (FirstTombstone != -1) {
76 HashTable[FirstTombstone] = FullHashValue;
77 return FirstTombstone;
80 HashTable[BucketNo] = FullHashValue;
84 if (BucketItem == getTombstoneVal()) {
85 // Skip over tombstones. However, remember the first one we see.
86 if (FirstTombstone == -1) FirstTombstone = BucketNo;
87 } else if (HashTable[BucketNo] == FullHashValue) {
88 // If the full hash value matches, check deeply for a match. The common
89 // case here is that we are only looking at the buckets (for item info
90 // being non-null and for the full hash value) not at the items. This
91 // is important for cache locality.
93 // Do the comparison like this because Name isn't necessarily
95 char *ItemStr = (char*)BucketItem+ItemSize;
96 if (Name == StringRef(ItemStr, BucketItem->getKeyLength())) {
102 // Okay, we didn't find the item. Probe to the next bucket.
103 BucketNo = (BucketNo+ProbeAmt) & (HTSize-1);
105 // Use quadratic probing, it has fewer clumping artifacts than linear
106 // probing and has good cache behavior in the common case.
112 /// FindKey - Look up the bucket that contains the specified key. If it exists
113 /// in the map, return the bucket number of the key. Otherwise return -1.
114 /// This does not modify the map.
115 int StringMapImpl::FindKey(StringRef Key) const {
116 unsigned HTSize = NumBuckets;
117 if (HTSize == 0) return -1; // Really empty table?
118 unsigned FullHashValue = HashString(Key);
119 unsigned BucketNo = FullHashValue & (HTSize-1);
120 unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1);
122 unsigned ProbeAmt = 1;
124 StringMapEntryBase *BucketItem = TheTable[BucketNo];
125 // If we found an empty bucket, this key isn't in the table yet, return.
129 if (BucketItem == getTombstoneVal()) {
130 // Ignore tombstones.
131 } else if (HashTable[BucketNo] == FullHashValue) {
132 // If the full hash value matches, check deeply for a match. The common
133 // case here is that we are only looking at the buckets (for item info
134 // being non-null and for the full hash value) not at the items. This
135 // is important for cache locality.
137 // Do the comparison like this because NameStart isn't necessarily
139 char *ItemStr = (char*)BucketItem+ItemSize;
140 if (Key == StringRef(ItemStr, BucketItem->getKeyLength())) {
146 // Okay, we didn't find the item. Probe to the next bucket.
147 BucketNo = (BucketNo+ProbeAmt) & (HTSize-1);
149 // Use quadratic probing, it has fewer clumping artifacts than linear
150 // probing and has good cache behavior in the common case.
155 /// RemoveKey - Remove the specified StringMapEntry from the table, but do not
156 /// delete it. This aborts if the value isn't in the table.
157 void StringMapImpl::RemoveKey(StringMapEntryBase *V) {
158 const char *VStr = (char*)V + ItemSize;
159 StringMapEntryBase *V2 = RemoveKey(StringRef(VStr, V->getKeyLength()));
161 assert(V == V2 && "Didn't find key?");
164 /// RemoveKey - Remove the StringMapEntry for the specified key from the
165 /// table, returning it. If the key is not in the table, this returns null.
166 StringMapEntryBase *StringMapImpl::RemoveKey(StringRef Key) {
167 int Bucket = FindKey(Key);
168 if (Bucket == -1) return 0;
170 StringMapEntryBase *Result = TheTable[Bucket];
171 TheTable[Bucket] = getTombstoneVal();
174 assert(NumItems + NumTombstones <= NumBuckets);
181 /// RehashTable - Grow the table, redistributing values into the buckets with
182 /// the appropriate mod-of-hashtable-size.
183 void StringMapImpl::RehashTable() {
185 unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1);
187 // If the hash table is now more than 3/4 full, or if fewer than 1/8 of
188 // the buckets are empty (meaning that many are filled with tombstones),
189 // grow/rehash the table.
190 if (NumItems*4 > NumBuckets*3) {
191 NewSize = NumBuckets*2;
192 } else if (NumBuckets-(NumItems+NumTombstones) < NumBuckets/8) {
193 NewSize = NumBuckets;
198 // Allocate one extra bucket which will always be non-empty. This allows the
199 // iterators to stop at end.
200 StringMapEntryBase **NewTableArray =
201 (StringMapEntryBase **)calloc(NewSize+1, sizeof(StringMapEntryBase *) +
203 unsigned *NewHashArray = (unsigned *)(NewTableArray + NewSize + 1);
204 NewTableArray[NewSize] = (StringMapEntryBase*)2;
206 // Rehash all the items into their new buckets. Luckily :) we already have
207 // the hash values available, so we don't have to rehash any strings.
208 for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
209 StringMapEntryBase *Bucket = TheTable[I];
210 if (Bucket && Bucket != getTombstoneVal()) {
211 // Fast case, bucket available.
212 unsigned FullHash = HashTable[I];
213 unsigned NewBucket = FullHash & (NewSize-1);
214 if (NewTableArray[NewBucket] == 0) {
215 NewTableArray[FullHash & (NewSize-1)] = Bucket;
216 NewHashArray[FullHash & (NewSize-1)] = FullHash;
220 // Otherwise probe for a spot.
221 unsigned ProbeSize = 1;
223 NewBucket = (NewBucket + ProbeSize++) & (NewSize-1);
224 } while (NewTableArray[NewBucket]);
226 // Finally found a slot. Fill it in.
227 NewTableArray[NewBucket] = Bucket;
228 NewHashArray[NewBucket] = FullHash;
234 TheTable = NewTableArray;
235 NumBuckets = NewSize;