14 #ifndef LLVM_ADT_DENSEMAP_H
15 #define LLVM_ADT_DENSEMAP_H
29 #include <initializer_list>
32 #include <type_traits>
41 template <
typename KeyT,
typename ValueT>
43 using std::pair<KeyT, ValueT>::pair;
46 const KeyT &
getFirst()
const {
return std::pair<KeyT, ValueT>::first; }
54 typename KeyInfoT = DenseMapInfo<KeyT>,
59 template <
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);
99 return getNumEntries() == 0;
101 unsigned size()
const {
return getNumEntries(); }
108 if (NumBuckets > getNumBuckets())
114 if (getNumEntries() == 0 && getNumTombstones() == 0)
return;
118 if (getNumEntries() * 4 < getNumBuckets() && getNumBuckets() > 64) {
124 if (std::is_trivially_destructible<ValueT>::value) {
126 for (BucketT *
P = getBuckets(), *
E = getBucketsEnd();
P !=
E; ++
P)
127 P->getFirst() = EmptyKey;
129 unsigned NumEntries = getNumEntries();
130 for (BucketT *
P = getBuckets(), *
E = getBucketsEnd();
P !=
E; ++
P) {
133 P->getSecond().~ValueT();
136 P->getFirst() = EmptyKey;
139 assert(NumEntries == 0 &&
"Node count imbalance!");
148 const BucketT *TheBucket;
149 return LookupBucketFor(Val, TheBucket) ? 1 : 0;
154 if (LookupBucketFor(Val, TheBucket))
155 return makeIterator(TheBucket,
156 shouldReverseIterate<KeyT>() ? getBuckets()
162 const BucketT *TheBucket;
163 if (LookupBucketFor(Val, TheBucket))
164 return makeConstIterator(TheBucket,
165 shouldReverseIterate<KeyT>() ? getBuckets()
176 template<
class LookupKeyT>
179 if (LookupBucketFor(Val, TheBucket))
180 return makeIterator(TheBucket,
181 shouldReverseIterate<KeyT>() ? getBuckets()
186 template<
class LookupKeyT>
188 const BucketT *TheBucket;
189 if (LookupBucketFor(Val, TheBucket))
190 return makeConstIterator(TheBucket,
191 shouldReverseIterate<KeyT>() ? getBuckets()
200 const BucketT *TheBucket;
201 if (LookupBucketFor(Val, TheBucket))
202 return TheBucket->getSecond();
209 std::pair<iterator, bool>
insert(
const std::pair<KeyT, ValueT> &KV) {
216 std::pair<iterator, bool>
insert(std::pair<KeyT, ValueT> &&KV) {
223 template <
typename... Ts>
226 if (LookupBucketFor(
Key, TheBucket))
227 return std::make_pair(makeIterator(TheBucket,
228 shouldReverseIterate<KeyT>()
237 return std::make_pair(makeIterator(TheBucket,
238 shouldReverseIterate<KeyT>()
248 template <
typename... Ts>
251 if (LookupBucketFor(
Key, TheBucket))
252 return std::make_pair(makeIterator(TheBucket,
253 shouldReverseIterate<KeyT>()
260 TheBucket = InsertIntoBucket(TheBucket,
Key, std::forward<Ts>(
Args)...);
261 return std::make_pair(makeIterator(TheBucket,
262 shouldReverseIterate<KeyT>()
274 template <
typename LookupKeyT>
275 std::pair<iterator, bool>
insert_as(std::pair<KeyT, ValueT> &&KV,
276 const LookupKeyT &Val) {
278 if (LookupBucketFor(Val, TheBucket))
279 return std::make_pair(makeIterator(TheBucket,
280 shouldReverseIterate<KeyT>()
287 TheBucket = InsertIntoBucketWithLookup(TheBucket,
std::move(KV.first),
289 return std::make_pair(makeIterator(TheBucket,
290 shouldReverseIterate<KeyT>()
298 template<
typename InputIt>
306 if (!LookupBucketFor(Val, TheBucket))
309 TheBucket->getSecond().~ValueT();
311 decrementNumEntries();
312 incrementNumTombstones();
316 BucketT *TheBucket = &*
I;
317 TheBucket->getSecond().~ValueT();
319 decrementNumEntries();
320 incrementNumTombstones();
325 if (LookupBucketFor(
Key, TheBucket))
328 return *InsertIntoBucket(TheBucket,
Key);
337 if (LookupBucketFor(
Key, TheBucket))
351 return Ptr >= getBuckets() && Ptr < getBucketsEnd();
363 if (getNumBuckets() == 0)
367 for (BucketT *
P = getBuckets(), *
E = getBucketsEnd();
P !=
E; ++
P) {
370 P->getSecond().~ValueT();
371 P->getFirst().~KeyT();
379 assert((getNumBuckets() & (getNumBuckets()-1)) == 0 &&
380 "# initial buckets must be a power of two!");
382 for (BucketT *
B = getBuckets(), *
E = getBucketsEnd();
B !=
E; ++
B)
383 ::
new (&
B->getFirst())
KeyT(EmptyKey);
403 for (BucketT *
B = OldBucketsBegin, *
E = OldBucketsEnd;
B !=
E; ++
B) {
408 bool FoundVal = LookupBucketFor(
B->getFirst(), DestBucket);
410 assert(!FoundVal &&
"Key already in new map?");
411 DestBucket->getFirst() =
std::move(
B->getFirst());
413 incrementNumEntries();
416 B->getSecond().~ValueT();
418 B->getFirst().~KeyT();
422 template <
typename OtherBaseT>
426 assert(getNumBuckets() == other.getNumBuckets());
428 setNumEntries(other.getNumEntries());
429 setNumTombstones(other.getNumTombstones());
431 if (std::is_trivially_copyable<KeyT>::value &&
432 std::is_trivially_copyable<ValueT>::value)
433 memcpy(
reinterpret_cast<void *
>(getBuckets()), other.getBuckets(),
434 getNumBuckets() *
sizeof(BucketT));
436 for (
size_t i = 0;
i < getNumBuckets(); ++
i) {
437 ::new (&getBuckets()[
i].getFirst())
438 KeyT(other.getBuckets()[
i].getFirst());
441 ::new (&getBuckets()[
i].getSecond())
442 ValueT(other.getBuckets()[
i].getSecond());
447 return KeyInfoT::getHashValue(Val);
450 template<
typename LookupKeyT>
452 return KeyInfoT::getHashValue(Val);
456 static_assert(std::is_base_of<DenseMapBase, DerivedT>::value,
457 "Must pass the derived type to this template!");
458 return KeyInfoT::getEmptyKey();
462 return KeyInfoT::getTombstoneKey();
468 bool NoAdvance=
false) {
469 if (shouldReverseIterate<KeyT>()) {
470 BucketT *
B =
P == getBucketsEnd() ? getBuckets() :
P + 1;
477 const DebugEpochBase &Epoch,
478 const bool NoAdvance=
false)
const {
479 if (shouldReverseIterate<KeyT>()) {
480 const BucketT *
B =
P == getBucketsEnd() ? getBuckets() :
P + 1;
486 unsigned getNumEntries()
const {
487 return static_cast<const DerivedT *
>(
this)->getNumEntries();
490 void setNumEntries(
unsigned Num) {
491 static_cast<DerivedT *
>(
this)->setNumEntries(Num);
494 void incrementNumEntries() {
495 setNumEntries(getNumEntries() + 1);
498 void decrementNumEntries() {
499 setNumEntries(getNumEntries() - 1);
502 unsigned getNumTombstones()
const {
503 return static_cast<const DerivedT *
>(
this)->getNumTombstones();
506 void setNumTombstones(
unsigned Num) {
507 static_cast<DerivedT *
>(
this)->setNumTombstones(Num);
510 void incrementNumTombstones() {
511 setNumTombstones(getNumTombstones() + 1);
514 void decrementNumTombstones() {
515 setNumTombstones(getNumTombstones() - 1);
518 const BucketT *getBuckets()
const {
519 return static_cast<const DerivedT *
>(
this)->getBuckets();
522 BucketT *getBuckets() {
523 return static_cast<DerivedT *
>(
this)->getBuckets();
526 unsigned getNumBuckets()
const {
527 return static_cast<const DerivedT *
>(
this)->getNumBuckets();
530 BucketT *getBucketsEnd() {
531 return getBuckets() + getNumBuckets();
534 const BucketT *getBucketsEnd()
const {
535 return getBuckets() + getNumBuckets();
538 void grow(
unsigned AtLeast) {
539 static_cast<DerivedT *
>(
this)->grow(AtLeast);
542 void shrink_and_clear() {
543 static_cast<DerivedT *
>(
this)->shrink_and_clear();
546 template <
typename KeyArg,
typename... ValueArgs>
547 BucketT *InsertIntoBucket(BucketT *TheBucket, KeyArg &&
Key,
548 ValueArgs &&... Values) {
549 TheBucket = InsertIntoBucketImpl(
Key,
Key, TheBucket);
551 TheBucket->getFirst() = std::forward<KeyArg>(
Key);
552 ::new (&TheBucket->getSecond())
ValueT(
std::forward<ValueArgs>(Values)...);
556 template <typename LookupKeyT>
557 BucketT *InsertIntoBucketWithLookup(BucketT *TheBucket,
KeyT &&
Key,
559 TheBucket = InsertIntoBucketImpl(
Key,
Lookup, TheBucket);
566 template <typename LookupKeyT>
568 BucketT *TheBucket) {
580 unsigned NewNumEntries = getNumEntries() + 1;
581 unsigned NumBuckets = getNumBuckets();
583 this->grow(NumBuckets * 2);
584 LookupBucketFor(
Lookup, TheBucket);
585 NumBuckets = getNumBuckets();
586 }
else if (
LLVM_UNLIKELY(NumBuckets-(NewNumEntries+getNumTombstones()) <=
588 this->grow(NumBuckets);
589 LookupBucketFor(
Lookup, TheBucket);
595 incrementNumEntries();
600 decrementNumTombstones();
609 template<
typename LookupKeyT>
610 bool LookupBucketFor(
const LookupKeyT &Val,
611 const BucketT *&FoundBucket)
const {
612 const BucketT *BucketsPtr = getBuckets();
613 const unsigned NumBuckets = getNumBuckets();
615 if (NumBuckets == 0) {
616 FoundBucket =
nullptr;
621 const BucketT *FoundTombstone =
nullptr;
626 "Empty/Tombstone value shouldn't be inserted into map!");
629 unsigned ProbeAmt = 1;
631 const BucketT *ThisBucket = BucketsPtr + BucketNo;
634 FoundBucket = ThisBucket;
643 FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket;
651 FoundTombstone = ThisBucket;
655 BucketNo += ProbeAmt++;
656 BucketNo &= (NumBuckets-1);
660 template <
typename LookupKeyT>
661 bool LookupBucketFor(
const LookupKeyT &Val, BucketT *&FoundBucket) {
662 const BucketT *ConstFoundBucket;
664 ->LookupBucketFor(Val, ConstFoundBucket);
665 FoundBucket =
const_cast<BucketT *
>(ConstFoundBucket);
675 return getNumBuckets() *
sizeof(BucketT);
685 template <
typename DerivedT,
typename KeyT,
typename ValueT,
typename KeyInfoT,
690 if (
LHS.size() !=
RHS.size())
693 for (
auto &KV :
LHS) {
694 auto I =
RHS.find(KV.first);
695 if (
I ==
RHS.end() ||
I->second != KV.second)
705 template <
typename DerivedT,
typename KeyT,
typename ValueT,
typename KeyInfoT,
714 typename KeyInfoT = DenseMapInfo<KeyT>,
717 KeyT, ValueT, KeyInfoT, BucketT> {
726 unsigned NumTombstones;
732 explicit DenseMap(
unsigned InitialReserve = 0) {
init(InitialReserve); }
744 template<
typename InputIt>
746 init(std::distance(
I,
E));
750 DenseMap(std::initializer_list<typename BaseT::value_type> Vals) {
752 this->
insert(Vals.begin(), Vals.end());
786 if (allocateBuckets(other.NumBuckets)) {
787 this->BaseT::copyFrom(other);
794 void init(
unsigned InitNumEntries) {
796 if (allocateBuckets(InitBuckets)) {
797 this->BaseT::initEmpty();
805 unsigned OldNumBuckets = NumBuckets;
806 BucketT *OldBuckets = Buckets;
808 allocateBuckets(std::max<unsigned>(64,
static_cast<unsigned>(
NextPowerOf2(AtLeast-1))));
811 this->BaseT::initEmpty();
823 unsigned OldNumBuckets = NumBuckets;
824 unsigned OldNumEntries = NumEntries;
828 unsigned NewNumBuckets = 0;
831 if (NewNumBuckets == NumBuckets) {
832 this->BaseT::initEmpty();
842 unsigned getNumEntries()
const {
846 void setNumEntries(
unsigned Num) {
850 unsigned getNumTombstones()
const {
851 return NumTombstones;
854 void setNumTombstones(
unsigned Num) {
858 BucketT *getBuckets()
const {
862 unsigned getNumBuckets()
const {
866 bool allocateBuckets(
unsigned Num) {
868 if (NumBuckets == 0) {
873 Buckets =
static_cast<BucketT *
>(
879 template <
typename KeyT,
typename ValueT,
unsigned InlineBuckets = 4,
880 typename KeyInfoT = DenseMapInfo<KeyT>,
884 SmallDenseMap<KeyT, ValueT, InlineBuckets, KeyInfoT, BucketT>, KeyT,
885 ValueT, KeyInfoT, BucketT> {
893 "InlineBuckets must be a power of 2.");
896 unsigned NumEntries : 31;
897 unsigned NumTombstones;
910 init(NumInitBuckets);
923 template<
typename InputIt>
938 unsigned TmpNumEntries =
RHS.NumEntries;
939 RHS.NumEntries = NumEntries;
940 NumEntries = TmpNumEntries;
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];
957 if (hasLHSValue && hasRHSValue) {
963 std::swap(LHSB->getFirst(), RHSB->getFirst());
966 LHSB->getSecond().~ValueT();
967 }
else if (hasRHSValue) {
969 RHSB->getSecond().~ValueT();
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];
995 OldB->getFirst().~KeyT();
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;
1057 for (BucketT *
P = getBuckets(), *
E =
P + InlineBuckets;
P !=
E; ++
P) {
1060 assert(
size_t(TmpEnd - TmpBegin) < InlineBuckets &&
1061 "Too many inline buckets!");
1065 P->getSecond().~ValueT();
1067 P->getFirst().~KeyT();
1073 if (AtLeast > InlineBuckets) {
1075 new (getLargeRep()) LargeRep(allocateBuckets(AtLeast));
1081 LargeRep OldRep =
std::move(*getLargeRep());
1082 getLargeRep()->~LargeRep();
1083 if (AtLeast <= InlineBuckets) {
1086 new (getLargeRep()) LargeRep(allocateBuckets(AtLeast));
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))),
1192 template <
typename KeyT,
typename ValueT,
typename KeyInfoT,
typename Bucket,
1194 class DenseMapIterator : DebugEpochBase::HandleBase {
1214 bool NoAdvance =
false)
1216 assert(isHandleInSync() &&
"invalid construction!");
1218 if (NoAdvance)
return;
1219 if (shouldReverseIterate<KeyT>()) {
1220 RetreatPastEmptyBuckets();
1223 AdvancePastEmptyBuckets();
1229 template <
bool IsConstSrc,
1230 typename = std::enable_if_t<!IsConstSrc && IsConst>>
1236 assert(isHandleInSync() &&
"invalid iterator access!");
1237 assert(Ptr != End &&
"dereferencing end() iterator");
1238 if (shouldReverseIterate<KeyT>())
1243 assert(isHandleInSync() &&
"invalid iterator access!");
1244 assert(Ptr != End &&
"dereferencing end() iterator");
1245 if (shouldReverseIterate<KeyT>())
1252 assert((!
LHS.Ptr ||
LHS.isHandleInSync()) &&
"handle not in sync!");
1253 assert((!
RHS.Ptr ||
RHS.isHandleInSync()) &&
"handle not in sync!");
1254 assert(
LHS.getEpochAddress() ==
RHS.getEpochAddress() &&
1255 "comparing incomparable iterators!");
1256 return LHS.Ptr ==
RHS.Ptr;
1265 assert(isHandleInSync() &&
"invalid iterator access!");
1266 assert(Ptr != End &&
"incrementing end() iterator");
1267 if (shouldReverseIterate<KeyT>()) {
1269 RetreatPastEmptyBuckets();
1273 AdvancePastEmptyBuckets();
1277 assert(isHandleInSync() &&
"invalid iterator access!");
1282 void AdvancePastEmptyBuckets() {
1284 const KeyT
Empty = KeyInfoT::getEmptyKey();
1285 const KeyT Tombstone = KeyInfoT::getTombstoneKey();
1292 void RetreatPastEmptyBuckets() {
1294 const KeyT Empty = KeyInfoT::getEmptyKey();
1295 const KeyT Tombstone = KeyInfoT::getTombstoneKey();
1303 template <
typename KeyT,
typename ValueT,
typename KeyInfoT>
1305 return X.getMemorySize();
1310 #endif // LLVM_ADT_DENSEMAP_H