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