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