LLVM: include/llvm/ADT/StringMap.h Source File (original) (raw)
1
2
3
4
5
6
7
8
9
10
11
12
13
14#ifndef LLVM_ADT_STRINGMAP_H
15#define LLVM_ADT_STRINGMAP_H
16
22#include <initializer_list>
23#include
24#include <type_traits>
25
26namespace llvm {
27
30
31
32
34protected:
35
36
37
43
44protected:
50 RHS.TheTable = nullptr;
51 RHS.NumBuckets = 0;
52 RHS.NumItems = 0;
53 RHS.NumTombstones = 0;
54 }
55
59
60
61
62
63
64
68
69
71
72
73
74
76
77
79
80
81
83
84
85
87
88
89
91
95
96public:
98 static_cast<uintptr_t>(-1)
100
104
107
110
111
112
113
114
115
117
124};
125
126
127
128
129
130template <typename ValueTy, typename AllocatorTy = MallocAllocator>
135
136public:
138
140
143
146
150
155
158
162 if (RHS.empty())
163 return;
164
165
166
169 *RHSHashTable = (unsigned *)(RHS.TheTable + NumBuckets + 1);
170
177 continue;
178 }
179
182 static_cast<MapEntryTy *>(Bucket)->getValue());
183 HashTable[I] = RHSHashTable[I];
184 }
185
186
187
188
189
190
191
192 }
193
199
201
202
203
208 }
209 }
210 }
211 }
212
213 using AllocTy::getAllocator;
214
219
222
231
236
238
240 int Bucket = FindKey(Key, FullHashValue);
241 if (Bucket == -1)
242 return end();
244 }
245
249
251 uint32_t FullHashValue) const {
252 int Bucket = FindKey(Key, FullHashValue);
253 if (Bucket == -1)
254 return end();
256 }
257
258
259
262 if (Iter != end())
263 return Iter->second;
264 return ValueTy();
265 }
266
267
268
269 [[nodiscard]] const ValueTy &at(StringRef Val) const {
270 auto Iter = this->find(Val);
271 assert(Iter != this->end() && "StringMap::at failed due to a missing key");
272 return Iter->second;
273 }
274
275
276
278
279
283
284
288
289 template
293
294
297 return false;
298
299 for (const auto &KeyValue : *this) {
300 auto FindInRHS = RHS.find(KeyValue.getKey());
301
302 if (FindInRHS == RHS.end())
303 return false;
304
305 if constexpr (!std::is_same_v<ValueTy, EmptyStringSetTag>) {
306 if (!(KeyValue.getValue() == FindInRHS->getValue()))
307 return false;
308 }
309 }
310
311 return true;
312 }
313
315 return !(*this == RHS);
316 }
317
318
319
320
325 return false;
326
329 Bucket = KeyValue;
332
334 return true;
335 }
336
337
338
339
340
341 std::pair<iterator, bool> insert(std::pair<StringRef, ValueTy> KV) {
343 std::move(KV.second));
344 }
345
346 std::pair<iterator, bool> insert(std::pair<StringRef, ValueTy> KV,
349 }
350
351
352
353
358
359
360
361
362 void insert(std::initializer_list<std::pair<StringRef, ValueTy>> List) {
364 }
365
366
367
368 template
371 if (!Ret.second)
372 Ret.first->second = std::forward(Val);
373 return Ret;
374 }
375
376
377
378
379
380 template <typename... ArgsTy>
384
385 template <typename... ArgsTy>
388 ArgsTy &&...Args) {
392 return {iterator(TheTable + BucketNo), false};
393
396 Bucket =
400
403 }
404
405
408 return;
409
410
411
415 }
416 Bucket = nullptr;
417 }
418
421 }
422
423
424
426
432
436 return false;
438 return true;
439 }
440};
441
444
445public:
449 using pointer = std::conditional_t<IsConst, const value_type *, value_type *>;
451 std::conditional_t<IsConst, const value_type &, value_type &>;
452
454
456 : Ptr(Bucket) {
457 if (Advance)
458 AdvancePastEmptyBuckets();
459 }
460
462 return *static_cast<value_type *>(*Ptr);
463 }
467
469 ++Ptr;
470 AdvancePastEmptyBuckets();
471 return *this;
472 }
473
476 ++*this;
477 return Tmp;
478 }
479
480 template <bool ToConst,
481 typename = typename std::enable_if::type>
485
488 return LHS.Ptr == RHS.Ptr;
489 }
490
494 }
495
496private:
497 void AdvancePastEmptyBuckets() {
499 ++Ptr;
500 }
501};
502
503template
506 StringMapIterBase<ValueTy, true>,
507 std::forward_iterator_tag, StringRef> {
510 std::forward_iterator_tag, StringRef>;
511
512public:
516
518};
519
520}
521
522#endif
for(const MachineOperand &MO :llvm::drop_begin(OldMI.operands(), Desc.getNumOperands()))
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
This file defines the StringMapEntry class - it is intended to be a low dependency implementation det...
This file defines MallocAllocator.
#define LLVM_ALLOCATORHOLDER_EMPTYBASE
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static bool contains(SmallPtrSetImpl< ConstantExpr * > &Cache, ConstantExpr *Expr, Constant *C)
static const BasicSubtargetSubTypeKV * find(StringRef S, ArrayRef< BasicSubtargetSubTypeKV > A)
Find KV in array using binary search.
StringMapEntryBase - Shared base class of StringMapEntry instances.
StringMapEntry - This is used to represent one value that is inserted into a StringMap.
static StringMapEntry * create(StringRef key, AllocatorTy &allocator, InitTy &&...initVals)
iterator_range< StringMapEntryBase ** > buckets()
Definition StringMap.h:92
void swap(StringMapImpl &Other)
Definition StringMap.h:118
static StringMapEntryBase * getTombstoneVal()
Definition StringMap.h:101
unsigned ItemSize
Definition StringMap.h:42
unsigned LookupBucketFor(StringRef Key)
LookupBucketFor - Look up the bucket that the specified string should end up in.
Definition StringMap.h:65
LLVM_ABI unsigned RehashTable(unsigned BucketNo=0)
RehashTable - Grow the table, redistributing values into the buckets with the appropriate mod-of-hash...
unsigned NumItems
Definition StringMap.h:40
LLVM_ABI void RemoveKey(StringMapEntryBase *V)
RemoveKey - Remove the specified StringMapEntry from the table, but do not delete it.
StringMapEntryBase ** TheTable
Definition StringMap.h:38
unsigned getNumBuckets() const
Definition StringMap.h:105
unsigned size() const
Definition StringMap.h:109
StringMapImpl(unsigned itemSize)
Definition StringMap.h:45
LLVM_ABI void init(unsigned Size)
Allocate the table with the specified number of buckets and otherwise setup the map as empty.
static LLVM_ABI uint32_t hash(StringRef Key)
Returns the hash value that will be used for the given string.
~StringMapImpl()
Definition StringMap.h:57
unsigned getNumItems() const
Definition StringMap.h:106
unsigned NumBuckets
Definition StringMap.h:39
static constexpr uintptr_t TombstoneIntVal
Definition StringMap.h:97
unsigned NumTombstones
Definition StringMap.h:41
int FindKey(StringRef Key) const
FindKey - Look up the bucket that contains the specified key.
Definition StringMap.h:75
bool empty() const
Definition StringMap.h:108
StringMapImpl(StringMapImpl &&RHS)
Definition StringMap.h:46
Definition StringMap.h:442
std::forward_iterator_tag iterator_category
Definition StringMap.h:446
StringMapIterBase & operator++()
Definition StringMap.h:468
pointer operator->() const
Definition StringMap.h:464
StringMapIterBase(StringMapEntryBase **Bucket, bool Advance=false)
Definition StringMap.h:455
StringMapEntry< ValueTy > value_type
Definition StringMap.h:447
StringMapIterBase operator++(int)
Definition StringMap.h:474
reference operator*() const
Definition StringMap.h:461
std::conditional_t< IsConst, const value_type *, value_type * > pointer
Definition StringMap.h:449
friend bool operator==(const StringMapIterBase &LHS, const StringMapIterBase &RHS)
Definition StringMap.h:486
StringMapIterBase()=default
friend bool operator!=(const StringMapIterBase &LHS, const StringMapIterBase &RHS)
Definition StringMap.h:491
std::ptrdiff_t difference_type
Definition StringMap.h:448
std::conditional_t< IsConst, const value_type &, value_type & > reference
Definition StringMap.h:450
Definition StringMap.h:507
StringRef operator*() const
Definition StringMap.h:517
StringMapKeyIterator()=default
StringMapKeyIterator(StringMapIterBase< ValueTy, true > Iter)
Definition StringMap.h:514
size_type count(const StringMapEntry< InputTy > &MapEntry) const
Definition StringMap.h:290
StringMap(StringMap &&RHS)
Definition StringMap.h:156
bool erase(StringRef Key)
Definition StringMap.h:433
void clear()
Definition StringMap.h:406
iterator end()
Definition StringMap.h:224
StringMap(std::initializer_list< std::pair< StringRef, ValueTy > > List)
Definition StringMap.h:151
bool operator!=(const StringMap &RHS) const
Definition StringMap.h:314
iterator begin()
Definition StringMap.h:223
void remove(MapEntryTy *KeyValue)
remove - Remove the specified key/value pair from the map, but do not erase it.
Definition StringMap.h:425
std::pair< iterator, bool > insert_or_assign(StringRef Key, V &&Val)
Inserts an element or assigns to the current element if the key already exists.
Definition StringMap.h:369
iterator find(StringRef Key)
Definition StringMap.h:237
const_iterator end() const
Definition StringMap.h:228
StringMap(const StringMap &RHS)
Definition StringMap.h:159
~StringMap()
Definition StringMap.h:200
const ValueTy & at(StringRef Val) const
at - Return the entry for the specified key, or abort if no such entry exists.
Definition StringMap.h:269
bool contains(StringRef Key) const
contains - Return true if the element is in the map, false otherwise.
Definition StringMap.h:280
StringMapIterBase< ValueTy, false > iterator
Definition StringMap.h:221
size_t size_type
Definition StringMap.h:218
ValueTy mapped_type
Definition StringMap.h:216
const char * key_type
Definition StringMap.h:215
iterator find(StringRef Key, uint32_t FullHashValue)
Definition StringMap.h:239
std::pair< iterator, bool > insert(std::pair< StringRef, ValueTy > KV)
insert - Inserts the specified key/value pair into the map if the key isn't already in the map.
Definition StringMap.h:341
iterator_range< StringMapKeyIterator< ValueTy > > keys() const
Definition StringMap.h:232
const_iterator find(StringRef Key) const
Definition StringMap.h:246
StringMap()
Definition StringMap.h:139
size_type count(StringRef Key) const
count - Return 1 if the element is in the map, 0 otherwise.
Definition StringMap.h:285
StringMap(AllocatorTy A)
Definition StringMap.h:144
StringMap & operator=(StringMap RHS)
Definition StringMap.h:194
void insert(InputIt First, InputIt Last)
Inserts elements from range [first, last).
Definition StringMap.h:354
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:260
StringMapEntry< ValueTy > value_type
Definition StringMap.h:217
const_iterator find(StringRef Key, uint32_t FullHashValue) const
Definition StringMap.h:250
StringMapIterBase< ValueTy, true > const_iterator
Definition StringMap.h:220
const_iterator begin() const
Definition StringMap.h:225
std::pair< iterator, bool > try_emplace_with_hash(StringRef Key, uint32_t FullHashValue, ArgsTy &&...Args)
Definition StringMap.h:386
void erase(iterator I)
Definition StringMap.h:427
StringMap(unsigned InitialSize)
Definition StringMap.h:141
std::pair< iterator, bool > try_emplace(StringRef Key, ArgsTy &&...Args)
Definition StringMap.h:381
std::pair< iterator, bool > insert(std::pair< StringRef, ValueTy > KV, uint32_t FullHashValue)
Definition StringMap.h:346
StringMap(unsigned InitialSize, AllocatorTy A)
Definition StringMap.h:147
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:277
AllocatorTy & getAllocator()
bool operator==(const StringMap &RHS) const
equal - check whether both of the containers are equal.
Definition StringMap.h:295
StringMapEntry< ValueTy > MapEntryTy
Definition StringMap.h:137
void insert(std::initializer_list< std::pair< StringRef, ValueTy > > List)
Inserts elements from initializer list ilist.
Definition StringMap.h:362
bool insert(MapEntryTy *KeyValue)
Definition StringMap.h:321
StringRef - Represent a constant reference to a string, i.e.
const StringMapIterBase< ValueTy, true > & wrapped() const
iterator_adaptor_base()=default
A range adaptor for a pair of iterators.
This is an optimization pass for GlobalISel generic memory operations.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
LLVM_ATTRIBUTE_VISIBILITY_DEFAULT AnalysisKey InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key
@ First
Helpers to iterate all locations in the MemoryEffectsBase class.
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Implement std::hash so that hash_code can be used in STL containers.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
A traits type that is used to handle pointer types and things that are just wrappers for pointers as ...