llvm/unittests/ADT/DenseSetTest.cpp

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