aboutsummaryrefslogtreecommitdiff
path: root/src/base/small_vector_unittest.cc
diff options
context:
space:
mode:
Diffstat (limited to 'src/base/small_vector_unittest.cc')
-rw-r--r--src/base/small_vector_unittest.cc232
1 files changed, 232 insertions, 0 deletions
diff --git a/src/base/small_vector_unittest.cc b/src/base/small_vector_unittest.cc
new file mode 100644
index 000000000..e99d84ae3
--- /dev/null
+++ b/src/base/small_vector_unittest.cc
@@ -0,0 +1,232 @@
+/*
+ * Copyright (C) 2021 The Android Open Source Project
+ *
+ * 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 "perfetto/ext/base/small_vector.h"
+
+#include <tuple>
+#include <utility>
+
+#include "test/gtest_and_gmock.h"
+
+namespace perfetto {
+namespace base {
+namespace {
+
+int g_instances = 0;
+
+struct Obj {
+ explicit Obj(size_t v = 0) : value(v) {
+ EXPECT_FALSE(constructed);
+ constructed = true;
+ g_instances++;
+ }
+
+ ~Obj() {
+ EXPECT_TRUE(constructed);
+ g_instances--;
+ }
+
+ // Move operators.
+ Obj(Obj&& other) noexcept {
+ g_instances++;
+ constructed = true;
+ moved_into = true;
+ value = other.value;
+ other.moved_from = true;
+ other.value = 0xffffffff - value;
+ }
+
+ Obj& operator=(Obj&& other) noexcept {
+ this->~Obj();
+ new (this) Obj(std::move(other));
+ return *this;
+ }
+
+ // Copy operators.
+ Obj(const Obj& other) {
+ other.copied_from = true;
+ g_instances++;
+ constructed = true;
+ copied_into = true;
+ value = other.value;
+ }
+
+ Obj& operator=(const Obj& other) {
+ this->~Obj();
+ new (this) Obj(other);
+ return *this;
+ }
+
+ uintptr_t addr = reinterpret_cast<uintptr_t>(this);
+ bool constructed = false;
+ size_t value = 0;
+ bool moved_from = false;
+ mutable bool copied_from = false;
+ bool moved_into = false;
+ bool copied_into = false;
+};
+
+TEST(SmallVectorTest, StaySmall) {
+ SmallVector<Obj, 8> v;
+ EXPECT_EQ(g_instances, 0);
+ EXPECT_EQ(v.size(), 0u);
+ EXPECT_TRUE(v.empty());
+ EXPECT_EQ(v.begin(), v.end());
+
+ for (size_t i = 1; i <= 8; i++) {
+ v.emplace_back(i);
+ EXPECT_EQ(g_instances, static_cast<int>(i));
+ EXPECT_FALSE(v.empty());
+ EXPECT_EQ(v.end(), v.begin() + i);
+ EXPECT_EQ(v.back().value, i);
+ EXPECT_EQ(v[static_cast<size_t>(i - 1)].value, i);
+ EXPECT_EQ(v[static_cast<size_t>(i - 1)].value, i);
+ }
+
+ for (size_t i = 1; i <= 3; i++) {
+ v.pop_back();
+ EXPECT_EQ(g_instances, 8 - static_cast<int>(i));
+ }
+
+ v.clear();
+ EXPECT_EQ(g_instances, 0);
+}
+
+TEST(SmallVectorTest, GrowOnHeap) {
+ SmallVector<Obj, 4> v;
+ for (size_t i = 0; i < 10; i++) {
+ v.emplace_back(i);
+ EXPECT_EQ(g_instances, static_cast<int>(i + 1));
+ EXPECT_FALSE(v.empty());
+ EXPECT_EQ(v.end(), v.begin() + i + 1);
+ EXPECT_EQ(v[i].value, i);
+ }
+
+ // Do a second pass and check that the initial elements aren't corrupt.
+ for (size_t i = 0; i < 10; i++) {
+ EXPECT_EQ(v[i].value, i);
+ EXPECT_TRUE(v[i].constructed);
+ }
+
+ // The first 4 elements must have been moved into because of the heap growth.
+ for (size_t i = 0; i < 4; i++)
+ EXPECT_TRUE(v[i].moved_into);
+ EXPECT_FALSE(v.back().moved_into);
+}
+
+class SmallVectorTestP : public testing::TestWithParam<size_t> {};
+
+TEST_P(SmallVectorTestP, MoveOperators) {
+ size_t num_elements = GetParam();
+ static constexpr size_t kInlineCapacity = 4;
+ SmallVector<Obj, kInlineCapacity> v1;
+ for (size_t i = 0; i < num_elements; i++)
+ v1.emplace_back(i);
+
+ SmallVector<Obj, kInlineCapacity> v2(std::move(v1));
+ EXPECT_TRUE(v1.empty());
+ EXPECT_EQ(v2.size(), num_elements);
+
+ // Check that v2 (the moved into vector) is consistent.
+ for (size_t i = 0; i < num_elements; i++) {
+ EXPECT_EQ(v2[i].value, i);
+ EXPECT_TRUE(v2[i].constructed);
+ if (num_elements <= kInlineCapacity) {
+ EXPECT_TRUE(v2[i].moved_into);
+ }
+ }
+
+ // Check that v1 (the moved-from object) is still usable.
+ EXPECT_EQ(v1.size(), 0u);
+
+ for (size_t i = 0; i < num_elements; i++) {
+ v1.emplace_back(1000 + i);
+ EXPECT_EQ(v1.size(), i + 1);
+ }
+
+ EXPECT_NE(v1.data(), v2.data());
+
+ for (size_t i = 0; i < num_elements; i++) {
+ EXPECT_EQ(v1[i].value, 1000 + i);
+ EXPECT_EQ(v2[i].value, i);
+ EXPECT_TRUE(v1[i].constructed);
+ EXPECT_FALSE(v1[i].moved_from);
+ }
+
+ // Now swap again using the move-assignment.
+
+ v1 = std::move(v2);
+ EXPECT_EQ(v1.size(), num_elements);
+ EXPECT_TRUE(v2.empty());
+ for (size_t i = 0; i < num_elements; i++) {
+ EXPECT_EQ(v1[i].value, i);
+ EXPECT_TRUE(v1[i].constructed);
+ }
+
+ { auto destroy = std::move(v1); }
+
+ EXPECT_EQ(g_instances, 0);
+}
+
+TEST_P(SmallVectorTestP, CopyOperators) {
+ size_t num_elements = GetParam();
+ static constexpr size_t kInlineCapacity = 4;
+ SmallVector<Obj, kInlineCapacity> v1;
+ for (size_t i = 0; i < num_elements; i++)
+ v1.emplace_back(i);
+
+ SmallVector<Obj, kInlineCapacity> v2(v1);
+ EXPECT_EQ(v1.size(), num_elements);
+ EXPECT_EQ(v2.size(), num_elements);
+ EXPECT_EQ(g_instances, static_cast<int>(num_elements * 2));
+
+ for (size_t i = 0; i < num_elements; i++) {
+ EXPECT_EQ(v1[i].value, i);
+ EXPECT_TRUE(v1[i].copied_from);
+ EXPECT_EQ(v2[i].value, i);
+ EXPECT_TRUE(v2[i].copied_into);
+ }
+
+ // Now edit v2.
+ for (size_t i = 0; i < num_elements; i++)
+ v2[i].value = i + 100;
+ EXPECT_EQ(g_instances, static_cast<int>(num_elements * 2));
+
+ // Append some extra elements.
+ for (size_t i = 0; i < num_elements; i++)
+ v2.emplace_back(i + 200);
+ EXPECT_EQ(g_instances, static_cast<int>(num_elements * 3));
+
+ for (size_t i = 0; i < num_elements * 2; i++) {
+ if (i < num_elements) {
+ EXPECT_EQ(v1[i].value, i);
+ EXPECT_EQ(v2[i].value, 100 + i);
+ } else {
+ EXPECT_EQ(v2[i].value, 200 + i - num_elements);
+ }
+ }
+
+ v2.clear();
+ EXPECT_EQ(g_instances, static_cast<int>(num_elements));
+}
+
+INSTANTIATE_TEST_SUITE_P(SmallVectorTest,
+ SmallVectorTestP,
+ testing::Values(2, 4, 7, 512));
+
+} // namespace
+} // namespace base
+} // namespace perfetto
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-11 22:10:36 +0000