LLVM  7.0.0svn
StringMap.h
Go to the documentation of this file.
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"
20 #include "llvm/Support/Allocator.h"
23 #include <algorithm>
24 #include <cassert>
25 #include <cstdint>
26 #include <cstdlib>
27 #include <cstring>
28 #include <initializer_list>
29 #include <iterator>
30 #include <utility>
31 
32 namespace llvm {
33 
34 template<typename ValueTy> class StringMapConstIterator;
35 template<typename ValueTy> class StringMapIterator;
36 template<typename ValueTy> class StringMapKeyIterator;
37 
38 /// StringMapEntryBase - Shared base class of StringMapEntry instances.
40  size_t StrLen;
41 
42 public:
43  explicit StringMapEntryBase(size_t Len) : StrLen(Len) {}
44 
45  size_t getKeyLength() const { return StrLen; }
46 };
47 
48 /// StringMapImpl - This is the base class of StringMap that is shared among
49 /// all of its instantiations.
51 protected:
52  // Array of NumBuckets pointers to entries, null pointers are holes.
53  // TheTable[NumBuckets] contains a sentinel value for easy iteration. Followed
54  // by an array of the actual hash values as unsigned integers.
55  StringMapEntryBase **TheTable = nullptr;
56  unsigned NumBuckets = 0;
57  unsigned NumItems = 0;
58  unsigned NumTombstones = 0;
59  unsigned ItemSize;
60 
61 protected:
62  explicit StringMapImpl(unsigned itemSize)
63  : ItemSize(itemSize) {}
65  : TheTable(RHS.TheTable), NumBuckets(RHS.NumBuckets),
66  NumItems(RHS.NumItems), NumTombstones(RHS.NumTombstones),
67  ItemSize(RHS.ItemSize) {
68  RHS.TheTable = nullptr;
69  RHS.NumBuckets = 0;
70  RHS.NumItems = 0;
71  RHS.NumTombstones = 0;
72  }
73 
74  StringMapImpl(unsigned InitSize, unsigned ItemSize);
75  unsigned RehashTable(unsigned BucketNo = 0);
76 
77  /// LookupBucketFor - Look up the bucket that the specified string should end
78  /// up in. If it already exists as a key in the map, the Item pointer for the
79  /// specified bucket will be non-null. Otherwise, it will be null. In either
80  /// case, the FullHashValue field of the bucket will be set to the hash value
81  /// of the string.
82  unsigned LookupBucketFor(StringRef Key);
83 
84  /// FindKey - Look up the bucket that contains the specified key. If it exists
85  /// in the map, return the bucket number of the key. Otherwise return -1.
86  /// This does not modify the map.
87  int FindKey(StringRef Key) const;
88 
89  /// RemoveKey - Remove the specified StringMapEntry from the table, but do not
90  /// delete it. This aborts if the value isn't in the table.
91  void RemoveKey(StringMapEntryBase *V);
92 
93  /// RemoveKey - Remove the StringMapEntry for the specified key from the
94  /// table, returning it. If the key is not in the table, this returns null.
95  StringMapEntryBase *RemoveKey(StringRef Key);
96 
97  /// Allocate the table with the specified number of buckets and otherwise
98  /// setup the map as empty.
99  void init(unsigned Size);
100 
101 public:
103  uintptr_t Val = static_cast<uintptr_t>(-1);
104  Val <<= PointerLikeTypeTraits<StringMapEntryBase *>::NumLowBitsAvailable;
105  return reinterpret_cast<StringMapEntryBase *>(Val);
106  }
107 
108  unsigned getNumBuckets() const { return NumBuckets; }
109  unsigned getNumItems() const { return NumItems; }
110 
111  bool empty() const { return NumItems == 0; }
112  unsigned size() const { return NumItems; }
113 
114  void swap(StringMapImpl &Other) {
115  std::swap(TheTable, Other.TheTable);
116  std::swap(NumBuckets, Other.NumBuckets);
117  std::swap(NumItems, Other.NumItems);
118  std::swap(NumTombstones, Other.NumTombstones);
119  }
120 };
121 
122 /// StringMapEntry - This is used to represent one value that is inserted into
123 /// a StringMap. It contains the Value itself and the key: the string length
124 /// and data.
125 template<typename ValueTy>
127 public:
128  ValueTy second;
129 
130  explicit StringMapEntry(size_t strLen)
131  : StringMapEntryBase(strLen), second() {}
132  template <typename... InitTy>
133  StringMapEntry(size_t strLen, InitTy &&... InitVals)
134  : StringMapEntryBase(strLen), second(std::forward<InitTy>(InitVals)...) {}
135  StringMapEntry(StringMapEntry &E) = delete;
136 
137  StringRef getKey() const {
138  return StringRef(getKeyData(), getKeyLength());
139  }
140 
141  const ValueTy &getValue() const { return second; }
142  ValueTy &getValue() { return second; }
143 
144  void setValue(const ValueTy &V) { second = V; }
145 
146  /// getKeyData - Return the start of the string data that is the key for this
147  /// value. The string data is always stored immediately after the
148  /// StringMapEntry object.
149  const char *getKeyData() const {return reinterpret_cast<const char*>(this+1);}
150 
151  StringRef first() const { return StringRef(getKeyData(), getKeyLength()); }
152 
153  /// Create a StringMapEntry for the specified key construct the value using
154  /// \p InitiVals.
155  template <typename AllocatorTy, typename... InitTy>
156  static StringMapEntry *Create(StringRef Key, AllocatorTy &Allocator,
157  InitTy &&... InitVals) {
158  size_t KeyLength = Key.size();
159 
160  // Allocate a new item with space for the string at the end and a null
161  // terminator.
162  size_t AllocSize = sizeof(StringMapEntry) + KeyLength + 1;
163  size_t Alignment = alignof(StringMapEntry);
164 
165  StringMapEntry *NewItem =
166  static_cast<StringMapEntry*>(Allocator.Allocate(AllocSize,Alignment));
167  assert(NewItem && "Unhandled out-of-memory");
168 
169  // Construct the value.
170  new (NewItem) StringMapEntry(KeyLength, std::forward<InitTy>(InitVals)...);
171 
172  // Copy the string information.
173  char *StrBuffer = const_cast<char*>(NewItem->getKeyData());
174  if (KeyLength > 0)
175  memcpy(StrBuffer, Key.data(), KeyLength);
176  StrBuffer[KeyLength] = 0; // Null terminate for convenience of clients.
177  return NewItem;
178  }
179 
180  /// Create - Create a StringMapEntry with normal malloc/free.
181  template <typename... InitType>
182  static StringMapEntry *Create(StringRef Key, InitType &&... InitVal) {
183  MallocAllocator A;
184  return Create(Key, A, std::forward<InitType>(InitVal)...);
185  }
186 
188  return Create(Key, ValueTy());
189  }
190 
191  /// GetStringMapEntryFromKeyData - Given key data that is known to be embedded
192  /// into a StringMapEntry, return the StringMapEntry itself.
193  static StringMapEntry &GetStringMapEntryFromKeyData(const char *KeyData) {
194  char *Ptr = const_cast<char*>(KeyData) - sizeof(StringMapEntry<ValueTy>);
195  return *reinterpret_cast<StringMapEntry*>(Ptr);
196  }
197 
198  /// Destroy - Destroy this StringMapEntry, releasing memory back to the
199  /// specified allocator.
200  template<typename AllocatorTy>
201  void Destroy(AllocatorTy &Allocator) {
202  // Free memory referenced by the item.
203  size_t AllocSize = 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.
219 template<typename ValueTy, typename AllocatorTy = MallocAllocator>
220 class StringMap : public StringMapImpl {
221  AllocatorTy Allocator;
222 
223 public:
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 
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 
284  StringMapImpl::swap(RHS);
285  std::swap(Allocator, RHS.Allocator);
286  return *this;
287  }
288 
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;
310  using size_type = size_t;
311 
314 
316  return iterator(TheTable, NumBuckets == 0);
317  }
319  return iterator(TheTable+NumBuckets, true);
320  }
322  return const_iterator(TheTable, NumBuckets == 0);
323  }
324  const_iterator end() const {
325  return const_iterator(TheTable+NumBuckets, true);
326  }
327 
331  }
332 
334  int Bucket = FindKey(Key);
335  if (Bucket == -1) return end();
336  return iterator(TheTable+Bucket, true);
337  }
338 
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.
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 
443  iterator I = find(Key);
444  if (I == end()) return false;
445  erase(I);
446  return true;
447  }
448 };
449 
450 template <typename DerivedTy, typename ValueTy>
452  : public iterator_facade_base<DerivedTy, std::forward_iterator_tag,
453  ValueTy> {
454 protected:
455  StringMapEntryBase **Ptr = nullptr;
456 
457 public:
458  StringMapIterBase() = default;
459 
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 
485 private:
486  void AdvancePastEmptyBuckets() {
487  while (*Ptr == nullptr || *Ptr == StringMapImpl::getTombstoneVal())
488  ++Ptr;
489  }
490 };
491 
492 template <typename ValueTy>
494  : public StringMapIterBase<StringMapConstIterator<ValueTy>,
495  const StringMapEntry<ValueTy>> {
498 
499 public:
500  StringMapConstIterator() = default;
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 
510 template <typename ValueTy>
511 class StringMapIterator : public StringMapIterBase<StringMapIterator<ValueTy>,
512  StringMapEntry<ValueTy>> {
513  using base =
515 
516 public:
517  StringMapIterator() = default;
519  bool NoAdvance = false)
520  : base(Bucket, NoAdvance) {}
521 
522  StringMapEntry<ValueTy> &operator*() const {
523  return *static_cast<StringMapEntry<ValueTy> *>(*this->Ptr);
524  }
525 
527  return StringMapConstIterator<ValueTy>(this->Ptr, true);
528  }
529 };
530 
531 template <typename ValueTy>
533  : public iterator_adaptor_base<StringMapKeyIterator<ValueTy>,
534  StringMapConstIterator<ValueTy>,
535  std::forward_iterator_tag, StringRef> {
538  std::forward_iterator_tag, StringRef>;
539 
540 public:
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 
550 private:
551  StringRef Key;
552 };
553 
554 } // end namespace llvm
555 
556 #endif // LLVM_ADT_STRINGMAP_H
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:250
iterator_range< StringMapKeyIterator< ValueTy > > keys() const
Definition: StringMap.h:328
StringMapImpl(unsigned itemSize)
Definition: StringMap.h:62
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:241
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
StringMapEntry - This is used to represent one value that is inserted into a StringMap.
Definition: StringMap.h:126
void setValue(const ValueTy &V)
Definition: StringMap.h:144
This provides a very simple, boring adaptor for a begin and end iterator into a range type...
LLVM_NODISCARD LLVM_ATTRIBUTE_ALWAYS_INLINE size_t size() const
size - Get the string size.
Definition: StringRef.h:138
iterator find(StringRef Key)
Definition: StringMap.h:333
unsigned second
const_iterator end() const
Definition: StringMap.h:324
StringRef & operator*()
Definition: StringMap.h:545
LLVM_NODISCARD LLVM_ATTRIBUTE_ALWAYS_INLINE const char * data() const
data - Get a pointer to the start of the string (which may not be null terminated).
Definition: StringRef.h:128
This file defines the MallocAllocator and BumpPtrAllocator interfaces.
StringMap(const StringMap &RHS)
Definition: StringMap.h:248
const_iterator find(StringRef Key) const
Definition: StringMap.h:339
StringMapKeyIterator(StringMapConstIterator< ValueTy > Iter)
Definition: StringMap.h:542
Definition: BitVector.h:921
unsigned size() const
Definition: StringMap.h:112
const ValueTy & getValue() const
Definition: StringMap.h:141
StringMap & operator=(StringMap RHS)
Definition: StringMap.h:283
static StringMapEntry & GetStringMapEntryFromKeyData(const char *KeyData)
GetStringMapEntryFromKeyData - Given key data that is known to be embedded into a StringMapEntry...
Definition: StringMap.h:193
StringMapIterator(StringMapEntryBase **Bucket, bool NoAdvance=false)
Definition: StringMap.h:518
StringMap(AllocatorTy A)
Definition: StringMap.h:231
static StringMapEntry * Create(StringRef Key, AllocatorTy &Allocator, InitTy &&... InitVals)
Create a StringMapEntry for the specified key construct the value using InitiVals.
Definition: StringMap.h:156
StringMapImpl - This is the base class of StringMap that is shared among all of its instantiations...
Definition: StringMap.h:50
Key
PAL metadata keys.
StringMapEntry< ValueTy > & operator*() const
Definition: StringMap.h:522
void Destroy(AllocatorTy &Allocator)
Destroy - Destroy this StringMapEntry, releasing memory back to the specified allocator.
Definition: StringMap.h:201
StringMapIterBase(StringMapEntryBase **Bucket, bool NoAdvance=false)
Definition: StringMap.h:460
void swap(StringMapImpl &Other)
Definition: StringMap.h:114
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:395
CRTP base class which implements the entire standard iterator facade in terms of a minimal subset of ...
Definition: iterator.h:68
StringMap(StringMap &&RHS)
Definition: StringMap.h:245
#define P(N)
unsigned NumItems
Definition: StringMap.h:57
StringMapEntryBase ** TheTable
Definition: StringMap.h:55
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:410
StringRef first() const
Definition: StringMap.h:151
size_type count(StringRef Key) const
count - Return 1 if the element is in the map, 0 otherwise.
Definition: StringMap.h:359
CRTP base class for adapting an iterator to a different type.
Definition: iterator.h:208
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
const_iterator begin() const
Definition: StringMap.h:321
StringRef getKey() const
Definition: StringMap.h:137
void erase(iterator I)
Definition: StringMap.h:436
void Destroy()
Destroy this object, releasing memory back to the malloc allocator.
Definition: StringMap.h:209
StringMap(unsigned InitialSize)
Definition: StringMap.h:228
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:347
DerivedTy & operator++()
Definition: StringMap.h:473
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:929
bool erase(StringRef Key)
Definition: StringMap.h:442
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:1032
StringMapEntryBase(size_t Len)
Definition: StringMap.h:43
StringMapEntry(size_t strLen, InitTy &&... InitVals)
Definition: StringMap.h:133
unsigned ItemSize
Definition: StringMap.h:59
AllocatorTy & getAllocator()
Definition: StringMap.h:304
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:386
const AllocatorTy & getAllocator() const
Definition: StringMap.h:305
static StringMapEntryBase * getTombstoneVal()
Definition: StringMap.h:102
bool insert(MapEntryTy *KeyValue)
insert - Insert the specified key/value pair into the map.
Definition: StringMap.h:366
unsigned NumBuckets
Definition: StringMap.h:56
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:924
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:220
ValueTy & getValue()
Definition: StringMap.h:142
StringMap(unsigned InitialSize, AllocatorTy A)
Definition: StringMap.h:234
bool operator==(const DerivedTy &RHS) const
Definition: StringMap.h:471
unsigned getNumBuckets() const
Definition: StringMap.h:108
StringMapConstIterator(StringMapEntryBase **Bucket, bool NoAdvance=false)
Definition: StringMap.h:501
size_t getKeyLength() const
Definition: StringMap.h:45
DerivedTy & operator=(const DerivedTy &Other)
Definition: StringMap.h:466
iterator begin()
Definition: StringMap.h:315
StringMapEntry(size_t strLen)
Definition: StringMap.h:130
const NodeList & List
Definition: RDFGraph.cpp:210
#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:149
static StringMapEntry * Create(StringRef Key, InitType &&... InitVal)
Create - Create a StringMapEntry with normal malloc/free.
Definition: StringMap.h:182
static StringMapEntry * Create(StringRef Key)
Definition: StringMap.h:187
DerivedTy operator++(int)
Definition: StringMap.h:479
StringMap(std::initializer_list< std::pair< StringRef, ValueTy >> List)
Definition: StringMap.h:238
bool empty() const
Definition: StringMap.h:111
unsigned NumTombstones
Definition: StringMap.h:58
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
StringMapImpl(StringMapImpl &&RHS)
Definition: StringMap.h:64
constexpr char Size[]
Key for Kernel::Arg::Metadata::mSize.
unsigned getNumItems() const
Definition: StringMap.h:109
StringMapEntryBase - Shared base class of StringMapEntry instances.
Definition: StringMap.h:39
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
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:356
const StringMapEntry< ValueTy > & operator*() const
Definition: StringMap.h:505
iterator end()
Definition: StringMap.h:318
constexpr char Args[]
Key for Kernel::Metadata::mArgs.