/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/Support/StringMap.cpp
Line | Count | Source (jump to first uncovered line) |
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 "llvm/Support/MathExtras.h" |
18 | | #include <cassert> |
19 | | |
20 | | using namespace llvm; |
21 | | |
22 | | /// Returns the number of buckets to allocate to ensure that the DenseMap can |
23 | | /// accommodate \p NumEntries without need to grow(). |
24 | 446k | static unsigned getMinBucketToReserveForEntries(unsigned NumEntries) { |
25 | 446k | // Ensure that "NumEntries * 4 < NumBuckets * 3" |
26 | 446k | if (NumEntries == 0) |
27 | 0 | return 0; |
28 | 446k | // +1 is required because of the strict equality. |
29 | 446k | // For example if NumEntries is 48, we need to return 401. |
30 | 446k | return NextPowerOf2(NumEntries * 4 / 3 + 1); |
31 | 446k | } |
32 | | |
33 | 3.14M | StringMapImpl::StringMapImpl(unsigned InitSize, unsigned itemSize) { |
34 | 3.14M | ItemSize = itemSize; |
35 | 3.14M | |
36 | 3.14M | // If a size is specified, initialize the table with that many buckets. |
37 | 3.14M | if (InitSize3.14M ) { |
38 | 446k | // The table will grow when the number of entries reach 3/4 of the number of |
39 | 446k | // buckets. To guarantee that "InitSize" number of entries can be inserted |
40 | 446k | // in the table without growing, we allocate just what is needed here. |
41 | 446k | init(getMinBucketToReserveForEntries(InitSize)); |
42 | 446k | return; |
43 | 446k | } |
44 | 2.69M | |
45 | 2.69M | // Otherwise, initialize it with zero buckets to avoid the allocation. |
46 | 2.69M | TheTable = nullptr; |
47 | 2.69M | NumBuckets = 0; |
48 | 2.69M | NumItems = 0; |
49 | 2.69M | NumTombstones = 0; |
50 | 2.69M | } |
51 | | |
52 | 3.57M | void StringMapImpl::init(unsigned InitSize) { |
53 | 3.57M | assert((InitSize & (InitSize-1)) == 0 && |
54 | 3.57M | "Init Size must be a power of 2 or zero!"); |
55 | 3.57M | |
56 | 3.57M | unsigned NewNumBuckets = InitSize ? InitSize3.57M : 160 ; |
57 | 3.57M | NumItems = 0; |
58 | 3.57M | NumTombstones = 0; |
59 | 3.57M | |
60 | 3.57M | TheTable = (StringMapEntryBase **)calloc(NewNumBuckets+1, |
61 | 3.57M | sizeof(StringMapEntryBase **) + |
62 | 3.57M | sizeof(unsigned)); |
63 | 3.57M | |
64 | 3.57M | if (TheTable == nullptr) |
65 | 0 | report_bad_alloc_error("Allocation of StringMap table failed."); |
66 | 3.57M | |
67 | 3.57M | // Set the member only if TheTable was successfully allocated |
68 | 3.57M | NumBuckets = NewNumBuckets; |
69 | 3.57M | |
70 | 3.57M | // Allocate one extra bucket, set it to look filled so the iterators stop at |
71 | 3.57M | // end. |
72 | 3.57M | TheTable[NumBuckets] = (StringMapEntryBase*)2; |
73 | 3.57M | } |
74 | | |
75 | | /// LookupBucketFor - Look up the bucket that the specified string should end |
76 | | /// up in. If it already exists as a key in the map, the Item pointer for the |
77 | | /// specified bucket will be non-null. Otherwise, it will be null. In either |
78 | | /// case, the FullHashValue field of the bucket will be set to the hash value |
79 | | /// of the string. |
80 | 840M | unsigned StringMapImpl::LookupBucketFor(StringRef Name) { |
81 | 840M | unsigned HTSize = NumBuckets; |
82 | 840M | if (HTSize == 0840M ) { // Hash table unallocated so far? |
83 | 3.11M | init(16); |
84 | 3.11M | HTSize = NumBuckets; |
85 | 3.11M | } |
86 | 840M | unsigned FullHashValue = HashString(Name); |
87 | 840M | unsigned BucketNo = FullHashValue & (HTSize-1); |
88 | 840M | unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1); |
89 | 840M | |
90 | 840M | unsigned ProbeAmt = 1; |
91 | 840M | int FirstTombstone = -1; |
92 | 1.30G | while (true1.30G ) { |
93 | 1.30G | StringMapEntryBase *BucketItem = TheTable[BucketNo]; |
94 | 1.30G | // If we found an empty bucket, this key isn't in the table yet, return it. |
95 | 1.30G | if (LLVM_LIKELY1.30G (!BucketItem)) { |
96 | 348M | // If we found a tombstone, we want to reuse the tombstone instead of an |
97 | 348M | // empty bucket. This reduces probing. |
98 | 348M | if (FirstTombstone != -1348M ) { |
99 | 2.84M | HashTable[FirstTombstone] = FullHashValue; |
100 | 2.84M | return FirstTombstone; |
101 | 2.84M | } |
102 | 346M | |
103 | 346M | HashTable[BucketNo] = FullHashValue; |
104 | 346M | return BucketNo; |
105 | 346M | } |
106 | 952M | |
107 | 952M | if (952M BucketItem == getTombstoneVal()952M ) { |
108 | 4.85M | // Skip over tombstones. However, remember the first one we see. |
109 | 4.85M | if (FirstTombstone == -14.85M ) FirstTombstone = BucketNo2.90M ; |
110 | 952M | } else if (947M LLVM_LIKELY947M (HashTable[BucketNo] == FullHashValue)) { |
111 | 491M | // If the full hash value matches, check deeply for a match. The common |
112 | 491M | // case here is that we are only looking at the buckets (for item info |
113 | 491M | // being non-null and for the full hash value) not at the items. This |
114 | 491M | // is important for cache locality. |
115 | 491M | |
116 | 491M | // Do the comparison like this because Name isn't necessarily |
117 | 491M | // null-terminated! |
118 | 491M | char *ItemStr = (char*)BucketItem+ItemSize; |
119 | 491M | if (Name == StringRef(ItemStr, BucketItem->getKeyLength())491M ) { |
120 | 491M | // We found a match! |
121 | 491M | return BucketNo; |
122 | 491M | } |
123 | 461M | } |
124 | 461M | |
125 | 461M | // Okay, we didn't find the item. Probe to the next bucket. |
126 | 461M | BucketNo = (BucketNo+ProbeAmt) & (HTSize-1); |
127 | 461M | |
128 | 461M | // Use quadratic probing, it has fewer clumping artifacts than linear |
129 | 461M | // probing and has good cache behavior in the common case. |
130 | 461M | ++ProbeAmt; |
131 | 461M | } |
132 | 840M | } |
133 | | |
134 | | /// FindKey - Look up the bucket that contains the specified key. If it exists |
135 | | /// in the map, return the bucket number of the key. Otherwise return -1. |
136 | | /// This does not modify the map. |
137 | 114M | int StringMapImpl::FindKey(StringRef Key) const { |
138 | 114M | unsigned HTSize = NumBuckets; |
139 | 114M | if (HTSize == 0114M ) return -13.43M ; // Really empty table? |
140 | 110M | unsigned FullHashValue = HashString(Key); |
141 | 110M | unsigned BucketNo = FullHashValue & (HTSize-1); |
142 | 110M | unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1); |
143 | 110M | |
144 | 110M | unsigned ProbeAmt = 1; |
145 | 281M | while (true281M ) { |
146 | 281M | StringMapEntryBase *BucketItem = TheTable[BucketNo]; |
147 | 281M | // If we found an empty bucket, this key isn't in the table yet, return. |
148 | 281M | if (LLVM_LIKELY(!BucketItem)) |
149 | 81.9M | return -1; |
150 | 199M | |
151 | 199M | if (199M BucketItem == getTombstoneVal()199M ) { |
152 | 32.1M | // Ignore tombstones. |
153 | 199M | } else if (167M LLVM_LIKELY167M (HashTable[BucketNo] == FullHashValue)) { |
154 | 28.9M | // If the full hash value matches, check deeply for a match. The common |
155 | 28.9M | // case here is that we are only looking at the buckets (for item info |
156 | 28.9M | // being non-null and for the full hash value) not at the items. This |
157 | 28.9M | // is important for cache locality. |
158 | 28.9M | |
159 | 28.9M | // Do the comparison like this because NameStart isn't necessarily |
160 | 28.9M | // null-terminated! |
161 | 28.9M | char *ItemStr = (char*)BucketItem+ItemSize; |
162 | 28.9M | if (Key == StringRef(ItemStr, BucketItem->getKeyLength())28.9M ) { |
163 | 28.9M | // We found a match! |
164 | 28.9M | return BucketNo; |
165 | 28.9M | } |
166 | 170M | } |
167 | 170M | |
168 | 170M | // Okay, we didn't find the item. Probe to the next bucket. |
169 | 170M | BucketNo = (BucketNo+ProbeAmt) & (HTSize-1); |
170 | 170M | |
171 | 170M | // Use quadratic probing, it has fewer clumping artifacts than linear |
172 | 170M | // probing and has good cache behavior in the common case. |
173 | 170M | ++ProbeAmt; |
174 | 170M | } |
175 | 114M | } |
176 | | |
177 | | /// RemoveKey - Remove the specified StringMapEntry from the table, but do not |
178 | | /// delete it. This aborts if the value isn't in the table. |
179 | 14.5M | void StringMapImpl::RemoveKey(StringMapEntryBase *V) { |
180 | 14.5M | const char *VStr = (char*)V + ItemSize; |
181 | 14.5M | StringMapEntryBase *V2 = RemoveKey(StringRef(VStr, V->getKeyLength())); |
182 | 14.5M | (void)V2; |
183 | 14.5M | assert(V == V2 && "Didn't find key?"); |
184 | 14.5M | } |
185 | | |
186 | | /// RemoveKey - Remove the StringMapEntry for the specified key from the |
187 | | /// table, returning it. If the key is not in the table, this returns null. |
188 | 14.5M | StringMapEntryBase *StringMapImpl::RemoveKey(StringRef Key) { |
189 | 14.5M | int Bucket = FindKey(Key); |
190 | 14.5M | if (Bucket == -114.5M ) return nullptr0 ; |
191 | 14.5M | |
192 | 14.5M | StringMapEntryBase *Result = TheTable[Bucket]; |
193 | 14.5M | TheTable[Bucket] = getTombstoneVal(); |
194 | 14.5M | --NumItems; |
195 | 14.5M | ++NumTombstones; |
196 | 14.5M | assert(NumItems + NumTombstones <= NumBuckets); |
197 | 14.5M | |
198 | 14.5M | return Result; |
199 | 14.5M | } |
200 | | |
201 | | /// RehashTable - Grow the table, redistributing values into the buckets with |
202 | | /// the appropriate mod-of-hashtable-size. |
203 | 348M | unsigned StringMapImpl::RehashTable(unsigned BucketNo) { |
204 | 348M | unsigned NewSize; |
205 | 348M | unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1); |
206 | 348M | |
207 | 348M | // If the hash table is now more than 3/4 full, or if fewer than 1/8 of |
208 | 348M | // the buckets are empty (meaning that many are filled with tombstones), |
209 | 348M | // grow/rehash the table. |
210 | 348M | if (LLVM_UNLIKELY348M (NumItems * 4 > NumBuckets * 3)) { |
211 | 2.42M | NewSize = NumBuckets*2; |
212 | 348M | } else if (346M LLVM_UNLIKELY346M (NumBuckets - (NumItems + NumTombstones) <= |
213 | 1.44k | NumBuckets / 8)) { |
214 | 1.44k | NewSize = NumBuckets; |
215 | 346M | } else { |
216 | 346M | return BucketNo; |
217 | 346M | } |
218 | 2.42M | |
219 | 2.42M | unsigned NewBucketNo = BucketNo; |
220 | 2.42M | // Allocate one extra bucket which will always be non-empty. This allows the |
221 | 2.42M | // iterators to stop at end. |
222 | 2.42M | StringMapEntryBase **NewTableArray = |
223 | 2.42M | (StringMapEntryBase **)calloc(NewSize+1, sizeof(StringMapEntryBase *) + |
224 | 2.42M | sizeof(unsigned)); |
225 | 2.42M | |
226 | 2.42M | if (NewTableArray == nullptr) |
227 | 0 | report_bad_alloc_error("Allocation of StringMap hash table failed."); |
228 | 2.42M | |
229 | 2.42M | unsigned *NewHashArray = (unsigned *)(NewTableArray + NewSize + 1); |
230 | 2.42M | NewTableArray[NewSize] = (StringMapEntryBase*)2; |
231 | 2.42M | |
232 | 2.42M | // Rehash all the items into their new buckets. Luckily :) we already have |
233 | 2.42M | // the hash values available, so we don't have to rehash any strings. |
234 | 381M | for (unsigned I = 0, E = NumBuckets; I != E381M ; ++I378M ) { |
235 | 378M | StringMapEntryBase *Bucket = TheTable[I]; |
236 | 378M | if (Bucket && 378M Bucket != getTombstoneVal()286M ) { |
237 | 286M | // Fast case, bucket available. |
238 | 286M | unsigned FullHash = HashTable[I]; |
239 | 286M | unsigned NewBucket = FullHash & (NewSize-1); |
240 | 286M | if (!NewTableArray[NewBucket]286M ) { |
241 | 229M | NewTableArray[FullHash & (NewSize-1)] = Bucket; |
242 | 229M | NewHashArray[FullHash & (NewSize-1)] = FullHash; |
243 | 229M | if (I == BucketNo) |
244 | 1.67M | NewBucketNo = NewBucket; |
245 | 229M | continue; |
246 | 229M | } |
247 | 56.7M | |
248 | 56.7M | // Otherwise probe for a spot. |
249 | 56.7M | unsigned ProbeSize = 1; |
250 | 92.4M | do { |
251 | 92.4M | NewBucket = (NewBucket + ProbeSize++) & (NewSize-1); |
252 | 92.4M | } while (NewTableArray[NewBucket]); |
253 | 56.7M | |
254 | 56.7M | // Finally found a slot. Fill it in. |
255 | 56.7M | NewTableArray[NewBucket] = Bucket; |
256 | 56.7M | NewHashArray[NewBucket] = FullHash; |
257 | 56.7M | if (I == BucketNo) |
258 | 739k | NewBucketNo = NewBucket; |
259 | 286M | } |
260 | 378M | } |
261 | 348M | |
262 | 348M | free(TheTable); |
263 | 348M | |
264 | 348M | TheTable = NewTableArray; |
265 | 348M | NumBuckets = NewSize; |
266 | 348M | NumTombstones = 0; |
267 | 348M | return NewBucketNo; |
268 | 348M | } |