1 /*
2  * Copyright (C) 2016 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #include "gtest/gtest.h"
18 
19 #include "chre/util/dynamic_vector.h"
20 #include "chre/util/macros.h"
21 
22 #include <stdint.h>
23 
24 using chre::DynamicVector;
25 
26 namespace {
27 constexpr int kMaxTestCapacity = 10;
28 int gDestructorCount[kMaxTestCapacity];
29 
30 class Dummy {
31  public:
~Dummy()32   ~Dummy() {
33     if (mValue >= 0) {
34       gDestructorCount[mValue]++;
35     }
36   };
setValue(int value)37   void setValue(int value) {
38     mValue = value;
39   }
getValue()40   int getValue() {
41     return mValue;
42   }
43 
44  private:
45   int mValue = -1;
46 };
47 
resetDestructorCounts()48 void resetDestructorCounts() {
49   for (size_t i = 0; i < ARRAY_SIZE(gDestructorCount); i++) {
50     gDestructorCount[i] = 0;
51   }
52 }
53 }
54 
TEST(DynamicVector,EmptyByDefault)55 TEST(DynamicVector, EmptyByDefault) {
56   DynamicVector<int> vector;
57   EXPECT_EQ(vector.data(), nullptr);
58   EXPECT_TRUE(vector.empty());
59   EXPECT_EQ(vector.size(), 0);
60   EXPECT_EQ(vector.capacity(), 0);
61   vector.clear();
62 }
63 
TEST(DynamicVector,PushBackAndRead)64 TEST(DynamicVector, PushBackAndRead) {
65   DynamicVector<int> vector;
66   ASSERT_TRUE(vector.push_back(0x1337));
67   EXPECT_EQ(vector.size(), 1);
68   EXPECT_EQ(vector.capacity(), 1);
69   EXPECT_EQ(vector.data(), &vector[0]);
70   EXPECT_FALSE(vector.empty());
71   EXPECT_EQ(vector[0], 0x1337);
72 }
73 
TEST(DynamicVector,PushBackReserveAndReadTrivialType)74 TEST(DynamicVector, PushBackReserveAndReadTrivialType) {
75   DynamicVector<int> vector;
76   ASSERT_TRUE(vector.emplace_back(0x1337));
77   ASSERT_TRUE(vector.push_back(0xface));
78   int x = 0xcafe;
79   ASSERT_TRUE(vector.push_back(std::move(x)));
80   ASSERT_TRUE(vector.insert(vector.size(), 0xd00d));
81   EXPECT_EQ(vector.size(), 4);
82   EXPECT_EQ(vector.capacity(), 4);
83   EXPECT_EQ(vector[0], 0x1337);
84   EXPECT_EQ(vector[1], 0xface);
85   EXPECT_EQ(vector[2], 0xcafe);
86   EXPECT_EQ(vector[3], 0xd00d);
87 
88   ASSERT_TRUE(vector.reserve(8));
89   EXPECT_EQ(vector.size(), 4);
90   EXPECT_EQ(vector.capacity(), 8);
91   EXPECT_EQ(vector[0], 0x1337);
92   EXPECT_EQ(vector[1], 0xface);
93   EXPECT_EQ(vector[2], 0xcafe);
94   EXPECT_EQ(vector[3], 0xd00d);
95 }
96 
97 constexpr int kConstructedMagic = 0xdeadbeef;
98 
99 class MovableButNonCopyable : public chre::NonCopyable {
100  public:
MovableButNonCopyable(int value)101   MovableButNonCopyable(int value) : mValue(value) {}
102 
MovableButNonCopyable(MovableButNonCopyable && other)103   MovableButNonCopyable(MovableButNonCopyable&& other) {
104     mValue = other.mValue;
105     other.mValue = -1;
106   }
107 
operator =(MovableButNonCopyable && other)108   MovableButNonCopyable& operator=(MovableButNonCopyable&& other) {
109     assert(mMagic == kConstructedMagic);
110     mValue = other.mValue;
111     other.mValue = -1;
112     return *this;
113   }
114 
getValue() const115   int getValue() const {
116     return mValue;
117   }
118 
119  private:
120   int mMagic = kConstructedMagic;
121   int mValue;
122 };
123 
TEST(DynamicVector,PushBackReserveAndReadMovableButNonCopyable)124 TEST(DynamicVector, PushBackReserveAndReadMovableButNonCopyable) {
125   DynamicVector<MovableButNonCopyable> vector;
126   ASSERT_TRUE(vector.emplace_back(0x1337));
127   ASSERT_TRUE(vector.emplace_back(0xface));
128   MovableButNonCopyable mbnc(0xcafe);
129   ASSERT_TRUE(vector.push_back(std::move(mbnc)));
130   EXPECT_EQ(mbnc.getValue(), -1);
131   MovableButNonCopyable mbnc2(0xd00d);
132   ASSERT_TRUE(vector.insert(vector.size(), std::move(mbnc2)));
133   EXPECT_EQ(mbnc2.getValue(), -1);
134 
135   ASSERT_TRUE(vector.reserve(8));
136   EXPECT_EQ(vector[0].getValue(), 0x1337);
137   EXPECT_EQ(vector[1].getValue(), 0xface);
138   EXPECT_EQ(vector[2].getValue(), 0xcafe);
139   EXPECT_EQ(vector[3].getValue(), 0xd00d);
140   EXPECT_EQ(vector.size(), 4);
141   EXPECT_EQ(vector.capacity(), 8);
142 }
143 
144 class CopyableButNonMovable {
145  public:
CopyableButNonMovable(int value)146   CopyableButNonMovable(int value) : mValue(value) {}
147 
CopyableButNonMovable(const CopyableButNonMovable & other)148   CopyableButNonMovable(const CopyableButNonMovable& other) {
149     mValue = other.mValue;
150   }
151 
operator =(const CopyableButNonMovable & other)152   CopyableButNonMovable& operator=(const CopyableButNonMovable& other) {
153     assert(mMagic == kConstructedMagic);
154     mValue = other.mValue;
155     return *this;
156   }
157 
158   CopyableButNonMovable(CopyableButNonMovable&& other) = delete;
159   CopyableButNonMovable& operator=(CopyableButNonMovable&& other) = delete;
160 
getValue() const161   int getValue() const {
162     return mValue;
163   }
164 
165  private:
166   int mMagic = kConstructedMagic;
167   int mValue;
168 };
169 
TEST(DynamicVector,PushBackReserveAndReadCopyableButNonMovable)170 TEST(DynamicVector, PushBackReserveAndReadCopyableButNonMovable) {
171   DynamicVector<CopyableButNonMovable> vector;
172   ASSERT_TRUE(vector.emplace_back(0x1337));
173   ASSERT_TRUE(vector.emplace_back(0xface));
174   CopyableButNonMovable cbnm(0xcafe);
175   ASSERT_TRUE(vector.push_back(cbnm));
176   CopyableButNonMovable cbnm2(0xd00d);
177   ASSERT_TRUE(vector.insert(vector.size(), cbnm2));
178 
179   ASSERT_TRUE(vector.reserve(8));
180   EXPECT_EQ(vector[0].getValue(), 0x1337);
181   EXPECT_EQ(vector[1].getValue(), 0xface);
182   EXPECT_EQ(vector[2].getValue(), 0xcafe);
183   EXPECT_EQ(vector[3].getValue(), 0xd00d);
184   EXPECT_EQ(vector.size(), 4);
185   EXPECT_EQ(vector.capacity(), 8);
186 }
187 
188 class MovableAndCopyable {
189  public:
MovableAndCopyable(int value)190   MovableAndCopyable(int value) : mValue(value) {}
191 
MovableAndCopyable(const MovableAndCopyable & other)192   MovableAndCopyable(const MovableAndCopyable& other) {
193     mValue = other.mValue;
194   }
195 
MovableAndCopyable(MovableAndCopyable && other)196   MovableAndCopyable(MovableAndCopyable&& other) {
197     // The move constructor multiplies the value by 2 so that we can see that it
198     // was used
199     mValue = other.mValue * 2;
200   }
201 
operator =(const MovableAndCopyable & other)202   MovableAndCopyable& operator=(const MovableAndCopyable& other) {
203     assert(mMagic == kConstructedMagic);
204     mValue = other.mValue;
205     return *this;
206   }
207 
operator =(MovableAndCopyable && other)208   MovableAndCopyable& operator=(MovableAndCopyable&& other) {
209     assert(mMagic == kConstructedMagic);
210     mValue = other.mValue * 2;
211     other.mValue = -1;
212     return *this;
213   }
214 
getValue() const215   int getValue() const {
216     return mValue;
217   }
218 
219  private:
220   int mMagic = kConstructedMagic;
221   int mValue;
222 };
223 
TEST(DynamicVector,ReservePrefersMove)224 TEST(DynamicVector, ReservePrefersMove) {
225   // Ensure that preference is given to std::move in reserve()
226   DynamicVector<MovableAndCopyable> vector;
227 
228   // Reserve enough space for the first two elements.
229   ASSERT_TRUE(vector.reserve(2));
230   ASSERT_TRUE(vector.emplace_back(1000));
231   ASSERT_TRUE(vector.emplace_back(2000));
232 
233   // Reserve more than enough space causing a move to be required.
234   ASSERT_TRUE(vector.reserve(4));
235 
236   // Move on this type results in a multiplication by 2. Verify that all
237   // elements have been multiplied by 2.
238   EXPECT_EQ(vector[0].getValue(), 2000);
239   EXPECT_EQ(vector[1].getValue(), 4000);
240 }
241 
242 /**
243  * A simple test helper object to count number of construction and destructions.
244  */
245 class Foo {
246  public:
247   /**
248    * Construct an object storing a simple integer. Increment the number of
249    * objects that have been constructed of this type.
250    */
Foo(int value)251   Foo(int value) : value(value) {
252     sConstructedCounter++;
253   }
254 
Foo(const Foo & other)255   Foo(const Foo& other) {
256     value = other.value;
257     sConstructedCounter++;
258   }
259 
260   Foo(Foo&& other) = delete;
261 
262   /**
263    * Tear down the object, decrementing the number of objects that have been
264    * constructed of this type.
265    */
~Foo()266   ~Foo() {
267     sConstructedCounter--;
268   }
269 
270   //! The number of objects of this type that have been constructed.
271   static ssize_t sConstructedCounter;
272 
273   //! The value stored in the object to verify the contents of this object after
274   //! construction.
275   int value;
276 };
277 
278 //! Storage for the Foo reference counter.
279 ssize_t Foo::sConstructedCounter = 0;
280 
TEST(DynamicVector,EmplaceBackAndDestruct)281 TEST(DynamicVector, EmplaceBackAndDestruct) {
282   Foo::sConstructedCounter = 0;
283   {
284     DynamicVector<Foo> vector;
285     ASSERT_TRUE(vector.emplace_back(1000));
286     ASSERT_TRUE(vector.emplace_back(2000));
287     ASSERT_TRUE(vector.emplace_back(3000));
288     ASSERT_TRUE(vector.emplace_back(4000));
289 
290     ASSERT_EQ(vector[0].value, 1000);
291     ASSERT_EQ(vector[1].value, 2000);
292     ASSERT_EQ(vector[2].value, 3000);
293     ASSERT_EQ(vector[3].value, 4000);
294 
295     EXPECT_EQ(Foo::sConstructedCounter, 4);
296   }
297 
298   EXPECT_EQ(Foo::sConstructedCounter, 0);
299 }
300 
TEST(DynamicVector,InsertEmpty)301 TEST(DynamicVector, InsertEmpty) {
302   DynamicVector<int> vector;
303   EXPECT_CHRE_ASSERT(EXPECT_FALSE(vector.insert(1, 0x1337)));
304 
305   // Insert to empty vector
306   ASSERT_TRUE(vector.insert(0, 0x1337));
307   EXPECT_EQ(vector[0], 0x1337);
308 
309   // Insert at end triggering grow
310   ASSERT_EQ(vector.capacity(), 1);
311   EXPECT_TRUE(vector.insert(1, 0xface));
312   EXPECT_EQ(vector[0], 0x1337);
313   EXPECT_EQ(vector[1], 0xface);
314 
315   // Insert at beginning triggering grow
316   ASSERT_EQ(vector.capacity(), 2);
317   EXPECT_TRUE(vector.insert(0, 0xcafe));
318   EXPECT_EQ(vector[0], 0xcafe);
319   EXPECT_EQ(vector[1], 0x1337);
320   EXPECT_EQ(vector[2], 0xface);
321 
322   // Insert at middle with spare capacity
323   ASSERT_EQ(vector.capacity(), 4);
324   EXPECT_TRUE(vector.insert(1, 0xdead));
325   EXPECT_EQ(vector[0], 0xcafe);
326   EXPECT_EQ(vector[1], 0xdead);
327   EXPECT_EQ(vector[2], 0x1337);
328   EXPECT_EQ(vector[3], 0xface);
329 
330   // Insert at middle triggering grow
331   ASSERT_EQ(vector.capacity(), 4);
332   EXPECT_TRUE(vector.insert(2, 0xbeef));
333   EXPECT_EQ(vector[0], 0xcafe);
334   EXPECT_EQ(vector[1], 0xdead);
335   EXPECT_EQ(vector[2], 0xbeef);
336   EXPECT_EQ(vector[3], 0x1337);
337   EXPECT_EQ(vector[4], 0xface);
338 
339   // Insert at beginning with spare capacity
340   ASSERT_EQ(vector.capacity(), 8);
341   ASSERT_EQ(vector.size(), 5);
342   EXPECT_TRUE(vector.insert(0, 0xabad));
343   EXPECT_EQ(vector[0], 0xabad);
344   EXPECT_EQ(vector[1], 0xcafe);
345   EXPECT_EQ(vector[2], 0xdead);
346   EXPECT_EQ(vector[3], 0xbeef);
347   EXPECT_EQ(vector[4], 0x1337);
348   EXPECT_EQ(vector[5], 0xface);
349 
350   // Insert at end with spare capacity
351   ASSERT_EQ(vector.size(), 6);
352   EXPECT_TRUE(vector.insert(vector.size(), 0xc0de));
353   EXPECT_EQ(vector[0], 0xabad);
354   EXPECT_EQ(vector[1], 0xcafe);
355   EXPECT_EQ(vector[2], 0xdead);
356   EXPECT_EQ(vector[3], 0xbeef);
357   EXPECT_EQ(vector[4], 0x1337);
358   EXPECT_EQ(vector[5], 0xface);
359   EXPECT_EQ(vector[6], 0xc0de);
360 }
361 
TEST(DynamicVector,PushBackInsertInMiddleAndRead)362 TEST(DynamicVector, PushBackInsertInMiddleAndRead) {
363   DynamicVector<int> vector;
364   ASSERT_TRUE(vector.push_back(0x1337));
365   ASSERT_TRUE(vector.push_back(0xface));
366   ASSERT_TRUE(vector.push_back(0xcafe));
367   ASSERT_TRUE(vector.insert(1, 0xbeef));
368 
369   ASSERT_EQ(vector[0], 0x1337);
370   ASSERT_EQ(vector[1], 0xbeef);
371   ASSERT_EQ(vector[2], 0xface);
372   ASSERT_EQ(vector[3], 0xcafe);
373 }
374 
TEST(DynamicVector,PushBackAndErase)375 TEST(DynamicVector, PushBackAndErase) {
376   DynamicVector<int> vector;
377   ASSERT_TRUE(vector.push_back(0x1337));
378   ASSERT_TRUE(vector.push_back(0xcafe));
379   ASSERT_TRUE(vector.push_back(0xbeef));
380   ASSERT_TRUE(vector.push_back(0xface));
381 
382   vector.erase(1);
383 
384   ASSERT_EQ(vector[0], 0x1337);
385   ASSERT_EQ(vector[1], 0xbeef);
386   ASSERT_EQ(vector[2], 0xface);
387   ASSERT_EQ(vector.size(), 3);
388 }
389 
TEST(DynamicVector,FindEmpty)390 TEST(DynamicVector, FindEmpty) {
391   DynamicVector<int> vector;
392   ASSERT_EQ(vector.find(0), 0);
393 }
394 
TEST(DynamicVector,FindWithElements)395 TEST(DynamicVector, FindWithElements) {
396   DynamicVector<int> vector;
397   ASSERT_TRUE(vector.push_back(0x1337));
398   ASSERT_TRUE(vector.push_back(0xcafe));
399   ASSERT_TRUE(vector.push_back(0xbeef));
400 
401   ASSERT_EQ(vector.find(0x1337), 0);
402   ASSERT_EQ(vector.find(0xcafe), 1);
403   ASSERT_EQ(vector.find(0xbeef), 2);
404   ASSERT_EQ(vector.find(1000), 3);
405 }
406 
TEST(DynamicVector,EraseDestructorCalled)407 TEST(DynamicVector, EraseDestructorCalled) {
408   resetDestructorCounts();
409 
410   DynamicVector<Dummy> vector;
411   vector.reserve(4);
412   for (size_t i = 0; i < 4; ++i) {
413     vector.emplace_back();
414     vector[i].setValue(i);
415   }
416 
417   // last item before erase is '3'.
418   vector.erase(1);
419   EXPECT_EQ(0, gDestructorCount[0]);
420   EXPECT_EQ(0, gDestructorCount[1]);
421   EXPECT_EQ(0, gDestructorCount[2]);
422   EXPECT_EQ(1, gDestructorCount[3]);
423 
424   // last item before erase is still '3'.
425   vector.erase(2);
426   EXPECT_EQ(0, gDestructorCount[0]);
427   EXPECT_EQ(0, gDestructorCount[1]);
428   EXPECT_EQ(0, gDestructorCount[2]);
429   EXPECT_EQ(2, gDestructorCount[3]);
430 
431   // last item before erase is now '2'.
432   vector.erase(0);
433   EXPECT_EQ(0, gDestructorCount[0]);
434   EXPECT_EQ(0, gDestructorCount[1]);
435   EXPECT_EQ(1, gDestructorCount[2]);
436   EXPECT_EQ(2, gDestructorCount[3]);
437 }
438 
TEST(DynamicVector,Clear)439 TEST(DynamicVector, Clear) {
440   resetDestructorCounts();
441 
442   DynamicVector<Dummy> vector;
443   vector.reserve(4);
444   for (size_t i = 0; i < 4; ++i) {
445     vector.emplace_back();
446     vector[i].setValue(i);
447   }
448 
449   vector.clear();
450   EXPECT_EQ(vector.size(), 0);
451   EXPECT_EQ(vector.capacity(), 4);
452 
453   for (size_t i = 0; i < 4; ++i) {
454     EXPECT_EQ(gDestructorCount[i], 1);
455   }
456 }
457 
458 // Make sure that a vector wrapping an array doesn't call the destructor when
459 // the vector is destructed
TEST(DynamicVector,WrapDoesntCallDestructor)460 TEST(DynamicVector, WrapDoesntCallDestructor) {
461   resetDestructorCounts();
462 
463   Dummy array[4];
464   for (size_t i = 0; i < 4; ++i) {
465     array[i].setValue(i);
466   }
467 
468   {
469     DynamicVector<Dummy> vector;
470     vector.wrap(array, ARRAY_SIZE(array));
471   }
472 
473   for (size_t i = 0; i < 4; ++i) {
474     EXPECT_EQ(gDestructorCount[i], 0);
475   }
476 }
477 
478 // Make sure that a wrapped vector does call the destructor when it's expected
479 // as part of an API call
TEST(DynamicVector,WrapExplicitlyCallsDestructor)480 TEST(DynamicVector, WrapExplicitlyCallsDestructor) {
481   resetDestructorCounts();
482 
483   Dummy array[4];
484   constexpr size_t kSize = ARRAY_SIZE(array);
485   static_assert(ARRAY_SIZE(array) <= ARRAY_SIZE(gDestructorCount),
486                 "gDestructorCount array must fit test array");
487   for (size_t i = 0; i < kSize; ++i) {
488     array[i].setValue(i);
489   }
490   DynamicVector<Dummy> vector;
491   vector.wrap(array, ARRAY_SIZE(array));
492 
493   vector.erase(kSize - 1);
494   for (size_t i = 0; i < kSize - 1; i++) {
495     EXPECT_EQ(gDestructorCount[i], 0);
496   }
497   EXPECT_EQ(gDestructorCount[kSize - 1], 1);
498 
499   vector.clear();
500   for (size_t i = 0; i < kSize; ++i) {
501     EXPECT_EQ(gDestructorCount[i], 1);
502   }
503 }
504 
TEST(DynamicVectorDeathTest,SwapWithInvalidIndex)505 TEST(DynamicVectorDeathTest, SwapWithInvalidIndex) {
506   DynamicVector<int> vector;
507   vector.push_back(0x1337);
508   vector.push_back(0xcafe);
509   EXPECT_DEATH(vector.swap(0, 2), "");
510 }
511 
TEST(DynamicVectorDeathTest,SwapWithInvalidIndices)512 TEST(DynamicVectorDeathTest, SwapWithInvalidIndices) {
513   DynamicVector<int> vector;
514   vector.push_back(0x1337);
515   vector.push_back(0xcafe);
516   EXPECT_DEATH(vector.swap(2, 3), "");
517 }
518 
TEST(DynamicVector,Swap)519 TEST(DynamicVector, Swap) {
520   DynamicVector<int> vector;
521   vector.push_back(0x1337);
522   vector.push_back(0xcafe);
523 
524   vector.swap(0, 1);
525   EXPECT_EQ(vector[0], 0xcafe);
526   EXPECT_EQ(vector[1], 0x1337);
527 }
528 
TEST(DynamicVector,BackFront)529 TEST(DynamicVector, BackFront) {
530   DynamicVector<int> vector;
531   vector.push_back(0x1337);
532   EXPECT_EQ(vector.front(), 0x1337);
533   EXPECT_EQ(vector.back(), 0x1337);
534   vector.push_back(0xcafe);
535   EXPECT_EQ(vector.front(), 0x1337);
536   EXPECT_EQ(vector.back(), 0xcafe);
537   vector.erase(0);
538   EXPECT_EQ(vector.front(), 0xcafe);
539   EXPECT_EQ(vector.back(), 0xcafe);
540 }
541 
TEST(DynamicVector,Iterator)542 TEST(DynamicVector, Iterator) {
543   DynamicVector<int> vector;
544   vector.push_back(0);
545   vector.push_back(1);
546   vector.push_back(2);
547 
548   size_t index = 0;
549   for (DynamicVector<int>::iterator it = vector.begin();
550        it != vector.end(); ++it) {
551     EXPECT_EQ(vector[index++], *it);
552   }
553 
554   DynamicVector<int>::iterator it = vector.begin() + vector.size() - 1;
555   EXPECT_EQ(vector[vector.size() - 1], *it);
556 
557   it = vector.begin() + vector.size();
558   EXPECT_TRUE(it == vector.end());
559 }
560 
TEST(DynamicVector,ConstIterator)561 TEST(DynamicVector, ConstIterator) {
562   DynamicVector<int> vector;
563   vector.push_back(0);
564   vector.push_back(1);
565   vector.push_back(2);
566 
567   size_t index = 0;
568   for (DynamicVector<int>::const_iterator cit = vector.cbegin();
569        cit != vector.cend(); ++cit) {
570     EXPECT_EQ(vector[index++], *cit);
571   }
572 
573   DynamicVector<int>::const_iterator cit = vector.cbegin() + vector.size() - 1;
574   EXPECT_EQ(vector[vector.size() - 1], *cit);
575 
576   cit = vector.cbegin() + vector.size();
577   EXPECT_TRUE(cit == vector.cend());
578 }
579 
TEST(DynamicVector,IteratorAndPushBack)580 TEST(DynamicVector, IteratorAndPushBack) {
581   DynamicVector<int> vector;
582   vector.push_back(0);
583   vector.push_back(1);
584   vector.push_back(2);
585   size_t oldCapacity = vector.capacity();
586 
587   DynamicVector<int>::iterator it_b = vector.begin();
588   DynamicVector<int>::iterator it_e = vector.end();
589 
590   vector.push_back(3);
591   ASSERT_TRUE(oldCapacity == vector.capacity());
592 
593   size_t index = 0;
594   for (; it_b != it_e; ++it_b) {
595     EXPECT_EQ(vector[index++], *it_b);
596   }
597 }
598 
TEST(DynamicVector,IteratorAndEmplaceBack)599 TEST(DynamicVector, IteratorAndEmplaceBack) {
600   DynamicVector<int> vector;
601   vector.push_back(0);
602   vector.push_back(1);
603   vector.push_back(2);
604   size_t oldCapacity = vector.capacity();
605 
606   DynamicVector<int>::iterator it_b = vector.begin();
607   DynamicVector<int>::iterator it_e = vector.end();
608 
609   vector.emplace_back(3);
610   ASSERT_TRUE(oldCapacity == vector.capacity());
611 
612   size_t index = 0;
613   for (; it_b != it_e; ++it_b) {
614     EXPECT_EQ(vector[index++], *it_b);
615   }
616 }
617 
TEST(DynamicVector,IteratorAndReserve)618 TEST(DynamicVector, IteratorAndReserve) {
619   DynamicVector<int> vector;
620   vector.push_back(0);
621   vector.push_back(1);
622   vector.push_back(2);
623   size_t oldCapacity = vector.capacity();
624 
625   DynamicVector<int>::iterator it_b = vector.begin();
626   DynamicVector<int>::iterator it_e = vector.end();
627 
628   vector.reserve(oldCapacity);
629   ASSERT_TRUE(oldCapacity == vector.capacity());
630 
631   size_t index = 0;
632   for (; it_b != it_e; ++it_b) {
633     EXPECT_EQ(vector[index++], *it_b);
634   }
635 }
636 
TEST(DynamicVector,IteratorAndInsert)637 TEST(DynamicVector, IteratorAndInsert) {
638   DynamicVector<int> vector;
639   vector.push_back(0);
640   vector.push_back(1);
641   vector.push_back(2);
642   size_t oldCapacity = vector.capacity();
643 
644   DynamicVector<int>::iterator it_b = vector.begin();
645 
646   vector.insert(2, 3);
647   ASSERT_TRUE(oldCapacity == vector.capacity());
648 
649   size_t index = 0;
650   while (index < 2) {
651     EXPECT_EQ(vector[index++], *it_b++);
652   }
653 }
654 
TEST(DynamicVector,IteratorAndErase)655 TEST(DynamicVector, IteratorAndErase) {
656   DynamicVector<int> vector;
657   vector.push_back(0);
658   vector.push_back(1);
659   vector.push_back(2);
660 
661   DynamicVector<int>::iterator it_b = vector.begin();
662 
663   vector.erase(2);
664 
665   size_t index = 0;
666   while (index < 2) {
667     EXPECT_EQ(vector[index++], *it_b++);
668   }
669 }
670 
TEST(DynamicVector,IteratorAndSwap)671 TEST(DynamicVector, IteratorAndSwap) {
672   DynamicVector<int> vector;
673   vector.push_back(0);
674   vector.push_back(1);
675   vector.push_back(2);
676   vector.push_back(3);
677 
678   DynamicVector<int>::iterator it_b = vector.begin();
679 
680   vector.swap(1, 3);
681 
682   size_t index = 0;
683   while (index < 4) {
684     if (index != 1 && index != 3) {
685       EXPECT_EQ(vector[index], *it_b);
686     }
687     index++;
688     it_b++;
689   }
690 }
691 
TEST(DynamicVector,MoveConstruct)692 TEST(DynamicVector, MoveConstruct) {
693   DynamicVector<int> vector;
694   ASSERT_TRUE(vector.push_back(0));
695   ASSERT_TRUE(vector.push_back(1));
696   ASSERT_TRUE(vector.push_back(2));
697 
698   DynamicVector<int> movedVector(std::move(vector));
699   EXPECT_EQ(vector.data(), nullptr);
700   EXPECT_NE(movedVector.data(), nullptr);
701   EXPECT_EQ(vector.size(), 0);
702   EXPECT_EQ(movedVector.size(), 3);
703   EXPECT_EQ(vector.capacity(), 0);
704   EXPECT_EQ(movedVector.capacity(), 4);
705 }
706 
707 // Tests basic functionality of a vector wrapping an array
TEST(DynamicVector,Wrap)708 TEST(DynamicVector, Wrap) {
709   constexpr size_t kSize = 4;
710   int buf[kSize];
711   for (size_t i = 0; i < kSize; i++) {
712     buf[i] = i;
713   }
714 
715   DynamicVector<int> vector;
716   EXPECT_TRUE(vector.owns_data());
717   vector.wrap(buf, kSize);
718   EXPECT_FALSE(vector.owns_data());
719   EXPECT_EQ(vector.size(), kSize);
720   EXPECT_EQ(vector.capacity(), kSize);
721   EXPECT_EQ(vector.data(), buf);
722 
723   EXPECT_CHRE_ASSERT(EXPECT_FALSE(vector.reserve(8)));
724   EXPECT_CHRE_ASSERT(EXPECT_FALSE(vector.push_back(-1)));
725   EXPECT_CHRE_ASSERT(EXPECT_FALSE(vector.emplace_back(-1)));
726   EXPECT_CHRE_ASSERT(EXPECT_FALSE(vector.insert(1, -1)));
727   EXPECT_CHRE_ASSERT(EXPECT_FALSE(vector.copy_array(buf, kSize)));
728 
729   for (size_t i = 0; i < kSize; i++) {
730     EXPECT_EQ(vector[i], i);
731   }
732 
733   vector.erase(0);
734   for (size_t i = 0; i < kSize - 1; i++) {
735     EXPECT_EQ(vector[i], i + 1);
736   }
737 
738   EXPECT_TRUE(vector.push_back(kSize + 1));
739   EXPECT_EQ(vector.back(), kSize + 1);
740 }
741 
TEST(DynamicVector,MoveWrappedVector)742 TEST(DynamicVector, MoveWrappedVector) {
743   constexpr size_t kSize = 4;
744   int buf[kSize];
745   for (size_t i = 0; i < kSize; i++) {
746     buf[i] = i;
747   }
748 
749   DynamicVector<int> vector1;
750   vector1.wrap(buf, kSize);
751 
752   DynamicVector<int> vector2 = std::move(vector1);
753   EXPECT_TRUE(vector1.owns_data());
754   EXPECT_EQ(vector1.size(), 0);
755   EXPECT_EQ(vector1.capacity(), 0);
756   EXPECT_EQ(vector1.data(), nullptr);
757 
758   EXPECT_FALSE(vector2.owns_data());
759   EXPECT_EQ(vector2.size(), kSize);
760   EXPECT_EQ(vector2.capacity(), kSize);
761   EXPECT_EQ(vector2.data(), buf);
762 }
763 
TEST(DynamicVector,Unwrap)764 TEST(DynamicVector, Unwrap) {
765   constexpr size_t kSize = 4;
766   int buf[kSize];
767   for (size_t i = 0; i < kSize; i++) {
768     buf[i] = i;
769   }
770 
771   DynamicVector<int> vec;
772   vec.wrap(buf, kSize);
773   ASSERT_FALSE(vec.owns_data());
774 
775   vec.unwrap();
776   EXPECT_TRUE(vec.owns_data());
777   EXPECT_EQ(vec.size(), 0);
778   EXPECT_EQ(vec.capacity(), 0);
779   EXPECT_EQ(vec.data(), nullptr);
780 
781   EXPECT_TRUE(vec.push_back(1));
782 }
783 
TEST(DynamicVector,CopyArray)784 TEST(DynamicVector, CopyArray) {
785   constexpr size_t kSize = 4;
786   int buf[kSize];
787   for (size_t i = 0; i < kSize; i++) {
788     buf[i] = i;
789   }
790 
791   DynamicVector<int> vec;
792   ASSERT_TRUE(vec.copy_array(buf, kSize));
793   EXPECT_TRUE(vec.owns_data());
794 
795   EXPECT_EQ(vec.size(), kSize);
796   EXPECT_EQ(vec.capacity(), kSize);
797   EXPECT_NE(vec.data(), buf);
798 
799   EXPECT_TRUE(vec.push_back(kSize));
800   EXPECT_EQ(vec.size(), kSize + 1);
801   EXPECT_GE(vec.capacity(), kSize + 1);
802 
803   for (size_t i = 0; i < kSize + 1; i++) {
804     EXPECT_EQ(vec[i], i);
805   }
806 }
807 
TEST(DynamicVector,CopyArrayHandlesDestructor)808 TEST(DynamicVector, CopyArrayHandlesDestructor) {
809   resetDestructorCounts();
810   constexpr size_t kSize = 4;
811 
812   {
813     DynamicVector<Dummy> vec;
814     {
815       Dummy array[kSize];
816       for (size_t i = 0; i < kSize; i++) {
817         array[i].setValue(i);
818       }
819 
820       ASSERT_TRUE(vec.copy_array(array, kSize));
821     }
822 
823     for (size_t i = 0; i < kSize; i++) {
824       EXPECT_EQ(gDestructorCount[i], 1);
825     }
826 
827     for (size_t i = 0; i < kSize; i++) {
828       ASSERT_TRUE(vec[i].getValue() == i);
829     }
830   }
831 
832   for (size_t i = 0; i < kSize; i++) {
833     EXPECT_EQ(gDestructorCount[i], 2);
834   }
835 }
836 
TEST(DynamicVector,CopyEmptyArray)837 TEST(DynamicVector, CopyEmptyArray) {
838   DynamicVector<int> vec;
839 
840   EXPECT_TRUE(vec.copy_array(nullptr, 0));
841   EXPECT_EQ(vec.size(), 0);
842 
843   vec.emplace_back(1);
844   EXPECT_TRUE(vec.copy_array(nullptr, 0));
845   EXPECT_EQ(vec.size(), 0);
846 }
847 
TEST(DynamicVector,PrepareForPush)848 TEST(DynamicVector, PrepareForPush) {
849   DynamicVector<int> vector;
850   EXPECT_EQ(vector.size(), 0);
851   EXPECT_EQ(vector.capacity(), 0);
852 
853   // Perform an initial prepareForPush operation which causes a size of one.
854   ASSERT_TRUE(vector.prepareForPush());
855   EXPECT_EQ(vector.size(), 0);
856   EXPECT_EQ(vector.capacity(), 1);
857   ASSERT_TRUE(vector.push_back(0xcafe));
858   EXPECT_EQ(vector.size(), 1);
859   EXPECT_EQ(vector.capacity(), 1);
860 
861   // Verify that it becomes larger
862   ASSERT_TRUE(vector.prepareForPush());
863   EXPECT_EQ(vector[0], 0xcafe);
864   EXPECT_EQ(vector.size(), 1);
865   EXPECT_EQ(vector.capacity(), 2);
866 
867   // The vector should not become any larger than necessary.
868   ASSERT_TRUE(vector.prepareForPush());
869   EXPECT_EQ(vector[0], 0xcafe);
870   EXPECT_EQ(vector.size(), 1);
871   EXPECT_EQ(vector.capacity(), 2);
872 }
873 
TEST(DynamicVector,RidiculouslyHugeReserveFails)874 TEST(DynamicVector, RidiculouslyHugeReserveFails) {
875   DynamicVector<int> vector;
876   ASSERT_FALSE(vector.reserve(SIZE_MAX));
877 }
878