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, EmptyInitializerList) { 77 TypeParam set({}); 78 EXPECT_EQ(0u, set.size()); 79 EXPECT_EQ(0u, set.count(0)); 80 } 81 82 TYPED_TEST(DenseSetTest, FindAsTest) { 83 auto &set = this->Set; 84 // Size tests 85 EXPECT_EQ(3u, set.size()); 86 87 // Normal lookup tests 88 EXPECT_EQ(1u, set.count(1)); 89 EXPECT_EQ(0u, *set.find(0)); 90 EXPECT_EQ(1u, *set.find(1)); 91 EXPECT_EQ(2u, *set.find(2)); 92 EXPECT_TRUE(set.find(3) == set.end()); 93 94 // find_as() tests 95 EXPECT_EQ(0u, *set.find_as("a")); 96 EXPECT_EQ(1u, *set.find_as("b")); 97 EXPECT_EQ(2u, *set.find_as("c")); 98 EXPECT_TRUE(set.find_as("d") == set.end()); 99 } 100 101 // Simple class that counts how many moves and copy happens when growing a map 102 struct CountCopyAndMove { 103 static int Move; 104 static int Copy; 105 int Value; 106 CountCopyAndMove(int Value) : Value(Value) {} 107 108 CountCopyAndMove(const CountCopyAndMove &RHS) { 109 Value = RHS.Value; 110 Copy++; 111 } 112 CountCopyAndMove &operator=(const CountCopyAndMove &RHS) { 113 Value = RHS.Value; 114 Copy++; 115 return *this; 116 } 117 CountCopyAndMove(CountCopyAndMove &&RHS) { 118 Value = RHS.Value; 119 Move++; 120 } 121 CountCopyAndMove &operator=(const CountCopyAndMove &&RHS) { 122 Value = RHS.Value; 123 Move++; 124 return *this; 125 } 126 }; 127 int CountCopyAndMove::Copy = 0; 128 int CountCopyAndMove::Move = 0; 129 } // anonymous namespace 130 131 namespace llvm { 132 // Specialization required to insert a CountCopyAndMove into a DenseSet. 133 template <> struct DenseMapInfo<CountCopyAndMove> { 134 static inline CountCopyAndMove getEmptyKey() { return CountCopyAndMove(-1); }; 135 static inline CountCopyAndMove getTombstoneKey() { 136 return CountCopyAndMove(-2); 137 }; 138 static unsigned getHashValue(const CountCopyAndMove &Val) { 139 return Val.Value; 140 } 141 static bool isEqual(const CountCopyAndMove &LHS, 142 const CountCopyAndMove &RHS) { 143 return LHS.Value == RHS.Value; 144 } 145 }; 146 } 147 148 namespace { 149 // Make sure reserve actually gives us enough buckets to insert N items 150 // without increasing allocation size. 151 TEST(DenseSetCustomTest, ReserveTest) { 152 // Test a few different size, 48 is *not* a random choice: we need a value 153 // that is 2/3 of a power of two to stress the grow() condition, and the power 154 // of two has to be at least 64 because of minimum size allocation in the 155 // DenseMa. 66 is a value just above the 64 default init. 156 for (auto Size : {1, 2, 48, 66}) { 157 DenseSet<CountCopyAndMove> Set; 158 Set.reserve(Size); 159 unsigned MemorySize = Set.getMemorySize(); 160 CountCopyAndMove::Copy = 0; 161 CountCopyAndMove::Move = 0; 162 for (int i = 0; i < Size; ++i) 163 Set.insert(CountCopyAndMove(i)); 164 // Check that we didn't grow 165 EXPECT_EQ(MemorySize, Set.getMemorySize()); 166 // Check that move was called the expected number of times 167 EXPECT_EQ(Size, CountCopyAndMove::Move); 168 // Check that no copy occured 169 EXPECT_EQ(0, CountCopyAndMove::Copy); 170 } 171 } 172 } 173