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 // Test hashing with a set of only two entries. 19 TEST(DenseSetTest, DoubleEntrySetTest) { 20 llvm::DenseSet<unsigned> set(2); 21 set.insert(0); 22 set.insert(1); 23 // Original failure was an infinite loop in this call: 24 EXPECT_EQ(0u, set.count(2)); 25 } 26 27 struct TestDenseSetInfo { 28 static inline unsigned getEmptyKey() { return ~0; } 29 static inline unsigned getTombstoneKey() { return ~0U - 1; } 30 static unsigned getHashValue(const unsigned& Val) { return Val * 37U; } 31 static unsigned getHashValue(const char* Val) { 32 return (unsigned)(Val[0] - 'a') * 37U; 33 } 34 static bool isEqual(const unsigned& LHS, const unsigned& RHS) { 35 return LHS == RHS; 36 } 37 static bool isEqual(const char* LHS, const unsigned& RHS) { 38 return (unsigned)(LHS[0] - 'a') == RHS; 39 } 40 }; 41 42 // Test fixture 43 template <typename T> class DenseSetTest : public testing::Test { 44 protected: 45 T Set = GetTestSet(); 46 47 private: 48 static T GetTestSet() { 49 typename std::remove_const<T>::type Set; 50 Set.insert(0); 51 Set.insert(1); 52 Set.insert(2); 53 return Set; 54 } 55 }; 56 57 // Register these types for testing. 58 typedef ::testing::Types<DenseSet<unsigned, TestDenseSetInfo>, 59 const DenseSet<unsigned, TestDenseSetInfo>, 60 SmallDenseSet<unsigned, 1, TestDenseSetInfo>, 61 SmallDenseSet<unsigned, 4, TestDenseSetInfo>, 62 const SmallDenseSet<unsigned, 4, TestDenseSetInfo>, 63 SmallDenseSet<unsigned, 64, TestDenseSetInfo>> 64 DenseSetTestTypes; 65 TYPED_TEST_CASE(DenseSetTest, DenseSetTestTypes); 66 67 TYPED_TEST(DenseSetTest, InitializerList) { 68 TypeParam set({1, 2, 1, 4}); 69 EXPECT_EQ(3u, set.size()); 70 EXPECT_EQ(1u, set.count(1)); 71 EXPECT_EQ(1u, set.count(2)); 72 EXPECT_EQ(1u, set.count(4)); 73 EXPECT_EQ(0u, set.count(3)); 74 } 75 76 TYPED_TEST(DenseSetTest, ConstIteratorComparison){ 77 TypeParam set({1}); 78 const TypeParam &cset = set; 79 EXPECT_EQ(set.begin(), cset.begin()); 80 EXPECT_EQ(set.end(), cset.end()); 81 EXPECT_NE(set.end(), cset.begin()); 82 EXPECT_NE(set.begin(), cset.end()); 83 } 84 85 TYPED_TEST(DenseSetTest, EmptyInitializerList) { 86 TypeParam set({}); 87 EXPECT_EQ(0u, set.size()); 88 EXPECT_EQ(0u, set.count(0)); 89 } 90 91 TYPED_TEST(DenseSetTest, FindAsTest) { 92 auto &set = this->Set; 93 // Size tests 94 EXPECT_EQ(3u, set.size()); 95 96 // Normal lookup tests 97 EXPECT_EQ(1u, set.count(1)); 98 EXPECT_EQ(0u, *set.find(0)); 99 EXPECT_EQ(1u, *set.find(1)); 100 EXPECT_EQ(2u, *set.find(2)); 101 EXPECT_TRUE(set.find(3) == set.end()); 102 103 // find_as() tests 104 EXPECT_EQ(0u, *set.find_as("a")); 105 EXPECT_EQ(1u, *set.find_as("b")); 106 EXPECT_EQ(2u, *set.find_as("c")); 107 EXPECT_TRUE(set.find_as("d") == set.end()); 108 } 109 110 // Simple class that counts how many moves and copy happens when growing a map 111 struct CountCopyAndMove { 112 static int Move; 113 static int Copy; 114 int Value; 115 CountCopyAndMove(int Value) : Value(Value) {} 116 117 CountCopyAndMove(const CountCopyAndMove &RHS) { 118 Value = RHS.Value; 119 Copy++; 120 } 121 CountCopyAndMove &operator=(const CountCopyAndMove &RHS) { 122 Value = RHS.Value; 123 Copy++; 124 return *this; 125 } 126 CountCopyAndMove(CountCopyAndMove &&RHS) { 127 Value = RHS.Value; 128 Move++; 129 } 130 CountCopyAndMove &operator=(const CountCopyAndMove &&RHS) { 131 Value = RHS.Value; 132 Move++; 133 return *this; 134 } 135 }; 136 int CountCopyAndMove::Copy = 0; 137 int CountCopyAndMove::Move = 0; 138 } // anonymous namespace 139 140 namespace llvm { 141 // Specialization required to insert a CountCopyAndMove into a DenseSet. 142 template <> struct DenseMapInfo<CountCopyAndMove> { 143 static inline CountCopyAndMove getEmptyKey() { return CountCopyAndMove(-1); }; 144 static inline CountCopyAndMove getTombstoneKey() { 145 return CountCopyAndMove(-2); 146 }; 147 static unsigned getHashValue(const CountCopyAndMove &Val) { 148 return Val.Value; 149 } 150 static bool isEqual(const CountCopyAndMove &LHS, 151 const CountCopyAndMove &RHS) { 152 return LHS.Value == RHS.Value; 153 } 154 }; 155 } 156 157 namespace { 158 // Make sure reserve actually gives us enough buckets to insert N items 159 // without increasing allocation size. 160 TEST(DenseSetCustomTest, ReserveTest) { 161 // Test a few different size, 48 is *not* a random choice: we need a value 162 // that is 2/3 of a power of two to stress the grow() condition, and the power 163 // of two has to be at least 64 because of minimum size allocation in the 164 // DenseMa. 66 is a value just above the 64 default init. 165 for (auto Size : {1, 2, 48, 66}) { 166 DenseSet<CountCopyAndMove> Set; 167 Set.reserve(Size); 168 unsigned MemorySize = Set.getMemorySize(); 169 CountCopyAndMove::Copy = 0; 170 CountCopyAndMove::Move = 0; 171 for (int i = 0; i < Size; ++i) 172 Set.insert(CountCopyAndMove(i)); 173 // Check that we didn't grow 174 EXPECT_EQ(MemorySize, Set.getMemorySize()); 175 // Check that move was called the expected number of times 176 EXPECT_EQ(Size, CountCopyAndMove::Move); 177 // Check that no copy occured 178 EXPECT_EQ(0, CountCopyAndMove::Copy); 179 } 180 } 181 } 182