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 
168  if (NewItem == nullptr)
169  report_bad_alloc_error("Allocation of StringMap entry failed.");
170 
171  // Construct the value.
172  new (NewItem) StringMapEntry(KeyLength, std::forward<InitTy>(InitVals)...);
173 
174  // Copy the string information.
175  char *StrBuffer = const_cast<char*>(NewItem->getKeyData());
176  if (KeyLength > 0)
177  memcpy(StrBuffer, Key.data(), KeyLength);
178  StrBuffer[KeyLength] = 0; // Null terminate for convenience of clients.
179  return NewItem;
180  }
181 
182  /// Create - Create a StringMapEntry with normal malloc/free.
183  template <typename... InitType>
184  static StringMapEntry *Create(StringRef Key, InitType &&... InitVal) {
185  MallocAllocator A;
186  return Create(Key, A, std::forward<InitType>(InitVal)...);
187  }
188 
190  return Create(Key, ValueTy());
191  }
192 
193  /// GetStringMapEntryFromKeyData - Given key data that is known to be embedded
194  /// into a StringMapEntry, return the StringMapEntry itself.
195  static StringMapEntry &GetStringMapEntryFromKeyData(const char *KeyData) {
196  char *Ptr = const_cast<char*>(KeyData) - sizeof(StringMapEntry<ValueTy>);
197  return *reinterpret_cast<StringMapEntry*>(Ptr);
198  }
199 
200  /// Destroy - Destroy this StringMapEntry, releasing memory back to the
201  /// specified allocator.
202  template<typename AllocatorTy>
203  void Destroy(AllocatorTy &Allocator) {
204  // Free memory referenced by the item.
205  size_t AllocSize = sizeof(StringMapEntry) + getKeyLength() + 1;
206  this->~StringMapEntry();
207  Allocator.Deallocate(static_cast<void *>(this), AllocSize);
208  }
209 
210  /// Destroy this object, releasing memory back to the malloc allocator.
211  void Destroy() {
212  MallocAllocator A;
213  Destroy(A);
214  }
215 };
216 
217 /// StringMap - This is an unconventional map that is specialized for handling
218 /// keys that are "strings", which are basically ranges of bytes. This does some
219 /// funky memory allocation and hashing things to make it extremely efficient,
220 /// storing the string data *after* the value in the map.
221 template<typename ValueTy, typename AllocatorTy = MallocAllocator>
222 class StringMap : public StringMapImpl {
223  AllocatorTy Allocator;
224 
225 public:
227 
228  StringMap() : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))) {}
229 
230  explicit StringMap(unsigned InitialSize)
231  : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))) {}
232 
233  explicit StringMap(AllocatorTy A)
234  : StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))), Allocator(A) {}
235 
236  StringMap(unsigned InitialSize, AllocatorTy A)
237  : StringMapImpl(InitialSize, static_cast<unsigned>(sizeof(MapEntryTy))),
238  Allocator(A) {}
239 
240  StringMap(std::initializer_list<std::pair<StringRef, ValueTy>> List)
241  : StringMapImpl(List.size(), static_cast<unsigned>(sizeof(MapEntryTy))) {
242  for (const auto &P : List) {
243  insert(P);
244  }
245  }
246 
248  : StringMapImpl(std::move(RHS)), Allocator(std::move(RHS.Allocator)) {}
249 
250  StringMap(const StringMap &RHS) :
251  StringMapImpl(static_cast<unsigned>(sizeof(MapEntryTy))),
252  Allocator(RHS.Allocator) {
253  if (RHS.empty())
254  return;
255 
256  // Allocate TheTable of the same size as RHS's TheTable, and set the
257  // sentinel appropriately (and NumBuckets).
258  init(RHS.NumBuckets);
259  unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1),
260  *RHSHashTable = (unsigned *)(RHS.TheTable + NumBuckets + 1);
261 
262  NumItems = RHS.NumItems;
263  NumTombstones = RHS.NumTombstones;
264  for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
265  StringMapEntryBase *Bucket = RHS.TheTable[I];
266  if (!Bucket || Bucket == getTombstoneVal()) {
267  TheTable[I] = Bucket;
268  continue;
269  }
270 
271  TheTable[I] = MapEntryTy::Create(
272  static_cast<MapEntryTy *>(Bucket)->getKey(), Allocator,
273  static_cast<MapEntryTy *>(Bucket)->getValue());
274  HashTable[I] = RHSHashTable[I];
275  }
276 
277  // Note that here we've copied everything from the RHS into this object,
278  // tombstones included. We could, instead, have re-probed for each key to
279  // instantiate this new object without any tombstone buckets. The
280  // assumption here is that items are rarely deleted from most StringMaps,
281  // and so tombstones are rare, so the cost of re-probing for all inputs is
282  // not worthwhile.
283  }
284 
286  StringMapImpl::swap(RHS);
287  std::swap(Allocator, RHS.Allocator);
288  return *this;
289  }
290 
292  // Delete all the elements in the map, but don't reset the elements
293  // to default values. This is a copy of clear(), but avoids unnecessary
294  // work not required in the destructor.
295  if (!empty()) {
296  for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
297  StringMapEntryBase *Bucket = TheTable[I];
298  if (Bucket && Bucket != getTombstoneVal()) {
299  static_cast<MapEntryTy*>(Bucket)->Destroy(Allocator);
300  }
301  }
302  }
303  free(TheTable);
304  }
305 
306  AllocatorTy &getAllocator() { return Allocator; }
307  const AllocatorTy &getAllocator() const { return Allocator; }
308 
309  using key_type = const char*;
310  using mapped_type = ValueTy;
312  using size_type = size_t;
313 
316 
318  return iterator(TheTable, NumBuckets == 0);
319  }
321  return iterator(TheTable+NumBuckets, true);
322  }
324  return const_iterator(TheTable, NumBuckets == 0);
325  }
326  const_iterator end() const {
327  return const_iterator(TheTable+NumBuckets, true);
328  }
329 
333  }
334 
336  int Bucket = FindKey(Key);
337  if (Bucket == -1) return end();
338  return iterator(TheTable+Bucket, true);
339  }
340 
342  int Bucket = FindKey(Key);
343  if (Bucket == -1) return end();
344  return const_iterator(TheTable+Bucket, true);
345  }
346 
347  /// lookup - Return the entry for the specified key, or a default
348  /// constructed value if no such entry exists.
349  ValueTy lookup(StringRef Key) const {
350  const_iterator it = find(Key);
351  if (it != end())
352  return it->second;
353  return ValueTy();
354  }
355 
356  /// Lookup the ValueTy for the \p Key, or create a default constructed value
357  /// if the key is not in the map.
358  ValueTy &operator[](StringRef Key) { return try_emplace(Key).first->second; }
359 
360  /// count - Return 1 if the element is in the map, 0 otherwise.
362  return find(Key) == end() ? 0 : 1;
363  }
364 
365  /// insert - Insert the specified key/value pair into the map. If the key
366  /// already exists in the map, return false and ignore the request, otherwise
367  /// insert it and return true.
368  bool insert(MapEntryTy *KeyValue) {
369  unsigned BucketNo = LookupBucketFor(KeyValue->getKey());
370  StringMapEntryBase *&Bucket = TheTable[BucketNo];
371  if (Bucket && Bucket != getTombstoneVal())
372  return false; // Already exists in map.
373 
374  if (Bucket == getTombstoneVal())
375  --NumTombstones;
376  Bucket = KeyValue;
377  ++NumItems;
378  assert(NumItems + NumTombstones <= NumBuckets);
379 
380  RehashTable();
381  return true;
382  }
383 
384  /// insert - Inserts the specified key/value pair into the map if the key
385  /// isn't already in the map. The bool component of the returned pair is true
386  /// if and only if the insertion takes place, and the iterator component of
387  /// the pair points to the element with key equivalent to the key of the pair.
388  std::pair<iterator, bool> insert(std::pair<StringRef, ValueTy> KV) {
389  return try_emplace(KV.first, std::move(KV.second));
390  }
391 
392  /// Emplace a new element for the specified key into the map if the key isn't
393  /// already in the map. The bool component of the returned pair is true
394  /// if and only if the insertion takes place, and the iterator component of
395  /// the pair points to the element with key equivalent to the key of the pair.
396  template <typename... ArgsTy>
397  std::pair<iterator, bool> try_emplace(StringRef Key, ArgsTy &&... Args) {
398  unsigned BucketNo = LookupBucketFor(Key);
399  StringMapEntryBase *&Bucket = TheTable[BucketNo];
400  if (Bucket && Bucket != getTombstoneVal())
401  return std::make_pair(iterator(TheTable + BucketNo, false),
402  false); // Already exists in map.
403 
404  if (Bucket == getTombstoneVal())
405  --NumTombstones;
406  Bucket = MapEntryTy::Create(Key, Allocator, std::forward<ArgsTy>(Args)...);
407  ++NumItems;
408  assert(NumItems + NumTombstones <= NumBuckets);
409 
410  BucketNo = RehashTable(BucketNo);
411  return std::make_pair(iterator(TheTable + BucketNo, false), true);
412  }
413 
414  // clear - Empties out the StringMap
415  void clear() {
416  if (empty()) return;
417 
418  // Zap all values, resetting the keys back to non-present (not tombstone),
419  // which is safe because we're removing all elements.
420  for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
421  StringMapEntryBase *&Bucket = TheTable[I];
422  if (Bucket && Bucket != getTombstoneVal()) {
423  static_cast<MapEntryTy*>(Bucket)->Destroy(Allocator);
424  }
425  Bucket = nullptr;
426  }
427 
428  NumItems = 0;
429  NumTombstones = 0;
430  }
431 
432  /// remove - Remove the specified key/value pair from the map, but do not
433  /// erase it. This aborts if the key is not in the map.
434  void remove(MapEntryTy *KeyValue) {
435  RemoveKey(KeyValue);
436  }
437 
438  void erase(iterator I) {
439  MapEntryTy &V = *I;
440  remove(&V);
441  V.Destroy(Allocator);
442  }
443 
445  iterator I = find(Key);
446  if (I == end()) return false;
447  erase(I);
448  return true;
449  }
450 };
451 
452 template <typename DerivedTy, typename ValueTy>
454  : public iterator_facade_base<DerivedTy, std::forward_iterator_tag,
455  ValueTy> {
456 protected:
457  StringMapEntryBase **Ptr = nullptr;
458 
459 public:
460  StringMapIterBase() = default;
461 
463  bool NoAdvance = false)
464  : Ptr(Bucket) {
465  if (!NoAdvance) AdvancePastEmptyBuckets();
466  }
467 
468  DerivedTy &operator=(const DerivedTy &Other) {
469  Ptr = Other.Ptr;
470  return static_cast<DerivedTy &>(*this);
471  }
472 
473  bool operator==(const DerivedTy &RHS) const { return Ptr == RHS.Ptr; }
474 
475  DerivedTy &operator++() { // Preincrement
476  ++Ptr;
477  AdvancePastEmptyBuckets();
478  return static_cast<DerivedTy &>(*this);
479  }
480 
481  DerivedTy operator++(int) { // Post-increment
482  DerivedTy Tmp(Ptr);
483  ++*this;
484  return Tmp;
485  }
486 
487 private:
488  void AdvancePastEmptyBuckets() {
489  while (*Ptr == nullptr || *Ptr == StringMapImpl::getTombstoneVal())
490  ++Ptr;
491  }
492 };
493 
494 template <typename ValueTy>
496  : public StringMapIterBase<StringMapConstIterator<ValueTy>,
497  const StringMapEntry<ValueTy>> {
500 
501 public:
502  StringMapConstIterator() = default;
504  bool NoAdvance = false)
505  : base(Bucket, NoAdvance) {}
506 
507  const StringMapEntry<ValueTy> &operator*() const {
508  return *static_cast<const StringMapEntry<ValueTy> *>(*this->Ptr);
509  }
510 };
511 
512 template <typename ValueTy>
513 class StringMapIterator : public StringMapIterBase<StringMapIterator<ValueTy>,
514  StringMapEntry<ValueTy>> {
515  using base =
517 
518 public:
519  StringMapIterator() = default;
521  bool NoAdvance = false)
522  : base(Bucket, NoAdvance) {}
523 
524  StringMapEntry<ValueTy> &operator*() const {
525  return *static_cast<StringMapEntry<ValueTy> *>(*this->Ptr);
526  }
527 
529  return StringMapConstIterator<ValueTy>(this->Ptr, true);
530  }
531 };
532 
533 template <typename ValueTy>
535  : public iterator_adaptor_base<StringMapKeyIterator<ValueTy>,
536  StringMapConstIterator<ValueTy>,
537  std::forward_iterator_tag, StringRef> {
540  std::forward_iterator_tag, StringRef>;
541 
542 public:
543  StringMapKeyIterator() = default;
544  explicit StringMapKeyIterator(StringMapConstIterator<ValueTy> Iter)
545  : base(std::move(Iter)) {}
546 
547  StringRef &operator*() {
548  Key = this->wrapped()->getKey();
549  return Key;
550  }
551 
552 private:
553  StringRef Key;
554 };
555 
556 } // end namespace llvm
557 
558 #endif // LLVM_ADT_STRINGMAP_H
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:245
iterator_range< StringMapKeyIterator< ValueTy > > keys() const
Definition: StringMap.h:330
StringMapImpl(unsigned itemSize)
Definition: StringMap.h:62
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:236
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:335
unsigned second
const_iterator end() const
Definition: StringMap.h:326
StringRef & operator*()
Definition: StringMap.h:547
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:250
const_iterator find(StringRef Key) const
Definition: StringMap.h:341
StringMapKeyIterator(StringMapConstIterator< ValueTy > Iter)
Definition: StringMap.h:544
Definition: BitVector.h:920
unsigned size() const
Definition: StringMap.h:112
const ValueTy & getValue() const
Definition: StringMap.h:141
StringMap & operator=(StringMap RHS)
Definition: StringMap.h:285
static StringMapEntry & GetStringMapEntryFromKeyData(const char *KeyData)
GetStringMapEntryFromKeyData - Given key data that is known to be embedded into a StringMapEntry...
Definition: StringMap.h:195
StringMapIterator(StringMapEntryBase **Bucket, bool NoAdvance=false)
Definition: StringMap.h:520
StringMap(AllocatorTy A)
Definition: StringMap.h:233
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:524
void Destroy(AllocatorTy &Allocator)
Destroy - Destroy this StringMapEntry, releasing memory back to the specified allocator.
Definition: StringMap.h:203
StringMapIterBase(StringMapEntryBase **Bucket, bool NoAdvance=false)
Definition: StringMap.h:462
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:397
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:247
#define P(N)
unsigned NumItems
Definition: StringMap.h:57
StringMapEntryBase ** TheTable
Definition: StringMap.h:55
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:406
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:361
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:323
StringRef getKey() const
Definition: StringMap.h:137
void erase(iterator I)
Definition: StringMap.h:438
void Destroy()
Destroy this object, releasing memory back to the malloc allocator.
Definition: StringMap.h:211
StringMap(unsigned InitialSize)
Definition: StringMap.h:230
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:349
DerivedTy & operator++()
Definition: StringMap.h:475
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:835
bool erase(StringRef Key)
Definition: StringMap.h:444
void report_bad_alloc_error(const char *Reason, bool GenCrashDiag=true)
Reports a bad alloc error, calling any user defined bad alloc error handler.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Basic Register Allocator
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:306
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:388
const AllocatorTy & getAllocator() const
Definition: StringMap.h:307
static StringMapEntryBase * getTombstoneVal()
Definition: StringMap.h:102
bool insert(MapEntryTy *KeyValue)
insert - Insert the specified key/value pair into the map.
Definition: StringMap.h:368
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:923
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:222
ValueTy & getValue()
Definition: StringMap.h:142
StringMap(unsigned InitialSize, AllocatorTy A)
Definition: StringMap.h:236
bool operator==(const DerivedTy &RHS) const
Definition: StringMap.h:473
unsigned getNumBuckets() const
Definition: StringMap.h:108
StringMapConstIterator(StringMapEntryBase **Bucket, bool NoAdvance=false)
Definition: StringMap.h:503
size_t getKeyLength() const
Definition: StringMap.h:45
DerivedTy & operator=(const DerivedTy &Other)
Definition: StringMap.h:468
iterator begin()
Definition: StringMap.h:317
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:184
static StringMapEntry * Create(StringRef Key)
Definition: StringMap.h:189
DerivedTy operator++(int)
Definition: StringMap.h:481
StringMap(std::initializer_list< std::pair< StringRef, ValueTy >> List)
Definition: StringMap.h:240
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:358
const StringMapEntry< ValueTy > & operator*() const
Definition: StringMap.h:507
iterator end()
Definition: StringMap.h:320
constexpr char Args[]
Key for Kernel::Metadata::mArgs.