// Copyright 2017 The Abseil Authors. // // Licensed under the Apache License, Version 2.0 (the "License"); // you may not use this file except in compliance with the License. // You may obtain a copy of the License at // // http://www.apache.org/licenses/LICENSE-2.0 // // Unless required by applicable law or agreed to in writing, software // distributed under the License is distributed on an "AS IS" BASIS, // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. // See the License for the specific language governing permissions and // limitations under the License. #include "absl/container/inlined_vector.h" #include <algorithm> #include <forward_list> #include <list> #include <memory> #include <scoped_allocator> #include <sstream> #include <stdexcept> #include <string> #include <vector> #include "gmock/gmock.h" #include "gtest/gtest.h" #include "absl/base/attributes.h" #include "absl/base/internal/exception_testing.h" #include "absl/base/internal/raw_logging.h" #include "absl/base/macros.h" #include "absl/container/internal/test_instance_tracker.h" #include "absl/hash/hash_testing.h" #include "absl/memory/memory.h" #include "absl/strings/str_cat.h" namespace { using absl::test_internal::CopyableMovableInstance; using absl::test_internal::CopyableOnlyInstance; using absl::test_internal::InstanceTracker; using testing::AllOf; using testing::Each; using testing::ElementsAre; using testing::ElementsAreArray; using testing::Eq; using testing::Gt; using testing::PrintToString; using IntVec = absl::InlinedVector<int, 8>; MATCHER_P(SizeIs, n, "") { return testing::ExplainMatchResult(n, arg.size(), result_listener); } MATCHER_P(CapacityIs, n, "") { return testing::ExplainMatchResult(n, arg.capacity(), result_listener); } MATCHER_P(ValueIs, e, "") { return testing::ExplainMatchResult(e, arg.value(), result_listener); } // TODO(bsamwel): Add support for movable-only types. // Test fixture for typed tests on BaseCountedInstance derived classes, see // test_instance_tracker.h. template <typename T> class InstanceTest : public ::testing::Test {}; TYPED_TEST_CASE_P(InstanceTest); // A simple reference counted class to make sure that the proper elements are // destroyed in the erase(begin, end) test. class RefCounted { public: RefCounted(int value, int* count) : value_(value), count_(count) { Ref(); } RefCounted(const RefCounted& v) : value_(v.value_), count_(v.count_) { Ref(); } ~RefCounted() { Unref(); count_ = nullptr; } friend void swap(RefCounted& a, RefCounted& b) { using std::swap; swap(a.value_, b.value_); swap(a.count_, b.count_); } RefCounted& operator=(RefCounted v) { using std::swap; swap(*this, v); return *this; } void Ref() const { ABSL_RAW_CHECK(count_ != nullptr, ""); ++(*count_); } void Unref() const { --(*count_); ABSL_RAW_CHECK(*count_ >= 0, ""); } int value_; int* count_; }; using RefCountedVec = absl::InlinedVector<RefCounted, 8>; // A class with a vtable pointer class Dynamic { public: virtual ~Dynamic() {} }; using DynamicVec = absl::InlinedVector<Dynamic, 8>; // Append 0..len-1 to *v template <typename Container> static void Fill(Container* v, int len, int offset = 0) { for (int i = 0; i < len; i++) { v->push_back(i + offset); } } static IntVec Fill(int len, int offset = 0) { IntVec v; Fill(&v, len, offset); return v; } // This is a stateful allocator, but the state lives outside of the // allocator (in whatever test is using the allocator). This is odd // but helps in tests where the allocator is propagated into nested // containers - that chain of allocators uses the same state and is // thus easier to query for aggregate allocation information. template <typename T> class CountingAllocator : public std::allocator<T> { public: using Alloc = std::allocator<T>; using pointer = typename Alloc::pointer; using size_type = typename Alloc::size_type; CountingAllocator() : bytes_used_(nullptr) {} explicit CountingAllocator(int64_t* b) : bytes_used_(b) {} template <typename U> CountingAllocator(const CountingAllocator<U>& x) : Alloc(x), bytes_used_(x.bytes_used_) {} pointer allocate(size_type n, std::allocator<void>::const_pointer hint = nullptr) { assert(bytes_used_ != nullptr); *bytes_used_ += n * sizeof(T); return Alloc::allocate(n, hint); } void deallocate(pointer p, size_type n) { Alloc::deallocate(p, n); assert(bytes_used_ != nullptr); *bytes_used_ -= n * sizeof(T); } template<typename U> class rebind { public: using other = CountingAllocator<U>; }; friend bool operator==(const CountingAllocator& a, const CountingAllocator& b) { return a.bytes_used_ == b.bytes_used_; } friend bool operator!=(const CountingAllocator& a, const CountingAllocator& b) { return !(a == b); } int64_t* bytes_used_; }; TEST(IntVec, SimpleOps) { for (int len = 0; len < 20; len++) { IntVec v; const IntVec& cv = v; // const alias Fill(&v, len); EXPECT_EQ(len, v.size()); EXPECT_LE(len, v.capacity()); for (int i = 0; i < len; i++) { EXPECT_EQ(i, v[i]); EXPECT_EQ(i, v.at(i)); } EXPECT_EQ(v.begin(), v.data()); EXPECT_EQ(cv.begin(), cv.data()); int counter = 0; for (IntVec::iterator iter = v.begin(); iter != v.end(); ++iter) { EXPECT_EQ(counter, *iter); counter++; } EXPECT_EQ(counter, len); counter = 0; for (IntVec::const_iterator iter = v.begin(); iter != v.end(); ++iter) { EXPECT_EQ(counter, *iter); counter++; } EXPECT_EQ(counter, len); counter = 0; for (IntVec::const_iterator iter = v.cbegin(); iter != v.cend(); ++iter) { EXPECT_EQ(counter, *iter); counter++; } EXPECT_EQ(counter, len); if (len > 0) { EXPECT_EQ(0, v.front()); EXPECT_EQ(len - 1, v.back()); v.pop_back(); EXPECT_EQ(len - 1, v.size()); for (int i = 0; i < v.size(); ++i) { EXPECT_EQ(i, v[i]); EXPECT_EQ(i, v.at(i)); } } } } TEST(IntVec, AtThrows) { IntVec v = {1, 2, 3}; EXPECT_EQ(v.at(2), 3); ABSL_BASE_INTERNAL_EXPECT_FAIL(v.at(3), std::out_of_range, "failed bounds check"); } TEST(IntVec, ReverseIterator) { for (int len = 0; len < 20; len++) { IntVec v; Fill(&v, len); int counter = len; for (IntVec::reverse_iterator iter = v.rbegin(); iter != v.rend(); ++iter) { counter--; EXPECT_EQ(counter, *iter); } EXPECT_EQ(counter, 0); counter = len; for (IntVec::const_reverse_iterator iter = v.rbegin(); iter != v.rend(); ++iter) { counter--; EXPECT_EQ(counter, *iter); } EXPECT_EQ(counter, 0); counter = len; for (IntVec::const_reverse_iterator iter = v.crbegin(); iter != v.crend(); ++iter) { counter--; EXPECT_EQ(counter, *iter); } EXPECT_EQ(counter, 0); } } TEST(IntVec, Erase) { for (int len = 1; len < 20; len++) { for (int i = 0; i < len; ++i) { IntVec v; Fill(&v, len); v.erase(v.begin() + i); EXPECT_EQ(len - 1, v.size()); for (int j = 0; j < i; ++j) { EXPECT_EQ(j, v[j]); } for (int j = i; j < len - 1; ++j) { EXPECT_EQ(j + 1, v[j]); } } } } // At the end of this test loop, the elements between [erase_begin, erase_end) // should have reference counts == 0, and all others elements should have // reference counts == 1. TEST(RefCountedVec, EraseBeginEnd) { for (int len = 1; len < 20; ++len) { for (int erase_begin = 0; erase_begin < len; ++erase_begin) { for (int erase_end = erase_begin; erase_end <= len; ++erase_end) { std::vector<int> counts(len, 0); RefCountedVec v; for (int i = 0; i < len; ++i) { v.push_back(RefCounted(i, &counts[i])); } int erase_len = erase_end - erase_begin; v.erase(v.begin() + erase_begin, v.begin() + erase_end); EXPECT_EQ(len - erase_len, v.size()); // Check the elements before the first element erased. for (int i = 0; i < erase_begin; ++i) { EXPECT_EQ(i, v[i].value_); } // Check the elements after the first element erased. for (int i = erase_begin; i < v.size(); ++i) { EXPECT_EQ(i + erase_len, v[i].value_); } // Check that the elements at the beginning are preserved. for (int i = 0; i < erase_begin; ++i) { EXPECT_EQ(1, counts[i]); } // Check that the erased elements are destroyed for (int i = erase_begin; i < erase_end; ++i) { EXPECT_EQ(0, counts[i]); } // Check that the elements at the end are preserved. for (int i = erase_end; i< len; ++i) { EXPECT_EQ(1, counts[i]); } } } } } struct NoDefaultCtor { explicit NoDefaultCtor(int) {} }; struct NoCopy { NoCopy() {} NoCopy(const NoCopy&) = delete; }; struct NoAssign { NoAssign() {} NoAssign& operator=(const NoAssign&) = delete; }; struct MoveOnly { MoveOnly() {} MoveOnly(MoveOnly&&) = default; MoveOnly& operator=(MoveOnly&&) = default; }; TEST(InlinedVectorTest, NoDefaultCtor) { absl::InlinedVector<NoDefaultCtor, 1> v(10, NoDefaultCtor(2)); (void)v; } TEST(InlinedVectorTest, NoCopy) { absl::InlinedVector<NoCopy, 1> v(10); (void)v; } TEST(InlinedVectorTest, NoAssign) { absl::InlinedVector<NoAssign, 1> v(10); (void)v; } TEST(InlinedVectorTest, MoveOnly) { absl::InlinedVector<MoveOnly, 2> v; v.push_back(MoveOnly{}); v.push_back(MoveOnly{}); v.push_back(MoveOnly{}); v.erase(v.begin()); v.push_back(MoveOnly{}); v.erase(v.begin(), v.begin() + 1); v.insert(v.begin(), MoveOnly{}); v.emplace(v.begin()); v.emplace(v.begin(), MoveOnly{}); } TEST(InlinedVectorTest, Noexcept) { EXPECT_TRUE(std::is_nothrow_move_constructible<IntVec>::value); EXPECT_TRUE((std::is_nothrow_move_constructible< absl::InlinedVector<MoveOnly, 2>>::value)); struct MoveCanThrow { MoveCanThrow(MoveCanThrow&&) {} }; EXPECT_EQ(absl::default_allocator_is_nothrow::value, (std::is_nothrow_move_constructible< absl::InlinedVector<MoveCanThrow, 2>>::value)); } TEST(InlinedVectorTest, EmplaceBack) { absl::InlinedVector<std::pair<std::string, int>, 1> v; auto& inlined_element = v.emplace_back("answer", 42); EXPECT_EQ(&inlined_element, &v[0]); EXPECT_EQ(inlined_element.first, "answer"); EXPECT_EQ(inlined_element.second, 42); auto& allocated_element = v.emplace_back("taxicab", 1729); EXPECT_EQ(&allocated_element, &v[1]); EXPECT_EQ(allocated_element.first, "taxicab"); EXPECT_EQ(allocated_element.second, 1729); } TEST(InlinedVectorTest, ShrinkToFitGrowingVector) { absl::InlinedVector<std::pair<std::string, int>, 1> v; v.shrink_to_fit(); EXPECT_EQ(v.capacity(), 1); v.emplace_back("answer", 42); v.shrink_to_fit(); EXPECT_EQ(v.capacity(), 1); v.emplace_back("taxicab", 1729); EXPECT_GE(v.capacity(), 2); v.shrink_to_fit(); EXPECT_EQ(v.capacity(), 2); v.reserve(100); EXPECT_GE(v.capacity(), 100); v.shrink_to_fit(); EXPECT_EQ(v.capacity(), 2); } TEST(InlinedVectorTest, ShrinkToFitEdgeCases) { { absl::InlinedVector<std::pair<std::string, int>, 1> v; v.emplace_back("answer", 42); v.emplace_back("taxicab", 1729); EXPECT_GE(v.capacity(), 2); v.pop_back(); v.shrink_to_fit(); EXPECT_EQ(v.capacity(), 1); EXPECT_EQ(v[0].first, "answer"); EXPECT_EQ(v[0].second, 42); } { absl::InlinedVector<std::string, 2> v(100); v.resize(0); v.shrink_to_fit(); EXPECT_EQ(v.capacity(), 2); // inlined capacity } { absl::InlinedVector<std::string, 2> v(100); v.resize(1); v.shrink_to_fit(); EXPECT_EQ(v.capacity(), 2); // inlined capacity } { absl::InlinedVector<std::string, 2> v(100); v.resize(2); v.shrink_to_fit(); EXPECT_EQ(v.capacity(), 2); } { absl::InlinedVector<std::string, 2> v(100); v.resize(3); v.shrink_to_fit(); EXPECT_EQ(v.capacity(), 3); } } TEST(IntVec, Insert) { for (int len = 0; len < 20; len++) { for (int pos = 0; pos <= len; pos++) { { // Single element std::vector<int> std_v; Fill(&std_v, len); IntVec v; Fill(&v, len); std_v.insert(std_v.begin() + pos, 9999); IntVec::iterator it = v.insert(v.cbegin() + pos, 9999); EXPECT_THAT(v, ElementsAreArray(std_v)); EXPECT_EQ(it, v.cbegin() + pos); } { // n elements std::vector<int> std_v; Fill(&std_v, len); IntVec v; Fill(&v, len); IntVec::size_type n = 5; std_v.insert(std_v.begin() + pos, n, 9999); IntVec::iterator it = v.insert(v.cbegin() + pos, n, 9999); EXPECT_THAT(v, ElementsAreArray(std_v)); EXPECT_EQ(it, v.cbegin() + pos); } { // Iterator range (random access iterator) std::vector<int> std_v; Fill(&std_v, len); IntVec v; Fill(&v, len); const std::vector<int> input = {9999, 8888, 7777}; std_v.insert(std_v.begin() + pos, input.cbegin(), input.cend()); IntVec::iterator it = v.insert(v.cbegin() + pos, input.cbegin(), input.cend()); EXPECT_THAT(v, ElementsAreArray(std_v)); EXPECT_EQ(it, v.cbegin() + pos); } { // Iterator range (forward iterator) std::vector<int> std_v; Fill(&std_v, len); IntVec v; Fill(&v, len); const std::forward_list<int> input = {9999, 8888, 7777}; std_v.insert(std_v.begin() + pos, input.cbegin(), input.cend()); IntVec::iterator it = v.insert(v.cbegin() + pos, input.cbegin(), input.cend()); EXPECT_THAT(v, ElementsAreArray(std_v)); EXPECT_EQ(it, v.cbegin() + pos); } { // Iterator range (input iterator) std::vector<int> std_v; Fill(&std_v, len); IntVec v; Fill(&v, len); std_v.insert(std_v.begin() + pos, {9999, 8888, 7777}); std::istringstream input("9999 8888 7777"); IntVec::iterator it = v.insert(v.cbegin() + pos, std::istream_iterator<int>(input), std::istream_iterator<int>()); EXPECT_THAT(v, ElementsAreArray(std_v)); EXPECT_EQ(it, v.cbegin() + pos); } { // Initializer list std::vector<int> std_v; Fill(&std_v, len); IntVec v; Fill(&v, len); std_v.insert(std_v.begin() + pos, {9999, 8888}); IntVec::iterator it = v.insert(v.cbegin() + pos, {9999, 8888}); EXPECT_THAT(v, ElementsAreArray(std_v)); EXPECT_EQ(it, v.cbegin() + pos); } } } } TEST(RefCountedVec, InsertConstructorDestructor) { // Make sure the proper construction/destruction happen during insert // operations. for (int len = 0; len < 20; len++) { SCOPED_TRACE(len); for (int pos = 0; pos <= len; pos++) { SCOPED_TRACE(pos); std::vector<int> counts(len, 0); int inserted_count = 0; RefCountedVec v; for (int i = 0; i < len; ++i) { SCOPED_TRACE(i); v.push_back(RefCounted(i, &counts[i])); } EXPECT_THAT(counts, Each(Eq(1))); RefCounted insert_element(9999, &inserted_count); EXPECT_EQ(1, inserted_count); v.insert(v.begin() + pos, insert_element); EXPECT_EQ(2, inserted_count); // Check that the elements at the end are preserved. EXPECT_THAT(counts, Each(Eq(1))); EXPECT_EQ(2, inserted_count); } } } TEST(IntVec, Resize) { for (int len = 0; len < 20; len++) { IntVec v; Fill(&v, len); // Try resizing up and down by k elements static const int kResizeElem = 1000000; for (int k = 0; k < 10; k++) { // Enlarging resize v.resize(len+k, kResizeElem); EXPECT_EQ(len+k, v.size()); EXPECT_LE(len+k, v.capacity()); for (int i = 0; i < len+k; i++) { if (i < len) { EXPECT_EQ(i, v[i]); } else { EXPECT_EQ(kResizeElem, v[i]); } } // Shrinking resize v.resize(len, kResizeElem); EXPECT_EQ(len, v.size()); EXPECT_LE(len, v.capacity()); for (int i = 0; i < len; i++) { EXPECT_EQ(i, v[i]); } } } } TEST(IntVec, InitWithLength) { for (int len = 0; len < 20; len++) { IntVec v(len, 7); EXPECT_EQ(len, v.size()); EXPECT_LE(len, v.capacity()); for (int i = 0; i < len; i++) { EXPECT_EQ(7, v[i]); } } } TEST(IntVec, CopyConstructorAndAssignment) { for (int len = 0; len < 20; len++) { IntVec v; Fill(&v, len); EXPECT_EQ(len, v.size()); EXPECT_LE(len, v.capacity()); IntVec v2(v); EXPECT_TRUE(v == v2) << PrintToString(v) << PrintToString(v2); for (int start_len = 0; start_len < 20; start_len++) { IntVec v3; Fill(&v3, start_len, 99); // Add dummy elements that should go away v3 = v; EXPECT_TRUE(v == v3) << PrintToString(v) << PrintToString(v3); } } } TEST(IntVec, AliasingCopyAssignment) { for (int len = 0; len < 20; ++len) { IntVec original; Fill(&original, len); IntVec dup = original; dup = *&dup; EXPECT_EQ(dup, original); } } TEST(IntVec, MoveConstructorAndAssignment) { for (int len = 0; len < 20; len++) { IntVec v_in; const int inlined_capacity = v_in.capacity(); Fill(&v_in, len); EXPECT_EQ(len, v_in.size()); EXPECT_LE(len, v_in.capacity()); { IntVec v_temp(v_in); auto* old_data = v_temp.data(); IntVec v_out(std::move(v_temp)); EXPECT_TRUE(v_in == v_out) << PrintToString(v_in) << PrintToString(v_out); if (v_in.size() > inlined_capacity) { // Allocation is moved as a whole, data stays in place. EXPECT_TRUE(v_out.data() == old_data); } else { EXPECT_FALSE(v_out.data() == old_data); } } for (int start_len = 0; start_len < 20; start_len++) { IntVec v_out; Fill(&v_out, start_len, 99); // Add dummy elements that should go away IntVec v_temp(v_in); auto* old_data = v_temp.data(); v_out = std::move(v_temp); EXPECT_TRUE(v_in == v_out) << PrintToString(v_in) << PrintToString(v_out); if (v_in.size() > inlined_capacity) { // Allocation is moved as a whole, data stays in place. EXPECT_TRUE(v_out.data() == old_data); } else { EXPECT_FALSE(v_out.data() == old_data); } } } } class NotTriviallyDestructible { public: NotTriviallyDestructible() : p_(new int(1)) {} explicit NotTriviallyDestructible(int i) : p_(new int(i)) {} NotTriviallyDestructible(const NotTriviallyDestructible& other) : p_(new int(*other.p_)) {} NotTriviallyDestructible& operator=(const NotTriviallyDestructible& other) { p_ = absl::make_unique<int>(*other.p_); return *this; } bool operator==(const NotTriviallyDestructible& other) const { return *p_ == *other.p_; } private: std::unique_ptr<int> p_; }; TEST(AliasingTest, Emplace) { for (int i = 2; i < 20; ++i) { absl::InlinedVector<NotTriviallyDestructible, 10> vec; for (int j = 0; j < i; ++j) { vec.push_back(NotTriviallyDestructible(j)); } vec.emplace(vec.begin(), vec[0]); EXPECT_EQ(vec[0], vec[1]); vec.emplace(vec.begin() + i / 2, vec[i / 2]); EXPECT_EQ(vec[i / 2], vec[i / 2 + 1]); vec.emplace(vec.end() - 1, vec.back()); EXPECT_EQ(vec[vec.size() - 2], vec.back()); } } TEST(AliasingTest, InsertWithCount) { for (int i = 1; i < 20; ++i) { absl::InlinedVector<NotTriviallyDestructible, 10> vec; for (int j = 0; j < i; ++j) { vec.push_back(NotTriviallyDestructible(j)); } for (int n = 0; n < 5; ++n) { // We use back where we can because it's guaranteed to become invalidated vec.insert(vec.begin(), n, vec.back()); auto b = vec.begin(); EXPECT_TRUE( std::all_of(b, b + n, [&vec](const NotTriviallyDestructible& x) { return x == vec.back(); })); auto m_idx = vec.size() / 2; vec.insert(vec.begin() + m_idx, n, vec.back()); auto m = vec.begin() + m_idx; EXPECT_TRUE( std::all_of(m, m + n, [&vec](const NotTriviallyDestructible& x) { return x == vec.back(); })); // We want distinct values so the equality test is meaningful, // vec[vec.size() - 1] is also almost always invalidated. auto old_e = vec.size() - 1; auto val = vec[old_e]; vec.insert(vec.end(), n, vec[old_e]); auto e = vec.begin() + old_e; EXPECT_TRUE(std::all_of( e, e + n, [&val](const NotTriviallyDestructible& x) { return x == val; })); } } } TEST(OverheadTest, Storage) { // Check for size overhead. // In particular, ensure that std::allocator doesn't cost anything to store. // The union should be absorbing some of the allocation bookkeeping overhead // in the larger vectors, leaving only the size_ field as overhead. EXPECT_EQ(2 * sizeof(int*), sizeof(absl::InlinedVector<int*, 1>) - 1 * sizeof(int*)); EXPECT_EQ(1 * sizeof(int*), sizeof(absl::InlinedVector<int*, 2>) - 2 * sizeof(int*)); EXPECT_EQ(1 * sizeof(int*), sizeof(absl::InlinedVector<int*, 3>) - 3 * sizeof(int*)); EXPECT_EQ(1 * sizeof(int*), sizeof(absl::InlinedVector<int*, 4>) - 4 * sizeof(int*)); EXPECT_EQ(1 * sizeof(int*), sizeof(absl::InlinedVector<int*, 5>) - 5 * sizeof(int*)); EXPECT_EQ(1 * sizeof(int*), sizeof(absl::InlinedVector<int*, 6>) - 6 * sizeof(int*)); EXPECT_EQ(1 * sizeof(int*), sizeof(absl::InlinedVector<int*, 7>) - 7 * sizeof(int*)); EXPECT_EQ(1 * sizeof(int*), sizeof(absl::InlinedVector<int*, 8>) - 8 * sizeof(int*)); } TEST(IntVec, Clear) { for (int len = 0; len < 20; len++) { SCOPED_TRACE(len); IntVec v; Fill(&v, len); v.clear(); EXPECT_EQ(0, v.size()); EXPECT_EQ(v.begin(), v.end()); } } TEST(IntVec, Reserve) { for (int len = 0; len < 20; len++) { IntVec v; Fill(&v, len); for (int newlen = 0; newlen < 100; newlen++) { const int* start_rep = v.data(); v.reserve(newlen); const int* final_rep = v.data(); if (newlen <= len) { EXPECT_EQ(start_rep, final_rep); } EXPECT_LE(newlen, v.capacity()); // Filling up to newlen should not change rep while (v.size() < newlen) { v.push_back(0); } EXPECT_EQ(final_rep, v.data()); } } } TEST(StringVec, SelfRefPushBack) { std::vector<std::string> std_v; absl::InlinedVector<std::string, 4> v; const std::string s = "A quite long std::string to ensure heap."; std_v.push_back(s); v.push_back(s); for (int i = 0; i < 20; ++i) { EXPECT_THAT(v, ElementsAreArray(std_v)); v.push_back(v.back()); std_v.push_back(std_v.back()); } EXPECT_THAT(v, ElementsAreArray(std_v)); } TEST(StringVec, SelfRefPushBackWithMove) { std::vector<std::string> std_v; absl::InlinedVector<std::string, 4> v; const std::string s = "A quite long std::string to ensure heap."; std_v.push_back(s); v.push_back(s); for (int i = 0; i < 20; ++i) { EXPECT_EQ(v.back(), std_v.back()); v.push_back(std::move(v.back())); std_v.push_back(std::move(std_v.back())); } EXPECT_EQ(v.back(), std_v.back()); } TEST(StringVec, SelfMove) { const std::string s = "A quite long std::string to ensure heap."; for (int len = 0; len < 20; len++) { SCOPED_TRACE(len); absl::InlinedVector<std::string, 8> v; for (int i = 0; i < len; ++i) { SCOPED_TRACE(i); v.push_back(s); } // Indirection necessary to avoid compiler warning. v = std::move(*(&v)); // Ensure that the inlined vector is still in a valid state by copying it. // We don't expect specific contents since a self-move results in an // unspecified valid state. std::vector<std::string> copy(v.begin(), v.end()); } } TEST(IntVec, Swap) { for (int l1 = 0; l1 < 20; l1++) { SCOPED_TRACE(l1); for (int l2 = 0; l2 < 20; l2++) { SCOPED_TRACE(l2); IntVec a = Fill(l1, 0); IntVec b = Fill(l2, 100); { using std::swap; swap(a, b); } EXPECT_EQ(l1, b.size()); EXPECT_EQ(l2, a.size()); for (int i = 0; i < l1; i++) { SCOPED_TRACE(i); EXPECT_EQ(i, b[i]); } for (int i = 0; i < l2; i++) { SCOPED_TRACE(i); EXPECT_EQ(100 + i, a[i]); } } } } TYPED_TEST_P(InstanceTest, Swap) { using Instance = TypeParam; using InstanceVec = absl::InlinedVector<Instance, 8>; for (int l1 = 0; l1 < 20; l1++) { SCOPED_TRACE(l1); for (int l2 = 0; l2 < 20; l2++) { SCOPED_TRACE(l2); InstanceTracker tracker; InstanceVec a, b; const size_t inlined_capacity = a.capacity(); for (int i = 0; i < l1; i++) a.push_back(Instance(i)); for (int i = 0; i < l2; i++) b.push_back(Instance(100+i)); EXPECT_EQ(tracker.instances(), l1 + l2); tracker.ResetCopiesMovesSwaps(); { using std::swap; swap(a, b); } EXPECT_EQ(tracker.instances(), l1 + l2); if (a.size() > inlined_capacity && b.size() > inlined_capacity) { EXPECT_EQ(tracker.swaps(), 0); // Allocations are swapped. EXPECT_EQ(tracker.moves(), 0); } else if (a.size() <= inlined_capacity && b.size() <= inlined_capacity) { EXPECT_EQ(tracker.swaps(), std::min(l1, l2)); // TODO(bsamwel): This should use moves when the type is movable. EXPECT_EQ(tracker.copies(), std::max(l1, l2) - std::min(l1, l2)); } else { // One is allocated and the other isn't. The allocation is transferred // without copying elements, and the inlined instances are copied/moved. EXPECT_EQ(tracker.swaps(), 0); // TODO(bsamwel): This should use moves when the type is movable. EXPECT_EQ(tracker.copies(), std::min(l1, l2)); } EXPECT_EQ(l1, b.size()); EXPECT_EQ(l2, a.size()); for (int i = 0; i < l1; i++) { EXPECT_EQ(i, b[i].value()); } for (int i = 0; i < l2; i++) { EXPECT_EQ(100 + i, a[i].value()); } } } } TEST(IntVec, EqualAndNotEqual) { IntVec a, b; EXPECT_TRUE(a == b); EXPECT_FALSE(a != b); a.push_back(3); EXPECT_FALSE(a == b); EXPECT_TRUE(a != b); b.push_back(3); EXPECT_TRUE(a == b); EXPECT_FALSE(a != b); b.push_back(7); EXPECT_FALSE(a == b); EXPECT_TRUE(a != b); a.push_back(6); EXPECT_FALSE(a == b); EXPECT_TRUE(a != b); a.clear(); b.clear(); for (int i = 0; i < 100; i++) { a.push_back(i); b.push_back(i); EXPECT_TRUE(a == b); EXPECT_FALSE(a != b); b[i] = b[i] + 1; EXPECT_FALSE(a == b); EXPECT_TRUE(a != b); b[i] = b[i] - 1; // Back to before EXPECT_TRUE(a == b); EXPECT_FALSE(a != b); } } TEST(IntVec, RelationalOps) { IntVec a, b; EXPECT_FALSE(a < b); EXPECT_FALSE(b < a); EXPECT_FALSE(a > b); EXPECT_FALSE(b > a); EXPECT_TRUE(a <= b); EXPECT_TRUE(b <= a); EXPECT_TRUE(a >= b); EXPECT_TRUE(b >= a); b.push_back(3); EXPECT_TRUE(a < b); EXPECT_FALSE(b < a); EXPECT_FALSE(a > b); EXPECT_TRUE(b > a); EXPECT_TRUE(a <= b); EXPECT_FALSE(b <= a); EXPECT_FALSE(a >= b); EXPECT_TRUE(b >= a); } TYPED_TEST_P(InstanceTest, CountConstructorsDestructors) { using Instance = TypeParam; using InstanceVec = absl::InlinedVector<Instance, 8>; InstanceTracker tracker; for (int len = 0; len < 20; len++) { SCOPED_TRACE(len); tracker.ResetCopiesMovesSwaps(); InstanceVec v; const size_t inlined_capacity = v.capacity(); for (int i = 0; i < len; i++) { v.push_back(Instance(i)); } EXPECT_EQ(tracker.instances(), len); EXPECT_GE(tracker.copies() + tracker.moves(), len); // More due to reallocation. tracker.ResetCopiesMovesSwaps(); // Enlarging resize() must construct some objects tracker.ResetCopiesMovesSwaps(); v.resize(len + 10, Instance(100)); EXPECT_EQ(tracker.instances(), len + 10); if (len <= inlined_capacity && len + 10 > inlined_capacity) { EXPECT_EQ(tracker.copies() + tracker.moves(), 10 + len); } else { // Only specify a minimum number of copies + moves. We don't want to // depend on the reallocation policy here. EXPECT_GE(tracker.copies() + tracker.moves(), 10); // More due to reallocation. } // Shrinking resize() must destroy some objects tracker.ResetCopiesMovesSwaps(); v.resize(len, Instance(100)); EXPECT_EQ(tracker.instances(), len); EXPECT_EQ(tracker.copies(), 0); EXPECT_EQ(tracker.moves(), 0); // reserve() must not increase the number of initialized objects SCOPED_TRACE("reserve"); v.reserve(len+1000); EXPECT_EQ(tracker.instances(), len); EXPECT_EQ(tracker.copies() + tracker.moves(), len); // pop_back() and erase() must destroy one object if (len > 0) { tracker.ResetCopiesMovesSwaps(); v.pop_back(); EXPECT_EQ(tracker.instances(), len - 1); EXPECT_EQ(tracker.copies(), 0); EXPECT_EQ(tracker.moves(), 0); if (!v.empty()) { tracker.ResetCopiesMovesSwaps(); v.erase(v.begin()); EXPECT_EQ(tracker.instances(), len - 2); EXPECT_EQ(tracker.copies() + tracker.moves(), len - 2); } } tracker.ResetCopiesMovesSwaps(); int instances_before_empty_erase = tracker.instances(); v.erase(v.begin(), v.begin()); EXPECT_EQ(tracker.instances(), instances_before_empty_erase); EXPECT_EQ(tracker.copies() + tracker.moves(), 0); } } TYPED_TEST_P(InstanceTest, CountConstructorsDestructorsOnCopyConstruction) { using Instance = TypeParam; using InstanceVec = absl::InlinedVector<Instance, 8>; InstanceTracker tracker; for (int len = 0; len < 20; len++) { SCOPED_TRACE(len); tracker.ResetCopiesMovesSwaps(); InstanceVec v; for (int i = 0; i < len; i++) { v.push_back(Instance(i)); } EXPECT_EQ(tracker.instances(), len); EXPECT_GE(tracker.copies() + tracker.moves(), len); // More due to reallocation. tracker.ResetCopiesMovesSwaps(); { // Copy constructor should create 'len' more instances. InstanceVec v_copy(v); EXPECT_EQ(tracker.instances(), len + len); EXPECT_EQ(tracker.copies(), len); EXPECT_EQ(tracker.moves(), 0); } EXPECT_EQ(tracker.instances(), len); } } TYPED_TEST_P(InstanceTest, CountConstructorsDestructorsOnMoveConstruction) { using Instance = TypeParam; using InstanceVec = absl::InlinedVector<Instance, 8>; InstanceTracker tracker; for (int len = 0; len < 20; len++) { SCOPED_TRACE(len); tracker.ResetCopiesMovesSwaps(); InstanceVec v; const size_t inlined_capacity = v.capacity(); for (int i = 0; i < len; i++) { v.push_back(Instance(i)); } EXPECT_EQ(tracker.instances(), len); EXPECT_GE(tracker.copies() + tracker.moves(), len); // More due to reallocation. tracker.ResetCopiesMovesSwaps(); { InstanceVec v_copy(std::move(v)); if (len > inlined_capacity) { // Allocation is moved as a whole. EXPECT_EQ(tracker.instances(), len); EXPECT_EQ(tracker.live_instances(), len); // Tests an implementation detail, don't rely on this in your code. EXPECT_EQ(v.size(), 0); // NOLINT misc-use-after-move EXPECT_EQ(tracker.copies(), 0); EXPECT_EQ(tracker.moves(), 0); } else { EXPECT_EQ(tracker.instances(), len + len); if (Instance::supports_move()) { EXPECT_EQ(tracker.live_instances(), len); EXPECT_EQ(tracker.copies(), 0); EXPECT_EQ(tracker.moves(), len); } else { EXPECT_EQ(tracker.live_instances(), len + len); EXPECT_EQ(tracker.copies(), len); EXPECT_EQ(tracker.moves(), 0); } } EXPECT_EQ(tracker.swaps(), 0); } } } TYPED_TEST_P(InstanceTest, CountConstructorsDestructorsOnAssignment) { using Instance = TypeParam; using InstanceVec = absl::InlinedVector<Instance, 8>; InstanceTracker tracker; for (int len = 0; len < 20; len++) { SCOPED_TRACE(len); for (int longorshort = 0; longorshort <= 1; ++longorshort) { SCOPED_TRACE(longorshort); tracker.ResetCopiesMovesSwaps(); InstanceVec longer, shorter; for (int i = 0; i < len; i++) { longer.push_back(Instance(i)); shorter.push_back(Instance(i)); } longer.push_back(Instance(len)); EXPECT_EQ(tracker.instances(), len + len + 1); EXPECT_GE(tracker.copies() + tracker.moves(), len + len + 1); // More due to reallocation. tracker.ResetCopiesMovesSwaps(); if (longorshort) { shorter = longer; EXPECT_EQ(tracker.instances(), (len + 1) + (len + 1)); EXPECT_GE(tracker.copies() + tracker.moves(), len + 1); // More due to reallocation. } else { longer = shorter; EXPECT_EQ(tracker.instances(), len + len); EXPECT_EQ(tracker.copies() + tracker.moves(), len); } } } } TYPED_TEST_P(InstanceTest, CountConstructorsDestructorsOnMoveAssignment) { using Instance = TypeParam; using InstanceVec = absl::InlinedVector<Instance, 8>; InstanceTracker tracker; for (int len = 0; len < 20; len++) { SCOPED_TRACE(len); for (int longorshort = 0; longorshort <= 1; ++longorshort) { SCOPED_TRACE(longorshort); tracker.ResetCopiesMovesSwaps(); InstanceVec longer, shorter; const int inlined_capacity = longer.capacity(); for (int i = 0; i < len; i++) { longer.push_back(Instance(i)); shorter.push_back(Instance(i)); } longer.push_back(Instance(len)); EXPECT_EQ(tracker.instances(), len + len + 1); EXPECT_GE(tracker.copies() + tracker.moves(), len + len + 1); // More due to reallocation. tracker.ResetCopiesMovesSwaps(); int src_len; if (longorshort) { src_len = len + 1; shorter = std::move(longer); } else { src_len = len; longer = std::move(shorter); } if (src_len > inlined_capacity) { // Allocation moved as a whole. EXPECT_EQ(tracker.instances(), src_len); EXPECT_EQ(tracker.live_instances(), src_len); EXPECT_EQ(tracker.copies(), 0); EXPECT_EQ(tracker.moves(), 0); } else { // Elements are all copied. EXPECT_EQ(tracker.instances(), src_len + src_len); if (Instance::supports_move()) { EXPECT_EQ(tracker.copies(), 0); EXPECT_EQ(tracker.moves(), src_len); EXPECT_EQ(tracker.live_instances(), src_len); } else { EXPECT_EQ(tracker.copies(), src_len); EXPECT_EQ(tracker.moves(), 0); EXPECT_EQ(tracker.live_instances(), src_len + src_len); } } EXPECT_EQ(tracker.swaps(), 0); } } } TEST(CountElemAssign, SimpleTypeWithInlineBacking) { for (size_t original_size = 0; original_size <= 5; ++original_size) { SCOPED_TRACE(original_size); // Original contents are [12345, 12345, ...] std::vector<int> original_contents(original_size, 12345); absl::InlinedVector<int, 2> v(original_contents.begin(), original_contents.end()); v.assign(2, 123); EXPECT_THAT(v, AllOf(SizeIs(2), ElementsAre(123, 123))); if (original_size <= 2) { // If the original had inline backing, it should stay inline. EXPECT_EQ(2, v.capacity()); } } } TEST(CountElemAssign, SimpleTypeWithAllocation) { for (size_t original_size = 0; original_size <= 5; ++original_size) { SCOPED_TRACE(original_size); // Original contents are [12345, 12345, ...] std::vector<int> original_contents(original_size, 12345); absl::InlinedVector<int, 2> v(original_contents.begin(), original_contents.end()); v.assign(3, 123); EXPECT_THAT(v, AllOf(SizeIs(3), ElementsAre(123, 123, 123))); EXPECT_LE(v.size(), v.capacity()); } } TYPED_TEST_P(InstanceTest, CountElemAssignInlineBacking) { using Instance = TypeParam; for (size_t original_size = 0; original_size <= 5; ++original_size) { SCOPED_TRACE(original_size); // Original contents are [12345, 12345, ...] std::vector<Instance> original_contents(original_size, Instance(12345)); absl::InlinedVector<Instance, 2> v(original_contents.begin(), original_contents.end()); v.assign(2, Instance(123)); EXPECT_THAT(v, AllOf(SizeIs(2), ElementsAre(ValueIs(123), ValueIs(123)))); if (original_size <= 2) { // If the original had inline backing, it should stay inline. EXPECT_EQ(2, v.capacity()); } } } template <typename Instance> void InstanceCountElemAssignWithAllocationTest() { for (size_t original_size = 0; original_size <= 5; ++original_size) { SCOPED_TRACE(original_size); // Original contents are [12345, 12345, ...] std::vector<Instance> original_contents(original_size, Instance(12345)); absl::InlinedVector<Instance, 2> v(original_contents.begin(), original_contents.end()); v.assign(3, Instance(123)); EXPECT_THAT(v, AllOf(SizeIs(3), ElementsAre(ValueIs(123), ValueIs(123), ValueIs(123)))); EXPECT_LE(v.size(), v.capacity()); } } TEST(CountElemAssign, WithAllocationCopyableInstance) { InstanceCountElemAssignWithAllocationTest<CopyableOnlyInstance>(); } TEST(CountElemAssign, WithAllocationCopyableMovableInstance) { InstanceCountElemAssignWithAllocationTest<CopyableMovableInstance>(); } TEST(RangedConstructor, SimpleType) { std::vector<int> source_v = {4, 5, 6}; // First try to fit in inline backing absl::InlinedVector<int, 4> v(source_v.begin(), source_v.end()); EXPECT_EQ(3, v.size()); EXPECT_EQ(4, v.capacity()); // Indication that we're still on inlined storage EXPECT_EQ(4, v[0]); EXPECT_EQ(5, v[1]); EXPECT_EQ(6, v[2]); // Now, force a re-allocate absl::InlinedVector<int, 2> realloc_v(source_v.begin(), source_v.end()); EXPECT_EQ(3, realloc_v.size()); EXPECT_LT(2, realloc_v.capacity()); EXPECT_EQ(4, realloc_v[0]); EXPECT_EQ(5, realloc_v[1]); EXPECT_EQ(6, realloc_v[2]); } // Test for ranged constructors using Instance as the element type and // SourceContainer as the source container type. template <typename Instance, typename SourceContainer, int inlined_capacity> void InstanceRangedConstructorTestForContainer() { InstanceTracker tracker; SourceContainer source_v = {Instance(0), Instance(1)}; tracker.ResetCopiesMovesSwaps(); absl::InlinedVector<Instance, inlined_capacity> v(source_v.begin(), source_v.end()); EXPECT_EQ(2, v.size()); EXPECT_LT(1, v.capacity()); EXPECT_EQ(0, v[0].value()); EXPECT_EQ(1, v[1].value()); EXPECT_EQ(tracker.copies(), 2); EXPECT_EQ(tracker.moves(), 0); } template <typename Instance, int inlined_capacity> void InstanceRangedConstructorTestWithCapacity() { // Test with const and non-const, random access and non-random-access sources. // TODO(bsamwel): Test with an input iterator source. { SCOPED_TRACE("std::list"); InstanceRangedConstructorTestForContainer<Instance, std::list<Instance>, inlined_capacity>(); { SCOPED_TRACE("const std::list"); InstanceRangedConstructorTestForContainer< Instance, const std::list<Instance>, inlined_capacity>(); } { SCOPED_TRACE("std::vector"); InstanceRangedConstructorTestForContainer<Instance, std::vector<Instance>, inlined_capacity>(); } { SCOPED_TRACE("const std::vector"); InstanceRangedConstructorTestForContainer< Instance, const std::vector<Instance>, inlined_capacity>(); } } } TYPED_TEST_P(InstanceTest, RangedConstructor) { using Instance = TypeParam; SCOPED_TRACE("capacity=1"); InstanceRangedConstructorTestWithCapacity<Instance, 1>(); SCOPED_TRACE("capacity=2"); InstanceRangedConstructorTestWithCapacity<Instance, 2>(); } TEST(RangedConstructor, ElementsAreConstructed) { std::vector<std::string> source_v = {"cat", "dog"}; // Force expansion and re-allocation of v. Ensures that when the vector is // expanded that new elements are constructed. absl::InlinedVector<std::string, 1> v(source_v.begin(), source_v.end()); EXPECT_EQ("cat", v[0]); EXPECT_EQ("dog", v[1]); } TEST(RangedAssign, SimpleType) { // Test for all combinations of original sizes (empty and non-empty inline, // and out of line) and target sizes. for (size_t original_size = 0; original_size <= 5; ++original_size) { SCOPED_TRACE(original_size); // Original contents are [12345, 12345, ...] std::vector<int> original_contents(original_size, 12345); for (size_t target_size = 0; target_size <= 5; ++target_size) { SCOPED_TRACE(target_size); // New contents are [3, 4, ...] std::vector<int> new_contents; for (size_t i = 0; i < target_size; ++i) { new_contents.push_back(i + 3); } absl::InlinedVector<int, 3> v(original_contents.begin(), original_contents.end()); v.assign(new_contents.begin(), new_contents.end()); EXPECT_EQ(new_contents.size(), v.size()); EXPECT_LE(new_contents.size(), v.capacity()); if (target_size <= 3 && original_size <= 3) { // Storage should stay inline when target size is small. EXPECT_EQ(3, v.capacity()); } EXPECT_THAT(v, ElementsAreArray(new_contents)); } } } // Returns true if lhs and rhs have the same value. template <typename Instance> static bool InstanceValuesEqual(const Instance& lhs, const Instance& rhs) { return lhs.value() == rhs.value(); } // Test for ranged assign() using Instance as the element type and // SourceContainer as the source container type. template <typename Instance, typename SourceContainer> void InstanceRangedAssignTestForContainer() { // Test for all combinations of original sizes (empty and non-empty inline, // and out of line) and target sizes. for (size_t original_size = 0; original_size <= 5; ++original_size) { SCOPED_TRACE(original_size); // Original contents are [12345, 12345, ...] std::vector<Instance> original_contents(original_size, Instance(12345)); for (size_t target_size = 0; target_size <= 5; ++target_size) { SCOPED_TRACE(target_size); // New contents are [3, 4, ...] // Generate data using a non-const container, because SourceContainer // itself may be const. // TODO(bsamwel): Test with an input iterator. std::vector<Instance> new_contents_in; for (size_t i = 0; i < target_size; ++i) { new_contents_in.push_back(Instance(i + 3)); } SourceContainer new_contents(new_contents_in.begin(), new_contents_in.end()); absl::InlinedVector<Instance, 3> v(original_contents.begin(), original_contents.end()); v.assign(new_contents.begin(), new_contents.end()); EXPECT_EQ(new_contents.size(), v.size()); EXPECT_LE(new_contents.size(), v.capacity()); if (target_size <= 3 && original_size <= 3) { // Storage should stay inline when target size is small. EXPECT_EQ(3, v.capacity()); } EXPECT_TRUE(std::equal(v.begin(), v.end(), new_contents.begin(), InstanceValuesEqual<Instance>)); } } } TYPED_TEST_P(InstanceTest, RangedAssign) { using Instance = TypeParam; // Test with const and non-const, random access and non-random-access sources. // TODO(bsamwel): Test with an input iterator source. SCOPED_TRACE("std::list"); InstanceRangedAssignTestForContainer<Instance, std::list<Instance>>(); SCOPED_TRACE("const std::list"); InstanceRangedAssignTestForContainer<Instance, const std::list<Instance>>(); SCOPED_TRACE("std::vector"); InstanceRangedAssignTestForContainer<Instance, std::vector<Instance>>(); SCOPED_TRACE("const std::vector"); InstanceRangedAssignTestForContainer<Instance, const std::vector<Instance>>(); } TEST(InitializerListConstructor, SimpleTypeWithInlineBacking) { EXPECT_THAT((absl::InlinedVector<int, 4>{4, 5, 6}), AllOf(SizeIs(3), CapacityIs(4), ElementsAre(4, 5, 6))); } TEST(InitializerListConstructor, SimpleTypeWithReallocationRequired) { EXPECT_THAT((absl::InlinedVector<int, 2>{4, 5, 6}), AllOf(SizeIs(3), CapacityIs(Gt(2)), ElementsAre(4, 5, 6))); } TEST(InitializerListConstructor, DisparateTypesInList) { EXPECT_THAT((absl::InlinedVector<int, 2>{-7, 8ULL}), ElementsAre(-7, 8)); EXPECT_THAT((absl::InlinedVector<std::string, 2>{"foo", std::string("bar")}), ElementsAre("foo", "bar")); } TEST(InitializerListConstructor, ComplexTypeWithInlineBacking) { EXPECT_THAT((absl::InlinedVector<CopyableMovableInstance, 1>{ CopyableMovableInstance(0)}), AllOf(SizeIs(1), CapacityIs(1), ElementsAre(ValueIs(0)))); } TEST(InitializerListConstructor, ComplexTypeWithReallocationRequired) { EXPECT_THAT( (absl::InlinedVector<CopyableMovableInstance, 1>{ CopyableMovableInstance(0), CopyableMovableInstance(1)}), AllOf(SizeIs(2), CapacityIs(Gt(1)), ElementsAre(ValueIs(0), ValueIs(1)))); } TEST(InitializerListAssign, SimpleTypeFitsInlineBacking) { for (size_t original_size = 0; original_size <= 4; ++original_size) { SCOPED_TRACE(original_size); absl::InlinedVector<int, 2> v1(original_size, 12345); const size_t original_capacity_v1 = v1.capacity(); v1.assign({3}); EXPECT_THAT( v1, AllOf(SizeIs(1), CapacityIs(original_capacity_v1), ElementsAre(3))); absl::InlinedVector<int, 2> v2(original_size, 12345); const size_t original_capacity_v2 = v2.capacity(); v2 = {3}; EXPECT_THAT( v2, AllOf(SizeIs(1), CapacityIs(original_capacity_v2), ElementsAre(3))); } } TEST(InitializerListAssign, SimpleTypeDoesNotFitInlineBacking) { for (size_t original_size = 0; original_size <= 4; ++original_size) { SCOPED_TRACE(original_size); absl::InlinedVector<int, 2> v1(original_size, 12345); v1.assign({3, 4, 5}); EXPECT_THAT(v1, AllOf(SizeIs(3), ElementsAre(3, 4, 5))); EXPECT_LE(3, v1.capacity()); absl::InlinedVector<int, 2> v2(original_size, 12345); v2 = {3, 4, 5}; EXPECT_THAT(v2, AllOf(SizeIs(3), ElementsAre(3, 4, 5))); EXPECT_LE(3, v2.capacity()); } } TEST(InitializerListAssign, DisparateTypesInList) { absl::InlinedVector<int, 2> v_int1; v_int1.assign({-7, 8ULL}); EXPECT_THAT(v_int1, ElementsAre(-7, 8)); absl::InlinedVector<int, 2> v_int2; v_int2 = {-7, 8ULL}; EXPECT_THAT(v_int2, ElementsAre(-7, 8)); absl::InlinedVector<std::string, 2> v_string1; v_string1.assign({"foo", std::string("bar")}); EXPECT_THAT(v_string1, ElementsAre("foo", "bar")); absl::InlinedVector<std::string, 2> v_string2; v_string2 = {"foo", std::string("bar")}; EXPECT_THAT(v_string2, ElementsAre("foo", "bar")); } TYPED_TEST_P(InstanceTest, InitializerListAssign) { using Instance = TypeParam; for (size_t original_size = 0; original_size <= 4; ++original_size) { SCOPED_TRACE(original_size); absl::InlinedVector<Instance, 2> v(original_size, Instance(12345)); const size_t original_capacity = v.capacity(); v.assign({Instance(3)}); EXPECT_THAT(v, AllOf(SizeIs(1), CapacityIs(original_capacity), ElementsAre(ValueIs(3)))); } for (size_t original_size = 0; original_size <= 4; ++original_size) { SCOPED_TRACE(original_size); absl::InlinedVector<Instance, 2> v(original_size, Instance(12345)); v.assign({Instance(3), Instance(4), Instance(5)}); EXPECT_THAT(v, AllOf(SizeIs(3), ElementsAre(ValueIs(3), ValueIs(4), ValueIs(5)))); EXPECT_LE(3, v.capacity()); } } REGISTER_TYPED_TEST_CASE_P(InstanceTest, Swap, CountConstructorsDestructors, CountConstructorsDestructorsOnCopyConstruction, CountConstructorsDestructorsOnMoveConstruction, CountConstructorsDestructorsOnAssignment, CountConstructorsDestructorsOnMoveAssignment, CountElemAssignInlineBacking, RangedConstructor, RangedAssign, InitializerListAssign); using InstanceTypes = ::testing::Types<CopyableOnlyInstance, CopyableMovableInstance>; INSTANTIATE_TYPED_TEST_CASE_P(InstanceTestOnTypes, InstanceTest, InstanceTypes); TEST(DynamicVec, DynamicVecCompiles) { DynamicVec v; (void)v; } TEST(AllocatorSupportTest, Constructors) { using MyAlloc = CountingAllocator<int>; using AllocVec = absl::InlinedVector<int, 4, MyAlloc>; const int ia[] = { 0, 1, 2, 3, 4, 5, 6, 7 }; int64_t allocated = 0; MyAlloc alloc(&allocated); { AllocVec ABSL_ATTRIBUTE_UNUSED v; } { AllocVec ABSL_ATTRIBUTE_UNUSED v(alloc); } { AllocVec ABSL_ATTRIBUTE_UNUSED v(ia, ia + ABSL_ARRAYSIZE(ia), alloc); } { AllocVec ABSL_ATTRIBUTE_UNUSED v({1, 2, 3}, alloc); } AllocVec v2; { AllocVec ABSL_ATTRIBUTE_UNUSED v(v2, alloc); } { AllocVec ABSL_ATTRIBUTE_UNUSED v(std::move(v2), alloc); } } TEST(AllocatorSupportTest, CountAllocations) { using MyAlloc = CountingAllocator<int>; using AllocVec = absl::InlinedVector<int, 4, MyAlloc>; const int ia[] = { 0, 1, 2, 3, 4, 5, 6, 7 }; int64_t allocated = 0; MyAlloc alloc(&allocated); { AllocVec ABSL_ATTRIBUTE_UNUSED v(ia, ia + 4, alloc); EXPECT_THAT(allocated, 0); } EXPECT_THAT(allocated, 0); { AllocVec ABSL_ATTRIBUTE_UNUSED v(ia, ia + ABSL_ARRAYSIZE(ia), alloc); EXPECT_THAT(allocated, v.size() * sizeof(int)); } EXPECT_THAT(allocated, 0); { AllocVec v(4, 1, alloc); EXPECT_THAT(allocated, 0); int64_t allocated2 = 0; MyAlloc alloc2(&allocated2); AllocVec v2(v, alloc2); EXPECT_THAT(allocated2, 0); int64_t allocated3 = 0; MyAlloc alloc3(&allocated3); AllocVec v3(std::move(v), alloc3); EXPECT_THAT(allocated3, 0); } EXPECT_THAT(allocated, 0); { AllocVec v(8, 2, alloc); EXPECT_THAT(allocated, v.size() * sizeof(int)); int64_t allocated2 = 0; MyAlloc alloc2(&allocated2); AllocVec v2(v, alloc2); EXPECT_THAT(allocated2, v2.size() * sizeof(int)); int64_t allocated3 = 0; MyAlloc alloc3(&allocated3); AllocVec v3(std::move(v), alloc3); EXPECT_THAT(allocated3, v3.size() * sizeof(int)); } EXPECT_EQ(allocated, 0); { // Test shrink_to_fit deallocations. AllocVec v(8, 2, alloc); EXPECT_EQ(allocated, 8 * sizeof(int)); v.resize(5); EXPECT_EQ(allocated, 8 * sizeof(int)); v.shrink_to_fit(); EXPECT_EQ(allocated, 5 * sizeof(int)); v.resize(4); EXPECT_EQ(allocated, 5 * sizeof(int)); v.shrink_to_fit(); EXPECT_EQ(allocated, 0); } } TEST(AllocatorSupportTest, SwapBothAllocated) { using MyAlloc = CountingAllocator<int>; using AllocVec = absl::InlinedVector<int, 4, MyAlloc>; int64_t allocated1 = 0; int64_t allocated2 = 0; { const int ia1[] = { 0, 1, 2, 3, 4, 5, 6, 7 }; const int ia2[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8 }; MyAlloc a1(&allocated1); MyAlloc a2(&allocated2); AllocVec v1(ia1, ia1 + ABSL_ARRAYSIZE(ia1), a1); AllocVec v2(ia2, ia2 + ABSL_ARRAYSIZE(ia2), a2); EXPECT_LT(v1.capacity(), v2.capacity()); EXPECT_THAT(allocated1, v1.capacity() * sizeof(int)); EXPECT_THAT(allocated2, v2.capacity() * sizeof(int)); v1.swap(v2); EXPECT_THAT(v1, ElementsAreArray(ia2)); EXPECT_THAT(v2, ElementsAreArray(ia1)); EXPECT_THAT(allocated1, v2.capacity() * sizeof(int)); EXPECT_THAT(allocated2, v1.capacity() * sizeof(int)); } EXPECT_THAT(allocated1, 0); EXPECT_THAT(allocated2, 0); } TEST(AllocatorSupportTest, SwapOneAllocated) { using MyAlloc = CountingAllocator<int>; using AllocVec = absl::InlinedVector<int, 4, MyAlloc>; int64_t allocated1 = 0; int64_t allocated2 = 0; { const int ia1[] = { 0, 1, 2, 3, 4, 5, 6, 7 }; const int ia2[] = { 0, 1, 2, 3 }; MyAlloc a1(&allocated1); MyAlloc a2(&allocated2); AllocVec v1(ia1, ia1 + ABSL_ARRAYSIZE(ia1), a1); AllocVec v2(ia2, ia2 + ABSL_ARRAYSIZE(ia2), a2); EXPECT_THAT(allocated1, v1.capacity() * sizeof(int)); EXPECT_THAT(allocated2, 0); v1.swap(v2); EXPECT_THAT(v1, ElementsAreArray(ia2)); EXPECT_THAT(v2, ElementsAreArray(ia1)); EXPECT_THAT(allocated1, v2.capacity() * sizeof(int)); EXPECT_THAT(allocated2, 0); EXPECT_TRUE(v2.get_allocator() == a1); EXPECT_TRUE(v1.get_allocator() == a2); } EXPECT_THAT(allocated1, 0); EXPECT_THAT(allocated2, 0); } TEST(AllocatorSupportTest, ScopedAllocatorWorks) { using StdVector = std::vector<int, CountingAllocator<int>>; using MyAlloc = std::scoped_allocator_adaptor<CountingAllocator<StdVector>>; using AllocVec = absl::InlinedVector<StdVector, 4, MyAlloc>; int64_t allocated = 0; AllocVec vec(MyAlloc{CountingAllocator<StdVector>{&allocated}}); EXPECT_EQ(allocated, 0); // This default constructs a vector<int>, but the allocator should pass itself // into the vector<int>. // The absl::InlinedVector does not allocate any memory. // The vector<int> does not allocate any memory. vec.resize(1); EXPECT_EQ(allocated, 0); // We make vector<int> allocate memory. // It must go through the allocator even though we didn't construct the // vector directly. vec[0].push_back(1); EXPECT_EQ(allocated, sizeof(int) * 1); // Another allocating vector. vec.push_back(vec[0]); EXPECT_EQ(allocated, sizeof(int) * 2); // Overflow the inlined memory. // The absl::InlinedVector will now allocate. vec.resize(5); EXPECT_EQ(allocated, sizeof(int) * 2 + sizeof(StdVector) * 8); // Adding one more in external mode should also work. vec.push_back(vec[0]); EXPECT_EQ(allocated, sizeof(int) * 3 + sizeof(StdVector) * 8); // And extending these should still work. vec[0].push_back(1); EXPECT_EQ(allocated, sizeof(int) * 4 + sizeof(StdVector) * 8); vec.clear(); EXPECT_EQ(allocated, 0); } TEST(AllocatorSupportTest, SizeAllocConstructor) { constexpr int inlined_size = 4; using Alloc = CountingAllocator<int>; using AllocVec = absl::InlinedVector<int, inlined_size, Alloc>; { auto len = inlined_size / 2; int64_t allocated = 0; auto v = AllocVec(len, Alloc(&allocated)); // Inline storage used; allocator should not be invoked EXPECT_THAT(allocated, 0); EXPECT_THAT(v, AllOf(SizeIs(len), Each(0))); } { auto len = inlined_size * 2; int64_t allocated = 0; auto v = AllocVec(len, Alloc(&allocated)); // Out of line storage used; allocation of 8 elements expected EXPECT_THAT(allocated, len * sizeof(int)); EXPECT_THAT(v, AllOf(SizeIs(len), Each(0))); } } } // anonymous namespace