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
17namespace llvm {
18TEST(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
33TEST(PagedVectorTest, ExpandTest) {
34 PagedVector<int, 10> V;
35 V.resize(NewSize: 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
44TEST(PagedVectorTest, FullPageFillingTest) {
45 PagedVector<int, 10> V;
46 V.resize(NewSize: 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
62TEST(PagedVectorTest, HalfPageFillingTest) {
63 PagedVector<int, 10> V;
64 V.resize(NewSize: 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
80TEST(PagedVectorTest, FillFullMultiPageTest) {
81 PagedVector<int, 10> V;
82 V.resize(NewSize: 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
94TEST(PagedVectorTest, FillHalfMultiPageTest) {
95 PagedVector<int, 10> V;
96 V.resize(NewSize: 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
111TEST(PagedVectorTest, FillLastMultiPageTest) {
112 PagedVector<int, 10> V;
113 V.resize(NewSize: 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
138TEST(PagedVectorTest, FillSparseMultiPageTest) {
139 PagedVector<int, 10> V;
140 V.resize(NewSize: 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
154struct TestHelper {
155 int A = -1;
156};
157
158// Use this to count how many times the constructor / destructor are called
159struct TestHelper2 {
160 int A = -1;
161 static int constructed;
162 static int destroyed;
163
164 TestHelper2() { constructed++; }
165 ~TestHelper2() { destroyed++; }
166};
167
168int TestHelper2::constructed = 0;
169int TestHelper2::destroyed = 0;
170
171TEST(PagedVectorTest, FillNonTrivialConstructor) {
172 PagedVector<TestHelper, 10> V;
173 V.resize(NewSize: 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.
187TEST(PagedVectorTest, FillNonTrivialConstructorDestructor) {
188 PagedVector<TestHelper2, 10> V;
189 V.resize(NewSize: 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(NewSize: 18);
214 EXPECT_EQ(TestHelper2::destroyed, 0);
215 V.resize(NewSize: 1);
216 EXPECT_EQ(TestHelper2::destroyed, 10);
217 V.resize(NewSize: 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(NewSize: 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(NewSize: 0);
228 EXPECT_EQ(TestHelper2::destroyed, 30);
229}
230
231TEST(PagedVectorTest, ShrinkTest) {
232 PagedVector<int, 10> V;
233 V.resize(NewSize: 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(NewSize: 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(NewSize: 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
258TEST(PagedVectorTest, FunctionalityTest) {
259 PagedVector<int, 10> V;
260 EXPECT_EQ(V.empty(), true);
261
262 // Next ten numbers are 10..19
263 V.resize(NewSize: 2);
264 EXPECT_EQ(V.empty(), false);
265 V.resize(NewSize: 10);
266 V.resize(NewSize: 20);
267 V.resize(NewSize: 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(NewSize: 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(NewSize: 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(NewSize: 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(NewSize: 50);
313 EXPECT_EQ(V.capacity(), 50ULL);
314 EXPECT_EQ(V.size(), 50ULL);
315 EXPECT_EQ(V[40], 40);
316 V.resize(NewSize: 50ULL);
317 V.clear();
318 EXPECT_EQ(V.size(), 0ULL);
319 EXPECT_EQ(V.capacity(), 0ULL);
320}
321} // namespace llvm
322

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