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; }
54 template <
typename DerivedT,
typename KeyT,
typename ValueT,
typename KeyInfoT,
58 using const_arg_type_t =
typename const_pointer_or_const_ref<T>::type;
61 using size_type = unsigned;
62 using key_type = KeyT;
63 using mapped_type = ValueT;
64 using value_type = BucketT;
75 return makeIterator(getBuckets(), getBucketsEnd(), *
this);
78 return makeIterator(getBucketsEnd(), getBucketsEnd(), *
this,
true);
83 return makeConstIterator(getBuckets(), getBucketsEnd(), *
this);
86 return makeConstIterator(getBucketsEnd(), getBucketsEnd(), *
this,
true);
89 LLVM_NODISCARD
bool empty()
const {
90 return getNumEntries() == 0;
92 unsigned size()
const {
return getNumEntries(); }
97 auto NumBuckets = getMinBucketToReserveForEntries(NumEntries);
99 if (NumBuckets > getNumBuckets())
105 if (getNumEntries() == 0 && getNumTombstones() == 0)
return;
109 if (getNumEntries() * 4 < getNumBuckets() && getNumBuckets() > 64) {
114 const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
117 for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P)
118 P->getFirst() = EmptyKey;
120 unsigned NumEntries = getNumEntries();
121 for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) {
122 if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey)) {
123 if (!KeyInfoT::isEqual(P->getFirst(), TombstoneKey)) {
124 P->getSecond().~ValueT();
127 P->getFirst() = EmptyKey;
130 assert(NumEntries == 0 &&
"Node count imbalance!");
137 size_type
count(const_arg_type_t<KeyT> Val)
const {
138 const BucketT *TheBucket;
139 return LookupBucketFor(Val, TheBucket) ? 1 : 0;
144 if (LookupBucketFor(Val, TheBucket))
145 return makeIterator(TheBucket, getBucketsEnd(), *
this,
true);
149 const BucketT *TheBucket;
150 if (LookupBucketFor(Val, TheBucket))
151 return makeConstIterator(TheBucket, getBucketsEnd(), *
this,
true);
160 template<
class LookupKeyT>
163 if (LookupBucketFor(Val, TheBucket))
164 return makeIterator(TheBucket, getBucketsEnd(), *
this,
true);
167 template<
class LookupKeyT>
169 const BucketT *TheBucket;
170 if (LookupBucketFor(Val, TheBucket))
171 return makeConstIterator(TheBucket, getBucketsEnd(), *
this,
true);
177 ValueT
lookup(const_arg_type_t<KeyT> Val)
const {
178 const BucketT *TheBucket;
179 if (LookupBucketFor(Val, TheBucket))
180 return TheBucket->getSecond();
187 std::pair<iterator, bool> insert(
const std::pair<KeyT, ValueT> &KV) {
188 return try_emplace(KV.first, KV.second);
194 std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) {
195 return try_emplace(std::move(KV.first), std::move(KV.second));
201 template <
typename... Ts>
202 std::pair<iterator, bool> try_emplace(KeyT &&Key, Ts &&... Args) {
204 if (LookupBucketFor(Key, TheBucket))
205 return std::make_pair(
206 makeIterator(TheBucket, getBucketsEnd(), *
this,
true),
211 InsertIntoBucket(TheBucket, std::move(Key), std::forward<Ts>(Args)...);
212 return std::make_pair(
213 makeIterator(TheBucket, getBucketsEnd(), *
this,
true),
220 template <
typename... Ts>
221 std::pair<iterator, bool> try_emplace(
const KeyT &Key, Ts &&... Args) {
223 if (LookupBucketFor(Key, TheBucket))
224 return std::make_pair(
225 makeIterator(TheBucket, getBucketsEnd(), *
this,
true),
229 TheBucket = InsertIntoBucket(TheBucket, Key, std::forward<Ts>(Args)...);
230 return std::make_pair(
231 makeIterator(TheBucket, getBucketsEnd(), *
this,
true),
240 template <
typename LookupKeyT>
241 std::pair<iterator, bool>
insert_as(std::pair<KeyT, ValueT> &&KV,
242 const LookupKeyT &Val) {
244 if (LookupBucketFor(Val, TheBucket))
245 return std::make_pair(
246 makeIterator(TheBucket, getBucketsEnd(), *
this,
true),
250 TheBucket = InsertIntoBucketWithLookup(TheBucket, std::move(KV.first),
251 std::move(KV.second), Val);
252 return std::make_pair(
253 makeIterator(TheBucket, getBucketsEnd(), *
this,
true),
258 template<
typename InputIt>
264 bool erase(
const KeyT &Val) {
266 if (!LookupBucketFor(Val, TheBucket))
269 TheBucket->getSecond().~ValueT();
270 TheBucket->getFirst() = getTombstoneKey();
271 decrementNumEntries();
272 incrementNumTombstones();
276 BucketT *TheBucket = &*I;
277 TheBucket->getSecond().~ValueT();
278 TheBucket->getFirst() = getTombstoneKey();
279 decrementNumEntries();
280 incrementNumTombstones();
283 value_type& FindAndConstruct(
const KeyT &Key) {
285 if (LookupBucketFor(Key, TheBucket))
288 return *InsertIntoBucket(TheBucket, Key);
291 ValueT &operator[](
const KeyT &Key) {
292 return FindAndConstruct(Key).second;
295 value_type& FindAndConstruct(KeyT &&Key) {
297 if (LookupBucketFor(Key, TheBucket))
300 return *InsertIntoBucket(TheBucket, std::move(Key));
303 ValueT &operator[](KeyT &&Key) {
304 return FindAndConstruct(std::move(Key)).second;
311 return Ptr >= getBuckets() && Ptr < getBucketsEnd();
323 if (getNumBuckets() == 0)
326 const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
327 for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) {
328 if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey) &&
329 !KeyInfoT::isEqual(P->getFirst(), TombstoneKey))
330 P->getSecond().~ValueT();
331 P->getFirst().~KeyT();
339 assert((getNumBuckets() & (getNumBuckets()-1)) == 0 &&
340 "# initial buckets must be a power of two!");
341 const KeyT EmptyKey = getEmptyKey();
342 for (BucketT *B = getBuckets(), *E = getBucketsEnd(); B != E; ++B)
343 ::
new (&B->getFirst()) KeyT(EmptyKey);
357 void moveFromOldBuckets(BucketT *OldBucketsBegin, BucketT *OldBucketsEnd) {
361 const KeyT EmptyKey = getEmptyKey();
362 const KeyT TombstoneKey = getTombstoneKey();
363 for (BucketT *B = OldBucketsBegin, *E = OldBucketsEnd; B != E; ++B) {
364 if (!KeyInfoT::isEqual(B->getFirst(), EmptyKey) &&
365 !KeyInfoT::isEqual(B->getFirst(), TombstoneKey)) {
368 bool FoundVal = LookupBucketFor(B->getFirst(), DestBucket);
370 assert(!FoundVal &&
"Key already in new map?");
371 DestBucket->getFirst() = std::move(B->getFirst());
372 ::new (&DestBucket->getSecond()) ValueT(std::move(B->getSecond()));
373 incrementNumEntries();
376 B->getSecond().~ValueT();
378 B->getFirst().~KeyT();
382 template <
typename OtherBaseT>
385 assert(&other !=
this);
386 assert(getNumBuckets() == other.getNumBuckets());
388 setNumEntries(other.getNumEntries());
389 setNumTombstones(other.getNumTombstones());
392 memcpy(getBuckets(), other.getBuckets(),
393 getNumBuckets() *
sizeof(BucketT));
395 for (
size_t i = 0; i < getNumBuckets(); ++i) {
396 ::new (&getBuckets()[i].getFirst())
397 KeyT(other.getBuckets()[i].getFirst());
398 if (!KeyInfoT::isEqual(getBuckets()[i].getFirst(), getEmptyKey()) &&
399 !KeyInfoT::isEqual(getBuckets()[i].getFirst(), getTombstoneKey()))
400 ::
new (&getBuckets()[i].getSecond())
401 ValueT(other.getBuckets()[i].getSecond());
405 static unsigned getHashValue(
const KeyT &Val) {
406 return KeyInfoT::getHashValue(Val);
409 template<
typename LookupKeyT>
410 static unsigned getHashValue(
const LookupKeyT &Val) {
411 return KeyInfoT::getHashValue(Val);
414 static const KeyT getEmptyKey() {
415 static_assert(std::is_base_of<DenseMapBase, DerivedT>::value,
416 "Must pass the derived type to this template!");
417 return KeyInfoT::getEmptyKey();
420 static const KeyT getTombstoneKey() {
421 return KeyInfoT::getTombstoneKey();
425 iterator makeIterator(BucketT *P, BucketT *E,
427 bool NoAdvance=
false) {
428 return iterator(P, E, Epoch, NoAdvance);
431 const_iterator makeConstIterator(
const BucketT *P,
const BucketT *E,
433 const bool NoAdvance=
false)
const {
437 unsigned getNumEntries()
const {
438 return static_cast<const DerivedT *
>(
this)->getNumEntries();
441 void setNumEntries(
unsigned Num) {
442 static_cast<DerivedT *
>(
this)->setNumEntries(Num);
445 void incrementNumEntries() {
446 setNumEntries(getNumEntries() + 1);
449 void decrementNumEntries() {
450 setNumEntries(getNumEntries() - 1);
453 unsigned getNumTombstones()
const {
454 return static_cast<const DerivedT *
>(
this)->getNumTombstones();
457 void setNumTombstones(
unsigned Num) {
458 static_cast<DerivedT *
>(
this)->setNumTombstones(Num);
461 void incrementNumTombstones() {
462 setNumTombstones(getNumTombstones() + 1);
465 void decrementNumTombstones() {
466 setNumTombstones(getNumTombstones() - 1);
469 const BucketT *getBuckets()
const {
470 return static_cast<const DerivedT *
>(
this)->getBuckets();
473 BucketT *getBuckets() {
474 return static_cast<DerivedT *
>(
this)->getBuckets();
477 unsigned getNumBuckets()
const {
478 return static_cast<const DerivedT *
>(
this)->getNumBuckets();
481 BucketT *getBucketsEnd() {
482 return getBuckets() + getNumBuckets();
485 const BucketT *getBucketsEnd()
const {
486 return getBuckets() + getNumBuckets();
489 void grow(
unsigned AtLeast) {
490 static_cast<DerivedT *
>(
this)->grow(AtLeast);
493 void shrink_and_clear() {
494 static_cast<DerivedT *
>(
this)->shrink_and_clear();
497 template <
typename KeyArg,
typename... ValueArgs>
498 BucketT *InsertIntoBucket(BucketT *TheBucket, KeyArg &&Key,
499 ValueArgs &&... Values) {
500 TheBucket = InsertIntoBucketImpl(Key, Key, TheBucket);
502 TheBucket->getFirst() = std::forward<KeyArg>(Key);
503 ::new (&TheBucket->getSecond()) ValueT(std::forward<ValueArgs>(Values)...);
507 template <
typename LookupKeyT>
508 BucketT *InsertIntoBucketWithLookup(BucketT *TheBucket, KeyT &&Key,
509 ValueT &&Value, LookupKeyT &Lookup) {
510 TheBucket = InsertIntoBucketImpl(Key, Lookup, TheBucket);
512 TheBucket->getFirst() = std::move(Key);
513 ::new (&TheBucket->getSecond()) ValueT(std::move(Value));
517 template <
typename LookupKeyT>
518 BucketT *InsertIntoBucketImpl(
const KeyT &Key,
const LookupKeyT &Lookup,
519 BucketT *TheBucket) {
531 unsigned NewNumEntries = getNumEntries() + 1;
532 unsigned NumBuckets = getNumBuckets();
533 if (LLVM_UNLIKELY(NewNumEntries * 4 >= NumBuckets * 3)) {
534 this->grow(NumBuckets * 2);
535 LookupBucketFor(Lookup, TheBucket);
536 NumBuckets = getNumBuckets();
537 }
else if (LLVM_UNLIKELY(NumBuckets-(NewNumEntries+getNumTombstones()) <=
539 this->grow(NumBuckets);
540 LookupBucketFor(Lookup, TheBucket);
546 incrementNumEntries();
549 const KeyT EmptyKey = getEmptyKey();
550 if (!KeyInfoT::isEqual(TheBucket->getFirst(), EmptyKey))
551 decrementNumTombstones();
560 template<
typename LookupKeyT>
561 bool LookupBucketFor(
const LookupKeyT &Val,
562 const BucketT *&FoundBucket)
const {
563 const BucketT *BucketsPtr = getBuckets();
564 const unsigned NumBuckets = getNumBuckets();
566 if (NumBuckets == 0) {
567 FoundBucket =
nullptr;
572 const BucketT *FoundTombstone =
nullptr;
573 const KeyT EmptyKey = getEmptyKey();
574 const KeyT TombstoneKey = getTombstoneKey();
575 assert(!KeyInfoT::isEqual(Val, EmptyKey) &&
576 !KeyInfoT::isEqual(Val, TombstoneKey) &&
577 "Empty/Tombstone value shouldn't be inserted into map!");
579 unsigned BucketNo = getHashValue(Val) & (NumBuckets-1);
580 unsigned ProbeAmt = 1;
582 const BucketT *ThisBucket = BucketsPtr + BucketNo;
584 if (LLVM_LIKELY(KeyInfoT::isEqual(Val, ThisBucket->getFirst()))) {
585 FoundBucket = ThisBucket;
591 if (LLVM_LIKELY(KeyInfoT::isEqual(ThisBucket->getFirst(), EmptyKey))) {
594 FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket;
600 if (KeyInfoT::isEqual(ThisBucket->getFirst(), TombstoneKey) &&
602 FoundTombstone = ThisBucket;
606 BucketNo += ProbeAmt++;
607 BucketNo &= (NumBuckets-1);
611 template <
typename LookupKeyT>
612 bool LookupBucketFor(
const LookupKeyT &Val, BucketT *&FoundBucket) {
613 const BucketT *ConstFoundBucket;
615 ->LookupBucketFor(Val, ConstFoundBucket);
616 FoundBucket =
const_cast<BucketT *
>(ConstFoundBucket);
626 return getNumBuckets() *
sizeof(BucketT);
630 template <
typename KeyT,
typename ValueT,
634 KeyT, ValueT, KeyInfoT, BucketT> {
635 friend class DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT, BucketT>;
643 unsigned NumTombstones;
649 explicit DenseMap(
unsigned InitialReserve = 0) { init(InitialReserve); }
651 DenseMap(
const DenseMap &other) : BaseT() {
656 DenseMap(DenseMap &&other) : BaseT() {
661 template<
typename InputIt>
662 DenseMap(
const InputIt &I,
const InputIt &E) {
663 init(std::distance(I, E));
669 operator delete(Buckets);
672 void swap(DenseMap& RHS) {
673 this->incrementEpoch();
675 std::swap(Buckets, RHS.Buckets);
676 std::swap(NumEntries, RHS.NumEntries);
677 std::swap(NumTombstones, RHS.NumTombstones);
678 std::swap(NumBuckets, RHS.NumBuckets);
681 DenseMap& operator=(
const DenseMap& other) {
687 DenseMap& operator=(DenseMap &&other) {
689 operator delete(Buckets);
695 void copyFrom(
const DenseMap& other) {
697 operator delete(Buckets);
698 if (allocateBuckets(other.NumBuckets)) {
699 this->BaseT::copyFrom(other);
706 void init(
unsigned InitNumEntries) {
707 auto InitBuckets = BaseT::getMinBucketToReserveForEntries(InitNumEntries);
708 if (allocateBuckets(InitBuckets)) {
709 this->BaseT::initEmpty();
716 void grow(
unsigned AtLeast) {
717 unsigned OldNumBuckets = NumBuckets;
718 BucketT *OldBuckets = Buckets;
720 allocateBuckets(std::max<unsigned>(64, static_cast<unsigned>(
NextPowerOf2(AtLeast-1))));
723 this->BaseT::initEmpty();
727 this->moveFromOldBuckets(OldBuckets, OldBuckets+OldNumBuckets);
730 operator delete(OldBuckets);
733 void shrink_and_clear() {
734 unsigned OldNumEntries = NumEntries;
738 unsigned NewNumBuckets = 0;
740 NewNumBuckets = std::max(64, 1 << (
Log2_32_Ceil(OldNumEntries) + 1));
741 if (NewNumBuckets == NumBuckets) {
742 this->BaseT::initEmpty();
746 operator delete(Buckets);
751 unsigned getNumEntries()
const {
755 void setNumEntries(
unsigned Num) {
759 unsigned getNumTombstones()
const {
760 return NumTombstones;
763 void setNumTombstones(
unsigned Num) {
767 BucketT *getBuckets()
const {
771 unsigned getNumBuckets()
const {
775 bool allocateBuckets(
unsigned Num) {
777 if (NumBuckets == 0) {
782 Buckets =
static_cast<BucketT*
>(
operator new(
sizeof(BucketT) * NumBuckets));
787 template <
typename KeyT,
typename ValueT,
unsigned InlineBuckets = 4,
792 SmallDenseMap<KeyT, ValueT, InlineBuckets, KeyInfoT, BucketT>, KeyT,
793 ValueT, KeyInfoT, BucketT> {
794 friend class DenseMapBase<SmallDenseMap, KeyT, ValueT, KeyInfoT, BucketT>;
801 "InlineBuckets must be a power of 2.");
804 unsigned NumEntries : 31;
805 unsigned NumTombstones;
817 explicit SmallDenseMap(
unsigned NumInitBuckets = 0) {
818 init(NumInitBuckets);
821 SmallDenseMap(
const SmallDenseMap &other) : BaseT() {
826 SmallDenseMap(SmallDenseMap &&other) : BaseT() {
831 template<
typename InputIt>
832 SmallDenseMap(
const InputIt &I,
const InputIt &E) {
842 void swap(SmallDenseMap& RHS) {
843 unsigned TmpNumEntries = RHS.NumEntries;
844 RHS.NumEntries = NumEntries;
845 NumEntries = TmpNumEntries;
846 std::swap(NumTombstones, RHS.NumTombstones);
848 const KeyT EmptyKey = this->getEmptyKey();
849 const KeyT TombstoneKey = this->getTombstoneKey();
850 if (Small && RHS.Small) {
855 for (
unsigned i = 0, e = InlineBuckets; i != e; ++i) {
856 BucketT *LHSB = &getInlineBuckets()[i],
857 *RHSB = &RHS.getInlineBuckets()[i];
858 bool hasLHSValue = (!KeyInfoT::isEqual(LHSB->getFirst(), EmptyKey) &&
859 !KeyInfoT::isEqual(LHSB->getFirst(), TombstoneKey));
860 bool hasRHSValue = (!KeyInfoT::isEqual(RHSB->getFirst(), EmptyKey) &&
861 !KeyInfoT::isEqual(RHSB->getFirst(), TombstoneKey));
862 if (hasLHSValue && hasRHSValue) {
864 std::swap(*LHSB, *RHSB);
868 std::swap(LHSB->getFirst(), RHSB->getFirst());
870 ::new (&RHSB->getSecond()) ValueT(std::move(LHSB->getSecond()));
871 LHSB->getSecond().~ValueT();
872 }
else if (hasRHSValue) {
873 ::new (&LHSB->getSecond()) ValueT(std::move(RHSB->getSecond()));
874 RHSB->getSecond().~ValueT();
879 if (!Small && !RHS.Small) {
880 std::swap(getLargeRep()->Buckets, RHS.getLargeRep()->Buckets);
881 std::swap(getLargeRep()->NumBuckets, RHS.getLargeRep()->NumBuckets);
885 SmallDenseMap &SmallSide = Small ? *
this : RHS;
886 SmallDenseMap &LargeSide = Small ? RHS : *
this;
889 LargeRep TmpRep = std::move(*LargeSide.getLargeRep());
890 LargeSide.getLargeRep()->~LargeRep();
891 LargeSide.Small =
true;
896 for (
unsigned i = 0, e = InlineBuckets; i != e; ++i) {
897 BucketT *NewB = &LargeSide.getInlineBuckets()[i],
898 *OldB = &SmallSide.getInlineBuckets()[i];
899 ::new (&NewB->getFirst()) KeyT(std::move(OldB->getFirst()));
900 OldB->getFirst().~KeyT();
901 if (!KeyInfoT::isEqual(NewB->getFirst(), EmptyKey) &&
902 !KeyInfoT::isEqual(NewB->getFirst(), TombstoneKey)) {
903 ::new (&NewB->getSecond()) ValueT(std::move(OldB->getSecond()));
904 OldB->getSecond().~ValueT();
910 SmallSide.Small =
false;
911 new (SmallSide.getLargeRep()) LargeRep(std::move(TmpRep));
914 SmallDenseMap& operator=(
const SmallDenseMap& other) {
920 SmallDenseMap& operator=(SmallDenseMap &&other) {
928 void copyFrom(
const SmallDenseMap& other) {
932 if (other.getNumBuckets() > InlineBuckets) {
934 new (getLargeRep()) LargeRep(allocateBuckets(other.getNumBuckets()));
936 this->BaseT::copyFrom(other);
939 void init(
unsigned InitBuckets) {
941 if (InitBuckets > InlineBuckets) {
943 new (getLargeRep()) LargeRep(allocateBuckets(InitBuckets));
945 this->BaseT::initEmpty();
948 void grow(
unsigned AtLeast) {
949 if (AtLeast >= InlineBuckets)
950 AtLeast = std::max<unsigned>(64,
NextPowerOf2(AtLeast-1));
953 if (AtLeast < InlineBuckets)
958 BucketT *TmpBegin =
reinterpret_cast<BucketT *
>(TmpStorage.buffer);
959 BucketT *TmpEnd = TmpBegin;
963 const KeyT EmptyKey = this->getEmptyKey();
964 const KeyT TombstoneKey = this->getTombstoneKey();
965 for (BucketT *P = getBuckets(), *E = P + InlineBuckets; P != E; ++P) {
966 if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey) &&
967 !KeyInfoT::isEqual(P->getFirst(), TombstoneKey)) {
968 assert(
size_t(TmpEnd - TmpBegin) < InlineBuckets &&
969 "Too many inline buckets!");
970 ::new (&TmpEnd->getFirst()) KeyT(std::move(P->getFirst()));
971 ::new (&TmpEnd->getSecond()) ValueT(std::move(P->getSecond()));
973 P->getSecond().~ValueT();
975 P->getFirst().~KeyT();
981 new (getLargeRep()) LargeRep(allocateBuckets(AtLeast));
982 this->moveFromOldBuckets(TmpBegin, TmpEnd);
986 LargeRep OldRep = std::move(*getLargeRep());
987 getLargeRep()->~LargeRep();
988 if (AtLeast <= InlineBuckets) {
991 new (getLargeRep()) LargeRep(allocateBuckets(AtLeast));
994 this->moveFromOldBuckets(OldRep.Buckets, OldRep.Buckets+OldRep.NumBuckets);
997 operator delete(OldRep.Buckets);
1000 void shrink_and_clear() {
1001 unsigned OldSize = this->
size();
1005 unsigned NewNumBuckets = 0;
1008 if (NewNumBuckets > InlineBuckets && NewNumBuckets < 64u)
1011 if ((Small && NewNumBuckets <= InlineBuckets) ||
1012 (!Small && NewNumBuckets == getLargeRep()->NumBuckets)) {
1013 this->BaseT::initEmpty();
1017 deallocateBuckets();
1018 init(NewNumBuckets);
1022 unsigned getNumEntries()
const {
1026 void setNumEntries(
unsigned Num) {
1028 assert(Num < (1U << 31) &&
"Cannot support more than 1<<31 entries");
1032 unsigned getNumTombstones()
const {
1033 return NumTombstones;
1036 void setNumTombstones(
unsigned Num) {
1037 NumTombstones = Num;
1040 const BucketT *getInlineBuckets()
const {
1045 return reinterpret_cast<const BucketT *
>(storage.buffer);
1048 BucketT *getInlineBuckets() {
1049 return const_cast<BucketT *
>(
1050 const_cast<const SmallDenseMap *
>(
this)->getInlineBuckets());
1053 const LargeRep *getLargeRep()
const {
1056 return reinterpret_cast<const LargeRep *
>(storage.buffer);
1059 LargeRep *getLargeRep() {
1060 return const_cast<LargeRep *
>(
1061 const_cast<const SmallDenseMap *
>(
this)->getLargeRep());
1064 const BucketT *getBuckets()
const {
1065 return Small ? getInlineBuckets() : getLargeRep()->Buckets;
1068 BucketT *getBuckets() {
1069 return const_cast<BucketT *
>(
1070 const_cast<const SmallDenseMap *
>(
this)->getBuckets());
1073 unsigned getNumBuckets()
const {
1074 return Small ? InlineBuckets : getLargeRep()->NumBuckets;
1077 void deallocateBuckets() {
1081 operator delete(getLargeRep()->Buckets);
1082 getLargeRep()->~LargeRep();
1085 LargeRep allocateBuckets(
unsigned Num) {
1086 assert(Num > InlineBuckets &&
"Must allocate more buckets than are inline");
1088 static_cast<BucketT*
>(
operator new(
sizeof(BucketT) * Num)), Num
1094 template <
typename KeyT,
typename ValueT,
typename KeyInfoT,
typename Bucket,
1103 using difference_type = ptrdiff_t;
1105 typename std::conditional<IsConst, const Bucket, Bucket>::type;
1106 using pointer = value_type *;
1107 using reference = value_type &;
1108 using iterator_category = std::forward_iterator_tag;
1111 pointer Ptr =
nullptr;
1112 pointer End =
nullptr;
1118 bool NoAdvance =
false)
1120 assert(isHandleInSync() &&
"invalid construction!");
1122 if (NoAdvance)
return;
1123 AdvancePastEmptyBuckets();
1129 template <
bool IsConstSrc,
1130 typename =
typename std::enable_if<!IsConstSrc && IsConst>::type>
1135 reference operator*()
const {
1136 assert(isHandleInSync() &&
"invalid iterator access!");
1139 pointer operator->()
const {
1140 assert(isHandleInSync() &&
"invalid iterator access!");
1144 bool operator==(
const ConstIterator &RHS)
const {
1145 assert((!Ptr || isHandleInSync()) &&
"handle not in sync!");
1146 assert((!RHS.Ptr || RHS.isHandleInSync()) &&
"handle not in sync!");
1147 assert(getEpochAddress() == RHS.getEpochAddress() &&
1148 "comparing incomparable iterators!");
1149 return Ptr == RHS.Ptr;
1151 bool operator!=(
const ConstIterator &RHS)
const {
1152 assert((!Ptr || isHandleInSync()) &&
"handle not in sync!");
1153 assert((!RHS.Ptr || RHS.isHandleInSync()) &&
"handle not in sync!");
1154 assert(getEpochAddress() == RHS.getEpochAddress() &&
1155 "comparing incomparable iterators!");
1156 return Ptr != RHS.Ptr;
1159 inline DenseMapIterator& operator++() {
1160 assert(isHandleInSync() &&
"invalid iterator access!");
1162 AdvancePastEmptyBuckets();
1165 DenseMapIterator operator++(
int) {
1166 assert(isHandleInSync() &&
"invalid iterator access!");
1167 DenseMapIterator tmp = *
this; ++*
this;
return tmp;
1171 void AdvancePastEmptyBuckets() {
1173 const KeyT Empty = KeyInfoT::getEmptyKey();
1174 const KeyT Tombstone = KeyInfoT::getTombstoneKey();
1176 while (Ptr != End && (KeyInfoT::isEqual(Ptr->getFirst(), Empty) ||
1177 KeyInfoT::isEqual(Ptr->getFirst(), Tombstone)))
1181 void RetreatPastEmptyBuckets() {
1183 const KeyT Empty = KeyInfoT::getEmptyKey();
1184 const KeyT Tombstone = KeyInfoT::getTombstoneKey();
1186 while (Ptr != End && (KeyInfoT::isEqual(Ptr[-1].getFirst(), Empty) ||
1187 KeyInfoT::isEqual(Ptr[-1].getFirst(), Tombstone)))
1192 template <
typename KeyT,
typename ValueT,
typename KeyInfoT>
1199 #endif // LLVM_ADT_DENSEMAP_H unsigned Log2_32_Ceil(uint32_t Value)
Return the ceil log base 2 of the specified value, 32 if the value is zero.
Definition: MathExtras.h:526
A base class for iterator classes ("handles") that wish to poll for iterator invalidating modificatio...
Definition: EpochTracker.h:71
size_t getMemorySize() const
Return the approximate size (in bytes) of the actual map.
Definition: DenseMap.h:625
Definition: DenseMapInfo.h:29
Definition: DenseMap.h:633
Definition: DenseMap.h:56
namespace to hold default to_json function
Definition: json_binary_writer.cpp:39
void reserve(size_type NumEntries)
Grow the densemap so that it can contain at least NumEntries items before resizing again...
Definition: DenseMap.h:96
DenseMap(unsigned InitialReserve=0)
Create a DenseMap wth an optional InitialReserve that guarantee that this number of elements can be i...
Definition: DenseMap.h:649
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:137
iterator find_as(const LookupKeyT &Val)
Alternate version of find() which allows a different, and possibly less expensive, key type.
Definition: DenseMap.h:161
isPodLike - This is a type trait that is used to determine whether a given type can be copied around ...
Definition: ArrayRef.h:530
Definition: DenseMap.h:790
uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
Definition: MathExtras.h:614
void incrementEpoch()
Calling incrementEpoch invalidates all handles pointing into the calling instance.
Definition: EpochTracker.h:57
auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:896
unsigned getMinBucketToReserveForEntries(unsigned NumEntries)
Returns the number of buckets to allocate to ensure that the DenseMap can accommodate NumEntries with...
Definition: DenseMap.h:348
A base class for data structure classes wishing to make iterators ("handles") pointing into themselve...
Definition: EpochTracker.h:49
void insert(InputIt I, InputIt E)
insert - Range insertion of pairs.
Definition: DenseMap.h:259
Definition: DenseMap.h:40
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...
Definition: DenseMap.h:177
auto size(R &&Range, typename std::enable_if< std::is_same< typename std::iterator_traits< decltype(Range.begin())>::iterator_category, std::random_access_iterator_tag >::value, void >::type *=nullptr) -> decltype(std::distance(Range.begin(), Range.end()))
Get the size of a range.
Definition: STLExtras.h:999
constexpr bool isPowerOf2_64(uint64_t Value)
Return true if the argument is a power of two > 0 (64 bit edition.)
Definition: MathExtras.h:423
Definition: DenseMap.h:52
bool operator==(json::const_reference lhs, json::const_reference rhs) noexcept
Definition: json.cpp:921
bool isPointerIntoBucketsArray(const void *Ptr) const
isPointerIntoBucketsArray - Return true if the specified pointer points somewhere into the DenseMap's...
Definition: DenseMap.h:310
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, key type.
Definition: DenseMap.h:241
const void * getPointerIntoBucketsArray() const
getPointerIntoBucketsArray() - Return an opaque pointer into the buckets array.
Definition: DenseMap.h:317