dynamic_vector_test.cc revision 83be94436ec4d35296e00da877c7198f67b6af44 
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/array.h"
20#include "chre/util/dynamic_vector.h"
21
22using chre::DynamicVector;
23
24namespace {
25constexpr int kMaxTestCapacity = 10;
26int gDestructorCount[kMaxTestCapacity];
27
28class Dummy {
29 public:
30  ~Dummy() {
31    if (mValue >= 0) {
32      gDestructorCount[mValue]++;
33    }
34  };
35  void setValue(int value) {
36    mValue = value;
37  }
38
39 private:
40  int mValue = -1;
41};
42
43void resetDestructorCounts() {
44  for (size_t i = 0; i < ARRAY_SIZE(gDestructorCount); i++) {
45    gDestructorCount[i] = 0;
46  }
47}
48}
49
50TEST(DynamicVector, EmptyByDefault) {
51  DynamicVector<int> vector;
52  ASSERT_EQ(vector.data(), nullptr);
53  ASSERT_EQ(vector.size(), 0);
54  ASSERT_EQ(vector.capacity(), 0);
55}
56
57TEST(DynamicVector, PushBackAndRead) {
58  DynamicVector<int> vector;
59  ASSERT_TRUE(vector.push_back(0x1337));
60  ASSERT_EQ(vector[0], 0x1337);
61  ASSERT_EQ(vector.data()[0], 0x1337);
62}
63
64TEST(DynamicVector, PushBackReserveAndRead) {
65  DynamicVector<int> vector;
66  ASSERT_TRUE(vector.push_back(0x1337));
67  ASSERT_TRUE(vector.push_back(0xface));
68  ASSERT_TRUE(vector.reserve(4));
69  ASSERT_EQ(vector[0], 0x1337);
70  ASSERT_EQ(vector.data()[0], 0x1337);
71  ASSERT_EQ(vector[1], 0xface);
72  ASSERT_EQ(vector.data()[1], 0xface);
73}
74
75class MovableButNonCopyable : public chre::NonCopyable {
76 public:
77  MovableButNonCopyable(int value) : mValue(value) {}
78
79  MovableButNonCopyable(MovableButNonCopyable&& other) {
80    mValue = other.mValue;
81  }
82
83  MovableButNonCopyable& operator=(MovableButNonCopyable&& other) {
84    mValue = other.mValue;
85    return *this;
86  }
87
88  int getValue() const {
89    return mValue;
90  }
91
92 private:
93  int mValue;
94};
95
96TEST(DynamicVector, PushBackReserveAndReadMovableButNonCopyable) {
97  DynamicVector<MovableButNonCopyable> vector;
98  ASSERT_TRUE(vector.emplace_back(0x1337));
99  ASSERT_TRUE(vector.emplace_back(0xface));
100  ASSERT_TRUE(vector.reserve(4));
101  EXPECT_EQ(vector[0].getValue(), 0x1337);
102  EXPECT_EQ(vector.data()[0].getValue(), 0x1337);
103  EXPECT_EQ(vector[1].getValue(), 0xface);
104  EXPECT_EQ(vector.data()[1].getValue(), 0xface);
105}
106
107class CopyableButNonMovable {
108 public:
109  CopyableButNonMovable(int value) : mValue(value) {}
110
111  CopyableButNonMovable(const CopyableButNonMovable& other) {
112    mValue = other.mValue;
113  }
114
115  CopyableButNonMovable(CopyableButNonMovable&& other) = delete;
116
117  CopyableButNonMovable& operator=(const CopyableButNonMovable& other) {
118    mValue = other.mValue;
119    return *this;
120  }
121
122  CopyableButNonMovable& operator=(CopyableButNonMovable&& other) = delete;
123
124  int getValue() const {
125    return mValue;
126  }
127
128 private:
129  int mValue;
130};
131
132TEST(DynamicVector, PushBackReserveAndReadCopyableButNonMovable) {
133  DynamicVector<CopyableButNonMovable> vector;
134  ASSERT_TRUE(vector.emplace_back(0xcafe));
135  ASSERT_TRUE(vector.emplace_back(0xface));
136  ASSERT_TRUE(vector.reserve(4));
137  EXPECT_EQ(vector[0].getValue(), 0xcafe);
138  EXPECT_EQ(vector.data()[0].getValue(), 0xcafe);
139  EXPECT_EQ(vector[1].getValue(), 0xface);
140  EXPECT_EQ(vector.data()[1].getValue(), 0xface);
141}
142
143class MovableAndCopyable {
144 public:
145  MovableAndCopyable(int value) : mValue(value) {}
146
147  MovableAndCopyable(const MovableAndCopyable& other) {
148    mValue = other.mValue;
149  }
150
151  MovableAndCopyable(MovableAndCopyable&& other) {
152    mValue = other.mValue;
153  }
154
155  MovableAndCopyable& operator=(const MovableAndCopyable& other) {
156    mValue = other.mValue;
157    return *this;
158  }
159
160  MovableAndCopyable& operator=(MovableAndCopyable&& other) {
161    // The move operation multiplies the value by 2 so that we can see that the
162    // move assignment operator was used.
163    mValue = other.mValue * 2;
164    return *this;
165  }
166
167  int getValue() const {
168    return mValue;
169  }
170
171 private:
172  int mValue;
173};
174
175TEST(DynamicVector, PushBackReserveAndReadMovableAndCopyable) {
176  // Ensure that preference is given to std::move.
177  DynamicVector<MovableAndCopyable> vector;
178
179  // Reserve enough space for the first two elements.
180  ASSERT_TRUE(vector.reserve(2));
181  ASSERT_TRUE(vector.emplace_back(1000));
182  ASSERT_TRUE(vector.emplace_back(2000));
183
184  // Reserve more than enough space causing a move to be required.
185  ASSERT_TRUE(vector.reserve(4));
186
187  // Move on this type results in a multiplication by 2. Verify that all
188  // elements have been multiplied by 2.
189  EXPECT_EQ(vector[0].getValue(), 2000);
190  EXPECT_EQ(vector.data()[0].getValue(), 2000);
191  EXPECT_EQ(vector[1].getValue(), 4000);
192  EXPECT_EQ(vector.data()[1].getValue(), 4000);
193}
194
195/**
196 * A simple test helper object to count number of construction and destructions.
197 */
198class Foo {
199 public:
200  /**
201   * Construct an object storing a simple integer. Increment the number of
202   * objects that have been constructed of this type.
203   */
204  Foo(int value) : value(value) {
205    sConstructedCounter++;
206  }
207
208  /**
209   * Tear down the object, decrementing the number of objects that have been
210   * constructed of this type.
211   */
212  ~Foo() {
213    sConstructedCounter--;
214  }
215
216  //! The number of objects of this type that have been constructed.
217  static size_t sConstructedCounter;
218
219  //! The value stored in the object to verify the contents of this object after
220  //! construction.
221  int value;
222};
223
224//! Storage for the Foo reference counter.
225size_t Foo::sConstructedCounter = 0;
226
227TEST(DynamicVector, EmplaceBackAndDestruct) {
228  {
229    DynamicVector<Foo> vector;
230    ASSERT_TRUE(vector.emplace_back(1000));
231    ASSERT_TRUE(vector.emplace_back(2000));
232    ASSERT_TRUE(vector.emplace_back(3000));
233    ASSERT_TRUE(vector.emplace_back(4000));
234
235    ASSERT_EQ(vector[0].value, 1000);
236    ASSERT_EQ(vector.data()[0].value, 1000);
237    ASSERT_EQ(vector[1].value, 2000);
238    ASSERT_EQ(vector.data()[1].value, 2000);
239    ASSERT_EQ(vector[2].value, 3000);
240    ASSERT_EQ(vector.data()[2].value, 3000);
241    ASSERT_EQ(vector[3].value, 4000);
242    ASSERT_EQ(vector.data()[3].value, 4000);
243
244    ASSERT_EQ(Foo::sConstructedCounter, 4);
245  }
246
247  ASSERT_EQ(Foo::sConstructedCounter, 0);
248}
249
250TEST(DynamicVector, InsertEmpty) {
251  DynamicVector<int> vector;
252  EXPECT_CHRE_ASSERT(EXPECT_FALSE(vector.insert(1, 0x1337)));
253  ASSERT_TRUE(vector.insert(0, 0x1337));
254  EXPECT_EQ(vector[0], 0x1337);
255  EXPECT_EQ(vector.data()[0], 0x1337);
256}
257
258TEST(DynamicVector, PushBackInsertInMiddleAndRead) {
259  DynamicVector<int> vector;
260  ASSERT_TRUE(vector.push_back(0x1337));
261  ASSERT_TRUE(vector.push_back(0xface));
262  ASSERT_TRUE(vector.push_back(0xcafe));
263  ASSERT_TRUE(vector.insert(1, 0xbeef));
264
265  ASSERT_EQ(vector[0], 0x1337);
266  ASSERT_EQ(vector.data()[0], 0x1337);
267  ASSERT_EQ(vector[1], 0xbeef);
268  ASSERT_EQ(vector.data()[1], 0xbeef);
269  ASSERT_EQ(vector[2], 0xface);
270  ASSERT_EQ(vector.data()[2], 0xface);
271  ASSERT_EQ(vector[3], 0xcafe);
272  ASSERT_EQ(vector.data()[3], 0xcafe);
273}
274
275TEST(DynamicVector, PushBackAndErase) {
276  DynamicVector<int> vector;
277  ASSERT_TRUE(vector.push_back(0x1337));
278  ASSERT_TRUE(vector.push_back(0xcafe));
279  ASSERT_TRUE(vector.push_back(0xbeef));
280  ASSERT_TRUE(vector.push_back(0xface));
281
282  vector.erase(1);
283
284  ASSERT_EQ(vector[0], 0x1337);
285  ASSERT_EQ(vector.data()[0], 0x1337);
286  ASSERT_EQ(vector[1], 0xbeef);
287  ASSERT_EQ(vector.data()[1], 0xbeef);
288  ASSERT_EQ(vector[2], 0xface);
289  ASSERT_EQ(vector.data()[2], 0xface);
290  ASSERT_EQ(vector.size(), 3);
291}
292
293TEST(DynamicVector, FindEmpty) {
294  DynamicVector<int> vector;
295  ASSERT_EQ(vector.find(0), 0);
296}
297
298TEST(DynamicVector, FindWithElements) {
299  DynamicVector<int> vector;
300  ASSERT_TRUE(vector.push_back(0x1337));
301  ASSERT_TRUE(vector.push_back(0xcafe));
302  ASSERT_TRUE(vector.push_back(0xbeef));
303
304  ASSERT_EQ(vector.find(0x1337), 0);
305  ASSERT_EQ(vector.find(0xcafe), 1);
306  ASSERT_EQ(vector.find(0xbeef), 2);
307  ASSERT_EQ(vector.find(1000), 3);
308}
309
310TEST(DynamicVector, EraseDestructorCalled) {
311  resetDestructorCounts();
312
313  DynamicVector<Dummy> vector;
314  for (size_t i = 0; i < 4; ++i) {
315    vector.push_back(Dummy());
316    vector[i].setValue(i);
317  }
318
319  // last item before erase is '3'.
320  vector.erase(1);
321  EXPECT_EQ(0, gDestructorCount[0]);
322  EXPECT_EQ(0, gDestructorCount[1]);
323  EXPECT_EQ(0, gDestructorCount[2]);
324  EXPECT_EQ(1, gDestructorCount[3]);
325
326  // last item before erase is still '3'.
327  vector.erase(2);
328  EXPECT_EQ(0, gDestructorCount[0]);
329  EXPECT_EQ(0, gDestructorCount[1]);
330  EXPECT_EQ(0, gDestructorCount[2]);
331  EXPECT_EQ(2, gDestructorCount[3]);
332
333  // last item before erase is now '2'.
334  vector.erase(0);
335  EXPECT_EQ(0, gDestructorCount[0]);
336  EXPECT_EQ(0, gDestructorCount[1]);
337  EXPECT_EQ(1, gDestructorCount[2]);
338  EXPECT_EQ(2, gDestructorCount[3]);
339}
340
341TEST(DynamicVector, Clear) {
342  resetDestructorCounts();
343
344  DynamicVector<Dummy> vector;
345  for (size_t i = 0; i < 4; ++i) {
346    vector.push_back(Dummy());
347    vector[i].setValue(i);
348  }
349
350  vector.clear();
351  EXPECT_EQ(vector.size(), 0);
352  EXPECT_EQ(vector.capacity(), 4);
353
354  for (size_t i = 0; i < 4; ++i) {
355    EXPECT_EQ(gDestructorCount[i], 1);
356  }
357}
358
359// Make sure that a vector wrapping an array doesn't call the destructor when
360// the vector is destructed
361TEST(DynamicVector, WrapDoesntCallDestructor) {
362  resetDestructorCounts();
363
364  Dummy array[4];
365  for (size_t i = 0; i < 4; ++i) {
366    array[i].setValue(i);
367  }
368
369  {
370    DynamicVector<Dummy> vector;
371    vector.wrap(array, ARRAY_SIZE(array));
372  }
373
374  for (size_t i = 0; i < 4; ++i) {
375    EXPECT_EQ(gDestructorCount[i], 0);
376  }
377}
378
379// Make sure that a wrapped vector does call the destructor when it's expected
380// as part of an API call
381TEST(DynamicVector, WrapExplicitlyCallsDestructor) {
382  resetDestructorCounts();
383
384  Dummy array[4];
385  constexpr size_t kSize = ARRAY_SIZE(array);
386  static_assert(ARRAY_SIZE(array) <= ARRAY_SIZE(gDestructorCount),
387                "gDestructorCount array must fit test array");
388  for (size_t i = 0; i < kSize; ++i) {
389    array[i].setValue(i);
390  }
391  DynamicVector<Dummy> vector;
392  vector.wrap(array, ARRAY_SIZE(array));
393
394  vector.erase(kSize - 1);
395  for (size_t i = 0; i < kSize - 1; i++) {
396    EXPECT_EQ(gDestructorCount[i], 0);
397  }
398  EXPECT_EQ(gDestructorCount[kSize - 1], 1);
399
400  vector.clear();
401  for (size_t i = 0; i < kSize; ++i) {
402    EXPECT_EQ(gDestructorCount[i], 1);
403  }
404}
405
406TEST(DynamicVectorDeathTest, SwapWithInvalidIndex) {
407  DynamicVector<int> vector;
408  vector.push_back(0x1337);
409  vector.push_back(0xcafe);
410  EXPECT_DEATH(vector.swap(0, 2), "");
411}
412
413TEST(DynamicVectorDeathTest, SwapWithInvalidIndices) {
414  DynamicVector<int> vector;
415  vector.push_back(0x1337);
416  vector.push_back(0xcafe);
417  EXPECT_DEATH(vector.swap(2, 3), "");
418}
419
420TEST(DynamicVector, Swap) {
421  DynamicVector<int> vector;
422  vector.push_back(0x1337);
423  vector.push_back(0xcafe);
424
425  vector.swap(0, 1);
426  EXPECT_EQ(vector[0], 0xcafe);
427  EXPECT_EQ(vector[1], 0x1337);
428}
429
430TEST(DynamicVector, BackFront) {
431  DynamicVector<int> vector;
432  vector.push_back(0x1337);
433  EXPECT_EQ(vector.front(), 0x1337);
434  EXPECT_EQ(vector.back(), 0x1337);
435  vector.push_back(0xcafe);
436  EXPECT_EQ(vector.front(), 0x1337);
437  EXPECT_EQ(vector.back(), 0xcafe);
438  vector.erase(0);
439  EXPECT_EQ(vector.front(), 0xcafe);
440  EXPECT_EQ(vector.back(), 0xcafe);
441}
442
443TEST(DynamicVector, Iterator) {
444  DynamicVector<int> vector;
445  vector.push_back(0);
446  vector.push_back(1);
447  vector.push_back(2);
448
449  size_t index = 0;
450  for (DynamicVector<int>::iterator it = vector.begin();
451       it != vector.end(); ++it) {
452    EXPECT_EQ(vector[index++], *it);
453  }
454
455  DynamicVector<int>::iterator it = vector.begin() + vector.size() - 1;
456  EXPECT_EQ(vector[vector.size() - 1], *it);
457
458  it = vector.begin() + vector.size();
459  EXPECT_TRUE(it == vector.end());
460}
461
462TEST(DynamicVector, ConstIterator) {
463  DynamicVector<int> vector;
464  vector.push_back(0);
465  vector.push_back(1);
466  vector.push_back(2);
467
468  size_t index = 0;
469  for (DynamicVector<int>::const_iterator cit = vector.cbegin();
470       cit != vector.cend(); ++cit) {
471    EXPECT_EQ(vector[index++], *cit);
472  }
473
474  DynamicVector<int>::const_iterator cit = vector.cbegin() + vector.size() - 1;
475  EXPECT_EQ(vector[vector.size() - 1], *cit);
476
477  cit = vector.cbegin() + vector.size();
478  EXPECT_TRUE(cit == vector.cend());
479}
480
481TEST(DynamicVector, IteratorAndPushBack) {
482  DynamicVector<int> vector;
483  vector.push_back(0);
484  vector.push_back(1);
485  vector.push_back(2);
486  size_t oldCapacity = vector.capacity();
487
488  DynamicVector<int>::iterator it_b = vector.begin();
489  DynamicVector<int>::iterator it_e = vector.end();
490
491  vector.push_back(3);
492  ASSERT_TRUE(oldCapacity == vector.capacity());
493
494  size_t index = 0;
495  for (; it_b != it_e; ++it_b) {
496    EXPECT_EQ(vector[index++], *it_b);
497  }
498}
499
500TEST(DynamicVector, IteratorAndEmplaceBack) {
501  DynamicVector<int> vector;
502  vector.push_back(0);
503  vector.push_back(1);
504  vector.push_back(2);
505  size_t oldCapacity = vector.capacity();
506
507  DynamicVector<int>::iterator it_b = vector.begin();
508  DynamicVector<int>::iterator it_e = vector.end();
509
510  vector.emplace_back(3);
511  ASSERT_TRUE(oldCapacity == vector.capacity());
512
513  size_t index = 0;
514  for (; it_b != it_e; ++it_b) {
515    EXPECT_EQ(vector[index++], *it_b);
516  }
517}
518
519TEST(DynamicVector, IteratorAndReserve) {
520  DynamicVector<int> vector;
521  vector.push_back(0);
522  vector.push_back(1);
523  vector.push_back(2);
524  size_t oldCapacity = vector.capacity();
525
526  DynamicVector<int>::iterator it_b = vector.begin();
527  DynamicVector<int>::iterator it_e = vector.end();
528
529  vector.reserve(oldCapacity);
530  ASSERT_TRUE(oldCapacity == vector.capacity());
531
532  size_t index = 0;
533  for (; it_b != it_e; ++it_b) {
534    EXPECT_EQ(vector[index++], *it_b);
535  }
536}
537
538TEST(DynamicVector, IteratorAndInsert) {
539  DynamicVector<int> vector;
540  vector.push_back(0);
541  vector.push_back(1);
542  vector.push_back(2);
543  size_t oldCapacity = vector.capacity();
544
545  DynamicVector<int>::iterator it_b = vector.begin();
546
547  vector.insert(2, 3);
548  ASSERT_TRUE(oldCapacity == vector.capacity());
549
550  size_t index = 0;
551  while (index < 2) {
552    EXPECT_EQ(vector[index++], *it_b++);
553  }
554}
555
556TEST(DynamicVector, IteratorAndErase) {
557  DynamicVector<int> vector;
558  vector.push_back(0);
559  vector.push_back(1);
560  vector.push_back(2);
561
562  DynamicVector<int>::iterator it_b = vector.begin();
563
564  vector.erase(2);
565
566  size_t index = 0;
567  while (index < 2) {
568    EXPECT_EQ(vector[index++], *it_b++);
569  }
570}
571
572TEST(DynamicVector, IteratorAndSwap) {
573  DynamicVector<int> vector;
574  vector.push_back(0);
575  vector.push_back(1);
576  vector.push_back(2);
577  vector.push_back(3);
578
579  DynamicVector<int>::iterator it_b = vector.begin();
580
581  vector.swap(1, 3);
582
583  size_t index = 0;
584  while (index < 4) {
585    if (index != 1 && index != 3) {
586      EXPECT_EQ(vector[index], *it_b);
587    }
588    index++;
589    it_b++;
590  }
591}
592
593TEST(DynamicVector, MoveConstruct) {
594  DynamicVector<int> vector;
595  ASSERT_TRUE(vector.push_back(0));
596  ASSERT_TRUE(vector.push_back(1));
597  ASSERT_TRUE(vector.push_back(2));
598
599  DynamicVector<int> movedVector(std::move(vector));
600  EXPECT_EQ(vector.data(), nullptr);
601  EXPECT_NE(movedVector.data(), nullptr);
602  EXPECT_EQ(vector.size(), 0);
603  EXPECT_EQ(movedVector.size(), 3);
604  EXPECT_EQ(vector.capacity(), 0);
605  EXPECT_EQ(movedVector.capacity(), 4);
606}
607
608// Tests basic functionality of a vector wrapping an array
609TEST(DynamicVector, Wrap) {
610  constexpr size_t kSize = 4;
611  int buf[kSize];
612  for (size_t i = 0; i < kSize; i++) {
613    buf[i] = i;
614  }
615
616  DynamicVector<int> vector;
617  EXPECT_TRUE(vector.owns_data());
618  vector.wrap(buf, kSize);
619  EXPECT_FALSE(vector.owns_data());
620  EXPECT_EQ(vector.size(), kSize);
621  EXPECT_EQ(vector.capacity(), kSize);
622  EXPECT_EQ(vector.data(), buf);
623
624  EXPECT_CHRE_ASSERT(EXPECT_FALSE(vector.reserve(8)));
625  EXPECT_CHRE_ASSERT(EXPECT_FALSE(vector.push_back(-1)));
626  EXPECT_CHRE_ASSERT(EXPECT_FALSE(vector.emplace_back(-1)));
627  EXPECT_CHRE_ASSERT(EXPECT_FALSE(vector.insert(1, -1)));
628
629  for (size_t i = 0; i < kSize; i++) {
630    EXPECT_EQ(vector[i], i);
631  }
632
633  vector.erase(0);
634  for (size_t i = 0; i < kSize - 1; i++) {
635    EXPECT_EQ(vector[i], i + 1);
636  }
637
638  EXPECT_TRUE(vector.push_back(kSize + 1));
639  EXPECT_EQ(vector.back(), kSize + 1);
640}
641
642TEST(DynamicVector, MoveWrappedVector) {
643  constexpr size_t kSize = 4;
644  int buf[kSize];
645  for (size_t i = 0; i < kSize; i++) {
646    buf[i] = i;
647  }
648
649  DynamicVector<int> vector1;
650  vector1.wrap(buf, kSize);
651
652  DynamicVector<int> vector2 = std::move(vector1);
653  EXPECT_TRUE(vector1.owns_data());
654  EXPECT_EQ(vector1.size(), 0);
655  EXPECT_EQ(vector1.capacity(), 0);
656  EXPECT_EQ(vector1.data(), nullptr);
657
658  EXPECT_FALSE(vector2.owns_data());
659  EXPECT_EQ(vector2.size(), kSize);
660  EXPECT_EQ(vector2.capacity(), kSize);
661  EXPECT_EQ(vector2.data(), buf);
662}
663
664TEST(DynamicVector, Unwrap) {
665  constexpr size_t kSize = 4;
666  int buf[kSize];
667  for (size_t i = 0; i < kSize; i++) {
668    buf[i] = i;
669  }
670
671  DynamicVector<int> vec;
672  vec.wrap(buf, kSize);
673  ASSERT_FALSE(vec.owns_data());
674
675  vec.unwrap();
676  EXPECT_TRUE(vec.owns_data());
677  EXPECT_EQ(vec.size(), 0);
678  EXPECT_EQ(vec.capacity(), 0);
679  EXPECT_EQ(vec.data(), nullptr);
680
681  EXPECT_TRUE(vec.push_back(1));
682}
683