#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>
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 {
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();
}
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();
}
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.
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
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.
}
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();
}
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
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;
}
inline DenseMapIterator& operator++() { // Preincrement
assert(isHandleInSync() && "invalid iterator access!");
+ if (shouldReverseIterate<KeyT>()) {
+ --Ptr;
+ RetreatPastEmptyBuckets();
+ return *this;
+ }
++Ptr;
AdvancePastEmptyBuckets();
return *this;
private:
void AdvancePastEmptyBuckets() {
+ assert(Ptr <= End);
const KeyT Empty = KeyInfoT::getEmptyKey();
const KeyT Tombstone = KeyInfoT::getTombstoneKey();
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>