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 { |
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 | |
33 | TEST(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 | |
44 | TEST(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 | |
62 | TEST(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 | |
80 | TEST(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 | |
94 | TEST(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 | |
111 | TEST(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 |
138 | TEST(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 | |
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 | |
164 | TestHelper2() { constructed++; } |
165 | ~TestHelper2() { destroyed++; } |
166 | }; |
167 | |
168 | int TestHelper2::constructed = 0; |
169 | int TestHelper2::destroyed = 0; |
170 | |
171 | TEST(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. |
187 | TEST(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 | |
231 | TEST(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 | |
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(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 | |