LLVM  9.0.0svn
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 
16 #include "llvm/ADT/StringRef.h"
17 #include "llvm/ADT/iterator.h"
19 #include "llvm/Support/Allocator.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 
31 namespace llvm {
32 
33 template<typename ValueTy> class StringMapConstIterator;
34 template<typename ValueTy> class StringMapIterator;
35 template<typename ValueTy> class StringMapKeyIterator;
36 
37 /// StringMapEntryBase - Shared base class of StringMapEntry instances.
39  size_t StrLen;
40 
41 public:
42  explicit StringMapEntryBase(size_t Len) : StrLen(Len) {}
43 
44  size_t getKeyLength() const { return StrLen; }
45 };
46 
47 /// StringMapImpl - This is the base class of StringMap that is shared among
48 /// all of its instantiations.
50 protected:
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 
60 protected:
61  explicit StringMapImpl(unsigned itemSize)
62  : ItemSize(itemSize) {}
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 
100 public:
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.
124 template<typename ValueTy>
126 public:
127  ValueTy second;
128 
129  explicit StringMapEntry(size_t strLen)
130  : StringMapEntryBase(strLen), second() {}
131  template <typename... InitTy>
132  StringMapEntry(size_t 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  size_t KeyLength = Key.size();
158 
159  // Allocate a new item with space for the string at the end and a null
160  // terminator.
161  size_t AllocSize = sizeof(StringMapEntry) + KeyLength + 1;
162  size_t Alignment = alignof(StringMapEntry);
163 
164  StringMapEntry *NewItem =
165  static_cast<StringMapEntry*>(Allocator.Allocate(AllocSize,Alignment));
166  assert(NewItem && "Unhandled out-of-memory");
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 
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  size_t AllocSize = sizeof(StringMapEntry) + getKeyLength() + 1;
203  this->~StringMapEntry();
204  Allocator.Deallocate(static_cast<void *>(this), AllocSize);
205  }
206 
207  /// Destroy this object, releasing memory back to the malloc allocator.
208  void Destroy() {
209  MallocAllocator A;
210  Destroy(A);
211  }
212 };
213 
214 /// StringMap - This is an unconventional map that is specialized for handling
215 /// keys that are "strings", which are basically ranges of bytes. This does some
216 /// funky memory allocation and hashing things to make it extremely efficient,
217 /// storing the string data *after* the value in the map.
218 template<typename ValueTy, typename AllocatorTy = MallocAllocator>
219 class StringMap : public StringMapImpl {
220  AllocatorTy Allocator;
221 
222 public:
224 
225  StringMap() : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {}
226 
227  explicit StringMap(unsigned InitialSize)
228  : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))) {}
229 
230  explicit StringMap(AllocatorTy A)
231  : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))), Allocator(A) {}
232 
233  StringMap(unsigned InitialSize, AllocatorTy A)
234  : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))),
235  Allocator(A) {}
236 
237  StringMap(std::initializer_list<std::pair<StringRef, ValueTy>> List)
238  : StringMapImpl(List.size(), static_cast<unsigned>(sizeof(MapEntryTy))) {
239  for (const auto &P : List) {
240  insert(P);
241  }
242  }
243 
245  : StringMapImpl(std::move(RHS)), Allocator(std::move(RHS.Allocator)) {}
246 
247  StringMap(const StringMap &RHS) :
248  StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))),
249  Allocator(RHS.Allocator) {
250  if (RHS.empty())
251  return;
252 
253  // Allocate TheTable of the same size as RHS's TheTable, and set the
254  // sentinel appropriately (and NumBuckets).
255  init(RHS.NumBuckets);
256  unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1),
257  *RHSHashTable = (unsigned *)(RHS.TheTable + NumBuckets + 1);
258 
259  NumItems = RHS.NumItems;
260  NumTombstones = RHS.NumTombstones;
261  for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
262  StringMapEntryBase *Bucket = RHS.TheTable[I];
263  if (!Bucket || Bucket == getTombstoneVal()) {
264  TheTable[I] = Bucket;
265  continue;
266  }
267 
268  TheTable[I] = MapEntryTy::Create(
269  static_cast<MapEntryTy *>(Bucket)->getKey(), Allocator,
270  static_cast<MapEntryTy *>(Bucket)->getValue());
271  HashTable[I] = RHSHashTable[I];
272  }
273 
274  // Note that here we've copied everything from the RHS into this object,
275  // tombstones included. We could, instead, have re-probed for each key to
276  // instantiate this new object without any tombstone buckets. The
277  // assumption here is that items are rarely deleted from most StringMaps,
278  // and so tombstones are rare, so the cost of re-probing for all inputs is
279  // not worthwhile.
280  }
281 
283  StringMapImpl::swap(RHS);
284  std::swap(Allocator, RHS.Allocator);
285  return *this;
286  }
287 
289  // Delete all the elements in the map, but don't reset the elements
290  // to default values. This is a copy of clear(), but avoids unnecessary
291  // work not required in the destructor.
292  if (!empty()) {
293  for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
294  StringMapEntryBase *Bucket = TheTable[I];
295  if (Bucket && Bucket != getTombstoneVal()) {
296  static_cast<MapEntryTy*>(Bucket)->Destroy(Allocator);
297  }
298  }
299  }
300  free(TheTable);
301  }
302 
303  AllocatorTy &getAllocator() { return Allocator; }
304  const AllocatorTy &getAllocator() const { return Allocator; }
305 
306  using key_type = const char*;
307  using mapped_type = ValueTy;
309  using size_type = size_t;
310 
313 
315  return iterator(TheTable, NumBuckets == 0);
316  }
318  return iterator(TheTable+NumBuckets, true);
319  }
321  return const_iterator(TheTable, NumBuckets == 0);
322  }
323  const_iterator end() const {
324  return const_iterator(TheTable+NumBuckets, true);
325  }
326 
330  }
331 
333  int Bucket = FindKey(Key);
334  if (Bucket == -1) return end();
335  return iterator(TheTable+Bucket, true);
336  }
337 
339  int Bucket = FindKey(Key);
340  if (Bucket == -1) return end();
341  return const_iterator(TheTable+Bucket, true);
342  }
343 
344  /// lookup - Return the entry for the specified key, or a default
345  /// constructed value if no such entry exists.
346  ValueTy lookup(StringRef Key) const {
347  const_iterator it = find(Key);
348  if (it != end())
349  return it->second;
350  return ValueTy();
351  }
352 
353  /// Lookup the ValueTy for the \p Key, or create a default constructed value
354  /// if the key is not in the map.
355  ValueTy &operator[](StringRef Key) { return try_emplace(Key).first->second; }
356 
357  /// count - Return 1 if the element is in the map, 0 otherwise.
359  return find(Key) == end() ? 0 : 1;
360  }
361 
362  /// insert - Insert the specified key/value pair into the map. If the key
363  /// already exists in the map, return false and ignore the request, otherwise
364  /// insert it and return true.
365  bool insert(MapEntryTy *KeyValue) {
366  unsigned BucketNo = LookupBucketFor(KeyValue->getKey());
367  StringMapEntryBase *&Bucket = TheTable[BucketNo];
368  if (Bucket && Bucket != getTombstoneVal())
369  return false; // Already exists in map.
370 
371  if (Bucket == getTombstoneVal())
372  --NumTombstones;
373  Bucket = KeyValue;
374  ++NumItems;
375  assert(NumItems + NumTombstones <= NumBuckets);
376 
377  RehashTable();
378  return true;
379  }
380 
381  /// insert - Inserts the specified key/value pair into the map if the key
382  /// isn't already in the map. The bool component of the returned pair is true
383  /// if and only if the insertion takes place, and the iterator component of
384  /// the pair points to the element with key equivalent to the key of the pair.
385  std::pair<iterator, bool> insert(std::pair<StringRef, ValueTy> KV) {
386  return try_emplace(KV.first, std::move(KV.second));
387  }
388 
389  /// Emplace a new element for the specified key into the map if the key isn't
390  /// already in the map. The bool component of the returned pair is true
391  /// if and only if the insertion takes place, and the iterator component of
392  /// the pair points to the element with key equivalent to the key of the pair.
393  template <typename... ArgsTy>
394  std::pair<iterator, bool> try_emplace(StringRef Key, ArgsTy &&... Args) {
395  unsigned BucketNo = LookupBucketFor(Key);
396  StringMapEntryBase *&Bucket = TheTable[BucketNo];
397  if (Bucket && Bucket != getTombstoneVal())
398  return std::make_pair(iterator(TheTable + BucketNo, false),
399  false); // Already exists in map.
400 
401  if (Bucket == getTombstoneVal())
402  --NumTombstones;
403  Bucket = MapEntryTy::Create(Key, Allocator, std::forward<ArgsTy>(Args)...);
404  ++NumItems;
405  assert(NumItems + NumTombstones <= NumBuckets);
406 
407  BucketNo = RehashTable(BucketNo);
408  return std::make_pair(iterator(TheTable + BucketNo, false), true);
409  }
410 
411  // clear - Empties out the StringMap
412  void clear() {
413  if (empty()) return;
414 
415  // Zap all values, resetting the keys back to non-present (not tombstone),
416  // which is safe because we're removing all elements.
417  for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
418  StringMapEntryBase *&Bucket = TheTable[I];
419  if (Bucket && Bucket != getTombstoneVal()) {
420  static_cast<MapEntryTy*>(Bucket)->Destroy(Allocator);
421  }
422  Bucket = nullptr;
423  }
424 
425  NumItems = 0;
426  NumTombstones = 0;
427  }
428 
429  /// remove - Remove the specified key/value pair from the map, but do not
430  /// erase it. This aborts if the key is not in the map.
431  void remove(MapEntryTy *KeyValue) {
432  RemoveKey(KeyValue);
433  }
434 
435  void erase(iterator I) {
436  MapEntryTy &V = *I;
437  remove(&V);
438  V.Destroy(Allocator);
439  }
440 
442  iterator I = find(Key);
443  if (I == end()) return false;
444  erase(I);
445  return true;
446  }
447 };
448 
449 template <typename DerivedTy, typename ValueTy>
451  : public iterator_facade_base<DerivedTy, std::forward_iterator_tag,
452  ValueTy> {
453 protected:
454  StringMapEntryBase **Ptr = nullptr;
455 
456 public:
457  StringMapIterBase() = default;
458 
460  bool NoAdvance = false)
461  : Ptr(Bucket) {
462  if (!NoAdvance) AdvancePastEmptyBuckets();
463  }
464 
465  DerivedTy &operator=(const DerivedTy &Other) {
466  Ptr = Other.Ptr;
467  return static_cast<DerivedTy &>(*this);
468  }
469 
470  bool operator==(const DerivedTy &RHS) const { return Ptr == RHS.Ptr; }
471 
472  DerivedTy &operator++() { // Preincrement
473  ++Ptr;
474  AdvancePastEmptyBuckets();
475  return static_cast<DerivedTy &>(*this);
476  }
477 
478  DerivedTy operator++(int) { // Post-increment
479  DerivedTy Tmp(Ptr);
480  ++*this;
481  return Tmp;
482  }
483 
484 private:
485  void AdvancePastEmptyBuckets() {
486  while (*Ptr == nullptr || *Ptr == StringMapImpl::getTombstoneVal())
487  ++Ptr;
488  }
489 };
490 
491 template <typename ValueTy>
493  : public StringMapIterBase<StringMapConstIterator<ValueTy>,
494  const StringMapEntry<ValueTy>> {
497 
498 public:
499  StringMapConstIterator() = default;
501  bool NoAdvance = false)
502  : base(Bucket, NoAdvance) {}
503 
504  const StringMapEntry<ValueTy> &operator*() const {
505  return *static_cast<const StringMapEntry<ValueTy> *>(*this->Ptr);
506  }
507 };
508 
509 template <typename ValueTy>
510 class StringMapIterator : public StringMapIterBase<StringMapIterator<ValueTy>,
511  StringMapEntry<ValueTy>> {
512  using base =
514 
515 public:
516  StringMapIterator() = default;
518  bool NoAdvance = false)
519  : base(Bucket, NoAdvance) {}
520 
521  StringMapEntry<ValueTy> &operator*() const {
522  return *static_cast<StringMapEntry<ValueTy> *>(*this->Ptr);
523  }
524 
526  return StringMapConstIterator<ValueTy>(this->Ptr, true);
527  }
528 };
529 
530 template <typename ValueTy>
532  : public iterator_adaptor_base<StringMapKeyIterator<ValueTy>,
533  StringMapConstIterator<ValueTy>,
534  std::forward_iterator_tag, StringRef> {
537  std::forward_iterator_tag, StringRef>;
538 
539 public:
540  StringMapKeyIterator() = default;
541  explicit StringMapKeyIterator(StringMapConstIterator<ValueTy> Iter)
542  : base(std::move(Iter)) {}
543 
544  StringRef &operator*() {
545  Key = this->wrapped()->getKey();
546  return Key;
547  }
548 
549 private:
550  StringRef Key;
551 };
552 
553 } // end namespace llvm
554 
555 #endif // LLVM_ADT_STRINGMAP_H
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:233
iterator_range< StringMapKeyIterator< ValueTy > > keys() const
Definition: StringMap.h:327
StringMapImpl(unsigned itemSize)
Definition: StringMap.h:61
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.
Definition: StringMap.h:125
void setValue(const ValueTy &V)
Definition: StringMap.h:143
This provides a very simple, boring adaptor for a begin and end iterator into a range type...
iterator find(StringRef Key)
Definition: StringMap.h:332
unsigned second
const_iterator end() const
Definition: StringMap.h:323
StringRef & operator*()
Definition: StringMap.h:544
This file defines the MallocAllocator and BumpPtrAllocator interfaces.
StringMap(const StringMap &RHS)
Definition: StringMap.h:247
const_iterator find(StringRef Key) const
Definition: StringMap.h:338
StringMapKeyIterator(StringMapConstIterator< ValueTy > Iter)
Definition: StringMap.h:541
Definition: BitVector.h:937
unsigned size() const
Definition: StringMap.h:111
const ValueTy & getValue() const
Definition: StringMap.h:140
StringMap & operator=(StringMap RHS)
Definition: StringMap.h:282
static StringMapEntry & GetStringMapEntryFromKeyData(const char *KeyData)
GetStringMapEntryFromKeyData - Given key data that is known to be embedded into a StringMapEntry...
Definition: StringMap.h:192
StringMapIterator(StringMapEntryBase **Bucket, bool NoAdvance=false)
Definition: StringMap.h:517
StringMap(AllocatorTy A)
Definition: StringMap.h:230
static StringMapEntry * Create(StringRef Key, AllocatorTy &Allocator, InitTy &&... InitVals)
Create a StringMapEntry for the specified key construct the value using InitiVals.
Definition: StringMap.h:155
StringMapImpl - This is the base class of StringMap that is shared among all of its instantiations...
Definition: StringMap.h:49
Key
PAL metadata keys.
StringMapEntry< ValueTy > & operator*() const
Definition: StringMap.h:521
void Destroy(AllocatorTy &Allocator)
Destroy - Destroy this StringMapEntry, releasing memory back to the specified allocator.
Definition: StringMap.h:200
StringMapIterBase(StringMapEntryBase **Bucket, bool NoAdvance=false)
Definition: StringMap.h:459
LLVM_NODISCARD size_t size() const
size - Get the string size.
Definition: StringRef.h:130
void swap(StringMapImpl &Other)
Definition: StringMap.h:113
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:394
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:244
#define P(N)
unsigned NumItems
Definition: StringMap.h:56
StringMapEntryBase ** TheTable
Definition: StringMap.h:54
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:427
StringRef first() const
Definition: StringMap.h:150
size_type count(StringRef Key) const
count - Return 1 if the element is in the map, 0 otherwise.
Definition: StringMap.h:358
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:320
StringRef getKey() const
Definition: StringMap.h:136
void erase(iterator I)
Definition: StringMap.h:435
void Destroy()
Destroy this object, releasing memory back to the malloc allocator.
Definition: StringMap.h:208
StringMap(unsigned InitialSize)
Definition: StringMap.h:227
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:346
DerivedTy & operator++()
Definition: StringMap.h:472
auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1206
bool erase(StringRef Key)
Definition: StringMap.h:441
constexpr bool empty(const T &RangeOrContainer)
Test whether RangeOrContainer is empty. Similar to C++17 std::empty.
Definition: STLExtras.h:209
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Basic Register Allocator
auto size(R &&Range, typename std::enable_if< std::is_same< typename std::iterator_traits< decltype(Range.begin())>::iterator_category, std::random_access_iterator_tag >::value, void >::type *=nullptr) -> decltype(std::distance(Range.begin(), Range.end()))
Get the size of a range.
Definition: STLExtras.h:1166
StringMapEntryBase(size_t Len)
Definition: StringMap.h:42
StringMapEntry(size_t strLen, InitTy &&... InitVals)
Definition: StringMap.h:132
unsigned ItemSize
Definition: StringMap.h:58
AllocatorTy & getAllocator()
Definition: StringMap.h:303
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:385
const AllocatorTy & getAllocator() const
Definition: StringMap.h:304
static StringMapEntryBase * getTombstoneVal()
Definition: StringMap.h:101
bool insert(MapEntryTy *KeyValue)
insert - Insert the specified key/value pair into the map.
Definition: StringMap.h:365
unsigned NumBuckets
Definition: StringMap.h:55
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:940
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:219
ValueTy & getValue()
Definition: StringMap.h:141
StringMap(unsigned InitialSize, AllocatorTy A)
Definition: StringMap.h:233
bool operator==(const DerivedTy &RHS) const
Definition: StringMap.h:470
unsigned getNumBuckets() const
Definition: StringMap.h:107
StringMapConstIterator(StringMapEntryBase **Bucket, bool NoAdvance=false)
Definition: StringMap.h:500
size_t getKeyLength() const
Definition: StringMap.h:44
DerivedTy & operator=(const DerivedTy &Other)
Definition: StringMap.h:465
iterator begin()
Definition: StringMap.h:314
StringMapEntry(size_t strLen)
Definition: StringMap.h:129
const NodeList & List
Definition: RDFGraph.cpp:201
#define I(x, y, z)
Definition: MD5.cpp:58
const char * getKeyData() const
getKeyData - Return the start of the string data that is the key for this value.
Definition: StringMap.h:148
static StringMapEntry * Create(StringRef Key, InitType &&... InitVal)
Create - Create a StringMapEntry with normal malloc/free.
Definition: StringMap.h:181
static StringMapEntry * Create(StringRef Key)
Definition: StringMap.h:186
uint32_t Size
Definition: Profile.cpp:46
DerivedTy operator++(int)
Definition: StringMap.h:478
LLVM_NODISCARD const char * data() const
data - Get a pointer to the start of the string (which may not be null terminated).
Definition: StringRef.h:122
StringMap(std::initializer_list< std::pair< StringRef, ValueTy >> List)
Definition: StringMap.h:237
bool empty() const
Definition: StringMap.h:110
unsigned NumTombstones
Definition: StringMap.h:57
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
StringMapImpl(StringMapImpl &&RHS)
Definition: StringMap.h:63
unsigned getNumItems() const
Definition: StringMap.h:108
StringMapEntryBase - Shared base class of StringMapEntry instances.
Definition: StringMap.h:38
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
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:355
const StringMapEntry< ValueTy > & operator*() const
Definition: StringMap.h:504
iterator end()
Definition: StringMap.h:317
constexpr char Args[]
Key for Kernel::Metadata::mArgs.