diff --git a/compiler-rt/lib/sanitizer_common/CMakeLists.txt b/compiler-rt/lib/sanitizer_common/CMakeLists.txt --- a/compiler-rt/lib/sanitizer_common/CMakeLists.txt +++ b/compiler-rt/lib/sanitizer_common/CMakeLists.txt @@ -131,6 +131,8 @@ sanitizer_dbghelp.h sanitizer_deadlock_detector.h sanitizer_deadlock_detector_interface.h + sanitizer_dense_map.h + sanitizer_dense_map_info.h sanitizer_errno.h sanitizer_errno_codes.h sanitizer_file.h diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_dense_map.h b/compiler-rt/lib/sanitizer_common/sanitizer_dense_map.h --- a/compiler-rt/lib/sanitizer_common/sanitizer_dense_map.h +++ b/compiler-rt/lib/sanitizer_common/sanitizer_dense_map.h @@ -6,7 +6,10 @@ // //===----------------------------------------------------------------------===// // -// This is fork of llvm/ADT/DenseMap.h class. +// This is fork of llvm/ADT/DenseMap.h class with the following changes: +// * No iterators. +// * Supports only trivially destructuble types. +// * Does not shrink. // //===----------------------------------------------------------------------===// @@ -18,114 +21,61 @@ #include "sanitizer_internal_defs.h" namespace __sanitizer { -namespace detail { - -// We extend a pair to allow users to override the bucket type with their own -// implementation without requiring two members. -template -struct DenseMapPair : public std::pair { - using std::pair::pair; - - KeyT &getFirst() { return std::pair::first; } - const KeyT &getFirst() const { return std::pair::first; } - ValueT &getSecond() { return std::pair::second; } - const ValueT &getSecond() const { return std::pair::second; } -}; - -} // end namespace detail - -template , - typename Bucket = llvm::detail::DenseMapPair, - bool IsConst = false> -class DenseMapIterator; template -class DenseMapBase : public DebugEpochBase { - template - using const_arg_type_t = typename const_pointer_or_const_ref::type; - +class DenseMapBase { public: using size_type = unsigned; using key_type = KeyT; using mapped_type = ValueT; using value_type = BucketT; - LLVM_NODISCARD bool empty() const { return getNumEntries() == 0; } + WARN_UNUSED_RESULT bool empty() const { return getNumEntries() == 0; } unsigned size() const { return getNumEntries(); } /// Grow the densemap so that it can contain at least \p NumEntries items /// before resizing again. void reserve(size_type NumEntries) { auto NumBuckets = getMinBucketToReserveForEntries(NumEntries); - incrementEpoch(); if (NumBuckets > getNumBuckets()) grow(NumBuckets); } void clear() { - incrementEpoch(); if (getNumEntries() == 0 && getNumTombstones() == 0) return; - // If the capacity of the array is huge, and the # elements used is small, - // shrink the array. - if (getNumEntries() * 4 < getNumBuckets() && getNumBuckets() > 64) { - shrink_and_clear(); - return; - } - const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); - if (std::is_trivially_destructible::value) { - // Use a simpler loop when values don't need destruction. - 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!"); - } + for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) + P->getFirst() = EmptyKey; + setNumEntries(0); setNumTombstones(0); } /// Return 1 if the specified key is in the map, 0 otherwise. - size_type count(const_arg_type_t Val) const { + size_type count(const KeyT &Val) const { const BucketT *TheBucket; return LookupBucketFor(Val, TheBucket) ? 1 : 0; } - iterator find(const_arg_type_t Val) { + value_type *find(const KeyT &Val) { BucketT *TheBucket; if (LookupBucketFor(Val, TheBucket)) - return makeIterator( - TheBucket, - shouldReverseIterate() ? getBuckets() : getBucketsEnd(), *this, - true); - return end(); + return TheBucket; + return nullptr; } - const_iterator find(const_arg_type_t Val) const { + const value_type *find(const KeyT &Val) const { const BucketT *TheBucket; if (LookupBucketFor(Val, TheBucket)) - return makeConstIterator( - TheBucket, - shouldReverseIterate() ? getBuckets() : getBucketsEnd(), *this, - true); - return end(); + return TheBucket; + return nullptr; } /// lookup - Return the entry for the specified key, or a default /// constructed value if no such entry exists. - ValueT lookup(const_arg_type_t Val) const { + ValueT lookup(const KeyT &Val) const { const BucketT *TheBucket; if (LookupBucketFor(Val, TheBucket)) return TheBucket->getSecond(); @@ -135,8 +85,14 @@ // Inserts key,value pair into the map if the key isn't already in the map. // If the key is already in the map, it returns false and doesn't update the // value. - std::pair insert(const std::pair &KV) { - return try_emplace(KV.first, KV.second); + detail::DenseMapPair insert(const value_type &KV) { + BucketT *TheBucket; + if (LookupBucketFor(KV.first, TheBucket)) + return {TheBucket, false}; // Already in map. + + // Otherwise, insert the new element. + TheBucket = InsertIntoBucket(TheBucket, KV.first, KV.second); + return {TheBucket, true}; } bool erase(const KeyT &Val) { @@ -144,15 +100,15 @@ if (!LookupBucketFor(Val, TheBucket)) return false; // not in map. - TheBucket->getSecond().~ValueT(); TheBucket->getFirst() = getTombstoneKey(); decrementNumEntries(); incrementNumTombstones(); return true; } - void erase(iterator I) { + + void erase(value_type *I) { + CHECK_NE(I, nullptr); BucketT *TheBucket = &*I; - TheBucket->getSecond().~ValueT(); TheBucket->getFirst() = getTombstoneKey(); decrementNumEntries(); incrementNumTombstones(); @@ -168,16 +124,27 @@ ValueT &operator[](const KeyT &Key) { return FindAndConstruct(Key).second; } - value_type &FindAndConstruct(KeyT &&Key) { - BucketT *TheBucket; - if (LookupBucketFor(Key, TheBucket)) - return *TheBucket; + /// Equality comparison for DenseMap. + /// + /// Iterates over elements of LHS confirming that each (key, value) pair in + /// LHS is also in RHS, and that no additional pairs are in RHS. Equivalent to + /// N calls to RHS.find and N value comparisons. Amortized complexity is + /// linear, worst case is O(N^2) (if every hash collides). + bool operator==(const DenseMapBase &RHS) const { + if (size() != RHS.size()) + return false; - return *InsertIntoBucket(TheBucket, std::move(Key)); - } + const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); + for (auto *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) { + const KeyT K = P->getFirst(); + if (K != EmptyKey && K != TombstoneKey) { + const auto *I = RHS.find(K); + if (!I || P->getSecond() != I->getSecond()) + return false; + } + } - ValueT &operator[](KeyT &&Key) { - return FindAndConstruct(std::move(Key)).second; + return true; } protected: @@ -187,11 +154,10 @@ setNumEntries(0); setNumTombstones(0); - assert((getNumBuckets() & (getNumBuckets() - 1)) == 0 && - "# initial buckets must be a power of two!"); + CHECK_EQ((getNumBuckets() & (getNumBuckets() - 1)), 0); const KeyT EmptyKey = getEmptyKey(); for (BucketT *B = getBuckets(), *E = getBucketsEnd(); B != E; ++B) - ::new (&B->getFirst()) KeyT(EmptyKey); + B->getFirst() = EmptyKey; } /// Returns the number of buckets to allocate to ensure that the DenseMap can @@ -202,7 +168,7 @@ return 0; // +1 is required because of the strict equality. // For example if NumEntries is 48, we need to return 401. - return NextPowerOf2(NumEntries * 4 / 3 + 1); + return detail::NextPowerOf2(NumEntries * 4 / 3 + 1); } void moveFromOldBuckets(BucketT *OldBucketsBegin, BucketT *OldBucketsEnd) { @@ -218,40 +184,24 @@ BucketT *DestBucket; bool FoundVal = LookupBucketFor(B->getFirst(), DestBucket); (void)FoundVal; // silence warning. - assert(!FoundVal && "Key already in new map?"); - DestBucket->getFirst() = std::move(B->getFirst()); - ::new (&DestBucket->getSecond()) ValueT(std::move(B->getSecond())); + CHECK(!FoundVal); + *DestBucket = *B; incrementNumEntries(); - - // Free the value. - B->getSecond().~ValueT(); } - B->getFirst().~KeyT(); } } template void copyFrom( const DenseMapBase &other) { - assert(&other != this); - assert(getNumBuckets() == other.getNumBuckets()); + CHECK_NE(&other, this); + CHECK_EQ(getNumBuckets(), other.getNumBuckets()); setNumEntries(other.getNumEntries()); setNumTombstones(other.getNumTombstones()); - if (std::is_trivially_copyable::value && - std::is_trivially_copyable::value) - memcpy(reinterpret_cast(getBuckets()), other.getBuckets(), - getNumBuckets() * sizeof(BucketT)); - else - for (size_t i = 0; i < getNumBuckets(); ++i) { - ::new (&getBuckets()[i].getFirst()) - KeyT(other.getBuckets()[i].getFirst()); - if (!KeyInfoT::isEqual(getBuckets()[i].getFirst(), getEmptyKey()) && - !KeyInfoT::isEqual(getBuckets()[i].getFirst(), getTombstoneKey())) - ::new (&getBuckets()[i].getSecond()) - ValueT(other.getBuckets()[i].getSecond()); - } + internal_memcpy(reinterpret_cast(getBuckets()), other.getBuckets(), + getNumBuckets() * sizeof(BucketT)); } static unsigned getHashValue(const KeyT &Val) { @@ -263,11 +213,7 @@ return KeyInfoT::getHashValue(Val); } - static const KeyT getEmptyKey() { - static_assert(std::is_base_of::value, - "Must pass the derived type to this template!"); - return KeyInfoT::getEmptyKey(); - } + static const KeyT getEmptyKey() { return KeyInfoT::getEmptyKey(); } static const KeyT getTombstoneKey() { return KeyInfoT::getTombstoneKey(); } @@ -314,13 +260,13 @@ void grow(unsigned AtLeast) { static_cast(this)->grow(AtLeast); } - template + template BucketT *InsertIntoBucket(BucketT *TheBucket, KeyArg &&Key, - ValueArgs &&...Values) { + const ValueArg &Value = ValueArg{}) { TheBucket = InsertIntoBucketImpl(Key, Key, TheBucket); - TheBucket->getFirst() = std::forward(Key); - ::new (&TheBucket->getSecond()) ValueT(std::forward(Values)...); + TheBucket->getFirst() = Key; + TheBucket->getSecond() = Value; return TheBucket; } @@ -329,8 +275,8 @@ ValueT &&Value, LookupKeyT &Lookup) { TheBucket = InsertIntoBucketImpl(Key, Lookup, TheBucket); - TheBucket->getFirst() = std::move(Key); - ::new (&TheBucket->getSecond()) ValueT(std::move(Value)); + TheBucket->getFirst() = Key; + TheBucket->getSecond() = Value; return TheBucket; } @@ -348,17 +294,16 @@ // causing infinite loops in lookup. unsigned NewNumEntries = getNumEntries() + 1; unsigned NumBuckets = getNumBuckets(); - if (LLVM_UNLIKELY(NewNumEntries * 4 >= NumBuckets * 3)) { + if (UNLIKELY(NewNumEntries * 4 >= NumBuckets * 3)) { this->grow(NumBuckets * 2); LookupBucketFor(Lookup, TheBucket); NumBuckets = getNumBuckets(); - } else if (LLVM_UNLIKELY(NumBuckets - - (NewNumEntries + getNumTombstones()) <= - NumBuckets / 8)) { + } else if (UNLIKELY(NumBuckets - (NewNumEntries + getNumTombstones()) <= + NumBuckets / 8)) { this->grow(NumBuckets); LookupBucketFor(Lookup, TheBucket); } - assert(TheBucket); + CHECK(TheBucket); // Only update the state after we've grown our bucket space appropriately // so that when growing buckets we have self-consistent entry count. @@ -391,23 +336,22 @@ const BucketT *FoundTombstone = nullptr; const KeyT EmptyKey = getEmptyKey(); const KeyT TombstoneKey = getTombstoneKey(); - assert(!KeyInfoT::isEqual(Val, EmptyKey) && - !KeyInfoT::isEqual(Val, TombstoneKey) && - "Empty/Tombstone value shouldn't be inserted into map!"); + CHECK(!KeyInfoT::isEqual(Val, EmptyKey)); + CHECK(!KeyInfoT::isEqual(Val, TombstoneKey)); unsigned BucketNo = getHashValue(Val) & (NumBuckets - 1); unsigned ProbeAmt = 1; while (true) { const BucketT *ThisBucket = BucketsPtr + BucketNo; // Found Val's bucket? If so, return it. - if (LLVM_LIKELY(KeyInfoT::isEqual(Val, ThisBucket->getFirst()))) { + if (LIKELY(KeyInfoT::isEqual(Val, ThisBucket->getFirst()))) { FoundBucket = ThisBucket; return true; } // If we found an empty bucket, the key doesn't exist in the set. // Insert it and return the default value. - if (LLVM_LIKELY(KeyInfoT::isEqual(ThisBucket->getFirst(), EmptyKey))) { + if (LIKELY(KeyInfoT::isEqual(ThisBucket->getFirst(), EmptyKey))) { // If we've already seen a tombstone while probing, fill it in instead // of the empty bucket we eventually probed to. FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket; @@ -441,7 +385,9 @@ /// This is just the raw memory used by DenseMap. /// If entries are pointers to objects, the size of the referenced objects /// are not included. - size_t getMemorySize() const { return getNumBuckets() * sizeof(BucketT); } + uptr getMemorySize() const { + return RoundUpTo(getNumBuckets() * sizeof(BucketT), GetPageSizeCached()); + } }; /// Inequality comparison for DenseMap. @@ -457,7 +403,7 @@ template , - typename BucketT = llvm::detail::DenseMapPair> + typename BucketT = detail::DenseMapPair> class DenseMap : public DenseMapBase, KeyT, ValueT, KeyInfoT, BucketT> { friend class DenseMapBase; @@ -466,15 +412,16 @@ // simplicity of referring to them. using BaseT = DenseMapBase; - BucketT *Buckets; - unsigned NumEntries; - unsigned NumTombstones; - unsigned NumBuckets; + BucketT *Buckets = nullptr; + unsigned NumEntries = 0; + unsigned NumTombstones = 0; + unsigned NumBuckets = 0; public: /// Create a DenseMap with an optional \p InitialReserve that guarantee that /// this number of elements can be inserted in the map without grow() - explicit DenseMap(unsigned InitialReserve = 0) { init(InitialReserve); } + explicit DenseMap(unsigned InitialReserve) { init(InitialReserve); } + constexpr DenseMap() = default; DenseMap(const DenseMap &other) : BaseT() { init(0); @@ -486,29 +433,13 @@ swap(other); } - template - DenseMap(const InputIt &I, const InputIt &E) { - init(std::distance(I, E)); - this->insert(I, E); - } - - DenseMap(std::initializer_list Vals) { - init(Vals.size()); - this->insert(Vals.begin(), Vals.end()); - } - - ~DenseMap() { - this->destroyAll(); - deallocate_buffer(Buckets, sizeof(BucketT) * NumBuckets, alignof(BucketT)); - } + ~DenseMap() { deallocate_buffer(Buckets, sizeof(BucketT) * NumBuckets); } void swap(DenseMap &RHS) { - this->incrementEpoch(); - RHS.incrementEpoch(); - std::swap(Buckets, RHS.Buckets); - std::swap(NumEntries, RHS.NumEntries); - std::swap(NumTombstones, RHS.NumTombstones); - std::swap(NumBuckets, RHS.NumBuckets); + Swap(Buckets, RHS.Buckets); + Swap(NumEntries, RHS.NumEntries); + Swap(NumTombstones, RHS.NumTombstones); + Swap(NumBuckets, RHS.NumBuckets); } DenseMap &operator=(const DenseMap &other) { @@ -518,8 +449,7 @@ } void copyFrom(const DenseMap &other) { - this->destroyAll(); - deallocate_buffer(Buckets, sizeof(BucketT) * NumBuckets, alignof(BucketT)); + deallocate_buffer(Buckets, sizeof(BucketT) * NumBuckets); if (allocateBuckets(other.NumBuckets)) { this->BaseT::copyFrom(other); } else { @@ -542,9 +472,9 @@ unsigned OldNumBuckets = NumBuckets; BucketT *OldBuckets = Buckets; - allocateBuckets(std::max( - 64, static_cast(NextPowerOf2(AtLeast - 1)))); - assert(Buckets); + allocateBuckets(Max( + 64, static_cast(detail::NextPowerOf2(AtLeast - 1)))); + CHECK(Buckets); if (!OldBuckets) { this->BaseT::initEmpty(); return; @@ -553,8 +483,7 @@ this->moveFromOldBuckets(OldBuckets, OldBuckets + OldNumBuckets); // Free the old table. - deallocate_buffer(OldBuckets, sizeof(BucketT) * OldNumBuckets, - alignof(BucketT)); + deallocate_buffer(OldBuckets, sizeof(BucketT) * OldNumBuckets); } private: @@ -577,10 +506,26 @@ return false; } - Buckets = static_cast( - allocate_buffer(sizeof(BucketT) * NumBuckets, alignof(BucketT))); + uptr Size = sizeof(BucketT) * NumBuckets; + if (Size * 2 <= GetPageSizeCached()) { + // We always allocate a page, use entire space. + unsigned Log2 = MostSignificantSetBitIndex(GetPageSizeCached() / Size); + Size <<= Log2; + NumBuckets <<= Log2; + CHECK_EQ(Size, sizeof(BucketT) * NumBuckets); + CHECK_GT(Size * 2, GetPageSizeCached()); + } + Buckets = static_cast(allocate_buffer(Size)); return true; } + + void *allocate_buffer(uptr Size) { + return MmapOrDie(RoundUpTo(Size, GetPageSizeCached()), "DenseMap"); + } + + void deallocate_buffer(void *Ptr, uptr Size) { + UnmapOrDie(Ptr, RoundUpTo(Size, GetPageSizeCached())); + } }; } // namespace __sanitizer diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_dense_map_info.h b/compiler-rt/lib/sanitizer_common/sanitizer_dense_map_info.h --- a/compiler-rt/lib/sanitizer_common/sanitizer_dense_map_info.h +++ b/compiler-rt/lib/sanitizer_common/sanitizer_dense_map_info.h @@ -17,7 +17,7 @@ /// Simplistic combination of 32-bit hash values into 32-bit hash values. static inline unsigned combineHashValue(unsigned a, unsigned b) { - uint64_t key = (uint64_t)a << 32 | (uint64_t)b; + u64 key = (u64)a << 32 | (u64)b; key += ~(key << 32); key ^= (key >> 22); key += ~(key << 13); @@ -29,6 +29,31 @@ return (unsigned)key; } +static inline u64 NextPowerOf2(u64 A) { + A |= (A >> 1); + A |= (A >> 2); + A |= (A >> 4); + A |= (A >> 8); + A |= (A >> 16); + A |= (A >> 32); + return A + 1; +} + +// We extend a pair to allow users to override the bucket type with their own +// implementation without requiring two members. +template +struct DenseMapPair { + KeyT first; + ValueT second; + DenseMapPair() = default; + DenseMapPair(const KeyT &f, const ValueT &s) : first(f), second(s) {} + + KeyT &getFirst() { return first; } + const KeyT &getFirst() const { return first; } + ValueT &getSecond() { return second; } + const ValueT &getSecond() const { return second; } +}; + } // end namespace detail template @@ -50,23 +75,22 @@ // static_assert(alignof(T) <= (1 << Log2MaxAlign), // "DenseMap does not support pointer keys requiring more than " // "Log2MaxAlign bits of alignment"); - static constexpr uintptr_t Log2MaxAlign = 12; + static constexpr uptr Log2MaxAlign = 12; static inline T *getEmptyKey() { - uintptr_t Val = static_cast(-1); + uptr Val = static_cast(-1); Val <<= Log2MaxAlign; return reinterpret_cast(Val); } static inline T *getTombstoneKey() { - uintptr_t Val = static_cast(-2); + uptr Val = static_cast(-2); Val <<= Log2MaxAlign; return reinterpret_cast(Val); } static unsigned getHashValue(const T *PtrVal) { - return (unsigned((uintptr_t)PtrVal) >> 4) ^ - (unsigned((uintptr_t)PtrVal) >> 9); + return (unsigned((uptr)PtrVal) >> 4) ^ (unsigned((uptr)PtrVal) >> 9); } static bool isEqual(const T *LHS, const T *RHS) { return LHS == RHS; } @@ -203,18 +227,19 @@ // Provide DenseMapInfo for all pairs whose members have info. template -struct DenseMapInfo> { - using Pair = std::pair; +struct DenseMapInfo> { + using Pair = detail::DenseMapPair; using FirstInfo = DenseMapInfo; using SecondInfo = DenseMapInfo; static inline Pair getEmptyKey() { - return std::make_pair(FirstInfo::getEmptyKey(), SecondInfo::getEmptyKey()); + return detail::DenseMapPair(FirstInfo::getEmptyKey(), + SecondInfo::getEmptyKey()); } static inline Pair getTombstoneKey() { - return std::make_pair(FirstInfo::getTombstoneKey(), - SecondInfo::getTombstoneKey()); + return detail::DenseMapPair(FirstInfo::getTombstoneKey(), + SecondInfo::getTombstoneKey()); } static unsigned getHashValue(const Pair &PairVal) { diff --git a/compiler-rt/lib/sanitizer_common/tests/CMakeLists.txt b/compiler-rt/lib/sanitizer_common/tests/CMakeLists.txt --- a/compiler-rt/lib/sanitizer_common/tests/CMakeLists.txt +++ b/compiler-rt/lib/sanitizer_common/tests/CMakeLists.txt @@ -17,6 +17,7 @@ sanitizer_chained_origin_depot_test.cpp sanitizer_common_test.cpp sanitizer_deadlock_detector_test.cpp + sanitizer_dense_map_test.cpp sanitizer_flags_test.cpp sanitizer_flat_map_test.cpp sanitizer_format_interceptor_test.cpp diff --git a/compiler-rt/lib/sanitizer_common/tests/sanitizer_dense_map_test.cpp b/compiler-rt/lib/sanitizer_common/tests/sanitizer_dense_map_test.cpp --- a/compiler-rt/lib/sanitizer_common/tests/sanitizer_dense_map_test.cpp +++ b/compiler-rt/lib/sanitizer_common/tests/sanitizer_dense_map_test.cpp @@ -18,6 +18,33 @@ namespace { +// Helps to keep some tests. +template , + typename BucketT = detail::DenseMapPair> +class TestDenseMap : public DenseMap { + using BaseT = DenseMap; + + public: + using BaseT::BaseT; + + TestDenseMap(std::initializer_list Vals) + : BaseT(Vals.size()) { + for (const auto &V : Vals) this->BaseT::insert(V); + } + + template + TestDenseMap(I B, I E) : BaseT(std::distance(B, E)) { + for (; B != E; ++B) + this->BaseT::insert(typename BaseT::value_type(B->first, B->second)); + } + + TestDenseMap(const TestDenseMap &other) : BaseT(other) {} +}; + +template +using DenseMap = TestDenseMap; + uint32_t getTestKey(int i, uint32_t *) { return i; } uint32_t getTestValue(int i, uint32_t *) { return 42 + i; } @@ -98,11 +125,9 @@ typename T::mapped_type *const DenseMapTest::dummy_value_ptr = nullptr; // Register these types for testing. -typedef ::testing::Types< - DenseMap, DenseMap, - DenseMap, - SmallDenseMap, SmallDenseMap, - SmallDenseMap> +typedef ::testing::Types, + DenseMap, + DenseMap> DenseMapTestTypes; TYPED_TEST_SUITE(DenseMapTest, DenseMapTestTypes, ); @@ -112,12 +137,9 @@ EXPECT_EQ(0u, this->Map.size()); EXPECT_TRUE(this->Map.empty()); - // Iterator tests - EXPECT_TRUE(this->Map.begin() == this->Map.end()); - // Lookup tests EXPECT_FALSE(this->Map.count(this->getKey())); - EXPECT_TRUE(this->Map.find(this->getKey()) == this->Map.end()); + EXPECT_EQ(nullptr, this->Map.find(this->getKey())); EXPECT_EQ(typename TypeParam::mapped_type(), this->Map.lookup(this->getKey())); } @@ -127,7 +149,6 @@ const TypeParam &ConstMap = this->Map; EXPECT_EQ(0u, ConstMap.size()); EXPECT_TRUE(ConstMap.empty()); - EXPECT_TRUE(ConstMap.begin() == ConstMap.end()); } // A map with a single entry @@ -136,19 +157,11 @@ // Size tests EXPECT_EQ(1u, this->Map.size()); - EXPECT_FALSE(this->Map.begin() == this->Map.end()); EXPECT_FALSE(this->Map.empty()); - // Iterator tests - typename TypeParam::iterator it = this->Map.begin(); - EXPECT_EQ(this->getKey(), it->first); - EXPECT_EQ(this->getValue(), it->second); - ++it; - EXPECT_TRUE(it == this->Map.end()); - // Lookup tests EXPECT_TRUE(this->Map.count(this->getKey())); - EXPECT_TRUE(this->Map.find(this->getKey()) == this->Map.begin()); + EXPECT_NE(nullptr, this->Map.find(this->getKey())); EXPECT_EQ(this->getValue(), this->Map.lookup(this->getKey())); EXPECT_EQ(this->getValue(), this->Map[this->getKey()]); } @@ -160,17 +173,15 @@ EXPECT_EQ(0u, this->Map.size()); EXPECT_TRUE(this->Map.empty()); - EXPECT_TRUE(this->Map.begin() == this->Map.end()); } // Test erase(iterator) method TYPED_TEST(DenseMapTest, EraseTest) { this->Map[this->getKey()] = this->getValue(); - this->Map.erase(this->Map.begin()); + this->Map.erase(this->Map.find(this->getKey())); EXPECT_EQ(0u, this->Map.size()); EXPECT_TRUE(this->Map.empty()); - EXPECT_TRUE(this->Map.begin() == this->Map.end()); } // Test erase(value) method @@ -180,12 +191,12 @@ EXPECT_EQ(0u, this->Map.size()); EXPECT_TRUE(this->Map.empty()); - EXPECT_TRUE(this->Map.begin() == this->Map.end()); } // Test insert() method TYPED_TEST(DenseMapTest, InsertTest) { - this->Map.insert(std::make_pair(this->getKey(), this->getValue())); + this->Map.insert( + typename TypeParam::value_type(this->getKey(), this->getValue())); EXPECT_EQ(1u, this->Map.size()); EXPECT_EQ(this->getValue(), this->Map[this->getKey()]); } @@ -293,25 +304,8 @@ } namespace { -// Simple class that counts how many moves and copy happens when growing a map -struct CountCopyAndMove { - static int Move; - static int Copy; - CountCopyAndMove() {} - - CountCopyAndMove(const CountCopyAndMove &) { Copy++; } - CountCopyAndMove &operator=(const CountCopyAndMove &) { - Copy++; - return *this; - } - CountCopyAndMove(CountCopyAndMove &&) { Move++; } - CountCopyAndMove &operator=(const CountCopyAndMove &&) { - Move++; - return *this; - } -}; -int CountCopyAndMove::Copy = 0; -int CountCopyAndMove::Move = 0; +// Simple empty structure. +struct Struct {}; } // anonymous namespace @@ -337,109 +331,59 @@ // Test for the default minimum size of a DenseMap TEST(DenseMapCustomTest, DefaultMinReservedSizeTest) { - // IF THIS VALUE CHANGE, please update InitialSizeTest, InitFromIterator, and - // ReserveTest as well! - const int ExpectedInitialBucketCount = 64; + const int ExpectedInitialBucketCount = 512; // Formula from DenseMap::getMinBucketToReserveForEntries() const int ExpectedMaxInitialEntries = ExpectedInitialBucketCount * 3 / 4 - 1; - DenseMap Map; + DenseMap Map; // Will allocate 64 buckets Map.reserve(1); unsigned MemorySize = Map.getMemorySize(); - CountCopyAndMove::Copy = 0; - CountCopyAndMove::Move = 0; for (int i = 0; i < ExpectedMaxInitialEntries; ++i) - Map.insert(std::pair(std::piecewise_construct, - std::forward_as_tuple(i), - std::forward_as_tuple())); + Map.insert(detail::DenseMapPair(i, {})); // Check that we didn't grow EXPECT_EQ(MemorySize, Map.getMemorySize()); - // Check that move was called the expected number of times - EXPECT_EQ(ExpectedMaxInitialEntries, CountCopyAndMove::Move); - // Check that no copy occurred - EXPECT_EQ(0, CountCopyAndMove::Copy); // Adding one extra element should grow the map - Map.insert(std::pair( - std::piecewise_construct, - std::forward_as_tuple(ExpectedMaxInitialEntries), - std::forward_as_tuple())); + Map.insert(detail::DenseMapPair(ExpectedMaxInitialEntries, {})); // Check that we grew EXPECT_NE(MemorySize, Map.getMemorySize()); - // Check that move was called the expected number of times - // This relies on move-construction elision, and cannot be reliably tested. - // EXPECT_EQ(ExpectedMaxInitialEntries + 2, CountCopyAndMove::Move); - // Check that no copy occurred - EXPECT_EQ(0, CountCopyAndMove::Copy); } // Make sure creating the map with an initial size of N actually gives us enough // buckets to insert N items without increasing allocation size. TEST(DenseMapCustomTest, InitialSizeTest) { - // Test a few different sizes, 48 is *not* a random choice: we need a value + // Test a few different size, 341 is *not* a random choice: we need a value // that is 2/3 of a power of two to stress the grow() condition, and the power - // of two has to be at least 64 because of minimum size allocation in the - // DenseMap (see DefaultMinReservedSizeTest). 66 is a value just above the - // 64 default init. - for (auto Size : {1, 2, 48, 66}) { - DenseMap Map(Size); + // of two has to be at least 512 because of minimum size allocation in the + // DenseMap (see DefaultMinReservedSizeTest). 513 is a value just above the + // 512 default init. + for (auto Size : {1, 2, 48, 66, 341, 513}) { + DenseMap Map(Size); unsigned MemorySize = Map.getMemorySize(); - CountCopyAndMove::Copy = 0; - CountCopyAndMove::Move = 0; for (int i = 0; i < Size; ++i) - Map.insert(std::pair(std::piecewise_construct, - std::forward_as_tuple(i), - std::forward_as_tuple())); + Map.insert(detail::DenseMapPair(i, {})); // Check that we didn't grow EXPECT_EQ(MemorySize, Map.getMemorySize()); - // Check that move was called the expected number of times - EXPECT_EQ(Size, CountCopyAndMove::Move); - // Check that no copy occurred - EXPECT_EQ(0, CountCopyAndMove::Copy); } } -// Make sure creating the map with a iterator range does not trigger grow() -TEST(DenseMapCustomTest, InitFromIterator) { - std::vector> Values; - // The size is a random value greater than 64 (hardcoded DenseMap min init) - const int Count = 65; - for (int i = 0; i < Count; i++) Values.emplace_back(i, CountCopyAndMove()); - - CountCopyAndMove::Move = 0; - CountCopyAndMove::Copy = 0; - DenseMap Map(Values.begin(), Values.end()); - // Check that no move occurred - EXPECT_EQ(0, CountCopyAndMove::Move); - // Check that copy was called the expected number of times - EXPECT_EQ(Count, CountCopyAndMove::Copy); -} - // Make sure reserve actually gives us enough buckets to insert N items // without increasing allocation size. TEST(DenseMapCustomTest, ReserveTest) { - // Test a few different size, 48 is *not* a random choice: we need a value + // Test a few different size, 341 is *not* a random choice: we need a value // that is 2/3 of a power of two to stress the grow() condition, and the power - // of two has to be at least 64 because of minimum size allocation in the - // DenseMap (see DefaultMinReservedSizeTest). 66 is a value just above the - // 64 default init. - for (auto Size : {1, 2, 48, 66}) { - DenseMap Map; + // of two has to be at least 512 because of minimum size allocation in the + // DenseMap (see DefaultMinReservedSizeTest). 513 is a value just above the + // 512 default init. + for (auto Size : {1, 2, 48, 66, 341, 513}) { + DenseMap Map; Map.reserve(Size); unsigned MemorySize = Map.getMemorySize(); - CountCopyAndMove::Copy = 0; - CountCopyAndMove::Move = 0; for (int i = 0; i < Size; ++i) - Map.insert(std::pair(std::piecewise_construct, - std::forward_as_tuple(i), - std::forward_as_tuple())); + Map.insert(detail::DenseMapPair(i, {})); // Check that we didn't grow EXPECT_EQ(MemorySize, Map.getMemorySize()); - // Check that move was called the expected number of times - EXPECT_EQ(Size, CountCopyAndMove::Move); - // Check that no copy occurred - EXPECT_EQ(0, CountCopyAndMove::Copy); } } @@ -475,7 +419,7 @@ EXPECT_EQ(1u, map.find(0)->second); EXPECT_EQ(2u, map.find(1)->second); EXPECT_EQ(3u, map.find(2)->second); - EXPECT_TRUE(map.find(3) == map.end()); + EXPECT_EQ(nullptr, map.find(3)); } struct IncompleteStruct; @@ -497,8 +441,8 @@ EXPECT_EQ(Map[K2], 2); EXPECT_EQ(Map[K3], 3); Map.clear(); - EXPECT_EQ(Map.find(K1), Map.end()); - EXPECT_EQ(Map.find(K2), Map.end()); - EXPECT_EQ(Map.find(K3), Map.end()); + EXPECT_EQ(nullptr, Map.find(K1)); + EXPECT_EQ(nullptr, Map.find(K2)); + EXPECT_EQ(nullptr, Map.find(K3)); } } // namespace