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);
157 if (LookupBucketFor(Val, TheBucket))
158 return makeIterator(TheBucket,
159 shouldReverseIterate<KeyT>() ? getBuckets()
165 const BucketT *TheBucket;
166 if (LookupBucketFor(Val, TheBucket))
167 return makeConstIterator(TheBucket,
168 shouldReverseIterate<KeyT>() ? getBuckets()
179 template<
class LookupKeyT>
182 if (LookupBucketFor(Val, TheBucket))
183 return makeIterator(TheBucket,
184 shouldReverseIterate<KeyT>() ? getBuckets()
189 template<
class LookupKeyT>
191 const BucketT *TheBucket;
192 if (LookupBucketFor(Val, TheBucket))
193 return makeConstIterator(TheBucket,
194 shouldReverseIterate<KeyT>() ? getBuckets()
203 const BucketT *TheBucket;
204 if (LookupBucketFor(Val, TheBucket))
205 return TheBucket->getSecond();
211 const ValueT &
at(const_arg_type_t<KeyT> Val)
const {
212 auto Iter = this->
find(std::move(Val));
213 assert(Iter != this->
end() &&
"DenseMap::at failed due to a missing key");
220 std::pair<iterator, bool>
insert(
const std::pair<KeyT, ValueT> &KV) {
227 std::pair<iterator, bool>
insert(std::pair<KeyT, ValueT> &&KV) {
228 return try_emplace(std::move(KV.first), std::move(KV.second));
234 template <
typename... Ts>
237 if (LookupBucketFor(Key, TheBucket))
238 return std::make_pair(makeIterator(TheBucket,
239 shouldReverseIterate<KeyT>()
247 InsertIntoBucket(TheBucket, std::move(Key), std::forward<Ts>(Args)...);
248 return std::make_pair(makeIterator(TheBucket,
249 shouldReverseIterate<KeyT>()
259 template <
typename... Ts>
262 if (LookupBucketFor(Key, TheBucket))
263 return std::make_pair(makeIterator(TheBucket,
264 shouldReverseIterate<KeyT>()
271 TheBucket = InsertIntoBucket(TheBucket, Key, std::forward<Ts>(Args)...);
272 return std::make_pair(makeIterator(TheBucket,
273 shouldReverseIterate<KeyT>()
285 template <
typename LookupKeyT>
286 std::pair<iterator, bool>
insert_as(std::pair<KeyT, ValueT> &&KV,
287 const LookupKeyT &Val) {
289 if (LookupBucketFor(Val, TheBucket))
290 return std::make_pair(makeIterator(TheBucket,
291 shouldReverseIterate<KeyT>()
298 TheBucket = InsertIntoBucketWithLookup(TheBucket, std::move(KV.first),
299 std::move(KV.second), Val);
300 return std::make_pair(makeIterator(TheBucket,
301 shouldReverseIterate<KeyT>()
309 template<
typename InputIt>
315 template <
typename V>
319 Ret.first->second = std::forward<V>(Val);
323 template <
typename V>
325 auto Ret =
try_emplace(std::move(Key), std::forward<V>(Val));
327 Ret.first->second = std::forward<V>(Val);
347 if (!LookupBucketFor(Val, TheBucket))
350 TheBucket->getSecond().~ValueT();
352 decrementNumEntries();
353 incrementNumTombstones();
357 BucketT *TheBucket = &*
I;
358 TheBucket->getSecond().~ValueT();
360 decrementNumEntries();
361 incrementNumTombstones();
366 if (LookupBucketFor(Key, TheBucket))
369 return *InsertIntoBucket(TheBucket, Key);
378 if (LookupBucketFor(Key, TheBucket))
381 return *InsertIntoBucket(TheBucket, std::move(Key));
392 return Ptr >= getBuckets() &&
Ptr < getBucketsEnd();
404 if (getNumBuckets() == 0)
408 for (BucketT *
P = getBuckets(), *
E = getBucketsEnd();
P !=
E; ++
P) {
409 if (!KeyInfoT::isEqual(
P->getFirst(), EmptyKey) &&
410 !KeyInfoT::isEqual(
P->getFirst(), TombstoneKey))
411 P->getSecond().~ValueT();
412 P->getFirst().~KeyT();
420 assert((getNumBuckets() & (getNumBuckets()-1)) == 0 &&
421 "# initial buckets must be a power of two!");
423 for (BucketT *
B = getBuckets(), *
E = getBucketsEnd();
B !=
E; ++
B)
424 ::new (&
B->getFirst())
KeyT(EmptyKey);
444 for (BucketT *
B = OldBucketsBegin, *
E = OldBucketsEnd;
B !=
E; ++
B) {
445 if (!KeyInfoT::isEqual(
B->getFirst(), EmptyKey) &&
446 !KeyInfoT::isEqual(
B->getFirst(), TombstoneKey)) {
449 bool FoundVal = LookupBucketFor(
B->getFirst(), DestBucket);
451 assert(!FoundVal &&
"Key already in new map?");
452 DestBucket->getFirst() = std::move(
B->getFirst());
453 ::new (&DestBucket->getSecond())
ValueT(std::move(
B->getSecond()));
454 incrementNumEntries();
457 B->getSecond().~ValueT();
459 B->getFirst().~KeyT();
463 template <
typename OtherBaseT>
467 assert(getNumBuckets() == other.getNumBuckets());
469 setNumEntries(other.getNumEntries());
470 setNumTombstones(other.getNumTombstones());
472 if (std::is_trivially_copyable<KeyT>::value &&
473 std::is_trivially_copyable<ValueT>::value)
474 memcpy(
reinterpret_cast<void *
>(getBuckets()), other.getBuckets(),
475 getNumBuckets() *
sizeof(BucketT));
477 for (
size_t i = 0; i < getNumBuckets(); ++i) {
478 ::new (&getBuckets()[i].getFirst())
479 KeyT(other.getBuckets()[i].getFirst());
480 if (!KeyInfoT::isEqual(getBuckets()[i].getFirst(),
getEmptyKey()) &&
482 ::new (&getBuckets()[i].getSecond())
483 ValueT(other.getBuckets()[i].getSecond());
488 return KeyInfoT::getHashValue(Val);
491 template<
typename LookupKeyT>
493 return KeyInfoT::getHashValue(Val);
497 static_assert(std::is_base_of<DenseMapBase, DerivedT>::value,
498 "Must pass the derived type to this template!");
499 return KeyInfoT::getEmptyKey();
503 return KeyInfoT::getTombstoneKey();
509 bool NoAdvance=
false) {
510 if (shouldReverseIterate<KeyT>()) {
511 BucketT *
B =
P == getBucketsEnd() ? getBuckets() :
P + 1;
518 const DebugEpochBase &Epoch,
519 const bool NoAdvance=
false)
const {
520 if (shouldReverseIterate<KeyT>()) {
521 const BucketT *
B =
P == getBucketsEnd() ? getBuckets() :
P + 1;
527 unsigned getNumEntries()
const {
528 return static_cast<const DerivedT *
>(
this)->getNumEntries();
531 void setNumEntries(
unsigned Num) {
532 static_cast<DerivedT *
>(
this)->setNumEntries(Num);
535 void incrementNumEntries() {
536 setNumEntries(getNumEntries() + 1);
539 void decrementNumEntries() {
540 setNumEntries(getNumEntries() - 1);
543 unsigned getNumTombstones()
const {
544 return static_cast<const DerivedT *
>(
this)->getNumTombstones();
547 void setNumTombstones(
unsigned Num) {
548 static_cast<DerivedT *
>(
this)->setNumTombstones(Num);
551 void incrementNumTombstones() {
552 setNumTombstones(getNumTombstones() + 1);
555 void decrementNumTombstones() {
556 setNumTombstones(getNumTombstones() - 1);
559 const BucketT *getBuckets()
const {
560 return static_cast<const DerivedT *
>(
this)->getBuckets();
563 BucketT *getBuckets() {
564 return static_cast<DerivedT *
>(
this)->getBuckets();
567 unsigned getNumBuckets()
const {
568 return static_cast<const DerivedT *
>(
this)->getNumBuckets();
571 BucketT *getBucketsEnd() {
572 return getBuckets() + getNumBuckets();
575 const BucketT *getBucketsEnd()
const {
576 return getBuckets() + getNumBuckets();
579 void grow(
unsigned AtLeast) {
580 static_cast<DerivedT *
>(
this)->grow(AtLeast);
583 void shrink_and_clear() {
584 static_cast<DerivedT *
>(
this)->shrink_and_clear();
587 template <
typename KeyArg,
typename... ValueArgs>
588 BucketT *InsertIntoBucket(BucketT *TheBucket, KeyArg &&Key,
589 ValueArgs &&... Values) {
590 TheBucket = InsertIntoBucketImpl(Key, Key, TheBucket);
592 TheBucket->getFirst() = std::forward<KeyArg>(Key);
593 ::new (&TheBucket->getSecond())
ValueT(
std::forward<ValueArgs>(Values)...);
597 template <typename LookupKeyT>
598 BucketT *InsertIntoBucketWithLookup(BucketT *TheBucket,
KeyT &&Key,
600 TheBucket = InsertIntoBucketImpl(Key,
Lookup, TheBucket);
602 TheBucket->getFirst() = std::move(Key);
607 template <typename LookupKeyT>
609 BucketT *TheBucket) {
621 unsigned NewNumEntries = getNumEntries() + 1;
622 unsigned NumBuckets = getNumBuckets();
624 this->grow(NumBuckets * 2);
625 LookupBucketFor(
Lookup, TheBucket);
626 NumBuckets = getNumBuckets();
627 }
else if (
LLVM_UNLIKELY(NumBuckets-(NewNumEntries+getNumTombstones()) <=
629 this->grow(NumBuckets);
630 LookupBucketFor(
Lookup, TheBucket);
636 incrementNumEntries();
640 if (!KeyInfoT::isEqual(TheBucket->getFirst(), EmptyKey))
641 decrementNumTombstones();
650 template<
typename LookupKeyT>
651 bool LookupBucketFor(
const LookupKeyT &Val,
652 const BucketT *&FoundBucket)
const {
653 const BucketT *BucketsPtr = getBuckets();
654 const unsigned NumBuckets = getNumBuckets();
656 if (NumBuckets == 0) {
657 FoundBucket =
nullptr;
662 const BucketT *FoundTombstone =
nullptr;
665 assert(!KeyInfoT::isEqual(Val, EmptyKey) &&
666 !KeyInfoT::isEqual(Val, TombstoneKey) &&
667 "Empty/Tombstone value shouldn't be inserted into map!");
670 unsigned ProbeAmt = 1;
672 const BucketT *ThisBucket = BucketsPtr + BucketNo;
674 if (
LLVM_LIKELY(KeyInfoT::isEqual(Val, ThisBucket->getFirst()))) {
675 FoundBucket = ThisBucket;
681 if (
LLVM_LIKELY(KeyInfoT::isEqual(ThisBucket->getFirst(), EmptyKey))) {
684 FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket;
690 if (KeyInfoT::isEqual(ThisBucket->getFirst(), TombstoneKey) &&
692 FoundTombstone = ThisBucket;
696 BucketNo += ProbeAmt++;
697 BucketNo &= (NumBuckets-1);
701 template <
typename LookupKeyT>
702 bool LookupBucketFor(
const LookupKeyT &Val, BucketT *&FoundBucket) {
703 const BucketT *ConstFoundBucket;
705 ->LookupBucketFor(Val, ConstFoundBucket);
706 FoundBucket =
const_cast<BucketT *
>(ConstFoundBucket);
716 return getNumBuckets() *
sizeof(BucketT);
726template <
typename DerivedT,
typename KeyT,
typename ValueT,
typename KeyInfoT,
731 if (
LHS.size() !=
RHS.size())
734 for (
auto &KV :
LHS) {
735 auto I =
RHS.find(KV.first);
736 if (
I ==
RHS.end() ||
I->second != KV.second)
746template <
typename DerivedT,
typename KeyT,
typename ValueT,
typename KeyInfoT,
755 typename KeyInfoT = DenseMapInfo<KeyT>,
758 KeyT, ValueT, KeyInfoT, BucketT> {
767 unsigned NumTombstones;
773 explicit DenseMap(
unsigned InitialReserve = 0) { init(InitialReserve); }
785 template<
typename InputIt>
787 init(std::distance(
I,
E));
791 DenseMap(std::initializer_list<typename BaseT::value_type> Vals) {
793 this->insert(Vals.begin(), Vals.end());
802 this->incrementEpoch();
803 RHS.incrementEpoch();
827 if (allocateBuckets(other.NumBuckets)) {
828 this->BaseT::copyFrom(other);
835 void init(
unsigned InitNumEntries) {
836 auto InitBuckets = BaseT::getMinBucketToReserveForEntries(InitNumEntries);
837 if (allocateBuckets(InitBuckets)) {
838 this->BaseT::initEmpty();
846 unsigned OldNumBuckets = NumBuckets;
847 BucketT *OldBuckets = Buckets;
849 allocateBuckets(std::max<unsigned>(64,
static_cast<unsigned>(
NextPowerOf2(AtLeast-1))));
852 this->BaseT::initEmpty();
856 this->moveFromOldBuckets(OldBuckets, OldBuckets+OldNumBuckets);
864 unsigned OldNumBuckets = NumBuckets;
865 unsigned OldNumEntries = NumEntries;
869 unsigned NewNumBuckets = 0;
871 NewNumBuckets = std::max(64, 1 << (
Log2_32_Ceil(OldNumEntries) + 1));
872 if (NewNumBuckets == NumBuckets) {
873 this->BaseT::initEmpty();
883 unsigned getNumEntries()
const {
887 void setNumEntries(
unsigned Num) {
891 unsigned getNumTombstones()
const {
892 return NumTombstones;
895 void setNumTombstones(
unsigned Num) {
899 BucketT *getBuckets()
const {
903 unsigned getNumBuckets()
const {
907 bool allocateBuckets(
unsigned Num) {
909 if (NumBuckets == 0) {
914 Buckets =
static_cast<BucketT *
>(
920template <
typename KeyT,
typename ValueT,
unsigned InlineBuckets = 4,
921 typename KeyInfoT = DenseMapInfo<KeyT>,
925 SmallDenseMap<KeyT, ValueT, InlineBuckets, KeyInfoT, BucketT>, KeyT,
926 ValueT, KeyInfoT, BucketT> {
934 "InlineBuckets must be a power of 2.");
937 unsigned NumEntries : 31;
938 unsigned NumTombstones;
951 if (NumInitBuckets > InlineBuckets)
953 init(NumInitBuckets);
966 template<
typename InputIt>
981 unsigned TmpNumEntries =
RHS.NumEntries;
982 RHS.NumEntries = NumEntries;
983 NumEntries = TmpNumEntries;
986 const KeyT EmptyKey = this->getEmptyKey();
987 const KeyT TombstoneKey = this->getTombstoneKey();
988 if (Small &&
RHS.Small) {
993 for (
unsigned i = 0, e = InlineBuckets; i != e; ++i) {
994 BucketT *LHSB = &getInlineBuckets()[i],
995 *RHSB = &
RHS.getInlineBuckets()[i];
996 bool hasLHSValue = (!KeyInfoT::isEqual(LHSB->getFirst(), EmptyKey) &&
997 !KeyInfoT::isEqual(LHSB->getFirst(), TombstoneKey));
998 bool hasRHSValue = (!KeyInfoT::isEqual(RHSB->getFirst(), EmptyKey) &&
999 !KeyInfoT::isEqual(RHSB->getFirst(), TombstoneKey));
1000 if (hasLHSValue && hasRHSValue) {
1006 std::swap(LHSB->getFirst(), RHSB->getFirst());
1008 ::new (&RHSB->getSecond())
ValueT(std::move(LHSB->getSecond()));
1009 LHSB->getSecond().~ValueT();
1010 }
else if (hasRHSValue) {
1011 ::new (&LHSB->getSecond())
ValueT(std::move(RHSB->getSecond()));
1012 RHSB->getSecond().~ValueT();
1017 if (!Small && !
RHS.Small) {
1018 std::swap(getLargeRep()->Buckets,
RHS.getLargeRep()->Buckets);
1019 std::swap(getLargeRep()->NumBuckets,
RHS.getLargeRep()->NumBuckets);
1027 LargeRep TmpRep = std::move(*LargeSide.getLargeRep());
1028 LargeSide.getLargeRep()->~LargeRep();
1029 LargeSide.Small =
true;
1034 for (
unsigned i = 0, e = InlineBuckets; i != e; ++i) {
1035 BucketT *NewB = &LargeSide.getInlineBuckets()[i],
1036 *OldB = &SmallSide.getInlineBuckets()[i];
1037 ::new (&NewB->getFirst())
KeyT(std::move(OldB->getFirst()));
1038 OldB->getFirst().~KeyT();
1039 if (!KeyInfoT::isEqual(NewB->getFirst(), EmptyKey) &&
1040 !KeyInfoT::isEqual(NewB->getFirst(), TombstoneKey)) {
1041 ::new (&NewB->getSecond())
ValueT(std::move(OldB->getSecond()));
1042 OldB->getSecond().~ValueT();
1048 SmallSide.Small =
false;
1049 new (SmallSide.getLargeRep()) LargeRep(std::move(TmpRep));
1060 deallocateBuckets();
1068 deallocateBuckets();
1070 if (other.getNumBuckets() > InlineBuckets) {
1072 new (getLargeRep()) LargeRep(allocateBuckets(other.getNumBuckets()));
1074 this->BaseT::copyFrom(other);
1079 if (InitBuckets > InlineBuckets) {
1081 new (getLargeRep()) LargeRep(allocateBuckets(InitBuckets));
1083 this->BaseT::initEmpty();
1087 if (AtLeast > InlineBuckets)
1088 AtLeast = std::max<unsigned>(64,
NextPowerOf2(AtLeast-1));
1093 BucketT *TmpBegin =
reinterpret_cast<BucketT *
>(&TmpStorage);
1094 BucketT *TmpEnd = TmpBegin;
1098 const KeyT EmptyKey = this->getEmptyKey();
1099 const KeyT TombstoneKey = this->getTombstoneKey();
1100 for (BucketT *
P = getBuckets(), *
E =
P + InlineBuckets;
P !=
E; ++
P) {
1101 if (!KeyInfoT::isEqual(
P->getFirst(), EmptyKey) &&
1102 !KeyInfoT::isEqual(
P->getFirst(), TombstoneKey)) {
1103 assert(
size_t(TmpEnd - TmpBegin) < InlineBuckets &&
1104 "Too many inline buckets!");
1105 ::new (&TmpEnd->getFirst())
KeyT(std::move(
P->getFirst()));
1106 ::new (&TmpEnd->getSecond())
ValueT(std::move(
P->getSecond()));
1108 P->getSecond().~ValueT();
1110 P->getFirst().~KeyT();
1116 if (AtLeast > InlineBuckets) {
1118 new (getLargeRep()) LargeRep(allocateBuckets(AtLeast));
1120 this->moveFromOldBuckets(TmpBegin, TmpEnd);
1124 LargeRep OldRep = std::move(*getLargeRep());
1125 getLargeRep()->~LargeRep();
1126 if (AtLeast <= InlineBuckets) {
1129 new (getLargeRep()) LargeRep(allocateBuckets(AtLeast));
1132 this->moveFromOldBuckets(OldRep.Buckets, OldRep.Buckets+OldRep.NumBuckets);
1140 unsigned OldSize = this->
size();
1144 unsigned NewNumBuckets = 0;
1147 if (NewNumBuckets > InlineBuckets && NewNumBuckets < 64u)
1150 if ((Small && NewNumBuckets <= InlineBuckets) ||
1151 (!Small && NewNumBuckets == getLargeRep()->NumBuckets)) {
1152 this->BaseT::initEmpty();
1156 deallocateBuckets();
1157 init(NewNumBuckets);
1161 unsigned getNumEntries()
const {
1165 void setNumEntries(
unsigned Num) {
1167 assert(Num < (1U << 31) &&
"Cannot support more than 1<<31 entries");
1171 unsigned getNumTombstones()
const {
1172 return NumTombstones;
1175 void setNumTombstones(
unsigned Num) {
1176 NumTombstones = Num;
1179 const BucketT *getInlineBuckets()
const {
1184 return reinterpret_cast<const BucketT *
>(&storage);
1187 BucketT *getInlineBuckets() {
1188 return const_cast<BucketT *
>(
1189 const_cast<const SmallDenseMap *
>(
this)->getInlineBuckets());
1192 const LargeRep *getLargeRep()
const {
1195 return reinterpret_cast<const LargeRep *
>(&storage);
1198 LargeRep *getLargeRep() {
1199 return const_cast<LargeRep *
>(
1200 const_cast<const SmallDenseMap *
>(
this)->getLargeRep());
1203 const BucketT *getBuckets()
const {
1204 return Small ? getInlineBuckets() : getLargeRep()->Buckets;
1207 BucketT *getBuckets() {
1208 return const_cast<BucketT *
>(
1209 const_cast<const SmallDenseMap *
>(
this)->getBuckets());
1212 unsigned getNumBuckets()
const {
1213 return Small ? InlineBuckets : getLargeRep()->NumBuckets;
1216 void deallocateBuckets() {
1221 sizeof(BucketT) * getLargeRep()->NumBuckets,
1223 getLargeRep()->~LargeRep();
1226 LargeRep allocateBuckets(
unsigned Num) {
1227 assert(Num > InlineBuckets &&
"Must allocate more buckets than are inline");
1229 sizeof(BucketT) * Num,
alignof(BucketT))),
1235template <
typename KeyT,
typename ValueT,
typename KeyInfoT,
typename Bucket,
1243 using value_type = std::conditional_t<IsConst, const Bucket, Bucket>;
1256 bool NoAdvance =
false)
1258 assert(isHandleInSync() &&
"invalid construction!");
1260 if (NoAdvance)
return;
1261 if (shouldReverseIterate<KeyT>()) {
1262 RetreatPastEmptyBuckets();
1265 AdvancePastEmptyBuckets();
1271 template <
bool IsConstSrc,
1272 typename = std::enable_if_t<!IsConstSrc && IsConst>>
1278 assert(isHandleInSync() &&
"invalid iterator access!");
1280 if (shouldReverseIterate<KeyT>())
1285 assert(isHandleInSync() &&
"invalid iterator access!");
1287 if (shouldReverseIterate<KeyT>())
1294 assert((!
LHS.Ptr ||
LHS.isHandleInSync()) &&
"handle not in sync!");
1295 assert((!
RHS.Ptr ||
RHS.isHandleInSync()) &&
"handle not in sync!");
1296 assert(
LHS.getEpochAddress() ==
RHS.getEpochAddress() &&
1297 "comparing incomparable iterators!");
1298 return LHS.Ptr ==
RHS.Ptr;
1307 assert(isHandleInSync() &&
"invalid iterator access!");
1309 if (shouldReverseIterate<KeyT>()) {
1311 RetreatPastEmptyBuckets();
1315 AdvancePastEmptyBuckets();
1319 assert(isHandleInSync() &&
"invalid iterator access!");
1324 void AdvancePastEmptyBuckets() {
1326 const KeyT Empty = KeyInfoT::getEmptyKey();
1327 const KeyT Tombstone = KeyInfoT::getTombstoneKey();
1329 while (
Ptr !=
End && (KeyInfoT::isEqual(
Ptr->getFirst(), Empty) ||
1330 KeyInfoT::isEqual(
Ptr->getFirst(), Tombstone)))
1334 void RetreatPastEmptyBuckets() {
1336 const KeyT Empty = KeyInfoT::getEmptyKey();
1337 const KeyT Tombstone = KeyInfoT::getTombstoneKey();
1339 while (
Ptr !=
End && (KeyInfoT::isEqual(
Ptr[-1].getFirst(), Empty) ||
1340 KeyInfoT::isEqual(
Ptr[-1].getFirst(), Tombstone)))
1345template <
typename KeyT,
typename ValueT,
typename KeyInfoT>
1347 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'.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static int Lookup(ArrayRef< TableEntry > Table, unsigned Opcode)
ValueT & getOrInsertDefault(const KeyT &Key)
Returns the value associated to the key in the map if it exists.
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()
const ValueT & at(const_arg_type_t< KeyT > Val) const
at - Return the entry for the specified key, or abort if no such entry exists.
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)
bool contains(const_arg_type_t< KeyT > Val) const
Return true if the specified key is in the map, false otherwise.
value_type & FindAndConstruct(const KeyT &Key)
const_iterator begin() const
const void * getPointerIntoBucketsArray() const
getPointerIntoBucketsArray() - Return an opaque pointer into the buckets array.
std::pair< iterator, bool > insert_or_assign(KeyT &&Key, V &&Val)
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
ValueT & getOrInsertDefault(KeyT &&Key)
Returns the value associated to the key in the map if it exists.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
std::pair< iterator, bool > insert_or_assign(const KeyT &Key, V &&Val)
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.
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
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.
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
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.
Implement std::hash so that hash_code can be used in STL containers.
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