File: | lib/Support/StringMap.cpp |
Warning: | line 228, column 26 Array access (from variable 'NewTableArray') results in a null pointer dereference |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
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 | return NextPowerOf2(NumEntries * 4 / 3 + 1); | |||
32 | } | |||
33 | ||||
34 | StringMapImpl::StringMapImpl(unsigned InitSize, unsigned itemSize) { | |||
35 | ItemSize = itemSize; | |||
36 | ||||
37 | // If a size is specified, initialize the table with that many buckets. | |||
38 | 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 | init(getMinBucketToReserveForEntries(InitSize)); | |||
43 | 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 | void StringMapImpl::init(unsigned InitSize) { | |||
54 | assert((InitSize & (InitSize-1)) == 0 &&(static_cast <bool> ((InitSize & (InitSize-1)) == 0 && "Init Size must be a power of 2 or zero!") ? void (0) : __assert_fail ("(InitSize & (InitSize-1)) == 0 && \"Init Size must be a power of 2 or zero!\"" , "/build/llvm-toolchain-snapshot-7~svn329677/lib/Support/StringMap.cpp" , 55, __extension__ __PRETTY_FUNCTION__)) | |||
55 | "Init Size must be a power of 2 or zero!")(static_cast <bool> ((InitSize & (InitSize-1)) == 0 && "Init Size must be a power of 2 or zero!") ? void (0) : __assert_fail ("(InitSize & (InitSize-1)) == 0 && \"Init Size must be a power of 2 or zero!\"" , "/build/llvm-toolchain-snapshot-7~svn329677/lib/Support/StringMap.cpp" , 55, __extension__ __PRETTY_FUNCTION__)); | |||
56 | ||||
57 | unsigned NewNumBuckets = InitSize ? InitSize : 16; | |||
58 | NumItems = 0; | |||
59 | NumTombstones = 0; | |||
60 | ||||
61 | TheTable = static_cast<StringMapEntryBase **>( | |||
62 | std::calloc(NewNumBuckets+1, | |||
63 | sizeof(StringMapEntryBase **) + sizeof(unsigned))); | |||
64 | if (TheTable == nullptr) | |||
65 | report_bad_alloc_error("Allocation of StringMap table failed."); | |||
66 | ||||
67 | // Set the member only if TheTable was successfully allocated | |||
68 | NumBuckets = NewNumBuckets; | |||
69 | ||||
70 | // Allocate one extra bucket, set it to look filled so the iterators stop at | |||
71 | // end. | |||
72 | TheTable[NumBuckets] = (StringMapEntryBase*)2; | |||
73 | } | |||
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 | unsigned StringMapImpl::LookupBucketFor(StringRef Name) { | |||
81 | unsigned HTSize = NumBuckets; | |||
82 | if (HTSize == 0) { // Hash table unallocated so far? | |||
83 | init(16); | |||
84 | HTSize = NumBuckets; | |||
85 | } | |||
86 | unsigned FullHashValue = djbHash(Name, 0); | |||
87 | unsigned BucketNo = FullHashValue & (HTSize-1); | |||
88 | unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1); | |||
89 | ||||
90 | unsigned ProbeAmt = 1; | |||
91 | int FirstTombstone = -1; | |||
92 | while (true) { | |||
93 | StringMapEntryBase *BucketItem = TheTable[BucketNo]; | |||
94 | // If we found an empty bucket, this key isn't in the table yet, return it. | |||
95 | if (LLVM_LIKELY(!BucketItem)__builtin_expect((bool)(!BucketItem), true)) { | |||
96 | // If we found a tombstone, we want to reuse the tombstone instead of an | |||
97 | // empty bucket. This reduces probing. | |||
98 | if (FirstTombstone != -1) { | |||
99 | HashTable[FirstTombstone] = FullHashValue; | |||
100 | return FirstTombstone; | |||
101 | } | |||
102 | ||||
103 | HashTable[BucketNo] = FullHashValue; | |||
104 | return BucketNo; | |||
105 | } | |||
106 | ||||
107 | if (BucketItem == getTombstoneVal()) { | |||
108 | // Skip over tombstones. However, remember the first one we see. | |||
109 | if (FirstTombstone == -1) FirstTombstone = BucketNo; | |||
110 | } else if (LLVM_LIKELY(HashTable[BucketNo] == FullHashValue)__builtin_expect((bool)(HashTable[BucketNo] == FullHashValue) , true)) { | |||
111 | // If the full hash value matches, check deeply for a match. The common | |||
112 | // case here is that we are only looking at the buckets (for item info | |||
113 | // being non-null and for the full hash value) not at the items. This | |||
114 | // is important for cache locality. | |||
115 | ||||
116 | // Do the comparison like this because Name isn't necessarily | |||
117 | // null-terminated! | |||
118 | char *ItemStr = (char*)BucketItem+ItemSize; | |||
119 | if (Name == StringRef(ItemStr, BucketItem->getKeyLength())) { | |||
120 | // We found a match! | |||
121 | return BucketNo; | |||
122 | } | |||
123 | } | |||
124 | ||||
125 | // Okay, we didn't find the item. Probe to the next bucket. | |||
126 | BucketNo = (BucketNo+ProbeAmt) & (HTSize-1); | |||
127 | ||||
128 | // Use quadratic probing, it has fewer clumping artifacts than linear | |||
129 | // probing and has good cache behavior in the common case. | |||
130 | ++ProbeAmt; | |||
131 | } | |||
132 | } | |||
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 | int StringMapImpl::FindKey(StringRef Key) const { | |||
138 | unsigned HTSize = NumBuckets; | |||
139 | if (HTSize == 0) return -1; // Really empty table? | |||
140 | unsigned FullHashValue = djbHash(Key, 0); | |||
141 | unsigned BucketNo = FullHashValue & (HTSize-1); | |||
142 | unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1); | |||
143 | ||||
144 | unsigned ProbeAmt = 1; | |||
145 | while (true) { | |||
146 | StringMapEntryBase *BucketItem = TheTable[BucketNo]; | |||
147 | // If we found an empty bucket, this key isn't in the table yet, return. | |||
148 | if (LLVM_LIKELY(!BucketItem)__builtin_expect((bool)(!BucketItem), true)) | |||
149 | return -1; | |||
150 | ||||
151 | if (BucketItem == getTombstoneVal()) { | |||
152 | // Ignore tombstones. | |||
153 | } else if (LLVM_LIKELY(HashTable[BucketNo] == FullHashValue)__builtin_expect((bool)(HashTable[BucketNo] == FullHashValue) , true)) { | |||
154 | // If the full hash value matches, check deeply for a match. The common | |||
155 | // case here is that we are only looking at the buckets (for item info | |||
156 | // being non-null and for the full hash value) not at the items. This | |||
157 | // is important for cache locality. | |||
158 | ||||
159 | // Do the comparison like this because NameStart isn't necessarily | |||
160 | // null-terminated! | |||
161 | char *ItemStr = (char*)BucketItem+ItemSize; | |||
162 | if (Key == StringRef(ItemStr, BucketItem->getKeyLength())) { | |||
163 | // We found a match! | |||
164 | return BucketNo; | |||
165 | } | |||
166 | } | |||
167 | ||||
168 | // Okay, we didn't find the item. Probe to the next bucket. | |||
169 | BucketNo = (BucketNo+ProbeAmt) & (HTSize-1); | |||
170 | ||||
171 | // Use quadratic probing, it has fewer clumping artifacts than linear | |||
172 | // probing and has good cache behavior in the common case. | |||
173 | ++ProbeAmt; | |||
174 | } | |||
175 | } | |||
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 | void StringMapImpl::RemoveKey(StringMapEntryBase *V) { | |||
180 | const char *VStr = (char*)V + ItemSize; | |||
181 | StringMapEntryBase *V2 = RemoveKey(StringRef(VStr, V->getKeyLength())); | |||
182 | (void)V2; | |||
183 | assert(V == V2 && "Didn't find key?")(static_cast <bool> (V == V2 && "Didn't find key?" ) ? void (0) : __assert_fail ("V == V2 && \"Didn't find key?\"" , "/build/llvm-toolchain-snapshot-7~svn329677/lib/Support/StringMap.cpp" , 183, __extension__ __PRETTY_FUNCTION__)); | |||
184 | } | |||
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 | StringMapEntryBase *StringMapImpl::RemoveKey(StringRef Key) { | |||
189 | int Bucket = FindKey(Key); | |||
190 | if (Bucket == -1) return nullptr; | |||
191 | ||||
192 | StringMapEntryBase *Result = TheTable[Bucket]; | |||
193 | TheTable[Bucket] = getTombstoneVal(); | |||
194 | --NumItems; | |||
195 | ++NumTombstones; | |||
196 | assert(NumItems + NumTombstones <= NumBuckets)(static_cast <bool> (NumItems + NumTombstones <= NumBuckets ) ? void (0) : __assert_fail ("NumItems + NumTombstones <= NumBuckets" , "/build/llvm-toolchain-snapshot-7~svn329677/lib/Support/StringMap.cpp" , 196, __extension__ __PRETTY_FUNCTION__)); | |||
197 | ||||
198 | return Result; | |||
199 | } | |||
200 | ||||
201 | /// RehashTable - Grow the table, redistributing values into the buckets with | |||
202 | /// the appropriate mod-of-hashtable-size. | |||
203 | unsigned StringMapImpl::RehashTable(unsigned BucketNo) { | |||
204 | unsigned NewSize; | |||
205 | unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1); | |||
206 | ||||
207 | // If the hash table is now more than 3/4 full, or if fewer than 1/8 of | |||
208 | // the buckets are empty (meaning that many are filled with tombstones), | |||
209 | // grow/rehash the table. | |||
210 | if (LLVM_UNLIKELY(NumItems * 4 > NumBuckets * 3)__builtin_expect((bool)(NumItems * 4 > NumBuckets * 3), false )) { | |||
| ||||
211 | NewSize = NumBuckets*2; | |||
212 | } else if (LLVM_UNLIKELY(NumBuckets - (NumItems + NumTombstones) <=__builtin_expect((bool)(NumBuckets - (NumItems + NumTombstones ) <= NumBuckets / 8), false) | |||
213 | NumBuckets / 8)__builtin_expect((bool)(NumBuckets - (NumItems + NumTombstones ) <= NumBuckets / 8), false)) { | |||
214 | NewSize = NumBuckets; | |||
215 | } else { | |||
216 | return BucketNo; | |||
217 | } | |||
218 | ||||
219 | unsigned NewBucketNo = BucketNo; | |||
220 | // Allocate one extra bucket which will always be non-empty. This allows the | |||
221 | // iterators to stop at end. | |||
222 | auto NewTableArray = static_cast<StringMapEntryBase **>( | |||
223 | std::calloc(NewSize+1, sizeof(StringMapEntryBase *) + sizeof(unsigned))); | |||
224 | if (NewTableArray == nullptr) | |||
225 | report_bad_alloc_error("Allocation of StringMap hash table failed."); | |||
226 | ||||
227 | unsigned *NewHashArray = (unsigned *)(NewTableArray + NewSize + 1); | |||
228 | NewTableArray[NewSize] = (StringMapEntryBase*)2; | |||
| ||||
229 | ||||
230 | // Rehash all the items into their new buckets. Luckily :) we already have | |||
231 | // the hash values available, so we don't have to rehash any strings. | |||
232 | for (unsigned I = 0, E = NumBuckets; I != E; ++I) { | |||
233 | StringMapEntryBase *Bucket = TheTable[I]; | |||
234 | if (Bucket && Bucket != getTombstoneVal()) { | |||
235 | // Fast case, bucket available. | |||
236 | unsigned FullHash = HashTable[I]; | |||
237 | unsigned NewBucket = FullHash & (NewSize-1); | |||
238 | if (!NewTableArray[NewBucket]) { | |||
239 | NewTableArray[FullHash & (NewSize-1)] = Bucket; | |||
240 | NewHashArray[FullHash & (NewSize-1)] = FullHash; | |||
241 | if (I == BucketNo) | |||
242 | NewBucketNo = NewBucket; | |||
243 | continue; | |||
244 | } | |||
245 | ||||
246 | // Otherwise probe for a spot. | |||
247 | unsigned ProbeSize = 1; | |||
248 | do { | |||
249 | NewBucket = (NewBucket + ProbeSize++) & (NewSize-1); | |||
250 | } while (NewTableArray[NewBucket]); | |||
251 | ||||
252 | // Finally found a slot. Fill it in. | |||
253 | NewTableArray[NewBucket] = Bucket; | |||
254 | NewHashArray[NewBucket] = FullHash; | |||
255 | if (I == BucketNo) | |||
256 | NewBucketNo = NewBucket; | |||
257 | } | |||
258 | } | |||
259 | ||||
260 | free(TheTable); | |||
261 | ||||
262 | TheTable = NewTableArray; | |||
263 | NumBuckets = NewSize; | |||
264 | NumTombstones = 0; | |||
265 | return NewBucketNo; | |||
266 | } |