14#ifndef LLVM_ADT_DENSEMAP_H
15#define LLVM_ADT_DENSEMAP_H
29#include <initializer_list>
41template <
typename KeyT,
typename ValueT>
46 const KeyT &
getFirst()
const {
return std::pair<KeyT, ValueT>::first; }
54 typename KeyInfoT = DenseMapInfo<KeyT>,
57class DenseMapIterator;
59template <
typename DerivedT,
typename KeyT,
typename ValueT,
typename KeyInfoT,
80 if (shouldReverseIterate<KeyT>())
81 return makeIterator(getBucketsEnd() - 1, getBuckets(), *
this);
82 return makeIterator(getBuckets(), getBucketsEnd(), *
this);
85 return makeIterator(getBucketsEnd(), getBucketsEnd(), *
this,
true);
90 if (shouldReverseIterate<KeyT>())
91 return makeConstIterator(getBucketsEnd() - 1, getBuckets(), *
this);
92 return makeConstIterator(getBuckets(), getBucketsEnd(), *
this);
95 return makeConstIterator(getBucketsEnd(), getBucketsEnd(), *
this,
true);
98 [[nodiscard]]
bool empty()
const {
return getNumEntries() == 0; }
99 unsigned size()
const {
return getNumEntries(); }
106 if (NumBuckets > getNumBuckets())
112 if (getNumEntries() == 0 && getNumTombstones() == 0)
return;
116 if (getNumEntries() * 4 < getNumBuckets() && getNumBuckets() > 64) {
122 if (std::is_trivially_destructible<ValueT>::value) {
124 for (BucketT *
P = getBuckets(), *
E = getBucketsEnd();
P !=
E; ++
P)
125 P->getFirst() = EmptyKey;
127 unsigned NumEntries = getNumEntries();
128 for (BucketT *
P = getBuckets(), *
E = getBucketsEnd();
P !=
E; ++
P) {
129 if (!KeyInfoT::isEqual(
P->getFirst(), EmptyKey)) {
130 if (!KeyInfoT::isEqual(
P->getFirst(), TombstoneKey)) {
131 P->getSecond().~ValueT();
134 P->getFirst() = EmptyKey;
137 assert(NumEntries == 0 &&
"Node count imbalance!");
146 const BucketT *TheBucket;
147 return LookupBucketFor(Val, TheBucket) ? 1 : 0;
152 if (LookupBucketFor(Val, TheBucket))
153 return makeIterator(TheBucket,
154 shouldReverseIterate<KeyT>() ? getBuckets()
160 const BucketT *TheBucket;
161 if (LookupBucketFor(Val, TheBucket))
162 return makeConstIterator(TheBucket,
163 shouldReverseIterate<KeyT>() ? getBuckets()
174 template<
class LookupKeyT>
177 if (LookupBucketFor(Val, TheBucket))
178 return makeIterator(TheBucket,
179 shouldReverseIterate<KeyT>() ? getBuckets()
184 template<
class LookupKeyT>
186 const BucketT *TheBucket;
187 if (LookupBucketFor(Val, TheBucket))
188 return makeConstIterator(TheBucket,
189 shouldReverseIterate<KeyT>() ? getBuckets()
198 const BucketT *TheBucket;
199 if (LookupBucketFor(Val, TheBucket))
200 return TheBucket->getSecond();
207 std::pair<iterator, bool>
insert(
const std::pair<KeyT, ValueT> &KV) {
214 std::pair<iterator, bool>
insert(std::pair<KeyT, ValueT> &&KV) {
215 return try_emplace(std::move(KV.first), std::move(KV.second));
221 template <
typename... Ts>
224 if (LookupBucketFor(Key, TheBucket))
225 return std::make_pair(makeIterator(TheBucket,
226 shouldReverseIterate<KeyT>()
234 InsertIntoBucket(TheBucket, std::move(Key), std::forward<Ts>(Args)...);
235 return std::make_pair(makeIterator(TheBucket,
236 shouldReverseIterate<KeyT>()
246 template <
typename... Ts>
249 if (LookupBucketFor(Key, TheBucket))
250 return std::make_pair(makeIterator(TheBucket,
251 shouldReverseIterate<KeyT>()
258 TheBucket = InsertIntoBucket(TheBucket, Key, std::forward<Ts>(Args)...);
259 return std::make_pair(makeIterator(TheBucket,
260 shouldReverseIterate<KeyT>()
272 template <
typename LookupKeyT>
273 std::pair<iterator, bool>
insert_as(std::pair<KeyT, ValueT> &&KV,
274 const LookupKeyT &Val) {
276 if (LookupBucketFor(Val, TheBucket))
277 return std::make_pair(makeIterator(TheBucket,
278 shouldReverseIterate<KeyT>()
285 TheBucket = InsertIntoBucketWithLookup(TheBucket, std::move(KV.first),
286 std::move(KV.second), Val);
287 return std::make_pair(makeIterator(TheBucket,
288 shouldReverseIterate<KeyT>()
296 template<
typename InputIt>
304 if (!LookupBucketFor(Val, TheBucket))
307 TheBucket->getSecond().~ValueT();
309 decrementNumEntries();
310 incrementNumTombstones();
314 BucketT *TheBucket = &*
I;
315 TheBucket->getSecond().~ValueT();
317 decrementNumEntries();
318 incrementNumTombstones();
323 if (LookupBucketFor(Key, TheBucket))
326 return *InsertIntoBucket(TheBucket, Key);
335 if (LookupBucketFor(Key, TheBucket))
338 return *InsertIntoBucket(TheBucket, std::move(Key));
349 return Ptr >= getBuckets() &&
Ptr < getBucketsEnd();
361 if (getNumBuckets() == 0)
365 for (BucketT *
P = getBuckets(), *
E = getBucketsEnd();
P !=
E; ++
P) {
366 if (!KeyInfoT::isEqual(
P->getFirst(), EmptyKey) &&
367 !KeyInfoT::isEqual(
P->getFirst(), TombstoneKey))
368 P->getSecond().~ValueT();
369 P->getFirst().~KeyT();
377 assert((getNumBuckets() & (getNumBuckets()-1)) == 0 &&
378 "# initial buckets must be a power of two!");
380 for (BucketT *
B = getBuckets(), *
E = getBucketsEnd();
B !=
E; ++
B)
381 ::new (&
B->getFirst())
KeyT(EmptyKey);
401 for (BucketT *
B = OldBucketsBegin, *
E = OldBucketsEnd;
B !=
E; ++
B) {
402 if (!KeyInfoT::isEqual(
B->getFirst(), EmptyKey) &&
403 !KeyInfoT::isEqual(
B->getFirst(), TombstoneKey)) {
406 bool FoundVal = LookupBucketFor(
B->getFirst(), DestBucket);
408 assert(!FoundVal &&
"Key already in new map?");
409 DestBucket->getFirst() = std::move(
B->getFirst());
410 ::new (&DestBucket->getSecond())
ValueT(std::move(
B->getSecond()));
411 incrementNumEntries();
414 B->getSecond().~ValueT();
416 B->getFirst().~KeyT();
420 template <
typename OtherBaseT>
424 assert(getNumBuckets() == other.getNumBuckets());
426 setNumEntries(other.getNumEntries());
427 setNumTombstones(other.getNumTombstones());
429 if (std::is_trivially_copyable<KeyT>::value &&
430 std::is_trivially_copyable<ValueT>::value)
431 memcpy(
reinterpret_cast<void *
>(getBuckets()), other.getBuckets(),
432 getNumBuckets() *
sizeof(BucketT));
434 for (
size_t i = 0; i < getNumBuckets(); ++i) {
435 ::new (&getBuckets()[i].getFirst())
436 KeyT(other.getBuckets()[i].getFirst());
437 if (!KeyInfoT::isEqual(getBuckets()[i].getFirst(),
getEmptyKey()) &&
439 ::new (&getBuckets()[i].getSecond())
440 ValueT(other.getBuckets()[i].getSecond());
445 return KeyInfoT::getHashValue(Val);
448 template<
typename LookupKeyT>
450 return KeyInfoT::getHashValue(Val);
454 static_assert(std::is_base_of<DenseMapBase, DerivedT>::value,
455 "Must pass the derived type to this template!");
456 return KeyInfoT::getEmptyKey();
460 return KeyInfoT::getTombstoneKey();
466 bool NoAdvance=
false) {
467 if (shouldReverseIterate<KeyT>()) {
468 BucketT *
B =
P == getBucketsEnd() ? getBuckets() :
P + 1;
475 const DebugEpochBase &Epoch,
476 const bool NoAdvance=
false)
const {
477 if (shouldReverseIterate<KeyT>()) {
478 const BucketT *
B =
P == getBucketsEnd() ? getBuckets() :
P + 1;
484 unsigned getNumEntries()
const {
485 return static_cast<const DerivedT *
>(
this)->getNumEntries();
488 void setNumEntries(
unsigned Num) {
489 static_cast<DerivedT *
>(
this)->setNumEntries(Num);
492 void incrementNumEntries() {
493 setNumEntries(getNumEntries() + 1);
496 void decrementNumEntries() {
497 setNumEntries(getNumEntries() - 1);
500 unsigned getNumTombstones()
const {
501 return static_cast<const DerivedT *
>(
this)->getNumTombstones();
504 void setNumTombstones(
unsigned Num) {
505 static_cast<DerivedT *
>(
this)->setNumTombstones(Num);
508 void incrementNumTombstones() {
509 setNumTombstones(getNumTombstones() + 1);
512 void decrementNumTombstones() {
513 setNumTombstones(getNumTombstones() - 1);
516 const BucketT *getBuckets()
const {
517 return static_cast<const DerivedT *
>(
this)->getBuckets();
520 BucketT *getBuckets() {
521 return static_cast<DerivedT *
>(
this)->getBuckets();
524 unsigned getNumBuckets()
const {
525 return static_cast<const DerivedT *
>(
this)->getNumBuckets();
528 BucketT *getBucketsEnd() {
529 return getBuckets() + getNumBuckets();
532 const BucketT *getBucketsEnd()
const {
533 return getBuckets() + getNumBuckets();
536 void grow(
unsigned AtLeast) {
537 static_cast<DerivedT *
>(
this)->grow(AtLeast);
540 void shrink_and_clear() {
541 static_cast<DerivedT *
>(
this)->shrink_and_clear();
544 template <
typename KeyArg,
typename... ValueArgs>
545 BucketT *InsertIntoBucket(BucketT *TheBucket, KeyArg &&Key,
546 ValueArgs &&... Values) {
547 TheBucket = InsertIntoBucketImpl(Key, Key, TheBucket);
549 TheBucket->getFirst() = std::forward<KeyArg>(Key);
550 ::new (&TheBucket->getSecond())
ValueT(
std::forward<ValueArgs>(Values)...);
554 template <typename LookupKeyT>
555 BucketT *InsertIntoBucketWithLookup(BucketT *TheBucket,
KeyT &&Key,
557 TheBucket = InsertIntoBucketImpl(Key,
Lookup, TheBucket);
559 TheBucket->getFirst() = std::move(Key);
564 template <typename LookupKeyT>
566 BucketT *TheBucket) {
578 unsigned NewNumEntries = getNumEntries() + 1;
579 unsigned NumBuckets = getNumBuckets();
581 this->grow(NumBuckets * 2);
582 LookupBucketFor(
Lookup, TheBucket);
583 NumBuckets = getNumBuckets();
584 }
else if (
LLVM_UNLIKELY(NumBuckets-(NewNumEntries+getNumTombstones()) <=
586 this->grow(NumBuckets);
587 LookupBucketFor(
Lookup, TheBucket);
593 incrementNumEntries();
597 if (!KeyInfoT::isEqual(TheBucket->getFirst(), EmptyKey))
598 decrementNumTombstones();
607 template<
typename LookupKeyT>
608 bool LookupBucketFor(
const LookupKeyT &Val,
609 const BucketT *&FoundBucket)
const {
610 const BucketT *BucketsPtr = getBuckets();
611 const unsigned NumBuckets = getNumBuckets();
613 if (NumBuckets == 0) {
614 FoundBucket =
nullptr;
619 const BucketT *FoundTombstone =
nullptr;
622 assert(!KeyInfoT::isEqual(Val, EmptyKey) &&
623 !KeyInfoT::isEqual(Val, TombstoneKey) &&
624 "Empty/Tombstone value shouldn't be inserted into map!");
627 unsigned ProbeAmt = 1;
629 const BucketT *ThisBucket = BucketsPtr + BucketNo;
631 if (
LLVM_LIKELY(KeyInfoT::isEqual(Val, ThisBucket->getFirst()))) {
632 FoundBucket = ThisBucket;
638 if (
LLVM_LIKELY(KeyInfoT::isEqual(ThisBucket->getFirst(), EmptyKey))) {
641 FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket;
647 if (KeyInfoT::isEqual(ThisBucket->getFirst(), TombstoneKey) &&
649 FoundTombstone = ThisBucket;
653 BucketNo += ProbeAmt++;
654 BucketNo &= (NumBuckets-1);
658 template <
typename LookupKeyT>
659 bool LookupBucketFor(
const LookupKeyT &Val, BucketT *&FoundBucket) {
660 const BucketT *ConstFoundBucket;
662 ->LookupBucketFor(Val, ConstFoundBucket);
663 FoundBucket =
const_cast<BucketT *
>(ConstFoundBucket);
673 return getNumBuckets() *
sizeof(BucketT);
683template <
typename DerivedT,
typename KeyT,
typename ValueT,
typename KeyInfoT,
688 if (
LHS.size() !=
RHS.size())
691 for (
auto &KV :
LHS) {
692 auto I =
RHS.find(KV.first);
693 if (
I ==
RHS.end() ||
I->second != KV.second)
703template <
typename DerivedT,
typename KeyT,
typename ValueT,
typename KeyInfoT,
712 typename KeyInfoT = DenseMapInfo<KeyT>,
715 KeyT, ValueT, KeyInfoT, BucketT> {
724 unsigned NumTombstones;
730 explicit DenseMap(
unsigned InitialReserve = 0) { init(InitialReserve); }
742 template<
typename InputIt>
744 init(std::distance(
I,
E));
748 DenseMap(std::initializer_list<typename BaseT::value_type> Vals) {
750 this->insert(Vals.begin(), Vals.end());
759 this->incrementEpoch();
760 RHS.incrementEpoch();
784 if (allocateBuckets(other.NumBuckets)) {
785 this->BaseT::copyFrom(other);
792 void init(
unsigned InitNumEntries) {
793 auto InitBuckets = BaseT::getMinBucketToReserveForEntries(InitNumEntries);
794 if (allocateBuckets(InitBuckets)) {
795 this->BaseT::initEmpty();
803 unsigned OldNumBuckets = NumBuckets;
804 BucketT *OldBuckets = Buckets;
806 allocateBuckets(std::max<unsigned>(64,
static_cast<unsigned>(
NextPowerOf2(AtLeast-1))));
809 this->BaseT::initEmpty();
813 this->moveFromOldBuckets(OldBuckets, OldBuckets+OldNumBuckets);
821 unsigned OldNumBuckets = NumBuckets;
822 unsigned OldNumEntries = NumEntries;
826 unsigned NewNumBuckets = 0;
828 NewNumBuckets = std::max(64, 1 << (
Log2_32_Ceil(OldNumEntries) + 1));
829 if (NewNumBuckets == NumBuckets) {
830 this->BaseT::initEmpty();
840 unsigned getNumEntries()
const {
844 void setNumEntries(
unsigned Num) {
848 unsigned getNumTombstones()
const {
849 return NumTombstones;
852 void setNumTombstones(
unsigned Num) {
856 BucketT *getBuckets()
const {
860 unsigned getNumBuckets()
const {
864 bool allocateBuckets(
unsigned Num) {
866 if (NumBuckets == 0) {
871 Buckets =
static_cast<BucketT *
>(
877template <
typename KeyT,
typename ValueT,
unsigned InlineBuckets = 4,
878 typename KeyInfoT = DenseMapInfo<KeyT>,
882 SmallDenseMap<KeyT, ValueT, InlineBuckets, KeyInfoT, BucketT>, KeyT,
883 ValueT, KeyInfoT, BucketT> {
891 "InlineBuckets must be a power of 2.");
894 unsigned NumEntries : 31;
895 unsigned NumTombstones;
908 if (NumInitBuckets > InlineBuckets)
910 init(NumInitBuckets);
923 template<
typename InputIt>
938 unsigned TmpNumEntries =
RHS.NumEntries;
939 RHS.NumEntries = NumEntries;
940 NumEntries = TmpNumEntries;
943 const KeyT EmptyKey = this->getEmptyKey();
944 const KeyT TombstoneKey = this->getTombstoneKey();
945 if (Small &&
RHS.Small) {
950 for (
unsigned i = 0, e = InlineBuckets; i != e; ++i) {
951 BucketT *LHSB = &getInlineBuckets()[i],
952 *RHSB = &
RHS.getInlineBuckets()[i];
953 bool hasLHSValue = (!KeyInfoT::isEqual(LHSB->getFirst(), EmptyKey) &&
954 !KeyInfoT::isEqual(LHSB->getFirst(), TombstoneKey));
955 bool hasRHSValue = (!KeyInfoT::isEqual(RHSB->getFirst(), EmptyKey) &&
956 !KeyInfoT::isEqual(RHSB->getFirst(), TombstoneKey));
957 if (hasLHSValue && hasRHSValue) {
963 std::swap(LHSB->getFirst(), RHSB->getFirst());
965 ::new (&RHSB->getSecond())
ValueT(std::move(LHSB->getSecond()));
966 LHSB->getSecond().~ValueT();
967 }
else if (hasRHSValue) {
968 ::new (&LHSB->getSecond())
ValueT(std::move(RHSB->getSecond()));
969 RHSB->getSecond().~ValueT();
974 if (!Small && !
RHS.Small) {
975 std::swap(getLargeRep()->Buckets,
RHS.getLargeRep()->Buckets);
976 std::swap(getLargeRep()->NumBuckets,
RHS.getLargeRep()->NumBuckets);
984 LargeRep TmpRep = std::move(*LargeSide.getLargeRep());
985 LargeSide.getLargeRep()->~LargeRep();
986 LargeSide.Small =
true;
991 for (
unsigned i = 0, e = InlineBuckets; i != e; ++i) {
992 BucketT *NewB = &LargeSide.getInlineBuckets()[i],
993 *OldB = &SmallSide.getInlineBuckets()[i];
994 ::new (&NewB->getFirst())
KeyT(std::move(OldB->getFirst()));
995 OldB->getFirst().~KeyT();
996 if (!KeyInfoT::isEqual(NewB->getFirst(), EmptyKey) &&
997 !KeyInfoT::isEqual(NewB->getFirst(), TombstoneKey)) {
998 ::new (&NewB->getSecond())
ValueT(std::move(OldB->getSecond()));
999 OldB->getSecond().~ValueT();
1005 SmallSide.Small =
false;
1006 new (SmallSide.getLargeRep()) LargeRep(std::move(TmpRep));
1017 deallocateBuckets();
1025 deallocateBuckets();
1027 if (other.getNumBuckets() > InlineBuckets) {
1029 new (getLargeRep()) LargeRep(allocateBuckets(other.getNumBuckets()));
1031 this->BaseT::copyFrom(other);
1036 if (InitBuckets > InlineBuckets) {
1038 new (getLargeRep()) LargeRep(allocateBuckets(InitBuckets));
1040 this->BaseT::initEmpty();
1044 if (AtLeast > InlineBuckets)
1045 AtLeast = std::max<unsigned>(64,
NextPowerOf2(AtLeast-1));
1050 BucketT *TmpBegin =
reinterpret_cast<BucketT *
>(&TmpStorage);
1051 BucketT *TmpEnd = TmpBegin;
1055 const KeyT EmptyKey = this->getEmptyKey();
1056 const KeyT TombstoneKey = this->getTombstoneKey();
1057 for (BucketT *
P = getBuckets(), *
E =
P + InlineBuckets;
P !=
E; ++
P) {
1058 if (!KeyInfoT::isEqual(
P->getFirst(), EmptyKey) &&
1059 !KeyInfoT::isEqual(
P->getFirst(), TombstoneKey)) {
1060 assert(
size_t(TmpEnd - TmpBegin) < InlineBuckets &&
1061 "Too many inline buckets!");
1062 ::new (&TmpEnd->getFirst())
KeyT(std::move(
P->getFirst()));
1063 ::new (&TmpEnd->getSecond())
ValueT(std::move(
P->getSecond()));
1065 P->getSecond().~ValueT();
1067 P->getFirst().~KeyT();
1073 if (AtLeast > InlineBuckets) {
1075 new (getLargeRep()) LargeRep(allocateBuckets(AtLeast));
1077 this->moveFromOldBuckets(TmpBegin, TmpEnd);
1081 LargeRep OldRep = std::move(*getLargeRep());
1082 getLargeRep()->~LargeRep();
1083 if (AtLeast <= InlineBuckets) {
1086 new (getLargeRep()) LargeRep(allocateBuckets(AtLeast));
1089 this->moveFromOldBuckets(OldRep.Buckets, OldRep.Buckets+OldRep.NumBuckets);
1097 unsigned OldSize = this->
size();
1101 unsigned NewNumBuckets = 0;
1104 if (NewNumBuckets > InlineBuckets && NewNumBuckets < 64u)
1107 if ((Small && NewNumBuckets <= InlineBuckets) ||
1108 (!Small && NewNumBuckets == getLargeRep()->NumBuckets)) {
1109 this->BaseT::initEmpty();
1113 deallocateBuckets();
1114 init(NewNumBuckets);
1118 unsigned getNumEntries()
const {
1122 void setNumEntries(
unsigned Num) {
1124 assert(Num < (1U << 31) &&
"Cannot support more than 1<<31 entries");
1128 unsigned getNumTombstones()
const {
1129 return NumTombstones;
1132 void setNumTombstones(
unsigned Num) {
1133 NumTombstones = Num;
1136 const BucketT *getInlineBuckets()
const {
1141 return reinterpret_cast<const BucketT *
>(&storage);
1144 BucketT *getInlineBuckets() {
1145 return const_cast<BucketT *
>(
1146 const_cast<const SmallDenseMap *
>(
this)->getInlineBuckets());
1149 const LargeRep *getLargeRep()
const {
1152 return reinterpret_cast<const LargeRep *
>(&storage);
1155 LargeRep *getLargeRep() {
1156 return const_cast<LargeRep *
>(
1157 const_cast<const SmallDenseMap *
>(
this)->getLargeRep());
1160 const BucketT *getBuckets()
const {
1161 return Small ? getInlineBuckets() : getLargeRep()->Buckets;
1164 BucketT *getBuckets() {
1165 return const_cast<BucketT *
>(
1166 const_cast<const SmallDenseMap *
>(
this)->getBuckets());
1169 unsigned getNumBuckets()
const {
1170 return Small ? InlineBuckets : getLargeRep()->NumBuckets;
1173 void deallocateBuckets() {
1178 sizeof(BucketT) * getLargeRep()->NumBuckets,
1180 getLargeRep()->~LargeRep();
1183 LargeRep allocateBuckets(
unsigned Num) {
1184 assert(Num > InlineBuckets &&
"Must allocate more buckets than are inline");
1186 sizeof(BucketT) * Num,
alignof(BucketT))),
1192template <
typename KeyT,
typename ValueT,
typename KeyInfoT,
typename Bucket,
1200 using value_type = std::conditional_t<IsConst, const Bucket, Bucket>;
1213 bool NoAdvance =
false)
1215 assert(isHandleInSync() &&
"invalid construction!");
1217 if (NoAdvance)
return;
1218 if (shouldReverseIterate<KeyT>()) {
1219 RetreatPastEmptyBuckets();
1222 AdvancePastEmptyBuckets();
1228 template <
bool IsConstSrc,
1229 typename = std::enable_if_t<!IsConstSrc && IsConst>>
1235 assert(isHandleInSync() &&
"invalid iterator access!");
1236 assert(
Ptr != End &&
"dereferencing end() iterator");
1237 if (shouldReverseIterate<KeyT>())
1242 assert(isHandleInSync() &&
"invalid iterator access!");
1243 assert(
Ptr != End &&
"dereferencing end() iterator");
1244 if (shouldReverseIterate<KeyT>())
1251 assert((!
LHS.Ptr ||
LHS.isHandleInSync()) &&
"handle not in sync!");
1252 assert((!
RHS.Ptr ||
RHS.isHandleInSync()) &&
"handle not in sync!");
1253 assert(
LHS.getEpochAddress() ==
RHS.getEpochAddress() &&
1254 "comparing incomparable iterators!");
1255 return LHS.Ptr ==
RHS.Ptr;
1264 assert(isHandleInSync() &&
"invalid iterator access!");
1265 assert(
Ptr != End &&
"incrementing end() iterator");
1266 if (shouldReverseIterate<KeyT>()) {
1268 RetreatPastEmptyBuckets();
1272 AdvancePastEmptyBuckets();
1276 assert(isHandleInSync() &&
"invalid iterator access!");
1281 void AdvancePastEmptyBuckets() {
1283 const KeyT Empty = KeyInfoT::getEmptyKey();
1284 const KeyT Tombstone = KeyInfoT::getTombstoneKey();
1286 while (
Ptr != End && (KeyInfoT::isEqual(
Ptr->getFirst(), Empty) ||
1287 KeyInfoT::isEqual(
Ptr->getFirst(), Tombstone)))
1291 void RetreatPastEmptyBuckets() {
1293 const KeyT Empty = KeyInfoT::getEmptyKey();
1294 const KeyT Tombstone = KeyInfoT::getTombstoneKey();
1296 while (
Ptr != End && (KeyInfoT::isEqual(
Ptr[-1].getFirst(), Empty) ||
1297 KeyInfoT::isEqual(
Ptr[-1].getFirst(), Tombstone)))
1302template <
typename KeyT,
typename ValueT,
typename KeyInfoT>
1304 return X.getMemorySize();
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define LLVM_UNLIKELY(EXPR)
#define LLVM_LIKELY(EXPR)
This file defines DenseMapInfo traits for DenseMap.
This file defines the DebugEpochBase and DebugEpochBase::HandleBase classes.
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
This file defines counterparts of C library allocation functions defined in the namespace 'std'.
return ToRemove size() > 0
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static int Lookup(ArrayRef< TableEntry > Table, unsigned Opcode)
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
iterator find(const_arg_type_t< KeyT > Val)
static unsigned getHashValue(const KeyT &Val)
static const KeyT getEmptyKey()
value_type & FindAndConstruct(KeyT &&Key)
std::pair< iterator, bool > insert(std::pair< KeyT, ValueT > &&KV)
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&... Args)
bool erase(const KeyT &Val)
DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT > iterator
std::pair< iterator, bool > insert_as(std::pair< KeyT, ValueT > &&KV, const LookupKeyT &Val)
Alternate version of insert() which allows a different, and possibly less expensive,...
const_iterator find_as(const LookupKeyT &Val) const
const_iterator end() const
std::pair< iterator, bool > try_emplace(const KeyT &Key, Ts &&... Args)
void moveFromOldBuckets(BucketT *OldBucketsBegin, BucketT *OldBucketsEnd)
iterator find_as(const LookupKeyT &Val)
Alternate version of find() which allows a different, and possibly less expensive,...
const_iterator find(const_arg_type_t< KeyT > Val) const
void insert(InputIt I, InputIt E)
insert - Range insertion of pairs.
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
static const KeyT getTombstoneKey()
bool isPointerIntoBucketsArray(const void *Ptr) const
isPointerIntoBucketsArray - Return true if the specified pointer points somewhere into the DenseMap's...
void copyFrom(const DenseMapBase< OtherBaseT, KeyT, ValueT, KeyInfoT, BucketT > &other)
value_type & FindAndConstruct(const KeyT &Key)
const_iterator begin() const
const void * getPointerIntoBucketsArray() const
getPointerIntoBucketsArray() - Return an opaque pointer into the buckets array.
unsigned getMinBucketToReserveForEntries(unsigned NumEntries)
Returns the number of buckets to allocate to ensure that the DenseMap can accommodate NumEntries with...
static unsigned getHashValue(const LookupKeyT &Val)
ValueT & operator[](const KeyT &Key)
DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT, true > const_iterator
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
void reserve(size_type NumEntries)
Grow the densemap so that it can contain at least NumEntries items before resizing again.
ValueT & operator[](KeyT &&Key)
size_t getMemorySize() const
Return the approximate size (in bytes) of the actual map.
std::conditional_t< IsConst, const Bucket, Bucket > value_type
friend bool operator!=(const DenseMapIterator &LHS, const DenseMapIterator &RHS)
DenseMapIterator & operator++()
pointer operator->() const
reference operator*() const
DenseMapIterator(pointer Pos, pointer E, const DebugEpochBase &Epoch, bool NoAdvance=false)
DenseMapIterator()=default
DenseMapIterator operator++(int)
DenseMapIterator(const DenseMapIterator< KeyT, ValueT, KeyInfoT, Bucket, IsConstSrc > &I)
friend bool operator==(const DenseMapIterator &LHS, const DenseMapIterator &RHS)
std::forward_iterator_tag iterator_category
DenseMap(std::initializer_list< typename BaseT::value_type > Vals)
void copyFrom(const DenseMap &other)
DenseMap & operator=(DenseMap &&other)
DenseMap(unsigned InitialReserve=0)
Create a DenseMap with an optional InitialReserve that guarantee that this number of elements can be ...
void grow(unsigned AtLeast)
void init(unsigned InitNumEntries)
DenseMap(const DenseMap &other)
DenseMap(const InputIt &I, const InputIt &E)
DenseMap(DenseMap &&other)
DenseMap & operator=(const DenseMap &other)
void grow(unsigned AtLeast)
SmallDenseMap(const InputIt &I, const InputIt &E)
void swap(SmallDenseMap &RHS)
void init(unsigned InitBuckets)
SmallDenseMap & operator=(SmallDenseMap &&other)
SmallDenseMap & operator=(const SmallDenseMap &other)
SmallDenseMap(unsigned NumInitBuckets=0)
SmallDenseMap(std::initializer_list< typename BaseT::value_type > Vals)
SmallDenseMap(SmallDenseMap &&other)
SmallDenseMap(const SmallDenseMap &other)
void copyFrom(const SmallDenseMap &other)
constexpr char IsConst[]
Key for Kernel::Arg::Metadata::mIsConst.
This is an optimization pass for GlobalISel generic memory operations.
unsigned Log2_32_Ceil(uint32_t Value)
Return the ceil log base 2 of the specified value, 32 if the value is zero.
bool operator==(uint64_t V1, const APInt &V2)
BitVector::size_type capacity_in_bytes(const BitVector &X)
bool operator!=(uint64_t V1, const APInt &V2)
constexpr bool isPowerOf2_64(uint64_t Value)
Return true if the argument is a power of two > 0 (64 bit edition.)
T bit_ceil(T Value)
Returns the smallest integral power of two no smaller than Value if Value is nonzero.
LLVM_ATTRIBUTE_RETURNS_NONNULL LLVM_ATTRIBUTE_RETURNS_NOALIAS void * allocate_buffer(size_t Size, size_t Alignment)
Allocate a buffer of memory with the given size and alignment.
void deallocate_buffer(void *Ptr, size_t Size, size_t Alignment)
Deallocate a buffer of memory with the given size and alignment.
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
constexpr uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
A suitably aligned and sized character array member which can hold elements of any type.
const ValueT & getSecond() const
const KeyT & getFirst() const