14 #ifndef WPIUTIL_WPI_STRINGMAP_H
15 #define WPIUTIL_WPI_STRINGMAP_H
17 #include "wpi/SmallVector.h"
18 #include "wpi/StringRef.h"
19 #include "wpi/iterator.h"
21 #include "wpi/PointerLikeTypeTraits.h"
22 #include "wpi/deprecated.h"
23 #include "wpi/memory.h"
29 #include <initializer_list>
47 size_t getKeyLength()
const {
return StrLen; }
58 unsigned NumBuckets = 0;
59 unsigned NumItems = 0;
60 unsigned NumTombstones = 0;
65 : ItemSize(itemSize) {}
67 : TheTable(RHS.TheTable), NumBuckets(RHS.NumBuckets),
68 NumItems(RHS.NumItems), NumTombstones(RHS.NumTombstones),
69 ItemSize(RHS.ItemSize) {
70 RHS.TheTable =
nullptr;
73 RHS.NumTombstones = 0;
77 unsigned RehashTable(
unsigned BucketNo = 0);
101 void init(
unsigned Size);
105 uintptr_t Val =
static_cast<uintptr_t
>(-1);
106 Val <<= PointerLikeTypeTraits<StringMapEntryBase *>::NumLowBitsAvailable;
110 unsigned getNumBuckets()
const {
return NumBuckets; }
111 unsigned getNumItems()
const {
return NumItems; }
113 bool empty()
const {
return NumItems == 0; }
114 unsigned size()
const {
return NumItems; }
117 std::swap(TheTable, Other.TheTable);
118 std::swap(NumBuckets, Other.NumBuckets);
119 std::swap(NumItems, Other.NumItems);
120 std::swap(NumTombstones, Other.NumTombstones);
127 template<
typename ValueTy>
134 template <
typename... InitTy>
135 StringMapEntry(
size_t strLen, InitTy &&... InitVals)
136 : StringMapEntryBase(strLen), second(
std::forward<InitTy>(InitVals)...) {}
137 StringMapEntry(StringMapEntry &E) =
delete;
139 StringRef getKey()
const {
140 return StringRef(
getKeyData(), getKeyLength());
143 const ValueTy &getValue()
const {
return second; }
144 ValueTy &getValue() {
return second; }
146 void setValue(
const ValueTy &V) { second = V; }
151 const char *
getKeyData()
const {
return reinterpret_cast<const char*
>(
this+1);}
157 template <
typename... InitTy>
159 size_t KeyLength = Key.
size();
169 new (NewItem)
StringMapEntry(KeyLength, std::forward<InitTy>(InitVals)...);
172 char *StrBuffer =
const_cast<char*
>(NewItem->
getKeyData());
174 memcpy(StrBuffer, Key.
data(), KeyLength);
175 StrBuffer[KeyLength] = 0;
180 return Create(Key, ValueTy());
195 std::free(static_cast<void *>(
this));
204 template<
typename ValueTy>
214 StringMap(std::initializer_list<std::pair<StringRef, ValueTy>> List)
216 for (
const auto &P : List) {
231 init(RHS.NumBuckets);
232 unsigned *HashTable = (
unsigned *)(TheTable + NumBuckets + 1),
233 *RHSHashTable = (
unsigned *)(RHS.TheTable + NumBuckets + 1);
235 NumItems = RHS.NumItems;
236 NumTombstones = RHS.NumTombstones;
237 for (
unsigned I = 0, E = NumBuckets; I != E; ++I) {
239 if (!Bucket || Bucket == getTombstoneVal()) {
240 TheTable[I] = Bucket;
245 static_cast<MapEntryTy *>(Bucket)->getKey(),
246 static_cast<MapEntryTy *>(Bucket)->getValue());
247 HashTable[I] = RHSHashTable[I];
259 StringMapImpl::swap(RHS);
268 for (
unsigned I = 0, E = NumBuckets; I != E; ++I) {
270 if (Bucket && Bucket != getTombstoneVal()) {
278 using key_type =
const char*;
279 using mapped_type = ValueTy;
281 using size_type = size_t;
287 return iterator(TheTable, NumBuckets == 0);
290 return iterator(TheTable+NumBuckets,
true);
306 if (Bucket == -1)
return end();
307 return iterator(TheTable+Bucket,
true);
312 if (Bucket == -1)
return end();
331 return find(Key) == end() ? 0 : 1;
340 if (Bucket && Bucket != getTombstoneVal())
343 if (Bucket == getTombstoneVal())
347 assert(NumItems + NumTombstones <= NumBuckets);
357 std::pair<iterator, bool>
insert(std::pair<StringRef, ValueTy> KV) {
358 return try_emplace(KV.first, std::move(KV.second));
361 template <
typename... ArgsTy>
362 WPI_DEPRECATED(
"use try_emplace instead")
363 std::pair<iterator,
bool> emplace_second(
StringRef Key, ArgsTy &&... Args) {
364 return try_emplace(Key, std::forward<ArgsTy>(Args)...);
371 template <
typename... ArgsTy>
375 if (Bucket && Bucket != getTombstoneVal())
376 return std::make_pair(iterator(TheTable + BucketNo,
false),
379 if (Bucket == getTombstoneVal())
383 assert(NumItems + NumTombstones <= NumBuckets);
385 BucketNo = RehashTable(BucketNo);
386 return std::make_pair(iterator(TheTable + BucketNo,
false),
true);
395 for (
unsigned I = 0, E = NumBuckets; I != E; ++I) {
397 if (Bucket && Bucket != getTombstoneVal()) {
398 static_cast<MapEntryTy*
>(Bucket)->Destroy();
413 void erase(iterator I) {
419 bool erase(StringRef Key) {
420 iterator I = find(Key);
421 if (I == end())
return false;
427 template <
typename DerivedTy,
typename ValueTy>
438 bool NoAdvance =
false)
440 if (!NoAdvance) AdvancePastEmptyBuckets();
443 DerivedTy &operator=(
const DerivedTy &Other) {
445 return static_cast<DerivedTy &
>(*this);
448 bool operator==(
const DerivedTy &RHS)
const {
return Ptr == RHS.Ptr; }
450 DerivedTy &operator++() {
452 AdvancePastEmptyBuckets();
453 return static_cast<DerivedTy &
>(*this);
456 DerivedTy operator++(
int) {
462 DerivedTy &operator--() {
464 ReversePastEmptyBuckets();
465 return static_cast<DerivedTy &
>(*this);
468 DerivedTy operator--(
int) {
475 void AdvancePastEmptyBuckets() {
476 while (*Ptr ==
nullptr || *Ptr == StringMapImpl::getTombstoneVal())
479 void ReversePastEmptyBuckets() {
480 while (*Ptr ==
nullptr || *Ptr == StringMapImpl::getTombstoneVal())
485 template <
typename ValueTy>
488 const StringMapEntry<ValueTy>> {
493 using value_type =
const StringMapEntry<ValueTy>;
497 bool NoAdvance =
false)
498 : base(Bucket, NoAdvance) {}
500 value_type &operator*()
const {
501 return *
static_cast<value_type *
>(*this->Ptr);
505 template <
typename ValueTy>
506 class StringMapIterator :
public StringMapIterBase<StringMapIterator<ValueTy>,
507 StringMapEntry<ValueTy>> {
509 StringMapIterBase<StringMapIterator<ValueTy>, StringMapEntry<ValueTy>>;
512 using value_type = StringMapEntry<ValueTy>;
514 StringMapIterator() =
default;
515 explicit StringMapIterator(StringMapEntryBase **Bucket,
516 bool NoAdvance =
false)
517 : base(Bucket, NoAdvance) {}
519 value_type &operator*()
const {
520 return *
static_cast<value_type *
>(*this->Ptr);
523 operator StringMapConstIterator<ValueTy>()
const {
524 return StringMapConstIterator<ValueTy>(this->Ptr,
true);
528 template <
typename ValueTy>
529 class StringMapKeyIterator
530 :
public iterator_adaptor_base<StringMapKeyIterator<ValueTy>,
531 StringMapConstIterator<ValueTy>,
532 std::forward_iterator_tag, StringRef> {
533 using base = iterator_adaptor_base<StringMapKeyIterator<ValueTy>,
534 StringMapConstIterator<ValueTy>,
535 std::forward_iterator_tag, StringRef>;
538 StringMapKeyIterator() =
default;
539 explicit StringMapKeyIterator(StringMapConstIterator<ValueTy> Iter)
540 : base(
std::move(Iter)) {}
542 StringRef &operator*() {
543 Key = this->wrapped()->getKey();
551 template <
typename ValueTy>
552 bool operator==(
const StringMap<ValueTy>& lhs,
const StringMap<ValueTy>& rhs) {
554 if (&lhs == &rhs)
return true;
557 if (lhs.size() != rhs.size())
return false;
560 SmallVector<StringMapConstIterator<ValueTy>, 16> lhs_items;
561 lhs_items.reserve(lhs.size());
562 for (
auto i = lhs.begin(), end = lhs.
end(); i != end; ++i)
563 lhs_items.push_back(i);
564 std::sort(lhs_items.begin(), lhs_items.end(),
565 [](
const StringMapConstIterator<ValueTy>& a,
566 const StringMapConstIterator<ValueTy>& b) {
567 return a->getKey() < b->getKey();
570 SmallVector<StringMapConstIterator<ValueTy>, 16> rhs_items;
571 rhs_items.reserve(rhs.size());
572 for (
auto i = rhs.begin(), end = rhs.
end(); i != end; ++i)
573 rhs_items.push_back(i);
574 std::sort(rhs_items.begin(), rhs_items.end(),
575 [](
const StringMapConstIterator<ValueTy>& a,
576 const StringMapConstIterator<ValueTy>& b) {
577 return a->getKey() < b->getKey();
581 for (
auto a = lhs_items.begin(), b = rhs_items.begin(),
582 aend = lhs_items.end(), bend = rhs_items.end();
583 a != aend && b != bend; ++a, ++b) {
584 if ((*a)->first() != (*b)->first() || (*a)->second != (*b)->second)
590 template <
typename ValueTy>
591 inline bool operator!=(
const StringMap<ValueTy>& lhs,
592 const StringMap<ValueTy>& rhs) {
593 return !(lhs == rhs);
596 template <
typename ValueTy>
597 bool operator<(const StringMap<ValueTy>& lhs,
const StringMap<ValueTy>& rhs) {
599 if (&lhs == &rhs)
return false;
602 SmallVector<StringRef, 16> lhs_keys;
603 lhs_keys.reserve(lhs.size());
604 for (
auto i = lhs.begin(), end = lhs.
end(); i != end; ++i)
605 lhs_keys.push_back(i->getKey());
606 std::sort(lhs_keys.begin(), lhs_keys.end());
608 SmallVector<StringRef, 16> rhs_keys;
609 rhs_keys.reserve(rhs.size());
610 for (
auto i = rhs.begin(), end = rhs.
end(); i != end; ++i)
611 rhs_keys.push_back(i->getKey());
612 std::sort(rhs_keys.begin(), rhs_keys.end());
615 return lhs_keys < rhs_keys;
618 template <
typename ValueTy>
619 inline bool operator<=(const StringMap<ValueTy>& lhs,
620 const StringMap<ValueTy>& rhs) {
624 template <
typename ValueTy>
625 inline bool operator>(
const StringMap<ValueTy>& lhs,
626 const StringMap<ValueTy>& rhs) {
627 return !(lhs <= rhs);
630 template <
typename ValueTy>
631 inline bool operator>=(
const StringMap<ValueTy>& lhs,
632 const StringMap<ValueTy>& rhs) {
638 #endif // LLVM_ADT_STRINGMAP_H
static StringMapEntry * Create(StringRef Key, InitTy &&...InitVals)
Create a StringMapEntry for the specified key construct the value using InitiVals.
Definition: StringMap.h:158
void init(unsigned Size)
Allocate the table with the specified number of buckets and otherwise setup the map as empty...
Definition: StringMap.h:35
void Destroy()
Destroy - Destroy this StringMapEntry, releasing memory back to the specified allocator.
Definition: StringMap.h:192
Definition: StringMap.h:428
This provides a very simple, boring adaptor for a begin and end iterator into a range type...
Definition: SmallVector.h:946
StringMapEntryBase - Shared base class of StringMapEntry instances.
Definition: StringMap.h:41
LLVM_NODISCARD LLVM_ATTRIBUTE_ALWAYS_INLINE const char * data() const noexcept
data - Get a pointer to the start of the string (which may not be null terminated).
Definition: StringRef.h:128
namespace to hold default to_json function
Definition: SmallString.h:21
friend const_iterator end(StringRef path)
Get end iterator over path.
CRTP base class which implements the entire standard iterator facade in terms of a minimal subset of ...
Definition: iterator.h:68
unsigned LookupBucketFor(StringRef Key)
LookupBucketFor - Look up the bucket that the specified string should end up in.
Definition: StringMap.h:37
static StringMapEntry & GetStringMapEntryFromKeyData(const char *KeyData)
GetStringMapEntryFromKeyData - Given key data that is known to be embedded into a StringMapEntry...
Definition: StringMap.h:185
A range adaptor for a pair of iterators.
Definition: iterator_range.h:32
size_type count(StringRef Key) const
count - Return 1 if the element is in the map, 0 otherwise.
Definition: StringMap.h:330
void RemoveKey(StringMapEntryBase *V)
RemoveKey - Remove the specified StringMapEntry from the table, but do not delete it...
StringMapImpl - This is the base class of StringMap that is shared among all of its instantiations...
Definition: StringMap.h:52
StringMapEntry - This is used to represent one value that is inserted into a StringMap.
Definition: StringMap.h:38
void * CheckedMalloc(size_t size)
Wrapper around std::malloc that calls std::terminate on out of memory.
Definition: StringMap.h:36
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:54
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:327
const char * getKeyData() const
getKeyData - Return the start of the string data that is the key for this value.
Definition: StringMap.h:151
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
int FindKey(StringRef Key) const
FindKey - Look up the bucket that contains the specified key.
LLVM_NODISCARD LLVM_ATTRIBUTE_ALWAYS_INLINE size_t size() const noexcept
size - Get the string size.
Definition: StringRef.h:138
StringMap - This is an unconventional map that is specialized for handling keys that are "strings"...
Definition: StringMap.h:205
bool insert(MapEntryTy *KeyValue)
insert - Insert the specified key/value pair into the map.
Definition: StringMap.h:337
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...
Definition: StringMap.h:372
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:357
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:318