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;
92 static_cast<uintptr_t
>(-1)
124template <
typename ValueTy,
typename AllocatorTy = MallocAllocator>
145 StringMap(std::initializer_list<std::pair<StringRef, ValueTy>> List)
161 init(
RHS.NumBuckets);
162 unsigned *HashTable = (
unsigned *)(TheTable + NumBuckets + 1),
163 *RHSHashTable = (
unsigned *)(
RHS.TheTable + NumBuckets + 1);
165 NumItems =
RHS.NumItems;
166 NumTombstones =
RHS.NumTombstones;
167 for (
unsigned I = 0,
E = NumBuckets;
I !=
E; ++
I) {
169 if (!Bucket || Bucket == getTombstoneVal()) {
170 TheTable[
I] = Bucket;
174 TheTable[
I] = MapEntryTy::create(
175 static_cast<MapEntryTy *
>(Bucket)->getKey(), getAllocator(),
176 static_cast<MapEntryTy *
>(Bucket)->getValue());
177 HashTable[
I] = RHSHashTable[
I];
189 StringMapImpl::swap(
RHS);
199 for (
unsigned I = 0,
E = NumBuckets;
I !=
E; ++
I) {
201 if (Bucket && Bucket != getTombstoneVal()) {
202 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 (!(KeyValue.getValue() == FindInRHS->getValue()))
307 unsigned BucketNo = LookupBucketFor(KeyValue->
getKey());
309 if (Bucket && Bucket != getTombstoneVal())
312 if (Bucket == getTombstoneVal())
316 assert(NumItems + NumTombstones <= NumBuckets);
326 std::pair<iterator, bool>
insert(std::pair<StringRef, ValueTy> KV) {
327 return try_emplace_with_hash(KV.first, hash(KV.first),
328 std::move(KV.second));
331 std::pair<iterator, bool>
insert(std::pair<StringRef, ValueTy> KV,
333 return try_emplace_with_hash(KV.first, FullHashValue, std::move(KV.second));
339 template <
typename InputIt>
void insert(InputIt First, InputIt Last) {
340 for (InputIt It = First; It !=
Last; ++It)
347 void insert(std::initializer_list<std::pair<StringRef, ValueTy>> List) {
353 template <
typename V>
355 auto Ret = try_emplace(Key, std::forward<V>(Val));
357 Ret.first->second = std::forward<V>(Val);
365 template <
typename... ArgsTy>
367 return try_emplace_with_hash(Key, hash(Key), std::forward<ArgsTy>(Args)...);
370 template <
typename... ArgsTy>
374 unsigned BucketNo = LookupBucketFor(Key, FullHashValue);
376 if (Bucket && Bucket != getTombstoneVal())
377 return std::make_pair(
iterator(TheTable + BucketNo,
false),
380 if (Bucket == getTombstoneVal())
383 MapEntryTy::create(Key, getAllocator(), std::forward<ArgsTy>(Args)...);
385 assert(NumItems + NumTombstones <= NumBuckets);
387 BucketNo = RehashTable(BucketNo);
388 return std::make_pair(
iterator(TheTable + BucketNo,
false),
true);
398 for (
unsigned I = 0,
E = NumBuckets;
I !=
E; ++
I) {
400 if (Bucket && Bucket != getTombstoneVal()) {
401 static_cast<MapEntryTy *
>(Bucket)->Destroy(getAllocator());
417 V.Destroy(getAllocator());
429template <
typename DerivedTy,
typename ValueTy>
440 bool NoAdvance =
false)
443 AdvancePastEmptyBuckets();
448 return static_cast<DerivedTy &
>(*this);
452 return LHS.Ptr ==
RHS.Ptr;
457 AdvancePastEmptyBuckets();
458 return static_cast<DerivedTy &
>(*this);
468 void AdvancePastEmptyBuckets() {
474template <
typename ValueTy>
477 const StringMapEntry<ValueTy>> {
484 bool NoAdvance =
false)
485 :
base(Bucket, NoAdvance) {}
492template <
typename ValueTy>
494 StringMapEntry<ValueTy>> {
501 bool NoAdvance =
false)
502 :
base(Bucket, NoAdvance) {}
513template <
typename ValueTy>
516 StringMapConstIterator<ValueTy>,
517 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 ...