918fe04351
PR-URL: https://github.com/nodejs/node/pull/58070 Reviewed-By: Antoine du Hamel <duhamelantoine1995@gmail.com> Reviewed-By: Darshan Sen <raisinten@gmail.com> Reviewed-By: Joyee Cheung <joyeec9h3@gmail.com> Reviewed-By: Rafael Gonzaga <rafael.nunu@hotmail.com>
2292 lines
73 KiB
C++
2292 lines
73 KiB
C++
// Copyright 2025 the V8 project authors. All rights reserved.
|
|
// Use of this source code is governed by a BSD-style license that can be
|
|
// found in the LICENSE file.
|
|
|
|
#include "src/base/small-vector.h"
|
|
|
|
#include <algorithm>
|
|
#include <array>
|
|
#include <initializer_list>
|
|
#include <vector>
|
|
|
|
#include "testing/gmock-support.h"
|
|
|
|
namespace v8::base {
|
|
|
|
namespace {
|
|
template <size_t n, int start, int... I>
|
|
std::initializer_list<int> make_int_list_impl(
|
|
std::integer_sequence<int, I...> s) {
|
|
static std::initializer_list<int> result{(start + I)...};
|
|
return result;
|
|
}
|
|
|
|
template <size_t n, int start = 0>
|
|
constexpr std::initializer_list<int> make_int_list() {
|
|
return make_int_list_impl<n, start>(std::make_integer_sequence<int, n>());
|
|
}
|
|
} // anonymous namespace
|
|
|
|
// Tests with vector elements that are trivially constructible/destructible.
|
|
|
|
TEST(SmallVectorTest, SimpleConstructTrivial) {
|
|
// A vector with zero capacity.
|
|
{
|
|
SmallVector<int, 0> v;
|
|
EXPECT_EQ(0UL, v.size());
|
|
EXPECT_EQ(0UL, v.capacity());
|
|
EXPECT_TRUE(v.empty());
|
|
}
|
|
|
|
// An implicitly empty small vector.
|
|
{
|
|
SmallVector<int, 10> v;
|
|
EXPECT_EQ(0UL, v.size());
|
|
EXPECT_EQ(10UL, v.capacity());
|
|
EXPECT_TRUE(v.empty());
|
|
}
|
|
|
|
// An explicitly empty small vector.
|
|
{
|
|
SmallVector<int, 10> v(0);
|
|
EXPECT_EQ(0UL, v.size());
|
|
EXPECT_EQ(10UL, v.capacity());
|
|
EXPECT_TRUE(v.empty());
|
|
}
|
|
|
|
// A non-empty, default-initialized small vector.
|
|
{
|
|
SmallVector<int, 10> v(5);
|
|
EXPECT_EQ(5UL, v.size());
|
|
EXPECT_EQ(10UL, v.capacity());
|
|
EXPECT_FALSE(v.empty());
|
|
}
|
|
|
|
// A non-empty, default-initialized big vector.
|
|
{
|
|
SmallVector<int, 10> v(15);
|
|
EXPECT_EQ(15UL, v.size());
|
|
EXPECT_LE(15UL, v.capacity());
|
|
EXPECT_FALSE(v.empty());
|
|
}
|
|
|
|
// A non-empty, explicitly initialized small vector.
|
|
{
|
|
SmallVector<int, 10> v(5, 42);
|
|
EXPECT_EQ(5UL, v.size());
|
|
EXPECT_EQ(10UL, v.capacity());
|
|
EXPECT_FALSE(v.empty());
|
|
EXPECT_EQ(42, v[3]);
|
|
}
|
|
|
|
// A non-empty, explicitly initialized big vector.
|
|
{
|
|
SmallVector<int, 10> v(15, 42);
|
|
EXPECT_EQ(15UL, v.size());
|
|
EXPECT_LE(15UL, v.capacity());
|
|
EXPECT_FALSE(v.empty());
|
|
EXPECT_EQ(42, v[13]);
|
|
}
|
|
}
|
|
|
|
TEST(SmallVectorTest, ConstructFromListTrivial) {
|
|
// Constructor from initializer list, small.
|
|
{
|
|
SmallVector<int, 10> v{make_int_list<7>()};
|
|
EXPECT_EQ(7UL, v.size());
|
|
EXPECT_EQ(10UL, v.capacity());
|
|
EXPECT_FALSE(v.empty());
|
|
EXPECT_EQ(5, v[5]);
|
|
}
|
|
|
|
// Constructor from initializer list, big.
|
|
{
|
|
SmallVector<int, 10> v{make_int_list<14>()};
|
|
EXPECT_EQ(14UL, v.size());
|
|
EXPECT_LE(14UL, v.capacity());
|
|
EXPECT_FALSE(v.empty());
|
|
EXPECT_EQ(3, v[3]);
|
|
EXPECT_EQ(11, v[11]);
|
|
}
|
|
}
|
|
|
|
TEST(SmallVectorTest, ConstructFromVectorTrivial) {
|
|
// Constructor from base::Vector, small.
|
|
{
|
|
SmallVector<int, 10> v(base::VectorOf(make_int_list<7>()));
|
|
EXPECT_EQ(7UL, v.size());
|
|
EXPECT_EQ(10UL, v.capacity());
|
|
EXPECT_FALSE(v.empty());
|
|
EXPECT_EQ(5, v[5]);
|
|
}
|
|
|
|
// Constructor from base::Vector, big.
|
|
{
|
|
SmallVector<int, 10> v(base::VectorOf(make_int_list<14>()));
|
|
EXPECT_EQ(14UL, v.size());
|
|
EXPECT_LE(14UL, v.capacity());
|
|
EXPECT_FALSE(v.empty());
|
|
EXPECT_EQ(3, v[3]);
|
|
EXPECT_EQ(11, v[11]);
|
|
}
|
|
}
|
|
|
|
TEST(SmallVectorTest, CopyConstructTrivial) {
|
|
// Copy constructor, small.
|
|
{
|
|
SmallVector<int, 10> v1{make_int_list<7>()};
|
|
SmallVector<int, 10> v2 = v1;
|
|
EXPECT_EQ(7UL, v1.size());
|
|
EXPECT_EQ(10UL, v1.capacity());
|
|
EXPECT_FALSE(v1.empty());
|
|
EXPECT_EQ(5, v1[5]);
|
|
EXPECT_EQ(7UL, v2.size());
|
|
EXPECT_EQ(10UL, v2.capacity());
|
|
EXPECT_FALSE(v2.empty());
|
|
EXPECT_EQ(5, v2[5]);
|
|
}
|
|
|
|
// Copy constructor, big.
|
|
{
|
|
SmallVector<int, 10> v1{make_int_list<14>()};
|
|
SmallVector<int, 10> v2 = v1;
|
|
EXPECT_EQ(14UL, v1.size());
|
|
EXPECT_LE(14UL, v1.capacity());
|
|
EXPECT_FALSE(v1.empty());
|
|
EXPECT_EQ(3, v1[3]);
|
|
EXPECT_EQ(11, v1[11]);
|
|
EXPECT_EQ(14UL, v2.size());
|
|
EXPECT_LE(14UL, v2.capacity());
|
|
EXPECT_FALSE(v2.empty());
|
|
EXPECT_EQ(3, v2[3]);
|
|
EXPECT_EQ(11, v2[11]);
|
|
}
|
|
}
|
|
|
|
TEST(SmallVectorTest, MoveConstructTrivial) {
|
|
// Move constructor, small.
|
|
{
|
|
SmallVector<int, 10> v1{make_int_list<7>()};
|
|
SmallVector<int, 10> v2 = std::move(v1);
|
|
EXPECT_EQ(0UL, v1.size());
|
|
EXPECT_EQ(10UL, v1.capacity());
|
|
EXPECT_TRUE(v1.empty());
|
|
EXPECT_EQ(7UL, v2.size());
|
|
EXPECT_EQ(10UL, v2.capacity());
|
|
EXPECT_FALSE(v2.empty());
|
|
EXPECT_EQ(5, v2[5]);
|
|
}
|
|
|
|
// Move constructor, big.
|
|
{
|
|
SmallVector<int, 10> v1{make_int_list<14>()};
|
|
SmallVector<int, 10> v2 = std::move(v1);
|
|
EXPECT_EQ(0UL, v1.size());
|
|
EXPECT_EQ(10UL, v1.capacity());
|
|
EXPECT_TRUE(v1.empty());
|
|
EXPECT_EQ(14UL, v2.size());
|
|
EXPECT_LE(14UL, v2.capacity());
|
|
EXPECT_FALSE(v2.empty());
|
|
EXPECT_EQ(3, v2[3]);
|
|
EXPECT_EQ(11, v2[11]);
|
|
}
|
|
}
|
|
|
|
namespace {
|
|
template <size_t capacity, size_t src_size, size_t trg_size>
|
|
void TestAssignTrivial() {
|
|
constexpr int src_isize = static_cast<int>(src_size);
|
|
SmallVector<int, capacity> src{make_int_list<src_size>()};
|
|
SmallVector<int, capacity> trg{make_int_list<trg_size, 1000>()};
|
|
trg = src;
|
|
EXPECT_EQ(src_size, src.size());
|
|
EXPECT_LE(capacity, src.capacity());
|
|
EXPECT_TRUE((src_size == 0) == src.empty());
|
|
EXPECT_EQ(src_size, trg.size());
|
|
EXPECT_LE(src_size, trg.capacity());
|
|
EXPECT_LE(capacity, trg.capacity());
|
|
EXPECT_TRUE((src_size == 0) == trg.empty());
|
|
for (int i = 0; i < src_isize; ++i) {
|
|
EXPECT_EQ(i, src[i]);
|
|
EXPECT_EQ(i, trg[i]);
|
|
}
|
|
}
|
|
} // anonymous namespace
|
|
|
|
TEST(SmallVectorTest, AssignTrivial) {
|
|
// Small vectors.
|
|
TestAssignTrivial<10, 7, 7>();
|
|
TestAssignTrivial<10, 5, 7>();
|
|
TestAssignTrivial<10, 9, 7>();
|
|
TestAssignTrivial<0, 0, 0>();
|
|
// Big vectors.
|
|
TestAssignTrivial<10, 17, 17>();
|
|
TestAssignTrivial<10, 15, 17>();
|
|
TestAssignTrivial<10, 19, 17>();
|
|
TestAssignTrivial<0, 7, 7>();
|
|
TestAssignTrivial<0, 7, 5>();
|
|
TestAssignTrivial<0, 5, 7>();
|
|
// Small assigned to big.
|
|
TestAssignTrivial<10, 17, 7>();
|
|
TestAssignTrivial<0, 17, 0>();
|
|
// Big assigned to small.
|
|
TestAssignTrivial<10, 7, 17>();
|
|
TestAssignTrivial<0, 0, 17>();
|
|
}
|
|
|
|
namespace {
|
|
template <size_t capacity, size_t src_size, size_t trg_size>
|
|
void TestMoveAssignTrivial() {
|
|
constexpr int src_isize = static_cast<int>(src_size);
|
|
SmallVector<int, capacity> src{make_int_list<src_size>()};
|
|
SmallVector<int, capacity> trg{make_int_list<trg_size, 1000>()};
|
|
trg = std::move(src);
|
|
EXPECT_EQ(0UL, src.size());
|
|
EXPECT_EQ(capacity, src.capacity());
|
|
EXPECT_TRUE(src.empty());
|
|
EXPECT_EQ(src_size, trg.size());
|
|
EXPECT_LE(src_size, trg.capacity());
|
|
EXPECT_LE(capacity, trg.capacity());
|
|
EXPECT_TRUE((src_size == 0) == trg.empty());
|
|
for (int i = 0; i < src_isize; ++i) {
|
|
EXPECT_EQ(i, trg[i]);
|
|
}
|
|
}
|
|
} // anonymous namespace
|
|
|
|
TEST(SmallVectorTest, MoveAssignTrivial) {
|
|
// Small vectors.
|
|
TestMoveAssignTrivial<10, 7, 7>();
|
|
TestMoveAssignTrivial<10, 5, 7>();
|
|
TestMoveAssignTrivial<10, 9, 7>();
|
|
TestMoveAssignTrivial<0, 0, 0>();
|
|
// Big vectors.
|
|
TestMoveAssignTrivial<10, 17, 17>();
|
|
TestMoveAssignTrivial<10, 15, 17>();
|
|
TestMoveAssignTrivial<10, 19, 17>();
|
|
TestMoveAssignTrivial<0, 7, 7>();
|
|
TestMoveAssignTrivial<0, 7, 5>();
|
|
TestMoveAssignTrivial<0, 5, 7>();
|
|
// Small assigned to big.
|
|
TestMoveAssignTrivial<10, 17, 7>();
|
|
TestMoveAssignTrivial<0, 17, 0>();
|
|
// Big assigned to small.
|
|
TestMoveAssignTrivial<10, 7, 17>();
|
|
TestMoveAssignTrivial<0, 0, 17>();
|
|
}
|
|
|
|
namespace {
|
|
template <size_t capacity, size_t src_size, size_t trg_size>
|
|
void TestCopySeparation() {
|
|
constexpr int src_isize = static_cast<int>(src_size);
|
|
static_assert(src_size >= 3);
|
|
static_assert(trg_size >= 3);
|
|
|
|
// Copy constructor results in vector with different backing store.
|
|
{
|
|
SmallVector<int, capacity> src{make_int_list<src_size>()};
|
|
SmallVector<int, capacity> trg = src;
|
|
for (int i = 0; i < src_isize; ++i) {
|
|
EXPECT_EQ(i, src[i]);
|
|
EXPECT_EQ(i, trg[i]);
|
|
}
|
|
src[1] = 17;
|
|
trg[2] = 42;
|
|
EXPECT_EQ(17, src[1]);
|
|
EXPECT_EQ(2, src[2]);
|
|
EXPECT_EQ(1, trg[1]);
|
|
EXPECT_EQ(42, trg[2]);
|
|
}
|
|
|
|
// Copy assignment results in vector with different backing store.
|
|
{
|
|
SmallVector<int, capacity> src{make_int_list<src_size>()};
|
|
SmallVector<int, capacity> trg{make_int_list<trg_size, 1000>()};
|
|
trg = src;
|
|
for (int i = 0; i < src_isize; ++i) {
|
|
EXPECT_EQ(i, src[i]);
|
|
EXPECT_EQ(i, trg[i]);
|
|
}
|
|
src[1] = 17;
|
|
trg[2] = 42;
|
|
EXPECT_EQ(17, src[1]);
|
|
EXPECT_EQ(2, src[2]);
|
|
EXPECT_EQ(1, trg[1]);
|
|
EXPECT_EQ(42, trg[2]);
|
|
}
|
|
}
|
|
} // anonymous namespace
|
|
|
|
TEST(SmallVectorTest, CopySeparation) {
|
|
// Small vectors.
|
|
TestCopySeparation<10, 7, 7>();
|
|
TestCopySeparation<10, 5, 7>();
|
|
TestCopySeparation<10, 9, 7>();
|
|
// Big vectors.
|
|
TestCopySeparation<10, 17, 17>();
|
|
TestCopySeparation<10, 15, 17>();
|
|
TestCopySeparation<10, 19, 17>();
|
|
// Small assigned to big.
|
|
TestCopySeparation<10, 17, 7>();
|
|
// Big assigned to small.
|
|
TestCopySeparation<10, 7, 17>();
|
|
}
|
|
|
|
namespace {
|
|
template <size_t capacity, size_t size>
|
|
void TestIteratorsTrivial() {
|
|
constexpr int isize = static_cast<int>(size);
|
|
SmallVector<int, capacity> v{make_int_list<size, 1>()};
|
|
|
|
// Forward.
|
|
{
|
|
auto it = v.begin();
|
|
for (int i = 0; i < isize; ++i) {
|
|
if (i == 0) EXPECT_EQ(*it, v.front());
|
|
if (i == isize - 1) EXPECT_EQ(*it, v.back());
|
|
EXPECT_EQ(*it, v[i]);
|
|
EXPECT_EQ(*it, v.at(i));
|
|
EXPECT_EQ(*it, i + 1);
|
|
++it;
|
|
}
|
|
EXPECT_EQ(it, v.end());
|
|
for (int i = isize - 1; i >= 0; --i) {
|
|
--it;
|
|
if (i == 0) EXPECT_EQ(*it, v.front());
|
|
if (i == isize - 1) EXPECT_EQ(*it, v.back());
|
|
EXPECT_EQ(*it, v[i]);
|
|
EXPECT_EQ(*it, v.at(i));
|
|
EXPECT_EQ(*it, i + 1);
|
|
}
|
|
EXPECT_EQ(it, v.begin());
|
|
}
|
|
|
|
// Reverse.
|
|
{
|
|
auto rit = v.rbegin();
|
|
for (int i = isize - 1; i >= 0; --i) {
|
|
if (i == 0) EXPECT_EQ(*rit, v.front());
|
|
if (i == isize - 1) EXPECT_EQ(*rit, v.back());
|
|
EXPECT_EQ(*rit, v[i]);
|
|
EXPECT_EQ(*rit, v.at(i));
|
|
EXPECT_EQ(*rit, i + 1);
|
|
++rit;
|
|
}
|
|
EXPECT_EQ(rit, v.rend());
|
|
for (int i = 0; i < isize; ++i) {
|
|
--rit;
|
|
if (i == 0) EXPECT_EQ(*rit, v.front());
|
|
if (i == isize - 1) EXPECT_EQ(*rit, v.back());
|
|
EXPECT_EQ(*rit, v[i]);
|
|
EXPECT_EQ(*rit, v.at(i));
|
|
EXPECT_EQ(*rit, i + 1);
|
|
}
|
|
EXPECT_EQ(rit, v.rbegin());
|
|
}
|
|
|
|
// For loops.
|
|
{
|
|
int s = 0;
|
|
for (int x : v) s += x;
|
|
EXPECT_EQ(isize * (isize + 1) / 2, s);
|
|
s = 0;
|
|
for (const int& x : v) s += x;
|
|
EXPECT_EQ(isize * (isize + 1) / 2, s);
|
|
for (int& x : v) x += 1000;
|
|
for (int i = 0; i < isize; ++i) EXPECT_EQ(i + 1001, v[i]);
|
|
}
|
|
}
|
|
} // anonymous namespace
|
|
|
|
TEST(SmallVectorTest, IteratorsTrivial) {
|
|
TestIteratorsTrivial<10, 2>();
|
|
TestIteratorsTrivial<10, 2>();
|
|
TestIteratorsTrivial<10, 7>();
|
|
TestIteratorsTrivial<10, 17>();
|
|
TestIteratorsTrivial<0, 7>();
|
|
}
|
|
|
|
namespace {
|
|
template <size_t capacity, size_t size>
|
|
void TestAccessorsTrivial() {
|
|
constexpr int isize = static_cast<int>(size);
|
|
static_assert(size >= 2);
|
|
SmallVector<int, capacity> v{make_int_list<size, 1>()};
|
|
|
|
// Front.
|
|
{
|
|
EXPECT_EQ(v[0], v.front());
|
|
EXPECT_EQ(1, v.front());
|
|
v.front() += 1000;
|
|
EXPECT_EQ(v[0], v.front());
|
|
EXPECT_EQ(1001, v.front());
|
|
v.front() -= 1000;
|
|
EXPECT_EQ(v[0], v.front());
|
|
EXPECT_EQ(1, v.front());
|
|
}
|
|
|
|
// Back.
|
|
{
|
|
EXPECT_EQ(v[size - 1], v.back());
|
|
EXPECT_EQ(isize, v.back());
|
|
v.back() += 1000;
|
|
EXPECT_EQ(v[size - 1], v.back());
|
|
EXPECT_EQ(1000 + isize, v.back());
|
|
v.back() -= 1000;
|
|
EXPECT_EQ(v[size - 1], v.back());
|
|
EXPECT_EQ(isize, v.back());
|
|
}
|
|
|
|
// At, operator[].
|
|
{
|
|
for (int i = 0; i < isize; ++i) {
|
|
EXPECT_EQ(v[i], v.at(i));
|
|
EXPECT_EQ(i + 1, v.at(i));
|
|
v.at(i) += 1000;
|
|
EXPECT_EQ(v[i], v.at(i));
|
|
EXPECT_EQ(i + 1001, v.at(i));
|
|
v.at(i) -= 1000;
|
|
EXPECT_EQ(v[i], v.at(i));
|
|
EXPECT_EQ(i + 1, v.at(i));
|
|
}
|
|
}
|
|
}
|
|
} // anonymous namespace
|
|
|
|
TEST(SmallVectorTest, AccessorsTrivial) {
|
|
TestAccessorsTrivial<10, 2>();
|
|
TestAccessorsTrivial<10, 7>();
|
|
TestAccessorsTrivial<10, 17>();
|
|
TestAccessorsTrivial<0, 7>();
|
|
}
|
|
|
|
namespace {
|
|
template <size_t capacity, size_t size, size_t added>
|
|
void TestPushPopTrivial() {
|
|
constexpr int isize = static_cast<int>(size);
|
|
constexpr int iadded = static_cast<int>(added);
|
|
static_assert(added >= 2);
|
|
SmallVector<int, capacity> v{make_int_list<size, 1>()};
|
|
|
|
// Push a few elements.
|
|
for (int i = 0; i < iadded; ++i) {
|
|
v.push_back(1000 + i);
|
|
EXPECT_EQ(size + i + 1, v.size());
|
|
EXPECT_LE(size + i + 1, v.capacity());
|
|
EXPECT_EQ(1000 + i, v[size + i]);
|
|
}
|
|
|
|
// Pop one element.
|
|
EXPECT_EQ(1000 + iadded - 1, v.back());
|
|
v.pop_back();
|
|
EXPECT_EQ(size + added - 1, v.size());
|
|
EXPECT_LE(size + added - 1, v.capacity());
|
|
EXPECT_EQ(1000 + iadded - 2, v.back());
|
|
|
|
// Pop the remaining elements that were added.
|
|
v.pop_back(added - 1);
|
|
EXPECT_EQ(size, v.size());
|
|
EXPECT_LE(size, v.capacity());
|
|
if constexpr (size > 0) EXPECT_EQ(isize, v.back());
|
|
|
|
// Pop all elements.
|
|
v.pop_back(size);
|
|
EXPECT_EQ(0UL, v.size());
|
|
EXPECT_LE(size, v.capacity());
|
|
EXPECT_TRUE(v.empty());
|
|
EXPECT_EQ(v.begin(), v.end());
|
|
EXPECT_EQ(v.rbegin(), v.rend());
|
|
}
|
|
} // anonymous namespace
|
|
|
|
TEST(SmallVectorTest, PushPopTrivial) {
|
|
TestPushPopTrivial<10, 7, 2>();
|
|
TestPushPopTrivial<10, 7, 3>();
|
|
TestPushPopTrivial<10, 7, 5>();
|
|
TestPushPopTrivial<10, 10, 2>();
|
|
TestPushPopTrivial<10, 17, 2>();
|
|
TestPushPopTrivial<0, 0, 7>();
|
|
TestPushPopTrivial<0, 0, 17>();
|
|
}
|
|
|
|
namespace {
|
|
template <size_t capacity, size_t size, size_t added>
|
|
void TestEmplacePopTrivial() {
|
|
constexpr int isize = static_cast<int>(size);
|
|
constexpr int iadded = static_cast<int>(added);
|
|
static_assert(added >= 2);
|
|
SmallVector<int, capacity> v{make_int_list<size, 1>()};
|
|
|
|
// Push a few elements.
|
|
for (int i = 0; i < iadded; ++i) {
|
|
v.emplace_back(1000 + i);
|
|
EXPECT_EQ(size + i + 1, v.size());
|
|
EXPECT_LE(size + i + 1, v.capacity());
|
|
EXPECT_EQ(1000 + i, v[size + i]);
|
|
}
|
|
|
|
// Pop one element.
|
|
EXPECT_EQ(1000 + iadded - 1, v.back());
|
|
v.pop_back();
|
|
EXPECT_EQ(size + added - 1, v.size());
|
|
EXPECT_LE(size + added - 1, v.capacity());
|
|
EXPECT_EQ(1000 + iadded - 2, v.back());
|
|
|
|
// Pop the remaining elements that were added.
|
|
v.pop_back(added - 1);
|
|
EXPECT_EQ(size, v.size());
|
|
EXPECT_LE(size, v.capacity());
|
|
if constexpr (size > 0) EXPECT_EQ(isize, v.back());
|
|
|
|
// Pop all elements.
|
|
v.pop_back(size);
|
|
EXPECT_EQ(0UL, v.size());
|
|
EXPECT_LE(size, v.capacity());
|
|
EXPECT_TRUE(v.empty());
|
|
EXPECT_EQ(v.begin(), v.end());
|
|
EXPECT_EQ(v.rbegin(), v.rend());
|
|
}
|
|
} // anonymous namespace
|
|
|
|
TEST(SmallVectorTest, EmplacePopTrivial) {
|
|
TestEmplacePopTrivial<10, 7, 2>();
|
|
TestEmplacePopTrivial<10, 7, 3>();
|
|
TestEmplacePopTrivial<10, 7, 5>();
|
|
TestEmplacePopTrivial<10, 10, 2>();
|
|
TestEmplacePopTrivial<10, 17, 2>();
|
|
TestEmplacePopTrivial<0, 0, 7>();
|
|
TestEmplacePopTrivial<0, 0, 17>();
|
|
}
|
|
|
|
namespace {
|
|
template <size_t capacity, size_t size, size_t pos>
|
|
void TestInsertSimpleTrivial() {
|
|
constexpr int isize = static_cast<int>(size);
|
|
constexpr int ipos = static_cast<int>(pos);
|
|
static_assert(pos <= size);
|
|
SmallVector<int, capacity> v{make_int_list<size, 1>()};
|
|
|
|
v.insert(v.begin() + pos, 1000);
|
|
EXPECT_EQ(size + 1, v.size());
|
|
EXPECT_LE(size + 1, v.capacity());
|
|
for (int i = 0; i < ipos; ++i) EXPECT_EQ(i + 1, v[i]);
|
|
EXPECT_EQ(1000, v[pos]);
|
|
for (int i = ipos + 1; i < isize + 1; ++i) EXPECT_EQ(i, v[i]);
|
|
}
|
|
} // anonymous namespace
|
|
|
|
TEST(SmallVectorTest, InsertSimpleTrivial) {
|
|
TestInsertSimpleTrivial<10, 7, 0>();
|
|
TestInsertSimpleTrivial<10, 7, 4>();
|
|
TestInsertSimpleTrivial<10, 7, 7>();
|
|
TestInsertSimpleTrivial<10, 10, 0>();
|
|
TestInsertSimpleTrivial<10, 10, 4>();
|
|
TestInsertSimpleTrivial<10, 10, 7>();
|
|
TestInsertSimpleTrivial<10, 17, 0>();
|
|
TestInsertSimpleTrivial<10, 17, 13>();
|
|
TestInsertSimpleTrivial<10, 17, 17>();
|
|
TestInsertSimpleTrivial<0, 0, 0>();
|
|
TestInsertSimpleTrivial<0, 7, 0>();
|
|
TestInsertSimpleTrivial<0, 7, 4>();
|
|
TestInsertSimpleTrivial<0, 7, 7>();
|
|
}
|
|
|
|
namespace {
|
|
template <size_t capacity, size_t size, size_t pos, size_t added>
|
|
void TestInsertMultipleTrivial() {
|
|
constexpr int isize = static_cast<int>(size);
|
|
constexpr int ipos = static_cast<int>(pos);
|
|
constexpr int iadded = static_cast<int>(added);
|
|
static_assert(pos <= size);
|
|
SmallVector<int, capacity> v{make_int_list<size, 1>()};
|
|
|
|
v.insert(v.begin() + pos, added, 1000);
|
|
EXPECT_EQ(size + added, v.size());
|
|
EXPECT_LE(size + added, v.capacity());
|
|
for (int i = 0; i < ipos; ++i) EXPECT_EQ(i + 1, v[i]);
|
|
for (int i = ipos; i < ipos + iadded; ++i) EXPECT_EQ(1000, v[i]);
|
|
for (int i = ipos + iadded; i < isize + iadded; ++i)
|
|
EXPECT_EQ(i - iadded + 1, v[i]);
|
|
}
|
|
} // anonymous namespace
|
|
|
|
TEST(SmallVectorTest, InsertMultipleTrivial) {
|
|
TestInsertMultipleTrivial<10, 7, 0, 2>();
|
|
TestInsertMultipleTrivial<10, 7, 4, 2>();
|
|
TestInsertMultipleTrivial<10, 7, 7, 2>();
|
|
TestInsertMultipleTrivial<10, 7, 0, 3>();
|
|
TestInsertMultipleTrivial<10, 7, 4, 3>();
|
|
TestInsertMultipleTrivial<10, 7, 7, 3>();
|
|
TestInsertMultipleTrivial<10, 7, 0, 4>();
|
|
TestInsertMultipleTrivial<10, 7, 4, 4>();
|
|
TestInsertMultipleTrivial<10, 7, 7, 4>();
|
|
TestInsertMultipleTrivial<10, 10, 0, 2>();
|
|
TestInsertMultipleTrivial<10, 10, 4, 2>();
|
|
TestInsertMultipleTrivial<10, 10, 7, 2>();
|
|
TestInsertMultipleTrivial<10, 17, 0, 2>();
|
|
TestInsertMultipleTrivial<10, 17, 13, 2>();
|
|
TestInsertMultipleTrivial<10, 17, 17, 2>();
|
|
TestInsertMultipleTrivial<0, 0, 0, 2>();
|
|
TestInsertMultipleTrivial<0, 7, 0, 2>();
|
|
TestInsertMultipleTrivial<0, 7, 4, 2>();
|
|
TestInsertMultipleTrivial<0, 7, 7, 2>();
|
|
}
|
|
|
|
namespace {
|
|
template <size_t capacity, size_t size, size_t pos, size_t added>
|
|
void TestInsertListTrivial() {
|
|
constexpr int isize = static_cast<int>(size);
|
|
constexpr int ipos = static_cast<int>(pos);
|
|
constexpr int iadded = static_cast<int>(added);
|
|
static_assert(pos <= size);
|
|
SmallVector<int, capacity> v{make_int_list<size, 1>()};
|
|
|
|
v.insert(v.begin() + pos, make_int_list<added, 1000>());
|
|
EXPECT_EQ(size + added, v.size());
|
|
EXPECT_LE(size + added, v.capacity());
|
|
for (int i = 0; i < ipos; ++i) EXPECT_EQ(i + 1, v[i]);
|
|
for (int i = ipos; i < ipos + iadded; ++i) EXPECT_EQ(1000 + i - ipos, v[i]);
|
|
for (int i = ipos + iadded; i < isize + iadded; ++i)
|
|
EXPECT_EQ(i - iadded + 1, v[i]);
|
|
}
|
|
} // anonymous namespace
|
|
|
|
TEST(SmallVectorTest, InsertListTrivial) {
|
|
TestInsertListTrivial<10, 7, 0, 2>();
|
|
TestInsertListTrivial<10, 7, 4, 2>();
|
|
TestInsertListTrivial<10, 7, 7, 2>();
|
|
TestInsertListTrivial<10, 7, 0, 3>();
|
|
TestInsertListTrivial<10, 7, 4, 3>();
|
|
TestInsertListTrivial<10, 7, 7, 3>();
|
|
TestInsertListTrivial<10, 7, 0, 4>();
|
|
TestInsertListTrivial<10, 7, 4, 4>();
|
|
TestInsertListTrivial<10, 7, 7, 4>();
|
|
TestInsertListTrivial<10, 10, 0, 2>();
|
|
TestInsertListTrivial<10, 10, 4, 2>();
|
|
TestInsertListTrivial<10, 10, 7, 2>();
|
|
TestInsertListTrivial<10, 17, 0, 2>();
|
|
TestInsertListTrivial<10, 17, 13, 2>();
|
|
TestInsertListTrivial<10, 17, 17, 2>();
|
|
TestInsertListTrivial<0, 0, 0, 2>();
|
|
TestInsertListTrivial<0, 7, 0, 2>();
|
|
TestInsertListTrivial<0, 7, 4, 2>();
|
|
TestInsertListTrivial<0, 7, 7, 2>();
|
|
}
|
|
|
|
namespace {
|
|
template <size_t capacity, size_t size, size_t pos, size_t added>
|
|
void TestInsertIterTrivial() {
|
|
constexpr int isize = static_cast<int>(size);
|
|
constexpr int ipos = static_cast<int>(pos);
|
|
constexpr int iadded = static_cast<int>(added);
|
|
static_assert(pos <= size);
|
|
SmallVector<int, capacity> v{make_int_list<size, 1>()};
|
|
std::vector<int> vec(make_int_list<added, 1000>());
|
|
|
|
v.insert(v.begin() + pos, vec.begin(), vec.end());
|
|
EXPECT_EQ(size + added, v.size());
|
|
EXPECT_LE(size + added, v.capacity());
|
|
for (int i = 0; i < ipos; ++i) EXPECT_EQ(i + 1, v[i]);
|
|
for (int i = ipos; i < ipos + iadded; ++i) EXPECT_EQ(1000 + i - ipos, v[i]);
|
|
for (int i = ipos + iadded; i < isize + iadded; ++i)
|
|
EXPECT_EQ(i - iadded + 1, v[i]);
|
|
}
|
|
} // anonymous namespace
|
|
|
|
TEST(SmallVectorTest, InsertIterTrivial) {
|
|
TestInsertIterTrivial<10, 7, 0, 2>();
|
|
TestInsertIterTrivial<10, 7, 4, 2>();
|
|
TestInsertIterTrivial<10, 7, 7, 2>();
|
|
TestInsertIterTrivial<10, 7, 0, 3>();
|
|
TestInsertIterTrivial<10, 7, 4, 3>();
|
|
TestInsertIterTrivial<10, 7, 7, 3>();
|
|
TestInsertIterTrivial<10, 7, 0, 4>();
|
|
TestInsertIterTrivial<10, 7, 4, 4>();
|
|
TestInsertIterTrivial<10, 7, 7, 4>();
|
|
TestInsertIterTrivial<10, 10, 0, 2>();
|
|
TestInsertIterTrivial<10, 10, 4, 2>();
|
|
TestInsertIterTrivial<10, 10, 7, 2>();
|
|
TestInsertIterTrivial<10, 17, 0, 2>();
|
|
TestInsertIterTrivial<10, 17, 13, 2>();
|
|
TestInsertIterTrivial<10, 17, 17, 2>();
|
|
TestInsertIterTrivial<0, 0, 0, 2>();
|
|
TestInsertIterTrivial<0, 7, 0, 2>();
|
|
TestInsertIterTrivial<0, 7, 4, 2>();
|
|
TestInsertIterTrivial<0, 7, 7, 2>();
|
|
}
|
|
|
|
namespace {
|
|
template <size_t capacity, size_t size, size_t pos>
|
|
void TestEraseTrivial() {
|
|
constexpr int ipos = static_cast<int>(pos);
|
|
static_assert(pos <= size);
|
|
SmallVector<int, capacity> v{make_int_list<size, 1>()};
|
|
const size_t real_capacity = v.capacity();
|
|
|
|
v.erase(v.begin() + pos);
|
|
EXPECT_EQ(pos, v.size());
|
|
EXPECT_EQ(real_capacity, v.capacity());
|
|
for (int i = 0; i < ipos; ++i) EXPECT_EQ(i + 1, v[i]);
|
|
}
|
|
} // anonymous namespace
|
|
|
|
TEST(SmallVectorTest, EraseTrivial) {
|
|
TestEraseTrivial<10, 7, 0>();
|
|
TestEraseTrivial<10, 7, 4>();
|
|
TestEraseTrivial<10, 7, 7>();
|
|
TestEraseTrivial<10, 10, 0>();
|
|
TestEraseTrivial<10, 10, 4>();
|
|
TestEraseTrivial<10, 10, 7>();
|
|
TestEraseTrivial<10, 17, 0>();
|
|
TestEraseTrivial<10, 17, 13>();
|
|
TestEraseTrivial<10, 17, 17>();
|
|
TestEraseTrivial<0, 0, 0>();
|
|
TestEraseTrivial<0, 7, 0>();
|
|
TestEraseTrivial<0, 7, 4>();
|
|
TestEraseTrivial<0, 7, 7>();
|
|
}
|
|
|
|
namespace {
|
|
template <size_t capacity, size_t size, size_t new_size>
|
|
void TestResizeTrivial() {
|
|
constexpr int isize = static_cast<int>(size);
|
|
constexpr int new_isize = static_cast<int>(new_size);
|
|
SmallVector<int, capacity> v{make_int_list<size, 1>()};
|
|
const size_t real_capacity = v.capacity();
|
|
|
|
v.resize(new_size);
|
|
EXPECT_EQ(new_size, v.size());
|
|
if (new_size <= real_capacity) {
|
|
EXPECT_EQ(real_capacity, v.capacity());
|
|
} else {
|
|
EXPECT_LE(new_size, v.capacity());
|
|
}
|
|
for (int i = 0; i < std::min(isize, new_isize); ++i) EXPECT_EQ(i + 1, v[i]);
|
|
}
|
|
} // anonymous namespace
|
|
|
|
TEST(SmallVectorTest, ResizeTrivial) {
|
|
TestResizeTrivial<10, 7, 0>();
|
|
TestResizeTrivial<10, 7, 4>();
|
|
TestResizeTrivial<10, 7, 7>();
|
|
TestResizeTrivial<10, 7, 9>();
|
|
TestResizeTrivial<10, 7, 10>();
|
|
TestResizeTrivial<10, 7, 12>();
|
|
TestResizeTrivial<10, 17, 0>();
|
|
TestResizeTrivial<10, 17, 7>();
|
|
TestResizeTrivial<10, 17, 17>();
|
|
TestResizeTrivial<10, 17, 20>();
|
|
TestResizeTrivial<10, 17, 100>();
|
|
TestResizeTrivial<0, 0, 0>();
|
|
TestResizeTrivial<0, 0, 5>();
|
|
TestResizeTrivial<0, 7, 0>();
|
|
TestResizeTrivial<0, 7, 4>();
|
|
TestResizeTrivial<0, 7, 7>();
|
|
TestResizeTrivial<0, 7, 10>();
|
|
TestResizeTrivial<0, 7, 100>();
|
|
}
|
|
|
|
namespace {
|
|
template <size_t capacity, size_t size, size_t new_size>
|
|
void TestResizeInitTrivial() {
|
|
constexpr int isize = static_cast<int>(size);
|
|
constexpr int new_isize = static_cast<int>(new_size);
|
|
SmallVector<int, capacity> v{make_int_list<size, 1>()};
|
|
const size_t real_capacity = v.capacity();
|
|
|
|
v.resize(new_size, 42);
|
|
EXPECT_EQ(new_size, v.size());
|
|
if (new_size <= real_capacity) {
|
|
EXPECT_EQ(real_capacity, v.capacity());
|
|
} else {
|
|
EXPECT_LE(new_size, v.capacity());
|
|
}
|
|
for (int i = 0; i < std::min(isize, new_isize); ++i) EXPECT_EQ(i + 1, v[i]);
|
|
for (int i = isize; i < new_isize; ++i) EXPECT_EQ(42, v[i]);
|
|
}
|
|
} // anonymous namespace
|
|
|
|
TEST(SmallVectorTest, ResizeInitTrivial) {
|
|
TestResizeInitTrivial<10, 7, 0>();
|
|
TestResizeInitTrivial<10, 7, 4>();
|
|
TestResizeInitTrivial<10, 7, 7>();
|
|
TestResizeInitTrivial<10, 7, 9>();
|
|
TestResizeInitTrivial<10, 7, 10>();
|
|
TestResizeInitTrivial<10, 7, 12>();
|
|
TestResizeInitTrivial<10, 17, 0>();
|
|
TestResizeInitTrivial<10, 17, 7>();
|
|
TestResizeInitTrivial<10, 17, 17>();
|
|
TestResizeInitTrivial<10, 17, 20>();
|
|
TestResizeInitTrivial<10, 17, 100>();
|
|
TestResizeInitTrivial<0, 0, 0>();
|
|
TestResizeInitTrivial<0, 0, 5>();
|
|
TestResizeInitTrivial<0, 7, 0>();
|
|
TestResizeInitTrivial<0, 7, 4>();
|
|
TestResizeInitTrivial<0, 7, 7>();
|
|
TestResizeInitTrivial<0, 7, 10>();
|
|
TestResizeInitTrivial<0, 7, 100>();
|
|
}
|
|
|
|
namespace {
|
|
template <size_t capacity, size_t size, size_t new_size>
|
|
void TestReserveTrivial() {
|
|
constexpr int isize = static_cast<int>(size);
|
|
SmallVector<int, capacity> v{make_int_list<size, 1>()};
|
|
const size_t real_capacity = v.capacity();
|
|
|
|
v.reserve(new_size);
|
|
EXPECT_EQ(size, v.size());
|
|
if (new_size <= real_capacity) {
|
|
EXPECT_EQ(real_capacity, v.capacity());
|
|
} else {
|
|
EXPECT_LE(new_size, v.capacity());
|
|
}
|
|
for (int i = 0; i < isize; ++i) EXPECT_EQ(i + 1, v[i]);
|
|
}
|
|
} // anonymous namespace
|
|
|
|
TEST(SmallVectorTest, ReserveTrivial) {
|
|
TestReserveTrivial<10, 7, 0>();
|
|
TestReserveTrivial<10, 7, 4>();
|
|
TestReserveTrivial<10, 7, 7>();
|
|
TestReserveTrivial<10, 7, 9>();
|
|
TestReserveTrivial<10, 7, 10>();
|
|
TestReserveTrivial<10, 7, 12>();
|
|
TestReserveTrivial<10, 17, 0>();
|
|
TestReserveTrivial<10, 17, 7>();
|
|
TestReserveTrivial<10, 17, 17>();
|
|
TestReserveTrivial<10, 17, 20>();
|
|
TestReserveTrivial<10, 17, 100>();
|
|
TestReserveTrivial<0, 0, 0>();
|
|
TestReserveTrivial<0, 0, 5>();
|
|
TestReserveTrivial<0, 7, 0>();
|
|
TestReserveTrivial<0, 7, 4>();
|
|
TestReserveTrivial<0, 7, 7>();
|
|
TestReserveTrivial<0, 7, 10>();
|
|
TestReserveTrivial<0, 7, 100>();
|
|
}
|
|
|
|
namespace {
|
|
template <size_t capacity, size_t size>
|
|
void TestClearTrivial() {
|
|
SmallVector<int, capacity> v{make_int_list<size, 1>()};
|
|
const size_t real_capacity = v.capacity();
|
|
|
|
v.clear();
|
|
EXPECT_EQ(0UL, v.size());
|
|
EXPECT_EQ(real_capacity, v.capacity());
|
|
EXPECT_TRUE(v.empty());
|
|
EXPECT_EQ(v.begin(), v.end());
|
|
EXPECT_EQ(v.rbegin(), v.rend());
|
|
}
|
|
} // anonymous namespace
|
|
|
|
TEST(SmallVectorTest, ClearTrivial) {
|
|
TestClearTrivial<10, 7>();
|
|
TestClearTrivial<10, 17>();
|
|
TestClearTrivial<0, 0>();
|
|
TestClearTrivial<0, 7>();
|
|
}
|
|
|
|
// Tests with vector elements that are non-trivially constructible/destructible.
|
|
|
|
namespace {
|
|
|
|
enum CounterType : int {
|
|
kDefaultConstructor,
|
|
kExplicitConstructor,
|
|
kCopyConstructor,
|
|
kMoveConstructor,
|
|
kDestructor,
|
|
kCopyAssignment,
|
|
kMoveAssignment,
|
|
// The number of immediate counters (array size).
|
|
kSize,
|
|
// The rest is derived counters.
|
|
kAll = kSize,
|
|
kConstructor,
|
|
kAssignment,
|
|
};
|
|
|
|
// A class representing non-trivial object, that count the total number of
|
|
// constructor, destructor, and assignment operator calls.
|
|
template <typename T>
|
|
class NonTrivial {
|
|
public:
|
|
NonTrivial() : constructed_(true), value_() {
|
|
++counter_[kDefaultConstructor];
|
|
}
|
|
|
|
explicit NonTrivial(const T& val) : constructed_(true), value_(val) {
|
|
++counter_[kExplicitConstructor];
|
|
}
|
|
|
|
NonTrivial(const NonTrivial& src) : constructed_(true), value_(src.value()) {
|
|
++counter_[kCopyConstructor];
|
|
}
|
|
|
|
NonTrivial(NonTrivial&& src) : constructed_(true), value_(src.value()) {
|
|
src.value_ = 0;
|
|
++counter_[kMoveConstructor];
|
|
}
|
|
|
|
~NonTrivial() {
|
|
EXPECT_TRUE(constructed_);
|
|
++counter_[kDestructor];
|
|
constructed_ = false;
|
|
}
|
|
|
|
NonTrivial& operator=(const NonTrivial& src) {
|
|
EXPECT_TRUE(constructed_);
|
|
value_ = src.value();
|
|
++counter_[kCopyAssignment];
|
|
return *this;
|
|
}
|
|
|
|
NonTrivial& operator=(NonTrivial&& src) {
|
|
EXPECT_TRUE(constructed_);
|
|
value_ = src.value();
|
|
src.value_ = 0;
|
|
++counter_[kMoveAssignment];
|
|
return *this;
|
|
}
|
|
|
|
friend bool operator==(const NonTrivial& x, const NonTrivial& y) {
|
|
return x.value() == y.value();
|
|
}
|
|
|
|
bool constructed() const { return constructed_; }
|
|
|
|
const T& value() const {
|
|
EXPECT_TRUE(constructed_);
|
|
return value_;
|
|
}
|
|
|
|
static void ResetCounters() {
|
|
for (int i = 0; i < kSize; ++i) counter_[i] = 0;
|
|
}
|
|
|
|
static int GetCounter(CounterType i) {
|
|
switch (i) {
|
|
case kAll:
|
|
return counter_[kDefaultConstructor] + counter_[kExplicitConstructor] +
|
|
counter_[kCopyConstructor] + counter_[kMoveConstructor] +
|
|
counter_[kDestructor] + counter_[kCopyAssignment] +
|
|
counter_[kMoveAssignment];
|
|
case kConstructor:
|
|
return counter_[kDefaultConstructor] + counter_[kExplicitConstructor] +
|
|
counter_[kCopyConstructor] + counter_[kMoveConstructor];
|
|
case kAssignment:
|
|
return counter_[kCopyAssignment] + counter_[kMoveAssignment];
|
|
default:
|
|
CHECK_LT(i, kSize);
|
|
return counter_[i];
|
|
}
|
|
}
|
|
|
|
private:
|
|
static std::array<int, kSize> counter_;
|
|
|
|
bool constructed_;
|
|
T value_;
|
|
};
|
|
|
|
template <typename T>
|
|
std::array<int, kSize> NonTrivial<T>::counter_ = {0};
|
|
|
|
template <size_t n, int start, int... I>
|
|
std::array<NonTrivial<int>, n> make_non_trivial_array_impl(
|
|
std::integer_sequence<int, I...> s) {
|
|
return std::array<NonTrivial<int>, n>{NonTrivial<int>(start + I)...};
|
|
}
|
|
|
|
template <size_t n, int start = 0>
|
|
constexpr std::array<NonTrivial<int>, n> make_non_trivial_array() {
|
|
return make_non_trivial_array_impl<n, start>(
|
|
std::make_integer_sequence<int, n>());
|
|
}
|
|
|
|
} // anonymous namespace
|
|
|
|
TEST(SmallVectorTest, SimpleConstructNonTrivial) {
|
|
using ElementType = NonTrivial<int>;
|
|
const ElementType nt42(42);
|
|
EXPECT_EQ(1, ElementType::GetCounter(kExplicitConstructor));
|
|
EXPECT_EQ(1, ElementType::GetCounter(kAll));
|
|
ElementType::ResetCounters();
|
|
|
|
// A vector with zero capacity.
|
|
{
|
|
SmallVector<ElementType, 0> v;
|
|
EXPECT_EQ(0UL, v.size());
|
|
EXPECT_EQ(0UL, v.capacity());
|
|
EXPECT_TRUE(v.empty());
|
|
}
|
|
EXPECT_EQ(0, ElementType::GetCounter(kAll));
|
|
ElementType::ResetCounters();
|
|
|
|
// An implicitly empty small vector.
|
|
{
|
|
SmallVector<ElementType, 10> v;
|
|
EXPECT_EQ(0UL, v.size());
|
|
EXPECT_EQ(10UL, v.capacity());
|
|
EXPECT_TRUE(v.empty());
|
|
}
|
|
EXPECT_EQ(0, ElementType::GetCounter(kAll));
|
|
ElementType::ResetCounters();
|
|
|
|
// An explicitly empty small vector.
|
|
{
|
|
SmallVector<ElementType, 10> v(0);
|
|
EXPECT_EQ(0UL, v.size());
|
|
EXPECT_EQ(10UL, v.capacity());
|
|
EXPECT_TRUE(v.empty());
|
|
}
|
|
EXPECT_EQ(0, ElementType::GetCounter(kAll));
|
|
ElementType::ResetCounters();
|
|
|
|
// A non-empty, default-initialized small vector.
|
|
{
|
|
SmallVector<ElementType, 10> v(5);
|
|
EXPECT_EQ(5UL, v.size());
|
|
EXPECT_EQ(10UL, v.capacity());
|
|
EXPECT_FALSE(v.empty());
|
|
}
|
|
EXPECT_EQ(5, ElementType::GetCounter(kDefaultConstructor));
|
|
EXPECT_EQ(5, ElementType::GetCounter(kDestructor));
|
|
EXPECT_EQ(10, ElementType::GetCounter(kAll));
|
|
ElementType::ResetCounters();
|
|
|
|
// A non-empty, default-initialized big vector.
|
|
{
|
|
SmallVector<ElementType, 10> v(15);
|
|
EXPECT_EQ(15UL, v.size());
|
|
EXPECT_LE(15UL, v.capacity());
|
|
EXPECT_FALSE(v.empty());
|
|
}
|
|
EXPECT_EQ(15, ElementType::GetCounter(kDefaultConstructor));
|
|
EXPECT_EQ(15, ElementType::GetCounter(kDestructor));
|
|
EXPECT_EQ(30, ElementType::GetCounter(kAll));
|
|
ElementType::ResetCounters();
|
|
|
|
// A non-empty, explicitly initialized small vector.
|
|
{
|
|
SmallVector<ElementType, 10> v(5, nt42);
|
|
EXPECT_EQ(5UL, v.size());
|
|
EXPECT_EQ(10UL, v.capacity());
|
|
EXPECT_FALSE(v.empty());
|
|
EXPECT_EQ(42, v[3].value());
|
|
}
|
|
EXPECT_EQ(5, ElementType::GetCounter(kCopyConstructor));
|
|
EXPECT_EQ(5, ElementType::GetCounter(kDestructor));
|
|
EXPECT_EQ(10, ElementType::GetCounter(kAll));
|
|
ElementType::ResetCounters();
|
|
|
|
// A non-empty, explicitly initialized big vector.
|
|
{
|
|
SmallVector<ElementType, 10> v(15, nt42);
|
|
EXPECT_EQ(15UL, v.size());
|
|
EXPECT_LE(15UL, v.capacity());
|
|
EXPECT_FALSE(v.empty());
|
|
EXPECT_EQ(42, v[13].value());
|
|
}
|
|
EXPECT_EQ(15, ElementType::GetCounter(kCopyConstructor));
|
|
EXPECT_EQ(15, ElementType::GetCounter(kDestructor));
|
|
EXPECT_EQ(30, ElementType::GetCounter(kAll));
|
|
ElementType::ResetCounters();
|
|
}
|
|
|
|
TEST(SmallVectorTest, ConstructFromListNonTrivial) {
|
|
using ElementType = NonTrivial<int>;
|
|
std::initializer_list<ElementType> small{
|
|
ElementType(0), ElementType(1), ElementType(2), ElementType(3),
|
|
ElementType(4), ElementType(5), ElementType(6)};
|
|
std::initializer_list<ElementType> big{
|
|
ElementType(0), ElementType(1), ElementType(2), ElementType(3),
|
|
ElementType(4), ElementType(5), ElementType(6), ElementType(7),
|
|
ElementType(8), ElementType(9), ElementType(10), ElementType(11),
|
|
ElementType(12), ElementType(13)};
|
|
EXPECT_EQ(21, ElementType::GetCounter(kExplicitConstructor));
|
|
EXPECT_EQ(21, ElementType::GetCounter(kAll));
|
|
ElementType::ResetCounters();
|
|
|
|
// Constructor from initializer list, small.
|
|
{
|
|
SmallVector<ElementType, 10> v{small};
|
|
EXPECT_EQ(7UL, v.size());
|
|
EXPECT_EQ(10UL, v.capacity());
|
|
EXPECT_FALSE(v.empty());
|
|
EXPECT_EQ(5, v[5].value());
|
|
}
|
|
EXPECT_EQ(7, ElementType::GetCounter(kCopyConstructor));
|
|
EXPECT_EQ(7, ElementType::GetCounter(kDestructor));
|
|
EXPECT_EQ(14, ElementType::GetCounter(kAll));
|
|
ElementType::ResetCounters();
|
|
|
|
// Constructor from initializer list, big.
|
|
{
|
|
SmallVector<ElementType, 10> v{big};
|
|
EXPECT_EQ(14UL, v.size());
|
|
EXPECT_LE(14UL, v.capacity());
|
|
EXPECT_FALSE(v.empty());
|
|
EXPECT_EQ(3, v[3].value());
|
|
EXPECT_EQ(11, v[11].value());
|
|
}
|
|
EXPECT_EQ(14, ElementType::GetCounter(kCopyConstructor));
|
|
EXPECT_EQ(14, ElementType::GetCounter(kDestructor));
|
|
EXPECT_EQ(28, ElementType::GetCounter(kAll));
|
|
ElementType::ResetCounters();
|
|
}
|
|
|
|
TEST(SmallVectorTest, ConstructFromVectorNonTrivial) {
|
|
using ElementType = NonTrivial<int>;
|
|
auto arr = make_non_trivial_array<14>();
|
|
EXPECT_EQ(14, ElementType::GetCounter(kExplicitConstructor));
|
|
EXPECT_EQ(14, ElementType::GetCounter(kAll));
|
|
ElementType::ResetCounters();
|
|
|
|
// Constructor from base::Vector, small.
|
|
{
|
|
SmallVector<ElementType, 10> v{base::VectorOf(arr.data(), 7)};
|
|
EXPECT_EQ(7UL, v.size());
|
|
EXPECT_EQ(10UL, v.capacity());
|
|
EXPECT_FALSE(v.empty());
|
|
EXPECT_EQ(5, v[5].value());
|
|
}
|
|
EXPECT_EQ(7, ElementType::GetCounter(kCopyConstructor));
|
|
EXPECT_EQ(7, ElementType::GetCounter(kDestructor));
|
|
EXPECT_EQ(14, ElementType::GetCounter(kAll));
|
|
ElementType::ResetCounters();
|
|
|
|
// Constructor from base::Vector, big.
|
|
{
|
|
SmallVector<ElementType, 10> v{base::VectorOf(arr.data(), 14)};
|
|
EXPECT_EQ(14UL, v.size());
|
|
EXPECT_LE(14UL, v.capacity());
|
|
EXPECT_FALSE(v.empty());
|
|
EXPECT_EQ(3, v[3].value());
|
|
EXPECT_EQ(11, v[11].value());
|
|
}
|
|
EXPECT_EQ(14, ElementType::GetCounter(kCopyConstructor));
|
|
EXPECT_EQ(14, ElementType::GetCounter(kDestructor));
|
|
EXPECT_EQ(28, ElementType::GetCounter(kAll));
|
|
ElementType::ResetCounters();
|
|
}
|
|
|
|
TEST(SmallVectorTest, CopyConstructNonTrivial) {
|
|
using ElementType = NonTrivial<int>;
|
|
auto arr = make_non_trivial_array<14>();
|
|
EXPECT_EQ(14, ElementType::GetCounter(kExplicitConstructor));
|
|
EXPECT_EQ(14, ElementType::GetCounter(kAll));
|
|
ElementType::ResetCounters();
|
|
|
|
// Copy constructor, small.
|
|
{
|
|
SmallVector<ElementType, 10> v1{base::VectorOf(arr.data(), 7)};
|
|
EXPECT_EQ(7, ElementType::GetCounter(kCopyConstructor));
|
|
EXPECT_EQ(7, ElementType::GetCounter(kAll));
|
|
ElementType::ResetCounters();
|
|
|
|
SmallVector<ElementType, 10> v2 = v1;
|
|
EXPECT_EQ(7UL, v1.size());
|
|
EXPECT_EQ(10UL, v1.capacity());
|
|
EXPECT_FALSE(v1.empty());
|
|
EXPECT_EQ(5, v1[5].value());
|
|
EXPECT_EQ(7UL, v2.size());
|
|
EXPECT_EQ(10UL, v2.capacity());
|
|
EXPECT_FALSE(v2.empty());
|
|
EXPECT_EQ(5, v2[5].value());
|
|
}
|
|
EXPECT_EQ(7, ElementType::GetCounter(kCopyConstructor));
|
|
EXPECT_EQ(14, ElementType::GetCounter(kDestructor));
|
|
EXPECT_EQ(21, ElementType::GetCounter(kAll));
|
|
ElementType::ResetCounters();
|
|
|
|
// Copy constructor, big.
|
|
{
|
|
SmallVector<ElementType, 10> v1{{base::VectorOf(arr.data(), 14)}};
|
|
EXPECT_EQ(14, ElementType::GetCounter(kCopyConstructor));
|
|
EXPECT_EQ(14, ElementType::GetCounter(kAll));
|
|
ElementType::ResetCounters();
|
|
|
|
SmallVector<ElementType, 10> v2 = v1;
|
|
EXPECT_EQ(14UL, v1.size());
|
|
EXPECT_LE(14UL, v1.capacity());
|
|
EXPECT_FALSE(v1.empty());
|
|
EXPECT_EQ(3, v1[3].value());
|
|
EXPECT_EQ(11, v1[11].value());
|
|
EXPECT_EQ(14UL, v2.size());
|
|
EXPECT_LE(14UL, v2.capacity());
|
|
EXPECT_FALSE(v2.empty());
|
|
EXPECT_EQ(3, v2[3].value());
|
|
EXPECT_EQ(11, v2[11].value());
|
|
}
|
|
EXPECT_EQ(14, ElementType::GetCounter(kCopyConstructor));
|
|
EXPECT_EQ(28, ElementType::GetCounter(kDestructor));
|
|
EXPECT_EQ(42, ElementType::GetCounter(kAll));
|
|
ElementType::ResetCounters();
|
|
}
|
|
|
|
TEST(SmallVectorTest, MoveConstructNonTrivial) {
|
|
using ElementType = NonTrivial<int>;
|
|
auto arr = make_non_trivial_array<14>();
|
|
EXPECT_EQ(14, ElementType::GetCounter(kExplicitConstructor));
|
|
EXPECT_EQ(14, ElementType::GetCounter(kAll));
|
|
ElementType::ResetCounters();
|
|
|
|
// Move constructor, small.
|
|
{
|
|
SmallVector<ElementType, 10> v1{base::VectorOf(arr.data(), 7)};
|
|
EXPECT_EQ(7, ElementType::GetCounter(kCopyConstructor));
|
|
EXPECT_EQ(7, ElementType::GetCounter(kAll));
|
|
ElementType::ResetCounters();
|
|
|
|
SmallVector<ElementType, 10> v2 = std::move(v1);
|
|
EXPECT_EQ(0UL, v1.size());
|
|
EXPECT_EQ(10UL, v1.capacity());
|
|
EXPECT_TRUE(v1.empty());
|
|
EXPECT_EQ(7UL, v2.size());
|
|
EXPECT_EQ(10UL, v2.capacity());
|
|
EXPECT_FALSE(v2.empty());
|
|
EXPECT_EQ(5, v2[5].value());
|
|
}
|
|
EXPECT_EQ(7, ElementType::GetCounter(kMoveConstructor));
|
|
EXPECT_EQ(14, ElementType::GetCounter(kDestructor));
|
|
EXPECT_EQ(21, ElementType::GetCounter(kAll));
|
|
ElementType::ResetCounters();
|
|
|
|
// Move constructor, big.
|
|
{
|
|
SmallVector<ElementType, 10> v1{{base::VectorOf(arr.data(), 14)}};
|
|
EXPECT_EQ(14, ElementType::GetCounter(kCopyConstructor));
|
|
EXPECT_EQ(14, ElementType::GetCounter(kAll));
|
|
ElementType::ResetCounters();
|
|
|
|
SmallVector<ElementType, 10> v2 = std::move(v1);
|
|
EXPECT_EQ(0UL, v1.size());
|
|
EXPECT_EQ(10UL, v1.capacity());
|
|
EXPECT_TRUE(v1.empty());
|
|
EXPECT_EQ(14UL, v2.size());
|
|
EXPECT_LE(14UL, v2.capacity());
|
|
EXPECT_FALSE(v2.empty());
|
|
EXPECT_EQ(3, v2[3].value());
|
|
EXPECT_EQ(11, v2[11].value());
|
|
}
|
|
EXPECT_EQ(0, ElementType::GetCounter(kMoveConstructor));
|
|
EXPECT_EQ(14, ElementType::GetCounter(kDestructor));
|
|
EXPECT_EQ(14, ElementType::GetCounter(kAll));
|
|
ElementType::ResetCounters();
|
|
}
|
|
|
|
namespace {
|
|
template <size_t capacity, size_t src_size, size_t trg_size>
|
|
void TestAssignNonTrivial() {
|
|
constexpr int src_isize = static_cast<int>(src_size);
|
|
constexpr int trg_isize = static_cast<int>(trg_size);
|
|
using ElementType = NonTrivial<int>;
|
|
auto arr_src = make_non_trivial_array<src_size>();
|
|
auto arr_trg = make_non_trivial_array<trg_size, 1000>();
|
|
constexpr bool src_big = src_size > capacity;
|
|
|
|
SmallVector<ElementType, capacity> src{base::VectorOf(arr_src)};
|
|
SmallVector<ElementType, capacity> trg{base::VectorOf(arr_trg)};
|
|
ElementType::ResetCounters();
|
|
{
|
|
trg = src;
|
|
EXPECT_EQ(src_size, src.size());
|
|
EXPECT_LE(capacity, src.capacity());
|
|
EXPECT_TRUE((src_size == 0) == src.empty());
|
|
EXPECT_EQ(src_size, trg.size());
|
|
EXPECT_LE(src_size, trg.capacity());
|
|
EXPECT_LE(capacity, trg.capacity());
|
|
EXPECT_TRUE((src_isize == 0) == trg.empty());
|
|
for (int i = 0; i < src_isize; ++i) {
|
|
EXPECT_EQ(i, src[i].value());
|
|
EXPECT_EQ(i, trg[i].value());
|
|
}
|
|
}
|
|
EXPECT_EQ(src_isize, ElementType::GetCounter(kCopyConstructor) +
|
|
ElementType::GetCounter(kCopyAssignment));
|
|
if constexpr (!src_big) {
|
|
EXPECT_EQ(std::min(src_isize, trg_isize),
|
|
ElementType::GetCounter(kCopyAssignment));
|
|
}
|
|
EXPECT_EQ(trg_isize, ElementType::GetCounter(kDestructor) +
|
|
ElementType::GetCounter(kCopyAssignment));
|
|
EXPECT_EQ(ElementType::GetCounter(kAll),
|
|
ElementType::GetCounter(kCopyConstructor) +
|
|
ElementType::GetCounter(kDestructor) +
|
|
ElementType::GetCounter(kCopyAssignment));
|
|
ElementType::ResetCounters();
|
|
}
|
|
} // anonymous namespace
|
|
|
|
TEST(SmallVectorTest, AssignNonTrivial) {
|
|
// Small vectors.
|
|
TestAssignNonTrivial<10, 7, 7>();
|
|
TestAssignNonTrivial<10, 5, 7>();
|
|
TestAssignNonTrivial<10, 9, 7>();
|
|
TestAssignNonTrivial<0, 0, 0>();
|
|
// Big vectors.
|
|
TestAssignNonTrivial<10, 17, 17>();
|
|
TestAssignNonTrivial<10, 15, 17>();
|
|
TestAssignNonTrivial<10, 19, 17>();
|
|
TestAssignNonTrivial<0, 7, 7>();
|
|
TestAssignNonTrivial<0, 7, 5>();
|
|
TestAssignNonTrivial<0, 5, 7>();
|
|
// Small assigned to big.
|
|
TestAssignNonTrivial<10, 17, 7>();
|
|
TestAssignNonTrivial<0, 17, 0>();
|
|
// Big assigned to small.
|
|
TestAssignNonTrivial<10, 7, 17>();
|
|
TestAssignNonTrivial<0, 0, 17>();
|
|
}
|
|
|
|
namespace {
|
|
template <size_t capacity, size_t src_size, size_t trg_size>
|
|
void TestMoveAssignNonTrivial() {
|
|
constexpr int src_isize = static_cast<int>(src_size);
|
|
constexpr int trg_isize = static_cast<int>(trg_size);
|
|
using ElementType = NonTrivial<int>;
|
|
auto arr_src = make_non_trivial_array<src_size>();
|
|
auto arr_trg = make_non_trivial_array<trg_size, 1000>();
|
|
constexpr bool src_big = src_size > capacity;
|
|
|
|
SmallVector<ElementType, capacity> src{base::VectorOf(arr_src)};
|
|
SmallVector<ElementType, capacity> trg{base::VectorOf(arr_trg)};
|
|
ElementType::ResetCounters();
|
|
{
|
|
trg = std::move(src);
|
|
EXPECT_EQ(0UL, src.size());
|
|
EXPECT_EQ(capacity, src.capacity());
|
|
EXPECT_TRUE(src.empty());
|
|
EXPECT_EQ(src_size, trg.size());
|
|
EXPECT_LE(src_size, trg.capacity());
|
|
EXPECT_LE(capacity, trg.capacity());
|
|
EXPECT_TRUE((src_size == 0) == trg.empty());
|
|
for (int i = 0; i < src_isize; ++i) {
|
|
EXPECT_EQ(i, trg[i].value());
|
|
}
|
|
}
|
|
|
|
if constexpr (!src_big) {
|
|
EXPECT_EQ(src_isize, ElementType::GetCounter(kMoveConstructor) +
|
|
ElementType::GetCounter(kMoveAssignment));
|
|
EXPECT_EQ(std::min(src_isize, trg_isize),
|
|
ElementType::GetCounter(kMoveAssignment));
|
|
EXPECT_EQ(std::max(src_isize, trg_isize),
|
|
ElementType::GetCounter(kDestructor));
|
|
} else {
|
|
EXPECT_EQ(0, ElementType::GetCounter(kMoveConstructor) +
|
|
ElementType::GetCounter(kMoveAssignment));
|
|
EXPECT_EQ(trg_isize, ElementType::GetCounter(kDestructor));
|
|
}
|
|
EXPECT_EQ(ElementType::GetCounter(kAll),
|
|
ElementType::GetCounter(kMoveConstructor) +
|
|
ElementType::GetCounter(kDestructor) +
|
|
ElementType::GetCounter(kMoveAssignment));
|
|
ElementType::ResetCounters();
|
|
}
|
|
} // anonymous namespace
|
|
|
|
TEST(SmallVectorTest, MoveAssignNonTrivial) {
|
|
// Small vectors.
|
|
TestMoveAssignNonTrivial<10, 7, 7>();
|
|
TestMoveAssignNonTrivial<10, 5, 7>();
|
|
TestMoveAssignNonTrivial<10, 9, 7>();
|
|
TestMoveAssignNonTrivial<0, 0, 0>();
|
|
// Big vectors.
|
|
TestMoveAssignNonTrivial<10, 17, 17>();
|
|
TestMoveAssignNonTrivial<10, 15, 17>();
|
|
TestMoveAssignNonTrivial<10, 19, 17>();
|
|
TestMoveAssignNonTrivial<0, 7, 7>();
|
|
TestMoveAssignNonTrivial<0, 7, 5>();
|
|
TestMoveAssignNonTrivial<0, 5, 7>();
|
|
// Small assigned to big.
|
|
TestMoveAssignNonTrivial<10, 17, 7>();
|
|
TestMoveAssignNonTrivial<0, 17, 0>();
|
|
// Big assigned to small.
|
|
TestMoveAssignNonTrivial<10, 7, 17>();
|
|
TestMoveAssignNonTrivial<0, 0, 17>();
|
|
}
|
|
|
|
namespace {
|
|
template <size_t capacity, size_t size>
|
|
void TestIteratorsNonTrivial() {
|
|
constexpr int isize = static_cast<int>(size);
|
|
using ElementType = NonTrivial<int>;
|
|
auto arr = make_non_trivial_array<size, 1>();
|
|
SmallVector<ElementType, capacity> v{base::VectorOf(arr)};
|
|
ElementType::ResetCounters();
|
|
|
|
// Forward.
|
|
{
|
|
auto it = v.begin();
|
|
for (int i = 0; i < isize; ++i) {
|
|
if (i == 0) EXPECT_EQ(*it, v.front());
|
|
if (i == isize - 1) EXPECT_EQ(*it, v.back());
|
|
EXPECT_EQ(*it, v[i]);
|
|
EXPECT_EQ(*it, v.at(i));
|
|
EXPECT_EQ(it->value(), i + 1);
|
|
++it;
|
|
}
|
|
EXPECT_EQ(it, v.end());
|
|
for (int i = isize - 1; i >= 0; --i) {
|
|
--it;
|
|
if (i == 0) EXPECT_EQ(*it, v.front());
|
|
if (i == isize - 1) EXPECT_EQ(*it, v.back());
|
|
EXPECT_EQ(*it, v[i]);
|
|
EXPECT_EQ(*it, v.at(i));
|
|
EXPECT_EQ(it->value(), i + 1);
|
|
}
|
|
EXPECT_EQ(it, v.begin());
|
|
}
|
|
EXPECT_EQ(0, ElementType::GetCounter(kAll));
|
|
|
|
// Reverse.
|
|
{
|
|
auto rit = v.rbegin();
|
|
for (int i = isize - 1; i >= 0; --i) {
|
|
if (i == 0) EXPECT_EQ(*rit, v.front());
|
|
if (i == isize - 1) EXPECT_EQ(*rit, v.back());
|
|
EXPECT_EQ(*rit, v[i]);
|
|
EXPECT_EQ(*rit, v.at(i));
|
|
EXPECT_EQ(rit->value(), i + 1);
|
|
++rit;
|
|
}
|
|
EXPECT_EQ(rit, v.rend());
|
|
for (int i = 0; i < isize; ++i) {
|
|
--rit;
|
|
if (i == 0) EXPECT_EQ(*rit, v.front());
|
|
if (i == isize - 1) EXPECT_EQ(*rit, v.back());
|
|
EXPECT_EQ(*rit, v[i]);
|
|
EXPECT_EQ(*rit, v.at(i));
|
|
EXPECT_EQ(rit->value(), i + 1);
|
|
}
|
|
EXPECT_EQ(rit, v.rbegin());
|
|
}
|
|
EXPECT_EQ(0, ElementType::GetCounter(kAll));
|
|
|
|
// For loops.
|
|
{
|
|
int s = 0;
|
|
for (ElementType x : v) s += x.value();
|
|
EXPECT_EQ(isize * (isize + 1) / 2, s);
|
|
}
|
|
EXPECT_EQ(isize, ElementType::GetCounter(kCopyConstructor));
|
|
EXPECT_EQ(isize, ElementType::GetCounter(kDestructor));
|
|
EXPECT_EQ(2 * isize, ElementType::GetCounter(kAll));
|
|
ElementType::ResetCounters();
|
|
{
|
|
int s = 0;
|
|
for (const ElementType& x : v) s += x.value();
|
|
EXPECT_EQ(isize * (isize + 1) / 2, s);
|
|
}
|
|
EXPECT_EQ(0, ElementType::GetCounter(kAll));
|
|
{
|
|
for (ElementType& x : v) x = ElementType(x.value() + 1000);
|
|
for (int i = 0; i < isize; ++i) EXPECT_EQ(i + 1001, v[i].value());
|
|
}
|
|
EXPECT_EQ(isize, ElementType::GetCounter(kExplicitConstructor));
|
|
EXPECT_EQ(isize, ElementType::GetCounter(kMoveAssignment));
|
|
EXPECT_EQ(isize, ElementType::GetCounter(kDestructor));
|
|
EXPECT_EQ(3 * isize, ElementType::GetCounter(kAll));
|
|
}
|
|
} // anonymous namespace
|
|
|
|
TEST(SmallVectorTest, IteratorsNonTrivial) {
|
|
TestIteratorsNonTrivial<10, 2>();
|
|
TestIteratorsNonTrivial<10, 7>();
|
|
TestIteratorsNonTrivial<10, 17>();
|
|
TestIteratorsNonTrivial<0, 7>();
|
|
}
|
|
|
|
namespace {
|
|
template <size_t capacity, size_t size>
|
|
void TestAccessorsNonTrivial() {
|
|
constexpr int isize = static_cast<int>(size);
|
|
static_assert(size >= 2);
|
|
using ElementType = NonTrivial<int>;
|
|
auto arr = make_non_trivial_array<size, 1>();
|
|
SmallVector<ElementType, capacity> v{base::VectorOf(arr)};
|
|
ElementType::ResetCounters();
|
|
|
|
// Front.
|
|
{
|
|
EXPECT_EQ(v[0], v.front());
|
|
EXPECT_EQ(1, v.front().value());
|
|
v.front() = ElementType(v.front().value() + 1000);
|
|
EXPECT_EQ(v[0], v.front());
|
|
EXPECT_EQ(1001, v.front().value());
|
|
v.front() = ElementType(v.front().value() - 1000);
|
|
EXPECT_EQ(v[0], v.front());
|
|
EXPECT_EQ(1, v.front().value());
|
|
}
|
|
EXPECT_EQ(2, ElementType::GetCounter(kExplicitConstructor));
|
|
EXPECT_EQ(2, ElementType::GetCounter(kMoveAssignment));
|
|
EXPECT_EQ(2, ElementType::GetCounter(kDestructor));
|
|
EXPECT_EQ(6, ElementType::GetCounter(kAll));
|
|
ElementType::ResetCounters();
|
|
|
|
// Back.
|
|
{
|
|
EXPECT_EQ(v[size - 1], v.back());
|
|
EXPECT_EQ(isize, v.back().value());
|
|
v.back() = ElementType(v.back().value() + 1000);
|
|
EXPECT_EQ(v[size - 1], v.back());
|
|
EXPECT_EQ(1000 + isize, v.back().value());
|
|
v.back() = ElementType(v.back().value() - 1000);
|
|
EXPECT_EQ(v[size - 1], v.back());
|
|
EXPECT_EQ(isize, v.back().value());
|
|
}
|
|
EXPECT_EQ(2, ElementType::GetCounter(kExplicitConstructor));
|
|
EXPECT_EQ(2, ElementType::GetCounter(kMoveAssignment));
|
|
EXPECT_EQ(2, ElementType::GetCounter(kDestructor));
|
|
EXPECT_EQ(6, ElementType::GetCounter(kAll));
|
|
ElementType::ResetCounters();
|
|
|
|
// At, operator[].
|
|
{
|
|
for (int i = 0; i < isize; ++i) {
|
|
EXPECT_EQ(v[i], v.at(i));
|
|
EXPECT_EQ(i + 1, v.at(i).value());
|
|
v.at(i) = ElementType(v.at(i).value() + 1000);
|
|
EXPECT_EQ(v[i], v.at(i));
|
|
EXPECT_EQ(i + 1001, v.at(i).value());
|
|
v.at(i) = ElementType(v.at(i).value() - 1000);
|
|
EXPECT_EQ(v[i], v.at(i));
|
|
EXPECT_EQ(i + 1, v.at(i).value());
|
|
}
|
|
}
|
|
EXPECT_EQ(2 * isize, ElementType::GetCounter(kExplicitConstructor));
|
|
EXPECT_EQ(2 * isize, ElementType::GetCounter(kMoveAssignment));
|
|
EXPECT_EQ(2 * isize, ElementType::GetCounter(kDestructor));
|
|
EXPECT_EQ(6 * isize, ElementType::GetCounter(kAll));
|
|
ElementType::ResetCounters();
|
|
}
|
|
} // anonymous namespace
|
|
|
|
TEST(SmallVectorTest, AccessorsNonTrivial) {
|
|
TestAccessorsNonTrivial<10, 2>();
|
|
TestAccessorsNonTrivial<10, 7>();
|
|
TestAccessorsNonTrivial<10, 17>();
|
|
TestAccessorsNonTrivial<0, 7>();
|
|
}
|
|
|
|
namespace {
|
|
template <size_t capacity, size_t size, size_t added>
|
|
void TestPushPopNonTrivial() {
|
|
constexpr int isize = static_cast<int>(size);
|
|
constexpr int iadded = static_cast<int>(added);
|
|
static_assert(added >= 2);
|
|
using ElementType = NonTrivial<int>;
|
|
auto arr = make_non_trivial_array<size, 1>();
|
|
SmallVector<ElementType, capacity> v{base::VectorOf(arr)};
|
|
ElementType::ResetCounters();
|
|
|
|
// Push a few elements.
|
|
for (int i = 0; i < iadded; ++i) {
|
|
v.push_back(ElementType(1000 + i));
|
|
EXPECT_EQ(size + i + 1, v.size());
|
|
EXPECT_LE(size + i + 1, v.capacity());
|
|
EXPECT_EQ(1000 + i, v[size + i].value());
|
|
}
|
|
EXPECT_EQ(iadded, ElementType::GetCounter(kExplicitConstructor));
|
|
if constexpr (size + added <= capacity) {
|
|
EXPECT_EQ(iadded, ElementType::GetCounter(kMoveConstructor));
|
|
EXPECT_EQ(iadded, ElementType::GetCounter(kDestructor));
|
|
EXPECT_EQ(3 * iadded, ElementType::GetCounter(kAll));
|
|
} else {
|
|
EXPECT_LE(iadded, ElementType::GetCounter(kMoveConstructor));
|
|
EXPECT_LE(iadded, ElementType::GetCounter(kDestructor));
|
|
}
|
|
ElementType::ResetCounters();
|
|
|
|
// Pop one element.
|
|
{
|
|
EXPECT_EQ(1000 + iadded - 1, v.back().value());
|
|
v.pop_back();
|
|
EXPECT_EQ(size + added - 1, v.size());
|
|
EXPECT_LE(size + added - 1, v.capacity());
|
|
EXPECT_EQ(1000 + iadded - 2, v.back().value());
|
|
}
|
|
|
|
// Pop the remaining elements that were added.
|
|
{
|
|
v.pop_back(added - 1);
|
|
EXPECT_EQ(size, v.size());
|
|
EXPECT_LE(size, v.capacity());
|
|
if constexpr (size > 0) EXPECT_EQ(isize, v.back().value());
|
|
}
|
|
EXPECT_EQ(iadded, ElementType::GetCounter(kDestructor));
|
|
EXPECT_EQ(iadded, ElementType::GetCounter(kAll));
|
|
ElementType::ResetCounters();
|
|
|
|
// Pop all elements.
|
|
{
|
|
v.pop_back(size);
|
|
EXPECT_EQ(0UL, v.size());
|
|
EXPECT_LE(size, v.capacity());
|
|
EXPECT_TRUE(v.empty());
|
|
EXPECT_EQ(v.begin(), v.end());
|
|
EXPECT_EQ(v.rbegin(), v.rend());
|
|
}
|
|
EXPECT_EQ(isize, ElementType::GetCounter(kDestructor));
|
|
EXPECT_EQ(isize, ElementType::GetCounter(kAll));
|
|
ElementType::ResetCounters();
|
|
}
|
|
} // anonymous namespace
|
|
|
|
TEST(SmallVectorTest, PushPopNonTrivial) {
|
|
TestPushPopNonTrivial<10, 7, 2>();
|
|
TestPushPopNonTrivial<10, 7, 3>();
|
|
TestPushPopNonTrivial<10, 7, 5>();
|
|
TestPushPopNonTrivial<10, 10, 2>();
|
|
TestPushPopNonTrivial<10, 17, 2>();
|
|
TestPushPopNonTrivial<0, 0, 7>();
|
|
TestPushPopNonTrivial<0, 0, 17>();
|
|
}
|
|
|
|
namespace {
|
|
template <size_t capacity, size_t size, size_t added>
|
|
void TestEmplacePopNonTrivial() {
|
|
constexpr int isize = static_cast<int>(size);
|
|
constexpr int iadded = static_cast<int>(added);
|
|
static_assert(added >= 2);
|
|
using ElementType = NonTrivial<int>;
|
|
auto arr = make_non_trivial_array<size, 1>();
|
|
SmallVector<ElementType, capacity> v{base::VectorOf(arr)};
|
|
ElementType::ResetCounters();
|
|
|
|
// Push a few elements.
|
|
for (int i = 0; i < iadded; ++i) {
|
|
v.emplace_back(1000 + i);
|
|
EXPECT_EQ(size + i + 1, v.size());
|
|
EXPECT_LE(size + i + 1, v.capacity());
|
|
EXPECT_EQ(1000 + i, v[size + i].value());
|
|
}
|
|
EXPECT_EQ(iadded, ElementType::GetCounter(kExplicitConstructor));
|
|
if constexpr (size + added <= capacity) {
|
|
EXPECT_EQ(iadded, ElementType::GetCounter(kAll));
|
|
}
|
|
ElementType::ResetCounters();
|
|
|
|
// Pop one element.
|
|
{
|
|
EXPECT_EQ(1000 + iadded - 1, v.back().value());
|
|
v.pop_back();
|
|
EXPECT_EQ(size + added - 1, v.size());
|
|
EXPECT_LE(size + added - 1, v.capacity());
|
|
EXPECT_EQ(1000 + iadded - 2, v.back().value());
|
|
}
|
|
|
|
// Pop the remaining elements that were added.
|
|
{
|
|
v.pop_back(added - 1);
|
|
EXPECT_EQ(size, v.size());
|
|
EXPECT_LE(size, v.capacity());
|
|
if constexpr (size > 0) EXPECT_EQ(isize, v.back().value());
|
|
}
|
|
EXPECT_EQ(iadded, ElementType::GetCounter(kDestructor));
|
|
EXPECT_EQ(iadded, ElementType::GetCounter(kAll));
|
|
ElementType::ResetCounters();
|
|
|
|
// Pop all elements.
|
|
{
|
|
v.pop_back(size);
|
|
EXPECT_EQ(0UL, v.size());
|
|
EXPECT_LE(size, v.capacity());
|
|
EXPECT_TRUE(v.empty());
|
|
EXPECT_EQ(v.begin(), v.end());
|
|
EXPECT_EQ(v.rbegin(), v.rend());
|
|
}
|
|
EXPECT_EQ(isize, ElementType::GetCounter(kDestructor));
|
|
EXPECT_EQ(isize, ElementType::GetCounter(kAll));
|
|
ElementType::ResetCounters();
|
|
}
|
|
} // anonymous namespace
|
|
|
|
TEST(SmallVectorTest, EmplacePopNonTrivial) {
|
|
TestEmplacePopNonTrivial<10, 7, 2>();
|
|
TestEmplacePopNonTrivial<10, 7, 3>();
|
|
TestEmplacePopNonTrivial<10, 7, 5>();
|
|
TestEmplacePopNonTrivial<10, 10, 2>();
|
|
TestEmplacePopNonTrivial<10, 17, 2>();
|
|
TestEmplacePopNonTrivial<0, 0, 7>();
|
|
TestEmplacePopNonTrivial<0, 0, 17>();
|
|
}
|
|
|
|
namespace {
|
|
template <size_t capacity, size_t size, size_t pos>
|
|
void TestInsertSimpleNonTrivial() {
|
|
constexpr int isize = static_cast<int>(size);
|
|
constexpr int ipos = static_cast<int>(pos);
|
|
static_assert(pos <= size);
|
|
using ElementType = NonTrivial<int>;
|
|
auto arr = make_non_trivial_array<size, 1>();
|
|
SmallVector<ElementType, capacity> v{base::VectorOf(arr)};
|
|
const size_t real_capacity = v.capacity();
|
|
ElementType::ResetCounters();
|
|
|
|
{
|
|
v.insert(v.begin() + pos, ElementType(1000));
|
|
EXPECT_EQ(size + 1, v.size());
|
|
EXPECT_LE(size + 1, v.capacity());
|
|
for (int i = 0; i < ipos; ++i) EXPECT_EQ(i + 1, v[i].value());
|
|
EXPECT_EQ(1000, v[pos].value());
|
|
for (int i = ipos + 1; i < isize + 1; ++i) EXPECT_EQ(i, v[i].value());
|
|
}
|
|
if (size + 1 <= real_capacity) {
|
|
EXPECT_EQ(1, ElementType::GetCounter(kDefaultConstructor));
|
|
EXPECT_EQ(1, ElementType::GetCounter(kExplicitConstructor));
|
|
EXPECT_EQ(1, ElementType::GetCounter(kCopyAssignment));
|
|
EXPECT_EQ(isize - ipos, ElementType::GetCounter(kMoveAssignment));
|
|
EXPECT_EQ(1, ElementType::GetCounter(kDestructor));
|
|
EXPECT_EQ(isize - ipos + 4, ElementType::GetCounter(kAll));
|
|
} else {
|
|
EXPECT_EQ(1, ElementType::GetCounter(kDefaultConstructor));
|
|
EXPECT_EQ(1, ElementType::GetCounter(kExplicitConstructor));
|
|
EXPECT_EQ(isize, ElementType::GetCounter(kMoveConstructor));
|
|
EXPECT_EQ(1, ElementType::GetCounter(kCopyAssignment));
|
|
EXPECT_EQ(isize - ipos, ElementType::GetCounter(kMoveAssignment));
|
|
EXPECT_EQ(isize + 1, ElementType::GetCounter(kDestructor));
|
|
EXPECT_EQ(3 * isize - ipos + 4, ElementType::GetCounter(kAll));
|
|
}
|
|
ElementType::ResetCounters();
|
|
}
|
|
} // anonymous namespace
|
|
|
|
TEST(SmallVectorTest, InsertSimpleNonTrivial) {
|
|
TestInsertSimpleNonTrivial<10, 7, 0>();
|
|
TestInsertSimpleNonTrivial<10, 7, 4>();
|
|
TestInsertSimpleNonTrivial<10, 7, 7>();
|
|
TestInsertSimpleNonTrivial<10, 10, 0>();
|
|
TestInsertSimpleNonTrivial<10, 10, 4>();
|
|
TestInsertSimpleNonTrivial<10, 10, 7>();
|
|
TestInsertSimpleNonTrivial<10, 17, 0>();
|
|
TestInsertSimpleNonTrivial<10, 17, 13>();
|
|
TestInsertSimpleNonTrivial<10, 17, 17>();
|
|
TestInsertSimpleNonTrivial<0, 0, 0>();
|
|
TestInsertSimpleNonTrivial<0, 7, 0>();
|
|
TestInsertSimpleNonTrivial<0, 7, 4>();
|
|
TestInsertSimpleNonTrivial<0, 7, 7>();
|
|
}
|
|
|
|
namespace {
|
|
template <size_t capacity, size_t size, size_t pos, size_t added>
|
|
void TestInsertMultipleNonTrivial() {
|
|
constexpr int isize = static_cast<int>(size);
|
|
constexpr int ipos = static_cast<int>(pos);
|
|
constexpr int iadded = static_cast<int>(added);
|
|
static_assert(pos <= size);
|
|
using ElementType = NonTrivial<int>;
|
|
auto arr = make_non_trivial_array<size, 1>();
|
|
SmallVector<ElementType, capacity> v{base::VectorOf(arr)};
|
|
const size_t real_capacity = v.capacity();
|
|
ElementType::ResetCounters();
|
|
|
|
{
|
|
v.insert(v.begin() + pos, added, ElementType(1000));
|
|
EXPECT_EQ(size + added, v.size());
|
|
EXPECT_LE(size + added, v.capacity());
|
|
for (int i = 0; i < ipos; ++i) EXPECT_EQ(i + 1, v[i].value());
|
|
for (int i = ipos; i < ipos + iadded; ++i) EXPECT_EQ(1000, v[i].value());
|
|
for (int i = ipos + iadded; i < isize + iadded; ++i)
|
|
EXPECT_EQ(i - iadded + 1, v[i].value());
|
|
}
|
|
if (size + added <= real_capacity) {
|
|
EXPECT_EQ(iadded, ElementType::GetCounter(kDefaultConstructor));
|
|
EXPECT_EQ(1, ElementType::GetCounter(kExplicitConstructor));
|
|
EXPECT_EQ(iadded, ElementType::GetCounter(kCopyAssignment));
|
|
EXPECT_EQ(isize - ipos, ElementType::GetCounter(kMoveAssignment));
|
|
EXPECT_EQ(1, ElementType::GetCounter(kDestructor));
|
|
EXPECT_EQ(isize - ipos + 2 * iadded + 2, ElementType::GetCounter(kAll));
|
|
} else {
|
|
EXPECT_EQ(iadded, ElementType::GetCounter(kDefaultConstructor));
|
|
EXPECT_EQ(1, ElementType::GetCounter(kExplicitConstructor));
|
|
EXPECT_EQ(isize, ElementType::GetCounter(kMoveConstructor));
|
|
EXPECT_EQ(iadded, ElementType::GetCounter(kCopyAssignment));
|
|
EXPECT_EQ(isize - ipos, ElementType::GetCounter(kMoveAssignment));
|
|
EXPECT_EQ(isize + 1, ElementType::GetCounter(kDestructor));
|
|
EXPECT_EQ(3 * isize - ipos + 2 * iadded + 2, ElementType::GetCounter(kAll));
|
|
}
|
|
ElementType::ResetCounters();
|
|
}
|
|
} // anonymous namespace
|
|
|
|
TEST(SmallVectorTest, InsertMultipleNonTrivial) {
|
|
TestInsertMultipleNonTrivial<10, 7, 0, 2>();
|
|
TestInsertMultipleNonTrivial<10, 7, 4, 2>();
|
|
TestInsertMultipleNonTrivial<10, 7, 7, 2>();
|
|
TestInsertMultipleNonTrivial<10, 7, 0, 3>();
|
|
TestInsertMultipleNonTrivial<10, 7, 4, 3>();
|
|
TestInsertMultipleNonTrivial<10, 7, 7, 3>();
|
|
TestInsertMultipleNonTrivial<10, 7, 0, 4>();
|
|
TestInsertMultipleNonTrivial<10, 7, 4, 4>();
|
|
TestInsertMultipleNonTrivial<10, 7, 7, 4>();
|
|
TestInsertMultipleNonTrivial<10, 10, 0, 2>();
|
|
TestInsertMultipleNonTrivial<10, 10, 4, 2>();
|
|
TestInsertMultipleNonTrivial<10, 10, 7, 2>();
|
|
TestInsertMultipleNonTrivial<10, 17, 0, 2>();
|
|
TestInsertMultipleNonTrivial<10, 17, 13, 2>();
|
|
TestInsertMultipleNonTrivial<10, 17, 17, 2>();
|
|
TestInsertMultipleNonTrivial<0, 0, 0, 2>();
|
|
TestInsertMultipleNonTrivial<0, 7, 0, 2>();
|
|
TestInsertMultipleNonTrivial<0, 7, 4, 2>();
|
|
TestInsertMultipleNonTrivial<0, 7, 7, 2>();
|
|
}
|
|
|
|
namespace {
|
|
template <size_t capacity, size_t size, size_t pos, size_t added>
|
|
void TestInsertListNonTrivial() {
|
|
constexpr int isize = static_cast<int>(size);
|
|
constexpr int ipos = static_cast<int>(pos);
|
|
constexpr int iadded = static_cast<int>(added);
|
|
static_assert(pos <= size);
|
|
using ElementType = NonTrivial<int>;
|
|
auto arr = make_non_trivial_array<size, 1>();
|
|
SmallVector<ElementType, capacity> v{base::VectorOf(arr)};
|
|
const size_t real_capacity = v.capacity();
|
|
std::initializer_list<ElementType> v2{ElementType(1000), ElementType(1001)};
|
|
std::initializer_list<ElementType> v3{ElementType(1000), ElementType(1001),
|
|
ElementType(1002)};
|
|
std::initializer_list<ElementType> v4{ElementType(1000), ElementType(1001),
|
|
ElementType(1002), ElementType(1003)};
|
|
ElementType::ResetCounters();
|
|
|
|
{
|
|
switch (added) {
|
|
case 2:
|
|
v.insert(v.begin() + pos, v2);
|
|
break;
|
|
case 3:
|
|
v.insert(v.begin() + pos, v3);
|
|
break;
|
|
case 4:
|
|
v.insert(v.begin() + pos, v4);
|
|
break;
|
|
default:
|
|
UNREACHABLE();
|
|
}
|
|
EXPECT_EQ(size + added, v.size());
|
|
EXPECT_LE(size + added, v.capacity());
|
|
for (int i = 0; i < ipos; ++i) EXPECT_EQ(i + 1, v[i].value());
|
|
for (int i = ipos; i < ipos + iadded; ++i)
|
|
EXPECT_EQ(1000 + i - ipos, v[i].value());
|
|
for (int i = ipos + iadded; i < isize + iadded; ++i)
|
|
EXPECT_EQ(i - iadded + 1, v[i].value());
|
|
}
|
|
if (size + added <= real_capacity) {
|
|
EXPECT_EQ(iadded, ElementType::GetCounter(kDefaultConstructor));
|
|
EXPECT_EQ(iadded, ElementType::GetCounter(kCopyAssignment));
|
|
EXPECT_EQ(isize - ipos, ElementType::GetCounter(kMoveAssignment));
|
|
EXPECT_EQ(isize - ipos + 2 * iadded, ElementType::GetCounter(kAll));
|
|
} else {
|
|
EXPECT_EQ(iadded, ElementType::GetCounter(kDefaultConstructor));
|
|
EXPECT_EQ(isize, ElementType::GetCounter(kMoveConstructor));
|
|
EXPECT_EQ(iadded, ElementType::GetCounter(kCopyAssignment));
|
|
EXPECT_EQ(isize - ipos, ElementType::GetCounter(kMoveAssignment));
|
|
EXPECT_EQ(isize, ElementType::GetCounter(kDestructor));
|
|
EXPECT_EQ(3 * isize - ipos + 2 * iadded, ElementType::GetCounter(kAll));
|
|
}
|
|
ElementType::ResetCounters();
|
|
}
|
|
} // anonymous namespace
|
|
|
|
TEST(SmallVectorTest, InsertListNonTrivial) {
|
|
TestInsertListNonTrivial<10, 7, 0, 2>();
|
|
TestInsertListNonTrivial<10, 7, 4, 2>();
|
|
TestInsertListNonTrivial<10, 7, 7, 2>();
|
|
TestInsertListNonTrivial<10, 7, 0, 3>();
|
|
TestInsertListNonTrivial<10, 7, 4, 3>();
|
|
TestInsertListNonTrivial<10, 7, 7, 3>();
|
|
TestInsertListNonTrivial<10, 7, 0, 4>();
|
|
TestInsertListNonTrivial<10, 7, 4, 4>();
|
|
TestInsertListNonTrivial<10, 7, 7, 4>();
|
|
TestInsertListNonTrivial<10, 10, 0, 2>();
|
|
TestInsertListNonTrivial<10, 10, 4, 2>();
|
|
TestInsertListNonTrivial<10, 10, 7, 2>();
|
|
TestInsertListNonTrivial<10, 17, 0, 2>();
|
|
TestInsertListNonTrivial<10, 17, 13, 2>();
|
|
TestInsertListNonTrivial<10, 17, 17, 2>();
|
|
TestInsertListNonTrivial<0, 0, 0, 2>();
|
|
TestInsertListNonTrivial<0, 7, 0, 2>();
|
|
TestInsertListNonTrivial<0, 7, 4, 2>();
|
|
TestInsertListNonTrivial<0, 7, 7, 2>();
|
|
}
|
|
|
|
namespace {
|
|
template <size_t capacity, size_t size, size_t pos, size_t added>
|
|
void TestInsertIterNonTrivial() {
|
|
constexpr int isize = static_cast<int>(size);
|
|
constexpr int ipos = static_cast<int>(pos);
|
|
constexpr int iadded = static_cast<int>(added);
|
|
static_assert(pos <= size);
|
|
using ElementType = NonTrivial<int>;
|
|
auto arr = make_non_trivial_array<size, 1>();
|
|
SmallVector<ElementType, capacity> v{base::VectorOf(arr)};
|
|
const size_t real_capacity = v.capacity();
|
|
auto append = make_non_trivial_array<added, 1000>();
|
|
ElementType::ResetCounters();
|
|
|
|
{
|
|
v.insert(v.begin() + pos, append.begin(), append.end());
|
|
EXPECT_EQ(size + added, v.size());
|
|
EXPECT_LE(size + added, v.capacity());
|
|
for (int i = 0; i < ipos; ++i) EXPECT_EQ(i + 1, v[i].value());
|
|
for (int i = ipos; i < ipos + iadded; ++i)
|
|
EXPECT_EQ(1000 + i - ipos, v[i].value());
|
|
for (int i = ipos + iadded; i < isize + iadded; ++i)
|
|
EXPECT_EQ(i - iadded + 1, v[i].value());
|
|
}
|
|
if (size + added <= real_capacity) {
|
|
EXPECT_EQ(iadded, ElementType::GetCounter(kDefaultConstructor));
|
|
EXPECT_EQ(iadded, ElementType::GetCounter(kCopyAssignment));
|
|
EXPECT_EQ(isize - ipos, ElementType::GetCounter(kMoveAssignment));
|
|
EXPECT_EQ(isize - ipos + 2 * iadded, ElementType::GetCounter(kAll));
|
|
} else {
|
|
EXPECT_EQ(iadded, ElementType::GetCounter(kDefaultConstructor));
|
|
EXPECT_EQ(isize, ElementType::GetCounter(kMoveConstructor));
|
|
EXPECT_EQ(iadded, ElementType::GetCounter(kCopyAssignment));
|
|
EXPECT_EQ(isize - ipos, ElementType::GetCounter(kMoveAssignment));
|
|
EXPECT_EQ(isize, ElementType::GetCounter(kDestructor));
|
|
EXPECT_EQ(3 * isize - ipos + 2 * iadded, ElementType::GetCounter(kAll));
|
|
}
|
|
ElementType::ResetCounters();
|
|
}
|
|
} // anonymous namespace
|
|
|
|
TEST(SmallVectorTest, InsertIterNonTrivial) {
|
|
TestInsertIterNonTrivial<10, 7, 0, 2>();
|
|
TestInsertIterNonTrivial<10, 7, 4, 2>();
|
|
TestInsertIterNonTrivial<10, 7, 7, 2>();
|
|
TestInsertIterNonTrivial<10, 7, 0, 3>();
|
|
TestInsertIterNonTrivial<10, 7, 4, 3>();
|
|
TestInsertIterNonTrivial<10, 7, 7, 3>();
|
|
TestInsertIterNonTrivial<10, 7, 0, 4>();
|
|
TestInsertIterNonTrivial<10, 7, 4, 4>();
|
|
TestInsertIterNonTrivial<10, 7, 7, 4>();
|
|
TestInsertIterNonTrivial<10, 10, 0, 2>();
|
|
TestInsertIterNonTrivial<10, 10, 4, 2>();
|
|
TestInsertIterNonTrivial<10, 10, 7, 2>();
|
|
TestInsertIterNonTrivial<10, 17, 0, 2>();
|
|
TestInsertIterNonTrivial<10, 17, 13, 2>();
|
|
TestInsertIterNonTrivial<10, 17, 17, 2>();
|
|
TestInsertIterNonTrivial<0, 0, 0, 2>();
|
|
TestInsertIterNonTrivial<0, 7, 0, 2>();
|
|
TestInsertIterNonTrivial<0, 7, 4, 2>();
|
|
TestInsertIterNonTrivial<0, 7, 7, 2>();
|
|
}
|
|
|
|
namespace {
|
|
template <size_t capacity, size_t size, size_t pos>
|
|
void TestEraseNonTrivial() {
|
|
constexpr int isize = static_cast<int>(size);
|
|
constexpr int ipos = static_cast<int>(pos);
|
|
static_assert(pos <= size);
|
|
using ElementType = NonTrivial<int>;
|
|
auto arr = make_non_trivial_array<size, 1>();
|
|
SmallVector<ElementType, capacity> v{base::VectorOf(arr)};
|
|
const size_t real_capacity = v.capacity();
|
|
ElementType::ResetCounters();
|
|
|
|
{
|
|
v.erase(v.begin() + pos);
|
|
EXPECT_EQ(pos, v.size());
|
|
EXPECT_EQ(real_capacity, v.capacity());
|
|
for (int i = 0; i < ipos; ++i) EXPECT_EQ(i + 1, v[i].value());
|
|
}
|
|
EXPECT_EQ(isize - ipos, ElementType::GetCounter(kDestructor));
|
|
EXPECT_EQ(isize - ipos, ElementType::GetCounter(kAll));
|
|
ElementType::ResetCounters();
|
|
}
|
|
} // anonymous namespace
|
|
|
|
TEST(SmallVectorTest, EraseNonTrivial) {
|
|
TestEraseNonTrivial<10, 7, 0>();
|
|
TestEraseNonTrivial<10, 7, 4>();
|
|
TestEraseNonTrivial<10, 7, 7>();
|
|
TestEraseNonTrivial<10, 10, 0>();
|
|
TestEraseNonTrivial<10, 10, 4>();
|
|
TestEraseNonTrivial<10, 10, 7>();
|
|
TestEraseNonTrivial<10, 17, 0>();
|
|
TestEraseNonTrivial<10, 17, 13>();
|
|
TestEraseNonTrivial<10, 17, 17>();
|
|
TestEraseNonTrivial<0, 0, 0>();
|
|
TestEraseNonTrivial<0, 7, 0>();
|
|
TestEraseNonTrivial<0, 7, 4>();
|
|
TestEraseNonTrivial<0, 7, 7>();
|
|
}
|
|
|
|
namespace {
|
|
constexpr int size_diff(int x, int y) { return x > y ? x - y : 0; }
|
|
|
|
template <size_t capacity, size_t size, size_t new_size>
|
|
void TestResizeNonTrivial() {
|
|
constexpr int isize = static_cast<int>(size);
|
|
constexpr int new_isize = static_cast<int>(new_size);
|
|
using ElementType = NonTrivial<int>;
|
|
auto arr = make_non_trivial_array<size, 1>();
|
|
SmallVector<ElementType, capacity> v{base::VectorOf(arr)};
|
|
const size_t real_capacity = v.capacity();
|
|
ElementType::ResetCounters();
|
|
|
|
{
|
|
v.resize(new_size);
|
|
EXPECT_EQ(new_size, v.size());
|
|
if (new_size <= real_capacity) {
|
|
EXPECT_EQ(real_capacity, v.capacity());
|
|
} else {
|
|
EXPECT_LE(new_size, v.capacity());
|
|
}
|
|
for (int i = 0; i < std::min(isize, new_isize); ++i)
|
|
EXPECT_EQ(i + 1, v[i].value());
|
|
}
|
|
if (new_size <= real_capacity) {
|
|
EXPECT_EQ(size_diff(new_isize, isize),
|
|
ElementType::GetCounter(kDefaultConstructor));
|
|
EXPECT_EQ(size_diff(isize, new_isize),
|
|
ElementType::GetCounter(kDestructor));
|
|
EXPECT_EQ(ElementType::GetCounter(kDefaultConstructor) +
|
|
ElementType::GetCounter(kDestructor),
|
|
ElementType::GetCounter(kAll));
|
|
} else {
|
|
EXPECT_EQ(size_diff(new_isize, isize),
|
|
ElementType::GetCounter(kDefaultConstructor));
|
|
EXPECT_EQ(isize, ElementType::GetCounter(kMoveConstructor));
|
|
EXPECT_EQ(isize, ElementType::GetCounter(kDestructor));
|
|
EXPECT_EQ(ElementType::GetCounter(kDefaultConstructor) +
|
|
ElementType::GetCounter(kMoveConstructor) +
|
|
ElementType::GetCounter(kDestructor),
|
|
ElementType::GetCounter(kAll));
|
|
}
|
|
ElementType::ResetCounters();
|
|
}
|
|
} // anonymous namespace
|
|
|
|
TEST(SmallVectorTest, ResizeNonTrivial) {
|
|
TestResizeNonTrivial<10, 7, 0>();
|
|
TestResizeNonTrivial<10, 7, 4>();
|
|
TestResizeNonTrivial<10, 7, 7>();
|
|
TestResizeNonTrivial<10, 7, 9>();
|
|
TestResizeNonTrivial<10, 7, 10>();
|
|
TestResizeNonTrivial<10, 7, 12>();
|
|
TestResizeNonTrivial<10, 17, 0>();
|
|
TestResizeNonTrivial<10, 17, 7>();
|
|
TestResizeNonTrivial<10, 17, 17>();
|
|
TestResizeNonTrivial<10, 17, 20>();
|
|
TestResizeNonTrivial<10, 17, 100>();
|
|
TestResizeNonTrivial<0, 0, 0>();
|
|
TestResizeNonTrivial<0, 0, 5>();
|
|
TestResizeNonTrivial<0, 7, 0>();
|
|
TestResizeNonTrivial<0, 7, 4>();
|
|
TestResizeNonTrivial<0, 7, 7>();
|
|
TestResizeNonTrivial<0, 7, 10>();
|
|
TestResizeNonTrivial<0, 7, 100>();
|
|
}
|
|
|
|
namespace {
|
|
template <size_t capacity, size_t size, size_t new_size>
|
|
void TestResizeInitNonTrivial() {
|
|
constexpr int isize = static_cast<int>(size);
|
|
constexpr int new_isize = static_cast<int>(new_size);
|
|
using ElementType = NonTrivial<int>;
|
|
auto arr = make_non_trivial_array<size, 1>();
|
|
SmallVector<ElementType, capacity> v{base::VectorOf(arr)};
|
|
const size_t real_capacity = v.capacity();
|
|
ElementType::ResetCounters();
|
|
|
|
{
|
|
v.resize(new_size, ElementType(42));
|
|
EXPECT_EQ(new_size, v.size());
|
|
if (new_size <= real_capacity) {
|
|
EXPECT_EQ(real_capacity, v.capacity());
|
|
} else {
|
|
EXPECT_LE(new_size, v.capacity());
|
|
}
|
|
for (int i = 0; i < std::min(isize, new_isize); ++i)
|
|
EXPECT_EQ(i + 1, v[i].value());
|
|
for (int i = isize; i < new_isize; ++i) EXPECT_EQ(42, v[i].value());
|
|
}
|
|
if (new_size <= real_capacity) {
|
|
EXPECT_EQ(1, ElementType::GetCounter(kExplicitConstructor));
|
|
EXPECT_EQ(size_diff(new_isize, isize),
|
|
ElementType::GetCounter(kCopyConstructor));
|
|
EXPECT_EQ(size_diff(isize, new_isize) + 1,
|
|
ElementType::GetCounter(kDestructor));
|
|
EXPECT_EQ(ElementType::GetCounter(kExplicitConstructor) +
|
|
ElementType::GetCounter(kCopyConstructor) +
|
|
ElementType::GetCounter(kDestructor),
|
|
ElementType::GetCounter(kAll));
|
|
} else {
|
|
EXPECT_EQ(1, ElementType::GetCounter(kExplicitConstructor));
|
|
EXPECT_EQ(size_diff(new_isize, isize),
|
|
ElementType::GetCounter(kCopyConstructor));
|
|
EXPECT_EQ(isize, ElementType::GetCounter(kMoveConstructor));
|
|
EXPECT_EQ(isize + 1, ElementType::GetCounter(kDestructor));
|
|
EXPECT_EQ(ElementType::GetCounter(kExplicitConstructor) +
|
|
ElementType::GetCounter(kCopyConstructor) +
|
|
ElementType::GetCounter(kMoveConstructor) +
|
|
ElementType::GetCounter(kDestructor),
|
|
ElementType::GetCounter(kAll));
|
|
}
|
|
ElementType::ResetCounters();
|
|
}
|
|
} // anonymous namespace
|
|
|
|
TEST(SmallVectorTest, ResizeInitNonTrivial) {
|
|
TestResizeInitNonTrivial<10, 7, 0>();
|
|
TestResizeInitNonTrivial<10, 7, 4>();
|
|
TestResizeInitNonTrivial<10, 7, 7>();
|
|
TestResizeInitNonTrivial<10, 7, 9>();
|
|
TestResizeInitNonTrivial<10, 7, 10>();
|
|
TestResizeInitNonTrivial<10, 7, 12>();
|
|
TestResizeInitNonTrivial<10, 17, 0>();
|
|
TestResizeInitNonTrivial<10, 17, 7>();
|
|
TestResizeInitNonTrivial<10, 17, 17>();
|
|
TestResizeInitNonTrivial<10, 17, 20>();
|
|
TestResizeInitNonTrivial<10, 17, 100>();
|
|
TestResizeInitNonTrivial<0, 0, 0>();
|
|
TestResizeInitNonTrivial<0, 0, 5>();
|
|
TestResizeInitNonTrivial<0, 7, 0>();
|
|
TestResizeInitNonTrivial<0, 7, 4>();
|
|
TestResizeInitNonTrivial<0, 7, 7>();
|
|
TestResizeInitNonTrivial<0, 7, 10>();
|
|
TestResizeInitNonTrivial<0, 7, 100>();
|
|
}
|
|
|
|
namespace {
|
|
template <size_t capacity, size_t size, size_t new_size>
|
|
void TestReserveNonTrivial() {
|
|
constexpr int isize = static_cast<int>(size);
|
|
using ElementType = NonTrivial<int>;
|
|
auto arr = make_non_trivial_array<size, 1>();
|
|
SmallVector<ElementType, capacity> v{base::VectorOf(arr)};
|
|
const size_t real_capacity = v.capacity();
|
|
ElementType::ResetCounters();
|
|
|
|
{
|
|
v.reserve(new_size);
|
|
EXPECT_EQ(size, v.size());
|
|
if (new_size <= real_capacity) {
|
|
EXPECT_EQ(real_capacity, v.capacity());
|
|
} else {
|
|
EXPECT_LE(new_size, v.capacity());
|
|
}
|
|
for (int i = 0; i < isize; ++i) EXPECT_EQ(i + 1, v[i].value());
|
|
}
|
|
if (new_size <= real_capacity) {
|
|
EXPECT_EQ(0, ElementType::GetCounter(kAll));
|
|
} else {
|
|
EXPECT_EQ(isize, ElementType::GetCounter(kMoveConstructor));
|
|
EXPECT_EQ(isize, ElementType::GetCounter(kDestructor));
|
|
EXPECT_EQ(ElementType::GetCounter(kMoveConstructor) +
|
|
ElementType::GetCounter(kDestructor),
|
|
ElementType::GetCounter(kAll));
|
|
}
|
|
}
|
|
} // anonymous namespace
|
|
|
|
TEST(SmallVectorTest, ReserveNonTrivial) {
|
|
TestReserveNonTrivial<10, 7, 0>();
|
|
TestReserveNonTrivial<10, 7, 4>();
|
|
TestReserveNonTrivial<10, 7, 7>();
|
|
TestReserveNonTrivial<10, 7, 9>();
|
|
TestReserveNonTrivial<10, 7, 10>();
|
|
TestReserveNonTrivial<10, 7, 12>();
|
|
TestReserveNonTrivial<10, 17, 0>();
|
|
TestReserveNonTrivial<10, 17, 7>();
|
|
TestReserveNonTrivial<10, 17, 17>();
|
|
TestReserveNonTrivial<10, 17, 20>();
|
|
TestReserveNonTrivial<10, 17, 100>();
|
|
TestReserveNonTrivial<0, 0, 0>();
|
|
TestReserveNonTrivial<0, 0, 5>();
|
|
TestReserveNonTrivial<0, 7, 0>();
|
|
TestReserveNonTrivial<0, 7, 4>();
|
|
TestReserveNonTrivial<0, 7, 7>();
|
|
TestReserveNonTrivial<0, 7, 10>();
|
|
TestReserveNonTrivial<0, 7, 100>();
|
|
}
|
|
|
|
namespace {
|
|
template <size_t capacity, size_t size>
|
|
void TestClearNonTrivial() {
|
|
constexpr int isize = static_cast<int>(size);
|
|
using ElementType = NonTrivial<int>;
|
|
auto arr = make_non_trivial_array<size, 1>();
|
|
SmallVector<ElementType, capacity> v{base::VectorOf(arr)};
|
|
const size_t real_capacity = v.capacity();
|
|
ElementType::ResetCounters();
|
|
|
|
{
|
|
v.clear();
|
|
EXPECT_EQ(0UL, v.size());
|
|
EXPECT_EQ(real_capacity, v.capacity());
|
|
EXPECT_TRUE(v.empty());
|
|
EXPECT_EQ(v.begin(), v.end());
|
|
EXPECT_EQ(v.rbegin(), v.rend());
|
|
}
|
|
EXPECT_EQ(isize, ElementType::GetCounter(kDestructor));
|
|
EXPECT_EQ(isize, ElementType::GetCounter(kAll));
|
|
ElementType::ResetCounters();
|
|
}
|
|
} // anonymous namespace
|
|
|
|
TEST(SmallVectorTest, ClearNonTrivial) {
|
|
TestClearNonTrivial<10, 7>();
|
|
TestClearNonTrivial<10, 17>();
|
|
TestClearNonTrivial<0, 0>();
|
|
TestClearNonTrivial<0, 7>();
|
|
}
|
|
|
|
namespace {
|
|
template <size_t capacity>
|
|
void copy_assign(SmallVector<NonTrivial<int>, capacity>& trg,
|
|
const SmallVector<NonTrivial<int>, capacity>& src) {
|
|
trg = src;
|
|
}
|
|
|
|
template <size_t capacity>
|
|
void move_assign(SmallVector<NonTrivial<int>, capacity>& trg,
|
|
SmallVector<NonTrivial<int>, capacity>&& src) {
|
|
trg = std::move(src);
|
|
}
|
|
|
|
template <size_t capacity, size_t size>
|
|
void TestNoAssign() {
|
|
constexpr int isize = static_cast<int>(size);
|
|
using ElementType = NonTrivial<int>;
|
|
auto arr = make_non_trivial_array<size, 1>();
|
|
SmallVector<ElementType, capacity> v{base::VectorOf(arr)};
|
|
const size_t real_capacity = v.capacity();
|
|
ElementType::ResetCounters();
|
|
|
|
{
|
|
copy_assign(v, v);
|
|
EXPECT_EQ(size, v.size());
|
|
EXPECT_EQ(real_capacity, v.capacity());
|
|
for (int i = 0; i < isize; ++i) EXPECT_EQ(i + 1, v[i].value());
|
|
}
|
|
EXPECT_EQ(0, ElementType::GetCounter(kAll));
|
|
ElementType::ResetCounters();
|
|
|
|
{
|
|
move_assign(v, std::move(v));
|
|
EXPECT_EQ(size, v.size());
|
|
EXPECT_EQ(real_capacity, v.capacity());
|
|
for (int i = 0; i < isize; ++i) EXPECT_EQ(i + 1, v[i].value());
|
|
}
|
|
EXPECT_EQ(0, ElementType::GetCounter(kAll));
|
|
ElementType::ResetCounters();
|
|
}
|
|
} // anonymous namespace
|
|
|
|
TEST(SmallVectorTest, NoAssign) {
|
|
TestNoAssign<10, 7>();
|
|
TestNoAssign<10, 17>();
|
|
TestNoAssign<0, 0>();
|
|
TestNoAssign<0, 7>();
|
|
}
|
|
|
|
} // namespace v8::base
|