inlined_vector_test.cc
Go to the documentation of this file.
1 // Copyright 2017 The Abseil Authors.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 
16 
17 #include <algorithm>
18 #include <forward_list>
19 #include <list>
20 #include <memory>
21 #include <scoped_allocator>
22 #include <sstream>
23 #include <stdexcept>
24 #include <string>
25 #include <vector>
26 
27 #include "gmock/gmock.h"
28 #include "gtest/gtest.h"
29 #include "absl/base/attributes.h"
32 #include "absl/base/macros.h"
35 #include "absl/hash/hash_testing.h"
36 #include "absl/memory/memory.h"
37 #include "absl/strings/str_cat.h"
38 
39 namespace {
40 
45 using testing::AllOf;
46 using testing::Each;
47 using testing::ElementsAre;
48 using testing::ElementsAreArray;
49 using testing::Eq;
50 using testing::Gt;
51 using testing::PrintToString;
52 
53 using IntVec = absl::InlinedVector<int, 8>;
54 
55 MATCHER_P(SizeIs, n, "") {
56  return testing::ExplainMatchResult(n, arg.size(), result_listener);
57 }
58 
59 MATCHER_P(CapacityIs, n, "") {
60  return testing::ExplainMatchResult(n, arg.capacity(), result_listener);
61 }
62 
63 MATCHER_P(ValueIs, e, "") {
64  return testing::ExplainMatchResult(e, arg.value(), result_listener);
65 }
66 
67 // TODO(bsamwel): Add support for movable-only types.
68 
69 // Test fixture for typed tests on BaseCountedInstance derived classes, see
70 // test_instance_tracker.h.
71 template <typename T>
72 class InstanceTest : public ::testing::Test {};
73 TYPED_TEST_SUITE_P(InstanceTest);
74 
75 // A simple reference counted class to make sure that the proper elements are
76 // destroyed in the erase(begin, end) test.
77 class RefCounted {
78  public:
79  RefCounted(int value, int* count) : value_(value), count_(count) {
80  Ref();
81  }
82 
83  RefCounted(const RefCounted& v)
84  : value_(v.value_), count_(v.count_) {
85  Ref();
86  }
87 
88  ~RefCounted() {
89  Unref();
90  count_ = nullptr;
91  }
92 
93  friend void swap(RefCounted& a, RefCounted& b) {
94  using std::swap;
95  swap(a.value_, b.value_);
96  swap(a.count_, b.count_);
97  }
98 
99  RefCounted& operator=(RefCounted v) {
100  using std::swap;
101  swap(*this, v);
102  return *this;
103  }
104 
105  void Ref() const {
106  ABSL_RAW_CHECK(count_ != nullptr, "");
107  ++(*count_);
108  }
109 
110  void Unref() const {
111  --(*count_);
112  ABSL_RAW_CHECK(*count_ >= 0, "");
113  }
114 
115  int value_;
116  int* count_;
117 };
118 
119 using RefCountedVec = absl::InlinedVector<RefCounted, 8>;
120 
121 // A class with a vtable pointer
122 class Dynamic {
123  public:
124  virtual ~Dynamic() {}
125 };
126 
127 using DynamicVec = absl::InlinedVector<Dynamic, 8>;
128 
129 // Append 0..len-1 to *v
130 template <typename Container>
131 static void Fill(Container* v, int len, int offset = 0) {
132  for (int i = 0; i < len; i++) {
133  v->push_back(i + offset);
134  }
135 }
136 
137 static IntVec Fill(int len, int offset = 0) {
138  IntVec v;
139  Fill(&v, len, offset);
140  return v;
141 }
142 
143 TEST(IntVec, SimpleOps) {
144  for (int len = 0; len < 20; len++) {
145  IntVec v;
146  const IntVec& cv = v; // const alias
147 
148  Fill(&v, len);
149  EXPECT_EQ(len, v.size());
150  EXPECT_LE(len, v.capacity());
151 
152  for (int i = 0; i < len; i++) {
153  EXPECT_EQ(i, v[i]);
154  EXPECT_EQ(i, v.at(i));
155  }
156  EXPECT_EQ(v.begin(), v.data());
157  EXPECT_EQ(cv.begin(), cv.data());
158 
159  int counter = 0;
160  for (IntVec::iterator iter = v.begin(); iter != v.end(); ++iter) {
161  EXPECT_EQ(counter, *iter);
162  counter++;
163  }
164  EXPECT_EQ(counter, len);
165 
166  counter = 0;
167  for (IntVec::const_iterator iter = v.begin(); iter != v.end(); ++iter) {
168  EXPECT_EQ(counter, *iter);
169  counter++;
170  }
171  EXPECT_EQ(counter, len);
172 
173  counter = 0;
174  for (IntVec::const_iterator iter = v.cbegin(); iter != v.cend(); ++iter) {
175  EXPECT_EQ(counter, *iter);
176  counter++;
177  }
178  EXPECT_EQ(counter, len);
179 
180  if (len > 0) {
181  EXPECT_EQ(0, v.front());
182  EXPECT_EQ(len - 1, v.back());
183  v.pop_back();
184  EXPECT_EQ(len - 1, v.size());
185  for (int i = 0; i < v.size(); ++i) {
186  EXPECT_EQ(i, v[i]);
187  EXPECT_EQ(i, v.at(i));
188  }
189  }
190  }
191 }
192 
193 TEST(IntVec, AtThrows) {
194  IntVec v = {1, 2, 3};
195  EXPECT_EQ(v.at(2), 3);
196  ABSL_BASE_INTERNAL_EXPECT_FAIL(v.at(3), std::out_of_range,
197  "failed bounds check");
198 }
199 
200 TEST(IntVec, ReverseIterator) {
201  for (int len = 0; len < 20; len++) {
202  IntVec v;
203  Fill(&v, len);
204 
205  int counter = len;
206  for (IntVec::reverse_iterator iter = v.rbegin(); iter != v.rend(); ++iter) {
207  counter--;
208  EXPECT_EQ(counter, *iter);
209  }
210  EXPECT_EQ(counter, 0);
211 
212  counter = len;
213  for (IntVec::const_reverse_iterator iter = v.rbegin(); iter != v.rend();
214  ++iter) {
215  counter--;
216  EXPECT_EQ(counter, *iter);
217  }
218  EXPECT_EQ(counter, 0);
219 
220  counter = len;
221  for (IntVec::const_reverse_iterator iter = v.crbegin(); iter != v.crend();
222  ++iter) {
223  counter--;
224  EXPECT_EQ(counter, *iter);
225  }
226  EXPECT_EQ(counter, 0);
227  }
228 }
229 
230 TEST(IntVec, Erase) {
231  for (int len = 1; len < 20; len++) {
232  for (int i = 0; i < len; ++i) {
233  IntVec v;
234  Fill(&v, len);
235  v.erase(v.begin() + i);
236  EXPECT_EQ(len - 1, v.size());
237  for (int j = 0; j < i; ++j) {
238  EXPECT_EQ(j, v[j]);
239  }
240  for (int j = i; j < len - 1; ++j) {
241  EXPECT_EQ(j + 1, v[j]);
242  }
243  }
244  }
245 }
246 
247 // At the end of this test loop, the elements between [erase_begin, erase_end)
248 // should have reference counts == 0, and all others elements should have
249 // reference counts == 1.
250 TEST(RefCountedVec, EraseBeginEnd) {
251  for (int len = 1; len < 20; ++len) {
252  for (int erase_begin = 0; erase_begin < len; ++erase_begin) {
253  for (int erase_end = erase_begin; erase_end <= len; ++erase_end) {
254  std::vector<int> counts(len, 0);
255  RefCountedVec v;
256  for (int i = 0; i < len; ++i) {
257  v.push_back(RefCounted(i, &counts[i]));
258  }
259 
260  int erase_len = erase_end - erase_begin;
261 
262  v.erase(v.begin() + erase_begin, v.begin() + erase_end);
263 
264  EXPECT_EQ(len - erase_len, v.size());
265 
266  // Check the elements before the first element erased.
267  for (int i = 0; i < erase_begin; ++i) {
268  EXPECT_EQ(i, v[i].value_);
269  }
270 
271  // Check the elements after the first element erased.
272  for (int i = erase_begin; i < v.size(); ++i) {
273  EXPECT_EQ(i + erase_len, v[i].value_);
274  }
275 
276  // Check that the elements at the beginning are preserved.
277  for (int i = 0; i < erase_begin; ++i) {
278  EXPECT_EQ(1, counts[i]);
279  }
280 
281  // Check that the erased elements are destroyed
282  for (int i = erase_begin; i < erase_end; ++i) {
283  EXPECT_EQ(0, counts[i]);
284  }
285 
286  // Check that the elements at the end are preserved.
287  for (int i = erase_end; i< len; ++i) {
288  EXPECT_EQ(1, counts[i]);
289  }
290  }
291  }
292  }
293 }
294 
295 struct NoDefaultCtor {
296  explicit NoDefaultCtor(int) {}
297 };
298 struct NoCopy {
299  NoCopy() {}
300  NoCopy(const NoCopy&) = delete;
301 };
302 struct NoAssign {
303  NoAssign() {}
304  NoAssign& operator=(const NoAssign&) = delete;
305 };
306 struct MoveOnly {
307  MoveOnly() {}
308  MoveOnly(MoveOnly&&) = default;
309  MoveOnly& operator=(MoveOnly&&) = default;
310 };
311 TEST(InlinedVectorTest, NoDefaultCtor) {
312  absl::InlinedVector<NoDefaultCtor, 1> v(10, NoDefaultCtor(2));
313  (void)v;
314 }
315 TEST(InlinedVectorTest, NoCopy) {
317  (void)v;
318 }
319 TEST(InlinedVectorTest, NoAssign) {
321  (void)v;
322 }
323 TEST(InlinedVectorTest, MoveOnly) {
325  v.push_back(MoveOnly{});
326  v.push_back(MoveOnly{});
327  v.push_back(MoveOnly{});
328  v.erase(v.begin());
329  v.push_back(MoveOnly{});
330  v.erase(v.begin(), v.begin() + 1);
331  v.insert(v.begin(), MoveOnly{});
332  v.emplace(v.begin());
333  v.emplace(v.begin(), MoveOnly{});
334 }
335 TEST(InlinedVectorTest, Noexcept) {
337  EXPECT_TRUE((std::is_nothrow_move_constructible<
339 
340  struct MoveCanThrow {
341  MoveCanThrow(MoveCanThrow&&) {}
342  };
344  (std::is_nothrow_move_constructible<
346 }
347 
348 TEST(InlinedVectorTest, EmplaceBack) {
350 
351  auto& inlined_element = v.emplace_back("answer", 42);
352  EXPECT_EQ(&inlined_element, &v[0]);
353  EXPECT_EQ(inlined_element.first, "answer");
354  EXPECT_EQ(inlined_element.second, 42);
355 
356  auto& allocated_element = v.emplace_back("taxicab", 1729);
357  EXPECT_EQ(&allocated_element, &v[1]);
358  EXPECT_EQ(allocated_element.first, "taxicab");
359  EXPECT_EQ(allocated_element.second, 1729);
360 }
361 
362 TEST(InlinedVectorTest, ShrinkToFitGrowingVector) {
364 
365  v.shrink_to_fit();
366  EXPECT_EQ(v.capacity(), 1);
367 
368  v.emplace_back("answer", 42);
369  v.shrink_to_fit();
370  EXPECT_EQ(v.capacity(), 1);
371 
372  v.emplace_back("taxicab", 1729);
373  EXPECT_GE(v.capacity(), 2);
374  v.shrink_to_fit();
375  EXPECT_EQ(v.capacity(), 2);
376 
377  v.reserve(100);
378  EXPECT_GE(v.capacity(), 100);
379  v.shrink_to_fit();
380  EXPECT_EQ(v.capacity(), 2);
381 }
382 
383 TEST(InlinedVectorTest, ShrinkToFitEdgeCases) {
384  {
386  v.emplace_back("answer", 42);
387  v.emplace_back("taxicab", 1729);
388  EXPECT_GE(v.capacity(), 2);
389  v.pop_back();
390  v.shrink_to_fit();
391  EXPECT_EQ(v.capacity(), 1);
392  EXPECT_EQ(v[0].first, "answer");
393  EXPECT_EQ(v[0].second, 42);
394  }
395 
396  {
398  v.resize(0);
399  v.shrink_to_fit();
400  EXPECT_EQ(v.capacity(), 2); // inlined capacity
401  }
402 
403  {
405  v.resize(1);
406  v.shrink_to_fit();
407  EXPECT_EQ(v.capacity(), 2); // inlined capacity
408  }
409 
410  {
412  v.resize(2);
413  v.shrink_to_fit();
414  EXPECT_EQ(v.capacity(), 2);
415  }
416 
417  {
419  v.resize(3);
420  v.shrink_to_fit();
421  EXPECT_EQ(v.capacity(), 3);
422  }
423 }
424 
425 TEST(IntVec, Insert) {
426  for (int len = 0; len < 20; len++) {
427  for (int pos = 0; pos <= len; pos++) {
428  {
429  // Single element
430  std::vector<int> std_v;
431  Fill(&std_v, len);
432  IntVec v;
433  Fill(&v, len);
434 
435  std_v.insert(std_v.begin() + pos, 9999);
436  IntVec::iterator it = v.insert(v.cbegin() + pos, 9999);
437  EXPECT_THAT(v, ElementsAreArray(std_v));
438  EXPECT_EQ(it, v.cbegin() + pos);
439  }
440  {
441  // n elements
442  std::vector<int> std_v;
443  Fill(&std_v, len);
444  IntVec v;
445  Fill(&v, len);
446 
447  IntVec::size_type n = 5;
448  std_v.insert(std_v.begin() + pos, n, 9999);
449  IntVec::iterator it = v.insert(v.cbegin() + pos, n, 9999);
450  EXPECT_THAT(v, ElementsAreArray(std_v));
451  EXPECT_EQ(it, v.cbegin() + pos);
452  }
453  {
454  // Iterator range (random access iterator)
455  std::vector<int> std_v;
456  Fill(&std_v, len);
457  IntVec v;
458  Fill(&v, len);
459 
460  const std::vector<int> input = {9999, 8888, 7777};
461  std_v.insert(std_v.begin() + pos, input.cbegin(), input.cend());
462  IntVec::iterator it =
463  v.insert(v.cbegin() + pos, input.cbegin(), input.cend());
464  EXPECT_THAT(v, ElementsAreArray(std_v));
465  EXPECT_EQ(it, v.cbegin() + pos);
466  }
467  {
468  // Iterator range (forward iterator)
469  std::vector<int> std_v;
470  Fill(&std_v, len);
471  IntVec v;
472  Fill(&v, len);
473 
474  const std::forward_list<int> input = {9999, 8888, 7777};
475  std_v.insert(std_v.begin() + pos, input.cbegin(), input.cend());
476  IntVec::iterator it =
477  v.insert(v.cbegin() + pos, input.cbegin(), input.cend());
478  EXPECT_THAT(v, ElementsAreArray(std_v));
479  EXPECT_EQ(it, v.cbegin() + pos);
480  }
481  {
482  // Iterator range (input iterator)
483  std::vector<int> std_v;
484  Fill(&std_v, len);
485  IntVec v;
486  Fill(&v, len);
487 
488  std_v.insert(std_v.begin() + pos, {9999, 8888, 7777});
489  std::istringstream input("9999 8888 7777");
490  IntVec::iterator it =
491  v.insert(v.cbegin() + pos, std::istream_iterator<int>(input),
492  std::istream_iterator<int>());
493  EXPECT_THAT(v, ElementsAreArray(std_v));
494  EXPECT_EQ(it, v.cbegin() + pos);
495  }
496  {
497  // Initializer list
498  std::vector<int> std_v;
499  Fill(&std_v, len);
500  IntVec v;
501  Fill(&v, len);
502 
503  std_v.insert(std_v.begin() + pos, {9999, 8888});
504  IntVec::iterator it = v.insert(v.cbegin() + pos, {9999, 8888});
505  EXPECT_THAT(v, ElementsAreArray(std_v));
506  EXPECT_EQ(it, v.cbegin() + pos);
507  }
508  }
509  }
510 }
511 
512 TEST(RefCountedVec, InsertConstructorDestructor) {
513  // Make sure the proper construction/destruction happen during insert
514  // operations.
515  for (int len = 0; len < 20; len++) {
516  SCOPED_TRACE(len);
517  for (int pos = 0; pos <= len; pos++) {
518  SCOPED_TRACE(pos);
519  std::vector<int> counts(len, 0);
520  int inserted_count = 0;
521  RefCountedVec v;
522  for (int i = 0; i < len; ++i) {
523  SCOPED_TRACE(i);
524  v.push_back(RefCounted(i, &counts[i]));
525  }
526 
527  EXPECT_THAT(counts, Each(Eq(1)));
528 
529  RefCounted insert_element(9999, &inserted_count);
530  EXPECT_EQ(1, inserted_count);
531  v.insert(v.begin() + pos, insert_element);
532  EXPECT_EQ(2, inserted_count);
533  // Check that the elements at the end are preserved.
534  EXPECT_THAT(counts, Each(Eq(1)));
535  EXPECT_EQ(2, inserted_count);
536  }
537  }
538 }
539 
540 TEST(IntVec, Resize) {
541  for (int len = 0; len < 20; len++) {
542  IntVec v;
543  Fill(&v, len);
544 
545  // Try resizing up and down by k elements
546  static const int kResizeElem = 1000000;
547  for (int k = 0; k < 10; k++) {
548  // Enlarging resize
549  v.resize(len+k, kResizeElem);
550  EXPECT_EQ(len+k, v.size());
551  EXPECT_LE(len+k, v.capacity());
552  for (int i = 0; i < len+k; i++) {
553  if (i < len) {
554  EXPECT_EQ(i, v[i]);
555  } else {
556  EXPECT_EQ(kResizeElem, v[i]);
557  }
558  }
559 
560  // Shrinking resize
561  v.resize(len, kResizeElem);
562  EXPECT_EQ(len, v.size());
563  EXPECT_LE(len, v.capacity());
564  for (int i = 0; i < len; i++) {
565  EXPECT_EQ(i, v[i]);
566  }
567  }
568  }
569 }
570 
571 TEST(IntVec, InitWithLength) {
572  for (int len = 0; len < 20; len++) {
573  IntVec v(len, 7);
574  EXPECT_EQ(len, v.size());
575  EXPECT_LE(len, v.capacity());
576  for (int i = 0; i < len; i++) {
577  EXPECT_EQ(7, v[i]);
578  }
579  }
580 }
581 
582 TEST(IntVec, CopyConstructorAndAssignment) {
583  for (int len = 0; len < 20; len++) {
584  IntVec v;
585  Fill(&v, len);
586  EXPECT_EQ(len, v.size());
587  EXPECT_LE(len, v.capacity());
588 
589  IntVec v2(v);
590  EXPECT_TRUE(v == v2) << PrintToString(v) << PrintToString(v2);
591 
592  for (int start_len = 0; start_len < 20; start_len++) {
593  IntVec v3;
594  Fill(&v3, start_len, 99); // Add dummy elements that should go away
595  v3 = v;
596  EXPECT_TRUE(v == v3) << PrintToString(v) << PrintToString(v3);
597  }
598  }
599 }
600 
601 TEST(IntVec, AliasingCopyAssignment) {
602  for (int len = 0; len < 20; ++len) {
603  IntVec original;
604  Fill(&original, len);
605  IntVec dup = original;
606  dup = *&dup;
607  EXPECT_EQ(dup, original);
608  }
609 }
610 
611 TEST(IntVec, MoveConstructorAndAssignment) {
612  for (int len = 0; len < 20; len++) {
613  IntVec v_in;
614  const int inlined_capacity = v_in.capacity();
615  Fill(&v_in, len);
616  EXPECT_EQ(len, v_in.size());
617  EXPECT_LE(len, v_in.capacity());
618 
619  {
620  IntVec v_temp(v_in);
621  auto* old_data = v_temp.data();
622  IntVec v_out(std::move(v_temp));
623  EXPECT_TRUE(v_in == v_out) << PrintToString(v_in) << PrintToString(v_out);
624  if (v_in.size() > inlined_capacity) {
625  // Allocation is moved as a whole, data stays in place.
626  EXPECT_TRUE(v_out.data() == old_data);
627  } else {
628  EXPECT_FALSE(v_out.data() == old_data);
629  }
630  }
631  for (int start_len = 0; start_len < 20; start_len++) {
632  IntVec v_out;
633  Fill(&v_out, start_len, 99); // Add dummy elements that should go away
634  IntVec v_temp(v_in);
635  auto* old_data = v_temp.data();
636  v_out = std::move(v_temp);
637  EXPECT_TRUE(v_in == v_out) << PrintToString(v_in) << PrintToString(v_out);
638  if (v_in.size() > inlined_capacity) {
639  // Allocation is moved as a whole, data stays in place.
640  EXPECT_TRUE(v_out.data() == old_data);
641  } else {
642  EXPECT_FALSE(v_out.data() == old_data);
643  }
644  }
645  }
646 }
647 
648 class NotTriviallyDestructible {
649  public:
650  NotTriviallyDestructible() : p_(new int(1)) {}
651  explicit NotTriviallyDestructible(int i) : p_(new int(i)) {}
652 
653  NotTriviallyDestructible(const NotTriviallyDestructible& other)
654  : p_(new int(*other.p_)) {}
655 
656  NotTriviallyDestructible& operator=(const NotTriviallyDestructible& other) {
657  p_ = absl::make_unique<int>(*other.p_);
658  return *this;
659  }
660 
661  bool operator==(const NotTriviallyDestructible& other) const {
662  return *p_ == *other.p_;
663  }
664 
665  private:
666  std::unique_ptr<int> p_;
667 };
668 
669 TEST(AliasingTest, Emplace) {
670  for (int i = 2; i < 20; ++i) {
672  for (int j = 0; j < i; ++j) {
673  vec.push_back(NotTriviallyDestructible(j));
674  }
675  vec.emplace(vec.begin(), vec[0]);
676  EXPECT_EQ(vec[0], vec[1]);
677  vec.emplace(vec.begin() + i / 2, vec[i / 2]);
678  EXPECT_EQ(vec[i / 2], vec[i / 2 + 1]);
679  vec.emplace(vec.end() - 1, vec.back());
680  EXPECT_EQ(vec[vec.size() - 2], vec.back());
681  }
682 }
683 
684 TEST(AliasingTest, InsertWithCount) {
685  for (int i = 1; i < 20; ++i) {
687  for (int j = 0; j < i; ++j) {
688  vec.push_back(NotTriviallyDestructible(j));
689  }
690  for (int n = 0; n < 5; ++n) {
691  // We use back where we can because it's guaranteed to become invalidated
692  vec.insert(vec.begin(), n, vec.back());
693  auto b = vec.begin();
694  EXPECT_TRUE(
695  std::all_of(b, b + n, [&vec](const NotTriviallyDestructible& x) {
696  return x == vec.back();
697  }));
698 
699  auto m_idx = vec.size() / 2;
700  vec.insert(vec.begin() + m_idx, n, vec.back());
701  auto m = vec.begin() + m_idx;
702  EXPECT_TRUE(
703  std::all_of(m, m + n, [&vec](const NotTriviallyDestructible& x) {
704  return x == vec.back();
705  }));
706 
707  // We want distinct values so the equality test is meaningful,
708  // vec[vec.size() - 1] is also almost always invalidated.
709  auto old_e = vec.size() - 1;
710  auto val = vec[old_e];
711  vec.insert(vec.end(), n, vec[old_e]);
712  auto e = vec.begin() + old_e;
713  EXPECT_TRUE(std::all_of(
714  e, e + n,
715  [&val](const NotTriviallyDestructible& x) { return x == val; }));
716  }
717  }
718 }
719 
720 TEST(OverheadTest, Storage) {
721  // Check for size overhead.
722  // In particular, ensure that std::allocator doesn't cost anything to store.
723  // The union should be absorbing some of the allocation bookkeeping overhead
724  // in the larger vectors, leaving only the size_ field as overhead.
725  EXPECT_EQ(2 * sizeof(int*),
726  sizeof(absl::InlinedVector<int*, 1>) - 1 * sizeof(int*));
727  EXPECT_EQ(1 * sizeof(int*),
728  sizeof(absl::InlinedVector<int*, 2>) - 2 * sizeof(int*));
729  EXPECT_EQ(1 * sizeof(int*),
730  sizeof(absl::InlinedVector<int*, 3>) - 3 * sizeof(int*));
731  EXPECT_EQ(1 * sizeof(int*),
732  sizeof(absl::InlinedVector<int*, 4>) - 4 * sizeof(int*));
733  EXPECT_EQ(1 * sizeof(int*),
734  sizeof(absl::InlinedVector<int*, 5>) - 5 * sizeof(int*));
735  EXPECT_EQ(1 * sizeof(int*),
736  sizeof(absl::InlinedVector<int*, 6>) - 6 * sizeof(int*));
737  EXPECT_EQ(1 * sizeof(int*),
738  sizeof(absl::InlinedVector<int*, 7>) - 7 * sizeof(int*));
739  EXPECT_EQ(1 * sizeof(int*),
740  sizeof(absl::InlinedVector<int*, 8>) - 8 * sizeof(int*));
741 }
742 
743 TEST(IntVec, Clear) {
744  for (int len = 0; len < 20; len++) {
745  SCOPED_TRACE(len);
746  IntVec v;
747  Fill(&v, len);
748  v.clear();
749  EXPECT_EQ(0, v.size());
750  EXPECT_EQ(v.begin(), v.end());
751  }
752 }
753 
754 TEST(IntVec, Reserve) {
755  for (int len = 0; len < 20; len++) {
756  IntVec v;
757  Fill(&v, len);
758 
759  for (int newlen = 0; newlen < 100; newlen++) {
760  const int* start_rep = v.data();
761  v.reserve(newlen);
762  const int* final_rep = v.data();
763  if (newlen <= len) {
764  EXPECT_EQ(start_rep, final_rep);
765  }
766  EXPECT_LE(newlen, v.capacity());
767 
768  // Filling up to newlen should not change rep
769  while (v.size() < newlen) {
770  v.push_back(0);
771  }
772  EXPECT_EQ(final_rep, v.data());
773  }
774  }
775 }
776 
777 TEST(StringVec, SelfRefPushBack) {
778  std::vector<std::string> std_v;
780  const std::string s = "A quite long std::string to ensure heap.";
781  std_v.push_back(s);
782  v.push_back(s);
783  for (int i = 0; i < 20; ++i) {
784  EXPECT_THAT(v, ElementsAreArray(std_v));
785 
786  v.push_back(v.back());
787  std_v.push_back(std_v.back());
788  }
789  EXPECT_THAT(v, ElementsAreArray(std_v));
790 }
791 
792 TEST(StringVec, SelfRefPushBackWithMove) {
793  std::vector<std::string> std_v;
795  const std::string s = "A quite long std::string to ensure heap.";
796  std_v.push_back(s);
797  v.push_back(s);
798  for (int i = 0; i < 20; ++i) {
799  EXPECT_EQ(v.back(), std_v.back());
800 
801  v.push_back(std::move(v.back()));
802  std_v.push_back(std::move(std_v.back()));
803  }
804  EXPECT_EQ(v.back(), std_v.back());
805 }
806 
807 TEST(StringVec, SelfMove) {
808  const std::string s = "A quite long std::string to ensure heap.";
809  for (int len = 0; len < 20; len++) {
810  SCOPED_TRACE(len);
812  for (int i = 0; i < len; ++i) {
813  SCOPED_TRACE(i);
814  v.push_back(s);
815  }
816  // Indirection necessary to avoid compiler warning.
817  v = std::move(*(&v));
818  // Ensure that the inlined vector is still in a valid state by copying it.
819  // We don't expect specific contents since a self-move results in an
820  // unspecified valid state.
821  std::vector<std::string> copy(v.begin(), v.end());
822  }
823 }
824 
825 TEST(IntVec, Swap) {
826  for (int l1 = 0; l1 < 20; l1++) {
827  SCOPED_TRACE(l1);
828  for (int l2 = 0; l2 < 20; l2++) {
829  SCOPED_TRACE(l2);
830  IntVec a = Fill(l1, 0);
831  IntVec b = Fill(l2, 100);
832  {
833  using std::swap;
834  swap(a, b);
835  }
836  EXPECT_EQ(l1, b.size());
837  EXPECT_EQ(l2, a.size());
838  for (int i = 0; i < l1; i++) {
839  SCOPED_TRACE(i);
840  EXPECT_EQ(i, b[i]);
841  }
842  for (int i = 0; i < l2; i++) {
843  SCOPED_TRACE(i);
844  EXPECT_EQ(100 + i, a[i]);
845  }
846  }
847  }
848 }
849 
850 TYPED_TEST_P(InstanceTest, Swap) {
851  using Instance = TypeParam;
852  using InstanceVec = absl::InlinedVector<Instance, 8>;
853  for (int l1 = 0; l1 < 20; l1++) {
854  SCOPED_TRACE(l1);
855  for (int l2 = 0; l2 < 20; l2++) {
856  SCOPED_TRACE(l2);
857  InstanceTracker tracker;
858  InstanceVec a, b;
859  const size_t inlined_capacity = a.capacity();
860  auto min_len = std::min(l1, l2);
861  auto max_len = std::max(l1, l2);
862  for (int i = 0; i < l1; i++) a.push_back(Instance(i));
863  for (int i = 0; i < l2; i++) b.push_back(Instance(100+i));
864  EXPECT_EQ(tracker.instances(), l1 + l2);
865  tracker.ResetCopiesMovesSwaps();
866  {
867  using std::swap;
868  swap(a, b);
869  }
870  EXPECT_EQ(tracker.instances(), l1 + l2);
871  if (a.size() > inlined_capacity && b.size() > inlined_capacity) {
872  EXPECT_EQ(tracker.swaps(), 0); // Allocations are swapped.
873  EXPECT_EQ(tracker.moves(), 0);
874  } else if (a.size() <= inlined_capacity && b.size() <= inlined_capacity) {
875  EXPECT_EQ(tracker.swaps(), min_len);
876  EXPECT_EQ((tracker.moves() ? tracker.moves() : tracker.copies()),
877  max_len - min_len);
878  } else {
879  // One is allocated and the other isn't. The allocation is transferred
880  // without copying elements, and the inlined instances are copied/moved.
881  EXPECT_EQ(tracker.swaps(), 0);
882  EXPECT_EQ((tracker.moves() ? tracker.moves() : tracker.copies()),
883  min_len);
884  }
885 
886  EXPECT_EQ(l1, b.size());
887  EXPECT_EQ(l2, a.size());
888  for (int i = 0; i < l1; i++) {
889  EXPECT_EQ(i, b[i].value());
890  }
891  for (int i = 0; i < l2; i++) {
892  EXPECT_EQ(100 + i, a[i].value());
893  }
894  }
895  }
896 }
897 
898 TEST(IntVec, EqualAndNotEqual) {
899  IntVec a, b;
900  EXPECT_TRUE(a == b);
901  EXPECT_FALSE(a != b);
902 
903  a.push_back(3);
904  EXPECT_FALSE(a == b);
905  EXPECT_TRUE(a != b);
906 
907  b.push_back(3);
908  EXPECT_TRUE(a == b);
909  EXPECT_FALSE(a != b);
910 
911  b.push_back(7);
912  EXPECT_FALSE(a == b);
913  EXPECT_TRUE(a != b);
914 
915  a.push_back(6);
916  EXPECT_FALSE(a == b);
917  EXPECT_TRUE(a != b);
918 
919  a.clear();
920  b.clear();
921  for (int i = 0; i < 100; i++) {
922  a.push_back(i);
923  b.push_back(i);
924  EXPECT_TRUE(a == b);
925  EXPECT_FALSE(a != b);
926 
927  b[i] = b[i] + 1;
928  EXPECT_FALSE(a == b);
929  EXPECT_TRUE(a != b);
930 
931  b[i] = b[i] - 1; // Back to before
932  EXPECT_TRUE(a == b);
933  EXPECT_FALSE(a != b);
934  }
935 }
936 
937 TEST(IntVec, RelationalOps) {
938  IntVec a, b;
939  EXPECT_FALSE(a < b);
940  EXPECT_FALSE(b < a);
941  EXPECT_FALSE(a > b);
942  EXPECT_FALSE(b > a);
943  EXPECT_TRUE(a <= b);
944  EXPECT_TRUE(b <= a);
945  EXPECT_TRUE(a >= b);
946  EXPECT_TRUE(b >= a);
947  b.push_back(3);
948  EXPECT_TRUE(a < b);
949  EXPECT_FALSE(b < a);
950  EXPECT_FALSE(a > b);
951  EXPECT_TRUE(b > a);
952  EXPECT_TRUE(a <= b);
953  EXPECT_FALSE(b <= a);
954  EXPECT_FALSE(a >= b);
955  EXPECT_TRUE(b >= a);
956 }
957 
958 TYPED_TEST_P(InstanceTest, CountConstructorsDestructors) {
959  using Instance = TypeParam;
960  using InstanceVec = absl::InlinedVector<Instance, 8>;
961  InstanceTracker tracker;
962  for (int len = 0; len < 20; len++) {
963  SCOPED_TRACE(len);
964  tracker.ResetCopiesMovesSwaps();
965 
966  InstanceVec v;
967  const size_t inlined_capacity = v.capacity();
968  for (int i = 0; i < len; i++) {
969  v.push_back(Instance(i));
970  }
971  EXPECT_EQ(tracker.instances(), len);
972  EXPECT_GE(tracker.copies() + tracker.moves(),
973  len); // More due to reallocation.
974  tracker.ResetCopiesMovesSwaps();
975 
976  // Enlarging resize() must construct some objects
977  tracker.ResetCopiesMovesSwaps();
978  v.resize(len + 10, Instance(100));
979  EXPECT_EQ(tracker.instances(), len + 10);
980  if (len <= inlined_capacity && len + 10 > inlined_capacity) {
981  EXPECT_EQ(tracker.copies() + tracker.moves(), 10 + len);
982  } else {
983  // Only specify a minimum number of copies + moves. We don't want to
984  // depend on the reallocation policy here.
985  EXPECT_GE(tracker.copies() + tracker.moves(),
986  10); // More due to reallocation.
987  }
988 
989  // Shrinking resize() must destroy some objects
990  tracker.ResetCopiesMovesSwaps();
991  v.resize(len, Instance(100));
992  EXPECT_EQ(tracker.instances(), len);
993  EXPECT_EQ(tracker.copies(), 0);
994  EXPECT_EQ(tracker.moves(), 0);
995 
996  // reserve() must not increase the number of initialized objects
997  SCOPED_TRACE("reserve");
998  v.reserve(len+1000);
999  EXPECT_EQ(tracker.instances(), len);
1000  EXPECT_EQ(tracker.copies() + tracker.moves(), len);
1001 
1002  // pop_back() and erase() must destroy one object
1003  if (len > 0) {
1004  tracker.ResetCopiesMovesSwaps();
1005  v.pop_back();
1006  EXPECT_EQ(tracker.instances(), len - 1);
1007  EXPECT_EQ(tracker.copies(), 0);
1008  EXPECT_EQ(tracker.moves(), 0);
1009 
1010  if (!v.empty()) {
1011  tracker.ResetCopiesMovesSwaps();
1012  v.erase(v.begin());
1013  EXPECT_EQ(tracker.instances(), len - 2);
1014  EXPECT_EQ(tracker.copies() + tracker.moves(), len - 2);
1015  }
1016  }
1017 
1018  tracker.ResetCopiesMovesSwaps();
1019  int instances_before_empty_erase = tracker.instances();
1020  v.erase(v.begin(), v.begin());
1021  EXPECT_EQ(tracker.instances(), instances_before_empty_erase);
1022  EXPECT_EQ(tracker.copies() + tracker.moves(), 0);
1023  }
1024 }
1025 
1026 TYPED_TEST_P(InstanceTest, CountConstructorsDestructorsOnCopyConstruction) {
1027  using Instance = TypeParam;
1028  using InstanceVec = absl::InlinedVector<Instance, 8>;
1029  InstanceTracker tracker;
1030  for (int len = 0; len < 20; len++) {
1031  SCOPED_TRACE(len);
1032  tracker.ResetCopiesMovesSwaps();
1033 
1034  InstanceVec v;
1035  for (int i = 0; i < len; i++) {
1036  v.push_back(Instance(i));
1037  }
1038  EXPECT_EQ(tracker.instances(), len);
1039  EXPECT_GE(tracker.copies() + tracker.moves(),
1040  len); // More due to reallocation.
1041  tracker.ResetCopiesMovesSwaps();
1042  { // Copy constructor should create 'len' more instances.
1043  InstanceVec v_copy(v);
1044  EXPECT_EQ(tracker.instances(), len + len);
1045  EXPECT_EQ(tracker.copies(), len);
1046  EXPECT_EQ(tracker.moves(), 0);
1047  }
1048  EXPECT_EQ(tracker.instances(), len);
1049  }
1050 }
1051 
1052 TYPED_TEST_P(InstanceTest, CountConstructorsDestructorsOnMoveConstruction) {
1053  using Instance = TypeParam;
1054  using InstanceVec = absl::InlinedVector<Instance, 8>;
1055  InstanceTracker tracker;
1056  for (int len = 0; len < 20; len++) {
1057  SCOPED_TRACE(len);
1058  tracker.ResetCopiesMovesSwaps();
1059 
1060  InstanceVec v;
1061  const size_t inlined_capacity = v.capacity();
1062  for (int i = 0; i < len; i++) {
1063  v.push_back(Instance(i));
1064  }
1065  EXPECT_EQ(tracker.instances(), len);
1066  EXPECT_GE(tracker.copies() + tracker.moves(),
1067  len); // More due to reallocation.
1068  tracker.ResetCopiesMovesSwaps();
1069  {
1070  InstanceVec v_copy(std::move(v));
1071  if (len > inlined_capacity) {
1072  // Allocation is moved as a whole.
1073  EXPECT_EQ(tracker.instances(), len);
1074  EXPECT_EQ(tracker.live_instances(), len);
1075  // Tests an implementation detail, don't rely on this in your code.
1076  EXPECT_EQ(v.size(), 0); // NOLINT misc-use-after-move
1077  EXPECT_EQ(tracker.copies(), 0);
1078  EXPECT_EQ(tracker.moves(), 0);
1079  } else {
1080  EXPECT_EQ(tracker.instances(), len + len);
1081  if (Instance::supports_move()) {
1082  EXPECT_EQ(tracker.live_instances(), len);
1083  EXPECT_EQ(tracker.copies(), 0);
1084  EXPECT_EQ(tracker.moves(), len);
1085  } else {
1086  EXPECT_EQ(tracker.live_instances(), len + len);
1087  EXPECT_EQ(tracker.copies(), len);
1088  EXPECT_EQ(tracker.moves(), 0);
1089  }
1090  }
1091  EXPECT_EQ(tracker.swaps(), 0);
1092  }
1093  }
1094 }
1095 
1096 TYPED_TEST_P(InstanceTest, CountConstructorsDestructorsOnAssignment) {
1097  using Instance = TypeParam;
1098  using InstanceVec = absl::InlinedVector<Instance, 8>;
1099  InstanceTracker tracker;
1100  for (int len = 0; len < 20; len++) {
1101  SCOPED_TRACE(len);
1102  for (int longorshort = 0; longorshort <= 1; ++longorshort) {
1103  SCOPED_TRACE(longorshort);
1104  tracker.ResetCopiesMovesSwaps();
1105 
1106  InstanceVec longer, shorter;
1107  for (int i = 0; i < len; i++) {
1108  longer.push_back(Instance(i));
1109  shorter.push_back(Instance(i));
1110  }
1111  longer.push_back(Instance(len));
1112  EXPECT_EQ(tracker.instances(), len + len + 1);
1113  EXPECT_GE(tracker.copies() + tracker.moves(),
1114  len + len + 1); // More due to reallocation.
1115 
1116  tracker.ResetCopiesMovesSwaps();
1117  if (longorshort) {
1118  shorter = longer;
1119  EXPECT_EQ(tracker.instances(), (len + 1) + (len + 1));
1120  EXPECT_GE(tracker.copies() + tracker.moves(),
1121  len + 1); // More due to reallocation.
1122  } else {
1123  longer = shorter;
1124  EXPECT_EQ(tracker.instances(), len + len);
1125  EXPECT_EQ(tracker.copies() + tracker.moves(), len);
1126  }
1127  }
1128  }
1129 }
1130 
1131 TYPED_TEST_P(InstanceTest, CountConstructorsDestructorsOnMoveAssignment) {
1132  using Instance = TypeParam;
1133  using InstanceVec = absl::InlinedVector<Instance, 8>;
1134  InstanceTracker tracker;
1135  for (int len = 0; len < 20; len++) {
1136  SCOPED_TRACE(len);
1137  for (int longorshort = 0; longorshort <= 1; ++longorshort) {
1138  SCOPED_TRACE(longorshort);
1139  tracker.ResetCopiesMovesSwaps();
1140 
1141  InstanceVec longer, shorter;
1142  const int inlined_capacity = longer.capacity();
1143  for (int i = 0; i < len; i++) {
1144  longer.push_back(Instance(i));
1145  shorter.push_back(Instance(i));
1146  }
1147  longer.push_back(Instance(len));
1148  EXPECT_EQ(tracker.instances(), len + len + 1);
1149  EXPECT_GE(tracker.copies() + tracker.moves(),
1150  len + len + 1); // More due to reallocation.
1151 
1152  tracker.ResetCopiesMovesSwaps();
1153  int src_len;
1154  if (longorshort) {
1155  src_len = len + 1;
1156  shorter = std::move(longer);
1157  } else {
1158  src_len = len;
1159  longer = std::move(shorter);
1160  }
1161  if (src_len > inlined_capacity) {
1162  // Allocation moved as a whole.
1163  EXPECT_EQ(tracker.instances(), src_len);
1164  EXPECT_EQ(tracker.live_instances(), src_len);
1165  EXPECT_EQ(tracker.copies(), 0);
1166  EXPECT_EQ(tracker.moves(), 0);
1167  } else {
1168  // Elements are all copied.
1169  EXPECT_EQ(tracker.instances(), src_len + src_len);
1170  if (Instance::supports_move()) {
1171  EXPECT_EQ(tracker.copies(), 0);
1172  EXPECT_EQ(tracker.moves(), src_len);
1173  EXPECT_EQ(tracker.live_instances(), src_len);
1174  } else {
1175  EXPECT_EQ(tracker.copies(), src_len);
1176  EXPECT_EQ(tracker.moves(), 0);
1177  EXPECT_EQ(tracker.live_instances(), src_len + src_len);
1178  }
1179  }
1180  EXPECT_EQ(tracker.swaps(), 0);
1181  }
1182  }
1183 }
1184 
1185 TEST(CountElemAssign, SimpleTypeWithInlineBacking) {
1186  for (size_t original_size = 0; original_size <= 5; ++original_size) {
1187  SCOPED_TRACE(original_size);
1188  // Original contents are [12345, 12345, ...]
1189  std::vector<int> original_contents(original_size, 12345);
1190 
1191  absl::InlinedVector<int, 2> v(original_contents.begin(),
1192  original_contents.end());
1193  v.assign(2, 123);
1194  EXPECT_THAT(v, AllOf(SizeIs(2), ElementsAre(123, 123)));
1195  if (original_size <= 2) {
1196  // If the original had inline backing, it should stay inline.
1197  EXPECT_EQ(2, v.capacity());
1198  }
1199  }
1200 }
1201 
1202 TEST(CountElemAssign, SimpleTypeWithAllocation) {
1203  for (size_t original_size = 0; original_size <= 5; ++original_size) {
1204  SCOPED_TRACE(original_size);
1205  // Original contents are [12345, 12345, ...]
1206  std::vector<int> original_contents(original_size, 12345);
1207 
1208  absl::InlinedVector<int, 2> v(original_contents.begin(),
1209  original_contents.end());
1210  v.assign(3, 123);
1211  EXPECT_THAT(v, AllOf(SizeIs(3), ElementsAre(123, 123, 123)));
1212  EXPECT_LE(v.size(), v.capacity());
1213  }
1214 }
1215 
1216 TYPED_TEST_P(InstanceTest, CountElemAssignInlineBacking) {
1217  using Instance = TypeParam;
1218  for (size_t original_size = 0; original_size <= 5; ++original_size) {
1219  SCOPED_TRACE(original_size);
1220  // Original contents are [12345, 12345, ...]
1221  std::vector<Instance> original_contents(original_size, Instance(12345));
1222 
1223  absl::InlinedVector<Instance, 2> v(original_contents.begin(),
1224  original_contents.end());
1225  v.assign(2, Instance(123));
1226  EXPECT_THAT(v, AllOf(SizeIs(2), ElementsAre(ValueIs(123), ValueIs(123))));
1227  if (original_size <= 2) {
1228  // If the original had inline backing, it should stay inline.
1229  EXPECT_EQ(2, v.capacity());
1230  }
1231  }
1232 }
1233 
1234 template <typename Instance>
1235 void InstanceCountElemAssignWithAllocationTest() {
1236  for (size_t original_size = 0; original_size <= 5; ++original_size) {
1237  SCOPED_TRACE(original_size);
1238  // Original contents are [12345, 12345, ...]
1239  std::vector<Instance> original_contents(original_size, Instance(12345));
1240 
1241  absl::InlinedVector<Instance, 2> v(original_contents.begin(),
1242  original_contents.end());
1243  v.assign(3, Instance(123));
1244  EXPECT_THAT(v,
1245  AllOf(SizeIs(3),
1246  ElementsAre(ValueIs(123), ValueIs(123), ValueIs(123))));
1247  EXPECT_LE(v.size(), v.capacity());
1248  }
1249 }
1250 TEST(CountElemAssign, WithAllocationCopyableInstance) {
1251  InstanceCountElemAssignWithAllocationTest<CopyableOnlyInstance>();
1252 }
1253 TEST(CountElemAssign, WithAllocationCopyableMovableInstance) {
1254  InstanceCountElemAssignWithAllocationTest<CopyableMovableInstance>();
1255 }
1256 
1257 TEST(RangedConstructor, SimpleType) {
1258  std::vector<int> source_v = {4, 5, 6};
1259  // First try to fit in inline backing
1260  absl::InlinedVector<int, 4> v(source_v.begin(), source_v.end());
1261  EXPECT_EQ(3, v.size());
1262  EXPECT_EQ(4, v.capacity()); // Indication that we're still on inlined storage
1263  EXPECT_EQ(4, v[0]);
1264  EXPECT_EQ(5, v[1]);
1265  EXPECT_EQ(6, v[2]);
1266 
1267  // Now, force a re-allocate
1268  absl::InlinedVector<int, 2> realloc_v(source_v.begin(), source_v.end());
1269  EXPECT_EQ(3, realloc_v.size());
1270  EXPECT_LT(2, realloc_v.capacity());
1271  EXPECT_EQ(4, realloc_v[0]);
1272  EXPECT_EQ(5, realloc_v[1]);
1273  EXPECT_EQ(6, realloc_v[2]);
1274 }
1275 
1276 // Test for ranged constructors using Instance as the element type and
1277 // SourceContainer as the source container type.
1278 template <typename Instance, typename SourceContainer, int inlined_capacity>
1279 void InstanceRangedConstructorTestForContainer() {
1280  InstanceTracker tracker;
1281  SourceContainer source_v = {Instance(0), Instance(1)};
1282  tracker.ResetCopiesMovesSwaps();
1284  source_v.end());
1285  EXPECT_EQ(2, v.size());
1286  EXPECT_LT(1, v.capacity());
1287  EXPECT_EQ(0, v[0].value());
1288  EXPECT_EQ(1, v[1].value());
1289  EXPECT_EQ(tracker.copies(), 2);
1290  EXPECT_EQ(tracker.moves(), 0);
1291 }
1292 
1293 template <typename Instance, int inlined_capacity>
1294 void InstanceRangedConstructorTestWithCapacity() {
1295  // Test with const and non-const, random access and non-random-access sources.
1296  // TODO(bsamwel): Test with an input iterator source.
1297  {
1298  SCOPED_TRACE("std::list");
1299  InstanceRangedConstructorTestForContainer<Instance, std::list<Instance>,
1300  inlined_capacity>();
1301  {
1302  SCOPED_TRACE("const std::list");
1303  InstanceRangedConstructorTestForContainer<
1304  Instance, const std::list<Instance>, inlined_capacity>();
1305  }
1306  {
1307  SCOPED_TRACE("std::vector");
1308  InstanceRangedConstructorTestForContainer<Instance, std::vector<Instance>,
1309  inlined_capacity>();
1310  }
1311  {
1312  SCOPED_TRACE("const std::vector");
1313  InstanceRangedConstructorTestForContainer<
1314  Instance, const std::vector<Instance>, inlined_capacity>();
1315  }
1316  }
1317 }
1318 
1319 TYPED_TEST_P(InstanceTest, RangedConstructor) {
1320  using Instance = TypeParam;
1321  SCOPED_TRACE("capacity=1");
1322  InstanceRangedConstructorTestWithCapacity<Instance, 1>();
1323  SCOPED_TRACE("capacity=2");
1324  InstanceRangedConstructorTestWithCapacity<Instance, 2>();
1325 }
1326 
1327 TEST(RangedConstructor, ElementsAreConstructed) {
1328  std::vector<std::string> source_v = {"cat", "dog"};
1329 
1330  // Force expansion and re-allocation of v. Ensures that when the vector is
1331  // expanded that new elements are constructed.
1332  absl::InlinedVector<std::string, 1> v(source_v.begin(), source_v.end());
1333  EXPECT_EQ("cat", v[0]);
1334  EXPECT_EQ("dog", v[1]);
1335 }
1336 
1337 TEST(RangedAssign, SimpleType) {
1338  // Test for all combinations of original sizes (empty and non-empty inline,
1339  // and out of line) and target sizes.
1340  for (size_t original_size = 0; original_size <= 5; ++original_size) {
1341  SCOPED_TRACE(original_size);
1342  // Original contents are [12345, 12345, ...]
1343  std::vector<int> original_contents(original_size, 12345);
1344 
1345  for (size_t target_size = 0; target_size <= 5; ++target_size) {
1346  SCOPED_TRACE(target_size);
1347 
1348  // New contents are [3, 4, ...]
1349  std::vector<int> new_contents;
1350  for (size_t i = 0; i < target_size; ++i) {
1351  new_contents.push_back(i + 3);
1352  }
1353 
1354  absl::InlinedVector<int, 3> v(original_contents.begin(),
1355  original_contents.end());
1356  v.assign(new_contents.begin(), new_contents.end());
1357 
1358  EXPECT_EQ(new_contents.size(), v.size());
1359  EXPECT_LE(new_contents.size(), v.capacity());
1360  if (target_size <= 3 && original_size <= 3) {
1361  // Storage should stay inline when target size is small.
1362  EXPECT_EQ(3, v.capacity());
1363  }
1364  EXPECT_THAT(v, ElementsAreArray(new_contents));
1365  }
1366  }
1367 }
1368 
1369 // Returns true if lhs and rhs have the same value.
1370 template <typename Instance>
1371 static bool InstanceValuesEqual(const Instance& lhs, const Instance& rhs) {
1372  return lhs.value() == rhs.value();
1373 }
1374 
1375 // Test for ranged assign() using Instance as the element type and
1376 // SourceContainer as the source container type.
1377 template <typename Instance, typename SourceContainer>
1378 void InstanceRangedAssignTestForContainer() {
1379  // Test for all combinations of original sizes (empty and non-empty inline,
1380  // and out of line) and target sizes.
1381  for (size_t original_size = 0; original_size <= 5; ++original_size) {
1382  SCOPED_TRACE(original_size);
1383  // Original contents are [12345, 12345, ...]
1384  std::vector<Instance> original_contents(original_size, Instance(12345));
1385 
1386  for (size_t target_size = 0; target_size <= 5; ++target_size) {
1387  SCOPED_TRACE(target_size);
1388 
1389  // New contents are [3, 4, ...]
1390  // Generate data using a non-const container, because SourceContainer
1391  // itself may be const.
1392  // TODO(bsamwel): Test with an input iterator.
1393  std::vector<Instance> new_contents_in;
1394  for (size_t i = 0; i < target_size; ++i) {
1395  new_contents_in.push_back(Instance(i + 3));
1396  }
1397  SourceContainer new_contents(new_contents_in.begin(),
1398  new_contents_in.end());
1399 
1400  absl::InlinedVector<Instance, 3> v(original_contents.begin(),
1401  original_contents.end());
1402  v.assign(new_contents.begin(), new_contents.end());
1403 
1404  EXPECT_EQ(new_contents.size(), v.size());
1405  EXPECT_LE(new_contents.size(), v.capacity());
1406  if (target_size <= 3 && original_size <= 3) {
1407  // Storage should stay inline when target size is small.
1408  EXPECT_EQ(3, v.capacity());
1409  }
1410  EXPECT_TRUE(std::equal(v.begin(), v.end(), new_contents.begin(),
1411  InstanceValuesEqual<Instance>));
1412  }
1413  }
1414 }
1415 
1416 TYPED_TEST_P(InstanceTest, RangedAssign) {
1417  using Instance = TypeParam;
1418  // Test with const and non-const, random access and non-random-access sources.
1419  // TODO(bsamwel): Test with an input iterator source.
1420  SCOPED_TRACE("std::list");
1421  InstanceRangedAssignTestForContainer<Instance, std::list<Instance>>();
1422  SCOPED_TRACE("const std::list");
1423  InstanceRangedAssignTestForContainer<Instance, const std::list<Instance>>();
1424  SCOPED_TRACE("std::vector");
1425  InstanceRangedAssignTestForContainer<Instance, std::vector<Instance>>();
1426  SCOPED_TRACE("const std::vector");
1427  InstanceRangedAssignTestForContainer<Instance, const std::vector<Instance>>();
1428 }
1429 
1430 TEST(InitializerListConstructor, SimpleTypeWithInlineBacking) {
1431  EXPECT_THAT((absl::InlinedVector<int, 4>{4, 5, 6}),
1432  AllOf(SizeIs(3), CapacityIs(4), ElementsAre(4, 5, 6)));
1433 }
1434 
1435 TEST(InitializerListConstructor, SimpleTypeWithReallocationRequired) {
1436  EXPECT_THAT((absl::InlinedVector<int, 2>{4, 5, 6}),
1437  AllOf(SizeIs(3), CapacityIs(Gt(2)), ElementsAre(4, 5, 6)));
1438 }
1439 
1440 TEST(InitializerListConstructor, DisparateTypesInList) {
1441  EXPECT_THAT((absl::InlinedVector<int, 2>{-7, 8ULL}), ElementsAre(-7, 8));
1442 
1443  EXPECT_THAT((absl::InlinedVector<std::string, 2>{"foo", std::string("bar")}),
1444  ElementsAre("foo", "bar"));
1445 }
1446 
1447 TEST(InitializerListConstructor, ComplexTypeWithInlineBacking) {
1449  CopyableMovableInstance(0)}),
1450  AllOf(SizeIs(1), CapacityIs(1), ElementsAre(ValueIs(0))));
1451 }
1452 
1453 TEST(InitializerListConstructor, ComplexTypeWithReallocationRequired) {
1454  EXPECT_THAT(
1456  CopyableMovableInstance(0), CopyableMovableInstance(1)}),
1457  AllOf(SizeIs(2), CapacityIs(Gt(1)), ElementsAre(ValueIs(0), ValueIs(1))));
1458 }
1459 
1460 TEST(InitializerListAssign, SimpleTypeFitsInlineBacking) {
1461  for (size_t original_size = 0; original_size <= 4; ++original_size) {
1462  SCOPED_TRACE(original_size);
1463 
1464  absl::InlinedVector<int, 2> v1(original_size, 12345);
1465  const size_t original_capacity_v1 = v1.capacity();
1466  v1.assign({3});
1467  EXPECT_THAT(
1468  v1, AllOf(SizeIs(1), CapacityIs(original_capacity_v1), ElementsAre(3)));
1469 
1470  absl::InlinedVector<int, 2> v2(original_size, 12345);
1471  const size_t original_capacity_v2 = v2.capacity();
1472  v2 = {3};
1473  EXPECT_THAT(
1474  v2, AllOf(SizeIs(1), CapacityIs(original_capacity_v2), ElementsAre(3)));
1475  }
1476 }
1477 
1478 TEST(InitializerListAssign, SimpleTypeDoesNotFitInlineBacking) {
1479  for (size_t original_size = 0; original_size <= 4; ++original_size) {
1480  SCOPED_TRACE(original_size);
1481  absl::InlinedVector<int, 2> v1(original_size, 12345);
1482  v1.assign({3, 4, 5});
1483  EXPECT_THAT(v1, AllOf(SizeIs(3), ElementsAre(3, 4, 5)));
1484  EXPECT_LE(3, v1.capacity());
1485 
1486  absl::InlinedVector<int, 2> v2(original_size, 12345);
1487  v2 = {3, 4, 5};
1488  EXPECT_THAT(v2, AllOf(SizeIs(3), ElementsAre(3, 4, 5)));
1489  EXPECT_LE(3, v2.capacity());
1490  }
1491 }
1492 
1493 TEST(InitializerListAssign, DisparateTypesInList) {
1495  v_int1.assign({-7, 8ULL});
1496  EXPECT_THAT(v_int1, ElementsAre(-7, 8));
1497 
1499  v_int2 = {-7, 8ULL};
1500  EXPECT_THAT(v_int2, ElementsAre(-7, 8));
1501 
1503  v_string1.assign({"foo", std::string("bar")});
1504  EXPECT_THAT(v_string1, ElementsAre("foo", "bar"));
1505 
1507  v_string2 = {"foo", std::string("bar")};
1508  EXPECT_THAT(v_string2, ElementsAre("foo", "bar"));
1509 }
1510 
1511 TYPED_TEST_P(InstanceTest, InitializerListAssign) {
1512  using Instance = TypeParam;
1513  for (size_t original_size = 0; original_size <= 4; ++original_size) {
1514  SCOPED_TRACE(original_size);
1515  absl::InlinedVector<Instance, 2> v(original_size, Instance(12345));
1516  const size_t original_capacity = v.capacity();
1517  v.assign({Instance(3)});
1518  EXPECT_THAT(v, AllOf(SizeIs(1), CapacityIs(original_capacity),
1519  ElementsAre(ValueIs(3))));
1520  }
1521  for (size_t original_size = 0; original_size <= 4; ++original_size) {
1522  SCOPED_TRACE(original_size);
1523  absl::InlinedVector<Instance, 2> v(original_size, Instance(12345));
1524  v.assign({Instance(3), Instance(4), Instance(5)});
1525  EXPECT_THAT(v, AllOf(SizeIs(3),
1526  ElementsAre(ValueIs(3), ValueIs(4), ValueIs(5))));
1527  EXPECT_LE(3, v.capacity());
1528  }
1529 }
1530 
1531 REGISTER_TYPED_TEST_CASE_P(InstanceTest, Swap, CountConstructorsDestructors,
1532  CountConstructorsDestructorsOnCopyConstruction,
1533  CountConstructorsDestructorsOnMoveConstruction,
1534  CountConstructorsDestructorsOnAssignment,
1535  CountConstructorsDestructorsOnMoveAssignment,
1536  CountElemAssignInlineBacking, RangedConstructor,
1537  RangedAssign, InitializerListAssign);
1538 
1539 using InstanceTypes =
1540  ::testing::Types<CopyableOnlyInstance, CopyableMovableInstance>;
1541 INSTANTIATE_TYPED_TEST_CASE_P(InstanceTestOnTypes, InstanceTest, InstanceTypes);
1542 
1543 TEST(DynamicVec, DynamicVecCompiles) {
1544  DynamicVec v;
1545  (void)v;
1546 }
1547 
1548 TEST(AllocatorSupportTest, Constructors) {
1549  using MyAlloc = CountingAllocator<int>;
1550  using AllocVec = absl::InlinedVector<int, 4, MyAlloc>;
1551  const int ia[] = { 0, 1, 2, 3, 4, 5, 6, 7 };
1552  int64_t allocated = 0;
1553  MyAlloc alloc(&allocated);
1554  { AllocVec ABSL_ATTRIBUTE_UNUSED v; }
1555  { AllocVec ABSL_ATTRIBUTE_UNUSED v(alloc); }
1556  { AllocVec ABSL_ATTRIBUTE_UNUSED v(ia, ia + ABSL_ARRAYSIZE(ia), alloc); }
1557  { AllocVec ABSL_ATTRIBUTE_UNUSED v({1, 2, 3}, alloc); }
1558 
1559  AllocVec v2;
1560  { AllocVec ABSL_ATTRIBUTE_UNUSED v(v2, alloc); }
1561  { AllocVec ABSL_ATTRIBUTE_UNUSED v(std::move(v2), alloc); }
1562 }
1563 
1564 TEST(AllocatorSupportTest, CountAllocations) {
1565  using MyAlloc = CountingAllocator<int>;
1566  using AllocVec = absl::InlinedVector<int, 4, MyAlloc>;
1567  const int ia[] = { 0, 1, 2, 3, 4, 5, 6, 7 };
1568  int64_t allocated = 0;
1569  MyAlloc alloc(&allocated);
1570  {
1571  AllocVec ABSL_ATTRIBUTE_UNUSED v(ia, ia + 4, alloc);
1572  EXPECT_THAT(allocated, 0);
1573  }
1574  EXPECT_THAT(allocated, 0);
1575  {
1576  AllocVec ABSL_ATTRIBUTE_UNUSED v(ia, ia + ABSL_ARRAYSIZE(ia), alloc);
1577  EXPECT_THAT(allocated, v.size() * sizeof(int));
1578  }
1579  EXPECT_THAT(allocated, 0);
1580  {
1581  AllocVec v(4, 1, alloc);
1582  EXPECT_THAT(allocated, 0);
1583 
1584  int64_t allocated2 = 0;
1585  MyAlloc alloc2(&allocated2);
1586  AllocVec v2(v, alloc2);
1587  EXPECT_THAT(allocated2, 0);
1588 
1589  int64_t allocated3 = 0;
1590  MyAlloc alloc3(&allocated3);
1591  AllocVec v3(std::move(v), alloc3);
1592  EXPECT_THAT(allocated3, 0);
1593  }
1594  EXPECT_THAT(allocated, 0);
1595  {
1596  AllocVec v(8, 2, alloc);
1597  EXPECT_THAT(allocated, v.size() * sizeof(int));
1598 
1599  int64_t allocated2 = 0;
1600  MyAlloc alloc2(&allocated2);
1601  AllocVec v2(v, alloc2);
1602  EXPECT_THAT(allocated2, v2.size() * sizeof(int));
1603 
1604  int64_t allocated3 = 0;
1605  MyAlloc alloc3(&allocated3);
1606  AllocVec v3(std::move(v), alloc3);
1607  EXPECT_THAT(allocated3, v3.size() * sizeof(int));
1608  }
1609  EXPECT_EQ(allocated, 0);
1610  {
1611  // Test shrink_to_fit deallocations.
1612  AllocVec v(8, 2, alloc);
1613  EXPECT_EQ(allocated, 8 * sizeof(int));
1614  v.resize(5);
1615  EXPECT_EQ(allocated, 8 * sizeof(int));
1616  v.shrink_to_fit();
1617  EXPECT_EQ(allocated, 5 * sizeof(int));
1618  v.resize(4);
1619  EXPECT_EQ(allocated, 5 * sizeof(int));
1620  v.shrink_to_fit();
1621  EXPECT_EQ(allocated, 0);
1622  }
1623 }
1624 
1625 TEST(AllocatorSupportTest, SwapBothAllocated) {
1626  using MyAlloc = CountingAllocator<int>;
1627  using AllocVec = absl::InlinedVector<int, 4, MyAlloc>;
1628  int64_t allocated1 = 0;
1629  int64_t allocated2 = 0;
1630  {
1631  const int ia1[] = { 0, 1, 2, 3, 4, 5, 6, 7 };
1632  const int ia2[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
1633  MyAlloc a1(&allocated1);
1634  MyAlloc a2(&allocated2);
1635  AllocVec v1(ia1, ia1 + ABSL_ARRAYSIZE(ia1), a1);
1636  AllocVec v2(ia2, ia2 + ABSL_ARRAYSIZE(ia2), a2);
1637  EXPECT_LT(v1.capacity(), v2.capacity());
1638  EXPECT_THAT(allocated1, v1.capacity() * sizeof(int));
1639  EXPECT_THAT(allocated2, v2.capacity() * sizeof(int));
1640  v1.swap(v2);
1641  EXPECT_THAT(v1, ElementsAreArray(ia2));
1642  EXPECT_THAT(v2, ElementsAreArray(ia1));
1643  EXPECT_THAT(allocated1, v2.capacity() * sizeof(int));
1644  EXPECT_THAT(allocated2, v1.capacity() * sizeof(int));
1645  }
1646  EXPECT_THAT(allocated1, 0);
1647  EXPECT_THAT(allocated2, 0);
1648 }
1649 
1650 TEST(AllocatorSupportTest, SwapOneAllocated) {
1651  using MyAlloc = CountingAllocator<int>;
1652  using AllocVec = absl::InlinedVector<int, 4, MyAlloc>;
1653  int64_t allocated1 = 0;
1654  int64_t allocated2 = 0;
1655  {
1656  const int ia1[] = { 0, 1, 2, 3, 4, 5, 6, 7 };
1657  const int ia2[] = { 0, 1, 2, 3 };
1658  MyAlloc a1(&allocated1);
1659  MyAlloc a2(&allocated2);
1660  AllocVec v1(ia1, ia1 + ABSL_ARRAYSIZE(ia1), a1);
1661  AllocVec v2(ia2, ia2 + ABSL_ARRAYSIZE(ia2), a2);
1662  EXPECT_THAT(allocated1, v1.capacity() * sizeof(int));
1663  EXPECT_THAT(allocated2, 0);
1664  v1.swap(v2);
1665  EXPECT_THAT(v1, ElementsAreArray(ia2));
1666  EXPECT_THAT(v2, ElementsAreArray(ia1));
1667  EXPECT_THAT(allocated1, v2.capacity() * sizeof(int));
1668  EXPECT_THAT(allocated2, 0);
1669  EXPECT_TRUE(v2.get_allocator() == a1);
1670  EXPECT_TRUE(v1.get_allocator() == a2);
1671  }
1672  EXPECT_THAT(allocated1, 0);
1673  EXPECT_THAT(allocated2, 0);
1674 }
1675 
1676 TEST(AllocatorSupportTest, ScopedAllocatorWorks) {
1677  using StdVector = std::vector<int, CountingAllocator<int>>;
1678  using MyAlloc =
1679  std::scoped_allocator_adaptor<CountingAllocator<StdVector>>;
1681 
1682  // MSVC 2017's std::vector allocates different amounts of memory in debug
1683  // versus opt mode.
1684  int64_t test_allocated = 0;
1685  StdVector v(CountingAllocator<int>{&test_allocated});
1686  // The amount of memory allocated by a default constructed vector<int>
1687  auto default_std_vec_allocated = test_allocated;
1688  v.push_back(1);
1689  // The amound of memory allocated by a copy-constructed vector<int> with one
1690  // element.
1691  int64_t one_element_std_vec_copy_allocated = test_allocated;
1692 
1693  int64_t allocated = 0;
1694  AllocVec vec(MyAlloc{CountingAllocator<StdVector>{&allocated}});
1695  EXPECT_EQ(allocated, 0);
1696 
1697  // This default constructs a vector<int>, but the allocator should pass itself
1698  // into the vector<int>, so check allocation compared to that.
1699  // The absl::InlinedVector does not allocate any memory.
1700  // The vector<int> may allocate any memory.
1701  auto expected = default_std_vec_allocated;
1702  vec.resize(1);
1703  EXPECT_EQ(allocated, expected);
1704 
1705  // We make vector<int> allocate memory.
1706  // It must go through the allocator even though we didn't construct the
1707  // vector directly. This assumes that vec[0] doesn't need to grow its
1708  // allocation.
1709  expected += sizeof(int);
1710  vec[0].push_back(1);
1711  EXPECT_EQ(allocated, expected);
1712 
1713  // Another allocating vector.
1714  expected += one_element_std_vec_copy_allocated;
1715  vec.push_back(vec[0]);
1716  EXPECT_EQ(allocated, expected);
1717 
1718  // Overflow the inlined memory.
1719  // The absl::InlinedVector will now allocate.
1720  expected += sizeof(StdVector) * 8 + default_std_vec_allocated * 3;
1721  vec.resize(5);
1722  EXPECT_EQ(allocated, expected);
1723 
1724  // Adding one more in external mode should also work.
1725  expected += one_element_std_vec_copy_allocated;
1726  vec.push_back(vec[0]);
1727  EXPECT_EQ(allocated, expected);
1728 
1729  // And extending these should still work. This assumes that vec[0] does not
1730  // need to grow its allocation.
1731  expected += sizeof(int);
1732  vec[0].push_back(1);
1733  EXPECT_EQ(allocated, expected);
1734 
1735  vec.clear();
1736  EXPECT_EQ(allocated, 0);
1737 }
1738 
1739 TEST(AllocatorSupportTest, SizeAllocConstructor) {
1740  constexpr int inlined_size = 4;
1741  using Alloc = CountingAllocator<int>;
1743 
1744  {
1745  auto len = inlined_size / 2;
1746  int64_t allocated = 0;
1747  auto v = AllocVec(len, Alloc(&allocated));
1748 
1749  // Inline storage used; allocator should not be invoked
1750  EXPECT_THAT(allocated, 0);
1751  EXPECT_THAT(v, AllOf(SizeIs(len), Each(0)));
1752  }
1753 
1754  {
1755  auto len = inlined_size * 2;
1756  int64_t allocated = 0;
1757  auto v = AllocVec(len, Alloc(&allocated));
1758 
1759  // Out of line storage used; allocation of 8 elements expected
1760  EXPECT_THAT(allocated, len * sizeof(int));
1761  EXPECT_THAT(v, AllOf(SizeIs(len), Each(0)));
1762  }
1763 }
1764 
1765 TEST(InlinedVectorTest, AbslHashValueWorks) {
1766  using V = absl::InlinedVector<int, 4>;
1767  std::vector<V> cases;
1768 
1769  // Generate a variety of vectors some of these are small enough for the inline
1770  // space but are stored out of line.
1771  for (int i = 0; i < 10; ++i) {
1772  V v;
1773  for (int j = 0; j < i; ++j) {
1774  v.push_back(j);
1775  }
1776  cases.push_back(v);
1777  v.resize(i % 4);
1778  cases.push_back(v);
1779  }
1780 
1781  EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(cases));
1782 }
1783 
1784 } // anonymous namespace
int v
Definition: variant_test.cc:81
iterator emplace(const_iterator pos, Args &&...args)
#define ABSL_ATTRIBUTE_UNUSED
Definition: attributes.h:549
int * tracker
iterator end() noexcept
TYPED_TEST_SUITE_P(ConstructorTest)
T::first_type a1
int * counter
reference emplace_back(Args &&...args)
void reserve(size_type n)
void clear() noexcept
#define ABSL_BASE_INTERNAL_EXPECT_FAIL(expr, exception_t, text)
iterator insert(const_iterator pos, const_reference v)
#define ABSL_RAW_CHECK(condition, message)
Definition: raw_logging.h:57
bool operator==(const absl::InlinedVector< T, N, A > &a, const absl::InlinedVector< T, N, A > &b)
void Swap(T &lhs, T &rhs) noexcept(IsNothrowSwappable< T >::value)
Definition: type_traits.h:673
size_t value
void pop_back() noexcept
size_type capacity() const noexcept
size_type size() const noexcept
void swap(absl::InlinedVector< T, N, A > &a, absl::InlinedVector< T, N, A > &b) noexcept(noexcept(a.swap(b)))
ABSL_MUST_USE_RESULT testing::AssertionResult VerifyTypeImplementsAbslHashCorrectly(const Container &values)
Definition: hash_testing.h:344
void resize(size_type n)
T::first_type a2
constexpr bool AllOf()
Definition: checker.h:20
void assign(size_type n, const_reference v)
void * arg
Definition: mutex.cc:292
#define ABSL_ARRAYSIZE(array)
Definition: macros.h:42
TYPED_TEST_P(ConstructorTest, NoArgs)
TEST(Symbolize, Unimplemented)
uint64_t b
Definition: layout_test.cc:50
std::unique_ptr< unsigned char[]> p_
std::allocator< int > alloc
iterator begin() noexcept
constexpr absl::remove_reference_t< T > && move(T &&t) noexcept
Definition: utility.h:219
REGISTER_TYPED_TEST_CASE_P(ConstructorTest, NoArgs, BucketCount, BucketCountHash, BucketCountHashEqual, BucketCountHashEqualAlloc, BucketCountAlloc, BucketCountHashAlloc, Alloc, InputIteratorBucketHashEqualAlloc, InputIteratorBucketAlloc, InputIteratorBucketHashAlloc, CopyConstructor, CopyConstructorAlloc, MoveConstructor, MoveConstructorAlloc, InitializerListBucketHashEqualAlloc, InitializerListBucketAlloc, InitializerListBucketHashAlloc, Assignment, MoveAssignment, AssignmentFromInitializerList, AssignmentOverwritesExisting, MoveAssignmentOverwritesExisting, AssignmentFromInitializerListOverwritesExisting, AssignmentOnSelf)
void push_back(const_reference v)
iterator erase(const_iterator pos)


abseil_cpp
Author(s):
autogenerated on Tue Jun 18 2019 19:44:36