[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

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

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

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

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.

include/llvm/ADT/DenseMap.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>
 #include <cstddef>
 #include <cstring>
+#include <initializer_list>
 #include <iterator>
 #include <new>
 #include <type_traits>
 #include <utility>
 
 namespace llvm {
 
 namespace detail {
 
 // We extend a pair to allow users to override the bucket type with their own
 // 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; }
   const ValueT &getSecond() const { return std::pair<KeyT, ValueT>::second; }
 };
 
 } // end namespace detail
 
public:
   /// 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);
   }
 };
 
+/// Equality comparison for DenseMapBase.
+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 LHSI = LHS.begin(), RHSI = RHS.begin(), E = LHS.end(); LHSI != E;
+       ++LHSI, ++RHSI)
+    if (*LHSI != *RHSI)
+      return false;
+  return true;
+}
+
+/// Inequality comparison for DenseMapBase.
+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>>
 class DenseMap : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT, BucketT>,
                                      KeyT, ValueT, KeyInfoT, BucketT> {
   friend class DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT, BucketT>;
 
   // Lift some types from the dependent base class into this class for
public:
   }
 
   template<typename InputIt>
   DenseMap(const InputIt &I, const InputIt &E) {
     init(std::distance(I, E));
     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);
   }
 
   void swap(DenseMap& RHS) {
     this->incrementEpoch();
     RHS.incrementEpoch();

include/llvm/ADT/DenseSet.h

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ADT_DENSESET_H
 #define LLVM_ADT_DENSESET_H
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseMapInfo.h"
+#include "llvm/Support/MathExtras.h"
 #include "llvm/Support/type_traits.h"
 #include <algorithm>
 #include <cstddef>
 #include <initializer_list>
 #include <iterator>
 #include <utility>
 
 namespace llvm {

 public:
   using key_type = ValueT;
   using value_type = ValueT;
   using size_type = unsigned;
 
   explicit DenseSetImpl(unsigned InitialReserve = 0) : TheMap(InitialReserve) {}
 
   DenseSetImpl(std::initializer_list<ValueT> Elems)
-      : DenseSetImpl(Elems.size()) {
+      : DenseSetImpl(NextPowerOf2(Elems.size())) {
     insert(Elems.begin(), Elems.end());
   }
 
   bool empty() const { return TheMap.empty(); }
   size_type size() const { return TheMap.size(); }
   size_t getMemorySize() const { return TheMap.getMemorySize(); }
 
   /// Grow the DenseSet so that it has at least Size buckets. Will not shrink
public:
   // Range insertion of values.
   template<typename InputIt>
   void insert(InputIt I, InputIt E) {
     for (; I != E; ++I)
       insert(*I);
   }
 };
 
+/// Equality comparison for DenseSet.
+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 LHSI = LHS.begin(), RHSI = RHS.begin(), E = LHS.end(); LHSI != E;
+       ++LHSI, ++RHSI)
+    if (*LHSI != *RHSI)
+      return false;
+  return true;
+}
+
+/// Inequality comparison for DenseSet.
+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.
 template <typename ValueT, typename ValueInfoT = DenseMapInfo<ValueT>>
 class DenseSet : public detail::DenseSetImpl<
                      ValueT, DenseMap<ValueT, detail::DenseSetEmpty, ValueInfoT,
                                       detail::DenseSetPair<ValueT>>,
                      ValueInfoT> {

unittests/ADT/DenseMapTest.cpp

CountCopyAndMove &operator=(const CountCopyAndMove &&) {
     return *this;
   }
 };
 int CountCopyAndMove::Copy = 0;
 int CountCopyAndMove::Move = 0;
 
 } // 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
   // ReserveTest as well!
   const int ExpectedInitialBucketCount = 64;
   // Formula from DenseMap::getMinBucketToReserveForEntries()
   const int ExpectedMaxInitialEntries = ExpectedInitialBucketCount * 3 / 4 - 1;
 

unittests/ADT/DenseSetTest.cpp

TYPED_TEST(DenseSetTest, FindAsTest) {
 
   // find_as() tests
   EXPECT_EQ(0u, *set.find_as("a"));
   EXPECT_EQ(1u, *set.find_as("b"));
   EXPECT_EQ(2u, *set.find_as("c"));
   EXPECT_TRUE(set.find_as("d") == set.end());
 }
 
+TYPED_TEST(DenseSetTest, EqualityComparisonTest) {
+  TypeParam set1({1, 2, 3});
+  TypeParam set2({1,2,3});
+  TypeParam set3({1,2,4});
+
+  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;
   static int Copy;
   int Value;
   CountCopyAndMove(int Value) : Value(Value) {}
 
   CountCopyAndMove(const CountCopyAndMove &RHS) {