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>
137 StringMapEntry(StringMapEntry &E) =
delete;
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();
163 size_t AllocSize =
sizeof(StringMapEntry) + KeyLength + 1;
165 StringMapEntry *NewItem =
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;
179 static StringMapEntry *Create(
StringRef Key) {
180 return Create(Key, ValueTy());
187 return *
reinterpret_cast<StringMapEntry*
>(Ptr);
194 this->~StringMapEntry();
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;
244 TheTable[I] = MapEntryTy::Create(
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);
305 int Bucket = FindKey(Key);
306 if (Bucket == -1)
return end();
307 return iterator(TheTable+Bucket,
true);
311 int Bucket = FindKey(Key);
312 if (Bucket == -1)
return end();
331 return find(Key) == end() ? 0 : 1;
338 unsigned BucketNo = LookupBucketFor(KeyValue->getKey());
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>
373 unsigned BucketNo = LookupBucketFor(Key);
375 if (Bucket && Bucket != getTombstoneVal())
376 return std::make_pair(
iterator(TheTable + BucketNo,
false),
379 if (Bucket == getTombstoneVal())
381 Bucket = MapEntryTy::Create(Key, std::forward<ArgsTy>(Args)...);
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()) {
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>
507 StringMapEntry<ValueTy>> {
512 using value_type = StringMapEntry<ValueTy>;
516 bool NoAdvance =
false)
517 : base(Bucket, NoAdvance) {}
519 value_type &operator*()
const {
520 return *
static_cast<value_type *
>(*this->Ptr);
528 template <
typename ValueTy>
531 StringMapConstIterator<ValueTy>,
532 std::forward_iterator_tag, StringRef> {
540 : base(std::move(Iter)) {}
542 StringRef &operator*() {
543 Key = this->wrapped()->getKey();
551 template <
typename ValueTy>
554 if (&lhs == &rhs)
return true;
557 if (lhs.size() != rhs.size())
return false;
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(),
567 return a->getKey() < b->getKey();
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(),
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>
593 return !(lhs == rhs);
596 template <
typename ValueTy>
599 if (&lhs == &rhs)
return false;
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());
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,
624 template <
typename ValueTy>
627 return !(lhs <= rhs);
630 template <
typename ValueTy>
638 #endif // LLVM_ADT_STRINGMAP_H const char * getKeyData() const
getKeyData - Return the start of the string data that is the key for this value.
Definition: StringMap.h:151
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:868
Definition: StringMap.h:35
void * CheckedMalloc(size_t size)
Wrapper around std::malloc that calls std::terminate on out of memory.
Definition: memory.cpp:25
Definition: StringMap.h:428
This provides a very simple, boring adaptor for a begin and end iterator into a range type...
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: json_binary_writer.cpp:39
friend const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:170
CRTP base class for adapting an iterator to a different type.
Definition: iterator.h:208
CRTP base class which implements the entire standard iterator facade in terms of a minimal subset of ...
Definition: iterator.h:68
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
StringMapImpl - This is the base class of StringMap that is shared among all of its instantiations...
Definition: StringMap.h:52
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...
Definition: STLExtras.h:896
StringMapEntry - This is used to represent one value that is inserted into a StringMap.
Definition: StringMap.h:38
Definition: StringMap.h:37
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
static StringMapEntry & GetStringMapEntryFromKeyData(const char *KeyData)
GetStringMapEntryFromKeyData - Given key data that is known to be embedded into a StringMapEntry...
Definition: StringMap.h:185
Definition: StringMap.h:36
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.
Definition: STLExtras.h:999
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
LLVM_NODISCARD LLVM_ATTRIBUTE_ALWAYS_INLINE size_t size() const noexcept
size - Get the string size.
Definition: StringRef.h:138
static StringMapEntry * Create(StringRef Key, InitTy &&...InitVals)
Create a StringMapEntry for the specified key construct the value using InitiVals.
Definition: StringMap.h:158
void Destroy()
Destroy - Destroy this StringMapEntry, releasing memory back to the specified allocator.
Definition: StringMap.h:192
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
bool operator==(json::const_reference lhs, json::const_reference rhs) noexcept
Definition: json.cpp:921
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