13 #ifndef LLVM_ADT_STRINGMAP_H 14 #define LLVM_ADT_STRINGMAP_H 27 #include <initializer_list> 55 unsigned NumBuckets = 0;
56 unsigned NumItems = 0;
57 unsigned NumTombstones = 0;
62 : ItemSize(itemSize) {}
64 : TheTable(RHS.TheTable), NumBuckets(RHS.NumBuckets),
65 NumItems(RHS.NumItems), NumTombstones(RHS.NumTombstones),
66 ItemSize(RHS.ItemSize) {
67 RHS.TheTable =
nullptr;
70 RHS.NumTombstones = 0;
74 unsigned RehashTable(
unsigned BucketNo = 0);
102 uintptr_t Val =
static_cast<uintptr_t
>(-1);
103 Val <<= PointerLikeTypeTraits<StringMapEntryBase *>::NumLowBitsAvailable;
110 bool empty()
const {
return NumItems == 0; }
111 unsigned size()
const {
return NumItems; }
126 template<
typename ValueTy>
133 template <
typename... InitTy>
157 template<
typename ValueTy>
169 const char *
getKeyData()
const {
return reinterpret_cast<const char*
>(
this+1);}
177 template <
typename AllocatorTy,
typename... InitTy>
179 InitTy &&... InitVals) {
180 size_t KeyLength = Key.
size();
188 static_cast<StringMapEntry*
>(Allocator.Allocate(AllocSize,Alignment));
189 assert(NewItem &&
"Unhandled out-of-memory");
192 new (NewItem)
StringMapEntry(KeyLength, std::forward<InitTy>(InitVals)...);
195 char *StrBuffer =
const_cast<char*
>(NewItem->
getKeyData());
197 memcpy(StrBuffer, Key.
data(), KeyLength);
198 StrBuffer[KeyLength] = 0;
203 template <
typename... InitType>
206 return Create(Key, A, std::forward<InitType>(InitVal)...);
210 return Create(Key, ValueTy());
222 template<
typename AllocatorTy>
227 Allocator.Deallocate(static_cast<void *>(
this), AllocSize);
241 template<
typename ValueTy,
typename AllocatorTy = MallocAllocator>
262 for (
const auto &
P :
List) {
272 Allocator(RHS.Allocator) {
279 unsigned *HashTable = (
unsigned *)(TheTable + NumBuckets + 1),
280 *RHSHashTable = (
unsigned *)(RHS.
TheTable + NumBuckets + 1);
284 for (
unsigned I = 0,
E = NumBuckets;
I !=
E; ++
I) {
286 if (!Bucket || Bucket == getTombstoneVal()) {
287 TheTable[
I] = Bucket;
291 TheTable[
I] = MapEntryTy::Create(
292 static_cast<MapEntryTy *>(Bucket)->getKey(), Allocator,
293 static_cast<MapEntryTy *>(Bucket)->getValue());
294 HashTable[
I] = RHSHashTable[
I];
316 for (
unsigned I = 0,
E = NumBuckets;
I !=
E; ++
I) {
318 if (Bucket && Bucket != getTombstoneVal()) {
319 static_cast<MapEntryTy*
>(Bucket)->Destroy(Allocator);
338 return iterator(TheTable, NumBuckets == 0);
341 return iterator(TheTable+NumBuckets,
true);
356 int Bucket = FindKey(Key);
357 if (Bucket == -1)
return end();
358 return iterator(TheTable+Bucket,
true);
362 int Bucket = FindKey(Key);
363 if (Bucket == -1)
return end();
382 return find(Key) ==
end() ? 0 : 1;
385 template <
typename InputTy>
394 unsigned BucketNo = LookupBucketFor(KeyValue->
getKey());
396 if (Bucket && Bucket != getTombstoneVal())
399 if (Bucket == getTombstoneVal())
403 assert(NumItems + NumTombstones <= NumBuckets);
413 std::pair<iterator, bool>
insert(std::pair<StringRef, ValueTy> KV) {
414 return try_emplace(KV.first, std::move(KV.second));
419 template <
typename V>
421 auto Ret = try_emplace(Key, std::forward<V>(Val));
423 Ret.first->second = std::forward<V>(Val);
431 template <
typename... ArgsTy>
433 unsigned BucketNo = LookupBucketFor(Key);
435 if (Bucket && Bucket != getTombstoneVal())
436 return std::make_pair(
iterator(TheTable + BucketNo,
false),
439 if (Bucket == getTombstoneVal())
441 Bucket = MapEntryTy::Create(Key, Allocator, std::forward<ArgsTy>(
Args)...);
443 assert(NumItems + NumTombstones <= NumBuckets);
445 BucketNo = RehashTable(BucketNo);
446 return std::make_pair(
iterator(TheTable + BucketNo,
false),
true);
455 for (
unsigned I = 0,
E = NumBuckets;
I !=
E; ++
I) {
457 if (Bucket && Bucket != getTombstoneVal()) {
458 static_cast<MapEntryTy*
>(Bucket)->Destroy(Allocator);
481 if (I ==
end())
return false;
487 template <
typename DerivedTy,
typename ValueTy>
498 bool NoAdvance =
false)
500 if (!NoAdvance) AdvancePastEmptyBuckets();
505 return static_cast<DerivedTy &
>(*this);
508 bool operator==(
const DerivedTy &RHS)
const {
return Ptr == RHS.Ptr; }
512 AdvancePastEmptyBuckets();
513 return static_cast<DerivedTy &
>(*this);
523 void AdvancePastEmptyBuckets() {
529 template <
typename ValueTy>
532 const StringMapEntry<ValueTy>> {
539 bool NoAdvance =
false)
540 :
base(Bucket, NoAdvance) {}
543 return *
static_cast<const StringMapEntry<ValueTy> *
>(*this->Ptr);
547 template <
typename ValueTy>
549 StringMapEntry<ValueTy>> {
556 bool NoAdvance =
false)
557 :
base(Bucket, NoAdvance) {}
560 return *
static_cast<StringMapEntry<ValueTy> *
>(*this->Ptr);
568 template <
typename ValueTy>
571 StringMapConstIterator<ValueTy>,
572 std::forward_iterator_tag, StringRef> {
583 Key = this->wrapped()->getKey();
593 #endif // LLVM_ADT_STRINGMAP_H
StringMapEntryStorage(size_t strLen)
const_iterator end(StringRef path)
Get end iterator over path.
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_range< StringMapKeyIterator< ValueTy > > keys() const
StringMapImpl(unsigned itemSize)
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
This class represents lattice values for constants.
StringMapEntry - This is used to represent one value that is inserted into a StringMap.
NoneType
A simple null object to allow implicit construction of Optional<T> and similar types without having t...
This provides a very simple, boring adaptor for a begin and end iterator into a range type...
iterator find(StringRef Key)
const_iterator end() const
This file defines the MallocAllocator and BumpPtrAllocator interfaces.
StringMap(const StringMap &RHS)
const_iterator find(StringRef Key) const
StringMapKeyIterator(StringMapConstIterator< ValueTy > Iter)
StringMap & operator=(StringMap RHS)
static StringMapEntry & GetStringMapEntryFromKeyData(const char *KeyData)
GetStringMapEntryFromKeyData - Given key data that is known to be embedded into a StringMapEntry...
StringMapIterator(StringMapEntryBase **Bucket, bool NoAdvance=false)
static StringMapEntry * Create(StringRef Key, AllocatorTy &Allocator, InitTy &&... InitVals)
Create a StringMapEntry for the specified key construct the value using InitiVals.
StringMapImpl - This is the base class of StringMap that is shared among all of its instantiations...
StringMapEntry< ValueTy > & operator*() const
void Destroy(AllocatorTy &Allocator)
Destroy - Destroy this StringMapEntry, releasing memory back to the specified allocator.
StringMapIterBase(StringMapEntryBase **Bucket, bool NoAdvance=false)
LLVM_NODISCARD size_t size() const
size - Get the string size.
void swap(StringMapImpl &Other)
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...
void setValue(const ValueTy &V)
CRTP base class which implements the entire standard iterator facade in terms of a minimal subset of ...
StringMap(StringMap &&RHS)
StringMapEntryStorage(size_t strLen, InitTy &&... InitVals)
auto count(R &&Range, const E &Element) -> typename std::iterator_traits< decltype(adl_begin(Range))>::difference_type
Wrapper function around std::count to count the number of times an element Element occurs in the give...
NoneType getValue() const
size_type count(const StringMapEntry< InputTy > &MapEntry) const
StringMapEntryBase ** TheTable
initializer< Ty > init(const Ty &Val)
size_type count(StringRef Key) const
count - Return 1 if the element is in the map, 0 otherwise.
CRTP base class for adapting an iterator to a different type.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
const_iterator begin() const
void Destroy()
Destroy this object, releasing memory back to the malloc allocator.
StringMap(unsigned InitialSize)
ValueTy lookup(StringRef Key) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
bool erase(StringRef Key)
constexpr bool empty(const T &RangeOrContainer)
Test whether RangeOrContainer is empty. Similar to C++17 std::empty.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
auto size(R &&Range, typename std::enable_if< std::is_same< typename std::iterator_traits< decltype(Range.begin())>::iterator_category, std::random_access_iterator_tag >::value, void >::type *=nullptr) -> decltype(std::distance(Range.begin(), Range.end()))
Get the size of a range.
StringMapEntryStorage(size_t strLen, NoneType none=None)
StringMapEntryBase(size_t Len)
AllocatorTy & getAllocator()
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...
const AllocatorTy & getAllocator() const
static StringMapEntryBase * getTombstoneVal()
bool insert(MapEntryTy *KeyValue)
insert - Insert the specified key/value pair into the map.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
A range adaptor for a pair of iterators.
StringMap - This is an unconventional map that is specialized for handling keys that are "strings"...
StringMap(unsigned InitialSize, AllocatorTy A)
bool operator==(const DerivedTy &RHS) const
unsigned getNumBuckets() const
StringMapConstIterator(StringMapEntryBase **Bucket, bool NoAdvance=false)
size_t getKeyLength() const
DerivedTy & operator=(const DerivedTy &Other)
const char * getKeyData() const
getKeyData - Return the start of the string data that is the key for this value.
static StringMapEntry * Create(StringRef Key, InitType &&... InitVal)
Create - Create a StringMapEntry with normal malloc/free.
static StringMapEntry * Create(StringRef Key)
DerivedTy operator++(int)
LLVM_NODISCARD const char * data() const
data - Get a pointer to the start of the string (which may not be null terminated).
StringMap(std::initializer_list< std::pair< StringRef, ValueTy >> List)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
StringMapImpl(StringMapImpl &&RHS)
unsigned getNumItems() const
StringMapEntryBase - Shared base class of StringMapEntry instances.
const ValueTy & getValue() const
StringRef - Represent a constant reference to a string, i.e.
ValueTy & operator[](StringRef Key)
Lookup the ValueTy for the Key, or create a default constructed value if the key is not in the map...
const StringMapEntry< ValueTy > & operator*() const
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
StringMapEntryStorage - Holds the value in a StringMapEntry.