dynamic_vector_test.cc revision 8be5eabe6a4fc60c56a3b32794bb6677e26f6eab 
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
24using chre::DynamicVector;
25
26namespace {
27constexpr int kMaxTestCapacity = 10;
28int gDestructorCount[kMaxTestCapacity];
29
30class Dummy {
31 public:
32  ~Dummy() {
33    if (mValue >= 0) {
34      gDestructorCount[mValue]++;
35    }
36  };
37  void setValue(int value) {
38    mValue = value;
39  }
40  int getValue() {
41    return mValue;
42  }
43
44 private:
45  int mValue = -1;
46};
47
48void resetDestructorCounts() {
49  for (size_t i = 0; i < ARRAY_SIZE(gDestructorCount); i++) {
50    gDestructorCount[i] = 0;
51  }
52}
53}
54
55TEST(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
64TEST(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
74TEST(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
97constexpr int kConstructedMagic = 0xdeadbeef;
98
99class MovableButNonCopyable : public chre::NonCopyable {
100 public:
101  MovableButNonCopyable(int value) : mValue(value) {}
102
103  MovableButNonCopyable(MovableButNonCopyable&& other) {
104    mValue = other.mValue;
105    other.mValue = -1;
106  }
107
108  MovableButNonCopyable& operator=(MovableButNonCopyable&& other) {
109    assert(mMagic == kConstructedMagic);
110    mValue = other.mValue;
111    other.mValue = -1;
112    return *this;
113  }
114
115  int getValue() const {
116    return mValue;
117  }
118
119 private:
120  int mMagic = kConstructedMagic;
121  int mValue;
122};
123
124TEST(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
144class CopyableButNonMovable {
145 public:
146  CopyableButNonMovable(int value) : mValue(value) {}
147
148  CopyableButNonMovable(const CopyableButNonMovable& other) {
149    mValue = other.mValue;
150  }
151
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
161  int getValue() const {
162    return mValue;
163  }
164
165 private:
166  int mMagic = kConstructedMagic;
167  int mValue;
168};
169
170TEST(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
188class MovableAndCopyable {
189 public:
190  MovableAndCopyable(int value) : mValue(value) {}
191
192  MovableAndCopyable(const MovableAndCopyable& other) {
193    mValue = other.mValue;
194  }
195
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
202  MovableAndCopyable& operator=(const MovableAndCopyable& other) {
203    assert(mMagic == kConstructedMagic);
204    mValue = other.mValue;
205    return *this;
206  }
207
208  MovableAndCopyable& operator=(MovableAndCopyable&& other) {
209    assert(mMagic == kConstructedMagic);
210    mValue = other.mValue * 2;
211    other.mValue = -1;
212    return *this;
213  }
214
215  int getValue() const {
216    return mValue;
217  }
218
219 private:
220  int mMagic = kConstructedMagic;
221  int mValue;
222};
223
224TEST(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 */
245class 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   */
251  Foo(int value) : value(value) {
252    sConstructedCounter++;
253  }
254
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   */
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.
279ssize_t Foo::sConstructedCounter = 0;
280
281TEST(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
301TEST(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
362TEST(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
375TEST(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
390TEST(DynamicVector, FindEmpty) {
391  DynamicVector<int> vector;
392  ASSERT_EQ(vector.find(0), 0);
393}
394
395TEST(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
407TEST(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
439TEST(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
460TEST(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
480TEST(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
505TEST(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
512TEST(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
519TEST(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
529TEST(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
542TEST(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
561TEST(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
580TEST(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
599TEST(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
618TEST(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
637TEST(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
655TEST(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
671TEST(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
692TEST(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
708TEST(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
742TEST(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
764TEST(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
784TEST(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
808TEST(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
837TEST(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
848TEST(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
874TEST(DynamicVector, RidiculouslyHugeReserveFails) {
875  DynamicVector<int> vector;
876  ASSERT_FALSE(vector.reserve(SIZE_MAX));
877}
878