unittests/ADT/DenseSetTest.cpp

   1 //===- llvm/unittest/ADT/DenseSetTest.cpp - DenseSet unit tests --*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include "llvm/ADT/DenseSet.h"
  11 #include "gtest/gtest.h"
  12 #include <type_traits>
  13
  14 using namespace llvm;
  15
  16 namespace {
  17
  18 static_assert(std::is_const<std::remove_pointer<
  19                   DenseSet<int>::const_iterator::pointer>::type>::value,
  20               "Iterator pointer type should be const");
  21 static_assert(std::is_const<std::remove_reference<
  22                   DenseSet<int>::const_iterator::reference>::type>::value,
  23               "Iterator reference type should be const");
  24
  25 // Test hashing with a set of only two entries.
  26 TEST(DenseSetTest, DoubleEntrySetTest) {
  27   llvm::DenseSet<unsigned> set(2);
  28   set.insert(0);
  29   set.insert(1);
  30   // Original failure was an infinite loop in this call:
  31   EXPECT_EQ(0u, set.count(2));
  32 }
  33
  34 struct TestDenseSetInfo {
  35   static inline unsigned getEmptyKey() { return ~0; }
  36   static inline unsigned getTombstoneKey() { return ~0U - 1; }
  37   static unsigned getHashValue(const unsigned& Val) { return Val * 37U; }
  38   static unsigned getHashValue(const char* Val) {
  39     return (unsigned)(Val[0] - 'a') * 37U;
  40   }
  41   static bool isEqual(const unsigned& LHS, const unsigned& RHS) {
  42     return LHS == RHS;
  43   }
  44   static bool isEqual(const char* LHS, const unsigned& RHS) {
  45     return (unsigned)(LHS[0] - 'a') == RHS;
  46   }
  47 };
  48
  49 // Test fixture
  50 template <typename T> class DenseSetTest : public testing::Test {
  51 protected:
  52   T Set = GetTestSet();
  53
  54 private:
  55   static T GetTestSet() {
  56     typename std::remove_const<T>::type Set;
  57     Set.insert(0);
  58     Set.insert(1);
  59     Set.insert(2);
  60     return Set;
  61   }
  62 };
  63
  64 // Register these types for testing.
  65 typedef ::testing::Types<DenseSet<unsigned, TestDenseSetInfo>,
  66                          const DenseSet<unsigned, TestDenseSetInfo>,
  67                          SmallDenseSet<unsigned, 1, TestDenseSetInfo>,
  68                          SmallDenseSet<unsigned, 4, TestDenseSetInfo>,
  69                          const SmallDenseSet<unsigned, 4, TestDenseSetInfo>,
  70                          SmallDenseSet<unsigned, 64, TestDenseSetInfo>>
  71     DenseSetTestTypes;
  72 TYPED_TEST_CASE(DenseSetTest, DenseSetTestTypes);
  73
  74 TYPED_TEST(DenseSetTest, InitializerList) {
  75   TypeParam set({1, 2, 1, 4});
  76   EXPECT_EQ(3u, set.size());
  77   EXPECT_EQ(1u, set.count(1));
  78   EXPECT_EQ(1u, set.count(2));
  79   EXPECT_EQ(1u, set.count(4));
  80   EXPECT_EQ(0u, set.count(3));
  81 }
  82
  83 TYPED_TEST(DenseSetTest, ConstIteratorComparison) {
  84   TypeParam set({1});
  85   const TypeParam &cset = set;
  86   EXPECT_EQ(set.begin(), cset.begin());
  87   EXPECT_EQ(set.end(), cset.end());
  88   EXPECT_NE(set.end(), cset.begin());
  89   EXPECT_NE(set.begin(), cset.end());
  90 }
  91
  92 TYPED_TEST(DenseSetTest, DefaultConstruction) {
  93   typename TypeParam::iterator I, J;
  94   typename TypeParam::const_iterator CI, CJ;
  95   EXPECT_EQ(I, J);
  96   EXPECT_EQ(CI, CJ);
  97 }
  98
  99 TYPED_TEST(DenseSetTest, EmptyInitializerList) {
 100   TypeParam set({});
 101   EXPECT_EQ(0u, set.size());
 102   EXPECT_EQ(0u, set.count(0));
 103 }
 104
 105 TYPED_TEST(DenseSetTest, FindAsTest) {
 106   auto &set = this->Set;
 107   // Size tests
 108   EXPECT_EQ(3u, set.size());
 109
 110   // Normal lookup tests
 111   EXPECT_EQ(1u, set.count(1));
 112   EXPECT_EQ(0u, *set.find(0));
 113   EXPECT_EQ(1u, *set.find(1));
 114   EXPECT_EQ(2u, *set.find(2));
 115   EXPECT_TRUE(set.find(3) == set.end());
 116
 117   // find_as() tests
 118   EXPECT_EQ(0u, *set.find_as("a"));
 119   EXPECT_EQ(1u, *set.find_as("b"));
 120   EXPECT_EQ(2u, *set.find_as("c"));
 121   EXPECT_TRUE(set.find_as("d") == set.end());
 122 }
 123
 124 // Simple class that counts how many moves and copy happens when growing a map
 125 struct CountCopyAndMove {
 126   static int Move;
 127   static int Copy;
 128   int Value;
 129   CountCopyAndMove(int Value) : Value(Value) {}
 130
 131   CountCopyAndMove(const CountCopyAndMove &RHS) {
 132     Value = RHS.Value;
 133     Copy++;
 134   }
 135   CountCopyAndMove &operator=(const CountCopyAndMove &RHS) {
 136     Value = RHS.Value;
 137     Copy++;
 138     return *this;
 139   }
 140   CountCopyAndMove(CountCopyAndMove &&RHS) {
 141     Value = RHS.Value;
 142     Move++;
 143   }
 144   CountCopyAndMove &operator=(const CountCopyAndMove &&RHS) {
 145     Value = RHS.Value;
 146     Move++;
 147     return *this;
 148   }
 149 };
 150 int CountCopyAndMove::Copy = 0;
 151 int CountCopyAndMove::Move = 0;
 152 } // anonymous namespace
 153
 154 namespace llvm {
 155 // Specialization required to insert a CountCopyAndMove into a DenseSet.
 156 template <> struct DenseMapInfo<CountCopyAndMove> {
 157   static inline CountCopyAndMove getEmptyKey() { return CountCopyAndMove(-1); };
 158   static inline CountCopyAndMove getTombstoneKey() {
 159     return CountCopyAndMove(-2);
 160   };
 161   static unsigned getHashValue(const CountCopyAndMove &Val) {
 162     return Val.Value;
 163   }
 164   static bool isEqual(const CountCopyAndMove &LHS,
 165                       const CountCopyAndMove &RHS) {
 166     return LHS.Value == RHS.Value;
 167   }
 168 };
 169 }
 170
 171 namespace {
 172 // Make sure reserve actually gives us enough buckets to insert N items
 173 // without increasing allocation size.
 174 TEST(DenseSetCustomTest, ReserveTest) {
 175   // Test a few different size, 48 is *not* a random choice: we need a value
 176   // that is 2/3 of a power of two to stress the grow() condition, and the power
 177   // of two has to be at least 64 because of minimum size allocation in the
 178   // DenseMa. 66 is a value just above the 64 default init.
 179   for (auto Size : {1, 2, 48, 66}) {
 180     DenseSet<CountCopyAndMove> Set;
 181     Set.reserve(Size);
 182     unsigned MemorySize = Set.getMemorySize();
 183     CountCopyAndMove::Copy = 0;
 184     CountCopyAndMove::Move = 0;
 185     for (int i = 0; i < Size; ++i)
 186       Set.insert(CountCopyAndMove(i));
 187     // Check that we didn't grow
 188     EXPECT_EQ(MemorySize, Set.getMemorySize());
 189     // Check that move was called the expected number of times
 190     EXPECT_EQ(Size, CountCopyAndMove::Move);
 191     // Check that no copy occurred
 192     EXPECT_EQ(0, CountCopyAndMove::Copy);
 193   }
 194 }
 195 TEST(DenseSetCustomTest, ConstTest) {
 196   // Test that const pointers work okay for count and find, even when the
 197   // underlying map is a non-const pointer.
 198   DenseSet<int *> Map;
 199   int A;
 200   int *B = &A;
 201   const int *C = &A;
 202   Map.insert(B);
 203   EXPECT_EQ(Map.count(B), 1u);
 204   EXPECT_EQ(Map.count(C), 1u);
 205   EXPECT_NE(Map.find(B), Map.end());
 206   EXPECT_NE(Map.find(C), Map.end());
 207 }
 208 }