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>
TestVectorIteration(Vector & vector)95 void TestVectorIteration(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 std::copy(values.begin() + 4, values.end(), std::back_inserter(vector));
131 ASSERT_EQ(vector.size(), 10);
132 ASSERT_FALSE(vector.IsStatic());
133 ASSERT_TRUE(std::equal(vector.begin(), vector.end(), values.begin()));
134
135 {
136 auto it = std::find(vector.crbegin(), vector.crend(), 30);
137 ASSERT_NE(it, vector.crend());
138 ASSERT_EQ(*it, 30);
139 ASSERT_EQ(std::distance(vector.crbegin(), it), 7);
140
141 it = std::find(vector.crbegin(), vector.crend(), 190);
142 ASSERT_EQ(it, vector.crend());
143 }
144
145 {
146 auto it = vector.begin();
147 ASSERT_EQ(*(it + 3), vector[3]);
148 std::advance(it, 8);
149 ASSERT_EQ(*it, vector[8]);
150 it -= 3;
151 ASSERT_EQ(*it, vector[5]);
152 ASSERT_EQ(*(it - 3), vector[2]);
153 it++;
154 ASSERT_EQ(*(it - 3), vector[3]);
155 --it;
156 ASSERT_EQ(*(it - 3), vector[2]);
157 it--;
158 ASSERT_EQ(*(it - 3), vector[1]);
159 }
160 }
161
TEST_F(SmallVectorTest,Iteration)162 TEST_F(SmallVectorTest, Iteration)
163 {
164 {
165 SmallVector<int, 4> vector;
166 TestVectorIteration(vector);
167 }
168 {
169 SmallVector<int, 4, ArenaAllocator, true> vector(GetAllocator());
170 TestVectorIteration(vector);
171 }
172 }
173
174 struct Item {
Itempanda::test::Item175 Item()
176 {
177 constructed++;
178 }
Itempanda::test::Item179 Item(int aa, double bb) : a(aa), b(bb)
180 {
181 constructed++;
182 }
~Itempanda::test::Item183 virtual ~Item()
184 {
185 destroyed++;
186 }
187 DEFAULT_COPY_SEMANTIC(Item);
188 DEFAULT_MOVE_SEMANTIC(Item);
189
operator ==panda::test::Item190 bool operator==(const Item &rhs) const
191 {
192 return a == rhs.a && b == rhs.b;
193 }
Resetpanda::test::Item194 static void Reset()
195 {
196 constructed = 0;
197 destroyed = 0;
198 }
199 int a {101};
200 double b {202};
201 static inline size_t constructed = 0;
202 static inline size_t destroyed = 0;
203 };
204
TEST_F(SmallVectorTest,Emplace)205 TEST_F(SmallVectorTest, Emplace)
206 {
207 SmallVector<Item, 1> vector;
208 vector.emplace_back(1, 1.1);
209 ASSERT_EQ(vector.size(), 1);
210 ASSERT_EQ(vector[0], Item(1, 1.1));
211 ASSERT_TRUE(vector.IsStatic());
212 vector.emplace_back(2, 2.2);
213 ASSERT_FALSE(vector.IsStatic());
214 ASSERT_EQ(vector[1], Item(2, 2.2));
215 vector.push_back(Item(3, 3.3));
216 ASSERT_EQ(vector[2], Item(3, 3.3));
217 }
218
TEST_F(SmallVectorTest,ResizeStatic)219 TEST_F(SmallVectorTest, ResizeStatic)
220 {
221 SmallVector<Item, 4> vector;
222
223 vector.push_back(Item(1, 1.2));
224 ASSERT_EQ(vector[0], Item(1, 1.2));
225 Item::Reset();
226 vector.resize(3);
227 ASSERT_EQ(Item::constructed, 2);
228 ASSERT_EQ(vector.size(), 3);
229 ASSERT_TRUE(vector.IsStatic());
230 ASSERT_EQ(vector[0], Item(1, 1.2));
231 ASSERT_EQ(vector[1], Item());
232 ASSERT_EQ(vector[2], Item());
233
234 Item::Reset();
235 vector.resize(1);
236 ASSERT_EQ(vector.size(), 1);
237 ASSERT_EQ(Item::destroyed, 2);
238
239 Item::Reset();
240 vector.clear();
241 ASSERT_EQ(Item::destroyed, 1);
242 ASSERT_EQ(vector.size(), 0);
243 }
244
TEST_F(SmallVectorTest,ResizeDynamic)245 TEST_F(SmallVectorTest, ResizeDynamic)
246 {
247 std::array values = {Item(1, 1.2), Item(2, 2.3), Item(3, 3.4)};
248 SmallVector<Item, 2> vector;
249
250 Item::Reset();
251 vector.resize(6);
252 ASSERT_EQ(Item::constructed, 6);
253 ASSERT_FALSE(vector.IsStatic());
254 ASSERT_EQ(vector.size(), 6);
255 ASSERT_TRUE(std::all_of(vector.begin(), vector.end(), [](const auto &v) { return v == Item(); }));
256
257 Item::Reset();
258 vector.resize(3);
259 ASSERT_EQ(vector.size(), 3);
260 ASSERT_EQ(Item::destroyed, 3);
261 ASSERT_FALSE(vector.IsStatic());
262
263 Item::Reset();
264 vector.clear();
265 ASSERT_EQ(Item::destroyed, 3);
266 ASSERT_EQ(vector.size(), 0);
267 ASSERT_FALSE(vector.IsStatic());
268 }
269
TEST_F(SmallVectorTest,ResizeStaticWithValue)270 TEST_F(SmallVectorTest, ResizeStaticWithValue)
271 {
272 SmallVector<Item, 4> vector;
273
274 vector.push_back(Item(1, 1.2));
275 ASSERT_EQ(vector[0], Item(1, 1.2));
276 Item::Reset();
277 vector.resize(3, Item(3, 3.3));
278 ASSERT_EQ(vector.size(), 3);
279 ASSERT_TRUE(vector.IsStatic());
280 ASSERT_EQ(vector[0], Item(1, 1.2));
281 ASSERT_EQ(vector[1], Item(3, 3.3));
282 ASSERT_EQ(vector[2], Item(3, 3.3));
283
284 Item item(3, 3.3);
285 Item::Reset();
286 vector.resize(1, item);
287 ASSERT_EQ(vector.size(), 1);
288 ASSERT_EQ(Item::destroyed, 2);
289
290 Item::Reset();
291 vector.clear();
292 ASSERT_EQ(Item::destroyed, 1);
293 ASSERT_EQ(vector.size(), 0);
294 }
295
TEST_F(SmallVectorTest,ResizeDynamicWithValue)296 TEST_F(SmallVectorTest, ResizeDynamicWithValue)
297 {
298 std::array values = {Item(1, 1.2), Item(2, 2.3), Item(3, 3.4)};
299 SmallVector<Item, 2> vector;
300
301 Item::Reset();
302 vector.resize(6, Item(3, 3.3));
303 ASSERT_FALSE(vector.IsStatic());
304 ASSERT_EQ(vector.size(), 6);
305 ASSERT_TRUE(std::all_of(vector.begin(), vector.end(), [](const auto &v) { return v == Item(3, 3.3); }));
306
307 Item item(3, 3.3);
308 Item::Reset();
309 vector.resize(3, item);
310 ASSERT_EQ(vector.size(), 3);
311 ASSERT_EQ(Item::destroyed, 3);
312 ASSERT_FALSE(vector.IsStatic());
313
314 Item::Reset();
315 vector.clear();
316 ASSERT_EQ(Item::destroyed, 3);
317 ASSERT_EQ(vector.size(), 0);
318 ASSERT_FALSE(vector.IsStatic());
319 }
320
TEST_F(SmallVectorTest,Constructing)321 TEST_F(SmallVectorTest, Constructing)
322 {
323 std::array values = {0, 1, 2, 3, 4, 5, 6, 7};
324
325 // Assign from static vector to dynamic
326 {
327 SmallVector<int, 2> vector1;
328 SmallVector<int, 2> vector2;
329 std::copy(values.begin(), values.end(), std::back_inserter(vector1));
330 vector2.push_back(values[0]);
331 vector2.push_back(values[1]);
332
333 vector1 = vector2;
334 ASSERT_EQ(vector1.size(), 2);
335 ASSERT_TRUE(vector1.IsStatic());
336 ASSERT_TRUE(std::equal(vector1.begin(), vector1.end(), vector2.begin()));
337 vector1.push_back(values[2]);
338 ASSERT_FALSE(vector1.IsStatic());
339 }
340 // Assign from dynamic vector to static
341 {
342 SmallVector<int, 2> vector1;
343 SmallVector<int, 2> vector2;
344 std::copy(values.begin(), values.end(), std::back_inserter(vector2));
345 vector1.push_back(values[0]);
346 vector1.push_back(values[1]);
347
348 vector1 = vector2;
349 ASSERT_EQ(vector1.size(), values.size());
350 ASSERT_FALSE(vector1.IsStatic());
351 ASSERT_TRUE(std::equal(vector1.begin(), vector1.end(), vector2.begin()));
352 }
353
354 // Move assign from static vector to dynamic
355 {
356 SmallVector<int, 2> vector1;
357 SmallVector<int, 2> vector2;
358 std::copy(values.begin(), values.end(), std::back_inserter(vector1));
359 vector2.push_back(values[0]);
360 vector2.push_back(values[1]);
361
362 vector1 = std::move(vector2);
363 ASSERT_EQ(vector1.size(), 2);
364 ASSERT_EQ(vector2.size(), 0);
365 ASSERT_TRUE(vector2.IsStatic());
366 ASSERT_TRUE(vector1.IsStatic());
367 ASSERT_TRUE(std::equal(vector1.begin(), vector1.end(), values.begin()));
368 }
369 // Move assign from dynamic vector to static
370 {
371 SmallVector<int, 2> vector1;
372 SmallVector<int, 2> vector2;
373 std::copy(values.begin(), values.end(), std::back_inserter(vector2));
374 vector1.push_back(values[0]);
375 vector1.push_back(values[1]);
376
377 vector1 = std::move(vector2);
378 ASSERT_EQ(vector1.size(), values.size());
379 ASSERT_EQ(vector2.size(), 0);
380 ASSERT_TRUE(vector2.IsStatic());
381 ASSERT_FALSE(vector1.IsStatic());
382 ASSERT_TRUE(std::equal(vector1.begin(), vector1.end(), values.begin()));
383 }
384
385 // Copy constructor from dynamic
386 {
387 SmallVector<int, 2> vector1;
388 std::copy(values.begin(), values.end(), std::back_inserter(vector1));
389 ASSERT_FALSE(vector1.IsStatic());
390 ASSERT_EQ(vector1.size(), values.size());
391 SmallVector<int, 2> vector2(vector1);
392 ASSERT_EQ(vector1.size(), values.size());
393 ASSERT_EQ(vector2.size(), values.size());
394 ASSERT_TRUE(std::equal(vector2.begin(), vector2.end(), vector1.begin()));
395 }
396 // Copy constructor from static
397 {
398 SmallVector<int, 2> vector1;
399 std::copy(values.begin(), values.begin() + 2, std::back_inserter(vector1));
400 ASSERT_TRUE(vector1.IsStatic());
401 SmallVector<int, 2> vector2(vector1);
402 ASSERT_EQ(vector1.size(), 2);
403 ASSERT_EQ(vector2.size(), 2);
404 ASSERT_TRUE(std::equal(vector2.begin(), vector2.end(), vector1.begin()));
405 }
406
407 // Move constructor from dynamic
408 {
409 SmallVector<int, 2> vector1;
410 std::copy(values.begin(), values.end(), std::back_inserter(vector1));
411 ASSERT_FALSE(vector1.IsStatic());
412 ASSERT_EQ(vector1.size(), values.size());
413 SmallVector<int, 2> vector2(std::move(vector1));
414 ASSERT_EQ(vector1.size(), 0);
415 ASSERT_EQ(vector2.size(), values.size());
416 ASSERT_TRUE(std::equal(vector2.begin(), vector2.end(), values.begin()));
417 }
418 // Move constructor from static
419 {
420 SmallVector<int, 2> vector1;
421 std::copy(values.begin(), values.begin() + 2, std::back_inserter(vector1));
422 ASSERT_TRUE(vector1.IsStatic());
423 SmallVector<int, 2> vector2(std::move(vector1));
424 ASSERT_EQ(vector1.size(), 0);
425 ASSERT_EQ(vector2.size(), 2);
426 ASSERT_TRUE(std::equal(vector2.begin(), vector2.end(), values.begin()));
427 }
428 }
429
430 } // namespace panda::test
431