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. |
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(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 | |
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(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 | |
58 | struct 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 | |
69 | TEST(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 | |
83 | TEST(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 | |
98 | TEST(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 | |
110 | TEST(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 | |
119 | TEST(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 | |
127 | TEST(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 | |
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(N: &T, InsertPos); |
148 | EXPECT_EQ(1U, Trivial.size()); |
149 | } |
150 | |
151 | TEST(FoldingSetTest, EmptyIsTrue) { |
152 | FoldingSet<TrivialPair> Trivial; |
153 | EXPECT_TRUE(Trivial.empty()); |
154 | } |
155 | |
156 | TEST(FoldingSetTest, EmptyIsFalse) { |
157 | FoldingSet<TrivialPair> Trivial; |
158 | TrivialPair T(99, 42); |
159 | Trivial.InsertNode(N: &T); |
160 | EXPECT_FALSE(Trivial.empty()); |
161 | } |
162 | |
163 | TEST(FoldingSetTest, ClearOnEmpty) { |
164 | FoldingSet<TrivialPair> Trivial; |
165 | Trivial.clear(); |
166 | EXPECT_TRUE(Trivial.empty()); |
167 | } |
168 | |
169 | TEST(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 | |
177 | TEST(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 | |
184 | TEST(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 | |