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