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 } 234