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
17using namespace llvm;
18
19namespace {
20
21// Unaligned string test.
22TEST(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(String: str1);
29
30 // An unaligned string.
31 std::string str2 = ">" + str1;
32 b.AddString(String: str2.c_str() + 1);
33
34 EXPECT_EQ(a.ComputeHash(), b.ComputeHash());
35}
36
37TEST(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(I: A);
44 ID.AddInteger(I: 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
58struct TrivialPair : public FoldingSetNode {
59 unsigned Key = 0;
60 unsigned Value = 0;
61 TrivialPair(unsigned K, unsigned V) : FoldingSetNode(), Key(K), Value(V) {}
62
63 void Profile(FoldingSetNodeID &ID) const {
64 ID.AddInteger(I: Key);
65 ID.AddInteger(I: Value);
66 }
67};
68
69TEST(FoldingSetTest, IDComparison) {
70 FoldingSet<TrivialPair> Trivial;
71
72 TrivialPair T(99, 42);
73 Trivial.InsertNode(N: &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
83TEST(FoldingSetTest, MissedIDComparison) {
84 FoldingSet<TrivialPair> Trivial;
85
86 TrivialPair S(100, 42);
87 TrivialPair T(99, 42);
88 Trivial.InsertNode(N: &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
98TEST(FoldingSetTest, RemoveNodeThatIsPresent) {
99 FoldingSet<TrivialPair> Trivial;
100
101 TrivialPair T(99, 42);
102 Trivial.InsertNode(N: &T);
103 EXPECT_EQ(Trivial.size(), 1U);
104
105 bool WasThere = Trivial.RemoveNode(N: &T);
106 EXPECT_TRUE(WasThere);
107 EXPECT_EQ(0U, Trivial.size());
108}
109
110TEST(FoldingSetTest, RemoveNodeThatIsAbsent) {
111 FoldingSet<TrivialPair> Trivial;
112
113 TrivialPair T(99, 42);
114 bool WasThere = Trivial.RemoveNode(N: &T);
115 EXPECT_FALSE(WasThere);
116 EXPECT_EQ(0U, Trivial.size());
117}
118
119TEST(FoldingSetTest, GetOrInsertInserting) {
120 FoldingSet<TrivialPair> Trivial;
121
122 TrivialPair T(99, 42);
123 TrivialPair *N = Trivial.GetOrInsertNode(N: &T);
124 EXPECT_EQ(&T, N);
125}
126
127TEST(FoldingSetTest, GetOrInsertGetting) {
128 FoldingSet<TrivialPair> Trivial;
129
130 TrivialPair T(99, 42);
131 TrivialPair T2(99, 42);
132 Trivial.InsertNode(N: &T);
133 TrivialPair *N = Trivial.GetOrInsertNode(N: &T2);
134 EXPECT_EQ(&T, N);
135}
136
137TEST(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(N: &T, InsertPos);
148 EXPECT_EQ(1U, Trivial.size());
149}
150
151TEST(FoldingSetTest, EmptyIsTrue) {
152 FoldingSet<TrivialPair> Trivial;
153 EXPECT_TRUE(Trivial.empty());
154}
155
156TEST(FoldingSetTest, EmptyIsFalse) {
157 FoldingSet<TrivialPair> Trivial;
158 TrivialPair T(99, 42);
159 Trivial.InsertNode(N: &T);
160 EXPECT_FALSE(Trivial.empty());
161}
162
163TEST(FoldingSetTest, ClearOnEmpty) {
164 FoldingSet<TrivialPair> Trivial;
165 Trivial.clear();
166 EXPECT_TRUE(Trivial.empty());
167}
168
169TEST(FoldingSetTest, ClearOnNonEmpty) {
170 FoldingSet<TrivialPair> Trivial;
171 TrivialPair T(99, 42);
172 Trivial.InsertNode(N: &T);
173 Trivial.clear();
174 EXPECT_TRUE(Trivial.empty());
175}
176
177TEST(FoldingSetTest, CapacityLargerThanReserve) {
178 FoldingSet<TrivialPair> Trivial;
179 auto OldCapacity = Trivial.capacity();
180 Trivial.reserve(EltCount: OldCapacity + 1);
181 EXPECT_GE(Trivial.capacity(), OldCapacity + 1);
182}
183
184TEST(FoldingSetTest, SmallReserveChangesNothing) {
185 FoldingSet<TrivialPair> Trivial;
186 auto OldCapacity = Trivial.capacity();
187 Trivial.reserve(EltCount: OldCapacity - 1);
188 EXPECT_EQ(Trivial.capacity(), OldCapacity);
189}
190
191}
192
193

source code of llvm/unittests/ADT/FoldingSet.cpp