base: add SmallVector
A vector with inline storage. Falls back on the
heap when exceeding it.
Bug: 205302474
Change-Id: Iaa479ad09dfe7e7c22e41e36e52d3ef1cc1c3706
diff --git a/Android.bp b/Android.bp
index e5fd4a3..cc92485 100644
--- a/Android.bp
+++ b/Android.bp
@@ -6901,6 +6901,7 @@
"src/base/paged_memory_unittest.cc",
"src/base/periodic_task_unittest.cc",
"src/base/scoped_file_unittest.cc",
+ "src/base/small_vector_unittest.cc",
"src/base/string_splitter_unittest.cc",
"src/base/string_utils_unittest.cc",
"src/base/string_view_unittest.cc",
diff --git a/BUILD b/BUILD
index 5ce842e..b011148 100644
--- a/BUILD
+++ b/BUILD
@@ -355,6 +355,7 @@
"include/perfetto/ext/base/pipe.h",
"include/perfetto/ext/base/scoped_file.h",
"include/perfetto/ext/base/small_set.h",
+ "include/perfetto/ext/base/small_vector.h",
"include/perfetto/ext/base/string_splitter.h",
"include/perfetto/ext/base/string_utils.h",
"include/perfetto/ext/base/string_view.h",
diff --git a/include/perfetto/ext/base/BUILD.gn b/include/perfetto/ext/base/BUILD.gn
index 34e09de..de97cea 100644
--- a/include/perfetto/ext/base/BUILD.gn
+++ b/include/perfetto/ext/base/BUILD.gn
@@ -37,6 +37,7 @@
"pipe.h",
"scoped_file.h",
"small_set.h",
+ "small_vector.h",
"string_splitter.h",
"string_utils.h",
"string_view.h",
diff --git a/include/perfetto/ext/base/small_vector.h b/include/perfetto/ext/base/small_vector.h
new file mode 100644
index 0000000..15b1773
--- /dev/null
+++ b/include/perfetto/ext/base/small_vector.h
@@ -0,0 +1,188 @@
+/*
+ * 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.
+ */
+
+#ifndef INCLUDE_PERFETTO_EXT_BASE_SMALL_VECTOR_H_
+#define INCLUDE_PERFETTO_EXT_BASE_SMALL_VECTOR_H_
+
+#include <algorithm>
+#include <type_traits>
+#include <utility>
+
+#include "perfetto/base/compiler.h"
+#include "perfetto/base/logging.h"
+#include "perfetto/ext/base/utils.h"
+
+namespace perfetto {
+namespace base {
+
+// Uses inline storage first, switches to dynamic storage when it overflows.
+template <typename T, size_t kSize>
+class SmallVector {
+ public:
+ static constexpr size_t kInlineSize = kSize;
+
+ explicit SmallVector() = default;
+
+ ~SmallVector() {
+ clear();
+ if (PERFETTO_UNLIKELY(is_using_heap()))
+ AlignedFree(begin_);
+ begin_ = end_ = end_of_storage_ = nullptr;
+ }
+
+ // Move operators.
+ SmallVector(SmallVector&& other) noexcept(
+ std::is_nothrow_move_constructible<T>::value) {
+ if (other.is_using_heap()) {
+ // Move the heap content, no need to move the individual objects as their
+ // location won't change.
+ begin_ = other.begin_;
+ end_ = other.end_;
+ end_of_storage_ = other.end_of_storage_;
+ } else {
+ const size_t other_size = other.size();
+ PERFETTO_DCHECK(other_size <= capacity());
+ for (size_t i = 0; i < other_size; i++) {
+ // Move the entries and destroy the ones in the moved-from object.
+ new (&begin_[i]) T(std::move(other.begin_[i]));
+ other.begin_[i].~T();
+ }
+ end_ = begin_ + other_size;
+ }
+ auto* const other_inline_storage = other.inline_storage_begin();
+ other.end_ = other.begin_ = other_inline_storage;
+ other.end_of_storage_ = other_inline_storage + kInlineSize;
+ }
+
+ SmallVector& operator=(SmallVector&& other) noexcept(
+ std::is_nothrow_move_constructible<T>::value) {
+ this->~SmallVector();
+ new (this) SmallVector<T, kSize>(std::move(other));
+ return *this;
+ }
+
+ // Copy operators.
+ SmallVector(const SmallVector& other) {
+ const size_t other_size = other.size();
+ if (other_size > capacity())
+ Grow(other_size);
+ // Copy-construct the elements.
+ for (size_t i = 0; i < other_size; ++i)
+ new (&begin_[i]) T(other.begin_[i]);
+ end_ = begin_ + other_size;
+ }
+
+ SmallVector& operator=(const SmallVector& other) {
+ if (PERFETTO_UNLIKELY(this == &other))
+ return *this;
+ this->~SmallVector();
+ new (this) SmallVector<T, kSize>(other);
+ return *this;
+ }
+
+ T* data() { return begin_; }
+ const T* data() const { return begin_; }
+
+ T* begin() { return begin_; }
+ const T* begin() const { return begin_; }
+
+ T* end() { return end_; }
+ const T* end() const { return end_; }
+
+ size_t size() const { return static_cast<size_t>(end_ - begin_); }
+
+ bool empty() const { return end_ == begin_; }
+
+ size_t capacity() const {
+ return static_cast<size_t>(end_of_storage_ - begin_);
+ }
+
+ T& back() {
+ PERFETTO_DCHECK(!empty());
+ return end_[-1];
+ }
+ const T& back() const {
+ PERFETTO_DCHECK(!empty());
+ return end_[-1];
+ }
+
+ T& operator[](size_t index) {
+ PERFETTO_DCHECK(index < size());
+ return begin_[index];
+ }
+
+ const T& operator[](size_t index) const {
+ PERFETTO_DCHECK(index < size());
+ return begin_[index];
+ }
+
+ template <typename... Args>
+ void emplace_back(Args&&... args) {
+ T* end = end_;
+ if (PERFETTO_UNLIKELY(end == end_of_storage_))
+ end = Grow();
+ new (end) T(std::forward<Args>(args)...);
+ end_ = end + 1;
+ }
+
+ void pop_back() {
+ PERFETTO_DCHECK(!empty());
+ back().~T();
+ --end_;
+ }
+
+ // Clear without reverting back to inline storage.
+ void clear() {
+ while (!empty())
+ pop_back();
+ }
+
+ private:
+ PERFETTO_NO_INLINE T* Grow(size_t desired_capacity = 0) {
+ size_t cur_size = size();
+ size_t new_capacity = desired_capacity;
+ if (desired_capacity <= cur_size)
+ new_capacity = std::max(capacity() * 2, size_t(128));
+ T* new_storage =
+ static_cast<T*>(AlignedAlloc(alignof(T), new_capacity * sizeof(T)));
+ for (size_t i = 0; i < cur_size; ++i) {
+ // Move the elements into the new heap buffer and destroy the old ones.
+ new (&new_storage[i]) T(std::move(begin_[i]));
+ begin_[i].~T();
+ }
+ if (is_using_heap())
+ AlignedFree(begin_);
+ begin_ = new_storage;
+ end_ = new_storage + cur_size;
+ end_of_storage_ = new_storage + new_capacity;
+ return end_;
+ }
+
+ T* inline_storage_begin() { return reinterpret_cast<T*>(&inline_storage_); }
+ bool is_using_heap() { return begin_ != inline_storage_begin(); }
+
+ T* begin_ = inline_storage_begin();
+ T* end_ = begin_;
+ T* end_of_storage_ = begin_ + kInlineSize;
+
+ typename std::aligned_storage<sizeof(T) * kInlineSize, alignof(T)>::type
+ inline_storage_;
+};
+
+} // namespace base
+} // namespace perfetto
+
+#endif // INCLUDE_PERFETTO_EXT_BASE_SMALL_VECTOR_H_
diff --git a/src/base/BUILD.gn b/src/base/BUILD.gn
index f6d86b0..098103c 100644
--- a/src/base/BUILD.gn
+++ b/src/base/BUILD.gn
@@ -170,6 +170,7 @@
"paged_memory_unittest.cc",
"periodic_task_unittest.cc",
"scoped_file_unittest.cc",
+ "small_vector_unittest.cc",
"string_splitter_unittest.cc",
"string_utils_unittest.cc",
"string_view_unittest.cc",
diff --git a/src/base/small_vector_unittest.cc b/src/base/small_vector_unittest.cc
new file mode 100644
index 0000000..e99d84a
--- /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