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 &) { Copy++; } 76 CountCopyAndMove &operator=(const CountCopyAndMove &) { 77 Copy++; 78 return *this; 79 } 80 CountCopyAndMove(CountCopyAndMove &&) { Move++; } 81 CountCopyAndMove &operator=(const CountCopyAndMove &&) { 82 Move++; 83 return *this; 84 } 85 }; 86 int CountCopyAndMove::Copy = 0; 87 int CountCopyAndMove::Move = 0; 88 } // anonymous namespace 89 90 namespace llvm { 91 // Specialization required to insert a CountCopyAndMove into a DenseSet. 92 template <> struct DenseMapInfo<CountCopyAndMove> { 93 static inline CountCopyAndMove getEmptyKey() { return CountCopyAndMove(-1); }; 94 static inline CountCopyAndMove getTombstoneKey() { 95 return CountCopyAndMove(-2); 96 }; 97 static unsigned getHashValue(const CountCopyAndMove &Val) { 98 return Val.Value; 99 } 100 static bool isEqual(const CountCopyAndMove &LHS, 101 const CountCopyAndMove &RHS) { 102 return LHS.Value == RHS.Value; 103 } 104 }; 105 } 106 107 namespace { 108 // Make sure reserve actually gives us enough buckets to insert N items 109 // without increasing allocation size. 110 TEST(DenseSetCustomTest, ReserveTest) { 111 // Test a few different size, 48 is *not* a random choice: we need a value 112 // that is 2/3 of a power of two to stress the grow() condition, and the power 113 // of two has to be at least 64 because of minimum size allocation in the 114 // DenseMa. 66 is a value just above the 64 default init. 115 for (auto Size : {1, 2, 48, 66}) { 116 DenseSet<CountCopyAndMove> Set; 117 Set.reserve(Size); 118 unsigned MemorySize = Set.getMemorySize(); 119 CountCopyAndMove::Copy = 0; 120 CountCopyAndMove::Move = 0; 121 for (int i = 0; i < Size; ++i) 122 Set.insert(CountCopyAndMove(i)); 123 // Check that we didn't grow 124 EXPECT_EQ(MemorySize, Set.getMemorySize()); 125 // Check that move was called the expected number of times 126 EXPECT_EQ(Size, CountCopyAndMove::Move); 127 // Check that no copy occured 128 EXPECT_EQ(0, CountCopyAndMove::Copy); 129 } 130 } 131 } 132