1 //===- llvm/unittest/ADT/SmallPtrSetTest.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 // SmallPtrSet unit tests.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #include "gtest/gtest.h"
15 #include "llvm/ADT/SmallPtrSet.h"
16
17 using namespace llvm;
18
TEST(SmallPtrSetTest,Assignment)19 TEST(SmallPtrSetTest, Assignment) {
20 int buf[8];
21 for (int i = 0; i < 8; ++i)
22 buf[i] = 0;
23
24 SmallPtrSet<int *, 4> s1;
25 s1.insert(&buf[0]);
26 s1.insert(&buf[1]);
27
28 SmallPtrSet<int *, 4> s2;
29 (s2 = s1).insert(&buf[2]);
30
31 // Self assign as well.
32 (s2 = s2).insert(&buf[3]);
33
34 s1 = s2;
35 EXPECT_EQ(4U, s1.size());
36 for (int i = 0; i < 8; ++i)
37 if (i < 4)
38 EXPECT_TRUE(s1.count(&buf[i]));
39 else
40 EXPECT_FALSE(s1.count(&buf[i]));
41 }
42
TEST(SmallPtrSetTest,GrowthTest)43 TEST(SmallPtrSetTest, GrowthTest) {
44 int i;
45 int buf[8];
46 for(i=0; i<8; ++i) buf[i]=0;
47
48
49 SmallPtrSet<int *, 4> s;
50 typedef SmallPtrSet<int *, 4>::iterator iter;
51
52 s.insert(&buf[0]);
53 s.insert(&buf[1]);
54 s.insert(&buf[2]);
55 s.insert(&buf[3]);
56 EXPECT_EQ(4U, s.size());
57
58 i = 0;
59 for(iter I=s.begin(), E=s.end(); I!=E; ++I, ++i)
60 (**I)++;
61 EXPECT_EQ(4, i);
62 for(i=0; i<8; ++i)
63 EXPECT_EQ(i<4?1:0,buf[i]);
64
65 s.insert(&buf[4]);
66 s.insert(&buf[5]);
67 s.insert(&buf[6]);
68 s.insert(&buf[7]);
69
70 i = 0;
71 for(iter I=s.begin(), E=s.end(); I!=E; ++I, ++i)
72 (**I)++;
73 EXPECT_EQ(8, i);
74 s.erase(&buf[4]);
75 s.erase(&buf[5]);
76 s.erase(&buf[6]);
77 s.erase(&buf[7]);
78 EXPECT_EQ(4U, s.size());
79
80 i = 0;
81 for(iter I=s.begin(), E=s.end(); I!=E; ++I, ++i)
82 (**I)++;
83 EXPECT_EQ(4, i);
84 for(i=0; i<8; ++i)
85 EXPECT_EQ(i<4?3:1,buf[i]);
86
87 s.clear();
88 for(i=0; i<8; ++i) buf[i]=0;
89 for(i=0; i<128; ++i) s.insert(&buf[i%8]); // test repeated entires
90 EXPECT_EQ(8U, s.size());
91 for(iter I=s.begin(), E=s.end(); I!=E; ++I, ++i)
92 (**I)++;
93 for(i=0; i<8; ++i)
94 EXPECT_EQ(1,buf[i]);
95 }
96
TEST(SmallPtrSetTest,CopyAndMoveTest)97 TEST(SmallPtrSetTest, CopyAndMoveTest) {
98 int buf[8];
99 for (int i = 0; i < 8; ++i)
100 buf[i] = 0;
101
102 SmallPtrSet<int *, 4> s1;
103 s1.insert(&buf[0]);
104 s1.insert(&buf[1]);
105 s1.insert(&buf[2]);
106 s1.insert(&buf[3]);
107 EXPECT_EQ(4U, s1.size());
108 for (int i = 0; i < 8; ++i)
109 if (i < 4)
110 EXPECT_TRUE(s1.count(&buf[i]));
111 else
112 EXPECT_FALSE(s1.count(&buf[i]));
113
114 SmallPtrSet<int *, 4> s2(s1);
115 EXPECT_EQ(4U, s2.size());
116 for (int i = 0; i < 8; ++i)
117 if (i < 4)
118 EXPECT_TRUE(s2.count(&buf[i]));
119 else
120 EXPECT_FALSE(s2.count(&buf[i]));
121
122 s1 = s2;
123 EXPECT_EQ(4U, s1.size());
124 EXPECT_EQ(4U, s2.size());
125 for (int i = 0; i < 8; ++i)
126 if (i < 4)
127 EXPECT_TRUE(s1.count(&buf[i]));
128 else
129 EXPECT_FALSE(s1.count(&buf[i]));
130
131 SmallPtrSet<int *, 4> s3(std::move(s1));
132 EXPECT_EQ(4U, s3.size());
133 EXPECT_TRUE(s1.empty());
134 for (int i = 0; i < 8; ++i)
135 if (i < 4)
136 EXPECT_TRUE(s3.count(&buf[i]));
137 else
138 EXPECT_FALSE(s3.count(&buf[i]));
139
140 // Move assign into the moved-from object. Also test move of a non-small
141 // container.
142 s3.insert(&buf[4]);
143 s3.insert(&buf[5]);
144 s3.insert(&buf[6]);
145 s3.insert(&buf[7]);
146 s1 = std::move(s3);
147 EXPECT_EQ(8U, s1.size());
148 EXPECT_TRUE(s3.empty());
149 for (int i = 0; i < 8; ++i)
150 EXPECT_TRUE(s1.count(&buf[i]));
151
152 // Copy assign into a moved-from object.
153 s3 = s1;
154 EXPECT_EQ(8U, s3.size());
155 EXPECT_EQ(8U, s1.size());
156 for (int i = 0; i < 8; ++i)
157 EXPECT_TRUE(s3.count(&buf[i]));
158 }
159
TEST(SmallPtrSetTest,SwapTest)160 TEST(SmallPtrSetTest, SwapTest) {
161 int buf[10];
162
163 SmallPtrSet<int *, 2> a;
164 SmallPtrSet<int *, 2> b;
165
166 a.insert(&buf[0]);
167 a.insert(&buf[1]);
168 b.insert(&buf[2]);
169
170 EXPECT_EQ(2U, a.size());
171 EXPECT_EQ(1U, b.size());
172 EXPECT_TRUE(a.count(&buf[0]));
173 EXPECT_TRUE(a.count(&buf[1]));
174 EXPECT_FALSE(a.count(&buf[2]));
175 EXPECT_FALSE(a.count(&buf[3]));
176 EXPECT_FALSE(b.count(&buf[0]));
177 EXPECT_FALSE(b.count(&buf[1]));
178 EXPECT_TRUE(b.count(&buf[2]));
179 EXPECT_FALSE(b.count(&buf[3]));
180
181 std::swap(a, b);
182
183 EXPECT_EQ(1U, a.size());
184 EXPECT_EQ(2U, b.size());
185 EXPECT_FALSE(a.count(&buf[0]));
186 EXPECT_FALSE(a.count(&buf[1]));
187 EXPECT_TRUE(a.count(&buf[2]));
188 EXPECT_FALSE(a.count(&buf[3]));
189 EXPECT_TRUE(b.count(&buf[0]));
190 EXPECT_TRUE(b.count(&buf[1]));
191 EXPECT_FALSE(b.count(&buf[2]));
192 EXPECT_FALSE(b.count(&buf[3]));
193
194 b.insert(&buf[3]);
195 std::swap(a, b);
196
197 EXPECT_EQ(3U, a.size());
198 EXPECT_EQ(1U, b.size());
199 EXPECT_TRUE(a.count(&buf[0]));
200 EXPECT_TRUE(a.count(&buf[1]));
201 EXPECT_FALSE(a.count(&buf[2]));
202 EXPECT_TRUE(a.count(&buf[3]));
203 EXPECT_FALSE(b.count(&buf[0]));
204 EXPECT_FALSE(b.count(&buf[1]));
205 EXPECT_TRUE(b.count(&buf[2]));
206 EXPECT_FALSE(b.count(&buf[3]));
207
208 std::swap(a, b);
209
210 EXPECT_EQ(1U, a.size());
211 EXPECT_EQ(3U, b.size());
212 EXPECT_FALSE(a.count(&buf[0]));
213 EXPECT_FALSE(a.count(&buf[1]));
214 EXPECT_TRUE(a.count(&buf[2]));
215 EXPECT_FALSE(a.count(&buf[3]));
216 EXPECT_TRUE(b.count(&buf[0]));
217 EXPECT_TRUE(b.count(&buf[1]));
218 EXPECT_FALSE(b.count(&buf[2]));
219 EXPECT_TRUE(b.count(&buf[3]));
220
221 a.insert(&buf[4]);
222 a.insert(&buf[5]);
223 a.insert(&buf[6]);
224
225 std::swap(b, a);
226
227 EXPECT_EQ(3U, a.size());
228 EXPECT_EQ(4U, b.size());
229 EXPECT_TRUE(b.count(&buf[2]));
230 EXPECT_TRUE(b.count(&buf[4]));
231 EXPECT_TRUE(b.count(&buf[5]));
232 EXPECT_TRUE(b.count(&buf[6]));
233 EXPECT_TRUE(a.count(&buf[0]));
234 EXPECT_TRUE(a.count(&buf[1]));
235 EXPECT_TRUE(a.count(&buf[3]));
236 }
237
checkEraseAndIterators(SmallPtrSetImpl<int * > & S)238 void checkEraseAndIterators(SmallPtrSetImpl<int*> &S) {
239 int buf[3];
240
241 S.insert(&buf[0]);
242 S.insert(&buf[1]);
243 S.insert(&buf[2]);
244
245 // Iterators must still be valid after erase() calls;
246 auto B = S.begin();
247 auto M = std::next(B);
248 auto E = S.end();
249 EXPECT_TRUE(*B == &buf[0] || *B == &buf[1] || *B == &buf[2]);
250 EXPECT_TRUE(*M == &buf[0] || *M == &buf[1] || *M == &buf[2]);
251 EXPECT_TRUE(*B != *M);
252 int *Removable = *std::next(M);
253 // No iterator points to Removable now.
254 EXPECT_TRUE(Removable == &buf[0] || Removable == &buf[1] ||
255 Removable == &buf[2]);
256 EXPECT_TRUE(Removable != *B && Removable != *M);
257
258 S.erase(Removable);
259
260 // B,M,E iterators should still be valid
261 EXPECT_EQ(B, S.begin());
262 EXPECT_EQ(M, std::next(B));
263 EXPECT_EQ(E, S.end());
264 EXPECT_EQ(std::next(M), E);
265 }
266
TEST(SmallPtrSetTest,EraseTest)267 TEST(SmallPtrSetTest, EraseTest) {
268 // Test when set stays small.
269 SmallPtrSet<int *, 8> B;
270 checkEraseAndIterators(B);
271
272 // Test when set grows big.
273 SmallPtrSet<int *, 2> A;
274 checkEraseAndIterators(A);
275 }
276