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 "gtest/gtest.h" 11 #include "llvm/ADT/DenseSet.h" 12 13 using namespace llvm; 14 15 namespace { 16 17 // Test fixture 18 class DenseSetTest : public testing::Test { 19 }; 20 21 // Test hashing with a set of only two entries. 22 TEST_F(DenseSetTest, DoubleEntrySetTest) { 23 llvm::DenseSet<unsigned> set(2); 24 set.insert(0); 25 set.insert(1); 26 // Original failure was an infinite loop in this call: 27 EXPECT_EQ(0u, set.count(2)); 28 } 29 30 struct TestDenseSetInfo { 31 static inline unsigned getEmptyKey() { return ~0; } 32 static inline unsigned getTombstoneKey() { return ~0U - 1; } 33 static unsigned getHashValue(const unsigned& Val) { return Val * 37U; } 34 static unsigned getHashValue(const char* Val) { 35 return (unsigned)(Val[0] - 'a') * 37U; 36 } 37 static bool isEqual(const unsigned& LHS, const unsigned& RHS) { 38 return LHS == RHS; 39 } 40 static bool isEqual(const char* LHS, const unsigned& RHS) { 41 return (unsigned)(LHS[0] - 'a') == RHS; 42 } 43 }; 44 45 TEST(DenseSetCustomTest, FindAsTest) { 46 DenseSet<unsigned, TestDenseSetInfo> set; 47 set.insert(0); 48 set.insert(1); 49 set.insert(2); 50 51 // Size tests 52 EXPECT_EQ(3u, set.size()); 53 54 // Normal lookup tests 55 EXPECT_EQ(1u, set.count(1)); 56 EXPECT_EQ(0u, *set.find(0)); 57 EXPECT_EQ(1u, *set.find(1)); 58 EXPECT_EQ(2u, *set.find(2)); 59 EXPECT_TRUE(set.find(3) == set.end()); 60 61 // find_as() tests 62 EXPECT_EQ(0u, *set.find_as("a")); 63 EXPECT_EQ(1u, *set.find_as("b")); 64 EXPECT_EQ(2u, *set.find_as("c")); 65 EXPECT_TRUE(set.find_as("d") == set.end()); 66 } 67 68 // Simple class that counts how many moves and copy happens when growing a map 69 struct CountCopyAndMove { 70 static int Move; 71 static int Copy; 72 int Value; 73 CountCopyAndMove(int Value) : Value(Value) {} 74 75 CountCopyAndMove(const CountCopyAndMove &RHS) { 76 Value = RHS.Value; 77 Copy++; 78 } 79 CountCopyAndMove &operator=(const CountCopyAndMove &RHS) { 80 Value = RHS.Value; 81 Copy++; 82 return *this; 83 } 84 CountCopyAndMove(CountCopyAndMove &&RHS) { 85 Value = RHS.Value; 86 Move++; 87 } 88 CountCopyAndMove &operator=(const CountCopyAndMove &&RHS) { 89 Value = RHS.Value; 90 Move++; 91 return *this; 92 } 93 }; 94 int CountCopyAndMove::Copy = 0; 95 int CountCopyAndMove::Move = 0; 96 } // anonymous namespace 97 98 namespace llvm { 99 // Specialization required to insert a CountCopyAndMove into a DenseSet. 100 template <> struct DenseMapInfo<CountCopyAndMove> { 101 static inline CountCopyAndMove getEmptyKey() { return CountCopyAndMove(-1); }; 102 static inline CountCopyAndMove getTombstoneKey() { 103 return CountCopyAndMove(-2); 104 }; 105 static unsigned getHashValue(const CountCopyAndMove &Val) { 106 return Val.Value; 107 } 108 static bool isEqual(const CountCopyAndMove &LHS, 109 const CountCopyAndMove &RHS) { 110 return LHS.Value == RHS.Value; 111 } 112 }; 113 } 114 115 namespace { 116 // Make sure reserve actually gives us enough buckets to insert N items 117 // without increasing allocation size. 118 TEST(DenseSetCustomTest, ReserveTest) { 119 // Test a few different size, 48 is *not* a random choice: we need a value 120 // that is 2/3 of a power of two to stress the grow() condition, and the power 121 // of two has to be at least 64 because of minimum size allocation in the 122 // DenseMa. 66 is a value just above the 64 default init. 123 for (auto Size : {1, 2, 48, 66}) { 124 DenseSet<CountCopyAndMove> Set; 125 Set.reserve(Size); 126 unsigned MemorySize = Set.getMemorySize(); 127 CountCopyAndMove::Copy = 0; 128 CountCopyAndMove::Move = 0; 129 for (int i = 0; i < Size; ++i) 130 Set.insert(CountCopyAndMove(i)); 131 // Check that we didn't grow 132 EXPECT_EQ(MemorySize, Set.getMemorySize()); 133 // Check that move was called the expected number of times 134 EXPECT_EQ(Size, CountCopyAndMove::Move); 135 // Check that no copy occured 136 EXPECT_EQ(0, CountCopyAndMove::Copy); 137 } 138 } 139 } 140