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