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/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