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
18 using namespace llvm;
19
20 namespace {
21
22 // Unaligned string test.
TEST(FoldingSetTest,UnalignedStringTest)23 TEST(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
38 struct TrivialPair : public FoldingSetNode {
39 unsigned Key = 0;
40 unsigned Value = 0;
TrivialPair__anon30d59e4e0111::TrivialPair41 TrivialPair(unsigned K, unsigned V) : FoldingSetNode(), Key(K), Value(V) {}
42
Profile__anon30d59e4e0111::TrivialPair43 void Profile(FoldingSetNodeID &ID) const {
44 ID.AddInteger(Key);
45 ID.AddInteger(Value);
46 }
47 };
48
TEST(FoldingSetTest,IDComparison)49 TEST(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
TEST(FoldingSetTest,MissedIDComparison)63 TEST(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
TEST(FoldingSetTest,RemoveNodeThatIsPresent)78 TEST(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
TEST(FoldingSetTest,RemoveNodeThatIsAbsent)90 TEST(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
TEST(FoldingSetTest,GetOrInsertInserting)99 TEST(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
TEST(FoldingSetTest,GetOrInsertGetting)107 TEST(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
TEST(FoldingSetTest,InsertAtPos)117 TEST(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
TEST(FoldingSetTest,EmptyIsTrue)131 TEST(FoldingSetTest, EmptyIsTrue) {
132 FoldingSet<TrivialPair> Trivial;
133 EXPECT_TRUE(Trivial.empty());
134 }
135
TEST(FoldingSetTest,EmptyIsFalse)136 TEST(FoldingSetTest, EmptyIsFalse) {
137 FoldingSet<TrivialPair> Trivial;
138 TrivialPair T(99, 42);
139 Trivial.InsertNode(&T);
140 EXPECT_FALSE(Trivial.empty());
141 }
142
TEST(FoldingSetTest,ClearOnEmpty)143 TEST(FoldingSetTest, ClearOnEmpty) {
144 FoldingSet<TrivialPair> Trivial;
145 Trivial.clear();
146 EXPECT_TRUE(Trivial.empty());
147 }
148
TEST(FoldingSetTest,ClearOnNonEmpty)149 TEST(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
TEST(FoldingSetTest,CapacityLargerThanReserve)157 TEST(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
TEST(FoldingSetTest,SmallReserveChangesNothing)164 TEST(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