1 /**
2 * Copyright (c) 2021-2022 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16 #include "mem/pool_manager.h"
17 #include "utils/arena_containers.h"
18 #include "utils/small_vector.h"
19 #include <gtest/gtest.h>
20
21 namespace panda::test {
22
23 class SmallVectorTest : public ::testing::Test {
24 public:
SmallVectorTest()25 SmallVectorTest()
26 {
27 panda::mem::MemConfig::Initialize(0, 64_MB, 256_MB, 32_MB);
28 PoolManager::Initialize();
29 allocator_ = new ArenaAllocator(SpaceType::SPACE_TYPE_COMPILER);
30 }
31
~SmallVectorTest()32 virtual ~SmallVectorTest()
33 {
34 delete allocator_;
35 PoolManager::Finalize();
36 panda::mem::MemConfig::Finalize();
37 }
38
GetAllocator()39 ArenaAllocator *GetAllocator()
40 {
41 return allocator_;
42 }
43
44 private:
45 ArenaAllocator *allocator_ {nullptr};
46 };
47
48 template <typename Vector>
TestVectorGrow(Vector & vector)49 void TestVectorGrow(Vector &vector)
50 {
51 std::array values = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
52 ASSERT_EQ(vector.size(), 0);
53 ASSERT_EQ(vector.capacity(), 4);
54
55 vector.push_back(values[0]);
56 ASSERT_EQ(vector.size(), 1);
57 ASSERT_EQ(vector.capacity(), 4);
58 ASSERT_TRUE(vector.IsStatic());
59
60 vector.push_back(values[1]);
61 vector.push_back(values[2]);
62 vector.push_back(values[3]);
63 ASSERT_EQ(vector.size(), 4);
64 ASSERT_EQ(vector.capacity(), 4);
65 ASSERT_TRUE(vector.IsStatic());
66
67 vector.push_back(values[4]);
68 ASSERT_EQ(vector.size(), 5);
69 ASSERT_GE(vector.capacity(), 5);
70 ASSERT_FALSE(vector.IsStatic());
71
72 ASSERT_TRUE(std::equal(values.begin(), values.begin() + 5, vector.begin()));
73
74 std::copy(values.begin() + 5, values.end(), std::back_inserter(vector));
75 ASSERT_EQ(vector.size(), 10);
76 ASSERT_FALSE(vector.IsStatic());
77 for (size_t i = 0; i < values.size(); i++) {
78 ASSERT_EQ(vector[i], values[i]);
79 }
80 }
81
TEST_F(SmallVectorTest,Growing)82 TEST_F(SmallVectorTest, Growing)
83 {
84 {
85 SmallVector<int, 4> vector;
86 TestVectorGrow(vector);
87 }
88 {
89 SmallVector<int, 4, ArenaAllocator, true> vector(GetAllocator());
90 TestVectorGrow(vector);
91 }
92 }
93
94 template <typename Vector>
TestVectorFind(Vector & vector)95 void TestVectorFind(Vector &vector)
96 {
97 std::array values = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
98 ASSERT_EQ(vector.size(), 0);
99
100 std::copy(values.begin(), values.begin() + 4, std::back_inserter(vector));
101 ASSERT_TRUE(vector.IsStatic());
102 ASSERT_EQ(vector.size(), 4);
103 ASSERT_TRUE(std::equal(vector.begin(), vector.end(), values.begin()));
104
105 {
106 auto it = std::find(vector.begin(), vector.end(), 30);
107 ASSERT_NE(it, vector.end());
108 ASSERT_EQ(*it, 30);
109 ASSERT_EQ(std::distance(vector.begin(), it), 2);
110
111 it = std::find(vector.begin(), vector.end(), 50);
112 ASSERT_EQ(it, vector.end());
113 }
114
115 {
116 auto it = std::find(vector.rbegin(), vector.rend(), 30);
117 ASSERT_NE(it, vector.rend());
118 ASSERT_EQ(*it, 30);
119 ASSERT_EQ(std::distance(vector.rbegin(), it), 1);
120
121 it = std::find(vector.rbegin(), vector.rend(), 50);
122 ASSERT_EQ(it, vector.rend());
123 }
124
125 {
126 const auto const_vector = vector;
127 ASSERT_TRUE(std::equal(const_vector.begin(), const_vector.end(), values.begin()));
128 }
129 }
130
131 template <typename Vector>
TestVectorResize(Vector & vector)132 void TestVectorResize(Vector &vector)
133 {
134 std::array values = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
135 ASSERT_EQ(vector.size(), 0);
136
137 std::copy(values.begin(), values.begin() + 4, std::back_inserter(vector));
138 ASSERT_TRUE(vector.IsStatic());
139 ASSERT_EQ(vector.size(), 4);
140 ASSERT_TRUE(std::equal(vector.begin(), vector.end(), values.begin()));
141 std::copy(values.begin() + 4, values.end(), std::back_inserter(vector));
142 ASSERT_EQ(vector.size(), 10);
143 ASSERT_FALSE(vector.IsStatic());
144 ASSERT_TRUE(std::equal(vector.begin(), vector.end(), values.begin()));
145
146 {
147 auto it = std::find(vector.crbegin(), vector.crend(), 30);
148 ASSERT_NE(it, vector.crend());
149 ASSERT_EQ(*it, 30);
150 ASSERT_EQ(std::distance(vector.crbegin(), it), 7);
151
152 it = std::find(vector.crbegin(), vector.crend(), 190);
153 ASSERT_EQ(it, vector.crend());
154 }
155
156 {
157 auto it = vector.begin();
158 ASSERT_EQ(*(it + 3), vector[3]);
159 std::advance(it, 8);
160 ASSERT_EQ(*it, vector[8]);
161 it -= 3;
162 ASSERT_EQ(*it, vector[5]);
163 ASSERT_EQ(*(it - 3), vector[2]);
164 it++;
165 ASSERT_EQ(*(it - 3), vector[3]);
166 --it;
167 ASSERT_EQ(*(it - 3), vector[2]);
168 it--;
169 ASSERT_EQ(*(it - 3), vector[1]);
170 }
171 }
172
TEST_F(SmallVectorTest,Iteration)173 TEST_F(SmallVectorTest, Iteration)
174 {
175 {
176 SmallVector<int, 4> vector;
177 TestVectorFind(vector);
178 TestVectorResize(vector);
179 }
180 {
181 SmallVector<int, 4, ArenaAllocator, true> vector(GetAllocator());
182 TestVectorFind(vector);
183 TestVectorResize(vector);
184 }
185 }
186
187 struct Item {
Itempanda::test::Item188 Item()
189 {
190 constructed++;
191 }
Itempanda::test::Item192 Item(int aa, double bb) : a(aa), b(bb)
193 {
194 constructed++;
195 }
~Itempanda::test::Item196 virtual ~Item()
197 {
198 destroyed++;
199 }
200 DEFAULT_COPY_SEMANTIC(Item);
201 DEFAULT_MOVE_SEMANTIC(Item);
202
operator ==panda::test::Item203 bool operator==(const Item &rhs) const
204 {
205 return a == rhs.a && b == rhs.b;
206 }
Resetpanda::test::Item207 static void Reset()
208 {
209 constructed = 0;
210 destroyed = 0;
211 }
212 int a {101};
213 double b {202};
214 static inline size_t constructed = 0;
215 static inline size_t destroyed = 0;
216 };
217
TEST_F(SmallVectorTest,Emplace)218 TEST_F(SmallVectorTest, Emplace)
219 {
220 SmallVector<Item, 1> vector;
221 vector.emplace_back(1, 1.1);
222 ASSERT_EQ(vector.size(), 1);
223 ASSERT_EQ(vector[0], Item(1, 1.1));
224 ASSERT_TRUE(vector.IsStatic());
225 vector.emplace_back(2, 2.2);
226 ASSERT_FALSE(vector.IsStatic());
227 ASSERT_EQ(vector[1], Item(2, 2.2));
228 vector.push_back(Item(3, 3.3));
229 ASSERT_EQ(vector[2], Item(3, 3.3));
230 }
231
TEST_F(SmallVectorTest,ResizeStatic)232 TEST_F(SmallVectorTest, ResizeStatic)
233 {
234 SmallVector<Item, 4> vector;
235
236 vector.push_back(Item(1, 1.2));
237 ASSERT_EQ(vector[0], Item(1, 1.2));
238 Item::Reset();
239 vector.resize(3);
240 ASSERT_EQ(Item::constructed, 2);
241 ASSERT_EQ(vector.size(), 3);
242 ASSERT_TRUE(vector.IsStatic());
243 ASSERT_EQ(vector[0], Item(1, 1.2));
244 ASSERT_EQ(vector[1], Item());
245 ASSERT_EQ(vector[2], Item());
246
247 Item::Reset();
248 vector.resize(1);
249 ASSERT_EQ(vector.size(), 1);
250 ASSERT_EQ(Item::destroyed, 2);
251
252 Item::Reset();
253 vector.clear();
254 ASSERT_EQ(Item::destroyed, 1);
255 ASSERT_EQ(vector.size(), 0);
256 }
257
TEST_F(SmallVectorTest,ResizeDynamic)258 TEST_F(SmallVectorTest, ResizeDynamic)
259 {
260 std::array values = {Item(1, 1.2), Item(2, 2.3), Item(3, 3.4)};
261 SmallVector<Item, 2> vector;
262
263 Item::Reset();
264 vector.resize(6);
265 ASSERT_EQ(Item::constructed, 6);
266 ASSERT_FALSE(vector.IsStatic());
267 ASSERT_EQ(vector.size(), 6);
268 ASSERT_TRUE(std::all_of(vector.begin(), vector.end(), [](const auto &v) { return v == Item(); }));
269
270 Item::Reset();
271 vector.resize(3);
272 ASSERT_EQ(vector.size(), 3);
273 ASSERT_EQ(Item::destroyed, 3);
274 ASSERT_FALSE(vector.IsStatic());
275
276 Item::Reset();
277 vector.clear();
278 ASSERT_EQ(Item::destroyed, 3);
279 ASSERT_EQ(vector.size(), 0);
280 ASSERT_FALSE(vector.IsStatic());
281 }
282
TEST_F(SmallVectorTest,ResizeStaticWithValue)283 TEST_F(SmallVectorTest, ResizeStaticWithValue)
284 {
285 SmallVector<Item, 4> vector;
286
287 vector.push_back(Item(1, 1.2));
288 ASSERT_EQ(vector[0], Item(1, 1.2));
289 Item::Reset();
290 vector.resize(3, Item(3, 3.3));
291 ASSERT_EQ(vector.size(), 3);
292 ASSERT_TRUE(vector.IsStatic());
293 ASSERT_EQ(vector[0], Item(1, 1.2));
294 ASSERT_EQ(vector[1], Item(3, 3.3));
295 ASSERT_EQ(vector[2], Item(3, 3.3));
296
297 Item item(3, 3.3);
298 Item::Reset();
299 vector.resize(1, item);
300 ASSERT_EQ(vector.size(), 1);
301 ASSERT_EQ(Item::destroyed, 2);
302
303 Item::Reset();
304 vector.clear();
305 ASSERT_EQ(Item::destroyed, 1);
306 ASSERT_EQ(vector.size(), 0);
307 }
308
TEST_F(SmallVectorTest,ResizeDynamicWithValue)309 TEST_F(SmallVectorTest, ResizeDynamicWithValue)
310 {
311 std::array values = {Item(1, 1.2), Item(2, 2.3), Item(3, 3.4)};
312 SmallVector<Item, 2> vector;
313
314 Item::Reset();
315 vector.resize(6, Item(3, 3.3));
316 ASSERT_FALSE(vector.IsStatic());
317 ASSERT_EQ(vector.size(), 6);
318 ASSERT_TRUE(std::all_of(vector.begin(), vector.end(), [](const auto &v) { return v == Item(3, 3.3); }));
319
320 Item item(3, 3.3);
321 Item::Reset();
322 vector.resize(3, item);
323 ASSERT_EQ(vector.size(), 3);
324 ASSERT_EQ(Item::destroyed, 3);
325 ASSERT_FALSE(vector.IsStatic());
326
327 Item::Reset();
328 vector.clear();
329 ASSERT_EQ(Item::destroyed, 3);
330 ASSERT_EQ(vector.size(), 0);
331 ASSERT_FALSE(vector.IsStatic());
332 }
333
TEST_F(SmallVectorTest,ConstructingAssign)334 TEST_F(SmallVectorTest, ConstructingAssign)
335 {
336 std::array values = {0, 1, 2, 3, 4, 5, 6, 7};
337
338 // Assign from static vector to dynamic
339 {
340 SmallVector<int, 2> vector1;
341 SmallVector<int, 2> vector2;
342 std::copy(values.begin(), values.end(), std::back_inserter(vector1));
343 vector2.push_back(values[0]);
344 vector2.push_back(values[1]);
345
346 vector1 = vector2;
347 ASSERT_EQ(vector1.size(), 2);
348 ASSERT_TRUE(vector1.IsStatic());
349 ASSERT_TRUE(std::equal(vector1.begin(), vector1.end(), vector2.begin()));
350 vector1.push_back(values[2]);
351 ASSERT_FALSE(vector1.IsStatic());
352 }
353
354 // Assign from dynamic vector to static
355 {
356 SmallVector<int, 2> vector1;
357 SmallVector<int, 2> vector2;
358 std::copy(values.begin(), values.end(), std::back_inserter(vector2));
359 vector1.push_back(values[0]);
360 vector1.push_back(values[1]);
361
362 vector1 = vector2;
363 ASSERT_EQ(vector1.size(), values.size());
364 ASSERT_FALSE(vector1.IsStatic());
365 ASSERT_TRUE(std::equal(vector1.begin(), vector1.end(), vector2.begin()));
366 }
367 }
368
TEST_F(SmallVectorTest,ConstructingMove)369 TEST_F(SmallVectorTest, ConstructingMove)
370 {
371 std::array values = {0, 1, 2, 3, 4, 5, 6, 7};
372
373 // Move assign from static vector to dynamic
374 {
375 SmallVector<int, 2> vector1;
376 SmallVector<int, 2> vector2;
377 std::copy(values.begin(), values.end(), std::back_inserter(vector1));
378 vector2.push_back(values[0]);
379 vector2.push_back(values[1]);
380
381 vector1 = std::move(vector2);
382 ASSERT_EQ(vector1.size(), 2);
383 ASSERT_EQ(vector2.size(), 0);
384 ASSERT_TRUE(vector2.IsStatic());
385 ASSERT_TRUE(vector1.IsStatic());
386 ASSERT_TRUE(std::equal(vector1.begin(), vector1.end(), values.begin()));
387 }
388
389 // Move assign from dynamic vector to static
390 {
391 SmallVector<int, 2> vector1;
392 SmallVector<int, 2> vector2;
393 std::copy(values.begin(), values.end(), std::back_inserter(vector2));
394 vector1.push_back(values[0]);
395 vector1.push_back(values[1]);
396
397 vector1 = std::move(vector2);
398 ASSERT_EQ(vector1.size(), values.size());
399 ASSERT_EQ(vector2.size(), 0);
400 ASSERT_TRUE(vector2.IsStatic());
401 ASSERT_FALSE(vector1.IsStatic());
402 ASSERT_TRUE(std::equal(vector1.begin(), vector1.end(), values.begin()));
403 }
404 }
405
TEST_F(SmallVectorTest,ConstructingCopy)406 TEST_F(SmallVectorTest, ConstructingCopy)
407 {
408 std::array values = {0, 1, 2, 3, 4, 5, 6, 7};
409
410 // Copy constructor from dynamic
411 {
412 SmallVector<int, 2> vector1;
413 std::copy(values.begin(), values.end(), std::back_inserter(vector1));
414 ASSERT_FALSE(vector1.IsStatic());
415 ASSERT_EQ(vector1.size(), values.size());
416 SmallVector<int, 2> vector2(vector1);
417 ASSERT_EQ(vector1.size(), values.size());
418 ASSERT_EQ(vector2.size(), values.size());
419 ASSERT_TRUE(std::equal(vector2.begin(), vector2.end(), vector1.begin()));
420 }
421
422 // Copy constructor from static
423 {
424 SmallVector<int, 2> vector1;
425 std::copy(values.begin(), values.begin() + 2, std::back_inserter(vector1));
426 ASSERT_TRUE(vector1.IsStatic());
427 SmallVector<int, 2> vector2(vector1);
428 ASSERT_EQ(vector1.size(), 2);
429 ASSERT_EQ(vector2.size(), 2);
430 ASSERT_TRUE(std::equal(vector2.begin(), vector2.end(), vector1.begin()));
431 }
432 }
433
TEST_F(SmallVectorTest,ConstructingMoveDynamic)434 TEST_F(SmallVectorTest, ConstructingMoveDynamic)
435 {
436 std::array values = {0, 1, 2, 3, 4, 5, 6, 7};
437
438 // Move constructor from dynamic
439 {
440 SmallVector<int, 2> vector1;
441 std::copy(values.begin(), values.end(), std::back_inserter(vector1));
442 ASSERT_FALSE(vector1.IsStatic());
443 ASSERT_EQ(vector1.size(), values.size());
444 SmallVector<int, 2> vector2(std::move(vector1));
445 ASSERT_EQ(vector1.size(), 0);
446 ASSERT_EQ(vector2.size(), values.size());
447 ASSERT_TRUE(std::equal(vector2.begin(), vector2.end(), values.begin()));
448 }
449
450 // Move constructor from static
451 {
452 SmallVector<int, 2> vector1;
453 std::copy(values.begin(), values.begin() + 2, std::back_inserter(vector1));
454 ASSERT_TRUE(vector1.IsStatic());
455 SmallVector<int, 2> vector2(std::move(vector1));
456 ASSERT_EQ(vector1.size(), 0);
457 ASSERT_EQ(vector2.size(), 2);
458 ASSERT_TRUE(std::equal(vector2.begin(), vector2.end(), values.begin()));
459 }
460 }
461
462 } // namespace panda::test
463