14#ifndef LLVM_ADT_STRINGMAP_H
15#define LLVM_ADT_STRINGMAP_H
21#include <initializer_list>
26template <
typename ValueTy>
class StringMapConstIterator;
27template <
typename ValueTy>
class StringMapIterator;
28template <
typename ValueTy>
class StringMapKeyIterator;
49 RHS.TheTable =
nullptr;
52 RHS.NumTombstones = 0;
93 static_cast<uintptr_t
>(-1)
125template <
typename ValueTy,
typename AllocatorTy = MallocAllocator>
146 StringMap(std::initializer_list<std::pair<StringRef, ValueTy>> List)
162 init(
RHS.NumBuckets);
163 unsigned *HashTable = (
unsigned *)(TheTable + NumBuckets + 1),
164 *RHSHashTable = (
unsigned *)(
RHS.TheTable + NumBuckets + 1);
166 NumItems =
RHS.NumItems;
167 NumTombstones =
RHS.NumTombstones;
168 for (
unsigned I = 0,
E = NumBuckets;
I !=
E; ++
I) {
170 if (!Bucket || Bucket == getTombstoneVal()) {
171 TheTable[
I] = Bucket;
175 TheTable[
I] = MapEntryTy::create(
176 static_cast<MapEntryTy *
>(Bucket)->getKey(), getAllocator(),
177 static_cast<MapEntryTy *
>(Bucket)->getValue());
178 HashTable[
I] = RHSHashTable[
I];
190 StringMapImpl::swap(
RHS);
200 for (
unsigned I = 0,
E = NumBuckets;
I !=
E; ++
I) {
202 if (Bucket && Bucket != getTombstoneVal()) {
203 static_cast<MapEntryTy *
>(Bucket)->Destroy(getAllocator());
209 using AllocTy::getAllocator;
236 int Bucket = FindKey(Key, FullHashValue);
239 return iterator(TheTable + Bucket,
true);
245 int Bucket = FindKey(Key, FullHashValue);
263 auto Iter = this->
find(std::move(Val));
264 assert(Iter != this->end() &&
"StringMap::at failed due to a missing key");
278 template <
typename InputTy>
288 for (
const auto &KeyValue : *
this) {
289 auto FindInRHS =
RHS.find(KeyValue.getKey());
291 if (FindInRHS ==
RHS.end())
294 if constexpr (!std::is_same_v<ValueTy, std::nullopt_t>) {
295 if (!(KeyValue.getValue() == FindInRHS->getValue()))
309 unsigned BucketNo = LookupBucketFor(KeyValue->
getKey());
311 if (Bucket && Bucket != getTombstoneVal())
314 if (Bucket == getTombstoneVal())
318 assert(NumItems + NumTombstones <= NumBuckets);
328 std::pair<iterator, bool>
insert(std::pair<StringRef, ValueTy> KV) {
329 return try_emplace_with_hash(KV.first, hash(KV.first),
330 std::move(KV.second));
333 std::pair<iterator, bool>
insert(std::pair<StringRef, ValueTy> KV,
335 return try_emplace_with_hash(KV.first, FullHashValue, std::move(KV.second));
341 template <
typename InputIt>
void insert(InputIt First, InputIt Last) {
342 for (InputIt It = First; It != Last; ++It)
349 void insert(std::initializer_list<std::pair<StringRef, ValueTy>> List) {
355 template <
typename V>
357 auto Ret = try_emplace(Key, std::forward<V>(Val));
359 Ret.first->second = std::forward<V>(Val);
367 template <
typename... ArgsTy>
369 return try_emplace_with_hash(Key, hash(Key), std::forward<ArgsTy>(Args)...);
372 template <
typename... ArgsTy>
376 unsigned BucketNo = LookupBucketFor(Key, FullHashValue);
378 if (Bucket && Bucket != getTombstoneVal())
379 return std::make_pair(
iterator(TheTable + BucketNo,
false),
382 if (Bucket == getTombstoneVal())
385 MapEntryTy::create(Key, getAllocator(), std::forward<ArgsTy>(Args)...);
387 assert(NumItems + NumTombstones <= NumBuckets);
389 BucketNo = RehashTable(BucketNo);
390 return std::make_pair(
iterator(TheTable + BucketNo,
false),
true);
400 for (
unsigned I = 0,
E = NumBuckets;
I !=
E; ++
I) {
402 if (Bucket && Bucket != getTombstoneVal()) {
403 static_cast<MapEntryTy *
>(Bucket)->Destroy(getAllocator());
419 V.Destroy(getAllocator());
431template <
typename DerivedTy,
typename ValueTy>
442 bool NoAdvance =
false)
445 AdvancePastEmptyBuckets();
450 return static_cast<DerivedTy &
>(*this);
454 return LHS.Ptr ==
RHS.Ptr;
459 AdvancePastEmptyBuckets();
460 return static_cast<DerivedTy &
>(*this);
470 void AdvancePastEmptyBuckets() {
476template <
typename ValueTy>
479 const StringMapEntry<ValueTy>> {
486 bool NoAdvance =
false)
487 :
base(Bucket, NoAdvance) {}
494template <
typename ValueTy>
496 StringMapEntry<ValueTy>> {
503 bool NoAdvance =
false)
504 :
base(Bucket, NoAdvance) {}
515template <
typename ValueTy>
518 StringMapConstIterator<ValueTy>,
519 std::forward_iterator_tag, StringRef> {
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")
ToRemove erase(NewLastIter, ToRemove.end())
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static bool contains(SmallPtrSetImpl< ConstantExpr * > &Cache, ConstantExpr *Expr, Constant *C)
StringMapConstIterator()=default
StringMapConstIterator(StringMapEntryBase **Bucket, bool NoAdvance=false)
const StringMapEntry< ValueTy > & operator*() const
StringMapEntryBase - Shared base class of StringMapEntry instances.
StringMapEntry - This is used to represent one value that is inserted into a StringMap.
StringMapImpl - This is the base class of StringMap that is shared among all of its instantiations.
void swap(StringMapImpl &Other)
static StringMapEntryBase * getTombstoneVal()
unsigned LookupBucketFor(StringRef Key)
LookupBucketFor - Look up the bucket that the specified string should end up in.
unsigned RehashTable(unsigned BucketNo=0)
RehashTable - Grow the table, redistributing values into the buckets with the appropriate mod-of-hash...
void RemoveKey(StringMapEntryBase *V)
RemoveKey - Remove the specified StringMapEntry from the table, but do not delete it.
StringMapEntryBase ** TheTable
unsigned getNumBuckets() const
StringMapImpl(unsigned itemSize)
void init(unsigned Size)
Allocate the table with the specified number of buckets and otherwise setup the map as empty.
static uint32_t hash(StringRef Key)
Returns the hash value that will be used for the given string.
unsigned getNumItems() const
static constexpr uintptr_t TombstoneIntVal
int FindKey(StringRef Key) const
FindKey - Look up the bucket that contains the specified key.
StringMapImpl(StringMapImpl &&RHS)
StringMapEntryBase ** Ptr
DerivedTy operator++(int)
DerivedTy & operator=(const DerivedTy &Other)
StringMapIterBase(StringMapEntryBase **Bucket, bool NoAdvance=false)
friend bool operator==(const DerivedTy &LHS, const DerivedTy &RHS)
StringMapIterBase()=default
StringMapIterator(StringMapEntryBase **Bucket, bool NoAdvance=false)
StringMapEntry< ValueTy > & operator*() const
StringMapIterator()=default
StringRef operator*() const
StringMapKeyIterator()=default
StringMapKeyIterator(StringMapConstIterator< ValueTy > Iter)
StringMap - This is an unconventional map that is specialized for handling keys that are "strings",...
size_type count(const StringMapEntry< InputTy > &MapEntry) const
StringMap(StringMap &&RHS)
bool erase(StringRef Key)
StringMap(std::initializer_list< std::pair< StringRef, ValueTy > > List)
bool operator!=(const StringMap &RHS) const
void remove(MapEntryTy *KeyValue)
remove - Remove the specified key/value pair from the map, but do not erase it.
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.
iterator find(StringRef Key)
const_iterator end() const
StringMap(const StringMap &RHS)
const ValueTy & at(StringRef Val) const
at - Return the entry for the specified key, or abort if no such entry exists.
bool contains(StringRef Key) const
contains - Return true if the element is in the map, false otherwise.
iterator find(StringRef Key, uint32_t FullHashValue)
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.
iterator_range< StringMapKeyIterator< ValueTy > > keys() const
const_iterator find(StringRef Key) const
size_type count(StringRef Key) const
count - Return 1 if the element is in the map, 0 otherwise.
StringMap & operator=(StringMap RHS)
void insert(InputIt First, InputIt Last)
Inserts elements from range [first, last).
ValueTy lookup(StringRef Key) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
const_iterator find(StringRef Key, uint32_t FullHashValue) const
const_iterator begin() const
std::pair< iterator, bool > try_emplace_with_hash(StringRef Key, uint32_t FullHashValue, ArgsTy &&...Args)
StringMap(unsigned InitialSize)
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't already in the map.
std::pair< iterator, bool > insert(std::pair< StringRef, ValueTy > KV, uint32_t FullHashValue)
StringMap(unsigned InitialSize, AllocatorTy A)
ValueTy & operator[](StringRef Key)
Lookup the ValueTy for the Key, or create a default constructed value if the key is not in the map.
bool operator==(const StringMap &RHS) const
equal - check whether both of the containers are equal.
void insert(std::initializer_list< std::pair< StringRef, ValueTy > > List)
Inserts elements from initializer list ilist.
bool insert(MapEntryTy *KeyValue)
insert - Insert the specified key/value pair into the map.
StringRef - Represent a constant reference to a string, i.e.
CRTP base class for adapting an iterator to a different type.
const StringMapConstIterator< ValueTy > & wrapped() const
CRTP base class which implements the entire standard iterator facade in terms of a minimal subset of ...
A range adaptor for a pair of iterators.
This is an optimization pass for GlobalISel generic memory operations.
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
auto count(R &&Range, const E &Element)
Wrapper function around std::count to count the number of times an element Element occurs in the give...
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 ...