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