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;
84 static_cast<uintptr_t
>(-1)
109template <
typename ValueTy,
typename AllocatorTy = MallocAllocator>
130 StringMap(std::initializer_list<std::pair<StringRef, ValueTy>> List)
146 init(
RHS.NumBuckets);
147 unsigned *HashTable = (
unsigned *)(TheTable + NumBuckets + 1),
148 *RHSHashTable = (
unsigned *)(
RHS.TheTable + NumBuckets + 1);
150 NumItems =
RHS.NumItems;
151 NumTombstones =
RHS.NumTombstones;
152 for (
unsigned I = 0,
E = NumBuckets;
I !=
E; ++
I) {
154 if (!Bucket || Bucket == getTombstoneVal()) {
155 TheTable[
I] = Bucket;
159 TheTable[
I] = MapEntryTy::create(
160 static_cast<MapEntryTy *
>(Bucket)->getKey(), getAllocator(),
161 static_cast<MapEntryTy *
>(Bucket)->getValue());
162 HashTable[
I] = RHSHashTable[
I];
174 StringMapImpl::swap(
RHS);
184 for (
unsigned I = 0,
E = NumBuckets;
I !=
E; ++
I) {
186 if (Bucket && Bucket != getTombstoneVal()) {
187 static_cast<MapEntryTy *
>(Bucket)->Destroy(getAllocator());
194 using AllocTy::getAllocator;
219 int Bucket = FindKey(Key);
222 return iterator(TheTable + Bucket,
true);
226 int Bucket = FindKey(Key);
244 auto Iter = this->
find(std::move(Val));
245 assert(Iter != this->end() &&
"StringMap::at failed due to a missing key");
259 template <
typename InputTy>
269 for (
const auto &KeyValue : *
this) {
270 auto FindInRHS =
RHS.find(KeyValue.getKey());
272 if (FindInRHS ==
RHS.end())
275 if (!(KeyValue.getValue() == FindInRHS->getValue()))
288 unsigned BucketNo = LookupBucketFor(KeyValue->
getKey());
290 if (Bucket && Bucket != getTombstoneVal())
293 if (Bucket == getTombstoneVal())
297 assert(NumItems + NumTombstones <= NumBuckets);
307 std::pair<iterator, bool>
insert(std::pair<StringRef, ValueTy> KV) {
308 return try_emplace(KV.first, std::move(KV.second));
314 template <
typename InputIt>
void insert(InputIt First, InputIt Last) {
315 for (InputIt It = First; It !=
Last; ++It)
322 void insert(std::initializer_list<std::pair<StringRef, ValueTy>> List) {
328 template <
typename V>
330 auto Ret = try_emplace(Key, std::forward<V>(Val));
332 Ret.first->second = std::forward<V>(Val);
340 template <
typename... ArgsTy>
342 unsigned BucketNo = LookupBucketFor(Key);
344 if (Bucket && Bucket != getTombstoneVal())
345 return std::make_pair(
iterator(TheTable + BucketNo,
false),
348 if (Bucket == getTombstoneVal())
351 MapEntryTy::create(Key, getAllocator(), std::forward<ArgsTy>(Args)...);
353 assert(NumItems + NumTombstones <= NumBuckets);
355 BucketNo = RehashTable(BucketNo);
356 return std::make_pair(
iterator(TheTable + BucketNo,
false),
true);
366 for (
unsigned I = 0,
E = NumBuckets;
I !=
E; ++
I) {
368 if (Bucket && Bucket != getTombstoneVal()) {
369 static_cast<MapEntryTy *
>(Bucket)->Destroy(getAllocator());
385 V.Destroy(getAllocator());
397template <
typename DerivedTy,
typename ValueTy>
408 bool NoAdvance =
false)
411 AdvancePastEmptyBuckets();
416 return static_cast<DerivedTy &
>(*this);
420 return LHS.Ptr ==
RHS.Ptr;
425 AdvancePastEmptyBuckets();
426 return static_cast<DerivedTy &
>(*this);
436 void AdvancePastEmptyBuckets() {
442template <
typename ValueTy>
445 const StringMapEntry<ValueTy>> {
452 bool NoAdvance =
false)
453 :
base(Bucket, NoAdvance) {}
460template <
typename ValueTy>
462 StringMapEntry<ValueTy>> {
469 bool NoAdvance =
false)
470 :
base(Bucket, NoAdvance) {}
481template <
typename ValueTy>
484 StringMapConstIterator<ValueTy>,
485 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")
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()
int FindKey(StringRef Key) const
FindKey - Look up the bucket that contains the specified key.
unsigned RehashTable(unsigned BucketNo=0)
RehashTable - Grow the table, redistributing values into the buckets with the appropriate mod-of-hash...
unsigned LookupBucketFor(StringRef Key)
LookupBucketFor - Look up the bucket that the specified string should end up in.
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.
unsigned getNumItems() const
static constexpr uintptr_t TombstoneIntVal
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.
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 begin() const
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.
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 ...