14 #ifndef WPIUTIL_WPI_DENSEMAP_H
15 #define WPIUTIL_WPI_DENSEMAP_H
17 #include "wpi/DenseMapInfo.h"
18 #include "wpi/EpochTracker.h"
19 #include "wpi/AlignOf.h"
20 #include "wpi/Compiler.h"
21 #include "wpi/MathExtras.h"
22 #include "wpi/PointerLikeTypeTraits.h"
23 #include "wpi/type_traits.h"
30 #include <type_traits>
39 template <
typename KeyT,
typename ValueT>
41 KeyT &getFirst() {
return std::pair<KeyT, ValueT>::first; }
42 const KeyT &getFirst()
const {
return std::pair<KeyT, ValueT>::first; }
43 ValueT &getSecond() {
return std::pair<KeyT, ValueT>::second; }
44 const ValueT &getSecond()
const {
return std::pair<KeyT, ValueT>::second; }
49 template <
typename KeyT,
typename ValueT,
55 template <
typename DerivedT,
typename KeyT,
typename ValueT,
typename KeyInfoT,
59 using const_arg_type_t =
typename const_pointer_or_const_ref<T>::type;
62 using size_type = unsigned;
63 using key_type = KeyT;
64 using mapped_type = ValueT;
65 using value_type = BucketT;
76 return makeIterator(getBuckets(), getBucketsEnd(), *
this);
79 return makeIterator(getBucketsEnd(), getBucketsEnd(), *
this,
true);
84 return makeConstIterator(getBuckets(), getBucketsEnd(), *
this);
87 return makeConstIterator(getBucketsEnd(), getBucketsEnd(), *
this,
true);
90 LLVM_NODISCARD
bool empty()
const {
91 return getNumEntries() == 0;
93 unsigned size()
const {
return getNumEntries(); }
100 if (NumBuckets > getNumBuckets())
106 if (getNumEntries() == 0 && getNumTombstones() == 0)
return;
110 if (getNumEntries() * 4 < getNumBuckets() && getNumBuckets() > 64) {
115 const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
116 if (isPodLike<KeyT>::value && isPodLike<ValueT>::value) {
118 for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P)
119 P->getFirst() = EmptyKey;
121 unsigned NumEntries = getNumEntries();
122 for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) {
123 if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey)) {
124 if (!KeyInfoT::isEqual(P->getFirst(), TombstoneKey)) {
125 P->getSecond().~ValueT();
128 P->getFirst() = EmptyKey;
131 assert(NumEntries == 0 &&
"Node count imbalance!");
138 size_type
count(const_arg_type_t<KeyT> Val)
const {
139 const BucketT *TheBucket;
140 return LookupBucketFor(Val, TheBucket) ? 1 : 0;
143 iterator find(const_arg_type_t<KeyT> Val) {
145 if (LookupBucketFor(Val, TheBucket))
146 return makeIterator(TheBucket, getBucketsEnd(), *
this,
true);
149 const_iterator find(const_arg_type_t<KeyT> Val)
const {
150 const BucketT *TheBucket;
151 if (LookupBucketFor(Val, TheBucket))
152 return makeConstIterator(TheBucket, getBucketsEnd(), *
this,
true);
161 template<
class LookupKeyT>
164 if (LookupBucketFor(Val, TheBucket))
165 return makeIterator(TheBucket, getBucketsEnd(), *
this,
true);
168 template<
class LookupKeyT>
169 const_iterator
find_as(
const LookupKeyT &Val)
const {
170 const BucketT *TheBucket;
171 if (LookupBucketFor(Val, TheBucket))
172 return makeConstIterator(TheBucket, getBucketsEnd(), *
this,
true);
178 ValueT
lookup(const_arg_type_t<KeyT> Val)
const {
179 const BucketT *TheBucket;
180 if (LookupBucketFor(Val, TheBucket))
181 return TheBucket->getSecond();
188 std::pair<iterator, bool> insert(
const std::pair<KeyT, ValueT> &KV) {
189 return try_emplace(KV.first, KV.second);
195 std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) {
196 return try_emplace(std::move(KV.first), std::move(KV.second));
202 template <
typename... Ts>
203 std::pair<iterator, bool> try_emplace(KeyT &&Key, Ts &&... Args) {
205 if (LookupBucketFor(Key, TheBucket))
206 return std::make_pair(
207 makeIterator(TheBucket, getBucketsEnd(), *
this,
true),
212 InsertIntoBucket(TheBucket, std::move(Key), std::forward<Ts>(Args)...);
213 return std::make_pair(
214 makeIterator(TheBucket, getBucketsEnd(), *
this,
true),
221 template <
typename... Ts>
222 std::pair<iterator, bool> try_emplace(
const KeyT &Key, Ts &&... Args) {
224 if (LookupBucketFor(Key, TheBucket))
225 return std::make_pair(
226 makeIterator(TheBucket, getBucketsEnd(), *
this,
true),
230 TheBucket = InsertIntoBucket(TheBucket, Key, std::forward<Ts>(Args)...);
231 return std::make_pair(
232 makeIterator(TheBucket, getBucketsEnd(), *
this,
true),
241 template <
typename LookupKeyT>
242 std::pair<iterator, bool>
insert_as(std::pair<KeyT, ValueT> &&KV,
243 const LookupKeyT &Val) {
245 if (LookupBucketFor(Val, TheBucket))
246 return std::make_pair(
247 makeIterator(TheBucket, getBucketsEnd(), *
this,
true),
251 TheBucket = InsertIntoBucketWithLookup(TheBucket, std::move(KV.first),
252 std::move(KV.second), Val);
253 return std::make_pair(
254 makeIterator(TheBucket, getBucketsEnd(), *
this,
true),
259 template<
typename InputIt>
265 bool erase(
const KeyT &Val) {
267 if (!LookupBucketFor(Val, TheBucket))
270 TheBucket->getSecond().~ValueT();
271 TheBucket->getFirst() = getTombstoneKey();
272 decrementNumEntries();
273 incrementNumTombstones();
276 void erase(iterator I) {
277 BucketT *TheBucket = &*I;
278 TheBucket->getSecond().~ValueT();
279 TheBucket->getFirst() = getTombstoneKey();
280 decrementNumEntries();
281 incrementNumTombstones();
284 value_type& FindAndConstruct(
const KeyT &Key) {
286 if (LookupBucketFor(Key, TheBucket))
289 return *InsertIntoBucket(TheBucket, Key);
292 ValueT &operator[](
const KeyT &Key) {
293 return FindAndConstruct(Key).second;
296 value_type& FindAndConstruct(KeyT &&Key) {
298 if (LookupBucketFor(Key, TheBucket))
301 return *InsertIntoBucket(TheBucket, std::move(Key));
304 ValueT &operator[](KeyT &&Key) {
305 return FindAndConstruct(std::move(Key)).second;
312 return Ptr >= getBuckets() && Ptr < getBucketsEnd();
324 if (getNumBuckets() == 0)
327 const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
328 for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) {
329 if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey) &&
330 !KeyInfoT::isEqual(P->getFirst(), TombstoneKey))
331 P->getSecond().~ValueT();
332 P->getFirst().~KeyT();
340 assert((getNumBuckets() & (getNumBuckets()-1)) == 0 &&
341 "# initial buckets must be a power of two!");
342 const KeyT EmptyKey = getEmptyKey();
343 for (BucketT *B = getBuckets(), *E = getBucketsEnd(); B != E; ++B)
344 ::
new (&B->getFirst()) KeyT(EmptyKey);
355 return static_cast<unsigned>(
NextPowerOf2(NumEntries * 4 / 3 + 1));
358 void moveFromOldBuckets(BucketT *OldBucketsBegin, BucketT *OldBucketsEnd) {
362 const KeyT EmptyKey = getEmptyKey();
363 const KeyT TombstoneKey = getTombstoneKey();
364 for (BucketT *B = OldBucketsBegin, *E = OldBucketsEnd; B != E; ++B) {
365 if (!KeyInfoT::isEqual(B->getFirst(), EmptyKey) &&
366 !KeyInfoT::isEqual(B->getFirst(), TombstoneKey)) {
369 bool FoundVal = LookupBucketFor(B->getFirst(), DestBucket);
371 assert(!FoundVal &&
"Key already in new map?");
372 DestBucket->getFirst() = std::move(B->getFirst());
373 ::new (&DestBucket->getSecond()) ValueT(std::move(B->getSecond()));
374 incrementNumEntries();
377 B->getSecond().~ValueT();
379 B->getFirst().~KeyT();
383 template <
typename OtherBaseT>
385 const DenseMapBase<OtherBaseT, KeyT, ValueT, KeyInfoT, BucketT> &other) {
386 assert(&other !=
this);
387 assert(getNumBuckets() == other.getNumBuckets());
389 setNumEntries(other.getNumEntries());
390 setNumTombstones(other.getNumTombstones());
392 if (isPodLike<KeyT>::value && isPodLike<ValueT>::value)
393 memcpy(reinterpret_cast<void *>(getBuckets()), other.getBuckets(),
394 getNumBuckets() *
sizeof(BucketT));
396 for (
size_t i = 0; i < getNumBuckets(); ++i) {
397 ::new (&getBuckets()[i].getFirst())
398 KeyT(other.getBuckets()[i].getFirst());
399 if (!KeyInfoT::isEqual(getBuckets()[i].getFirst(), getEmptyKey()) &&
400 !KeyInfoT::isEqual(getBuckets()[i].getFirst(), getTombstoneKey()))
401 ::new (&getBuckets()[i].getSecond())
402 ValueT(other.getBuckets()[i].getSecond());
406 static
unsigned getHashValue(const KeyT &Val) {
407 return KeyInfoT::getHashValue(Val);
410 template<
typename LookupKeyT>
411 static unsigned getHashValue(
const LookupKeyT &Val) {
412 return KeyInfoT::getHashValue(Val);
415 static const KeyT getEmptyKey() {
416 static_assert(std::is_base_of<DenseMapBase, DerivedT>::value,
417 "Must pass the derived type to this template!");
418 return KeyInfoT::getEmptyKey();
421 static const KeyT getTombstoneKey() {
422 return KeyInfoT::getTombstoneKey();
426 iterator makeIterator(BucketT *P, BucketT *E,
427 DebugEpochBase &Epoch,
428 bool NoAdvance=
false) {
429 return iterator(P, E, Epoch, NoAdvance);
432 const_iterator makeConstIterator(
const BucketT *P,
const BucketT *E,
433 const DebugEpochBase &Epoch,
434 const bool NoAdvance=
false)
const {
435 return const_iterator(P, E, Epoch, NoAdvance);
438 unsigned getNumEntries()
const {
439 return static_cast<const DerivedT *>(
this)->getNumEntries();
442 void setNumEntries(
unsigned Num) {
443 static_cast<DerivedT *>(
this)->setNumEntries(Num);
446 void incrementNumEntries() {
447 setNumEntries(getNumEntries() + 1);
450 void decrementNumEntries() {
451 setNumEntries(getNumEntries() - 1);
454 unsigned getNumTombstones()
const {
455 return static_cast<const DerivedT *>(
this)->getNumTombstones();
458 void setNumTombstones(
unsigned Num) {
459 static_cast<DerivedT *>(
this)->setNumTombstones(Num);
462 void incrementNumTombstones() {
463 setNumTombstones(getNumTombstones() + 1);
466 void decrementNumTombstones() {
467 setNumTombstones(getNumTombstones() - 1);
470 const BucketT *getBuckets()
const {
471 return static_cast<const DerivedT *>(
this)->getBuckets();
474 BucketT *getBuckets() {
475 return static_cast<DerivedT *>(
this)->getBuckets();
478 unsigned getNumBuckets()
const {
479 return static_cast<const DerivedT *>(
this)->getNumBuckets();
482 BucketT *getBucketsEnd() {
483 return getBuckets() + getNumBuckets();
486 const BucketT *getBucketsEnd()
const {
487 return getBuckets() + getNumBuckets();
490 void grow(
unsigned AtLeast) {
491 static_cast<DerivedT *>(
this)->grow(AtLeast);
494 void shrink_and_clear() {
495 static_cast<DerivedT *>(
this)->shrink_and_clear();
498 template <
typename KeyArg,
typename... ValueArgs>
499 BucketT *InsertIntoBucket(BucketT *TheBucket, KeyArg &&Key,
500 ValueArgs &&... Values) {
501 TheBucket = InsertIntoBucketImpl(Key, Key, TheBucket);
503 TheBucket->getFirst() = std::forward<KeyArg>(Key);
504 ::new (&TheBucket->getSecond()) ValueT(std::forward<ValueArgs>(Values)...);
508 template <
typename LookupKeyT>
509 BucketT *InsertIntoBucketWithLookup(BucketT *TheBucket, KeyT &&Key,
510 ValueT &&Value, LookupKeyT &Lookup) {
511 TheBucket = InsertIntoBucketImpl(Key, Lookup, TheBucket);
513 TheBucket->getFirst() = std::move(Key);
514 ::new (&TheBucket->getSecond()) ValueT(std::move(Value));
518 template <
typename LookupKeyT>
519 BucketT *InsertIntoBucketImpl(
const KeyT &Key,
const LookupKeyT &Lookup,
520 BucketT *TheBucket) {
532 unsigned NewNumEntries = getNumEntries() + 1;
533 unsigned NumBuckets = getNumBuckets();
534 if (LLVM_UNLIKELY(NewNumEntries * 4 >= NumBuckets * 3)) {
535 this->grow(NumBuckets * 2);
536 LookupBucketFor(Lookup, TheBucket);
537 NumBuckets = getNumBuckets();
538 }
else if (LLVM_UNLIKELY(NumBuckets-(NewNumEntries+getNumTombstones()) <=
540 this->grow(NumBuckets);
541 LookupBucketFor(Lookup, TheBucket);
547 incrementNumEntries();
550 const KeyT EmptyKey = getEmptyKey();
551 if (!KeyInfoT::isEqual(TheBucket->getFirst(), EmptyKey))
552 decrementNumTombstones();
561 template<
typename LookupKeyT>
562 bool LookupBucketFor(
const LookupKeyT &Val,
563 const BucketT *&FoundBucket)
const {
564 const BucketT *BucketsPtr = getBuckets();
565 const unsigned NumBuckets = getNumBuckets();
567 if (NumBuckets == 0) {
568 FoundBucket =
nullptr;
573 const BucketT *FoundTombstone =
nullptr;
574 const KeyT EmptyKey = getEmptyKey();
575 const KeyT TombstoneKey = getTombstoneKey();
576 assert(!KeyInfoT::isEqual(Val, EmptyKey) &&
577 !KeyInfoT::isEqual(Val, TombstoneKey) &&
578 "Empty/Tombstone value shouldn't be inserted into map!");
580 unsigned BucketNo = getHashValue(Val) & (NumBuckets-1);
581 unsigned ProbeAmt = 1;
583 const BucketT *ThisBucket = BucketsPtr + BucketNo;
585 if (LLVM_LIKELY(KeyInfoT::isEqual(Val, ThisBucket->getFirst()))) {
586 FoundBucket = ThisBucket;
592 if (LLVM_LIKELY(KeyInfoT::isEqual(ThisBucket->getFirst(), EmptyKey))) {
595 FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket;
601 if (KeyInfoT::isEqual(ThisBucket->getFirst(), TombstoneKey) &&
603 FoundTombstone = ThisBucket;
607 BucketNo += ProbeAmt++;
608 BucketNo &= (NumBuckets-1);
612 template <
typename LookupKeyT>
613 bool LookupBucketFor(
const LookupKeyT &Val, BucketT *&FoundBucket) {
614 const BucketT *ConstFoundBucket;
615 bool Result = const_cast<const DenseMapBase *>(
this)
616 ->LookupBucketFor(Val, ConstFoundBucket);
617 FoundBucket = const_cast<BucketT *>(ConstFoundBucket);
627 return getNumBuckets() *
sizeof(BucketT);
637 template <
typename DerivedT,
typename KeyT,
typename ValueT,
typename KeyInfoT,
642 if (LHS.size() != RHS.size())
645 for (
auto &KV : LHS) {
646 auto I = RHS.find(KV.first);
647 if (I == RHS.end() || I->second != KV.second)
657 template <
typename DerivedT,
typename KeyT,
typename ValueT,
typename KeyInfoT,
662 return !(LHS == RHS);
665 template <
typename KeyT,
typename ValueT,
666 typename KeyInfoT = DenseMapInfo<KeyT>,
669 KeyT, ValueT, KeyInfoT, BucketT> {
678 unsigned NumTombstones;
684 explicit DenseMap(
unsigned InitialReserve = 0) { init(InitialReserve); }
691 DenseMap(DenseMap &&other) : BaseT() {
696 template<
typename InputIt>
697 DenseMap(
const InputIt &I,
const InputIt &E) {
698 init(std::distance(I, E));
702 DenseMap(std::initializer_list<typename BaseT::value_type> Vals) {
704 this->insert(Vals.begin(), Vals.end());
709 operator delete(Buckets);
712 void swap(DenseMap& RHS) {
714 RHS.incrementEpoch();
715 std::swap(Buckets, RHS.Buckets);
716 std::swap(NumEntries, RHS.NumEntries);
717 std::swap(NumTombstones, RHS.NumTombstones);
718 std::swap(NumBuckets, RHS.NumBuckets);
721 DenseMap& operator=(
const DenseMap& other) {
727 DenseMap& operator=(DenseMap &&other) {
729 operator delete(Buckets);
735 void copyFrom(
const DenseMap& other) {
737 operator delete(Buckets);
738 if (allocateBuckets(other.NumBuckets)) {
739 this->BaseT::copyFrom(other);
746 void init(
unsigned InitNumEntries) {
747 auto InitBuckets = BaseT::getMinBucketToReserveForEntries(InitNumEntries);
748 if (allocateBuckets(InitBuckets)) {
749 this->BaseT::initEmpty();
756 void grow(
unsigned AtLeast) {
757 unsigned OldNumBuckets = NumBuckets;
758 BucketT *OldBuckets = Buckets;
760 allocateBuckets(std::max<unsigned>(64, static_cast<unsigned>(
NextPowerOf2(AtLeast-1))));
763 this->BaseT::initEmpty();
767 this->moveFromOldBuckets(OldBuckets, OldBuckets+OldNumBuckets);
770 operator delete(OldBuckets);
773 void shrink_and_clear() {
774 unsigned OldNumEntries = NumEntries;
778 unsigned NewNumBuckets = 0;
780 NewNumBuckets = (std::max)(64, 1 << (
Log2_32_Ceil(OldNumEntries) + 1));
781 if (NewNumBuckets == NumBuckets) {
782 this->BaseT::initEmpty();
786 operator delete(Buckets);
791 unsigned getNumEntries()
const {
795 void setNumEntries(
unsigned Num) {
799 unsigned getNumTombstones()
const {
800 return NumTombstones;
803 void setNumTombstones(
unsigned Num) {
807 BucketT *getBuckets()
const {
811 unsigned getNumBuckets()
const {
815 bool allocateBuckets(
unsigned Num) {
817 if (NumBuckets == 0) {
822 Buckets = static_cast<BucketT*>(
operator new(
sizeof(BucketT) * NumBuckets));
827 template <
typename KeyT,
typename ValueT,
unsigned InlineBuckets = 4,
828 typename KeyInfoT = DenseMapInfo<KeyT>,
832 SmallDenseMap<KeyT, ValueT, InlineBuckets, KeyInfoT, BucketT>, KeyT,
833 ValueT, KeyInfoT, BucketT> {
841 "InlineBuckets must be a power of 2.");
844 unsigned NumEntries : 31;
845 unsigned NumTombstones;
858 init(NumInitBuckets);
871 template<
typename InputIt>
883 unsigned TmpNumEntries = RHS.NumEntries;
884 RHS.NumEntries = NumEntries;
885 NumEntries = TmpNumEntries;
886 std::swap(NumTombstones, RHS.NumTombstones);
888 const KeyT EmptyKey = this->getEmptyKey();
889 const KeyT TombstoneKey = this->getTombstoneKey();
890 if (Small && RHS.Small) {
895 for (
unsigned i = 0, e = InlineBuckets; i != e; ++i) {
896 BucketT *LHSB = &getInlineBuckets()[i],
897 *RHSB = &RHS.getInlineBuckets()[i];
898 bool hasLHSValue = (!KeyInfoT::isEqual(LHSB->getFirst(), EmptyKey) &&
899 !KeyInfoT::isEqual(LHSB->getFirst(), TombstoneKey));
900 bool hasRHSValue = (!KeyInfoT::isEqual(RHSB->getFirst(), EmptyKey) &&
901 !KeyInfoT::isEqual(RHSB->getFirst(), TombstoneKey));
902 if (hasLHSValue && hasRHSValue) {
904 std::swap(*LHSB, *RHSB);
908 std::swap(LHSB->getFirst(), RHSB->getFirst());
910 ::new (&RHSB->getSecond()) ValueT(std::move(LHSB->getSecond()));
911 LHSB->getSecond().~ValueT();
912 }
else if (hasRHSValue) {
913 ::new (&LHSB->getSecond()) ValueT(std::move(RHSB->getSecond()));
914 RHSB->getSecond().~ValueT();
919 if (!Small && !RHS.Small) {
920 std::swap(getLargeRep()->Buckets, RHS.getLargeRep()->Buckets);
921 std::swap(getLargeRep()->NumBuckets, RHS.getLargeRep()->NumBuckets);
929 LargeRep TmpRep = std::move(*LargeSide.getLargeRep());
930 LargeSide.getLargeRep()->~LargeRep();
931 LargeSide.Small =
true;
936 for (
unsigned i = 0, e = InlineBuckets; i != e; ++i) {
937 BucketT *NewB = &LargeSide.getInlineBuckets()[i],
938 *OldB = &SmallSide.getInlineBuckets()[i];
939 ::new (&NewB->getFirst()) KeyT(std::move(OldB->getFirst()));
940 OldB->getFirst().~KeyT();
941 if (!KeyInfoT::isEqual(NewB->getFirst(), EmptyKey) &&
942 !KeyInfoT::isEqual(NewB->getFirst(), TombstoneKey)) {
943 ::new (&NewB->getSecond()) ValueT(std::move(OldB->getSecond()));
944 OldB->getSecond().~ValueT();
950 SmallSide.Small =
false;
951 new (SmallSide.getLargeRep()) LargeRep(std::move(TmpRep));
972 if (other.getNumBuckets() > InlineBuckets) {
974 new (getLargeRep()) LargeRep(allocateBuckets(other.getNumBuckets()));
976 this->BaseT::copyFrom(other);
979 void init(
unsigned InitBuckets) {
981 if (InitBuckets > InlineBuckets) {
983 new (getLargeRep()) LargeRep(allocateBuckets(InitBuckets));
985 this->BaseT::initEmpty();
988 void grow(
unsigned AtLeast) {
989 if (AtLeast >= InlineBuckets)
990 AtLeast = std::max<unsigned>(64,
NextPowerOf2(AtLeast-1));
993 if (AtLeast < InlineBuckets)
998 BucketT *TmpBegin = reinterpret_cast<BucketT *>(TmpStorage.buffer);
999 BucketT *TmpEnd = TmpBegin;
1003 const KeyT EmptyKey = this->getEmptyKey();
1004 const KeyT TombstoneKey = this->getTombstoneKey();
1005 for (BucketT *P = getBuckets(), *E = P + InlineBuckets; P != E; ++P) {
1006 if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey) &&
1007 !KeyInfoT::isEqual(P->getFirst(), TombstoneKey)) {
1008 assert(
size_t(TmpEnd - TmpBegin) < InlineBuckets &&
1009 "Too many inline buckets!");
1010 ::new (&TmpEnd->getFirst()) KeyT(std::move(P->getFirst()));
1011 ::new (&TmpEnd->getSecond()) ValueT(std::move(P->getSecond()));
1013 P->getSecond().~ValueT();
1015 P->getFirst().~KeyT();
1021 new (getLargeRep()) LargeRep(allocateBuckets(AtLeast));
1022 this->moveFromOldBuckets(TmpBegin, TmpEnd);
1026 LargeRep OldRep = std::move(*getLargeRep());
1027 getLargeRep()->~LargeRep();
1028 if (AtLeast <= InlineBuckets) {
1031 new (getLargeRep()) LargeRep(allocateBuckets(AtLeast));
1034 this->moveFromOldBuckets(OldRep.Buckets, OldRep.Buckets+OldRep.NumBuckets);
1037 operator delete(OldRep.Buckets);
1040 void shrink_and_clear() {
1041 unsigned OldSize = this->
size();
1045 unsigned NewNumBuckets = 0;
1048 if (NewNumBuckets > InlineBuckets && NewNumBuckets < 64u)
1051 if ((Small && NewNumBuckets <= InlineBuckets) ||
1052 (!Small && NewNumBuckets == getLargeRep()->NumBuckets)) {
1053 this->BaseT::initEmpty();
1057 deallocateBuckets();
1058 init(NewNumBuckets);
1062 unsigned getNumEntries()
const {
1066 void setNumEntries(
unsigned Num) {
1068 assert(Num < (1U << 31) &&
"Cannot support more than 1<<31 entries");
1072 unsigned getNumTombstones()
const {
1073 return NumTombstones;
1076 void setNumTombstones(
unsigned Num) {
1077 NumTombstones = Num;
1080 const BucketT *getInlineBuckets()
const {
1085 return reinterpret_cast<const BucketT *>(storage.buffer);
1088 BucketT *getInlineBuckets() {
1089 return const_cast<BucketT *>(
1090 const_cast<const SmallDenseMap *>(
this)->getInlineBuckets());
1093 const LargeRep *getLargeRep()
const {
1096 return reinterpret_cast<const LargeRep *>(storage.buffer);
1099 LargeRep *getLargeRep() {
1100 return const_cast<LargeRep *>(
1101 const_cast<const SmallDenseMap *>(
this)->getLargeRep());
1104 const BucketT *getBuckets()
const {
1105 return Small ? getInlineBuckets() : getLargeRep()->Buckets;
1108 BucketT *getBuckets() {
1109 return const_cast<BucketT *>(
1110 const_cast<const SmallDenseMap *>(
this)->getBuckets());
1113 unsigned getNumBuckets()
const {
1114 return Small ? InlineBuckets : getLargeRep()->NumBuckets;
1117 void deallocateBuckets() {
1121 operator delete(getLargeRep()->Buckets);
1122 getLargeRep()->~LargeRep();
1125 LargeRep allocateBuckets(
unsigned Num) {
1126 assert(Num > InlineBuckets &&
"Must allocate more buckets than are inline");
1128 static_cast<BucketT*>(
operator new(
sizeof(BucketT) * Num)), Num
1134 template <
typename KeyT,
typename ValueT,
typename KeyInfoT,
typename Bucket,
1143 using difference_type = ptrdiff_t;
1145 typename std::conditional<IsConst, const Bucket, Bucket>::type;
1146 using pointer = value_type *;
1147 using reference = value_type &;
1148 using iterator_category = std::forward_iterator_tag;
1151 pointer Ptr =
nullptr;
1152 pointer End =
nullptr;
1158 bool NoAdvance =
false)
1160 assert(isHandleInSync() &&
"invalid construction!");
1162 if (NoAdvance)
return;
1163 AdvancePastEmptyBuckets();
1169 template <
bool IsConstSrc,
1170 typename =
typename std::enable_if<!IsConstSrc && IsConst>::type>
1172 const DenseMapIterator<KeyT, ValueT, KeyInfoT, Bucket, IsConstSrc> &I)
1173 : DebugEpochBase::HandleBase(I), Ptr(I.Ptr), End(I.End) {}
1175 reference operator*()
const {
1176 assert(isHandleInSync() &&
"invalid iterator access!");
1179 pointer operator->()
const {
1180 assert(isHandleInSync() &&
"invalid iterator access!");
1184 bool operator==(
const ConstIterator &RHS)
const {
1185 assert((!Ptr || isHandleInSync()) &&
"handle not in sync!");
1186 assert((!RHS.Ptr || RHS.isHandleInSync()) &&
"handle not in sync!");
1187 assert(getEpochAddress() == RHS.getEpochAddress() &&
1188 "comparing incomparable iterators!");
1189 return Ptr == RHS.Ptr;
1191 bool operator!=(
const ConstIterator &RHS)
const {
1192 assert((!Ptr || isHandleInSync()) &&
"handle not in sync!");
1193 assert((!RHS.Ptr || RHS.isHandleInSync()) &&
"handle not in sync!");
1194 assert(getEpochAddress() == RHS.getEpochAddress() &&
1195 "comparing incomparable iterators!");
1196 return Ptr != RHS.Ptr;
1199 inline DenseMapIterator& operator++() {
1200 assert(isHandleInSync() &&
"invalid iterator access!");
1202 AdvancePastEmptyBuckets();
1205 DenseMapIterator operator++(
int) {
1206 assert(isHandleInSync() &&
"invalid iterator access!");
1207 DenseMapIterator tmp = *
this; ++*
this;
return tmp;
1211 void AdvancePastEmptyBuckets() {
1213 const KeyT Empty = KeyInfoT::getEmptyKey();
1214 const KeyT Tombstone = KeyInfoT::getTombstoneKey();
1216 while (Ptr != End && (KeyInfoT::isEqual(Ptr->getFirst(), Empty) ||
1217 KeyInfoT::isEqual(Ptr->getFirst(), Tombstone)))
1221 void RetreatPastEmptyBuckets() {
1223 const KeyT Empty = KeyInfoT::getEmptyKey();
1224 const KeyT Tombstone = KeyInfoT::getTombstoneKey();
1226 while (Ptr != End && (KeyInfoT::isEqual(Ptr[-1].getFirst(), Empty) ||
1227 KeyInfoT::isEqual(Ptr[-1].getFirst(), Tombstone)))
1232 template <
typename KeyT,
typename ValueT,
typename KeyInfoT>
1233 inline size_t capacity_in_bytes(
const DenseMap<KeyT, ValueT, KeyInfoT> &X) {
1234 return X.getMemorySize();
1239 #endif // LLVM_ADT_DENSEMAP_H