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