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"
22 #include "wpi/PointerLikeTypeTraits.h"
23 #include "wpi/ErrorHandling.h"
24 #include "wpi/deprecated.h"
30 #include <initializer_list>
48 size_t getKeyLength()
const {
return StrLen; }
59 unsigned NumBuckets = 0;
60 unsigned NumItems = 0;
61 unsigned NumTombstones = 0;
66 : ItemSize(itemSize) {}
68 : TheTable(RHS.TheTable), NumBuckets(RHS.NumBuckets),
69 NumItems(RHS.NumItems), NumTombstones(RHS.NumTombstones),
70 ItemSize(RHS.ItemSize) {
71 RHS.TheTable =
nullptr;
74 RHS.NumTombstones = 0;
78 unsigned RehashTable(
unsigned BucketNo = 0);
102 void init(
unsigned Size);
106 uintptr_t Val = static_cast<uintptr_t>(-1);
107 Val <<= PointerLikeTypeTraits<StringMapEntryBase *>::NumLowBitsAvailable;
108 return reinterpret_cast<StringMapEntryBase *>(Val);
111 unsigned getNumBuckets()
const {
return NumBuckets; }
112 unsigned getNumItems()
const {
return NumItems; }
114 bool empty()
const {
return NumItems == 0; }
115 unsigned size()
const {
return NumItems; }
118 std::swap(TheTable, Other.TheTable);
119 std::swap(NumBuckets, Other.NumBuckets);
120 std::swap(NumItems, Other.NumItems);
121 std::swap(NumTombstones, Other.NumTombstones);
128 template<
typename ValueTy>
135 template <
typename... InitTy>
136 StringMapEntry(
size_t strLen, InitTy &&... InitVals)
137 : StringMapEntryBase(strLen), second(std::forward<InitTy>(InitVals)...) {}
138 StringMapEntry(StringMapEntry &E) =
delete;
140 StringRef getKey()
const {
141 return StringRef(
getKeyData(), getKeyLength());
144 const ValueTy &getValue()
const {
return second; }
145 ValueTy &getValue() {
return second; }
147 void setValue(
const ValueTy &V) { second = V; }
152 const char *
getKeyData()
const {
return reinterpret_cast<const char*>(
this+1);}
158 template <
typename... InitTy>
160 size_t KeyLength = Key.
size();
167 static_cast<StringMapEntry*>(safe_malloc(AllocSize));
170 new (NewItem)
StringMapEntry(KeyLength, std::forward<InitTy>(InitVals)...);
173 char *StrBuffer = const_cast<char*>(NewItem->
getKeyData());
175 memcpy(StrBuffer, Key.
data(), KeyLength);
176 StrBuffer[KeyLength] = 0;
181 return Create(Key, ValueTy());
188 return *reinterpret_cast<StringMapEntry*>(Ptr);
196 std::free(static_cast<void *>(
this));
205 template<
typename ValueTy>
215 StringMap(std::initializer_list<std::pair<StringRef, ValueTy>> List)
217 for (
const auto &P : List) {
232 init(RHS.NumBuckets);
233 unsigned *HashTable = (
unsigned *)(TheTable + NumBuckets + 1),
234 *RHSHashTable = (
unsigned *)(RHS.TheTable + NumBuckets + 1);
236 NumItems = RHS.NumItems;
237 NumTombstones = RHS.NumTombstones;
238 for (
unsigned I = 0, E = NumBuckets; I != E; ++I) {
240 if (!Bucket || Bucket == getTombstoneVal()) {
241 TheTable[I] = Bucket;
246 static_cast<MapEntryTy *>(Bucket)->getKey(),
247 static_cast<MapEntryTy *>(Bucket)->getValue());
248 HashTable[I] = RHSHashTable[I];
260 StringMapImpl::swap(RHS);
269 for (
unsigned I = 0, E = NumBuckets; I != E; ++I) {
271 if (Bucket && Bucket != getTombstoneVal()) {
272 static_cast<MapEntryTy*>(Bucket)->Destroy();
279 using key_type =
const char*;
280 using mapped_type = ValueTy;
282 using size_type = size_t;
288 return iterator(TheTable, NumBuckets == 0);
291 return iterator(TheTable+NumBuckets,
true);
307 if (Bucket == -1)
return end();
308 return iterator(TheTable+Bucket,
true);
313 if (Bucket == -1)
return end();
332 return find(Key) == end() ? 0 : 1;
341 if (Bucket && Bucket != getTombstoneVal())
344 if (Bucket == getTombstoneVal())
348 assert(NumItems + NumTombstones <= NumBuckets);
358 std::pair<iterator, bool>
insert(std::pair<StringRef, ValueTy> KV) {
359 return try_emplace(KV.first, std::move(KV.second));
366 template <
typename... ArgsTy>
370 if (Bucket && Bucket != getTombstoneVal())
371 return std::make_pair(
iterator(TheTable + BucketNo,
false),
374 if (Bucket == getTombstoneVal())
378 assert(NumItems + NumTombstones <= NumBuckets);
380 BucketNo = RehashTable(BucketNo);
381 return std::make_pair(
iterator(TheTable + BucketNo,
false),
true);
390 for (
unsigned I = 0, E = NumBuckets; I != E; ++I) {
392 if (Bucket && Bucket != getTombstoneVal()) {
393 static_cast<MapEntryTy*>(Bucket)->Destroy();
408 void erase(iterator I) {
414 bool erase(StringRef Key) {
415 iterator I = find(Key);
416 if (I == end())
return false;
422 template <
typename DerivedTy,
typename ValueTy>
433 bool NoAdvance =
false)
435 if (!NoAdvance) AdvancePastEmptyBuckets();
438 DerivedTy &operator=(
const DerivedTy &Other) {
440 return static_cast<DerivedTy &>(*
this);
443 bool operator==(
const DerivedTy &RHS)
const {
return Ptr == RHS.Ptr; }
445 DerivedTy &operator++() {
447 AdvancePastEmptyBuckets();
448 return static_cast<DerivedTy &>(*
this);
451 DerivedTy operator++(
int) {
457 DerivedTy &operator--() {
459 ReversePastEmptyBuckets();
460 return static_cast<DerivedTy &>(*
this);
463 DerivedTy operator--(
int) {
470 void AdvancePastEmptyBuckets() {
471 while (*Ptr ==
nullptr || *Ptr == StringMapImpl::getTombstoneVal())
474 void ReversePastEmptyBuckets() {
475 while (*Ptr ==
nullptr || *Ptr == StringMapImpl::getTombstoneVal())
480 template <
typename ValueTy>
483 const StringMapEntry<ValueTy>> {
492 bool NoAdvance =
false)
493 : base(Bucket, NoAdvance) {}
495 value_type &operator*()
const {
496 return *static_cast<value_type *>(*this->Ptr);
500 template <
typename ValueTy>
501 class StringMapIterator :
public StringMapIterBase<StringMapIterator<ValueTy>,
502 StringMapEntry<ValueTy>> {
504 StringMapIterBase<StringMapIterator<ValueTy>, StringMapEntry<ValueTy>>;
507 using value_type = StringMapEntry<ValueTy>;
509 StringMapIterator() =
default;
510 explicit StringMapIterator(StringMapEntryBase **Bucket,
511 bool NoAdvance =
false)
512 : base(Bucket, NoAdvance) {}
514 value_type &operator*()
const {
515 return *static_cast<value_type *>(*this->Ptr);
518 operator StringMapConstIterator<ValueTy>()
const {
519 return StringMapConstIterator<ValueTy>(this->Ptr,
true);
523 template <
typename ValueTy>
524 class StringMapKeyIterator
525 :
public iterator_adaptor_base<StringMapKeyIterator<ValueTy>,
526 StringMapConstIterator<ValueTy>,
527 std::forward_iterator_tag, StringRef> {
528 using base = iterator_adaptor_base<StringMapKeyIterator<ValueTy>,
529 StringMapConstIterator<ValueTy>,
530 std::forward_iterator_tag, StringRef>;
533 StringMapKeyIterator() =
default;
534 explicit StringMapKeyIterator(StringMapConstIterator<ValueTy> Iter)
535 : base(std::move(Iter)) {}
537 StringRef &operator*() {
538 Key = this->wrapped()->getKey();
546 template <
typename ValueTy>
547 bool operator==(
const StringMap<ValueTy>& lhs,
const StringMap<ValueTy>& rhs) {
549 if (&lhs == &rhs)
return true;
552 if (lhs.size() != rhs.size())
return false;
555 SmallVector<StringMapConstIterator<ValueTy>, 16> lhs_items;
556 lhs_items.reserve(lhs.size());
557 for (
auto i = lhs.begin(), end = lhs.
end(); i != end; ++i)
558 lhs_items.push_back(i);
559 std::sort(lhs_items.begin(), lhs_items.end(),
560 [](
const StringMapConstIterator<ValueTy>& a,
561 const StringMapConstIterator<ValueTy>& b) {
562 return a->getKey() < b->getKey();
565 SmallVector<StringMapConstIterator<ValueTy>, 16> rhs_items;
566 rhs_items.reserve(rhs.size());
567 for (
auto i = rhs.begin(), end = rhs.
end(); i != end; ++i)
568 rhs_items.push_back(i);
569 std::sort(rhs_items.begin(), rhs_items.end(),
570 [](
const StringMapConstIterator<ValueTy>& a,
571 const StringMapConstIterator<ValueTy>& b) {
572 return a->getKey() < b->getKey();
576 for (
auto a = lhs_items.begin(), b = rhs_items.begin(),
577 aend = lhs_items.end(), bend = rhs_items.end();
578 a != aend && b != bend; ++a, ++b) {
579 if ((*a)->first() != (*b)->first() || (*a)->second != (*b)->second)
585 template <
typename ValueTy>
586 inline bool operator!=(
const StringMap<ValueTy>& lhs,
587 const StringMap<ValueTy>& rhs) {
588 return !(lhs == rhs);
591 template <
typename ValueTy>
592 bool operator<(
const StringMap<ValueTy>& lhs,
const StringMap<ValueTy>& rhs) {
594 if (&lhs == &rhs)
return false;
597 SmallVector<StringRef, 16> lhs_keys;
598 lhs_keys.reserve(lhs.size());
599 for (
auto i = lhs.begin(), end = lhs.
end(); i != end; ++i)
600 lhs_keys.push_back(i->getKey());
601 std::sort(lhs_keys.begin(), lhs_keys.end());
603 SmallVector<StringRef, 16> rhs_keys;
604 rhs_keys.reserve(rhs.size());
605 for (
auto i = rhs.begin(), end = rhs.
end(); i != end; ++i)
606 rhs_keys.push_back(i->getKey());
607 std::sort(rhs_keys.begin(), rhs_keys.end());
610 return lhs_keys < rhs_keys;
613 template <
typename ValueTy>
614 inline bool operator<=(
const StringMap<ValueTy>& lhs,
615 const StringMap<ValueTy>& rhs) {
619 template <
typename ValueTy>
620 inline bool operator>(
const StringMap<ValueTy>& lhs,
621 const StringMap<ValueTy>& rhs) {
622 return !(lhs <= rhs);
625 template <
typename ValueTy>
626 inline bool operator>=(
const StringMap<ValueTy>& lhs,
627 const StringMap<ValueTy>& rhs) {
633 #endif // LLVM_ADT_STRINGMAP_H