/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Support/StringMap.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===--- StringMap.cpp - String Hash table map implementation -------------===// |
2 | | // |
3 | | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | | // See https://llvm.org/LICENSE.txt for license information. |
5 | | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | | // |
7 | | //===----------------------------------------------------------------------===// |
8 | | // |
9 | | // This file implements the StringMap class. |
10 | | // |
11 | | //===----------------------------------------------------------------------===// |
12 | | |
13 | | #include "llvm/ADT/StringMap.h" |
14 | | #include "llvm/ADT/StringExtras.h" |
15 | | #include "llvm/Support/Compiler.h" |
16 | | #include "llvm/Support/DJB.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 | 377k | static unsigned getMinBucketToReserveForEntries(unsigned NumEntries) { |
25 | 377k | // Ensure that "NumEntries * 4 < NumBuckets * 3" |
26 | 377k | if (NumEntries == 0) |
27 | 0 | return 0; |
28 | 377k | // +1 is required because of the strict equality. |
29 | 377k | // For example if NumEntries is 48, we need to return 401. |
30 | 377k | return NextPowerOf2(NumEntries * 4 / 3 + 1); |
31 | 377k | } |
32 | | |
33 | 2.24M | StringMapImpl::StringMapImpl(unsigned InitSize, unsigned itemSize) { |
34 | 2.24M | ItemSize = itemSize; |
35 | 2.24M | |
36 | 2.24M | // If a size is specified, initialize the table with that many buckets. |
37 | 2.24M | if (InitSize) { |
38 | 377k | // The table will grow when the number of entries reach 3/4 of the number of |
39 | 377k | // buckets. To guarantee that "InitSize" number of entries can be inserted |
40 | 377k | // in the table without growing, we allocate just what is needed here. |
41 | 377k | init(getMinBucketToReserveForEntries(InitSize)); |
42 | 377k | return; |
43 | 377k | } |
44 | 1.87M | |
45 | 1.87M | // Otherwise, initialize it with zero buckets to avoid the allocation. |
46 | 1.87M | TheTable = nullptr; |
47 | 1.87M | NumBuckets = 0; |
48 | 1.87M | NumItems = 0; |
49 | 1.87M | NumTombstones = 0; |
50 | 1.87M | } |
51 | | |
52 | 4.64M | void StringMapImpl::init(unsigned InitSize) { |
53 | 4.64M | assert((InitSize & (InitSize-1)) == 0 && |
54 | 4.64M | "Init Size must be a power of 2 or zero!"); |
55 | 4.64M | |
56 | 4.64M | unsigned NewNumBuckets = InitSize ? InitSize4.64M : 161 ; |
57 | 4.64M | NumItems = 0; |
58 | 4.64M | NumTombstones = 0; |
59 | 4.64M | |
60 | 4.64M | TheTable = static_cast<StringMapEntryBase **>( |
61 | 4.64M | safe_calloc(NewNumBuckets+1, |
62 | 4.64M | sizeof(StringMapEntryBase **) + sizeof(unsigned))); |
63 | 4.64M | |
64 | 4.64M | // Set the member only if TheTable was successfully allocated |
65 | 4.64M | NumBuckets = NewNumBuckets; |
66 | 4.64M | |
67 | 4.64M | // Allocate one extra bucket, set it to look filled so the iterators stop at |
68 | 4.64M | // end. |
69 | 4.64M | TheTable[NumBuckets] = (StringMapEntryBase*)2; |
70 | 4.64M | } |
71 | | |
72 | | /// LookupBucketFor - Look up the bucket that the specified string should end |
73 | | /// up in. If it already exists as a key in the map, the Item pointer for the |
74 | | /// specified bucket will be non-null. Otherwise, it will be null. In either |
75 | | /// case, the FullHashValue field of the bucket will be set to the hash value |
76 | | /// of the string. |
77 | 1.13G | unsigned StringMapImpl::LookupBucketFor(StringRef Name) { |
78 | 1.13G | unsigned HTSize = NumBuckets; |
79 | 1.13G | if (HTSize == 0) { // Hash table unallocated so far? |
80 | 4.25M | init(16); |
81 | 4.25M | HTSize = NumBuckets; |
82 | 4.25M | } |
83 | 1.13G | unsigned FullHashValue = djbHash(Name, 0); |
84 | 1.13G | unsigned BucketNo = FullHashValue & (HTSize-1); |
85 | 1.13G | unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1); |
86 | 1.13G | |
87 | 1.13G | unsigned ProbeAmt = 1; |
88 | 1.13G | int FirstTombstone = -1; |
89 | 1.76G | while (true1.76G ) { |
90 | 1.76G | StringMapEntryBase *BucketItem = TheTable[BucketNo]; |
91 | 1.76G | // If we found an empty bucket, this key isn't in the table yet, return it. |
92 | 1.76G | if (LLVM_LIKELY(!BucketItem)) { |
93 | 445M | // If we found a tombstone, we want to reuse the tombstone instead of an |
94 | 445M | // empty bucket. This reduces probing. |
95 | 445M | if (FirstTombstone != -1) { |
96 | 1.89M | HashTable[FirstTombstone] = FullHashValue; |
97 | 1.89M | return FirstTombstone; |
98 | 1.89M | } |
99 | 443M | |
100 | 443M | HashTable[BucketNo] = FullHashValue; |
101 | 443M | return BucketNo; |
102 | 443M | } |
103 | 1.32G | |
104 | 1.32G | if (BucketItem == getTombstoneVal()) { |
105 | 3.28M | // Skip over tombstones. However, remember the first one we see. |
106 | 3.28M | if (FirstTombstone == -1) FirstTombstone = BucketNo1.93M ; |
107 | 1.31G | } else if (LLVM_LIKELY(HashTable[BucketNo] == FullHashValue)) { |
108 | 690M | // If the full hash value matches, check deeply for a match. The common |
109 | 690M | // case here is that we are only looking at the buckets (for item info |
110 | 690M | // being non-null and for the full hash value) not at the items. This |
111 | 690M | // is important for cache locality. |
112 | 690M | |
113 | 690M | // Do the comparison like this because Name isn't necessarily |
114 | 690M | // null-terminated! |
115 | 690M | char *ItemStr = (char*)BucketItem+ItemSize; |
116 | 690M | if (Name == StringRef(ItemStr, BucketItem->getKeyLength())) { |
117 | 689M | // We found a match! |
118 | 689M | return BucketNo; |
119 | 689M | } |
120 | 630M | } |
121 | 630M | |
122 | 630M | // Okay, we didn't find the item. Probe to the next bucket. |
123 | 630M | BucketNo = (BucketNo+ProbeAmt) & (HTSize-1); |
124 | 630M | |
125 | 630M | // Use quadratic probing, it has fewer clumping artifacts than linear |
126 | 630M | // probing and has good cache behavior in the common case. |
127 | 630M | ++ProbeAmt; |
128 | 630M | } |
129 | 1.13G | } |
130 | | |
131 | | /// FindKey - Look up the bucket that contains the specified key. If it exists |
132 | | /// in the map, return the bucket number of the key. Otherwise return -1. |
133 | | /// This does not modify the map. |
134 | 127M | int StringMapImpl::FindKey(StringRef Key) const { |
135 | 127M | unsigned HTSize = NumBuckets; |
136 | 127M | if (HTSize == 0) return -18.03M ; // Really empty table? |
137 | 119M | unsigned FullHashValue = djbHash(Key, 0); |
138 | 119M | unsigned BucketNo = FullHashValue & (HTSize-1); |
139 | 119M | unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1); |
140 | 119M | |
141 | 119M | unsigned ProbeAmt = 1; |
142 | 256M | while (true256M ) { |
143 | 256M | StringMapEntryBase *BucketItem = TheTable[BucketNo]; |
144 | 256M | // If we found an empty bucket, this key isn't in the table yet, return. |
145 | 256M | if (LLVM_LIKELY(!BucketItem)) |
146 | 256M | return -174.0M ; |
147 | 182M | |
148 | 182M | if (BucketItem == getTombstoneVal()) { |
149 | 23.2M | // Ignore tombstones. |
150 | 158M | } else if (LLVM_LIKELY(HashTable[BucketNo] == FullHashValue)) { |
151 | 45.8M | // If the full hash value matches, check deeply for a match. The common |
152 | 45.8M | // case here is that we are only looking at the buckets (for item info |
153 | 45.8M | // being non-null and for the full hash value) not at the items. This |
154 | 45.8M | // is important for cache locality. |
155 | 45.8M | |
156 | 45.8M | // Do the comparison like this because NameStart isn't necessarily |
157 | 45.8M | // null-terminated! |
158 | 45.8M | char *ItemStr = (char*)BucketItem+ItemSize; |
159 | 45.8M | if (Key == StringRef(ItemStr, BucketItem->getKeyLength())) { |
160 | 45.8M | // We found a match! |
161 | 45.8M | return BucketNo; |
162 | 45.8M | } |
163 | 136M | } |
164 | 136M | |
165 | 136M | // Okay, we didn't find the item. Probe to the next bucket. |
166 | 136M | BucketNo = (BucketNo+ProbeAmt) & (HTSize-1); |
167 | 136M | |
168 | 136M | // Use quadratic probing, it has fewer clumping artifacts than linear |
169 | 136M | // probing and has good cache behavior in the common case. |
170 | 136M | ++ProbeAmt; |
171 | 136M | } |
172 | 119M | } |
173 | | |
174 | | /// RemoveKey - Remove the specified StringMapEntry from the table, but do not |
175 | | /// delete it. This aborts if the value isn't in the table. |
176 | 12.1M | void StringMapImpl::RemoveKey(StringMapEntryBase *V) { |
177 | 12.1M | const char *VStr = (char*)V + ItemSize; |
178 | 12.1M | StringMapEntryBase *V2 = RemoveKey(StringRef(VStr, V->getKeyLength())); |
179 | 12.1M | (void)V2; |
180 | 12.1M | assert(V == V2 && "Didn't find key?"); |
181 | 12.1M | } |
182 | | |
183 | | /// RemoveKey - Remove the StringMapEntry for the specified key from the |
184 | | /// table, returning it. If the key is not in the table, this returns null. |
185 | 12.1M | StringMapEntryBase *StringMapImpl::RemoveKey(StringRef Key) { |
186 | 12.1M | int Bucket = FindKey(Key); |
187 | 12.1M | if (Bucket == -1) return nullptr0 ; |
188 | 12.1M | |
189 | 12.1M | StringMapEntryBase *Result = TheTable[Bucket]; |
190 | 12.1M | TheTable[Bucket] = getTombstoneVal(); |
191 | 12.1M | --NumItems; |
192 | 12.1M | ++NumTombstones; |
193 | 12.1M | assert(NumItems + NumTombstones <= NumBuckets); |
194 | 12.1M | |
195 | 12.1M | return Result; |
196 | 12.1M | } |
197 | | |
198 | | /// RehashTable - Grow the table, redistributing values into the buckets with |
199 | | /// the appropriate mod-of-hashtable-size. |
200 | 445M | unsigned StringMapImpl::RehashTable(unsigned BucketNo) { |
201 | 445M | unsigned NewSize; |
202 | 445M | unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1); |
203 | 445M | |
204 | 445M | // If the hash table is now more than 3/4 full, or if fewer than 1/8 of |
205 | 445M | // the buckets are empty (meaning that many are filled with tombstones), |
206 | 445M | // grow/rehash the table. |
207 | 445M | if (LLVM_UNLIKELY(NumItems * 4 > NumBuckets * 3)) { |
208 | 3.13M | NewSize = NumBuckets*2; |
209 | 442M | } else if (LLVM_UNLIKELY(NumBuckets - (NumItems + NumTombstones) <= |
210 | 442M | NumBuckets / 8)) { |
211 | 4.75k | NewSize = NumBuckets; |
212 | 442M | } else { |
213 | 442M | return BucketNo; |
214 | 442M | } |
215 | 3.13M | |
216 | 3.13M | unsigned NewBucketNo = BucketNo; |
217 | 3.13M | // Allocate one extra bucket which will always be non-empty. This allows the |
218 | 3.13M | // iterators to stop at end. |
219 | 3.13M | auto NewTableArray = static_cast<StringMapEntryBase **>( |
220 | 3.13M | safe_calloc(NewSize+1, sizeof(StringMapEntryBase *) + sizeof(unsigned))); |
221 | 3.13M | |
222 | 3.13M | unsigned *NewHashArray = (unsigned *)(NewTableArray + NewSize + 1); |
223 | 3.13M | NewTableArray[NewSize] = (StringMapEntryBase*)2; |
224 | 3.13M | |
225 | 3.13M | // Rehash all the items into their new buckets. Luckily :) we already have |
226 | 3.13M | // the hash values available, so we don't have to rehash any strings. |
227 | 469M | for (unsigned I = 0, E = NumBuckets; I != E; ++I466M ) { |
228 | 466M | StringMapEntryBase *Bucket = TheTable[I]; |
229 | 466M | if (Bucket && Bucket != getTombstoneVal()352M ) { |
230 | 352M | // Fast case, bucket available. |
231 | 352M | unsigned FullHash = HashTable[I]; |
232 | 352M | unsigned NewBucket = FullHash & (NewSize-1); |
233 | 352M | if (!NewTableArray[NewBucket]) { |
234 | 285M | NewTableArray[FullHash & (NewSize-1)] = Bucket; |
235 | 285M | NewHashArray[FullHash & (NewSize-1)] = FullHash; |
236 | 285M | if (I == BucketNo) |
237 | 2.38M | NewBucketNo = NewBucket; |
238 | 285M | continue; |
239 | 285M | } |
240 | 67.0M | |
241 | 67.0M | // Otherwise probe for a spot. |
242 | 67.0M | unsigned ProbeSize = 1; |
243 | 103M | do { |
244 | 103M | NewBucket = (NewBucket + ProbeSize++) & (NewSize-1); |
245 | 103M | } while (NewTableArray[NewBucket]); |
246 | 67.0M | |
247 | 67.0M | // Finally found a slot. Fill it in. |
248 | 67.0M | NewTableArray[NewBucket] = Bucket; |
249 | 67.0M | NewHashArray[NewBucket] = FullHash; |
250 | 67.0M | if (I == BucketNo) |
251 | 742k | NewBucketNo = NewBucket; |
252 | 67.0M | } |
253 | 466M | } |
254 | 3.13M | |
255 | 3.13M | free(TheTable); |
256 | 3.13M | |
257 | 3.13M | TheTable = NewTableArray; |
258 | 3.13M | NumBuckets = NewSize; |
259 | 3.13M | NumTombstones = 0; |
260 | 3.13M | return NewBucketNo; |
261 | 3.13M | } |