1 // Copyright 2017 The Fuchsia Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include <fbl/ref_counted.h>
6 #include <fbl/ref_ptr.h>
7 #include <fbl/string.h>
8 #include <fbl/tests/lfsr.h>
9 #include <fbl/unique_ptr.h>
10 #include <fbl/vector.h>
11 #include <unittest/unittest.h>
12
13 #include <utility>
14
15 namespace fbl {
16 namespace tests {
17 namespace {
18
19 // Different container classes for the types of objects
20 // which should be tested within a vector (raw types,
21 // unique pointers, ref pointers).
22
23 using ValueType = size_t;
24
25 struct TestObject {
26 DISALLOW_COPY_AND_ASSIGN_ALLOW_MOVE(TestObject);
27 TestObject() = delete;
TestObjectfbl::tests::__anon76844adc0111::TestObject28 explicit TestObject(ValueType val)
29 : alive_(true), val_(val) {
30 ++live_obj_count_;
31 ++ctor_count_;
32 }
TestObjectfbl::tests::__anon76844adc0111::TestObject33 TestObject(TestObject&& r)
34 : alive_(r.alive_), val_(r.val_) {
35 r.alive_ = false;
36 ++ctor_count_;
37 }
operator =fbl::tests::__anon76844adc0111::TestObject38 TestObject& operator=(TestObject&& r) {
39 val_ = r.val_;
40 alive_ = r.alive_;
41 r.alive_ = false;
42 return *this;
43 }
~TestObjectfbl::tests::__anon76844adc0111::TestObject44 ~TestObject() {
45 if (alive_) {
46 --live_obj_count_;
47 }
48 ++dtor_count_;
49 }
50
valuefbl::tests::__anon76844adc0111::TestObject51 ValueType value() const { return val_; }
live_obj_countfbl::tests::__anon76844adc0111::TestObject52 static size_t live_obj_count() { return live_obj_count_; }
ResetLiveObjCountfbl::tests::__anon76844adc0111::TestObject53 static void ResetLiveObjCount() { live_obj_count_ = 0; }
54
55 bool alive_;
56 ValueType val_;
57
58 static size_t live_obj_count_;
59 static size_t ctor_count_;
60 static size_t dtor_count_;
61 };
62
63 size_t TestObject::live_obj_count_ = 0;
64 size_t TestObject::ctor_count_ = 0;
65 size_t TestObject::dtor_count_ = 0;
66
67 struct ValueTypeTraits {
68 using ItemType = ValueType;
Createfbl::tests::__anon76844adc0111::ValueTypeTraits69 static ItemType Create(ValueType val) { return val; }
GetValuefbl::tests::__anon76844adc0111::ValueTypeTraits70 static ValueType GetValue(const ItemType& c) { return c; }
71 // We have no way of managing the "live count" of raw types, so we don't.
CheckLiveCountfbl::tests::__anon76844adc0111::ValueTypeTraits72 static bool CheckLiveCount(size_t expected) { return true; }
CheckCtorDtorCountfbl::tests::__anon76844adc0111::ValueTypeTraits73 static bool CheckCtorDtorCount() { return true; }
74 };
75
76 struct StructTypeTraits {
77 using ItemType = TestObject;
Createfbl::tests::__anon76844adc0111::StructTypeTraits78 static ItemType Create(ValueType val) { return TestObject(val); }
GetValuefbl::tests::__anon76844adc0111::StructTypeTraits79 static ValueType GetValue(const ItemType& c) { return c.value(); }
CheckLiveCountfbl::tests::__anon76844adc0111::StructTypeTraits80 static bool CheckLiveCount(size_t expected) { return TestObject::live_obj_count() == expected; }
CheckCtorDtorCountfbl::tests::__anon76844adc0111::StructTypeTraits81 static bool CheckCtorDtorCount() { return TestObject::ctor_count_ == TestObject::dtor_count_; }
82 };
83
84 struct UniquePtrTraits {
85 using ItemType = fbl::unique_ptr<TestObject>;
86
Createfbl::tests::__anon76844adc0111::UniquePtrTraits87 static ItemType Create(ValueType val) {
88 AllocChecker ac;
89 ItemType ptr(new (&ac) TestObject(val));
90 ZX_ASSERT(ac.check());
91 return ptr;
92 }
GetValuefbl::tests::__anon76844adc0111::UniquePtrTraits93 static ValueType GetValue(const ItemType& c) { return c->value(); }
CheckLiveCountfbl::tests::__anon76844adc0111::UniquePtrTraits94 static bool CheckLiveCount(size_t expected) { return TestObject::live_obj_count() == expected; }
CheckCtorDtorCountfbl::tests::__anon76844adc0111::UniquePtrTraits95 static bool CheckCtorDtorCount() { return TestObject::ctor_count_ == TestObject::dtor_count_; }
96 };
97
98 template <typename T>
99 struct RefCountedItem : public fbl::RefCounted<RefCountedItem<T>> {
RefCountedItemfbl::tests::__anon76844adc0111::RefCountedItem100 RefCountedItem(T v)
101 : val(std::move(v)) {}
102 DISALLOW_COPY_ASSIGN_AND_MOVE(RefCountedItem);
103 T val;
104 };
105
106 struct RefPtrTraits {
107 using ItemType = fbl::RefPtr<RefCountedItem<TestObject>>;
108
Createfbl::tests::__anon76844adc0111::RefPtrTraits109 static ItemType Create(ValueType val) {
110 AllocChecker ac;
111 auto ptr = AdoptRef(new (&ac) RefCountedItem<TestObject>(TestObject(val)));
112 ZX_ASSERT(ac.check());
113 return ptr;
114 }
GetValuefbl::tests::__anon76844adc0111::RefPtrTraits115 static ValueType GetValue(const ItemType& c) { return c->val.value(); }
CheckLiveCountfbl::tests::__anon76844adc0111::RefPtrTraits116 static bool CheckLiveCount(size_t expected) { return TestObject::live_obj_count() == expected; }
CheckCtorDtorCountfbl::tests::__anon76844adc0111::RefPtrTraits117 static bool CheckCtorDtorCount() { return TestObject::ctor_count_ == TestObject::dtor_count_; }
118 };
119
120 // Helper classes
121
122 template <typename ItemTraits>
123 struct Generator {
124 using ItemType = typename ItemTraits::ItemType;
125
126 constexpr static ValueType seed = 0xa2328b73e323fd0f;
NextValuefbl::tests::__anon76844adc0111::Generator127 ValueType NextValue() { return key_lfsr_.GetNext(); }
NextItemfbl::tests::__anon76844adc0111::Generator128 ItemType NextItem() { return ItemTraits::Create(NextValue()); }
Resetfbl::tests::__anon76844adc0111::Generator129 void Reset() { key_lfsr_.SetCore(seed); }
130 Lfsr<ValueType> key_lfsr_ = Lfsr<ValueType>(seed);
131 };
132
133 struct TestAllocatorTraits : public DefaultAllocatorTraits {
Allocatefbl::tests::__anon76844adc0111::TestAllocatorTraits134 static void* Allocate(size_t size) {
135 void* result = DefaultAllocatorTraits::Allocate(size);
136 // Intentionally fill the allocated portion of memory
137 // with non-zero data to break the assumption that
138 // the heap will return "clean" data. This helps
139 // catch bugs where the vector might call move assignment
140 // operators into portions of uninitialized memory.
141 if (result) {
142 memset(result, 'f', size);
143 }
144 return result;
145 }
146 };
147
148 // Actual tests
149
150 template <typename ItemTraits, size_t size>
VectorTestAccessRelease()151 bool VectorTestAccessRelease() {
152 using ItemType = typename ItemTraits::ItemType;
153
154 BEGIN_TEST;
155
156 ASSERT_TRUE(ItemTraits::CheckCtorDtorCount());
157 Generator<ItemTraits> gen;
158 // Create the vector, verify its contents
159 {
160 fbl::Vector<ItemType, TestAllocatorTraits> vector;
161 fbl::AllocChecker ac;
162 vector.reserve(size, &ac);
163 ASSERT_TRUE(ac.check());
164 for (size_t i = 0; i < size; i++) {
165 ASSERT_TRUE(ItemTraits::CheckLiveCount(i));
166 vector.push_back(gen.NextItem(), &ac);
167 ASSERT_TRUE(ac.check());
168 }
169 ASSERT_TRUE(ItemTraits::CheckLiveCount(size));
170
171 gen.Reset();
172 ItemType* data = vector.get();
173 for (size_t i = 0; i < size; i++) {
174 auto base = gen.NextValue();
175 // Verify the contents using the [] operator
176 ASSERT_EQ(ItemTraits::GetValue(vector[i]), base);
177 // Verify the contents using the underlying array
178 ASSERT_EQ(ItemTraits::GetValue(data[i]), base);
179 }
180
181 // Release the vector's underlying array before it is destructed
182 ASSERT_TRUE(ItemTraits::CheckLiveCount(size));
183 vector.reset();
184 ASSERT_EQ(vector.size(), 0);
185 ASSERT_EQ(vector.capacity(), 0);
186 ASSERT_TRUE(ItemTraits::CheckLiveCount(0));
187 }
188 ASSERT_TRUE(ItemTraits::CheckLiveCount(0));
189 ASSERT_TRUE(ItemTraits::CheckCtorDtorCount());
190
191 END_TEST;
192 }
193
194 struct CountedAllocatorTraits : public TestAllocatorTraits {
Allocatefbl::tests::__anon76844adc0111::CountedAllocatorTraits195 static void* Allocate(size_t size) {
196 allocation_count++;
197 return TestAllocatorTraits::Allocate(size);
198 }
199 static size_t allocation_count;
200 };
201
202 size_t CountedAllocatorTraits::allocation_count = 0;
203
204 template <typename ItemTraits, size_t size>
VectorTestPushBackInCapacity()205 bool VectorTestPushBackInCapacity() {
206 using ItemType = typename ItemTraits::ItemType;
207
208 BEGIN_TEST;
209
210 Generator<ItemTraits> gen;
211
212 CountedAllocatorTraits::allocation_count = 0;
213 ASSERT_TRUE(ItemTraits::CheckLiveCount(0));
214 ASSERT_TRUE(ItemTraits::CheckCtorDtorCount());
215 {
216 fbl::Vector<ItemType, CountedAllocatorTraits> vector;
217 ASSERT_EQ(CountedAllocatorTraits::allocation_count, 0);
218 fbl::AllocChecker ac;
219 vector.reserve(size, &ac);
220 ASSERT_TRUE(ac.check());
221 ASSERT_EQ(CountedAllocatorTraits::allocation_count, 1);
222
223 for (size_t i = 0; i < size; i++) {
224 ASSERT_TRUE(ItemTraits::CheckLiveCount(i));
225 vector.push_back(gen.NextItem(), &ac);
226 ASSERT_TRUE(ac.check());
227 }
228 ASSERT_EQ(CountedAllocatorTraits::allocation_count, 1);
229
230 gen.Reset();
231 for (size_t i = 0; i < size; i++) {
232 ASSERT_EQ(ItemTraits::GetValue(vector[i]), gen.NextValue());
233 }
234 ASSERT_TRUE(ItemTraits::CheckLiveCount(size));
235 }
236 ASSERT_TRUE(ItemTraits::CheckLiveCount(0));
237 ASSERT_TRUE(ItemTraits::CheckCtorDtorCount());
238
239 END_TEST;
240 }
241
242 template <typename ItemTraits, size_t size>
VectorTestPushBackByConstRefInCapacity()243 bool VectorTestPushBackByConstRefInCapacity() {
244 using ItemType = typename ItemTraits::ItemType;
245
246 BEGIN_TEST;
247
248 Generator<ItemTraits> gen;
249
250 CountedAllocatorTraits::allocation_count = 0;
251 ASSERT_TRUE(ItemTraits::CheckLiveCount(0));
252 ASSERT_TRUE(ItemTraits::CheckCtorDtorCount());
253 {
254 fbl::Vector<ItemType, CountedAllocatorTraits> vector;
255 ASSERT_EQ(CountedAllocatorTraits::allocation_count, 0);
256 fbl::AllocChecker ac;
257 vector.reserve(size, &ac);
258 ASSERT_TRUE(ac.check());
259 ASSERT_EQ(CountedAllocatorTraits::allocation_count, 1);
260
261 for (size_t i = 0; i < size; i++) {
262 ASSERT_TRUE(ItemTraits::CheckLiveCount(i));
263 const ItemType item = gen.NextItem();
264 vector.push_back(item, &ac);
265 ASSERT_TRUE(ac.check());
266 }
267 ASSERT_EQ(CountedAllocatorTraits::allocation_count, 1);
268
269 gen.Reset();
270 for (size_t i = 0; i < size; i++) {
271 ASSERT_EQ(ItemTraits::GetValue(vector[i]), gen.NextValue());
272 }
273 ASSERT_TRUE(ItemTraits::CheckLiveCount(size));
274 }
275 ASSERT_TRUE(ItemTraits::CheckLiveCount(0));
276 ASSERT_TRUE(ItemTraits::CheckCtorDtorCount());
277
278 END_TEST;
279 }
280
281 template <typename ItemTraits, size_t size>
VectorTestPushBackBeyondCapacity()282 bool VectorTestPushBackBeyondCapacity() {
283 using ItemType = typename ItemTraits::ItemType;
284
285 BEGIN_TEST;
286
287 Generator<ItemTraits> gen;
288
289 ASSERT_TRUE(ItemTraits::CheckCtorDtorCount());
290 {
291 // Create an empty vector, push back beyond its capacity
292 fbl::Vector<ItemType, TestAllocatorTraits> vector;
293 for (size_t i = 0; i < size; i++) {
294 ASSERT_TRUE(ItemTraits::CheckLiveCount(i));
295 fbl::AllocChecker ac;
296 vector.push_back(gen.NextItem(), &ac);
297 ASSERT_TRUE(ac.check());
298 }
299
300 gen.Reset();
301 for (size_t i = 0; i < size; i++) {
302 ASSERT_EQ(ItemTraits::GetValue(vector[i]), gen.NextValue());
303 }
304 ASSERT_TRUE(ItemTraits::CheckLiveCount(size));
305 }
306 ASSERT_TRUE(ItemTraits::CheckLiveCount(0));
307 ASSERT_TRUE(ItemTraits::CheckCtorDtorCount());
308
309 END_TEST;
310 }
311
312 template <typename ItemTraits, size_t size>
VectorTestPushBackByConstRefBeyondCapacity()313 bool VectorTestPushBackByConstRefBeyondCapacity() {
314 using ItemType = typename ItemTraits::ItemType;
315
316 BEGIN_TEST;
317
318 Generator<ItemTraits> gen;
319
320 ASSERT_TRUE(ItemTraits::CheckCtorDtorCount());
321 {
322 // Create an empty vector, push back beyond its capacity
323 fbl::Vector<ItemType, TestAllocatorTraits> vector;
324 for (size_t i = 0; i < size; i++) {
325 ASSERT_TRUE(ItemTraits::CheckLiveCount(i));
326 const ItemType item = gen.NextItem();
327 fbl::AllocChecker ac;
328 vector.push_back(item, &ac);
329 ASSERT_TRUE(ac.check());
330 }
331
332 gen.Reset();
333 for (size_t i = 0; i < size; i++) {
334 ASSERT_EQ(ItemTraits::GetValue(vector[i]), gen.NextValue());
335 }
336 ASSERT_TRUE(ItemTraits::CheckLiveCount(size));
337 }
338 ASSERT_TRUE(ItemTraits::CheckLiveCount(0));
339 ASSERT_TRUE(ItemTraits::CheckCtorDtorCount());
340
341 END_TEST;
342 }
343
344 template <typename ItemTraits, size_t size>
VectorTestPopBack()345 bool VectorTestPopBack() {
346 using ItemType = typename ItemTraits::ItemType;
347
348 BEGIN_TEST;
349
350 Generator<ItemTraits> gen;
351
352 ASSERT_TRUE(ItemTraits::CheckCtorDtorCount());
353 {
354 // Create a vector filled with objects
355 fbl::Vector<ItemType, TestAllocatorTraits> vector;
356 for (size_t i = 0; i < size; i++) {
357 ASSERT_TRUE(ItemTraits::CheckLiveCount(i));
358 fbl::AllocChecker ac;
359 vector.push_back(gen.NextItem(), &ac);
360 ASSERT_TRUE(ac.check());
361 }
362
363 gen.Reset();
364 for (size_t i = 0; i < size; i++) {
365 ASSERT_EQ(ItemTraits::GetValue(vector[i]), gen.NextValue());
366 }
367
368 // Pop one at a time, and check the vector is still valid
369 while (vector.size()) {
370 vector.pop_back();
371 ASSERT_TRUE(ItemTraits::CheckLiveCount(vector.size()));
372 gen.Reset();
373 for (size_t i = 0; i < vector.size(); i++) {
374 ASSERT_EQ(ItemTraits::GetValue(vector[i]), gen.NextValue());
375 }
376 }
377
378 ASSERT_TRUE(ItemTraits::CheckLiveCount(0));
379 }
380 ASSERT_TRUE(ItemTraits::CheckLiveCount(0));
381 ASSERT_TRUE(ItemTraits::CheckCtorDtorCount());
382
383 END_TEST;
384 }
385
386 struct FailingAllocatorTraits {
Allocatefbl::tests::__anon76844adc0111::FailingAllocatorTraits387 static void* Allocate(size_t size) { return nullptr; }
Deallocatefbl::tests::__anon76844adc0111::FailingAllocatorTraits388 static void Deallocate(void* object) { return; }
389 };
390
391 template <typename ItemType, size_t S>
392 struct PartiallyFailingAllocatorTraits : public DefaultAllocatorTraits {
Allocatefbl::tests::__anon76844adc0111::PartiallyFailingAllocatorTraits393 static void* Allocate(size_t size) {
394 if (size <= sizeof(ItemType) * S) {
395 return DefaultAllocatorTraits::Allocate(size);
396 }
397 return nullptr;
398 }
399 };
400
401 template <typename ItemTraits, size_t size>
VectorTestAllocationFailure()402 bool VectorTestAllocationFailure() {
403 using ItemType = typename ItemTraits::ItemType;
404
405 BEGIN_TEST;
406
407 Generator<ItemTraits> gen;
408 ASSERT_TRUE(ItemTraits::CheckCtorDtorCount());
409
410 // Test that a failing allocator cannot take on additional elements
411 {
412 fbl::Vector<ItemType, FailingAllocatorTraits> vector;
413 fbl::AllocChecker ac;
414 vector.reserve(0, &ac);
415 ASSERT_TRUE(ac.check());
416 vector.reserve(1, &ac);
417 ASSERT_FALSE(ac.check());
418 vector.reserve(size, &ac);
419 ASSERT_FALSE(ac.check());
420
421 ASSERT_TRUE(ItemTraits::CheckLiveCount(0));
422 vector.push_back(gen.NextItem(), &ac);
423 ASSERT_FALSE(ac.check());
424 ASSERT_TRUE(ItemTraits::CheckLiveCount(0));
425 }
426 ASSERT_TRUE(ItemTraits::CheckLiveCount(0));
427 ASSERT_TRUE(ItemTraits::CheckCtorDtorCount());
428
429 // Test that a partially failing allocator stops taking on additional
430 // elements
431 {
432 fbl::Vector<ItemType, PartiallyFailingAllocatorTraits<ItemType, size>> vector;
433 fbl::AllocChecker ac;
434 vector.reserve(0, &ac);
435 ASSERT_TRUE(ac.check());
436 vector.reserve(1, &ac);
437 ASSERT_TRUE(ac.check());
438 vector.reserve(size, &ac);
439 ASSERT_TRUE(ac.check());
440 ASSERT_EQ(vector.capacity(), size);
441
442 ASSERT_TRUE(ItemTraits::CheckLiveCount(0));
443 gen.Reset();
444 while (vector.size() < size) {
445 vector.push_back(gen.NextItem(), &ac);
446 ASSERT_TRUE(ac.check());
447 ASSERT_TRUE(ItemTraits::CheckLiveCount(vector.size()));
448 }
449 vector.push_back(gen.NextItem(), &ac);
450 ASSERT_FALSE(ac.check());
451 ASSERT_TRUE(ItemTraits::CheckLiveCount(size));
452 ASSERT_EQ(vector.size(), size);
453 ASSERT_EQ(vector.capacity(), size);
454
455 // All the elements we were able to push back should still be present
456 gen.Reset();
457 for (size_t i = 0; i < vector.size(); i++) {
458 ASSERT_EQ(ItemTraits::GetValue(vector[i]), gen.NextValue());
459 }
460 ASSERT_TRUE(ItemTraits::CheckLiveCount(size));
461 }
462 ASSERT_TRUE(ItemTraits::CheckLiveCount(0));
463 ASSERT_TRUE(ItemTraits::CheckCtorDtorCount());
464
465 END_TEST;
466 }
467
468 template <typename ItemTraits, size_t size>
VectorTestMove()469 bool VectorTestMove() {
470 using ItemType = typename ItemTraits::ItemType;
471
472 BEGIN_TEST;
473
474 Generator<ItemTraits> gen;
475 ASSERT_TRUE(ItemTraits::CheckCtorDtorCount());
476
477 // Test move constructor
478 {
479 fbl::Vector<ItemType, TestAllocatorTraits> vectorA;
480 ASSERT_TRUE(vectorA.is_empty());
481 for (size_t i = 0; i < size; i++) {
482 ASSERT_TRUE(ItemTraits::CheckLiveCount(i));
483 fbl::AllocChecker ac;
484 vectorA.push_back(gen.NextItem(), &ac);
485 ASSERT_TRUE(ac.check());
486 }
487
488 gen.Reset();
489 ASSERT_FALSE(vectorA.is_empty());
490 ASSERT_EQ(vectorA.size(), size);
491 fbl::Vector<ItemType, TestAllocatorTraits> vectorB(std::move(vectorA));
492 ASSERT_TRUE(ItemTraits::CheckLiveCount(size));
493 ASSERT_TRUE(vectorA.is_empty());
494 ASSERT_EQ(vectorA.size(), 0);
495 ASSERT_EQ(vectorB.size(), size);
496 for (size_t i = 0; i < size; i++) {
497 ASSERT_EQ(ItemTraits::GetValue(vectorB[i]), gen.NextValue());
498 }
499 ASSERT_TRUE(ItemTraits::CheckLiveCount(size));
500 }
501 ASSERT_TRUE(ItemTraits::CheckLiveCount(0));
502 ASSERT_TRUE(ItemTraits::CheckCtorDtorCount());
503
504 // Test move assignment operator
505 {
506 gen.Reset();
507 fbl::Vector<ItemType, TestAllocatorTraits> vectorA;
508 for (size_t i = 0; i < size; i++) {
509 ASSERT_TRUE(ItemTraits::CheckLiveCount(i));
510 fbl::AllocChecker ac;
511 vectorA.push_back(gen.NextItem(), &ac);
512 ASSERT_TRUE(ac.check());
513 }
514
515 gen.Reset();
516 ASSERT_EQ(vectorA.size(), size);
517 fbl::Vector<ItemType, TestAllocatorTraits> vectorB;
518 vectorB = std::move(vectorA);
519 ASSERT_TRUE(ItemTraits::CheckLiveCount(size));
520 ASSERT_EQ(vectorA.size(), 0);
521 ASSERT_EQ(vectorB.size(), size);
522 for (size_t i = 0; i < size; i++) {
523 ASSERT_EQ(ItemTraits::GetValue(vectorB[i]), gen.NextValue());
524 }
525 ASSERT_TRUE(ItemTraits::CheckLiveCount(size));
526 }
527 ASSERT_TRUE(ItemTraits::CheckLiveCount(0));
528 ASSERT_TRUE(ItemTraits::CheckCtorDtorCount());
529
530 END_TEST;
531 }
532
533 template <typename ItemTraits, size_t size>
VectorTestSwap()534 bool VectorTestSwap() {
535 using ItemType = typename ItemTraits::ItemType;
536
537 BEGIN_TEST;
538
539 Generator<ItemTraits> gen;
540
541 ASSERT_TRUE(ItemTraits::CheckCtorDtorCount());
542 {
543 fbl::Vector<ItemType, TestAllocatorTraits> vectorA;
544 for (size_t i = 0; i < size; i++) {
545 ASSERT_TRUE(ItemTraits::CheckLiveCount(i));
546 fbl::AllocChecker ac;
547 vectorA.push_back(gen.NextItem(), &ac);
548 ASSERT_TRUE(ac.check());
549 }
550 fbl::Vector<ItemType, TestAllocatorTraits> vectorB;
551 for (size_t i = 0; i < size; i++) {
552 ASSERT_TRUE(ItemTraits::CheckLiveCount(size + i));
553 fbl::AllocChecker ac;
554 vectorB.push_back(gen.NextItem(), &ac);
555 ASSERT_TRUE(ac.check());
556 }
557
558 gen.Reset();
559
560 for (size_t i = 0; i < size; i++) {
561 ASSERT_EQ(ItemTraits::GetValue(vectorA[i]), gen.NextValue());
562 }
563 for (size_t i = 0; i < size; i++) {
564 ASSERT_EQ(ItemTraits::GetValue(vectorB[i]), gen.NextValue());
565 }
566
567 ASSERT_TRUE(ItemTraits::CheckLiveCount(size * 2));
568 vectorA.swap(vectorB);
569 ASSERT_TRUE(ItemTraits::CheckLiveCount(size * 2));
570
571 gen.Reset();
572
573 for (size_t i = 0; i < size; i++) {
574 ASSERT_EQ(ItemTraits::GetValue(vectorB[i]), gen.NextValue());
575 }
576 for (size_t i = 0; i < size; i++) {
577 ASSERT_EQ(ItemTraits::GetValue(vectorA[i]), gen.NextValue());
578 }
579 }
580 ASSERT_TRUE(ItemTraits::CheckLiveCount(0));
581 ASSERT_TRUE(ItemTraits::CheckCtorDtorCount());
582
583 END_TEST;
584 }
585
586 template <typename ItemTraits, size_t size>
VectorTestIterator()587 bool VectorTestIterator() {
588 using ItemType = typename ItemTraits::ItemType;
589
590 BEGIN_TEST;
591
592 Generator<ItemTraits> gen;
593 ASSERT_TRUE(ItemTraits::CheckCtorDtorCount());
594
595 {
596 fbl::Vector<ItemType, TestAllocatorTraits> vector;
597 for (size_t i = 0; i < size; i++) {
598 ASSERT_TRUE(ItemTraits::CheckLiveCount(i));
599 fbl::AllocChecker ac;
600 vector.push_back(gen.NextItem(), &ac);
601 ASSERT_TRUE(ac.check());
602 }
603
604 gen.Reset();
605 for (auto& e : vector) {
606 auto base = gen.NextValue();
607 ASSERT_EQ(ItemTraits::GetValue(e), base);
608 // Take the element out, and put it back... just to check
609 // that we can.
610 auto other = std::move(e);
611 e = std::move(other);
612 ASSERT_EQ(ItemTraits::GetValue(e), base);
613 }
614
615 gen.Reset();
616 const auto* cvector = &vector;
617 for (const auto& e : *cvector) {
618 ASSERT_EQ(ItemTraits::GetValue(e), gen.NextValue());
619 }
620 }
621 ASSERT_TRUE(ItemTraits::CheckLiveCount(0));
622 ASSERT_TRUE(ItemTraits::CheckCtorDtorCount());
623
624 END_TEST;
625 }
626
627 template <typename ItemTraits, size_t size>
VectorTestInsertDelete()628 bool VectorTestInsertDelete() {
629 using ItemType = typename ItemTraits::ItemType;
630
631 BEGIN_TEST;
632
633 Generator<ItemTraits> gen;
634 ASSERT_TRUE(ItemTraits::CheckCtorDtorCount());
635
636 {
637 fbl::Vector<ItemType, TestAllocatorTraits> vector;
638 fbl::AllocChecker ac;
639 for (size_t i = 0; i < size; i++) {
640 ASSERT_TRUE(ItemTraits::CheckLiveCount(i));
641 vector.insert(i, gen.NextItem(), &ac);
642 ASSERT_TRUE(ac.check());
643 }
644
645 // Insert at position zero and one
646 ASSERT_TRUE(ItemTraits::CheckLiveCount(size));
647 vector.insert(0, gen.NextItem(), &ac);
648 ASSERT_TRUE(ac.check());
649 ASSERT_TRUE(ItemTraits::CheckLiveCount(size + 1));
650 vector.insert(1, gen.NextItem(), &ac);
651 ASSERT_TRUE(ac.check());
652 ASSERT_TRUE(ItemTraits::CheckLiveCount(size + 2));
653 gen.Reset();
654
655 // Verify the contents
656 for (size_t i = 2; i < size + 2; i++) {
657 ASSERT_EQ(ItemTraits::GetValue(vector[i]), gen.NextValue());
658 }
659 ASSERT_EQ(ItemTraits::GetValue(vector[0]), gen.NextValue());
660 ASSERT_EQ(ItemTraits::GetValue(vector[1]), gen.NextValue());
661 gen.Reset();
662
663 {
664 // Erase from position one
665 ASSERT_TRUE(ItemTraits::CheckLiveCount(size + 2));
666 auto erasedval1 = vector.erase(1);
667 // Erase from position zero
668 ASSERT_TRUE(ItemTraits::CheckLiveCount(size + 2));
669 auto erasedval0 = vector.erase(0);
670 ASSERT_TRUE(ItemTraits::CheckLiveCount(size + 2));
671
672 // Verify the remaining contents
673 for (size_t i = 0; i < size; i++) {
674 ASSERT_EQ(ItemTraits::GetValue(vector[i]), gen.NextValue());
675 }
676 ASSERT_EQ(ItemTraits::GetValue(erasedval0), gen.NextValue());
677 ASSERT_EQ(ItemTraits::GetValue(erasedval1), gen.NextValue());
678 ASSERT_TRUE(ItemTraits::CheckLiveCount(size + 2));
679 }
680 ASSERT_TRUE(ItemTraits::CheckLiveCount(size));
681 gen.Reset();
682
683 // Erase the remainder of the vector
684 for (size_t i = 0; i < size; i++) {
685 vector.erase(0);
686 }
687 ASSERT_EQ(vector.size(), 0);
688 }
689 ASSERT_TRUE(ItemTraits::CheckLiveCount(0));
690 ASSERT_TRUE(ItemTraits::CheckCtorDtorCount());
691
692 END_TEST;
693 }
694
695 template <typename ItemTraits, size_t size>
VectorTestNoAllocCheck()696 bool VectorTestNoAllocCheck() {
697 using ItemType = typename ItemTraits::ItemType;
698
699 BEGIN_TEST;
700
701 ASSERT_TRUE(ItemTraits::CheckCtorDtorCount());
702
703 {
704 Generator<ItemTraits> gen;
705 fbl::Vector<ItemType, TestAllocatorTraits> vector;
706 for (size_t i = 0; i < size; i++) {
707 ASSERT_TRUE(ItemTraits::CheckLiveCount(i));
708 vector.push_back(gen.NextItem());
709 }
710 gen.Reset();
711 for (auto& e : vector) {
712 auto base = gen.NextValue();
713 ASSERT_EQ(ItemTraits::GetValue(e), base);
714 }
715 }
716
717 {
718 Generator<ItemTraits> gen;
719 fbl::Vector<ItemType, TestAllocatorTraits> vector;
720 vector.reserve(size);
721 for (size_t i = 0; i < size; i++) {
722 ASSERT_TRUE(ItemTraits::CheckLiveCount(i));
723 vector.push_back(gen.NextItem());
724 }
725 gen.Reset();
726 for (auto& e : vector) {
727 auto base = gen.NextValue();
728 ASSERT_EQ(ItemTraits::GetValue(e), base);
729 }
730 }
731
732 {
733 Generator<ItemTraits> gen;
734 fbl::Vector<ItemType, TestAllocatorTraits> vector;
735 for (size_t i = 0; i < size; i++) {
736 ASSERT_TRUE(ItemTraits::CheckLiveCount(i));
737 vector.insert(i, gen.NextItem());
738 }
739 gen.Reset();
740 for (auto& e : vector) {
741 auto base = gen.NextValue();
742 ASSERT_EQ(ItemTraits::GetValue(e), base);
743 }
744 }
745
746 ASSERT_TRUE(ItemTraits::CheckLiveCount(0));
747 ASSERT_TRUE(ItemTraits::CheckCtorDtorCount());
748
749 END_TEST;
750 }
751
752 template <typename ItemTraits>
VectorTestInitializerList()753 bool VectorTestInitializerList() {
754 using ItemType = typename ItemTraits::ItemType;
755
756 BEGIN_TEST;
757
758 Generator<ItemTraits> gen;
759
760 CountedAllocatorTraits::allocation_count = 0;
761 ASSERT_TRUE(ItemTraits::CheckLiveCount(0));
762 ASSERT_TRUE(ItemTraits::CheckCtorDtorCount());
763
764 // empty
765 {
766 fbl::Vector<ItemType, CountedAllocatorTraits> vector{};
767 ASSERT_EQ(CountedAllocatorTraits::allocation_count, 0);
768 ASSERT_EQ(0, vector.size());
769 ASSERT_EQ(0, vector.capacity());
770 }
771
772 // 5 items
773 {
774 fbl::Vector<ItemType, CountedAllocatorTraits> vector{
775 gen.NextItem(), gen.NextItem(), gen.NextItem(),
776 gen.NextItem(), gen.NextItem()};
777 ASSERT_EQ(CountedAllocatorTraits::allocation_count, 1);
778 ASSERT_EQ(5, vector.size());
779 ASSERT_EQ(5, vector.capacity());
780
781 gen.Reset();
782 for (size_t i = 0; i < 5; i++) {
783 ASSERT_EQ(ItemTraits::GetValue(vector[i]), gen.NextValue());
784 }
785 ASSERT_TRUE(ItemTraits::CheckLiveCount(5));
786 }
787 ASSERT_TRUE(ItemTraits::CheckLiveCount(0));
788 ASSERT_TRUE(ItemTraits::CheckCtorDtorCount());
789
790 END_TEST;
791 }
792
VectorTestImplicitConversion()793 bool VectorTestImplicitConversion() {
794 BEGIN_TEST;
795
796 {
797 fbl::Vector<fbl::String> v;
798 v.push_back(fbl::String("First"));
799 v.push_back("Second");
800 v.insert(2, fbl::String("Third"));
801 v.insert(3, "Fourth");
802
803 ASSERT_EQ(strcmp(v[0].c_str(), "First"), 0);
804 ASSERT_EQ(strcmp(v[1].c_str(), "Second"), 0);
805 ASSERT_EQ(strcmp(v[2].c_str(), "Third"), 0);
806 ASSERT_EQ(strcmp(v[3].c_str(), "Fourth"), 0);
807 }
808
809 {
810 fbl::Vector<fbl::String> v;
811 fbl::AllocChecker ac;
812 v.push_back(fbl::String("First"), &ac);
813 ASSERT_TRUE(ac.check());
814 v.push_back("Second", &ac);
815 ASSERT_TRUE(ac.check());
816 v.insert(2, fbl::String("Third"), &ac);
817 ASSERT_TRUE(ac.check());
818 v.insert(3, "Fourth", &ac);
819 ASSERT_TRUE(ac.check());
820
821 ASSERT_EQ(strcmp(v[0].c_str(), "First"), 0);
822 ASSERT_EQ(strcmp(v[1].c_str(), "Second"), 0);
823 ASSERT_EQ(strcmp(v[2].c_str(), "Third"), 0);
824 ASSERT_EQ(strcmp(v[3].c_str(), "Fourth"), 0);
825 }
826
827 END_TEST;
828 }
829
VectorGetConstness()830 bool VectorGetConstness() {
831 BEGIN_TEST;
832
833 fbl::Vector<int> vector_int;
834
835 auto& ref_vector_int = vector_int;
836 const auto& const_ref_vector_int = vector_int;
837
838 auto __UNUSED int_ptr = ref_vector_int.get();
839 auto __UNUSED const_int_ptr = const_ref_vector_int.get();
840
841 static_assert(!fbl::is_const<fbl::remove_pointer<decltype(int_ptr)>::type>::value, "");
842 static_assert(fbl::is_const<fbl::remove_pointer<decltype(const_int_ptr)>::type>::value, "");
843
844 END_TEST;
845 }
846
847 } // namespace
848
849 #define RUN_FOR_ALL_TRAITS(test_base, test_size) \
850 RUN_TEST((test_base<ValueTypeTraits, test_size>)) \
851 RUN_TEST((test_base<StructTypeTraits, test_size>)) \
852 RUN_TEST((test_base<UniquePtrTraits, test_size>)) \
853 RUN_TEST((test_base<RefPtrTraits, test_size>))
854
855 #define RUN_FOR_ALL(test_base) \
856 RUN_FOR_ALL_TRAITS(test_base, 1) \
857 RUN_FOR_ALL_TRAITS(test_base, 2) \
858 RUN_FOR_ALL_TRAITS(test_base, 10) \
859 RUN_FOR_ALL_TRAITS(test_base, 32) \
860 RUN_FOR_ALL_TRAITS(test_base, 64) \
861 RUN_FOR_ALL_TRAITS(test_base, 100)
862
863 BEGIN_TEST_CASE(vector_tests)
864 RUN_FOR_ALL(VectorTestAccessRelease)
865 RUN_FOR_ALL(VectorTestPushBackInCapacity)
866 RUN_TEST((VectorTestPushBackByConstRefInCapacity<ValueTypeTraits, 100>))
867 RUN_FOR_ALL(VectorTestPushBackBeyondCapacity)
868 RUN_TEST((VectorTestPushBackByConstRefBeyondCapacity<ValueTypeTraits, 100>))
869 RUN_FOR_ALL(VectorTestPopBack)
870 RUN_FOR_ALL(VectorTestAllocationFailure)
871 RUN_FOR_ALL(VectorTestMove)
872 RUN_FOR_ALL(VectorTestSwap)
873 RUN_FOR_ALL(VectorTestIterator)
874 RUN_FOR_ALL(VectorTestInsertDelete)
875 RUN_FOR_ALL(VectorTestNoAllocCheck)
876 RUN_TEST(VectorTestInitializerList<ValueTypeTraits>)
877 RUN_TEST(VectorTestInitializerList<RefPtrTraits>)
878 RUN_TEST(VectorTestImplicitConversion)
879 RUN_TEST(VectorGetConstness)
880 END_TEST_CASE(vector_tests)
881
882 } // namespace tests
883 } // namespace fbl
884