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