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 <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  unsigned StrLen;
40
41public:
42  explicit StringMapEntryBase(unsigned Len) : StrLen(Len) {}
43
44  unsigned 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(unsigned strLen)
130    : StringMapEntryBase(strLen), second() {}
131  template <typename... InitTy>
132  StringMapEntry(unsigned 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    unsigned KeyLength = Key.size();
158
159    // Allocate a new item with space for the string at the end and a null
160    // terminator.
161    unsigned AllocSize = static_cast<unsigned>(sizeof(StringMapEntry))+
162      KeyLength+1;
163    unsigned Alignment = alignof(StringMapEntry);
164
165    StringMapEntry *NewItem =
166      static_cast<StringMapEntry*>(Allocator.Allocate(AllocSize,Alignment));
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    unsigned AllocSize =
203        static_cast<unsigned>(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