Index: ADT/DenseMapTest.cpp =================================================================== --- ADT/DenseMapTest.cpp +++ ADT/DenseMapTest.cpp @@ -362,6 +362,26 @@ } // anonymous namespace +// Test initializer list construction. +TEST(DenseMapCustomTest, InitializerList) { + DenseMap M({{0, 0}, {0, 1}, {1, 2}}); + EXPECT_EQ(2u, M.size()); + EXPECT_EQ(1u, M.count(0)); + EXPECT_EQ(0, M[0]); + EXPECT_EQ(1u, M.count(1)); + EXPECT_EQ(2, M[1]); +} + +// Test initializer list construction. +TEST(DenseMapCustomTest, EqualityComparison) { + DenseMap M1({{0, 0}, {1, 2}}); + DenseMap M2({{0, 0}, {1, 2}}); + DenseMap M3({{0, 0}, {1, 3}}); + + EXPECT_EQ(M1, M2); + EXPECT_NE(M1, M3); +} + // Test for the default minimum size of a DenseMap TEST(DenseMapCustomTest, DefaultMinReservedSizeTest) { // IF THIS VALUE CHANGE, please update InitialSizeTest, InitFromIterator, and Index: ADT/DenseSetTest.cpp =================================================================== --- ADT/DenseSetTest.cpp +++ ADT/DenseSetTest.cpp @@ -121,6 +121,15 @@ EXPECT_TRUE(set.find_as("d") == set.end()); } +TYPED_TEST(DenseSetTest, EqualityComparisonTest) { + TypeParam set1({1, 2, 3, 4}); + TypeParam set2({4, 3, 2, 1}); + TypeParam set3({2, 3, 4, 5}); + + EXPECT_EQ(set1, set2); + EXPECT_NE(set1, set3); +} + // Simple class that counts how many moves and copy happens when growing a map struct CountCopyAndMove { static int Move; Index: llvm/ADT/DenseMap.h =================================================================== --- llvm/ADT/DenseMap.h +++ llvm/ADT/DenseMap.h @@ -25,6 +25,7 @@ #include #include #include +#include #include #include #include @@ -38,6 +39,9 @@ // 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; } @@ -640,6 +644,40 @@ } }; +/// 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). +template +bool operator==( + const DenseMapBase &LHS, + const DenseMapBase &RHS) { + if (LHS.size() != RHS.size()) + return false; + + for (auto &KV : LHS) { + auto I = RHS.find(KV.first); + if (I == RHS.end() || I->second != KV.second) + return false; + } + + return true; +} + +/// Inequality comparison for DenseMap. +/// +/// Equivalent to !(LHS == RHS). See operator== for performance notes. +template +bool operator!=( + const DenseMapBase &LHS, + const DenseMapBase &RHS) { + return !(LHS == RHS); +} + template , typename BucketT = llvm::detail::DenseMapPair> @@ -677,6 +715,11 @@ this->insert(I, E); } + DenseMap(std::initializer_list Vals) { + init(Vals.size()); + this->insert(Vals.begin(), Vals.end()); + } + ~DenseMap() { this->destroyAll(); operator delete(Buckets); Index: llvm/ADT/DenseSet.h =================================================================== --- llvm/ADT/DenseSet.h +++ llvm/ADT/DenseSet.h @@ -214,6 +214,34 @@ } }; +/// Equality comparison for DenseSet. +/// +/// Iterates over elements of LHS confirming that each element is also a member +/// of RHS, and that RHS contains no additional values. +/// Equivalent to N calls to RHS.count. Amortized complexity is linear, worst +/// case is O(N^2) (if every hash collides). +template +bool operator==(const DenseSetImpl &LHS, + const DenseSetImpl &RHS) { + if (LHS.size() != RHS.size()) + return false; + + for (auto &E : LHS) + if (!RHS.count(E)) + return false; + + return true; +} + +/// Inequality comparison for DenseSet. +/// +/// Equivalent to !(LHS == RHS). See operator== for performance notes. +template +bool operator!=(const DenseSetImpl &LHS, + const DenseSetImpl &RHS) { + return !(LHS == RHS); +} + } // end namespace detail /// Implements a dense probed hash-table based set.