]>
Commit | Line | Data |
---|---|---|
223e47cc LB |
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. | |
1a4d82fc | 30 | TheTable = nullptr; |
223e47cc LB |
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. | |
1a4d82fc | 73 | if (LLVM_LIKELY(!BucketItem)) { |
223e47cc LB |
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. | |
1a4d82fc | 127 | if (LLVM_LIKELY(!BucketItem)) |
223e47cc LB |
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); | |
1a4d82fc | 169 | if (Bucket == -1) return nullptr; |
223e47cc LB |
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. | |
1a4d82fc | 184 | unsigned StringMapImpl::RehashTable(unsigned BucketNo) { |
223e47cc LB |
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 (NumItems*4 > NumBuckets*3) { | |
192 | NewSize = NumBuckets*2; | |
193 | } else if (NumBuckets-(NumItems+NumTombstones) <= NumBuckets/8) { | |
194 | NewSize = NumBuckets; | |
195 | } else { | |
1a4d82fc | 196 | return BucketNo; |
223e47cc LB |
197 | } |
198 | ||
1a4d82fc | 199 | unsigned NewBucketNo = BucketNo; |
223e47cc LB |
200 | // Allocate one extra bucket which will always be non-empty. This allows the |
201 | // iterators to stop at end. | |
202 | StringMapEntryBase **NewTableArray = | |
203 | (StringMapEntryBase **)calloc(NewSize+1, sizeof(StringMapEntryBase *) + | |
204 | sizeof(unsigned)); | |
205 | unsigned *NewHashArray = (unsigned *)(NewTableArray + NewSize + 1); | |
206 | NewTableArray[NewSize] = (StringMapEntryBase*)2; | |
207 | ||
208 | // Rehash all the items into their new buckets. Luckily :) we already have | |
209 | // the hash values available, so we don't have to rehash any strings. | |
210 | for (unsigned I = 0, E = NumBuckets; I != E; ++I) { | |
211 | StringMapEntryBase *Bucket = TheTable[I]; | |
212 | if (Bucket && Bucket != getTombstoneVal()) { | |
213 | // Fast case, bucket available. | |
214 | unsigned FullHash = HashTable[I]; | |
215 | unsigned NewBucket = FullHash & (NewSize-1); | |
1a4d82fc | 216 | if (!NewTableArray[NewBucket]) { |
223e47cc LB |
217 | NewTableArray[FullHash & (NewSize-1)] = Bucket; |
218 | NewHashArray[FullHash & (NewSize-1)] = FullHash; | |
1a4d82fc JJ |
219 | if (I == BucketNo) |
220 | NewBucketNo = NewBucket; | |
223e47cc LB |
221 | continue; |
222 | } | |
223 | ||
224 | // Otherwise probe for a spot. | |
225 | unsigned ProbeSize = 1; | |
226 | do { | |
227 | NewBucket = (NewBucket + ProbeSize++) & (NewSize-1); | |
228 | } while (NewTableArray[NewBucket]); | |
229 | ||
230 | // Finally found a slot. Fill it in. | |
231 | NewTableArray[NewBucket] = Bucket; | |
232 | NewHashArray[NewBucket] = FullHash; | |
1a4d82fc JJ |
233 | if (I == BucketNo) |
234 | NewBucketNo = NewBucket; | |
223e47cc LB |
235 | } |
236 | } | |
237 | ||
238 | free(TheTable); | |
239 | ||
240 | TheTable = NewTableArray; | |
241 | NumBuckets = NewSize; | |
242 | NumTombstones = 0; | |
1a4d82fc | 243 | return NewBucketNo; |
223e47cc | 244 | } |