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