diff options
Diffstat (limited to 'include/llvm/ADT/DenseMap.h')
| -rw-r--r-- | include/llvm/ADT/DenseMap.h | 134 |
1 files changed, 100 insertions, 34 deletions
diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h index b311e69ec9d37..ba60b7972a8fc 100644 --- a/include/llvm/ADT/DenseMap.h +++ b/include/llvm/ADT/DenseMap.h @@ -19,6 +19,7 @@ #include "llvm/Support/AlignOf.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/MathExtras.h" +#include "llvm/Support/ReverseIteration.h" #include "llvm/Support/type_traits.h" #include <algorithm> #include <cassert> @@ -67,18 +68,26 @@ public: DenseMapIterator<KeyT, ValueT, KeyInfoT, BucketT, true>; inline iterator begin() { - // When the map is empty, avoid the overhead of AdvancePastEmptyBuckets(). - return empty() ? end() : iterator(getBuckets(), getBucketsEnd(), *this); + // When the map is empty, avoid the overhead of advancing/retreating past + // empty buckets. + if (empty()) + return end(); + if (shouldReverseIterate<KeyT>()) + return makeIterator(getBucketsEnd() - 1, getBuckets(), *this); + return makeIterator(getBuckets(), getBucketsEnd(), *this); } inline iterator end() { - return iterator(getBucketsEnd(), getBucketsEnd(), *this, true); + return makeIterator(getBucketsEnd(), getBucketsEnd(), *this, true); } inline const_iterator begin() const { - return empty() ? end() - : const_iterator(getBuckets(), getBucketsEnd(), *this); + if (empty()) + return end(); + if (shouldReverseIterate<KeyT>()) + return makeConstIterator(getBucketsEnd() - 1, getBuckets(), *this); + return makeConstIterator(getBuckets(), getBucketsEnd(), *this); } inline const_iterator end() const { - return const_iterator(getBucketsEnd(), getBucketsEnd(), *this, true); + return makeConstIterator(getBucketsEnd(), getBucketsEnd(), *this, true); } LLVM_NODISCARD bool empty() const { @@ -107,17 +116,23 @@ public: } const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); - unsigned NumEntries = getNumEntries(); - for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) { - if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey)) { - if (!KeyInfoT::isEqual(P->getFirst(), TombstoneKey)) { - P->getSecond().~ValueT(); - --NumEntries; - } + if (isPodLike<KeyT>::value && isPodLike<ValueT>::value) { + // Use a simpler loop when these are trivial types. + for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) P->getFirst() = EmptyKey; + } else { + unsigned NumEntries = getNumEntries(); + for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) { + if (!KeyInfoT::isEqual(P->getFirst(), EmptyKey)) { + if (!KeyInfoT::isEqual(P->getFirst(), TombstoneKey)) { + P->getSecond().~ValueT(); + --NumEntries; + } + P->getFirst() = EmptyKey; + } } + assert(NumEntries == 0 && "Node count imbalance!"); } - assert(NumEntries == 0 && "Node count imbalance!"); setNumEntries(0); setNumTombstones(0); } @@ -131,13 +146,13 @@ public: iterator find(const_arg_type_t<KeyT> Val) { BucketT *TheBucket; if (LookupBucketFor(Val, TheBucket)) - return iterator(TheBucket, getBucketsEnd(), *this, true); + return makeIterator(TheBucket, getBucketsEnd(), *this, true); return end(); } const_iterator find(const_arg_type_t<KeyT> Val) const { const BucketT *TheBucket; if (LookupBucketFor(Val, TheBucket)) - return const_iterator(TheBucket, getBucketsEnd(), *this, true); + return makeConstIterator(TheBucket, getBucketsEnd(), *this, true); return end(); } @@ -150,14 +165,14 @@ public: iterator find_as(const LookupKeyT &Val) { BucketT *TheBucket; if (LookupBucketFor(Val, TheBucket)) - return iterator(TheBucket, getBucketsEnd(), *this, true); + return makeIterator(TheBucket, getBucketsEnd(), *this, true); return end(); } template<class LookupKeyT> const_iterator find_as(const LookupKeyT &Val) const { const BucketT *TheBucket; if (LookupBucketFor(Val, TheBucket)) - return const_iterator(TheBucket, getBucketsEnd(), *this, true); + return makeConstIterator(TheBucket, getBucketsEnd(), *this, true); return end(); } @@ -191,14 +206,16 @@ public: std::pair<iterator, bool> try_emplace(KeyT &&Key, Ts &&... Args) { BucketT *TheBucket; if (LookupBucketFor(Key, TheBucket)) - return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true), - false); // Already in map. + return std::make_pair( + makeIterator(TheBucket, getBucketsEnd(), *this, true), + false); // Already in map. // Otherwise, insert the new element. TheBucket = InsertIntoBucket(TheBucket, std::move(Key), std::forward<Ts>(Args)...); - return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true), - true); + return std::make_pair( + makeIterator(TheBucket, getBucketsEnd(), *this, true), + true); } // Inserts key,value pair into the map if the key isn't already in the map. @@ -208,13 +225,15 @@ public: std::pair<iterator, bool> try_emplace(const KeyT &Key, Ts &&... Args) { BucketT *TheBucket; if (LookupBucketFor(Key, TheBucket)) - return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true), - false); // Already in map. + return std::make_pair( + makeIterator(TheBucket, getBucketsEnd(), *this, true), + false); // Already in map. // Otherwise, insert the new element. TheBucket = InsertIntoBucket(TheBucket, Key, std::forward<Ts>(Args)...); - return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true), - true); + return std::make_pair( + makeIterator(TheBucket, getBucketsEnd(), *this, true), + true); } /// Alternate version of insert() which allows a different, and possibly @@ -227,14 +246,16 @@ public: const LookupKeyT &Val) { BucketT *TheBucket; if (LookupBucketFor(Val, TheBucket)) - return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true), - false); // Already in map. + return std::make_pair( + makeIterator(TheBucket, getBucketsEnd(), *this, true), + false); // Already in map. // Otherwise, insert the new element. TheBucket = InsertIntoBucketWithLookup(TheBucket, std::move(KV.first), std::move(KV.second), Val); - return std::make_pair(iterator(TheBucket, getBucketsEnd(), *this, true), - true); + return std::make_pair( + makeIterator(TheBucket, getBucketsEnd(), *this, true), + true); } /// insert - Range insertion of pairs. @@ -405,6 +426,26 @@ protected: } private: + iterator makeIterator(BucketT *P, BucketT *E, + DebugEpochBase &Epoch, + bool NoAdvance=false) { + if (shouldReverseIterate<KeyT>()) { + BucketT *B = P == getBucketsEnd() ? getBuckets() : P + 1; + return iterator(B, E, Epoch, NoAdvance); + } + return iterator(P, E, Epoch, NoAdvance); + } + + const_iterator makeConstIterator(const BucketT *P, const BucketT *E, + const DebugEpochBase &Epoch, + const bool NoAdvance=false) const { + if (shouldReverseIterate<KeyT>()) { + const BucketT *B = P == getBucketsEnd() ? getBuckets() : P + 1; + return const_iterator(B, E, Epoch, NoAdvance); + } + return const_iterator(P, E, Epoch, NoAdvance); + } + unsigned getNumEntries() const { return static_cast<const DerivedT *>(this)->getNumEntries(); } @@ -1089,7 +1130,13 @@ public: bool NoAdvance = false) : DebugEpochBase::HandleBase(&Epoch), Ptr(Pos), End(E) { assert(isHandleInSync() && "invalid construction!"); - if (!NoAdvance) AdvancePastEmptyBuckets(); + + if (NoAdvance) return; + if (shouldReverseIterate<KeyT>()) { + RetreatPastEmptyBuckets(); + return; + } + AdvancePastEmptyBuckets(); } // Converting ctor from non-const iterators to const iterators. SFINAE'd out @@ -1103,10 +1150,14 @@ public: reference operator*() const { assert(isHandleInSync() && "invalid iterator access!"); + if (shouldReverseIterate<KeyT>()) + return Ptr[-1]; return *Ptr; } pointer operator->() const { assert(isHandleInSync() && "invalid iterator access!"); + if (shouldReverseIterate<KeyT>()) + return &(Ptr[-1]); return Ptr; } @@ -1127,6 +1178,11 @@ public: inline DenseMapIterator& operator++() { // Preincrement assert(isHandleInSync() && "invalid iterator access!"); + if (shouldReverseIterate<KeyT>()) { + --Ptr; + RetreatPastEmptyBuckets(); + return *this; + } ++Ptr; AdvancePastEmptyBuckets(); return *this; @@ -1138,6 +1194,7 @@ public: private: void AdvancePastEmptyBuckets() { + assert(Ptr <= End); const KeyT Empty = KeyInfoT::getEmptyKey(); const KeyT Tombstone = KeyInfoT::getTombstoneKey(); @@ -1145,11 +1202,20 @@ private: KeyInfoT::isEqual(Ptr->getFirst(), Tombstone))) ++Ptr; } + + void RetreatPastEmptyBuckets() { + assert(Ptr >= End); + const KeyT Empty = KeyInfoT::getEmptyKey(); + const KeyT Tombstone = KeyInfoT::getTombstoneKey(); + + while (Ptr != End && (KeyInfoT::isEqual(Ptr[-1].getFirst(), Empty) || + KeyInfoT::isEqual(Ptr[-1].getFirst(), Tombstone))) + --Ptr; + } }; -template<typename KeyT, typename ValueT, typename KeyInfoT> -static inline size_t -capacity_in_bytes(const DenseMap<KeyT, ValueT, KeyInfoT> &X) { +template <typename KeyT, typename ValueT, typename KeyInfoT> +inline size_t capacity_in_bytes(const DenseMap<KeyT, ValueT, KeyInfoT> &X) { return X.getMemorySize(); } |