LLVM  12.0.0git
StringMap.h
Go to the documentation of this file.
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 
19 #include <initializer_list>
20 #include <iterator>
21 
22 namespace llvm {
23 
24 template <typename ValueTy> class StringMapConstIterator;
25 template <typename ValueTy> class StringMapIterator;
26 template <typename ValueTy> class StringMapKeyIterator;
27 
28 /// StringMapImpl - This is the base class of StringMap that is shared among
29 /// all of its instantiations.
31 protected:
32  // Array of NumBuckets pointers to entries, null pointers are holes.
33  // TheTable[NumBuckets] contains a sentinel value for easy iteration. Followed
34  // by an array of the actual hash values as unsigned integers.
36  unsigned NumBuckets = 0;
37  unsigned NumItems = 0;
38  unsigned NumTombstones = 0;
39  unsigned ItemSize;
40 
41 protected:
42  explicit StringMapImpl(unsigned itemSize) : ItemSize(itemSize) {}
46  ItemSize(RHS.ItemSize) {
47  RHS.TheTable = nullptr;
48  RHS.NumBuckets = 0;
49  RHS.NumItems = 0;
50  RHS.NumTombstones = 0;
51  }
52 
53  StringMapImpl(unsigned InitSize, unsigned ItemSize);
54  unsigned RehashTable(unsigned BucketNo = 0);
55 
56  /// LookupBucketFor - Look up the bucket that the specified string should end
57  /// up in. If it already exists as a key in the map, the Item pointer for the
58  /// specified bucket will be non-null. Otherwise, it will be null. In either
59  /// case, the FullHashValue field of the bucket will be set to the hash value
60  /// of the string.
61  unsigned LookupBucketFor(StringRef Key);
62 
63  /// FindKey - Look up the bucket that contains the specified key. If it exists
64  /// in the map, return the bucket number of the key. Otherwise return -1.
65  /// This does not modify the map.
66  int FindKey(StringRef Key) const;
67 
68  /// RemoveKey - Remove the specified StringMapEntry from the table, but do not
69  /// delete it. This aborts if the value isn't in the table.
71 
72  /// RemoveKey - Remove the StringMapEntry for the specified key from the
73  /// table, returning it. If the key is not in the table, this returns null.
75 
76  /// Allocate the table with the specified number of buckets and otherwise
77  /// setup the map as empty.
78  void init(unsigned Size);
79 
80 public:
81  static constexpr uintptr_t TombstoneIntVal =
82  static_cast<uintptr_t>(-1)
84 
86  return reinterpret_cast<StringMapEntryBase *>(TombstoneIntVal);
87  }
88 
89  unsigned getNumBuckets() const { return NumBuckets; }
90  unsigned getNumItems() const { return NumItems; }
91 
92  bool empty() const { return NumItems == 0; }
93  unsigned size() const { return NumItems; }
94 
96  std::swap(TheTable, Other.TheTable);
97  std::swap(NumBuckets, Other.NumBuckets);
98  std::swap(NumItems, Other.NumItems);
99  std::swap(NumTombstones, Other.NumTombstones);
100  }
101 };
102 
103 /// StringMap - This is an unconventional map that is specialized for handling
104 /// keys that are "strings", which are basically ranges of bytes. This does some
105 /// funky memory allocation and hashing things to make it extremely efficient,
106 /// storing the string data *after* the value in the map.
107 template <typename ValueTy, typename AllocatorTy = MallocAllocator>
108 class StringMap : public StringMapImpl {
109  AllocatorTy Allocator;
110 
111 public:
113 
114  StringMap() : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {}
115 
116  explicit StringMap(unsigned InitialSize)
117  : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))) {}
118 
119  explicit StringMap(AllocatorTy A)
120  : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))), Allocator(A) {
121  }
122 
123  StringMap(unsigned InitialSize, AllocatorTy A)
124  : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))),
125  Allocator(A) {}
126 
127  StringMap(std::initializer_list<std::pair<StringRef, ValueTy>> List)
128  : StringMapImpl(List.size(), static_cast<unsigned>(sizeof(MapEntryTy))) {
129  for (const auto &P : List) {
130  insert(P);
131  }
132  }
133 
135  : StringMapImpl(std::move(RHS)), Allocator(std::move(RHS.Allocator)) {}
136 
137  StringMap(const StringMap &RHS)
138  : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))),
139  Allocator(RHS.Allocator) {
140  if (RHS.empty())
141  return;
142 
143  // Allocate TheTable of the same size as RHS's TheTable, and set the
144  // sentinel appropriately (and NumBuckets).
145  init(RHS.NumBuckets);
146  unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1),
147  *RHSHashTable = (unsigned *)(RHS.TheTable + NumBuckets + 1);
148 
149  NumItems = RHS.NumItems;
151  for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
152  StringMapEntryBase *Bucket = RHS.TheTable[I];
153  if (!Bucket || Bucket == getTombstoneVal()) {
154  TheTable[I] = Bucket;
155  continue;
156  }
157 
159  static_cast<MapEntryTy *>(Bucket)->getKey(), Allocator,
160  static_cast<MapEntryTy *>(Bucket)->getValue());
161  HashTable[I] = RHSHashTable[I];
162  }
163 
164  // Note that here we've copied everything from the RHS into this object,
165  // tombstones included. We could, instead, have re-probed for each key to
166  // instantiate this new object without any tombstone buckets. The
167  // assumption here is that items are rarely deleted from most StringMaps,
168  // and so tombstones are rare, so the cost of re-probing for all inputs is
169  // not worthwhile.
170  }
171 
173  StringMapImpl::swap(RHS);
174  std::swap(Allocator, RHS.Allocator);
175  return *this;
176  }
177 
179  // Delete all the elements in the map, but don't reset the elements
180  // to default values. This is a copy of clear(), but avoids unnecessary
181  // work not required in the destructor.
182  if (!empty()) {
183  for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
184  StringMapEntryBase *Bucket = TheTable[I];
185  if (Bucket && Bucket != getTombstoneVal()) {
186  static_cast<MapEntryTy *>(Bucket)->Destroy(Allocator);
187  }
188  }
189  }
190  free(TheTable);
191  }
192 
193  AllocatorTy &getAllocator() { return Allocator; }
194  const AllocatorTy &getAllocator() const { return Allocator; }
195 
196  using key_type = const char *;
197  using mapped_type = ValueTy;
199  using size_type = size_t;
200 
203 
205  iterator end() { return iterator(TheTable + NumBuckets, true); }
207  return const_iterator(TheTable, NumBuckets == 0);
208  }
209  const_iterator end() const {
210  return const_iterator(TheTable + NumBuckets, true);
211  }
212 
216  }
217 
219  int Bucket = FindKey(Key);
220  if (Bucket == -1)
221  return end();
222  return iterator(TheTable + Bucket, true);
223  }
224 
226  int Bucket = FindKey(Key);
227  if (Bucket == -1)
228  return end();
229  return const_iterator(TheTable + Bucket, true);
230  }
231 
232  /// lookup - Return the entry for the specified key, or a default
233  /// constructed value if no such entry exists.
234  ValueTy lookup(StringRef Key) const {
235  const_iterator it = find(Key);
236  if (it != end())
237  return it->second;
238  return ValueTy();
239  }
240 
241  /// Lookup the ValueTy for the \p Key, or create a default constructed value
242  /// if the key is not in the map.
243  ValueTy &operator[](StringRef Key) { return try_emplace(Key).first->second; }
244 
245  /// count - Return 1 if the element is in the map, 0 otherwise.
246  size_type count(StringRef Key) const { return find(Key) == end() ? 0 : 1; }
247 
248  template <typename InputTy>
249  size_type count(const StringMapEntry<InputTy> &MapEntry) const {
250  return count(MapEntry.getKey());
251  }
252 
253  /// equal - check whether both of the containers are equal.
254  bool operator==(const StringMap &RHS) const {
255  if (size() != RHS.size())
256  return false;
257 
258  for (const auto &KeyValue : *this) {
259  auto FindInRHS = RHS.find(KeyValue.getKey());
260 
261  if (FindInRHS == RHS.end())
262  return false;
263 
264  if (!(KeyValue.getValue() == FindInRHS->getValue()))
265  return false;
266  }
267 
268  return true;
269  }
270 
271  bool operator!=(const StringMap &RHS) const { return !(*this == RHS); }
272 
273  /// insert - Insert the specified key/value pair into the map. If the key
274  /// already exists in the map, return false and ignore the request, otherwise
275  /// insert it and return true.
276  bool insert(MapEntryTy *KeyValue) {
277  unsigned BucketNo = LookupBucketFor(KeyValue->getKey());
278  StringMapEntryBase *&Bucket = TheTable[BucketNo];
279  if (Bucket && Bucket != getTombstoneVal())
280  return false; // Already exists in map.
281 
282  if (Bucket == getTombstoneVal())
283  --NumTombstones;
284  Bucket = KeyValue;
285  ++NumItems;
287 
288  RehashTable();
289  return true;
290  }
291 
292  /// insert - Inserts the specified key/value pair into the map if the key
293  /// isn't already in the map. The bool component of the returned pair is true
294  /// if and only if the insertion takes place, and the iterator component of
295  /// the pair points to the element with key equivalent to the key of the pair.
296  std::pair<iterator, bool> insert(std::pair<StringRef, ValueTy> KV) {
297  return try_emplace(KV.first, std::move(KV.second));
298  }
299 
300  /// Inserts an element or assigns to the current element if the key already
301  /// exists. The return type is the same as try_emplace.
302  template <typename V>
303  std::pair<iterator, bool> insert_or_assign(StringRef Key, V &&Val) {
304  auto Ret = try_emplace(Key, std::forward<V>(Val));
305  if (!Ret.second)
306  Ret.first->second = std::forward<V>(Val);
307  return Ret;
308  }
309 
310  /// Emplace a new element for the specified key into the map if the key isn't
311  /// already in the map. The bool component of the returned pair is true
312  /// if and only if the insertion takes place, and the iterator component of
313  /// the pair points to the element with key equivalent to the key of the pair.
314  template <typename... ArgsTy>
315  std::pair<iterator, bool> try_emplace(StringRef Key, ArgsTy &&... Args) {
316  unsigned BucketNo = LookupBucketFor(Key);
317  StringMapEntryBase *&Bucket = TheTable[BucketNo];
318  if (Bucket && Bucket != getTombstoneVal())
319  return std::make_pair(iterator(TheTable + BucketNo, false),
320  false); // Already exists in map.
321 
322  if (Bucket == getTombstoneVal())
323  --NumTombstones;
324  Bucket = MapEntryTy::Create(Key, Allocator, std::forward<ArgsTy>(Args)...);
325  ++NumItems;
327 
328  BucketNo = RehashTable(BucketNo);
329  return std::make_pair(iterator(TheTable + BucketNo, false), true);
330  }
331 
332  // clear - Empties out the StringMap
333  void clear() {
334  if (empty())
335  return;
336 
337  // Zap all values, resetting the keys back to non-present (not tombstone),
338  // which is safe because we're removing all elements.
339  for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
340  StringMapEntryBase *&Bucket = TheTable[I];
341  if (Bucket && Bucket != getTombstoneVal()) {
342  static_cast<MapEntryTy *>(Bucket)->Destroy(Allocator);
343  }
344  Bucket = nullptr;
345  }
346 
347  NumItems = 0;
348  NumTombstones = 0;
349  }
350 
351  /// remove - Remove the specified key/value pair from the map, but do not
352  /// erase it. This aborts if the key is not in the map.
353  void remove(MapEntryTy *KeyValue) { RemoveKey(KeyValue); }
354 
355  void erase(iterator I) {
356  MapEntryTy &V = *I;
357  remove(&V);
358  V.Destroy(Allocator);
359  }
360 
362  iterator I = find(Key);
363  if (I == end())
364  return false;
365  erase(I);
366  return true;
367  }
368 };
369 
370 template <typename DerivedTy, typename ValueTy>
372  : public iterator_facade_base<DerivedTy, std::forward_iterator_tag,
373  ValueTy> {
374 protected:
375  StringMapEntryBase **Ptr = nullptr;
376 
377 public:
378  StringMapIterBase() = default;
379 
381  bool NoAdvance = false)
382  : Ptr(Bucket) {
383  if (!NoAdvance)
384  AdvancePastEmptyBuckets();
385  }
386 
387  DerivedTy &operator=(const DerivedTy &Other) {
388  Ptr = Other.Ptr;
389  return static_cast<DerivedTy &>(*this);
390  }
391 
392  friend bool operator==(const DerivedTy &LHS, const DerivedTy &RHS) {
393  return LHS.Ptr == RHS.Ptr;
394  }
395 
396  DerivedTy &operator++() { // Preincrement
397  ++Ptr;
398  AdvancePastEmptyBuckets();
399  return static_cast<DerivedTy &>(*this);
400  }
401 
402  DerivedTy operator++(int) { // Post-increment
403  DerivedTy Tmp(Ptr);
404  ++*this;
405  return Tmp;
406  }
407 
408 private:
409  void AdvancePastEmptyBuckets() {
410  while (*Ptr == nullptr || *Ptr == StringMapImpl::getTombstoneVal())
411  ++Ptr;
412  }
413 };
414 
415 template <typename ValueTy>
416 class StringMapConstIterator
417  : public StringMapIterBase<StringMapConstIterator<ValueTy>,
418  const StringMapEntry<ValueTy>> {
419  using base = StringMapIterBase<StringMapConstIterator<ValueTy>,
420  const StringMapEntry<ValueTy>>;
421 
422 public:
423  StringMapConstIterator() = default;
425  bool NoAdvance = false)
426  : base(Bucket, NoAdvance) {}
427 
429  return *static_cast<const StringMapEntry<ValueTy> *>(*this->Ptr);
430  }
431 };
432 
433 template <typename ValueTy>
434 class StringMapIterator : public StringMapIterBase<StringMapIterator<ValueTy>,
435  StringMapEntry<ValueTy>> {
436  using base =
437  StringMapIterBase<StringMapIterator<ValueTy>, StringMapEntry<ValueTy>>;
438 
439 public:
440  StringMapIterator() = default;
442  bool NoAdvance = false)
443  : base(Bucket, NoAdvance) {}
444 
446  return *static_cast<StringMapEntry<ValueTy> *>(*this->Ptr);
447  }
448 
450  return StringMapConstIterator<ValueTy>(this->Ptr, true);
451  }
452 };
453 
454 template <typename ValueTy>
455 class StringMapKeyIterator
456  : public iterator_adaptor_base<StringMapKeyIterator<ValueTy>,
457  StringMapConstIterator<ValueTy>,
458  std::forward_iterator_tag, StringRef> {
459  using base = iterator_adaptor_base<StringMapKeyIterator<ValueTy>,
461  std::forward_iterator_tag, StringRef>;
462 
463 public:
464  StringMapKeyIterator() = default;
466  : base(std::move(Iter)) {}
467 
469  Key = this->wrapped()->getKey();
470  return Key;
471  }
472 
473 private:
474  StringRef Key;
475 };
476 
477 } // end namespace llvm
478 
479 #endif // LLVM_ADT_STRINGMAP_H
std::pair< iterator, bool > insert_or_assign(StringRef Key, V &&Val)
Inserts an element or assigns to the current element if the key already exists.
Definition: StringMap.h:303
iterator_range< StringMapKeyIterator< ValueTy > > keys() const
Definition: StringMap.h:213
StringMapImpl(unsigned itemSize)
Definition: StringMap.h:42
This class represents lattice values for constants.
Definition: AllocatorList.h:23
StringMapEntry - This is used to represent one value that is inserted into a StringMap.
void remove(MapEntryTy *KeyValue)
remove - Remove the specified key/value pair from the map, but do not erase it.
Definition: StringMap.h:353
static StringMapEntry * Create(StringRef key, AllocatorTy &allocator, InitTy &&... initVals)
Create a StringMapEntry for the specified key construct the value using InitiVals.
unsigned RehashTable(unsigned BucketNo=0)
RehashTable - Grow the table, redistributing values into the buckets with the appropriate mod-of-hash...
Definition: StringMap.cpp:200
This file defines MallocAllocator.
iterator find(StringRef Key)
Definition: StringMap.h:218
unsigned LookupBucketFor(StringRef Key)
LookupBucketFor - Look up the bucket that the specified string should end up in.
Definition: StringMap.cpp:74
const_iterator end() const
Definition: StringMap.h:209
StringMap(const StringMap &RHS)
Definition: StringMap.h:137
const_iterator find(StringRef Key) const
Definition: StringMap.h:225
StringMapKeyIterator(StringMapConstIterator< ValueTy > Iter)
Definition: StringMap.h:465
Definition: BitVector.h:941
unsigned size() const
Definition: StringMap.h:93
StringMap & operator=(StringMap RHS)
Definition: StringMap.h:172
StringMapIterator(StringMapEntryBase **Bucket, bool NoAdvance=false)
Definition: StringMap.h:441
StringMap(AllocatorTy A)
Definition: StringMap.h:119
StringMapImpl - This is the base class of StringMap that is shared among all of its instantiations.
Definition: StringMap.h:30
const StringMapEntry< ValueTy > & operator *() const
Definition: StringMap.h:428
friend bool operator==(const DerivedTy &LHS, const DerivedTy &RHS)
Definition: StringMap.h:392
Key
PAL metadata keys.
A traits type that is used to handle pointer types and things that are just wrappers for pointers as ...
StringMapIterBase(StringMapEntryBase **Bucket, bool NoAdvance=false)
Definition: StringMap.h:380
void swap(StringMapImpl &Other)
Definition: StringMap.h:95
int FindKey(StringRef Key) const
FindKey - Look up the bucket that contains the specified key.
Definition: StringMap.cpp:132
std::pair< iterator, bool > try_emplace(StringRef Key, ArgsTy &&... Args)
Emplace a new element for the specified key into the map if the key isn't already in the map.
Definition: StringMap.h:315
CRTP base class which implements the entire standard iterator facade in terms of a minimal subset of ...
Definition: iterator.h:67
StringMap(StringMap &&RHS)
Definition: StringMap.h:134
size_type count(const StringMapEntry< InputTy > &MapEntry) const
Definition: StringMap.h:249
#define P(N)
unsigned NumItems
Definition: StringMap.h:37
StringMapEntryBase ** TheTable
Definition: StringMap.h:35
size_type count(StringRef Key) const
count - Return 1 if the element is in the map, 0 otherwise.
Definition: StringMap.h:246
StringRef & operator *()
Definition: StringMap.h:468
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
const_iterator begin() const
Definition: StringMap.h:206
static constexpr uintptr_t TombstoneIntVal
Definition: StringMap.h:81
StringRef getKey() const
void erase(iterator I)
Definition: StringMap.h:355
StringMap(unsigned InitialSize)
Definition: StringMap.h:116
ValueTy lookup(StringRef Key) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: StringMap.h:234
void init(unsigned Size)
Allocate the table with the specified number of buckets and otherwise setup the map as empty.
Definition: StringMap.cpp:50
DerivedTy & operator++()
Definition: StringMap.h:396
void Destroy(AllocatorTy &allocator)
Destroy - Destroy this StringMapEntry, releasing memory back to the specified allocator.
StringMapIterator< ValueTy > iterator
Definition: StringMap.h:202
bool operator==(const StringMap &RHS) const
equal - check whether both of the containers are equal.
Definition: StringMap.h:254
bool erase(StringRef Key)
Definition: StringMap.h:361
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Basic Register Allocator
unsigned ItemSize
Definition: StringMap.h:39
AllocatorTy & getAllocator()
Definition: StringMap.h:193
void RemoveKey(StringMapEntryBase *V)
RemoveKey - Remove the specified StringMapEntry from the table, but do not delete it.
Definition: StringMap.cpp:175
std::pair< iterator, bool > insert(std::pair< StringRef, ValueTy > KV)
insert - Inserts the specified key/value pair into the map if the key isn't already in the map.
Definition: StringMap.h:296
const AllocatorTy & getAllocator() const
Definition: StringMap.h:194
static StringMapEntryBase * getTombstoneVal()
Definition: StringMap.h:85
bool insert(MapEntryTy *KeyValue)
insert - Insert the specified key/value pair into the map.
Definition: StringMap.h:276
unsigned NumBuckets
Definition: StringMap.h:36
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:944
A range adaptor for a pair of iterators.
StringMap - This is an unconventional map that is specialized for handling keys that are "strings",...
Definition: StringMap.h:108
StringMap(unsigned InitialSize, AllocatorTy A)
Definition: StringMap.h:123
unsigned getNumBuckets() const
Definition: StringMap.h:89
StringMapConstIterator(StringMapEntryBase **Bucket, bool NoAdvance=false)
Definition: StringMap.h:424
DerivedTy & operator=(const DerivedTy &Other)
Definition: StringMap.h:387
iterator begin()
Definition: StringMap.h:204
#define I(x, y, z)
Definition: MD5.cpp:59
bool operator!=(const StringMap &RHS) const
Definition: StringMap.h:271
DerivedTy operator++(int)
Definition: StringMap.h:402
StringMap(std::initializer_list< std::pair< StringRef, ValueTy >> List)
Definition: StringMap.h:127
bool empty() const
Definition: StringMap.h:92
unsigned NumTombstones
Definition: StringMap.h:38
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
StringMapEntry< ValueTy > & operator *() const
Definition: StringMap.h:445
StringMapImpl(StringMapImpl &&RHS)
Definition: StringMap.h:43
unsigned getNumItems() const
Definition: StringMap.h:90
StringMapEntryBase - Shared base class of StringMapEntry instances.
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1556
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:57
ValueTy & operator[](StringRef Key)
Lookup the ValueTy for the Key, or create a default constructed value if the key is not in the map.
Definition: StringMap.h:243
StringMapConstIterator< ValueTy > const_iterator
Definition: StringMap.h:201
StringMapEntryBase ** Ptr
Definition: StringMap.h:375
iterator end()
Definition: StringMap.h:205
constexpr char Args[]
Key for Kernel::Metadata::mArgs.