[ADT] Add initializer_list constructor, equality tests for DenseMap/DenseSet.

[lhames]

Summary

Adds an initializer_list constructor to DenseMap and fixes a bug in the
initializer_list constructor for DenseSet (it previously crashed on
initializer_lists whose lengths were not a power of two).

Also adds equality and inequality operators for DenseMap and DenseSet.

These changes make it easier to migrate existing code that uses std::map and
std::set (which support initializer_list construction and equality comparison)
to DenseMap and DenseSet.

[dblaikie]

Might be good to separate this into three or four (five? maybe, given the change to the DenseSet initial capacity?) separate changes - but mostly the only interesting question for me is about the equality

include/llvm/ADT/DenseMap.h

656–659 ↗

(On Diff #169581)

Is this guaranteed to work, given the lack of ordering guarantees? I think the order can depend on insertion order - so equivalent containers might have different iteration orders, perhaps?

[lhames]

include/llvm/ADT/DenseMap.h

656–659 ↗

(On Diff #169581)

Good point. No -- this won't work.

This was mostly a convenience for unit tests, so dropping it (at the cost of some slightly more verbose unit tests) seems like the best solution.

[lhames]

include/llvm/ADT/DenseMap.h

656–659 ↗

(On Diff #169581)

Alternatively they could be implemented by iterating over one structure and testing that the corresponding element is present in the other. In either case I think I'll want some extra comments for them, so I will break the equality tests out into a separate patch.

[lhames]

Broke out https://reviews.llvm.org/D53260 for the DenseSet bug fix.

[dblaikie]

include/llvm/ADT/DenseMap.h

656–659 ↗

(On Diff #169581)

Yeah, sounds pretty reasonable to me.

Yeah, looks like the standard containers have similar complexity (amortized linear (since the lookups are amortized constant), worst case N^2 (if all the elements hash collide))

"Proportional to N calls to operator== on value_type, calls to the predicate returned by key_eq, and calls to the hasher returned by hash_function, in the average case, proportional to N2 in the worst case where N is the size of the container." - https://en.cppreference.com/w/cpp/container/unordered_set/operator_cmp

[lhames]

Updated to remove the dependence on stable iteration order for operator== (on both DenseMap and DenseSet). Also adds some comments on performance.

I decided to leave the initializer_list constructor for DenseMap in this patch, as it simplifies unit testing: The equality operators are the easiest way to test that DenseMap construction behaved as expected and vice-versa.

[dblaikie]

Looks good - thanks!

[lhames]

Committed in r344522.

ADT/DenseMapTest.cpp

 
 } // anonymous namespace
 
+// Test initializer list construction.
+TEST(DenseMapCustomTest, InitializerList) {
+  DenseMap<int, int> 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<int, int> M1({{0, 0}, {1, 2}});
+  DenseMap<int, int> M2({{0, 0}, {1, 2}});
+  DenseMap<int, int> 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

ADT/DenseSetTest.cpp

   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;

llvm/ADT/DenseMap.h

 #include <cassert>
 #include <cstddef>
 #include <cstring>
+#include <initializer_list>
 #include <iterator>
 #include <new>
 #include <type_traits>

 // implementation without requiring two members.
 template <typename KeyT, typename ValueT>
 struct DenseMapPair : public std::pair<KeyT, ValueT> {
+
+  using std::pair<KeyT, ValueT>::pair;
+
   KeyT &getFirst() { return std::pair<KeyT, ValueT>::first; }
   const KeyT &getFirst() const { return std::pair<KeyT, ValueT>::first; }
   ValueT &getSecond() { return std::pair<KeyT, ValueT>::second; }

   }
 };
 
+/// 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 <typename DerivedT, typename KeyT, typename ValueT, typename KeyInfoT,
+          typename BucketT>
+bool operator==(
+    const DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT> &LHS,
+    const DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT> &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 <typename DerivedT, typename KeyT, typename ValueT, typename KeyInfoT,
+          typename BucketT>
+bool operator!=(
+    const DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT> &LHS,
+    const DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT> &RHS) {
+  return !(LHS == RHS);
+}
+
 template <typename KeyT, typename ValueT,
           typename KeyInfoT = DenseMapInfo<KeyT>,
           typename BucketT = llvm::detail::DenseMapPair<KeyT, ValueT>>

     this->insert(I, E);
   }
 
+  DenseMap(std::initializer_list<typename BaseT::value_type> Vals) {
+    init(Vals.size());
+    this->insert(Vals.begin(), Vals.end());
+  }
+
   ~DenseMap() {
     this->destroyAll();
     operator delete(Buckets);

llvm/ADT/DenseSet.h

   }
 };
 
+/// 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 <typename ValueT, typename MapTy, typename ValueInfoT>
+bool operator==(const DenseSetImpl<ValueT, MapTy, ValueInfoT> &LHS,
+                const DenseSetImpl<ValueT, MapTy, ValueInfoT> &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 <typename ValueT, typename MapTy, typename ValueInfoT>
+bool operator!=(const DenseSetImpl<ValueT, MapTy, ValueInfoT> &LHS,
+                const DenseSetImpl<ValueT, MapTy, ValueInfoT> &RHS) {
+  return !(LHS == RHS);
+}
+
 } // end namespace detail
 
 /// Implements a dense probed hash-table based set.