1//===- llvm/unittest/ADT/FoldingSetTest.cpp -------------------------------===// 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// FoldingSet unit tests. 11// 12//===----------------------------------------------------------------------===// 13 14#include "gtest/gtest.h" 15#include "llvm/ADT/FoldingSet.h" 16#include <string> 17 18using namespace llvm; 19 20namespace { 21 22// Unaligned string test. 23TEST(FoldingSetTest, UnalignedStringTest) { 24 SCOPED_TRACE("UnalignedStringTest"); 25 26 FoldingSetNodeID a, b; 27 // An aligned string. 28 std::string str1= "a test string"; 29 a.AddString(str1); 30 31 // An unaligned string. 32 std::string str2 = ">" + str1; 33 b.AddString(str2.c_str() + 1); 34 35 EXPECT_EQ(a.ComputeHash(), b.ComputeHash()); 36} 37 38struct TrivialPair : public FoldingSetNode { 39 unsigned Key = 0; 40 unsigned Value = 0; 41 TrivialPair(unsigned K, unsigned V) : FoldingSetNode(), Key(K), Value(V) {} 42 43 void Profile(FoldingSetNodeID &ID) const { 44 ID.AddInteger(Key); 45 ID.AddInteger(Value); 46 } 47}; 48 49TEST(FoldingSetTest, IDComparison) { 50 FoldingSet<TrivialPair> Trivial; 51 52 TrivialPair T(99, 42); 53 Trivial.InsertNode(&T); 54 55 void *InsertPos = nullptr; 56 FoldingSetNodeID ID; 57 T.Profile(ID); 58 TrivialPair *N = Trivial.FindNodeOrInsertPos(ID, InsertPos); 59 EXPECT_EQ(&T, N); 60 EXPECT_EQ(nullptr, InsertPos); 61} 62 63TEST(FoldingSetTest, MissedIDComparison) { 64 FoldingSet<TrivialPair> Trivial; 65 66 TrivialPair S(100, 42); 67 TrivialPair T(99, 42); 68 Trivial.InsertNode(&T); 69 70 void *InsertPos = nullptr; 71 FoldingSetNodeID ID; 72 S.Profile(ID); 73 TrivialPair *N = Trivial.FindNodeOrInsertPos(ID, InsertPos); 74 EXPECT_EQ(nullptr, N); 75 EXPECT_NE(nullptr, InsertPos); 76} 77 78TEST(FoldingSetTest, RemoveNodeThatIsPresent) { 79 FoldingSet<TrivialPair> Trivial; 80 81 TrivialPair T(99, 42); 82 Trivial.InsertNode(&T); 83 EXPECT_EQ(Trivial.size(), 1U); 84 85 bool WasThere = Trivial.RemoveNode(&T); 86 EXPECT_TRUE(WasThere); 87 EXPECT_EQ(0U, Trivial.size()); 88} 89 90TEST(FoldingSetTest, RemoveNodeThatIsAbsent) { 91 FoldingSet<TrivialPair> Trivial; 92 93 TrivialPair T(99, 42); 94 bool WasThere = Trivial.RemoveNode(&T); 95 EXPECT_FALSE(WasThere); 96 EXPECT_EQ(0U, Trivial.size()); 97} 98 99TEST(FoldingSetTest, GetOrInsertInserting) { 100 FoldingSet<TrivialPair> Trivial; 101 102 TrivialPair T(99, 42); 103 TrivialPair *N = Trivial.GetOrInsertNode(&T); 104 EXPECT_EQ(&T, N); 105} 106 107TEST(FoldingSetTest, GetOrInsertGetting) { 108 FoldingSet<TrivialPair> Trivial; 109 110 TrivialPair T(99, 42); 111 TrivialPair T2(99, 42); 112 Trivial.InsertNode(&T); 113 TrivialPair *N = Trivial.GetOrInsertNode(&T2); 114 EXPECT_EQ(&T, N); 115} 116 117TEST(FoldingSetTest, InsertAtPos) { 118 FoldingSet<TrivialPair> Trivial; 119 120 void *InsertPos = nullptr; 121 TrivialPair Finder(99, 42); 122 FoldingSetNodeID ID; 123 Finder.Profile(ID); 124 Trivial.FindNodeOrInsertPos(ID, InsertPos); 125 126 TrivialPair T(99, 42); 127 Trivial.InsertNode(&T, InsertPos); 128 EXPECT_EQ(1U, Trivial.size()); 129} 130 131TEST(FoldingSetTest, EmptyIsTrue) { 132 FoldingSet<TrivialPair> Trivial; 133 EXPECT_TRUE(Trivial.empty()); 134} 135 136TEST(FoldingSetTest, EmptyIsFalse) { 137 FoldingSet<TrivialPair> Trivial; 138 TrivialPair T(99, 42); 139 Trivial.InsertNode(&T); 140 EXPECT_FALSE(Trivial.empty()); 141} 142 143TEST(FoldingSetTest, ClearOnEmpty) { 144 FoldingSet<TrivialPair> Trivial; 145 Trivial.clear(); 146 EXPECT_TRUE(Trivial.empty()); 147} 148 149TEST(FoldingSetTest, ClearOnNonEmpty) { 150 FoldingSet<TrivialPair> Trivial; 151 TrivialPair T(99, 42); 152 Trivial.InsertNode(&T); 153 Trivial.clear(); 154 EXPECT_TRUE(Trivial.empty()); 155} 156 157TEST(FoldingSetTest, CapacityLargerThanReserve) { 158 FoldingSet<TrivialPair> Trivial; 159 auto OldCapacity = Trivial.capacity(); 160 Trivial.reserve(OldCapacity + 1); 161 EXPECT_GE(Trivial.capacity(), OldCapacity + 1); 162} 163 164TEST(FoldingSetTest, SmallReserveChangesNothing) { 165 FoldingSet<TrivialPair> Trivial; 166 auto OldCapacity = Trivial.capacity(); 167 Trivial.reserve(OldCapacity - 1); 168 EXPECT_EQ(Trivial.capacity(), OldCapacity); 169} 170 171} 172 173