FTL: Add StaticVector<T, N>
FTL is a template library shared by SurfaceFlinger and InputFlinger.
StaticVector is a hybrid of std::array and std::vector, a statically
allocated container with fixed capacity. It will serve as a base for
SmallVector and SmallMap.
Bug: 160012986
Test: ftl_test
Test: Apply ag/12919186 and compare assembly
Change-Id: I821c736f3411e970402faf19d9238b68c056ca93
diff --git a/include/ftl/StaticVector.h b/include/ftl/StaticVector.h
new file mode 100644
index 0000000..b586e91
--- /dev/null
+++ b/include/ftl/StaticVector.h
@@ -0,0 +1,341 @@
+/*
+ * Copyright 2020 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.
+ */
+
+#pragma once
+
+#include <algorithm>
+#include <cassert>
+#include <iterator>
+#include <memory>
+#include <new>
+#include <type_traits>
+#include <utility>
+
+namespace android::ftl {
+
+// Fixed-capacity, statically allocated counterpart of std::vector. Akin to std::array, StaticVector
+// allocates contiguous storage for N elements of type T at compile time, but stores at most (rather
+// than exactly) N elements. Unlike std::array, its default constructor does not require T to have a
+// default constructor, since elements are constructed in-place as the vector grows. Operations that
+// insert an element, such as push_back and emplace, fail when the vector is full. The API otherwise
+// adheres to standard containers, except the unstable_erase operation that does not shift elements,
+// and the replace operation that destructively emplaces.
+//
+// StaticVector<T, 1> is analogous to an iterable std::optional, but StaticVector<T, 0> is an error.
+//
+// Example usage:
+//
+// ftl::StaticVector<char, 3> vector;
+// assert(vector.empty());
+//
+// vector = {'a', 'b'};
+// assert(vector.size() == 2u);
+//
+// vector.push_back('c');
+// assert(vector.full());
+//
+// assert(!vector.push_back('d'));
+// assert(vector.size() == 3u);
+//
+// vector.unstable_erase(vector.begin());
+// assert(vector == (ftl::StaticVector{'c', 'b'}));
+//
+// vector.pop_back();
+// assert(vector.back() == 'c');
+//
+// const char array[] = "hi";
+// vector = ftl::StaticVector(array);
+// assert(vector == (ftl::StaticVector{'h', 'i', '\0'}));
+//
+template <typename T, size_t N>
+class StaticVector {
+ static_assert(N > 0);
+
+ template <typename I>
+ using IsInputIterator = std::is_base_of<std::input_iterator_tag,
+ typename std::iterator_traits<I>::iterator_category>;
+
+public:
+ using value_type = T;
+ using size_type = size_t;
+ using difference_type = ptrdiff_t;
+
+ using pointer = value_type*;
+ using reference = value_type&;
+ using iterator = pointer;
+ using reverse_iterator = std::reverse_iterator<iterator>;
+
+ using const_pointer = const value_type*;
+ using const_reference = const value_type&;
+ using const_iterator = const_pointer;
+ using const_reverse_iterator = std::reverse_iterator<const_iterator>;
+
+ // Creates an empty vector.
+ StaticVector() = default;
+
+ // Copies and moves a vector, respectively.
+ StaticVector(const StaticVector& other) : StaticVector(other.begin(), other.end()) {}
+ StaticVector(StaticVector&& other) { swap<Empty>(other); }
+
+ // Copies at most N elements from a smaller convertible vector.
+ template <typename U, size_t M, typename = std::enable_if_t<M <= N>>
+ StaticVector(const StaticVector<U, M>& other) : StaticVector(other.begin(), other.end()) {}
+
+ // Copies at most N elements from an array.
+ template <typename U, size_t M>
+ explicit StaticVector(U (&array)[M]) : StaticVector(std::begin(array), std::end(array)) {}
+
+ // Copies at most N elements from the range [first, last).
+ template <typename Iterator, typename = std::enable_if_t<IsInputIterator<Iterator>{}>>
+ StaticVector(Iterator first, Iterator last)
+ : mSize(std::min(max_size(), static_cast<size_type>(std::distance(first, last)))) {
+ std::uninitialized_copy(first, first + mSize, begin());
+ }
+
+ // Constructs at most N elements. The template arguments T and N are inferred using the
+ // deduction guide defined below. Note that T is determined from the first element, and
+ // subsequent elements must have convertible types:
+ //
+ // ftl::StaticVector vector = {1, 2, 3};
+ // static_assert(std::is_same_v<decltype(vector), ftl::StaticVector<int, 3>>);
+ //
+ // const auto copy = "quince"s;
+ // auto move = "tart"s;
+ // ftl::StaticVector vector = {copy, std::move(move)};
+ //
+ // static_assert(std::is_same_v<decltype(vector), ftl::StaticVector<std::string, 2>>);
+ //
+ template <typename E, typename... Es,
+ typename = std::enable_if_t<std::is_constructible_v<value_type, E>>>
+ StaticVector(E&& element, Es&&... elements)
+ : StaticVector(std::index_sequence<0>{}, std::forward<E>(element),
+ std::forward<Es>(elements)...) {
+ static_assert(sizeof...(elements) < N, "Too many elements");
+ }
+
+ // Constructs at most N elements. The template arguments T and N are inferred using the
+ // deduction guide defined below. Element types must be convertible to the specified T:
+ //
+ // ftl::StaticVector vector(std::in_place_type<std::string>, "red", "velvet", "cake");
+ // static_assert(std::is_same_v<decltype(vector), ftl::StaticVector<std::string, 3>>);
+ //
+ template <typename... Es>
+ explicit StaticVector(std::in_place_type_t<T>, Es... elements)
+ : StaticVector(std::forward<Es>(elements)...) {}
+
+ ~StaticVector() { std::destroy(begin(), end()); }
+
+ StaticVector& operator=(const StaticVector& other) {
+ StaticVector copy(other);
+ swap(copy);
+ return *this;
+ }
+
+ StaticVector& operator=(StaticVector&& other) {
+ std::destroy(begin(), end());
+ mSize = 0;
+ swap<Empty>(other);
+ return *this;
+ }
+
+ template <typename = void>
+ void swap(StaticVector&);
+
+ size_type max_size() const { return N; }
+ size_type size() const { return mSize; }
+
+ bool empty() const { return size() == 0; }
+ bool full() const { return size() == max_size(); }
+
+ iterator begin() { return std::launder(reinterpret_cast<pointer>(mData)); }
+ const_iterator begin() const { return cbegin(); }
+ const_iterator cbegin() const { return mut().begin(); }
+
+ iterator end() { return begin() + size(); }
+ const_iterator end() const { return cend(); }
+ const_iterator cend() const { return mut().end(); }
+
+ reverse_iterator rbegin() { return std::make_reverse_iterator(end()); }
+ const_reverse_iterator rbegin() const { return crbegin(); }
+ const_reverse_iterator crbegin() const { return mut().rbegin(); }
+
+ reverse_iterator rend() { return std::make_reverse_iterator(begin()); }
+ const_reverse_iterator rend() const { return crend(); }
+ const_reverse_iterator crend() const { return mut().rend(); }
+
+ iterator last() { return end() - 1; }
+ const_iterator last() const { return mut().last(); }
+
+ reference front() { return *begin(); }
+ const_reference front() const { return mut().front(); }
+
+ reference back() { return *last(); }
+ const_reference back() const { return mut().back(); }
+
+ reference operator[](size_type i) { return *(begin() + i); }
+ const_reference operator[](size_type i) const { return mut()[i]; }
+
+ // Replaces an element, and returns an iterator to it. If the vector is full, the element is not
+ // replaced, and the end iterator is returned.
+ template <typename... Args>
+ iterator replace(const_iterator cit, Args&&... args) {
+ if (full()) return end();
+ // Append element, and move into place if not last.
+ emplace_back(std::forward<Args>(args)...);
+ if (cit != last()) unstable_erase(cit);
+ return const_cast<iterator>(cit);
+ }
+
+ // Appends an element, and returns an iterator to it. If the vector is full, the element is not
+ // inserted, and the end iterator is returned.
+ template <typename... Args>
+ iterator emplace_back(Args&&... args) {
+ if (full()) return end();
+ const iterator it = construct_at(end(), std::forward<Args>(args)...);
+ ++mSize;
+ return it;
+ }
+
+ // Erases an element, but does not preserve order. Rather than shifting subsequent elements,
+ // this moves the last element to the slot of the erased element.
+ void unstable_erase(const_iterator it) {
+ std::destroy_at(it);
+ if (it != last()) {
+ // Move last element and destroy its source for destructor side effects.
+ construct_at(it, std::move(back()));
+ std::destroy_at(last());
+ }
+ --mSize;
+ }
+
+ bool push_back(value_type v) {
+ // Two statements for sequence point.
+ const iterator it = emplace_back(std::move(v));
+ return it != end();
+ }
+
+ void pop_back() { unstable_erase(last()); }
+
+private:
+ struct Empty {};
+
+ StaticVector& mut() const { return *const_cast<StaticVector*>(this); }
+
+ // Recursion for variadic constructor.
+ template <size_t I, typename E, typename... Es>
+ StaticVector(std::index_sequence<I>, E&& element, Es&&... elements)
+ : StaticVector(std::index_sequence<I + 1>{}, std::forward<Es>(elements)...) {
+ construct_at(begin() + I, std::forward<E>(element));
+ }
+
+ // Base case for variadic constructor.
+ template <size_t I>
+ explicit StaticVector(std::index_sequence<I>) : mSize(I) {}
+
+ // TODO: Replace with std::construct_at in C++20.
+ template <typename... Args>
+ static pointer construct_at(const_iterator it, Args&&... args) {
+ void* const ptr = const_cast<void*>(static_cast<const void*>(it));
+ return new (ptr) value_type{std::forward<Args>(args)...};
+ }
+
+ size_type mSize = 0;
+ std::aligned_storage_t<sizeof(value_type), alignof(value_type)> mData[N];
+};
+
+// Deduction guide for array constructor.
+template <typename T, size_t N>
+StaticVector(T (&)[N]) -> StaticVector<std::remove_cv_t<T>, N>;
+
+// Deduction guide for variadic constructor.
+template <typename T, typename... Us, typename V = std::decay_t<T>,
+ typename = std::enable_if_t<(std::is_constructible_v<V, Us> && ...)>>
+StaticVector(T&&, Us&&...) -> StaticVector<V, 1 + sizeof...(Us)>;
+
+// Deduction guide for in-place constructor.
+template <typename T, typename... Us>
+StaticVector(std::in_place_type_t<T>, Us&&...) -> StaticVector<T, sizeof...(Us)>;
+
+template <typename T, size_t N>
+template <typename E>
+void StaticVector<T, N>::swap(StaticVector& other) {
+ auto [to, from] = std::make_pair(this, &other);
+ if (from == this) return;
+
+ // Assume this vector has fewer elements, so the excess of the other vector will be moved to it.
+ auto [min, max] = std::make_pair(size(), other.size());
+
+ // No elements to swap if moving into an empty vector.
+ if constexpr (std::is_same_v<E, Empty>) {
+ assert(min == 0);
+ } else {
+ if (min > max) {
+ std::swap(from, to);
+ std::swap(min, max);
+ }
+
+ // Swap elements [0, min).
+ std::swap_ranges(begin(), begin() + min, other.begin());
+
+ // No elements to move if sizes are equal.
+ if (min == max) return;
+ }
+
+ // Move elements [min, max) and destroy their source for destructor side effects.
+ const auto [first, last] = std::make_pair(from->begin() + min, from->begin() + max);
+ std::uninitialized_move(first, last, to->begin() + min);
+ std::destroy(first, last);
+
+ std::swap(mSize, other.mSize);
+}
+
+template <typename T, size_t N>
+inline void swap(StaticVector<T, N>& lhs, StaticVector<T, N>& rhs) {
+ lhs.swap(rhs);
+}
+
+// TODO: Replace with operator<=> in C++20.
+template <typename T, size_t N, size_t M>
+inline bool operator==(const StaticVector<T, N>& lhs, const StaticVector<T, M>& rhs) {
+ return lhs.size() == rhs.size() && std::equal(lhs.begin(), lhs.end(), rhs.begin());
+}
+
+template <typename T, size_t N, size_t M>
+inline bool operator<(const StaticVector<T, N>& lhs, const StaticVector<T, M>& rhs) {
+ return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
+}
+
+template <typename T, size_t N, size_t M>
+inline bool operator>(const StaticVector<T, N>& lhs, const StaticVector<T, M>& rhs) {
+ return rhs < lhs;
+}
+
+template <typename T, size_t N, size_t M>
+inline bool operator!=(const StaticVector<T, N>& lhs, const StaticVector<T, M>& rhs) {
+ return !(lhs == rhs);
+}
+
+template <typename T, size_t N, size_t M>
+inline bool operator>=(const StaticVector<T, N>& lhs, const StaticVector<T, M>& rhs) {
+ return !(lhs < rhs);
+}
+
+template <typename T, size_t N, size_t M>
+inline bool operator<=(const StaticVector<T, N>& lhs, const StaticVector<T, M>& rhs) {
+ return !(rhs < lhs);
+}
+
+} // namespace android::ftl
diff --git a/include/gfx/.clang-format b/include/gfx/.clang-format
deleted file mode 100644
index 86763a0..0000000
--- a/include/gfx/.clang-format
+++ /dev/null
@@ -1,11 +0,0 @@
-BasedOnStyle: Google
-
-AccessModifierOffset: -2
-AllowShortFunctionsOnASingleLine: Inline
-BinPackParameters: false
-ColumnLimit: 100
-CommentPragmas: NOLINT:.*
-ConstructorInitializerAllOnOneLineOrOnePerLine: true
-ConstructorInitializerIndentWidth: 2
-ContinuationIndentWidth: 8
-IndentWidth: 4
diff --git a/libs/ftl/Android.bp b/libs/ftl/Android.bp
new file mode 100644
index 0000000..e11be57
--- /dev/null
+++ b/libs/ftl/Android.bp
@@ -0,0 +1,16 @@
+cc_test {
+ name: "ftl_test",
+ test_suites: ["device-tests"],
+ sanitize: {
+ address: true,
+ },
+ srcs: [
+ "StaticVector_test.cpp",
+ ],
+ cflags: [
+ "-Wall",
+ "-Werror",
+ "-Wextra",
+ "-Wpedantic",
+ ],
+}
diff --git a/libs/ftl/StaticVector_test.cpp b/libs/ftl/StaticVector_test.cpp
new file mode 100644
index 0000000..06e4659
--- /dev/null
+++ b/libs/ftl/StaticVector_test.cpp
@@ -0,0 +1,347 @@
+/*
+ * Copyright 2020 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 <ftl/StaticVector.h>
+#include <gtest/gtest.h>
+
+#include <algorithm>
+#include <iterator>
+#include <string>
+#include <utility>
+
+using namespace std::string_literals;
+
+namespace android::test {
+
+using ftl::StaticVector;
+
+// Keep in sync with example usage in header file.
+TEST(StaticVector, Example) {
+ ftl::StaticVector<char, 3> vector;
+ EXPECT_TRUE(vector.empty());
+
+ vector = {'a', 'b'};
+ EXPECT_EQ(vector.size(), 2u);
+
+ vector.push_back('c');
+ EXPECT_TRUE(vector.full());
+
+ EXPECT_FALSE(vector.push_back('d'));
+ EXPECT_EQ(vector.size(), 3u);
+
+ vector.unstable_erase(vector.begin());
+ EXPECT_EQ(vector, (ftl::StaticVector{'c', 'b'}));
+
+ vector.pop_back();
+ EXPECT_EQ(vector.back(), 'c');
+
+ const char array[] = "hi";
+ vector = ftl::StaticVector(array);
+ EXPECT_EQ(vector, (ftl::StaticVector{'h', 'i', '\0'}));
+}
+
+TEST(StaticVector, Construct) {
+ {
+ // Default constructor.
+ StaticVector<std::string, 2> vector;
+ EXPECT_TRUE(vector.empty());
+ }
+ {
+ // Array constructor.
+ const float kFloats[] = {.1f, .2f, .3f};
+ StaticVector vector(kFloats);
+ EXPECT_EQ(vector, (StaticVector{.1f, .2f, .3f}));
+ }
+ {
+ // Iterator constructor.
+ const char chars[] = "abcdef";
+ std::string string(chars);
+ StaticVector<char, sizeof(chars)> vector(string.begin(), string.end());
+
+ EXPECT_STREQ(vector.begin(), chars);
+ }
+ {
+ // Variadic constructor with same types.
+ StaticVector vector = {1, 2, 3};
+
+ static_assert(std::is_same_v<decltype(vector), StaticVector<int, 3>>);
+ EXPECT_EQ(vector, (StaticVector{1, 2, 3}));
+ }
+ {
+ // Variadic constructor with different types.
+ const auto copy = "quince"s;
+ auto move = "tart"s;
+ StaticVector vector = {copy, std::move(move)};
+
+ static_assert(std::is_same_v<decltype(vector), StaticVector<std::string, 2>>);
+ EXPECT_EQ(vector, (StaticVector{"quince"s, "tart"s}));
+ }
+ {
+ // In-place constructor with same types.
+ StaticVector vector(std::in_place_type<std::string>, "red", "velvet", "cake");
+
+ static_assert(std::is_same_v<decltype(vector), StaticVector<std::string, 3>>);
+ EXPECT_EQ(vector, (StaticVector{"red"s, "velvet"s, "cake"s}));
+ }
+ {
+ // In-place constructor with different types.
+ const auto copy = "red"s;
+ auto move = "velvet"s;
+ std::initializer_list<char> list = {'c', 'a', 'k', 'e'};
+ StaticVector vector(std::in_place_type<std::string>, copy.c_str(), std::move(move), list);
+
+ static_assert(std::is_same_v<decltype(vector), StaticVector<std::string, 3>>);
+ EXPECT_EQ(vector, (StaticVector{"red"s, "velvet"s, "cake"s}));
+ }
+}
+
+TEST(StaticVector, String) {
+ StaticVector<char, 10> chars;
+ char c = 'a';
+ std::generate_n(std::back_inserter(chars), chars.max_size(), [&c] { return c++; });
+ chars.back() = '\0';
+
+ EXPECT_STREQ(chars.begin(), "abcdefghi");
+
+ // Constructor takes iterator range.
+ const char kString[] = "123456";
+ StaticVector<char, 10> string(std::begin(kString), std::end(kString));
+
+ EXPECT_STREQ(string.begin(), "123456");
+ EXPECT_EQ(string.size(), 7u);
+
+ // Similar to emplace, but replaces rather than inserts.
+ const auto it = string.replace(string.begin() + 5, '\0');
+ EXPECT_NE(it, string.end());
+ EXPECT_STREQ(string.begin(), "12345");
+
+ swap(chars, string);
+
+ EXPECT_STREQ(chars.begin(), "12345");
+ EXPECT_STREQ(string.begin(), "abcdefghi");
+}
+
+TEST(StaticVector, CopyableElement) {
+ struct Pair {
+ const int a, b;
+ bool operator==(Pair p) const { return p.a == a && p.b == b; }
+ };
+
+ StaticVector<Pair, 5> pairs;
+
+ EXPECT_TRUE(pairs.empty());
+ EXPECT_EQ(pairs.max_size(), 5u);
+
+ for (size_t i = 0; i < pairs.max_size(); ++i) {
+ EXPECT_EQ(pairs.size(), i);
+
+ const int a = static_cast<int>(i) * 2;
+ const auto it = pairs.emplace_back(a, a + 1);
+ ASSERT_NE(it, pairs.end());
+ EXPECT_EQ(*it, (Pair{a, a + 1}));
+ }
+
+ EXPECT_TRUE(pairs.full());
+ EXPECT_EQ(pairs.size(), 5u);
+
+ // Insertion fails if the vector is full.
+ const auto it = pairs.emplace_back(10, 11);
+ EXPECT_EQ(it, pairs.end());
+
+ EXPECT_EQ(pairs, (StaticVector{Pair{0, 1}, Pair{2, 3}, Pair{4, 5}, Pair{6, 7}, Pair{8, 9}}));
+
+ // Constructor takes at most N elements.
+ StaticVector<int, 6> sums = {0, 0, 0, 0, 0, -1};
+ EXPECT_TRUE(sums.full());
+
+ // Random-access iterators comply with standard.
+ std::transform(pairs.begin(), pairs.end(), sums.begin(), [](Pair p) { return p.a + p.b; });
+ EXPECT_EQ(sums, (StaticVector{1, 5, 9, 13, 17, -1}));
+
+ sums.pop_back();
+ std::reverse(sums.begin(), sums.end());
+
+ EXPECT_EQ(sums, (StaticVector{17, 13, 9, 5, 1}));
+}
+
+TEST(StaticVector, MovableElement) {
+ // Construct std::string elements in-place from C-style strings. Without std::in_place_type, the
+ // element type would be deduced from the first element, i.e. const char*.
+ StaticVector strings(std::in_place_type<std::string>, "", "", "", "cake", "velvet", "red", "");
+ strings.pop_back();
+
+ EXPECT_EQ(strings.max_size(), 7u);
+ EXPECT_EQ(strings.size(), 6u);
+
+ // Erase "cake" and append a substring copy.
+ {
+ auto it = std::find_if(strings.begin(), strings.end(),
+ [](const auto& s) { return !s.empty(); });
+ ASSERT_FALSE(it == strings.end());
+ EXPECT_EQ(*it, "cake");
+
+ strings.unstable_erase(it);
+
+ // Construct std::string from first 4 characters of C-style string.
+ it = strings.emplace_back("cakewalk", 4u);
+ ASSERT_NE(it, strings.end());
+ EXPECT_EQ(*it, "cake"s);
+ }
+
+ strings[1] = "quince"s;
+
+ // Replace last empty string with "tart".
+ {
+ const auto rit = std::find(strings.rbegin(), strings.rend(), std::string());
+ ASSERT_FALSE(rit == strings.rend());
+
+ std::initializer_list<char> list = {'t', 'a', 'r', 't'};
+ const auto it = strings.replace(rit.base() - 1, list);
+ EXPECT_NE(it, strings.end());
+ }
+
+ strings.front().assign("pie");
+
+ EXPECT_EQ(strings, (StaticVector{"pie"s, "quince"s, "tart"s, "red"s, "velvet"s, "cake"s}));
+}
+
+TEST(StaticVector, ReverseTruncate) {
+ StaticVector<std::string, 10> strings("pie", "quince", "tart", "red", "velvet", "cake");
+ EXPECT_FALSE(strings.full());
+
+ for (auto it = strings.begin(); it != strings.end(); ++it) {
+ strings.replace(it, strings.back());
+ strings.pop_back();
+ }
+
+ EXPECT_EQ(strings, (StaticVector{"cake"s, "velvet"s, "red"s}));
+}
+
+TEST(StaticVector, Sort) {
+ StaticVector<std::string, 7> strings("pie", "quince", "tart", "red", "velvet", "cake");
+ EXPECT_FALSE(strings.full());
+
+ auto sorted = std::move(strings);
+ EXPECT_TRUE(strings.empty());
+
+ std::sort(sorted.begin(), sorted.end());
+ EXPECT_EQ(sorted, (StaticVector{"cake"s, "pie"s, "quince"s, "red"s, "tart"s, "velvet"s}));
+
+ // Constructor takes array reference.
+ {
+ const char* kStrings[] = {"cake", "lie"};
+ strings = StaticVector(kStrings);
+ }
+
+ EXPECT_GT(sorted, strings);
+ swap(sorted, strings);
+ EXPECT_LT(sorted, strings);
+
+ // Append remaining elements, such that "pie" is the only difference.
+ sorted.replace(sorted.end(), "quince");
+ for (const char* str : {"red", "tart", "velvet"}) sorted.emplace_back(str);
+
+ EXPECT_NE(sorted, strings);
+
+ sorted.replace(sorted.begin() + 1, "pie");
+ EXPECT_EQ(sorted, strings);
+}
+
+namespace {
+
+struct DestroyCounts {
+ DestroyCounts(int& live, int& dead) : counts{live, dead} {}
+ DestroyCounts(const DestroyCounts& other) : counts(other.counts) {}
+ DestroyCounts(DestroyCounts&& other) : counts(other.counts) { other.alive = false; }
+ ~DestroyCounts() { ++(alive ? counts.live : counts.dead); }
+
+ struct {
+ int& live;
+ int& dead;
+ } counts;
+
+ bool alive = true;
+};
+
+void swap(DestroyCounts& lhs, DestroyCounts& rhs) {
+ std::swap(lhs.alive, rhs.alive);
+}
+
+} // namespace
+
+TEST(StaticVector, Destroy) {
+ int live = 0;
+ int dead = 0;
+
+ { StaticVector<DestroyCounts, 5> counts; }
+ EXPECT_EQ(0, live);
+ EXPECT_EQ(0, dead);
+
+ {
+ StaticVector<DestroyCounts, 5> counts;
+ counts.emplace_back(live, dead);
+ counts.emplace_back(live, dead);
+ counts.emplace_back(live, dead);
+ }
+ EXPECT_EQ(3, live);
+ EXPECT_EQ(0, dead);
+
+ live = 0;
+ {
+ StaticVector<DestroyCounts, 5> counts;
+ counts.emplace_back(live, dead);
+ counts.emplace_back(live, dead);
+ counts.emplace_back(live, dead);
+
+ auto copy = counts;
+ }
+ EXPECT_EQ(6, live);
+ EXPECT_EQ(0, dead);
+
+ live = 0;
+ {
+ StaticVector<DestroyCounts, 5> counts;
+ counts.emplace_back(live, dead);
+ counts.emplace_back(live, dead);
+ counts.emplace_back(live, dead);
+
+ auto move = std::move(counts);
+ }
+ EXPECT_EQ(3, live);
+ EXPECT_EQ(3, dead);
+
+ live = dead = 0;
+ {
+ StaticVector<DestroyCounts, 5> counts1;
+ counts1.emplace_back(live, dead);
+ counts1.emplace_back(live, dead);
+ counts1.emplace_back(live, dead);
+
+ StaticVector<DestroyCounts, 5> counts2;
+ counts2.emplace_back(live, dead);
+
+ swap(counts1, counts2);
+
+ EXPECT_EQ(0, live);
+ EXPECT_EQ(2, dead);
+
+ dead = 0;
+ }
+ EXPECT_EQ(4, live);
+ EXPECT_EQ(0, dead);
+}
+
+} // namespace android::test