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