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) {}
44  : TheTable(RHS.TheTable), NumBuckets(RHS.NumBuckets),
45  NumItems(RHS.NumItems), NumTombstones(RHS.NumTombstones),
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:
82  uintptr_t Val = static_cast<uintptr_t>(-1);
83  Val <<= PointerLikeTypeTraits<StringMapEntryBase *>::NumLowBitsAvailable;
84  return reinterpret_cast<StringMapEntryBase *>(Val);
85  }
86 
87  unsigned getNumBuckets() const { return NumBuckets; }
88  unsigned getNumItems() const { return NumItems; }
89 
90  bool empty() const { return NumItems == 0; }
91  unsigned size() const { return NumItems; }
92 
94  std::swap(TheTable, Other.TheTable);
95  std::swap(NumBuckets, Other.NumBuckets);
96  std::swap(NumItems, Other.NumItems);
97  std::swap(NumTombstones, Other.NumTombstones);
98  }
99 };
100 
101 /// StringMap - This is an unconventional map that is specialized for handling
102 /// keys that are "strings", which are basically ranges of bytes. This does some
103 /// funky memory allocation and hashing things to make it extremely efficient,
104 /// storing the string data *after* the value in the map.
105 template <typename ValueTy, typename AllocatorTy = MallocAllocator>
106 class StringMap : public StringMapImpl {
107  AllocatorTy Allocator;
108 
109 public:
111 
112  StringMap() : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {}
113 
114  explicit StringMap(unsigned InitialSize)
115  : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))) {}
116 
117  explicit StringMap(AllocatorTy A)
118  : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))), Allocator(A) {
119  }
120 
121  StringMap(unsigned InitialSize, AllocatorTy A)
122  : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))),
123  Allocator(A) {}
124 
125  StringMap(std::initializer_list<std::pair<StringRef, ValueTy>> List)
126  : StringMapImpl(List.size(), static_cast<unsigned>(sizeof(MapEntryTy))) {
127  for (const auto &P : List) {
128  insert(P);
129  }
130  }
131 
133  : StringMapImpl(std::move(RHS)), Allocator(std::move(RHS.Allocator)) {}
134 
135  StringMap(const StringMap &RHS)
136  : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))),
137  Allocator(RHS.Allocator) {
138  if (RHS.empty())
139  return;
140 
141  // Allocate TheTable of the same size as RHS's TheTable, and set the
142  // sentinel appropriately (and NumBuckets).
143  init(RHS.NumBuckets);
144  unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1),
145  *RHSHashTable = (unsigned *)(RHS.TheTable + NumBuckets + 1);
146 
147  NumItems = RHS.NumItems;
149  for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
150  StringMapEntryBase *Bucket = RHS.TheTable[I];
151  if (!Bucket || Bucket == getTombstoneVal()) {
152  TheTable[I] = Bucket;
153  continue;
154  }
155 
156  TheTable[I] = MapEntryTy::Create(
157  static_cast<MapEntryTy *>(Bucket)->getKey(), Allocator,
158  static_cast<MapEntryTy *>(Bucket)->getValue());
159  HashTable[I] = RHSHashTable[I];
160  }
161 
162  // Note that here we've copied everything from the RHS into this object,
163  // tombstones included. We could, instead, have re-probed for each key to
164  // instantiate this new object without any tombstone buckets. The
165  // assumption here is that items are rarely deleted from most StringMaps,
166  // and so tombstones are rare, so the cost of re-probing for all inputs is
167  // not worthwhile.
168  }
169 
171  StringMapImpl::swap(RHS);
172  std::swap(Allocator, RHS.Allocator);
173  return *this;
174  }
175 
177  // Delete all the elements in the map, but don't reset the elements
178  // to default values. This is a copy of clear(), but avoids unnecessary
179  // work not required in the destructor.
180  if (!empty()) {
181  for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
182  StringMapEntryBase *Bucket = TheTable[I];
183  if (Bucket && Bucket != getTombstoneVal()) {
184  static_cast<MapEntryTy *>(Bucket)->Destroy(Allocator);
185  }
186  }
187  }
188  free(TheTable);
189  }
190 
191  AllocatorTy &getAllocator() { return Allocator; }
192  const AllocatorTy &getAllocator() const { return Allocator; }
193 
194  using key_type = const char *;
195  using mapped_type = ValueTy;
197  using size_type = size_t;
198 
201 
203  iterator end() { return iterator(TheTable + NumBuckets, true); }
205  return const_iterator(TheTable, NumBuckets == 0);
206  }
207  const_iterator end() const {
208  return const_iterator(TheTable + NumBuckets, true);
209  }
210 
214  }
215 
217  int Bucket = FindKey(Key);
218  if (Bucket == -1)
219  return end();
220  return iterator(TheTable + Bucket, true);
221  }
222 
224  int Bucket = FindKey(Key);
225  if (Bucket == -1)
226  return end();
227  return const_iterator(TheTable + Bucket, true);
228  }
229 
230  /// lookup - Return the entry for the specified key, or a default
231  /// constructed value if no such entry exists.
232  ValueTy lookup(StringRef Key) const {
233  const_iterator it = find(Key);
234  if (it != end())
235  return it->second;
236  return ValueTy();
237  }
238 
239  /// Lookup the ValueTy for the \p Key, or create a default constructed value
240  /// if the key is not in the map.
241  ValueTy &operator[](StringRef Key) { return try_emplace(Key).first->second; }
242 
243  /// count - Return 1 if the element is in the map, 0 otherwise.
244  size_type count(StringRef Key) const { return find(Key) == end() ? 0 : 1; }
245 
246  template <typename InputTy>
247  size_type count(const StringMapEntry<InputTy> &MapEntry) const {
248  return count(MapEntry.getKey());
249  }
250 
251  /// equal - check whether both of the containers are equal.
252  bool operator==(const StringMap &RHS) const {
253  if (size() != RHS.size())
254  return false;
255 
256  for (const auto &KeyValue : *this) {
257  auto FindInRHS = RHS.find(KeyValue.getKey());
258 
259  if (FindInRHS == RHS.end())
260  return false;
261 
262  if (!(KeyValue.getValue() == FindInRHS->getValue()))
263  return false;
264  }
265 
266  return true;
267  }
268 
269  bool operator!=(const StringMap &RHS) const { return !(*this == RHS); }
270 
271  /// insert - Insert the specified key/value pair into the map. If the key
272  /// already exists in the map, return false and ignore the request, otherwise
273  /// insert it and return true.
274  bool insert(MapEntryTy *KeyValue) {
275  unsigned BucketNo = LookupBucketFor(KeyValue->getKey());
276  StringMapEntryBase *&Bucket = TheTable[BucketNo];
277  if (Bucket && Bucket != getTombstoneVal())
278  return false; // Already exists in map.
279 
280  if (Bucket == getTombstoneVal())
281  --NumTombstones;
282  Bucket = KeyValue;
283  ++NumItems;
285 
286  RehashTable();
287  return true;
288  }
289 
290  /// insert - Inserts the specified key/value pair into the map if the key
291  /// isn't already in the map. The bool component of the returned pair is true
292  /// if and only if the insertion takes place, and the iterator component of
293  /// the pair points to the element with key equivalent to the key of the pair.
294  std::pair<iterator, bool> insert(std::pair<StringRef, ValueTy> KV) {
295  return try_emplace(KV.first, std::move(KV.second));
296  }
297 
298  /// Inserts an element or assigns to the current element if the key already
299  /// exists. The return type is the same as try_emplace.
300  template <typename V>
301  std::pair<iterator, bool> insert_or_assign(StringRef Key, V &&Val) {
302  auto Ret = try_emplace(Key, std::forward<V>(Val));
303  if (!Ret.second)
304  Ret.first->second = std::forward<V>(Val);
305  return Ret;
306  }
307 
308  /// Emplace a new element for the specified key into the map if the key isn't
309  /// already in the map. The bool component of the returned pair is true
310  /// if and only if the insertion takes place, and the iterator component of
311  /// the pair points to the element with key equivalent to the key of the pair.
312  template <typename... ArgsTy>
313  std::pair<iterator, bool> try_emplace(StringRef Key, ArgsTy &&... Args) {
314  unsigned BucketNo = LookupBucketFor(Key);
315  StringMapEntryBase *&Bucket = TheTable[BucketNo];
316  if (Bucket && Bucket != getTombstoneVal())
317  return std::make_pair(iterator(TheTable + BucketNo, false),
318  false); // Already exists in map.
319 
320  if (Bucket == getTombstoneVal())
321  --NumTombstones;
322  Bucket = MapEntryTy::Create(Key, Allocator, std::forward<ArgsTy>(Args)...);
323  ++NumItems;
325 
326  BucketNo = RehashTable(BucketNo);
327  return std::make_pair(iterator(TheTable + BucketNo, false), true);
328  }
329 
330  // clear - Empties out the StringMap
331  void clear() {
332  if (empty())
333  return;
334 
335  // Zap all values, resetting the keys back to non-present (not tombstone),
336  // which is safe because we're removing all elements.
337  for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
338  StringMapEntryBase *&Bucket = TheTable[I];
339  if (Bucket && Bucket != getTombstoneVal()) {
340  static_cast<MapEntryTy *>(Bucket)->Destroy(Allocator);
341  }
342  Bucket = nullptr;
343  }
344 
345  NumItems = 0;
346  NumTombstones = 0;
347  }
348 
349  /// remove - Remove the specified key/value pair from the map, but do not
350  /// erase it. This aborts if the key is not in the map.
351  void remove(MapEntryTy *KeyValue) { RemoveKey(KeyValue); }
352 
353  void erase(iterator I) {
354  MapEntryTy &V = *I;
355  remove(&V);
356  V.Destroy(Allocator);
357  }
358 
360  iterator I = find(Key);
361  if (I == end())
362  return false;
363  erase(I);
364  return true;
365  }
366 };
367 
368 template <typename DerivedTy, typename ValueTy>
370  : public iterator_facade_base<DerivedTy, std::forward_iterator_tag,
371  ValueTy> {
372 protected:
373  StringMapEntryBase **Ptr = nullptr;
374 
375 public:
376  StringMapIterBase() = default;
377 
379  bool NoAdvance = false)
380  : Ptr(Bucket) {
381  if (!NoAdvance)
382  AdvancePastEmptyBuckets();
383  }
384 
385  DerivedTy &operator=(const DerivedTy &Other) {
386  Ptr = Other.Ptr;
387  return static_cast<DerivedTy &>(*this);
388  }
389 
390  bool operator==(const DerivedTy &RHS) const { return Ptr == RHS.Ptr; }
391 
392  DerivedTy &operator++() { // Preincrement
393  ++Ptr;
394  AdvancePastEmptyBuckets();
395  return static_cast<DerivedTy &>(*this);
396  }
397 
398  DerivedTy operator++(int) { // Post-increment
399  DerivedTy Tmp(Ptr);
400  ++*this;
401  return Tmp;
402  }
403 
404 private:
405  void AdvancePastEmptyBuckets() {
406  while (*Ptr == nullptr || *Ptr == StringMapImpl::getTombstoneVal())
407  ++Ptr;
408  }
409 };
410 
411 template <typename ValueTy>
413  : public StringMapIterBase<StringMapConstIterator<ValueTy>,
414  const StringMapEntry<ValueTy>> {
417 
418 public:
419  StringMapConstIterator() = default;
421  bool NoAdvance = false)
422  : base(Bucket, NoAdvance) {}
423 
424  const StringMapEntry<ValueTy> &operator*() const {
425  return *static_cast<const StringMapEntry<ValueTy> *>(*this->Ptr);
426  }
427 };
428 
429 template <typename ValueTy>
430 class StringMapIterator : public StringMapIterBase<StringMapIterator<ValueTy>,
431  StringMapEntry<ValueTy>> {
432  using base =
434 
435 public:
436  StringMapIterator() = default;
438  bool NoAdvance = false)
439  : base(Bucket, NoAdvance) {}
440 
441  StringMapEntry<ValueTy> &operator*() const {
442  return *static_cast<StringMapEntry<ValueTy> *>(*this->Ptr);
443  }
444 
446  return StringMapConstIterator<ValueTy>(this->Ptr, true);
447  }
448 };
449 
450 template <typename ValueTy>
452  : public iterator_adaptor_base<StringMapKeyIterator<ValueTy>,
453  StringMapConstIterator<ValueTy>,
454  std::forward_iterator_tag, StringRef> {
457  std::forward_iterator_tag, StringRef>;
458 
459 public:
460  StringMapKeyIterator() = default;
461  explicit StringMapKeyIterator(StringMapConstIterator<ValueTy> Iter)
462  : base(std::move(Iter)) {}
463 
464  StringRef &operator*() {
465  Key = this->wrapped()->getKey();
466  return Key;
467  }
468 
469 private:
470  StringRef Key;
471 };
472 
473 } // end namespace llvm
474 
475 #endif // LLVM_ADT_STRINGMAP_H
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:233
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:301
iterator_range< StringMapKeyIterator< ValueTy > > keys() const
Definition: StringMap.h:211
StringMapImpl(unsigned itemSize)
Definition: StringMap.h:42
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:224
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.
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:216
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:207
StringRef & operator*()
Definition: StringMap.h:464
StringMap(const StringMap &RHS)
Definition: StringMap.h:135
const_iterator find(StringRef Key) const
Definition: StringMap.h:223
StringMapKeyIterator(StringMapConstIterator< ValueTy > Iter)
Definition: StringMap.h:461
Definition: BitVector.h:959
unsigned size() const
Definition: StringMap.h:91
StringMap & operator=(StringMap RHS)
Definition: StringMap.h:170
StringMapIterator(StringMapEntryBase **Bucket, bool NoAdvance=false)
Definition: StringMap.h:437
StringMap(AllocatorTy A)
Definition: StringMap.h:117
StringMapImpl - This is the base class of StringMap that is shared among all of its instantiations...
Definition: StringMap.h:30
Key
PAL metadata keys.
StringMapEntry< ValueTy > & operator*() const
Definition: StringMap.h:441
StringMapIterBase(StringMapEntryBase **Bucket, bool NoAdvance=false)
Definition: StringMap.h:378
void swap(StringMapImpl &Other)
Definition: StringMap.h:93
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&#39;t already in the map...
Definition: StringMap.h:313
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:132
size_type count(const StringMapEntry< InputTy > &MapEntry) const
Definition: StringMap.h:247
#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:244
CRTP base class for adapting an iterator to a different type.
Definition: iterator.h:205
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
const_iterator begin() const
Definition: StringMap.h:204
StringRef getKey() const
void erase(iterator I)
Definition: StringMap.h:353
StringMap(unsigned InitialSize)
Definition: StringMap.h:114
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:232
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:392
void Destroy(AllocatorTy &allocator)
Destroy - Destroy this StringMapEntry, releasing memory back to the specified allocator.
bool operator==(const StringMap &RHS) const
equal - check whether both of the containers are equal.
Definition: StringMap.h:252
bool erase(StringRef Key)
Definition: StringMap.h:359
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Basic Register Allocator
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1511
unsigned ItemSize
Definition: StringMap.h:39
AllocatorTy & getAllocator()
Definition: StringMap.h:191
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&#39;t already in the map...
Definition: StringMap.h:294
const AllocatorTy & getAllocator() const
Definition: StringMap.h:192
static StringMapEntryBase * getTombstoneVal()
Definition: StringMap.h:81
bool insert(MapEntryTy *KeyValue)
insert - Insert the specified key/value pair into the map.
Definition: StringMap.h:274
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:962
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:106
StringMap(unsigned InitialSize, AllocatorTy A)
Definition: StringMap.h:121
bool operator==(const DerivedTy &RHS) const
Definition: StringMap.h:390
unsigned getNumBuckets() const
Definition: StringMap.h:87
StringMapConstIterator(StringMapEntryBase **Bucket, bool NoAdvance=false)
Definition: StringMap.h:420
DerivedTy & operator=(const DerivedTy &Other)
Definition: StringMap.h:385
iterator begin()
Definition: StringMap.h:202
#define I(x, y, z)
Definition: MD5.cpp:59
uint32_t Size
Definition: Profile.cpp:46
bool operator!=(const StringMap &RHS) const
Definition: StringMap.h:269
auto count(R &&Range, const E &Element)
Wrapper function around std::count to count the number of times an element Element occurs in the give...
Definition: STLExtras.h:1567
DerivedTy operator++(int)
Definition: StringMap.h:398
StringMap(std::initializer_list< std::pair< StringRef, ValueTy >> List)
Definition: StringMap.h:125
bool empty() const
Definition: StringMap.h:90
unsigned NumTombstones
Definition: StringMap.h:38
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
StringMapImpl(StringMapImpl &&RHS)
Definition: StringMap.h:43
unsigned getNumItems() const
Definition: StringMap.h:88
StringMapEntryBase - Shared base class of StringMapEntry instances.
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:241
const StringMapEntry< ValueTy > & operator*() const
Definition: StringMap.h:424
iterator end()
Definition: StringMap.h:203
constexpr char Args[]
Key for Kernel::Metadata::mArgs.