1 | //===- StringMap.h - String Hash table map interface ------------*- C++ -*-===// |
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 | /// \file |
10 | /// This file defines the StringMap class. |
11 | /// |
12 | //===----------------------------------------------------------------------===// |
13 | |
14 | #ifndef LLVM_ADT_STRINGMAP_H |
15 | #define LLVM_ADT_STRINGMAP_H |
16 | |
17 | #include "llvm/ADT/StringMapEntry.h" |
18 | #include "llvm/ADT/iterator.h" |
19 | #include "llvm/Support/AllocatorBase.h" |
20 | #include "llvm/Support/PointerLikeTypeTraits.h" |
21 | #include <initializer_list> |
22 | #include <iterator> |
23 | |
24 | namespace llvm { |
25 | |
26 | template <typename ValueTy> class StringMapConstIterator; |
27 | template <typename ValueTy> class StringMapIterator; |
28 | template <typename ValueTy> class StringMapKeyIterator; |
29 | |
30 | /// StringMapImpl - This is the base class of StringMap that is shared among |
31 | /// all of its instantiations. |
32 | class StringMapImpl { |
33 | protected: |
34 | // Array of NumBuckets pointers to entries, null pointers are holes. |
35 | // TheTable[NumBuckets] contains a sentinel value for easy iteration. Followed |
36 | // by an array of the actual hash values as unsigned integers. |
37 | StringMapEntryBase **TheTable = nullptr; |
38 | unsigned NumBuckets = 0; |
39 | unsigned NumItems = 0; |
40 | unsigned NumTombstones = 0; |
41 | unsigned ItemSize; |
42 | |
43 | protected: |
44 | explicit StringMapImpl(unsigned itemSize) : ItemSize(itemSize) {} |
45 | StringMapImpl(StringMapImpl &&RHS) |
46 | : TheTable(RHS.TheTable), NumBuckets(RHS.NumBuckets), |
47 | NumItems(RHS.NumItems), NumTombstones(RHS.NumTombstones), |
48 | ItemSize(RHS.ItemSize) { |
49 | RHS.TheTable = nullptr; |
50 | RHS.NumBuckets = 0; |
51 | RHS.NumItems = 0; |
52 | RHS.NumTombstones = 0; |
53 | } |
54 | |
55 | StringMapImpl(unsigned InitSize, unsigned ItemSize); |
56 | unsigned RehashTable(unsigned BucketNo = 0); |
57 | |
58 | /// LookupBucketFor - Look up the bucket that the specified string should end |
59 | /// up in. If it already exists as a key in the map, the Item pointer for the |
60 | /// specified bucket will be non-null. Otherwise, it will be null. In either |
61 | /// case, the FullHashValue field of the bucket will be set to the hash value |
62 | /// of the string. |
63 | unsigned LookupBucketFor(StringRef Key); |
64 | |
65 | /// FindKey - Look up the bucket that contains the specified key. If it exists |
66 | /// in the map, return the bucket number of the key. Otherwise return -1. |
67 | /// This does not modify the map. |
68 | int FindKey(StringRef Key) const; |
69 | |
70 | /// RemoveKey - Remove the specified StringMapEntry from the table, but do not |
71 | /// delete it. This aborts if the value isn't in the table. |
72 | void RemoveKey(StringMapEntryBase *V); |
73 | |
74 | /// RemoveKey - Remove the StringMapEntry for the specified key from the |
75 | /// table, returning it. If the key is not in the table, this returns null. |
76 | StringMapEntryBase *RemoveKey(StringRef Key); |
77 | |
78 | /// Allocate the table with the specified number of buckets and otherwise |
79 | /// setup the map as empty. |
80 | void init(unsigned Size); |
81 | |
82 | public: |
83 | static constexpr uintptr_t TombstoneIntVal = |
84 | static_cast<uintptr_t>(-1) |
85 | << PointerLikeTypeTraits<StringMapEntryBase *>::NumLowBitsAvailable; |
86 | |
87 | static StringMapEntryBase *getTombstoneVal() { |
88 | return reinterpret_cast<StringMapEntryBase *>(TombstoneIntVal); |
89 | } |
90 | |
91 | unsigned getNumBuckets() const { return NumBuckets; } |
92 | unsigned getNumItems() const { return NumItems; } |
93 | |
94 | bool empty() const { return NumItems == 0; } |
95 | unsigned size() const { return NumItems; } |
96 | |
97 | void swap(StringMapImpl &Other) { |
98 | std::swap(TheTable, Other.TheTable); |
99 | std::swap(NumBuckets, Other.NumBuckets); |
100 | std::swap(NumItems, Other.NumItems); |
101 | std::swap(NumTombstones, Other.NumTombstones); |
102 | } |
103 | }; |
104 | |
105 | /// StringMap - This is an unconventional map that is specialized for handling |
106 | /// keys that are "strings", which are basically ranges of bytes. This does some |
107 | /// funky memory allocation and hashing things to make it extremely efficient, |
108 | /// storing the string data *after* the value in the map. |
109 | template <typename ValueTy, typename AllocatorTy = MallocAllocator> |
110 | class StringMap : public StringMapImpl { |
111 | AllocatorTy Allocator; |
112 | |
113 | public: |
114 | using MapEntryTy = StringMapEntry<ValueTy>; |
115 | |
116 | StringMap() : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {} |
117 | |
118 | explicit StringMap(unsigned InitialSize) |
119 | : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))) {} |
120 | |
121 | explicit StringMap(AllocatorTy A) |
122 | : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))), Allocator(A) { |
123 | } |
124 | |
125 | StringMap(unsigned InitialSize, AllocatorTy A) |
126 | : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))), |
127 | Allocator(A) {} |
128 | |
129 | StringMap(std::initializer_list<std::pair<StringRef, ValueTy>> List) |
130 | : StringMapImpl(List.size(), static_cast<unsigned>(sizeof(MapEntryTy))) { |
131 | insert(List); |
132 | } |
133 | |
134 | StringMap(StringMap &&RHS) |
135 | : StringMapImpl(std::move(RHS)), Allocator(std::move(RHS.Allocator)) {} |
136 | |
137 | StringMap(const StringMap &RHS) |
138 | : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))), |
139 | Allocator(RHS.Allocator) { |
140 | if (RHS.empty()) |
141 | return; |
142 | |
143 | // Allocate TheTable of the same size as RHS's TheTable, and set the |
144 | // sentinel appropriately (and NumBuckets). |
145 | init(RHS.NumBuckets); |
146 | unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1), |
147 | *RHSHashTable = (unsigned *)(RHS.TheTable + NumBuckets + 1); |
148 | |
149 | NumItems = RHS.NumItems; |
150 | NumTombstones = RHS.NumTombstones; |
151 | for (unsigned I = 0, E = NumBuckets; I != E; ++I) { |
152 | StringMapEntryBase *Bucket = RHS.TheTable[I]; |
153 | if (!Bucket || Bucket == getTombstoneVal()) { |
154 | TheTable[I] = Bucket; |
155 | continue; |
156 | } |
157 | |
158 | TheTable[I] = MapEntryTy::Create( |
159 | static_cast<MapEntryTy *>(Bucket)->getKey(), Allocator, |
160 | static_cast<MapEntryTy *>(Bucket)->getValue()); |
161 | HashTable[I] = RHSHashTable[I]; |
162 | } |
163 | |
164 | // Note that here we've copied everything from the RHS into this object, |
165 | // tombstones included. We could, instead, have re-probed for each key to |
166 | // instantiate this new object without any tombstone buckets. The |
167 | // assumption here is that items are rarely deleted from most StringMaps, |
168 | // and so tombstones are rare, so the cost of re-probing for all inputs is |
169 | // not worthwhile. |
170 | } |
171 | |
172 | StringMap &operator=(StringMap RHS) { |
173 | StringMapImpl::swap(RHS); |
174 | std::swap(Allocator, RHS.Allocator); |
175 | return *this; |
176 | } |
177 | |
178 | ~StringMap() { |
179 | // Delete all the elements in the map, but don't reset the elements |
180 | // to default values. This is a copy of clear(), but avoids unnecessary |
181 | // work not required in the destructor. |
182 | if (!empty()) { |
183 | for (unsigned I = 0, E = NumBuckets; I != E; ++I) { |
184 | StringMapEntryBase *Bucket = TheTable[I]; |
185 | if (Bucket && Bucket != getTombstoneVal()) { |
186 | static_cast<MapEntryTy *>(Bucket)->Destroy(Allocator); |
187 | } |
188 | } |
189 | } |
190 | free(TheTable); |
191 | } |
192 | |
193 | AllocatorTy &getAllocator() { return Allocator; } |
194 | const AllocatorTy &getAllocator() const { return Allocator; } |
195 | |
196 | using key_type = const char *; |
197 | using mapped_type = ValueTy; |
198 | using value_type = StringMapEntry<ValueTy>; |
199 | using size_type = size_t; |
200 | |
201 | using const_iterator = StringMapConstIterator<ValueTy>; |
202 | using iterator = StringMapIterator<ValueTy>; |
203 | |
204 | iterator begin() { return iterator(TheTable, NumBuckets == 0); } |
205 | iterator end() { return iterator(TheTable + NumBuckets, true); } |
206 | const_iterator begin() const { |
207 | return const_iterator(TheTable, NumBuckets == 0); |
208 | } |
209 | const_iterator end() const { |
210 | return const_iterator(TheTable + NumBuckets, true); |
211 | } |
212 | |
213 | iterator_range<StringMapKeyIterator<ValueTy>> keys() const { |
214 | return make_range(StringMapKeyIterator<ValueTy>(begin()), |
215 | StringMapKeyIterator<ValueTy>(end())); |
216 | } |
217 | |
218 | iterator find(StringRef Key) { |
219 | int Bucket = FindKey(Key); |
220 | if (Bucket == -1) |
221 | return end(); |
222 | return iterator(TheTable + Bucket, true); |
223 | } |
224 | |
225 | const_iterator find(StringRef Key) const { |
226 | int Bucket = FindKey(Key); |
227 | if (Bucket == -1) |
228 | return end(); |
229 | return const_iterator(TheTable + Bucket, true); |
230 | } |
231 | |
232 | /// lookup - Return the entry for the specified key, or a default |
233 | /// constructed value if no such entry exists. |
234 | ValueTy lookup(StringRef Key) const { |
235 | const_iterator it = find(Key); |
236 | if (it != end()) |
237 | return it->second; |
238 | return ValueTy(); |
239 | } |
240 | |
241 | /// Lookup the ValueTy for the \p Key, or create a default constructed value |
242 | /// if the key is not in the map. |
243 | ValueTy &operator[](StringRef Key) { return try_emplace(Key).first->second; } |
244 | |
245 | /// count - Return 1 if the element is in the map, 0 otherwise. |
246 | size_type count(StringRef Key) const { return find(Key) == end() ? 0 : 1; } |
247 | |
248 | template <typename InputTy> |
249 | size_type count(const StringMapEntry<InputTy> &MapEntry) const { |
250 | return count(MapEntry.getKey()); |
251 | } |
252 | |
253 | /// equal - check whether both of the containers are equal. |
254 | bool operator==(const StringMap &RHS) const { |
255 | if (size() != RHS.size()) |
256 | return false; |
257 | |
258 | for (const auto &KeyValue : *this) { |
259 | auto FindInRHS = RHS.find(KeyValue.getKey()); |
260 | |
261 | if (FindInRHS == RHS.end()) |
262 | return false; |
263 | |
264 | if (!(KeyValue.getValue() == FindInRHS->getValue())) |
265 | return false; |
266 | } |
267 | |
268 | return true; |
269 | } |
270 | |
271 | bool operator!=(const StringMap &RHS) const { return !(*this == RHS); } |
272 | |
273 | /// insert - Insert the specified key/value pair into the map. If the key |
274 | /// already exists in the map, return false and ignore the request, otherwise |
275 | /// insert it and return true. |
276 | bool insert(MapEntryTy *KeyValue) { |
277 | unsigned BucketNo = LookupBucketFor(KeyValue->getKey()); |
278 | StringMapEntryBase *&Bucket = TheTable[BucketNo]; |
279 | if (Bucket && Bucket != getTombstoneVal()) |
280 | return false; // Already exists in map. |
281 | |
282 | if (Bucket == getTombstoneVal()) |
283 | --NumTombstones; |
284 | Bucket = KeyValue; |
285 | ++NumItems; |
286 | assert(NumItems + NumTombstones <= NumBuckets); |
287 | |
288 | RehashTable(); |
289 | return true; |
290 | } |
291 | |
292 | /// insert - Inserts the specified key/value pair into the map if the key |
293 | /// isn't already in the map. The bool component of the returned pair is true |
294 | /// if and only if the insertion takes place, and the iterator component of |
295 | /// the pair points to the element with key equivalent to the key of the pair. |
296 | std::pair<iterator, bool> insert(std::pair<StringRef, ValueTy> KV) { |
297 | return try_emplace(KV.first, std::move(KV.second)); |
298 | } |
299 | |
300 | /// Inserts elements from range [first, last). If multiple elements in the |
301 | /// range have keys that compare equivalent, it is unspecified which element |
302 | /// is inserted . |
303 | template <typename InputIt> void insert(InputIt First, InputIt Last) { |
304 | for (InputIt It = First; It != Last; ++It) |
305 | insert(*It); |
306 | } |
307 | |
308 | /// Inserts elements from initializer list ilist. If multiple elements in |
309 | /// the range have keys that compare equivalent, it is unspecified which |
310 | /// element is inserted |
311 | void insert(std::initializer_list<std::pair<StringRef, ValueTy>> List) { |
312 | insert(List.begin(), List.end()); |
313 | } |
314 | |
315 | /// Inserts an element or assigns to the current element if the key already |
316 | /// exists. The return type is the same as try_emplace. |
317 | template <typename V> |
318 | std::pair<iterator, bool> insert_or_assign(StringRef Key, V &&Val) { |
319 | auto Ret = try_emplace(Key, std::forward<V>(Val)); |
320 | if (!Ret.second) |
321 | Ret.first->second = std::forward<V>(Val); |
322 | return Ret; |
323 | } |
324 | |
325 | /// Emplace a new element for the specified key into the map if the key isn't |
326 | /// already in the map. The bool component of the returned pair is true |
327 | /// if and only if the insertion takes place, and the iterator component of |
328 | /// the pair points to the element with key equivalent to the key of the pair. |
329 | template <typename... ArgsTy> |
330 | std::pair<iterator, bool> try_emplace(StringRef Key, ArgsTy &&... Args) { |
331 | unsigned BucketNo = LookupBucketFor(Key); |
332 | StringMapEntryBase *&Bucket = TheTable[BucketNo]; |
333 | if (Bucket && Bucket != getTombstoneVal()) |
334 | return std::make_pair(iterator(TheTable + BucketNo, false), |
335 | false); // Already exists in map. |
336 | |
337 | if (Bucket == getTombstoneVal()) |
338 | --NumTombstones; |
339 | Bucket = MapEntryTy::Create(Key, Allocator, std::forward<ArgsTy>(Args)...); |
340 | ++NumItems; |
341 | assert(NumItems + NumTombstones <= NumBuckets); |
342 | |
343 | BucketNo = RehashTable(BucketNo); |
344 | return std::make_pair(iterator(TheTable + BucketNo, false), true); |
345 | } |
346 | |
347 | // clear - Empties out the StringMap |
348 | void clear() { |
349 | if (empty()) |
350 | return; |
351 | |
352 | // Zap all values, resetting the keys back to non-present (not tombstone), |
353 | // which is safe because we're removing all elements. |
354 | for (unsigned I = 0, E = NumBuckets; I != E; ++I) { |
355 | StringMapEntryBase *&Bucket = TheTable[I]; |
356 | if (Bucket && Bucket != getTombstoneVal()) { |
357 | static_cast<MapEntryTy *>(Bucket)->Destroy(Allocator); |
358 | } |
359 | Bucket = nullptr; |
360 | } |
361 | |
362 | NumItems = 0; |
363 | NumTombstones = 0; |
364 | } |
365 | |
366 | /// remove - Remove the specified key/value pair from the map, but do not |
367 | /// erase it. This aborts if the key is not in the map. |
368 | void remove(MapEntryTy *KeyValue) { RemoveKey(KeyValue); } |
369 | |
370 | void erase(iterator I) { |
371 | MapEntryTy &V = *I; |
372 | remove(&V); |
373 | V.Destroy(Allocator); |
374 | } |
375 | |
376 | bool erase(StringRef Key) { |
377 | iterator I = find(Key); |
378 | if (I == end()) |
379 | return false; |
380 | erase(I); |
381 | return true; |
382 | } |
383 | }; |
384 | |
385 | template <typename DerivedTy, typename ValueTy> |
386 | class StringMapIterBase |
387 | : public iterator_facade_base<DerivedTy, std::forward_iterator_tag, |
388 | ValueTy> { |
389 | protected: |
390 | StringMapEntryBase **Ptr = nullptr; |
391 | |
392 | public: |
393 | StringMapIterBase() = default; |
394 | |
395 | explicit StringMapIterBase(StringMapEntryBase **Bucket, |
396 | bool NoAdvance = false) |
397 | : Ptr(Bucket) { |
398 | if (!NoAdvance) |
399 | AdvancePastEmptyBuckets(); |
400 | } |
401 | |
402 | DerivedTy &operator=(const DerivedTy &Other) { |
403 | Ptr = Other.Ptr; |
404 | return static_cast<DerivedTy &>(*this); |
405 | } |
406 | |
407 | friend bool operator==(const DerivedTy &LHS, const DerivedTy &RHS) { |
408 | return LHS.Ptr == RHS.Ptr; |
409 | } |
410 | |
411 | DerivedTy &operator++() { // Preincrement |
412 | ++Ptr; |
413 | AdvancePastEmptyBuckets(); |
414 | return static_cast<DerivedTy &>(*this); |
415 | } |
416 | |
417 | DerivedTy operator++(int) { // Post-increment |
418 | DerivedTy Tmp(Ptr); |
419 | ++*this; |
420 | return Tmp; |
421 | } |
422 | |
423 | private: |
424 | void AdvancePastEmptyBuckets() { |
425 | while (*Ptr == nullptr || *Ptr == StringMapImpl::getTombstoneVal()) |
426 | ++Ptr; |
427 | } |
428 | }; |
429 | |
430 | template <typename ValueTy> |
431 | class StringMapConstIterator |
432 | : public StringMapIterBase<StringMapConstIterator<ValueTy>, |
433 | const StringMapEntry<ValueTy>> { |
434 | using base = StringMapIterBase<StringMapConstIterator<ValueTy>, |
435 | const StringMapEntry<ValueTy>>; |
436 | |
437 | public: |
438 | StringMapConstIterator() = default; |
439 | explicit StringMapConstIterator(StringMapEntryBase **Bucket, |
440 | bool NoAdvance = false) |
441 | : base(Bucket, NoAdvance) {} |
442 | |
443 | const StringMapEntry<ValueTy> &operator*() const { |
444 | return *static_cast<const StringMapEntry<ValueTy> *>(*this->Ptr); |
445 | } |
446 | }; |
447 | |
448 | template <typename ValueTy> |
449 | class StringMapIterator : public StringMapIterBase<StringMapIterator<ValueTy>, |
450 | StringMapEntry<ValueTy>> { |
451 | using base = |
452 | StringMapIterBase<StringMapIterator<ValueTy>, StringMapEntry<ValueTy>>; |
453 | |
454 | public: |
455 | StringMapIterator() = default; |
456 | explicit StringMapIterator(StringMapEntryBase **Bucket, |
457 | bool NoAdvance = false) |
458 | : base(Bucket, NoAdvance) {} |
459 | |
460 | StringMapEntry<ValueTy> &operator*() const { |
461 | return *static_cast<StringMapEntry<ValueTy> *>(*this->Ptr); |
462 | } |
463 | |
464 | operator StringMapConstIterator<ValueTy>() const { |
465 | return StringMapConstIterator<ValueTy>(this->Ptr, true); |
466 | } |
467 | }; |
468 | |
469 | template <typename ValueTy> |
470 | class StringMapKeyIterator |
471 | : public iterator_adaptor_base<StringMapKeyIterator<ValueTy>, |
472 | StringMapConstIterator<ValueTy>, |
473 | std::forward_iterator_tag, StringRef> { |
474 | using base = iterator_adaptor_base<StringMapKeyIterator<ValueTy>, |
475 | StringMapConstIterator<ValueTy>, |
476 | std::forward_iterator_tag, StringRef>; |
477 | |
478 | public: |
479 | StringMapKeyIterator() = default; |
480 | explicit StringMapKeyIterator(StringMapConstIterator<ValueTy> Iter) |
481 | : base(std::move(Iter)) {} |
482 | |
483 | StringRef operator*() const { return this->wrapped()->getKey(); } |
484 | }; |
485 | |
486 | } // end namespace llvm |
487 | |
488 | #endif // LLVM_ADT_STRINGMAP_H |
489 | |