1 //===- llvm/unittest/ADT/PagedVectorTest.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 // PagedVector unit tests.
10 //
11 //===----------------------------------------------------------------------===//
12
13 #include "llvm/ADT/PagedVector.h"
14 #include "gtest/gtest.h"
15 #include <iterator>
16
17 namespace llvm {
TEST(PagedVectorTest,EmptyTest)18 TEST(PagedVectorTest, EmptyTest) {
19 PagedVector<int, 10> V;
20 EXPECT_EQ(V.empty(), true);
21 EXPECT_EQ(V.size(), 0ULL);
22 EXPECT_EQ(V.capacity(), 0ULL);
23 EXPECT_EQ(V.materialized_begin().getIndex(), 0ULL);
24 EXPECT_EQ(V.materialized_end().getIndex(), 0ULL);
25 EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 0LL);
26
27 #if GTEST_HAS_DEATH_TEST && !defined(NDEBUG)
28 EXPECT_DEATH(V[0], "Index < Size");
29 EXPECT_DEATH(PagedVector<int>(nullptr), "Allocator cannot be null");
30 #endif
31 }
32
TEST(PagedVectorTest,ExpandTest)33 TEST(PagedVectorTest, ExpandTest) {
34 PagedVector<int, 10> V;
35 V.resize(2);
36 EXPECT_EQ(V.empty(), false);
37 EXPECT_EQ(V.size(), 2ULL);
38 EXPECT_EQ(V.capacity(), 10ULL);
39 EXPECT_EQ(V.materialized_begin().getIndex(), 2ULL);
40 EXPECT_EQ(V.materialized_end().getIndex(), 2ULL);
41 EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 0LL);
42 }
43
TEST(PagedVectorTest,FullPageFillingTest)44 TEST(PagedVectorTest, FullPageFillingTest) {
45 PagedVector<int, 10> V;
46 V.resize(10);
47 EXPECT_EQ(V.empty(), false);
48 EXPECT_EQ(V.size(), 10ULL);
49 EXPECT_EQ(V.capacity(), 10ULL);
50 for (int I = 0; I < 10; ++I)
51 V[I] = I;
52 EXPECT_EQ(V.empty(), false);
53 EXPECT_EQ(V.size(), 10ULL);
54 EXPECT_EQ(V.capacity(), 10ULL);
55 EXPECT_EQ(V.materialized_begin().getIndex(), 0ULL);
56 EXPECT_EQ(V.materialized_end().getIndex(), 10ULL);
57 EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 10LL);
58 for (int I = 0; I < 10; ++I)
59 EXPECT_EQ(V[I], I);
60 }
61
TEST(PagedVectorTest,HalfPageFillingTest)62 TEST(PagedVectorTest, HalfPageFillingTest) {
63 PagedVector<int, 10> V;
64 V.resize(5);
65 EXPECT_EQ(V.empty(), false);
66 EXPECT_EQ(V.size(), 5ULL);
67 EXPECT_EQ(V.capacity(), 10ULL);
68 for (int I = 0; I < 5; ++I)
69 V[I] = I;
70 EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 5LL);
71 for (int I = 0; I < 5; ++I)
72 EXPECT_EQ(V[I], I);
73
74 #if GTEST_HAS_DEATH_TEST && !defined(NDEBUG)
75 for (int I = 5; I < 10; ++I)
76 EXPECT_DEATH(V[I], "Index < Size");
77 #endif
78 }
79
TEST(PagedVectorTest,FillFullMultiPageTest)80 TEST(PagedVectorTest, FillFullMultiPageTest) {
81 PagedVector<int, 10> V;
82 V.resize(20);
83 EXPECT_EQ(V.empty(), false);
84 EXPECT_EQ(V.size(), 20ULL);
85 EXPECT_EQ(V.capacity(), 20ULL);
86 for (int I = 0; I < 20; ++I)
87 V[I] = I;
88 EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 20LL);
89 for (auto MI = V.materialized_begin(), ME = V.materialized_end(); MI != ME;
90 ++MI)
91 EXPECT_EQ(*MI, std::distance(V.materialized_begin(), MI));
92 }
93
TEST(PagedVectorTest,FillHalfMultiPageTest)94 TEST(PagedVectorTest, FillHalfMultiPageTest) {
95 PagedVector<int, 10> V;
96 V.resize(20);
97 EXPECT_EQ(V.empty(), false);
98 EXPECT_EQ(V.size(), 20ULL);
99 EXPECT_EQ(V.capacity(), 20ULL);
100 for (int I = 0; I < 5; ++I)
101 V[I] = I;
102 for (int I = 10; I < 15; ++I)
103 V[I] = I;
104 EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 20LL);
105 for (int I = 0; I < 5; ++I)
106 EXPECT_EQ(V[I], I);
107 for (int I = 10; I < 15; ++I)
108 EXPECT_EQ(V[I], I);
109 }
110
TEST(PagedVectorTest,FillLastMultiPageTest)111 TEST(PagedVectorTest, FillLastMultiPageTest) {
112 PagedVector<int, 10> V;
113 V.resize(20);
114 EXPECT_EQ(V.empty(), false);
115 EXPECT_EQ(V.size(), 20ULL);
116 EXPECT_EQ(V.capacity(), 20ULL);
117 for (int I = 10; I < 15; ++I)
118 V[I] = I;
119 for (int I = 10; I < 15; ++I)
120 EXPECT_EQ(V[I], I);
121
122 // Since we fill the last page only, the materialized vector
123 // should contain only the last page.
124 int J = 10;
125 for (auto MI = V.materialized_begin(), ME = V.materialized_end(); MI != ME;
126 ++MI) {
127 if (J < 15)
128 EXPECT_EQ(*MI, J);
129 else
130 EXPECT_EQ(*MI, 0);
131 ++J;
132 }
133 EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 10LL);
134 }
135
136 // Filling the first element of all the pages
137 // will allocate all of them
TEST(PagedVectorTest,FillSparseMultiPageTest)138 TEST(PagedVectorTest, FillSparseMultiPageTest) {
139 PagedVector<int, 10> V;
140 V.resize(100);
141 EXPECT_EQ(V.empty(), false);
142 EXPECT_EQ(V.size(), 100ULL);
143 EXPECT_EQ(V.capacity(), 100ULL);
144 for (int I = 0; I < 10; ++I)
145 V[I * 10] = I;
146 EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 100LL);
147 for (int I = 0; I < 100; ++I)
148 if (I % 10 == 0)
149 EXPECT_EQ(V[I], I / 10);
150 else
151 EXPECT_EQ(V[I], 0);
152 }
153
154 struct TestHelper {
155 int A = -1;
156 };
157
158 // Use this to count how many times the constructor / destructor are called
159 struct TestHelper2 {
160 int A = -1;
161 static int constructed;
162 static int destroyed;
163
TestHelper2llvm::TestHelper2164 TestHelper2() { constructed++; }
~TestHelper2llvm::TestHelper2165 ~TestHelper2() { destroyed++; }
166 };
167
168 int TestHelper2::constructed = 0;
169 int TestHelper2::destroyed = 0;
170
TEST(PagedVectorTest,FillNonTrivialConstructor)171 TEST(PagedVectorTest, FillNonTrivialConstructor) {
172 PagedVector<TestHelper, 10> V;
173 V.resize(10);
174 EXPECT_EQ(V.empty(), false);
175 EXPECT_EQ(V.size(), 10ULL);
176 EXPECT_EQ(V.capacity(), 10ULL);
177 EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 0LL);
178 for (int I = 0; I < 10; ++I)
179 EXPECT_EQ(V[I].A, -1);
180 EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 10LL);
181 }
182
183 // Elements are constructed, destructed in pages, so we expect
184 // the number of constructed / destructed elements to be a multiple of the
185 // page size and the constructor is invoked when the page is actually accessed
186 // the first time.
TEST(PagedVectorTest,FillNonTrivialConstructorDestructor)187 TEST(PagedVectorTest, FillNonTrivialConstructorDestructor) {
188 PagedVector<TestHelper2, 10> V;
189 V.resize(19);
190 EXPECT_EQ(TestHelper2::constructed, 0);
191 EXPECT_EQ(V.empty(), false);
192 EXPECT_EQ(V.size(), 19ULL);
193 EXPECT_EQ(V.capacity(), 20ULL);
194 EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 0LL);
195 EXPECT_EQ(V[0].A, -1);
196 EXPECT_EQ(TestHelper2::constructed, 10);
197
198 for (int I = 0; I < 10; ++I) {
199 EXPECT_EQ(V[I].A, -1);
200 EXPECT_EQ(TestHelper2::constructed, 10);
201 }
202 for (int I = 10; I < 11; ++I) {
203 EXPECT_EQ(V[I].A, -1);
204 EXPECT_EQ(TestHelper2::constructed, 20);
205 }
206 for (int I = 0; I < 19; ++I) {
207 EXPECT_EQ(V[I].A, -1);
208 EXPECT_EQ(TestHelper2::constructed, 20);
209 }
210 EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 19LL);
211 // We initialize the whole page, not just the materialized part
212 // EXPECT_EQ(TestHelper2::constructed, 20);
213 V.resize(18);
214 EXPECT_EQ(TestHelper2::destroyed, 0);
215 V.resize(1);
216 EXPECT_EQ(TestHelper2::destroyed, 10);
217 V.resize(0);
218 EXPECT_EQ(TestHelper2::destroyed, 20);
219
220 // Add a few empty pages so that we can test that the destructor
221 // is called only for the materialized pages
222 V.resize(50);
223 V[49].A = 0;
224 EXPECT_EQ(TestHelper2::constructed, 30);
225 EXPECT_EQ(TestHelper2::destroyed, 20);
226 EXPECT_EQ(V[49].A, 0);
227 V.resize(0);
228 EXPECT_EQ(TestHelper2::destroyed, 30);
229 }
230
TEST(PagedVectorTest,ShrinkTest)231 TEST(PagedVectorTest, ShrinkTest) {
232 PagedVector<int, 10> V;
233 V.resize(20);
234 EXPECT_EQ(V.empty(), false);
235 EXPECT_EQ(V.size(), 20ULL);
236 EXPECT_EQ(V.capacity(), 20ULL);
237 for (int I = 0; I < 20; ++I)
238 V[I] = I;
239 EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 20LL);
240 V.resize(9);
241 EXPECT_EQ(V.empty(), false);
242 EXPECT_EQ(V.size(), 9ULL);
243 EXPECT_EQ(V.capacity(), 10ULL);
244 for (int I = 0; I < 9; ++I)
245 EXPECT_EQ(V[I], I);
246 EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 9LL);
247 V.resize(0);
248 EXPECT_EQ(V.empty(), true);
249 EXPECT_EQ(V.size(), 0ULL);
250 EXPECT_EQ(V.capacity(), 0ULL);
251 EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 0LL);
252
253 #if GTEST_HAS_DEATH_TEST && !defined(NDEBUG)
254 EXPECT_DEATH(V[0], "Index < Size");
255 #endif
256 }
257
TEST(PagedVectorTest,FunctionalityTest)258 TEST(PagedVectorTest, FunctionalityTest) {
259 PagedVector<int, 10> V;
260 EXPECT_EQ(V.empty(), true);
261
262 // Next ten numbers are 10..19
263 V.resize(2);
264 EXPECT_EQ(V.empty(), false);
265 V.resize(10);
266 V.resize(20);
267 V.resize(30);
268 EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 0LL);
269
270 EXPECT_EQ(V.size(), 30ULL);
271 for (int I = 0; I < 10; ++I)
272 V[I] = I;
273 for (int I = 0; I < 10; ++I)
274 EXPECT_EQ(V[I], I);
275 EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 10LL);
276 for (int I = 20; I < 30; ++I)
277 V[I] = I;
278 for (int I = 20; I < 30; ++I)
279 EXPECT_EQ(V[I], I);
280 EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 20LL);
281
282 for (int I = 10; I < 20; ++I)
283 V[I] = I;
284 for (int I = 10; I < 20; ++I)
285 EXPECT_EQ(V[I], I);
286 EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 30LL);
287 V.resize(35);
288 EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 30LL);
289 for (int I = 30; I < 35; ++I)
290 V[I] = I;
291 EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 35LL);
292 EXPECT_EQ(V.size(), 35ULL);
293 EXPECT_EQ(V.capacity(), 40ULL);
294 V.resize(37);
295 for (int I = 30; I < 37; ++I)
296 V[I] = I;
297 EXPECT_EQ(V.size(), 37ULL);
298 EXPECT_EQ(V.capacity(), 40ULL);
299 for (int I = 0; I < 37; ++I)
300 EXPECT_EQ(V[I], I);
301
302 V.resize(41);
303 V[40] = 40;
304 EXPECT_EQ(V.size(), 41ULL);
305 EXPECT_EQ(V.capacity(), 50ULL);
306 for (int I = 0; I < 36; ++I)
307 EXPECT_EQ(V[I], I);
308
309 for (int I = 37; I < 40; ++I)
310 EXPECT_EQ(V[I], 0);
311
312 V.resize(50);
313 EXPECT_EQ(V.capacity(), 50ULL);
314 EXPECT_EQ(V.size(), 50ULL);
315 EXPECT_EQ(V[40], 40);
316 V.resize(50ULL);
317 V.clear();
318 EXPECT_EQ(V.size(), 0ULL);
319 EXPECT_EQ(V.capacity(), 0ULL);
320 }
321 } // namespace llvm
322