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