Merge changes Id8848530,I9331f202
* changes:
FTL: Add SmallMap<K, V, N>
FTL: Generalize StaticVector in-place construction
diff --git a/include/ftl/ArrayTraits.h b/include/ftl/ArrayTraits.h
index 28f717a..ff685c5 100644
--- a/include/ftl/ArrayTraits.h
+++ b/include/ftl/ArrayTraits.h
@@ -19,6 +19,7 @@
#include <algorithm>
#include <iterator>
#include <new>
+#include <type_traits>
#define FTL_ARRAY_TRAIT(T, U) using U = typename ArrayTraits<T>::U
@@ -40,11 +41,16 @@
using const_iterator = const_pointer;
using const_reverse_iterator = std::reverse_iterator<const_iterator>;
- // 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)...};
+ if constexpr (std::is_constructible_v<value_type, Args...>) {
+ // TODO: Replace with std::construct_at in C++20.
+ return new (ptr) value_type(std::forward<Args>(args)...);
+ } else {
+ // Fall back to list initialization.
+ return new (ptr) value_type{std::forward<Args>(args)...};
+ }
}
};
diff --git a/include/ftl/InitializerList.h b/include/ftl/InitializerList.h
new file mode 100644
index 0000000..bb99280
--- /dev/null
+++ b/include/ftl/InitializerList.h
@@ -0,0 +1,110 @@
+/*
+ * 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 <tuple>
+#include <utility>
+
+namespace android::ftl {
+
+// Compile-time counterpart of std::initializer_list<T> that stores per-element constructor
+// arguments with heterogeneous types. For a container with elements of type T, given Sizes
+// (S0, S1, ..., SN), N elements are initialized: the first element is initialized with the
+// first S0 arguments, the second element is initialized with the next S1 arguments, and so
+// on. The list of Types (T0, ..., TM) is flattened, so M is equal to the sum of the Sizes.
+//
+// The InitializerList is created using ftl::init::list, and is consumed by constructors of
+// containers. The function call operator is overloaded such that arguments are accumulated
+// in a tuple with each successive call. For instance, the following calls initialize three
+// strings using different constructors, i.e. string literal, default, and count/character:
+//
+// ... = ftl::init::list<std::string>("abc")()(3u, '?');
+//
+// The following syntax is a shorthand for key-value pairs, where the first argument is the
+// key, and the rest construct the value. The types of the key and value are deduced if the
+// first pair contains exactly two arguments:
+//
+// ... = ftl::init::map<int, std::string>(-1, "abc")(-2)(-3, 3u, '?');
+//
+// ... = ftl::init::map(0, 'a')(1, 'b')(2, 'c');
+//
+// WARNING: The InitializerList returned by an ftl::init::list expression must be consumed
+// immediately, since temporary arguments are destroyed after the full expression. Storing
+// an InitializerList results in dangling references.
+//
+template <typename T, typename Sizes = std::index_sequence<>, typename... Types>
+struct InitializerList;
+
+template <typename T, size_t... Sizes, typename... Types>
+struct InitializerList<T, std::index_sequence<Sizes...>, Types...> {
+ // Creates a superset InitializerList by appending the number of arguments to Sizes, and
+ // expanding Types with forwarding references for each argument.
+ template <typename... Args>
+ [[nodiscard]] constexpr auto operator()(Args&&... args) && -> InitializerList<
+ T, std::index_sequence<Sizes..., sizeof...(Args)>, Types..., Args&&...> {
+ return {std::tuple_cat(std::move(tuple),
+ std::forward_as_tuple(std::forward<Args>(args)...))};
+ }
+
+ // The temporary InitializerList returned by operator() is bound to an rvalue reference in
+ // container constructors, which extends the lifetime of any temporary arguments that this
+ // tuple refers to until the completion of the full expression containing the construction.
+ std::tuple<Types...> tuple;
+};
+
+template <typename K, typename V>
+struct KeyValue {};
+
+// Shorthand for key-value pairs that assigns the first argument to the key, and the rest to the
+// value. The specialization is on KeyValue rather than std::pair, so that ftl::init::list works
+// with the latter.
+template <typename K, typename V, size_t... Sizes, typename... Types>
+struct InitializerList<KeyValue<K, V>, std::index_sequence<Sizes...>, Types...> {
+ // Accumulate the three arguments to std::pair's piecewise constructor.
+ template <typename... Args>
+ [[nodiscard]] constexpr auto operator()(K&& k, Args&&... args) && -> InitializerList<
+ KeyValue<K, V>, std::index_sequence<Sizes..., 3>, Types..., std::piecewise_construct_t,
+ std::tuple<K&&>, std::tuple<Args&&...>> {
+ return {std::tuple_cat(std::move(tuple),
+ std::forward_as_tuple(std::piecewise_construct,
+ std::forward_as_tuple(std::forward<K>(k)),
+ std::forward_as_tuple(
+ std::forward<Args>(args)...)))};
+ }
+
+ std::tuple<Types...> tuple;
+};
+
+namespace init {
+
+template <typename T, typename... Args>
+[[nodiscard]] constexpr auto list(Args&&... args) {
+ return InitializerList<T>{}(std::forward<Args>(args)...);
+}
+
+template <typename K, typename V, typename... Args>
+[[nodiscard]] constexpr auto map(Args&&... args) {
+ return list<KeyValue<K, V>>(std::forward<Args>(args)...);
+}
+
+template <typename K, typename V>
+[[nodiscard]] constexpr auto map(K&& k, V&& v) {
+ return list<KeyValue<K, V>>(std::forward<K>(k), std::forward<V>(v));
+}
+
+} // namespace init
+} // namespace android::ftl
diff --git a/include/ftl/SmallMap.h b/include/ftl/SmallMap.h
new file mode 100644
index 0000000..87ae99c
--- /dev/null
+++ b/include/ftl/SmallMap.h
@@ -0,0 +1,205 @@
+/*
+ * 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 <ftl/InitializerList.h>
+#include <ftl/SmallVector.h>
+
+#include <functional>
+#include <optional>
+#include <type_traits>
+#include <utility>
+
+namespace android::ftl {
+
+// Associative container with unique, unordered keys. Unlike std::unordered_map, key-value pairs are
+// stored in contiguous storage for cache efficiency. The map is allocated statically until its size
+// exceeds N, at which point mappings are relocated to dynamic memory.
+//
+// SmallMap<K, V, 0> unconditionally allocates on the heap.
+//
+// Example usage:
+//
+// ftl::SmallMap<int, std::string, 3> map;
+// assert(map.empty());
+// assert(!map.dynamic());
+//
+// map = ftl::init::map<int, std::string>(123, "abc")(-1)(42, 3u, '?');
+// assert(map.size() == 3u);
+// assert(!map.dynamic());
+//
+// assert(map.contains(123));
+// assert(map.find(42, [](const std::string& s) { return s.size(); }) == 3u);
+//
+// const auto opt = map.find(-1);
+// assert(opt);
+//
+// std::string& ref = *opt;
+// assert(ref.empty());
+// ref = "xyz";
+//
+// assert(map == SmallMap(ftl::init::map(-1, "xyz")(42, "???")(123, "abc")));
+//
+template <typename K, typename V, size_t N>
+class SmallMap final {
+ using Map = SmallVector<std::pair<const K, V>, N>;
+
+public:
+ using key_type = K;
+ using mapped_type = V;
+
+ using value_type = typename Map::value_type;
+ using size_type = typename Map::size_type;
+ using difference_type = typename Map::difference_type;
+
+ using reference = typename Map::reference;
+ using iterator = typename Map::iterator;
+
+ using const_reference = typename Map::const_reference;
+ using const_iterator = typename Map::const_iterator;
+
+ // Creates an empty map.
+ SmallMap() = default;
+
+ // Constructs at most N key-value pairs in place by forwarding per-pair constructor arguments.
+ // The template arguments K, V, and N are inferred using the deduction guide defined below.
+ // The syntax for listing pairs is as follows:
+ //
+ // ftl::SmallMap map = ftl::init::map<int, std::string>(123, "abc")(-1)(42, 3u, '?');
+ //
+ // static_assert(std::is_same_v<decltype(map), ftl::SmallMap<int, std::string, 3>>);
+ // assert(map.size() == 3u);
+ // assert(map.contains(-1) && map.find(-1)->get().empty());
+ // assert(map.contains(42) && map.find(42)->get() == "???");
+ // assert(map.contains(123) && map.find(123)->get() == "abc");
+ //
+ // The types of the key and value are deduced if the first pair contains exactly two arguments:
+ //
+ // ftl::SmallMap map = ftl::init::map(0, 'a')(1, 'b')(2, 'c');
+ // static_assert(std::is_same_v<decltype(map), ftl::SmallMap<int, char, 3>>);
+ //
+ template <typename U, size_t... Sizes, typename... Types>
+ SmallMap(InitializerList<U, std::index_sequence<Sizes...>, Types...>&& init)
+ : mMap(std::move(init)) {
+ // TODO: Enforce unique keys.
+ }
+
+ size_type max_size() const { return mMap.max_size(); }
+ size_type size() const { return mMap.size(); }
+ bool empty() const { return mMap.empty(); }
+
+ // Returns whether the map is backed by static or dynamic storage.
+ bool dynamic() const { return mMap.dynamic(); }
+
+ iterator begin() { return mMap.begin(); }
+ const_iterator begin() const { return cbegin(); }
+ const_iterator cbegin() const { return mMap.cbegin(); }
+
+ iterator end() { return mMap.end(); }
+ const_iterator end() const { return cend(); }
+ const_iterator cend() const { return mMap.cend(); }
+
+ // Returns whether a mapping exists for the given key.
+ bool contains(const key_type& key) const {
+ return find(key, [](const mapped_type&) {});
+ }
+
+ // Returns a reference to the value for the given key, or std::nullopt if the key was not found.
+ //
+ // ftl::SmallMap map = ftl::init::map('a', 'A')('b', 'B')('c', 'C');
+ //
+ // const auto opt = map.find('c');
+ // assert(opt == 'C');
+ //
+ // char d = 'd';
+ // const auto ref = map.find('d').value_or(std::ref(d));
+ // ref.get() = 'D';
+ // assert(d == 'D');
+ //
+ auto find(const key_type& key) const
+ -> std::optional<std::reference_wrapper<const mapped_type>> {
+ return find(key, [](const mapped_type& v) { return std::cref(v); });
+ }
+
+ auto find(const key_type& key) -> std::optional<std::reference_wrapper<mapped_type>> {
+ return find(key, [](mapped_type& v) { return std::ref(v); });
+ }
+
+ // Returns the result R of a unary operation F on (a constant or mutable reference to) the value
+ // for the given key, or std::nullopt if the key was not found. If F has a return type of void,
+ // then the Boolean result indicates whether the key was found.
+ //
+ // ftl::SmallMap map = ftl::init::map('a', 'x')('b', 'y')('c', 'z');
+ //
+ // assert(map.find('c', [](char c) { return std::toupper(c); }) == 'Z');
+ // assert(map.find('c', [](char& c) { c = std::toupper(c); }));
+ //
+ template <typename F, typename R = std::invoke_result_t<F, const mapped_type&>>
+ auto find(const key_type& key, F f) const
+ -> std::conditional_t<std::is_void_v<R>, bool, std::optional<R>> {
+ for (auto& [k, v] : *this) {
+ if (k == key) {
+ if constexpr (std::is_void_v<R>) {
+ f(v);
+ return true;
+ } else {
+ return f(v);
+ }
+ }
+ }
+
+ return {};
+ }
+
+ template <typename F>
+ auto find(const key_type& key, F f) {
+ return std::as_const(*this).find(key, [&f](const mapped_type& v) {
+ return f(const_cast<mapped_type&>(v));
+ });
+ }
+
+private:
+ Map mMap;
+};
+
+// Deduction guide for in-place constructor.
+template <typename K, typename V, size_t... Sizes, typename... Types>
+SmallMap(InitializerList<KeyValue<K, V>, std::index_sequence<Sizes...>, Types...>&&)
+ -> SmallMap<K, V, sizeof...(Sizes)>;
+
+// Returns whether the key-value pairs of two maps are equal.
+template <typename K, typename V, size_t N, typename Q, typename W, size_t M>
+bool operator==(const SmallMap<K, V, N>& lhs, const SmallMap<Q, W, M>& rhs) {
+ if (lhs.size() != rhs.size()) return false;
+
+ for (const auto& [k, v] : lhs) {
+ const auto& lv = v;
+ if (!rhs.find(k, [&lv](const auto& rv) { return lv == rv; }).value_or(false)) {
+ return false;
+ }
+ }
+
+ return true;
+}
+
+// TODO: Remove in C++20.
+template <typename K, typename V, size_t N, typename Q, typename W, size_t M>
+inline bool operator!=(const SmallMap<K, V, N>& lhs, const SmallMap<Q, W, M>& rhs) {
+ return !(lhs == rhs);
+}
+
+} // namespace android::ftl
diff --git a/include/ftl/SmallVector.h b/include/ftl/SmallVector.h
index cecec7f..2f05a9b 100644
--- a/include/ftl/SmallVector.h
+++ b/include/ftl/SmallVector.h
@@ -64,6 +64,16 @@
// assert(vector == (ftl::SmallVector{'h', 'i', '\0'}));
// assert(!vector.dynamic());
//
+// ftl::SmallVector strings = ftl::init::list<std::string>("abc")
+// ("123456", 3u)
+// (3u, '?');
+// assert(strings.size() == 3u);
+// assert(!strings.dynamic());
+//
+// assert(strings[0] == "abc");
+// assert(strings[1] == "123");
+// assert(strings[2] == "???");
+//
template <typename T, size_t N>
class SmallVector final : ArrayTraits<T>, ArrayComparators<SmallVector> {
using Static = StaticVector<T, N>;
@@ -365,8 +375,9 @@
SmallVector(T&&, Us&&...) -> SmallVector<V, 1 + sizeof...(Us)>;
// Deduction guide for in-place constructor.
-template <typename T, typename... Us>
-SmallVector(std::in_place_type_t<T>, Us&&...) -> SmallVector<T, sizeof...(Us)>;
+template <typename T, size_t... Sizes, typename... Types>
+SmallVector(InitializerList<T, std::index_sequence<Sizes...>, Types...>&&)
+ -> SmallVector<T, sizeof...(Sizes)>;
// Deduction guide for StaticVector conversion.
template <typename T, size_t N>
diff --git a/include/ftl/StaticVector.h b/include/ftl/StaticVector.h
index 457095d..c132556 100644
--- a/include/ftl/StaticVector.h
+++ b/include/ftl/StaticVector.h
@@ -17,6 +17,7 @@
#pragma once
#include <ftl/ArrayTraits.h>
+#include <ftl/InitializerList.h>
#include <algorithm>
#include <cassert>
@@ -32,7 +33,7 @@
// 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
+// default constructor, since elements are constructed in place as the vector grows. Operations that
// insert an element (emplace_back, push_back, etc.) fail when the vector is full. The API otherwise
// adheres to standard containers, except the unstable_erase operation that does not preserve order,
// and the replace operation that destructively emplaces.
@@ -63,6 +64,14 @@
// vector = ftl::StaticVector(array);
// assert(vector == (ftl::StaticVector{'h', 'i', '\0'}));
//
+// ftl::StaticVector strings = ftl::init::list<std::string>("abc")
+// ("123456", 3u)
+// (3u, '?');
+// assert(strings.size() == 3u);
+// assert(strings[0] == "abc");
+// assert(strings[1] == "123");
+// assert(strings[2] == "???");
+//
template <typename T, size_t N>
class StaticVector final : ArrayTraits<T>,
ArrayIterators<StaticVector<T, N>, T>,
@@ -153,15 +162,22 @@
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:
+ // Constructs at most N elements in place by forwarding per-element constructor arguments. The
+ // template arguments T and N are inferred using the deduction guide defined below. The syntax
+ // for listing arguments is as follows:
//
- // ftl::StaticVector vector(std::in_place_type<std::string>, "red", "velvet", "cake");
+ // ftl::StaticVector vector = ftl::init::list<std::string>("abc")()(3u, '?');
+ //
// static_assert(std::is_same_v<decltype(vector), ftl::StaticVector<std::string, 3>>);
+ // assert(vector.full());
+ // assert(vector[0] == "abc");
+ // assert(vector[1].empty());
+ // assert(vector[2] == "???");
//
- template <typename... Es>
- explicit StaticVector(std::in_place_type_t<T>, Es... elements)
- : StaticVector(std::forward<Es>(elements)...) {}
+ template <typename U, size_t Size, size_t... Sizes, typename... Types>
+ StaticVector(InitializerList<U, std::index_sequence<Size, Sizes...>, Types...>&& init)
+ : StaticVector(std::index_sequence<0, 0, Size>{}, std::make_index_sequence<Size>{},
+ std::index_sequence<Sizes...>{}, init.tuple) {}
~StaticVector() { std::destroy(begin(), end()); }
@@ -292,6 +308,32 @@
template <size_t I>
explicit StaticVector(std::index_sequence<I>) : mSize(I) {}
+ // Recursion for in-place constructor.
+ //
+ // Construct element I by extracting its arguments from the InitializerList tuple. ArgIndex
+ // is the position of its first argument in Args, and ArgCount is the number of arguments.
+ // The Indices sequence corresponds to [0, ArgCount).
+ //
+ // The Sizes sequence lists the argument counts for elements after I, so Size is the ArgCount
+ // for the next element. The recursion stops when Sizes is empty for the last element.
+ //
+ template <size_t I, size_t ArgIndex, size_t ArgCount, size_t... Indices, size_t Size,
+ size_t... Sizes, typename... Args>
+ StaticVector(std::index_sequence<I, ArgIndex, ArgCount>, std::index_sequence<Indices...>,
+ std::index_sequence<Size, Sizes...>, std::tuple<Args...>& tuple)
+ : StaticVector(std::index_sequence<I + 1, ArgIndex + ArgCount, Size>{},
+ std::make_index_sequence<Size>{}, std::index_sequence<Sizes...>{}, tuple) {
+ construct_at(begin() + I, std::move(std::get<ArgIndex + Indices>(tuple))...);
+ }
+
+ // Base case for in-place constructor.
+ template <size_t I, size_t ArgIndex, size_t ArgCount, size_t... Indices, typename... Args>
+ StaticVector(std::index_sequence<I, ArgIndex, ArgCount>, std::index_sequence<Indices...>,
+ std::index_sequence<>, std::tuple<Args...>& tuple)
+ : mSize(I + 1) {
+ construct_at(begin() + I, std::move(std::get<ArgIndex + Indices>(tuple))...);
+ }
+
size_type mSize = 0;
std::aligned_storage_t<sizeof(value_type), alignof(value_type)> mData[N];
};
@@ -306,8 +348,9 @@
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... Sizes, typename... Types>
+StaticVector(InitializerList<T, std::index_sequence<Sizes...>, Types...>&&)
+ -> StaticVector<T, sizeof...(Sizes)>;
template <typename T, size_t N>
template <typename E>
diff --git a/libs/ftl/Android.bp b/libs/ftl/Android.bp
index fb32382..eb8e57a 100644
--- a/libs/ftl/Android.bp
+++ b/libs/ftl/Android.bp
@@ -5,6 +5,7 @@
address: true,
},
srcs: [
+ "SmallMap_test.cpp",
"SmallVector_test.cpp",
"StaticVector_test.cpp",
],
diff --git a/libs/ftl/SmallMap_test.cpp b/libs/ftl/SmallMap_test.cpp
new file mode 100644
index 0000000..fa00c06
--- /dev/null
+++ b/libs/ftl/SmallMap_test.cpp
@@ -0,0 +1,131 @@
+/*
+ * 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/SmallMap.h>
+#include <gtest/gtest.h>
+
+#include <cctype>
+
+namespace android::test {
+
+using ftl::SmallMap;
+
+// Keep in sync with example usage in header file.
+TEST(SmallMap, Example) {
+ ftl::SmallMap<int, std::string, 3> map;
+ EXPECT_TRUE(map.empty());
+ EXPECT_FALSE(map.dynamic());
+
+ map = ftl::init::map<int, std::string>(123, "abc")(-1)(42, 3u, '?');
+ EXPECT_EQ(map.size(), 3u);
+ EXPECT_FALSE(map.dynamic());
+
+ EXPECT_TRUE(map.contains(123));
+
+ EXPECT_EQ(map.find(42, [](const std::string& s) { return s.size(); }), 3u);
+
+ const auto opt = map.find(-1);
+ ASSERT_TRUE(opt);
+
+ std::string& ref = *opt;
+ EXPECT_TRUE(ref.empty());
+ ref = "xyz";
+
+ EXPECT_EQ(map, SmallMap(ftl::init::map(-1, "xyz")(42, "???")(123, "abc")));
+}
+
+TEST(SmallMap, Construct) {
+ {
+ // Default constructor.
+ SmallMap<int, std::string, 2> map;
+
+ EXPECT_TRUE(map.empty());
+ EXPECT_FALSE(map.dynamic());
+ }
+ {
+ // In-place constructor with same types.
+ SmallMap<int, std::string, 5> map =
+ ftl::init::map<int, std::string>(123, "abc")(456, "def")(789, "ghi");
+
+ EXPECT_EQ(map.size(), 3u);
+ EXPECT_EQ(map.max_size(), 5u);
+ EXPECT_FALSE(map.dynamic());
+
+ EXPECT_EQ(map, SmallMap(ftl::init::map(123, "abc")(456, "def")(789, "ghi")));
+ }
+ {
+ // In-place constructor with different types.
+ SmallMap<int, std::string, 5> map =
+ ftl::init::map<int, std::string>(123, "abc")(-1)(42, 3u, '?');
+
+ EXPECT_EQ(map.size(), 3u);
+ EXPECT_EQ(map.max_size(), 5u);
+ EXPECT_FALSE(map.dynamic());
+
+ EXPECT_EQ(map, SmallMap(ftl::init::map(42, "???")(123, "abc")(-1, "\0\0\0")));
+ }
+ {
+ // In-place constructor with implicit size.
+ SmallMap map = ftl::init::map<int, std::string>(123, "abc")(-1)(42, 3u, '?');
+
+ static_assert(std::is_same_v<decltype(map), SmallMap<int, std::string, 3>>);
+ EXPECT_EQ(map.size(), 3u);
+ EXPECT_EQ(map.max_size(), 3u);
+ EXPECT_FALSE(map.dynamic());
+
+ EXPECT_EQ(map, SmallMap(ftl::init::map(-1, "\0\0\0")(42, "???")(123, "abc")));
+ }
+}
+
+TEST(SmallMap, Find) {
+ {
+ // Constant reference.
+ const ftl::SmallMap map = ftl::init::map('a', 'A')('b', 'B')('c', 'C');
+
+ const auto opt = map.find('b');
+ EXPECT_EQ(opt, 'B');
+
+ const char d = 'D';
+ const auto ref = map.find('d').value_or(std::cref(d));
+ EXPECT_EQ(ref.get(), 'D');
+ }
+ {
+ // Mutable reference.
+ ftl::SmallMap map = ftl::init::map('a', 'A')('b', 'B')('c', 'C');
+
+ const auto opt = map.find('c');
+ EXPECT_EQ(opt, 'C');
+
+ char d = 'd';
+ const auto ref = map.find('d').value_or(std::ref(d));
+ ref.get() = 'D';
+ EXPECT_EQ(d, 'D');
+ }
+ {
+ // Constant unary operation.
+ const ftl::SmallMap map = ftl::init::map('a', 'x')('b', 'y')('c', 'z');
+ EXPECT_EQ(map.find('c', [](char c) { return std::toupper(c); }), 'Z');
+ }
+ {
+ // Mutable unary operation.
+ ftl::SmallMap map = ftl::init::map('a', 'x')('b', 'y')('c', 'z');
+ EXPECT_TRUE(map.find('c', [](char& c) { c = std::toupper(c); }));
+
+ EXPECT_EQ(map, SmallMap(ftl::init::map('c', 'Z')('b', 'y')('a', 'x')));
+ }
+}
+
+} // namespace android::test
diff --git a/libs/ftl/SmallVector_test.cpp b/libs/ftl/SmallVector_test.cpp
index c41e622..d0c2858 100644
--- a/libs/ftl/SmallVector_test.cpp
+++ b/libs/ftl/SmallVector_test.cpp
@@ -52,6 +52,14 @@
vector = ftl::SmallVector(array);
EXPECT_EQ(vector, (ftl::SmallVector{'h', 'i', '\0'}));
EXPECT_FALSE(vector.dynamic());
+
+ ftl::SmallVector strings = ftl::init::list<std::string>("abc")("123456", 3u)(3u, '?');
+ ASSERT_EQ(strings.size(), 3u);
+ EXPECT_FALSE(strings.dynamic());
+
+ EXPECT_EQ(strings[0], "abc");
+ EXPECT_EQ(strings[1], "123");
+ EXPECT_EQ(strings[2], "???");
}
TEST(SmallVector, Construct) {
@@ -99,7 +107,8 @@
}
{
// In-place constructor with same types.
- SmallVector vector(std::in_place_type<std::string>, "red", "velvet", "cake");
+ SmallVector vector =
+ ftl::init::list<std::string>("redolent", 3u)("velveteen", 6u)("cakewalk", 4u);
static_assert(std::is_same_v<decltype(vector), SmallVector<std::string, 3>>);
EXPECT_EQ(vector, (SmallVector{"red"s, "velvet"s, "cake"s}));
@@ -110,9 +119,10 @@
const auto copy = "red"s;
auto move = "velvet"s;
std::initializer_list<char> list = {'c', 'a', 'k', 'e'};
- SmallVector vector(std::in_place_type<std::string>, copy.c_str(), std::move(move), list);
+ SmallVector vector = ftl::init::list<std::string>(copy.c_str())(std::move(move))(list);
static_assert(std::is_same_v<decltype(vector), SmallVector<std::string, 3>>);
+ EXPECT_TRUE(move.empty());
EXPECT_EQ(vector, (SmallVector{"red"s, "velvet"s, "cake"s}));
EXPECT_FALSE(vector.dynamic());
}
@@ -206,9 +216,8 @@
}
TEST(SmallVector, 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*.
- SmallVector strings(std::in_place_type<std::string>, "", "", "", "cake", "velvet", "red", "");
+ // Construct std::string elements in place from per-element arguments.
+ SmallVector strings = ftl::init::list<std::string>()()()("cake")("velvet")("red")();
strings.pop_back();
EXPECT_EQ(strings.max_size(), 7u);
@@ -221,6 +230,7 @@
ASSERT_FALSE(it == strings.end());
EXPECT_EQ(*it, "cake");
+ // Construct std::string from first 4 characters of string literal.
strings.unstable_erase(it);
EXPECT_EQ(strings.emplace_back("cakewalk", 4u), "cake"s);
}
@@ -260,7 +270,7 @@
bool operator==(const Word& other) const { return other.str == str; }
};
- SmallVector words(std::in_place_type<Word>, "colored", "velour");
+ SmallVector words = ftl::init::list<Word>("colored")("velour");
// The replaced element can be referenced by the replacement.
{
@@ -301,7 +311,7 @@
}
TEST(SmallVector, Sort) {
- SmallVector strings(std::in_place_type<std::string>, "pie", "quince", "tart", "red", "velvet");
+ SmallVector strings = ftl::init::list<std::string>("pie")("quince")("tart")("red")("velvet");
strings.push_back("cake"s);
auto sorted = std::move(strings);
diff --git a/libs/ftl/StaticVector_test.cpp b/libs/ftl/StaticVector_test.cpp
index dd5ce35..db42d23 100644
--- a/libs/ftl/StaticVector_test.cpp
+++ b/libs/ftl/StaticVector_test.cpp
@@ -51,6 +51,13 @@
const char array[] = "hi";
vector = ftl::StaticVector(array);
EXPECT_EQ(vector, (ftl::StaticVector{'h', 'i', '\0'}));
+
+ ftl::StaticVector strings = ftl::init::list<std::string>("abc")("123456", 3u)(3u, '?');
+ ASSERT_EQ(strings.size(), 3u);
+
+ EXPECT_EQ(strings[0], "abc");
+ EXPECT_EQ(strings[1], "123");
+ EXPECT_EQ(strings[2], "???");
}
TEST(StaticVector, Construct) {
@@ -91,7 +98,8 @@
}
{
// In-place constructor with same types.
- StaticVector vector(std::in_place_type<std::string>, "red", "velvet", "cake");
+ StaticVector vector =
+ ftl::init::list<std::string>("redolent", 3u)("velveteen", 6u)("cakewalk", 4u);
static_assert(std::is_same_v<decltype(vector), StaticVector<std::string, 3>>);
EXPECT_EQ(vector, (StaticVector{"red"s, "velvet"s, "cake"s}));
@@ -101,9 +109,10 @@
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);
+ StaticVector vector = ftl::init::list<std::string>(copy.c_str())(std::move(move))(list);
static_assert(std::is_same_v<decltype(vector), StaticVector<std::string, 3>>);
+ EXPECT_TRUE(move.empty());
EXPECT_EQ(vector, (StaticVector{"red"s, "velvet"s, "cake"s}));
}
{
@@ -204,9 +213,8 @@
}
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", "");
+ // Construct std::string elements in place from per-element arguments.
+ StaticVector strings = ftl::init::list<std::string>()()()("cake")("velvet")("red")();
strings.pop_back();
EXPECT_EQ(strings.max_size(), 7u);
@@ -221,7 +229,7 @@
strings.unstable_erase(it);
- // Construct std::string from first 4 characters of C-style string.
+ // Construct std::string from first 4 characters of string literal.
it = strings.emplace_back("cakewalk", 4u);
ASSERT_NE(it, strings.end());
EXPECT_EQ(*it, "cake"s);
@@ -250,7 +258,7 @@
const std::string str;
};
- StaticVector words(std::in_place_type<Word>, "red", "velour", "cake");
+ StaticVector words = ftl::init::list<Word>("red")("velour")("cake");
// The replaced element can be referenced by the replacement.
const auto it = words.begin() + 1;