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  unsigned StrLen;
41
42public:
43  explicit StringMapEntryBase(unsigned Len) : StrLen(Len) {}
44
45  unsigned 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(unsigned strLen)
131    : StringMapEntryBase(strLen), second() {}
132  template <typename... InitTy>
133  StringMapEntry(unsigned 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    unsigned KeyLength = Key.size();
159
160    // Allocate a new item with space for the string at the end and a null
161    // terminator.
162    unsigned AllocSize = static_cast<unsigned>(sizeof(StringMapEntry))+
163      KeyLength+1;
164    unsigned Alignment = alignof(StringMapEntry);
165
166    StringMapEntry *NewItem =
167      static_cast<StringMapEntry*>(Allocator.Allocate(AllocSize,Alignment));
168
169    if (NewItem == nullptr)
170      report_bad_alloc_error("Allocation of StringMap entry failed.");
171
172    // Construct the value.
173    new (NewItem) StringMapEntry(KeyLength, std::forward<InitTy>(InitVals)...);
174
175    // Copy the string information.
176    char *StrBuffer = const_cast<char*>(NewItem->getKeyData());
177    if (KeyLength > 0)
178      memcpy(StrBuffer, Key.data(), KeyLength);
179    StrBuffer[KeyLength] = 0;  // Null terminate for convenience of clients.
180    return NewItem;
181  }
182
183  /// Create - Create a StringMapEntry with normal malloc/free.
184  template <typename... InitType>
185  static StringMapEntry *Create(StringRef Key, InitType &&... InitVal) {
186    MallocAllocator A;
187    return Create(Key, A, std::forward<InitType>(InitVal)...);
188  }
189
190  static StringMapEntry *Create(StringRef Key) {
191    return Create(Key, ValueTy());
192  }
193
194  /// GetStringMapEntryFromKeyData - Given key data that is known to be embedded
195  /// into a StringMapEntry, return the StringMapEntry itself.
196  static StringMapEntry &GetStringMapEntryFromKeyData(const char *KeyData) {
197    char *Ptr = const_cast<char*>(KeyData) - sizeof(StringMapEntry<ValueTy>);
198    return *reinterpret_cast<StringMapEntry*>(Ptr);
199  }
200
201  /// Destroy - Destroy this StringMapEntry, releasing memory back to the
202  /// specified allocator.
203  template<typename AllocatorTy>
204  void Destroy(AllocatorTy &Allocator) {
205    // Free memory referenced by the item.
206    unsigned AllocSize =
207        static_cast<unsigned>(sizeof(StringMapEntry)) + getKeyLength() + 1;
208    this->~StringMapEntry();
209    Allocator.Deallocate(static_cast<void *>(this), AllocSize);
210  }
211
212  /// Destroy this object, releasing memory back to the malloc allocator.
213  void Destroy() {
214    MallocAllocator A;
215    Destroy(A);
216  }
217};
218
219/// StringMap - This is an unconventional map that is specialized for handling
220/// keys that are "strings", which are basically ranges of bytes. This does some
221/// funky memory allocation and hashing things to make it extremely efficient,
222/// storing the string data *after* the value in the map.
223template<typename ValueTy, typename AllocatorTy = MallocAllocator>
224class StringMap : public StringMapImpl {
225  AllocatorTy Allocator;
226
227public:
228  using MapEntryTy = StringMapEntry<ValueTy>;
229
230  StringMap() : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {}
231
232  explicit StringMap(unsigned InitialSize)
233    : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))) {}
234
235  explicit StringMap(AllocatorTy A)
236    : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))), Allocator(A) {}
237
238  StringMap(unsigned InitialSize, AllocatorTy A)
239    : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))),
240      Allocator(A) {}
241
242  StringMap(std::initializer_list<std::pair<StringRef, ValueTy>> List)
243      : StringMapImpl(List.size(), static_cast<unsigned>(sizeof(MapEntryTy))) {
244    for (const auto &P : List) {
245      insert(P);
246    }
247  }
248
249  StringMap(StringMap &&RHS)
250      : StringMapImpl(std::move(RHS)), Allocator(std::move(RHS.Allocator)) {}
251
252  StringMap(const StringMap &RHS) :
253    StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))),
254    Allocator(RHS.Allocator) {
255    if (RHS.empty())
256      return;
257
258    // Allocate TheTable of the same size as RHS's TheTable, and set the
259    // sentinel appropriately (and NumBuckets).
260    init(RHS.NumBuckets);
261    unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1),
262             *RHSHashTable = (unsigned *)(RHS.TheTable + NumBuckets + 1);
263
264    NumItems = RHS.NumItems;
265    NumTombstones = RHS.NumTombstones;
266    for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
267      StringMapEntryBase *Bucket = RHS.TheTable[I];
268      if (!Bucket || Bucket == getTombstoneVal()) {
269        TheTable[I] = Bucket;
270        continue;
271      }
272
273      TheTable[I] = MapEntryTy::Create(
274          static_cast<MapEntryTy *>(Bucket)->getKey(), Allocator,
275          static_cast<MapEntryTy *>(Bucket)->getValue());
276      HashTable[I] = RHSHashTable[I];
277    }
278
279    // Note that here we've copied everything from the RHS into this object,
280    // tombstones included. We could, instead, have re-probed for each key to
281    // instantiate this new object without any tombstone buckets. The
282    // assumption here is that items are rarely deleted from most StringMaps,
283    // and so tombstones are rare, so the cost of re-probing for all inputs is
284    // not worthwhile.
285  }
286
287  StringMap &operator=(StringMap RHS) {
288    StringMapImpl::swap(RHS);
289    std::swap(Allocator, RHS.Allocator);
290    return *this;
291  }
292
293  ~StringMap() {
294    // Delete all the elements in the map, but don't reset the elements
295    // to default values.  This is a copy of clear(), but avoids unnecessary
296    // work not required in the destructor.
297    if (!empty()) {
298      for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
299        StringMapEntryBase *Bucket = TheTable[I];
300        if (Bucket && Bucket != getTombstoneVal()) {
301          static_cast<MapEntryTy*>(Bucket)->Destroy(Allocator);
302        }
303      }
304    }
305    free(TheTable);
306  }
307
308  AllocatorTy &getAllocator() { return Allocator; }
309  const AllocatorTy &getAllocator() const { return Allocator; }
310
311  using key_type = const char*;
312  using mapped_type = ValueTy;
313  using value_type = StringMapEntry<ValueTy>;
314  using size_type = size_t;
315
316  using const_iterator = StringMapConstIterator<ValueTy>;
317  using iterator = StringMapIterator<ValueTy>;
318
319  iterator begin() {
320    return iterator(TheTable, NumBuckets == 0);
321  }
322  iterator end() {
323    return iterator(TheTable+NumBuckets, true);
324  }
325  const_iterator begin() const {
326    return const_iterator(TheTable, NumBuckets == 0);
327  }
328  const_iterator end() const {
329    return const_iterator(TheTable+NumBuckets, true);
330  }
331
332  iterator_range<StringMapKeyIterator<ValueTy>> keys() const {
333    return make_range(StringMapKeyIterator<ValueTy>(begin()),
334                      StringMapKeyIterator<ValueTy>(end()));
335  }
336
337  iterator find(StringRef Key) {
338    int Bucket = FindKey(Key);
339    if (Bucket == -1) return end();
340    return iterator(TheTable+Bucket, true);
341  }
342
343  const_iterator find(StringRef Key) const {
344    int Bucket = FindKey(Key);
345    if (Bucket == -1) return end();
346    return const_iterator(TheTable+Bucket, true);
347  }
348
349  /// lookup - Return the entry for the specified key, or a default
350  /// constructed value if no such entry exists.
351  ValueTy lookup(StringRef Key) const {
352    const_iterator it = find(Key);
353    if (it != end())
354      return it->second;
355    return ValueTy();
356  }
357
358  /// Lookup the ValueTy for the \p Key, or create a default constructed value
359  /// if the key is not in the map.
360  ValueTy &operator[](StringRef Key) { return try_emplace(Key).first->second; }
361
362  /// count - Return 1 if the element is in the map, 0 otherwise.
363  size_type count(StringRef Key) const {
364    return find(Key) == end() ? 0 : 1;
365  }
366
367  /// insert - Insert the specified key/value pair into the map.  If the key
368  /// already exists in the map, return false and ignore the request, otherwise
369  /// insert it and return true.
370  bool insert(MapEntryTy *KeyValue) {
371    unsigned BucketNo = LookupBucketFor(KeyValue->getKey());
372    StringMapEntryBase *&Bucket = TheTable[BucketNo];
373    if (Bucket && Bucket != getTombstoneVal())
374      return false;  // Already exists in map.
375
376    if (Bucket == getTombstoneVal())
377      --NumTombstones;
378    Bucket = KeyValue;
379    ++NumItems;
380    assert(NumItems + NumTombstones <= NumBuckets);
381
382    RehashTable();
383    return true;
384  }
385
386  /// insert - Inserts the specified key/value pair into the map if the key
387  /// isn't already in the map. The bool component of the returned pair is true
388  /// if and only if the insertion takes place, and the iterator component of
389  /// the pair points to the element with key equivalent to the key of the pair.
390  std::pair<iterator, bool> insert(std::pair<StringRef, ValueTy> KV) {
391    return try_emplace(KV.first, std::move(KV.second));
392  }
393
394  /// Emplace a new element for the specified key into the map if the key isn't
395  /// already in the map. The bool component of the returned pair is true
396  /// if and only if the insertion takes place, and the iterator component of
397  /// the pair points to the element with key equivalent to the key of the pair.
398  template <typename... ArgsTy>
399  std::pair<iterator, bool> try_emplace(StringRef Key, ArgsTy &&... Args) {
400    unsigned BucketNo = LookupBucketFor(Key);
401    StringMapEntryBase *&Bucket = TheTable[BucketNo];
402    if (Bucket && Bucket != getTombstoneVal())
403      return std::make_pair(iterator(TheTable + BucketNo, false),
404                            false); // Already exists in map.
405
406    if (Bucket == getTombstoneVal())
407      --NumTombstones;
408    Bucket = MapEntryTy::Create(Key, Allocator, std::forward<ArgsTy>(Args)...);
409    ++NumItems;
410    assert(NumItems + NumTombstones <= NumBuckets);
411
412    BucketNo = RehashTable(BucketNo);
413    return std::make_pair(iterator(TheTable + BucketNo, false), true);
414  }
415
416  // clear - Empties out the StringMap
417  void clear() {
418    if (empty()) return;
419
420    // Zap all values, resetting the keys back to non-present (not tombstone),
421    // which is safe because we're removing all elements.
422    for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
423      StringMapEntryBase *&Bucket = TheTable[I];
424      if (Bucket && Bucket != getTombstoneVal()) {
425        static_cast<MapEntryTy*>(Bucket)->Destroy(Allocator);
426      }
427      Bucket = nullptr;
428    }
429
430    NumItems = 0;
431    NumTombstones = 0;
432  }
433
434  /// remove - Remove the specified key/value pair from the map, but do not
435  /// erase it.  This aborts if the key is not in the map.
436  void remove(MapEntryTy *KeyValue) {
437    RemoveKey(KeyValue);
438  }
439
440  void erase(iterator I) {
441    MapEntryTy &V = *I;
442    remove(&V);
443    V.Destroy(Allocator);
444  }
445
446  bool erase(StringRef Key) {
447    iterator I = find(Key);
448    if (I == end()) return false;
449    erase(I);
450    return true;
451  }
452};
453
454template <typename DerivedTy, typename ValueTy>
455class StringMapIterBase
456    : public iterator_facade_base<DerivedTy, std::forward_iterator_tag,
457                                  ValueTy> {
458protected:
459  StringMapEntryBase **Ptr = nullptr;
460
461public:
462  StringMapIterBase() = default;
463
464  explicit StringMapIterBase(StringMapEntryBase **Bucket,
465                             bool NoAdvance = false)
466      : Ptr(Bucket) {
467    if (!NoAdvance) AdvancePastEmptyBuckets();
468  }
469
470  DerivedTy &operator=(const DerivedTy &Other) {
471    Ptr = Other.Ptr;
472    return static_cast<DerivedTy &>(*this);
473  }
474
475  bool operator==(const DerivedTy &RHS) const { return Ptr == RHS.Ptr; }
476
477  DerivedTy &operator++() { // Preincrement
478    ++Ptr;
479    AdvancePastEmptyBuckets();
480    return static_cast<DerivedTy &>(*this);
481  }
482
483  DerivedTy operator++(int) { // Post-increment
484    DerivedTy Tmp(Ptr);
485    ++*this;
486    return Tmp;
487  }
488
489private:
490  void AdvancePastEmptyBuckets() {
491    while (*Ptr == nullptr || *Ptr == StringMapImpl::getTombstoneVal())
492      ++Ptr;
493  }
494};
495
496template <typename ValueTy>
497class StringMapConstIterator
498    : public StringMapIterBase<StringMapConstIterator<ValueTy>,
499                               const StringMapEntry<ValueTy>> {
500  using base = StringMapIterBase<StringMapConstIterator<ValueTy>,
501                                 const StringMapEntry<ValueTy>>;
502
503public:
504  StringMapConstIterator() = default;
505  explicit StringMapConstIterator(StringMapEntryBase **Bucket,
506                                  bool NoAdvance = false)
507      : base(Bucket, NoAdvance) {}
508
509  const StringMapEntry<ValueTy> &operator*() const {
510    return *static_cast<const StringMapEntry<ValueTy> *>(*this->Ptr);
511  }
512};
513
514template <typename ValueTy>
515class StringMapIterator : public StringMapIterBase<StringMapIterator<ValueTy>,
516                                                   StringMapEntry<ValueTy>> {
517  using base =
518      StringMapIterBase<StringMapIterator<ValueTy>, StringMapEntry<ValueTy>>;
519
520public:
521  StringMapIterator() = default;
522  explicit StringMapIterator(StringMapEntryBase **Bucket,
523                             bool NoAdvance = false)
524      : base(Bucket, NoAdvance) {}
525
526  StringMapEntry<ValueTy> &operator*() const {
527    return *static_cast<StringMapEntry<ValueTy> *>(*this->Ptr);
528  }
529
530  operator StringMapConstIterator<ValueTy>() const {
531    return StringMapConstIterator<ValueTy>(this->Ptr, true);
532  }
533};
534
535template <typename ValueTy>
536class StringMapKeyIterator
537    : public iterator_adaptor_base<StringMapKeyIterator<ValueTy>,
538                                   StringMapConstIterator<ValueTy>,
539                                   std::forward_iterator_tag, StringRef> {
540  using base = iterator_adaptor_base<StringMapKeyIterator<ValueTy>,
541                                     StringMapConstIterator<ValueTy>,
542                                     std::forward_iterator_tag, StringRef>;
543
544public:
545  StringMapKeyIterator() = default;
546  explicit StringMapKeyIterator(StringMapConstIterator<ValueTy> Iter)
547      : base(std::move(Iter)) {}
548
549  StringRef &operator*() {
550    Key = this->wrapped()->getKey();
551    return Key;
552  }
553
554private:
555  StringRef Key;
556};
557
558} // end namespace llvm
559
560#endif // LLVM_ADT_STRINGMAP_H
561