1 //===- llvm/unittest/ADT/FoldingSetTest.cpp -------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // FoldingSet unit tests.
10 //
11 //===----------------------------------------------------------------------===//
12
13 #include "llvm/ADT/FoldingSet.h"
14 #include "gtest/gtest.h"
15 #include <string>
16
17 using namespace llvm;
18
19 namespace {
20
21 // Unaligned string test.
TEST(FoldingSetTest,UnalignedStringTest)22 TEST(FoldingSetTest, UnalignedStringTest) {
23 SCOPED_TRACE("UnalignedStringTest");
24
25 FoldingSetNodeID a, b;
26 // An aligned string.
27 std::string str1= "a test string";
28 a.AddString(str1);
29
30 // An unaligned string.
31 std::string str2 = ">" + str1;
32 b.AddString(str2.c_str() + 1);
33
34 EXPECT_EQ(a.ComputeHash(), b.ComputeHash());
35 }
36
TEST(FoldingSetTest,LongLongComparison)37 TEST(FoldingSetTest, LongLongComparison) {
38 struct LongLongContainer : FoldingSetNode {
39 unsigned long long A, B;
40 LongLongContainer(unsigned long long A, unsigned long long B)
41 : A(A), B(B) {}
42 void Profile(FoldingSetNodeID &ID) const {
43 ID.AddInteger(A);
44 ID.AddInteger(B);
45 }
46 };
47
48 LongLongContainer C1((1ULL << 32) + 1, 1ULL);
49 LongLongContainer C2(1ULL, (1ULL << 32) + 1);
50
51 FoldingSet<LongLongContainer> Set;
52
53 EXPECT_EQ(&C1, Set.GetOrInsertNode(&C1));
54 EXPECT_EQ(&C2, Set.GetOrInsertNode(&C2));
55 EXPECT_EQ(2U, Set.size());
56 }
57
58 struct TrivialPair : public FoldingSetNode {
59 unsigned Key = 0;
60 unsigned Value = 0;
TrivialPair__anon7b4463960111::TrivialPair61 TrivialPair(unsigned K, unsigned V) : FoldingSetNode(), Key(K), Value(V) {}
62
Profile__anon7b4463960111::TrivialPair63 void Profile(FoldingSetNodeID &ID) const {
64 ID.AddInteger(Key);
65 ID.AddInteger(Value);
66 }
67 };
68
TEST(FoldingSetTest,IDComparison)69 TEST(FoldingSetTest, IDComparison) {
70 FoldingSet<TrivialPair> Trivial;
71
72 TrivialPair T(99, 42);
73 Trivial.InsertNode(&T);
74
75 void *InsertPos = nullptr;
76 FoldingSetNodeID ID;
77 T.Profile(ID);
78 TrivialPair *N = Trivial.FindNodeOrInsertPos(ID, InsertPos);
79 EXPECT_EQ(&T, N);
80 EXPECT_EQ(nullptr, InsertPos);
81 }
82
TEST(FoldingSetTest,MissedIDComparison)83 TEST(FoldingSetTest, MissedIDComparison) {
84 FoldingSet<TrivialPair> Trivial;
85
86 TrivialPair S(100, 42);
87 TrivialPair T(99, 42);
88 Trivial.InsertNode(&T);
89
90 void *InsertPos = nullptr;
91 FoldingSetNodeID ID;
92 S.Profile(ID);
93 TrivialPair *N = Trivial.FindNodeOrInsertPos(ID, InsertPos);
94 EXPECT_EQ(nullptr, N);
95 EXPECT_NE(nullptr, InsertPos);
96 }
97
TEST(FoldingSetTest,RemoveNodeThatIsPresent)98 TEST(FoldingSetTest, RemoveNodeThatIsPresent) {
99 FoldingSet<TrivialPair> Trivial;
100
101 TrivialPair T(99, 42);
102 Trivial.InsertNode(&T);
103 EXPECT_EQ(Trivial.size(), 1U);
104
105 bool WasThere = Trivial.RemoveNode(&T);
106 EXPECT_TRUE(WasThere);
107 EXPECT_EQ(0U, Trivial.size());
108 }
109
TEST(FoldingSetTest,RemoveNodeThatIsAbsent)110 TEST(FoldingSetTest, RemoveNodeThatIsAbsent) {
111 FoldingSet<TrivialPair> Trivial;
112
113 TrivialPair T(99, 42);
114 bool WasThere = Trivial.RemoveNode(&T);
115 EXPECT_FALSE(WasThere);
116 EXPECT_EQ(0U, Trivial.size());
117 }
118
TEST(FoldingSetTest,GetOrInsertInserting)119 TEST(FoldingSetTest, GetOrInsertInserting) {
120 FoldingSet<TrivialPair> Trivial;
121
122 TrivialPair T(99, 42);
123 TrivialPair *N = Trivial.GetOrInsertNode(&T);
124 EXPECT_EQ(&T, N);
125 }
126
TEST(FoldingSetTest,GetOrInsertGetting)127 TEST(FoldingSetTest, GetOrInsertGetting) {
128 FoldingSet<TrivialPair> Trivial;
129
130 TrivialPair T(99, 42);
131 TrivialPair T2(99, 42);
132 Trivial.InsertNode(&T);
133 TrivialPair *N = Trivial.GetOrInsertNode(&T2);
134 EXPECT_EQ(&T, N);
135 }
136
TEST(FoldingSetTest,InsertAtPos)137 TEST(FoldingSetTest, InsertAtPos) {
138 FoldingSet<TrivialPair> Trivial;
139
140 void *InsertPos = nullptr;
141 TrivialPair Finder(99, 42);
142 FoldingSetNodeID ID;
143 Finder.Profile(ID);
144 Trivial.FindNodeOrInsertPos(ID, InsertPos);
145
146 TrivialPair T(99, 42);
147 Trivial.InsertNode(&T, InsertPos);
148 EXPECT_EQ(1U, Trivial.size());
149 }
150
TEST(FoldingSetTest,EmptyIsTrue)151 TEST(FoldingSetTest, EmptyIsTrue) {
152 FoldingSet<TrivialPair> Trivial;
153 EXPECT_TRUE(Trivial.empty());
154 }
155
TEST(FoldingSetTest,EmptyIsFalse)156 TEST(FoldingSetTest, EmptyIsFalse) {
157 FoldingSet<TrivialPair> Trivial;
158 TrivialPair T(99, 42);
159 Trivial.InsertNode(&T);
160 EXPECT_FALSE(Trivial.empty());
161 }
162
TEST(FoldingSetTest,ClearOnEmpty)163 TEST(FoldingSetTest, ClearOnEmpty) {
164 FoldingSet<TrivialPair> Trivial;
165 Trivial.clear();
166 EXPECT_TRUE(Trivial.empty());
167 }
168
TEST(FoldingSetTest,ClearOnNonEmpty)169 TEST(FoldingSetTest, ClearOnNonEmpty) {
170 FoldingSet<TrivialPair> Trivial;
171 TrivialPair T(99, 42);
172 Trivial.InsertNode(&T);
173 Trivial.clear();
174 EXPECT_TRUE(Trivial.empty());
175 }
176
TEST(FoldingSetTest,CapacityLargerThanReserve)177 TEST(FoldingSetTest, CapacityLargerThanReserve) {
178 FoldingSet<TrivialPair> Trivial;
179 auto OldCapacity = Trivial.capacity();
180 Trivial.reserve(OldCapacity + 1);
181 EXPECT_GE(Trivial.capacity(), OldCapacity + 1);
182 }
183
TEST(FoldingSetTest,SmallReserveChangesNothing)184 TEST(FoldingSetTest, SmallReserveChangesNothing) {
185 FoldingSet<TrivialPair> Trivial;
186 auto OldCapacity = Trivial.capacity();
187 Trivial.reserve(OldCapacity - 1);
188 EXPECT_EQ(Trivial.capacity(), OldCapacity);
189 }
190
191 }
192
193