FTL: Configure clang-format
Bug: 160012986
Test: ftl_test
Change-Id: Iab01c967b9318afecb21107a6c25bebc4178edcd
diff --git a/include/ftl/.clang-format b/include/ftl/.clang-format
new file mode 120000
index 0000000..86b1593
--- /dev/null
+++ b/include/ftl/.clang-format
@@ -0,0 +1 @@
+../../../../build/soong/scripts/system-clang-format-2
\ No newline at end of file
diff --git a/include/ftl/array_traits.h b/include/ftl/array_traits.h
index 011034f..1265fa1 100644
--- a/include/ftl/array_traits.h
+++ b/include/ftl/array_traits.h
@@ -27,109 +27,109 @@
template <typename T>
struct ArrayTraits {
- using value_type = T;
- using size_type = std::size_t;
- using difference_type = std::ptrdiff_t;
+ using value_type = T;
+ using size_type = std::size_t;
+ using difference_type = std::ptrdiff_t;
- using pointer = value_type*;
- using reference = value_type&;
- using iterator = pointer;
- using reverse_iterator = std::reverse_iterator<iterator>;
+ 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>;
+ 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>;
- template <typename... Args>
- static pointer construct_at(const_iterator it, Args&&... args) {
- void* const ptr = const_cast<void*>(static_cast<const void*>(it));
- 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)...};
- }
+ template <typename... Args>
+ static pointer construct_at(const_iterator it, Args&&... args) {
+ void* const ptr = const_cast<void*>(static_cast<const void*>(it));
+ 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)...};
}
+ }
};
// CRTP mixin to define iterator functions in terms of non-const Self::begin and Self::end.
template <typename Self, typename T>
class ArrayIterators {
- FTL_ARRAY_TRAIT(T, size_type);
+ FTL_ARRAY_TRAIT(T, size_type);
- FTL_ARRAY_TRAIT(T, reference);
- FTL_ARRAY_TRAIT(T, iterator);
- FTL_ARRAY_TRAIT(T, reverse_iterator);
+ FTL_ARRAY_TRAIT(T, reference);
+ FTL_ARRAY_TRAIT(T, iterator);
+ FTL_ARRAY_TRAIT(T, reverse_iterator);
- FTL_ARRAY_TRAIT(T, const_reference);
- FTL_ARRAY_TRAIT(T, const_iterator);
- FTL_ARRAY_TRAIT(T, const_reverse_iterator);
+ FTL_ARRAY_TRAIT(T, const_reference);
+ FTL_ARRAY_TRAIT(T, const_iterator);
+ FTL_ARRAY_TRAIT(T, const_reverse_iterator);
- Self& self() const { return *const_cast<Self*>(static_cast<const Self*>(this)); }
+ Self& self() const { return *const_cast<Self*>(static_cast<const Self*>(this)); }
-public:
- const_iterator begin() const { return cbegin(); }
- const_iterator cbegin() const { return self().begin(); }
+ public:
+ const_iterator begin() const { return cbegin(); }
+ const_iterator cbegin() const { return self().begin(); }
- const_iterator end() const { return cend(); }
- const_iterator cend() const { return self().end(); }
+ const_iterator end() const { return cend(); }
+ const_iterator cend() const { return self().end(); }
- reverse_iterator rbegin() { return std::make_reverse_iterator(self().end()); }
- const_reverse_iterator rbegin() const { return crbegin(); }
- const_reverse_iterator crbegin() const { return self().rbegin(); }
+ reverse_iterator rbegin() { return std::make_reverse_iterator(self().end()); }
+ const_reverse_iterator rbegin() const { return crbegin(); }
+ const_reverse_iterator crbegin() const { return self().rbegin(); }
- reverse_iterator rend() { return std::make_reverse_iterator(self().begin()); }
- const_reverse_iterator rend() const { return crend(); }
- const_reverse_iterator crend() const { return self().rend(); }
+ reverse_iterator rend() { return std::make_reverse_iterator(self().begin()); }
+ const_reverse_iterator rend() const { return crend(); }
+ const_reverse_iterator crend() const { return self().rend(); }
- iterator last() { return self().end() - 1; }
- const_iterator last() const { return self().last(); }
+ iterator last() { return self().end() - 1; }
+ const_iterator last() const { return self().last(); }
- reference front() { return *self().begin(); }
- const_reference front() const { return self().front(); }
+ reference front() { return *self().begin(); }
+ const_reference front() const { return self().front(); }
- reference back() { return *last(); }
- const_reference back() const { return self().back(); }
+ reference back() { return *last(); }
+ const_reference back() const { return self().back(); }
- reference operator[](size_type i) { return *(self().begin() + i); }
- const_reference operator[](size_type i) const { return self()[i]; }
+ reference operator[](size_type i) { return *(self().begin() + i); }
+ const_reference operator[](size_type i) const { return self()[i]; }
};
// Mixin to define comparison operators for an array-like template.
// TODO: Replace with operator<=> in C++20.
template <template <typename, std::size_t> class Array>
struct ArrayComparators {
- template <typename T, std::size_t N, std::size_t M>
- friend bool operator==(const Array<T, N>& lhs, const Array<T, M>& rhs) {
- return lhs.size() == rhs.size() && std::equal(lhs.begin(), lhs.end(), rhs.begin());
- }
+ template <typename T, std::size_t N, std::size_t M>
+ friend bool operator==(const Array<T, N>& lhs, const Array<T, M>& rhs) {
+ return lhs.size() == rhs.size() && std::equal(lhs.begin(), lhs.end(), rhs.begin());
+ }
- template <typename T, std::size_t N, std::size_t M>
- friend bool operator<(const Array<T, N>& lhs, const Array<T, M>& rhs) {
- return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
- }
+ template <typename T, std::size_t N, std::size_t M>
+ friend bool operator<(const Array<T, N>& lhs, const Array<T, M>& rhs) {
+ return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
+ }
- template <typename T, std::size_t N, std::size_t M>
- friend bool operator>(const Array<T, N>& lhs, const Array<T, M>& rhs) {
- return rhs < lhs;
- }
+ template <typename T, std::size_t N, std::size_t M>
+ friend bool operator>(const Array<T, N>& lhs, const Array<T, M>& rhs) {
+ return rhs < lhs;
+ }
- template <typename T, std::size_t N, std::size_t M>
- friend bool operator!=(const Array<T, N>& lhs, const Array<T, M>& rhs) {
- return !(lhs == rhs);
- }
+ template <typename T, std::size_t N, std::size_t M>
+ friend bool operator!=(const Array<T, N>& lhs, const Array<T, M>& rhs) {
+ return !(lhs == rhs);
+ }
- template <typename T, std::size_t N, std::size_t M>
- friend bool operator>=(const Array<T, N>& lhs, const Array<T, M>& rhs) {
- return !(lhs < rhs);
- }
+ template <typename T, std::size_t N, std::size_t M>
+ friend bool operator>=(const Array<T, N>& lhs, const Array<T, M>& rhs) {
+ return !(lhs < rhs);
+ }
- template <typename T, std::size_t N, std::size_t M>
- friend bool operator<=(const Array<T, N>& lhs, const Array<T, M>& rhs) {
- return !(lhs > rhs);
- }
+ template <typename T, std::size_t N, std::size_t M>
+ friend bool operator<=(const Array<T, N>& lhs, const Array<T, M>& rhs) {
+ return !(lhs > rhs);
+ }
};
-} // namespace android::ftl
+} // namespace android::ftl
diff --git a/include/ftl/initializer_list.h b/include/ftl/initializer_list.h
index 62f63b7..769c09f 100644
--- a/include/ftl/initializer_list.h
+++ b/include/ftl/initializer_list.h
@@ -32,15 +32,15 @@
// 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, '?');
+// ... = 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<int, std::string>(-1, "abc")(-2)(-3, 3u, '?');
//
-// ... = ftl::init::map(0, 'a')(1, 'b')(2, 'c');
+// ... = 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
@@ -51,19 +51,18 @@
template <typename T, std::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)...))};
- }
+ // 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;
+ // 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>
@@ -74,37 +73,36 @@
// with the latter.
template <typename K, typename V, std::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)...)))};
- }
+ // 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;
+ std::tuple<Types...> tuple;
};
namespace init {
template <typename T, typename... Args>
[[nodiscard]] constexpr auto list(Args&&... args) {
- return InitializerList<T>{}(std::forward<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)...);
+ 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));
+ return list<KeyValue<K, V>>(std::forward<K>(k), std::forward<V>(v));
}
-} // namespace init
-} // namespace android::ftl
+} // namespace init
+} // namespace android::ftl
diff --git a/include/ftl/small_map.h b/include/ftl/small_map.h
index d058369..84c15eb 100644
--- a/include/ftl/small_map.h
+++ b/include/ftl/small_map.h
@@ -34,172 +34,170 @@
//
// Example usage:
//
-// ftl::SmallMap<int, std::string, 3> map;
-// assert(map.empty());
-// assert(!map.dynamic());
+// 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());
+// 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);
+// assert(map.contains(123));
+// assert(map.find(42, [](const std::string& s) { return s.size(); }) == 3u);
//
-// const auto opt = map.find(-1);
-// assert(opt);
+// const auto opt = map.find(-1);
+// assert(opt);
//
-// std::string& ref = *opt;
-// assert(ref.empty());
-// ref = "xyz";
+// std::string& ref = *opt;
+// assert(ref.empty());
+// ref = "xyz";
//
-// assert(map == SmallMap(ftl::init::map(-1, "xyz")(42, "???")(123, "abc")));
+// assert(map == SmallMap(ftl::init::map(-1, "xyz")(42, "???")(123, "abc")));
//
template <typename K, typename V, std::size_t N>
class SmallMap final {
- using Map = SmallVector<std::pair<const K, V>, N>;
+ using Map = SmallVector<std::pair<const K, V>, N>;
-public:
- using key_type = K;
- using mapped_type = V;
+ 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 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 reference = typename Map::reference;
+ using iterator = typename Map::iterator;
- using const_reference = typename Map::const_reference;
- using const_iterator = typename Map::const_iterator;
+ using const_reference = typename Map::const_reference;
+ using const_iterator = typename Map::const_iterator;
- // Creates an empty map.
- SmallMap() = default;
+ // 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, std::size_t... Sizes, typename... Types>
- SmallMap(InitializerList<U, std::index_sequence<Sizes...>, Types...>&& list)
- : map_(std::move(list)) {
- // TODO: Enforce unique keys.
- }
+ // 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, std::size_t... Sizes, typename... Types>
+ SmallMap(InitializerList<U, std::index_sequence<Sizes...>, Types...>&& list)
+ : map_(std::move(list)) {
+ // TODO: Enforce unique keys.
+ }
- size_type max_size() const { return map_.max_size(); }
- size_type size() const { return map_.size(); }
- bool empty() const { return map_.empty(); }
+ size_type max_size() const { return map_.max_size(); }
+ size_type size() const { return map_.size(); }
+ bool empty() const { return map_.empty(); }
- // Returns whether the map is backed by static or dynamic storage.
- bool dynamic() const { return map_.dynamic(); }
+ // Returns whether the map is backed by static or dynamic storage.
+ bool dynamic() const { return map_.dynamic(); }
- iterator begin() { return map_.begin(); }
- const_iterator begin() const { return cbegin(); }
- const_iterator cbegin() const { return map_.cbegin(); }
+ iterator begin() { return map_.begin(); }
+ const_iterator begin() const { return cbegin(); }
+ const_iterator cbegin() const { return map_.cbegin(); }
- iterator end() { return map_.end(); }
- const_iterator end() const { return cend(); }
- const_iterator cend() const { return map_.cend(); }
+ iterator end() { return map_.end(); }
+ const_iterator end() const { return cend(); }
+ const_iterator cend() const { return map_.cend(); }
- // Returns whether a mapping exists for the given key.
- bool contains(const key_type& key) const {
- return find(key, [](const mapped_type&) {});
- }
+ // 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); });
- }
+ // 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); });
- }
+ 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);
- }
- }
+ // 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));
- });
- }
+ return {};
+ }
-private:
- Map map_;
+ 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 map_;
};
// Deduction guide for in-place constructor.
template <typename K, typename V, std::size_t... Sizes, typename... Types>
SmallMap(InitializerList<KeyValue<K, V>, std::index_sequence<Sizes...>, Types...>&&)
- -> SmallMap<K, V, sizeof...(Sizes)>;
+ -> SmallMap<K, V, sizeof...(Sizes)>;
// Returns whether the key-value pairs of two maps are equal.
template <typename K, typename V, std::size_t N, typename Q, typename W, std::size_t M>
bool operator==(const SmallMap<K, V, N>& lhs, const SmallMap<Q, W, M>& rhs) {
- if (lhs.size() != rhs.size()) return false;
+ 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;
- }
+ 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;
+ return true;
}
// TODO: Remove in C++20.
template <typename K, typename V, std::size_t N, typename Q, typename W, std::size_t M>
inline bool operator!=(const SmallMap<K, V, N>& lhs, const SmallMap<Q, W, M>& rhs) {
- return !(lhs == rhs);
+ return !(lhs == rhs);
}
-} // namespace android::ftl
+} // namespace android::ftl
diff --git a/include/ftl/small_vector.h b/include/ftl/small_vector.h
index a8686ba..cb0ae35 100644
--- a/include/ftl/small_vector.h
+++ b/include/ftl/small_vector.h
@@ -41,231 +41,227 @@
//
// Example usage:
//
-// ftl::SmallVector<char, 3> vector;
-// assert(vector.empty());
-// assert(!vector.dynamic());
+// ftl::SmallVector<char, 3> vector;
+// assert(vector.empty());
+// assert(!vector.dynamic());
//
-// vector = {'a', 'b', 'c'};
-// assert(vector.size() == 3u);
-// assert(!vector.dynamic());
+// vector = {'a', 'b', 'c'};
+// assert(vector.size() == 3u);
+// assert(!vector.dynamic());
//
-// vector.push_back('d');
-// assert(vector.dynamic());
+// vector.push_back('d');
+// assert(vector.dynamic());
//
-// vector.unstable_erase(vector.begin());
-// assert(vector == (ftl::SmallVector{'d', 'b', 'c'}));
+// vector.unstable_erase(vector.begin());
+// assert(vector == (ftl::SmallVector{'d', 'b', 'c'}));
//
-// vector.pop_back();
-// assert(vector.back() == 'b');
-// assert(vector.dynamic());
+// vector.pop_back();
+// assert(vector.back() == 'b');
+// assert(vector.dynamic());
//
-// const char array[] = "hi";
-// vector = ftl::SmallVector(array);
-// assert(vector == (ftl::SmallVector{'h', 'i', '\0'}));
-// assert(!vector.dynamic());
+// const char array[] = "hi";
+// vector = ftl::SmallVector(array);
+// 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());
+// 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] == "???");
+// assert(strings[0] == "abc");
+// assert(strings[1] == "123");
+// assert(strings[2] == "???");
//
template <typename T, std::size_t N>
class SmallVector final : ArrayTraits<T>, ArrayComparators<SmallVector> {
- using Static = StaticVector<T, N>;
- using Dynamic = SmallVector<T, 0>;
+ using Static = StaticVector<T, N>;
+ using Dynamic = SmallVector<T, 0>;
- // TODO: Replace with std::remove_cvref_t in C++20.
- template <typename U>
- using remove_cvref_t = std::remove_cv_t<std::remove_reference_t<U>>;
+ // TODO: Replace with std::remove_cvref_t in C++20.
+ template <typename U>
+ using remove_cvref_t = std::remove_cv_t<std::remove_reference_t<U>>;
-public:
- FTL_ARRAY_TRAIT(T, value_type);
- FTL_ARRAY_TRAIT(T, size_type);
- FTL_ARRAY_TRAIT(T, difference_type);
+ public:
+ FTL_ARRAY_TRAIT(T, value_type);
+ FTL_ARRAY_TRAIT(T, size_type);
+ FTL_ARRAY_TRAIT(T, difference_type);
- FTL_ARRAY_TRAIT(T, pointer);
- FTL_ARRAY_TRAIT(T, reference);
- FTL_ARRAY_TRAIT(T, iterator);
- FTL_ARRAY_TRAIT(T, reverse_iterator);
+ FTL_ARRAY_TRAIT(T, pointer);
+ FTL_ARRAY_TRAIT(T, reference);
+ FTL_ARRAY_TRAIT(T, iterator);
+ FTL_ARRAY_TRAIT(T, reverse_iterator);
- FTL_ARRAY_TRAIT(T, const_pointer);
- FTL_ARRAY_TRAIT(T, const_reference);
- FTL_ARRAY_TRAIT(T, const_iterator);
- FTL_ARRAY_TRAIT(T, const_reverse_iterator);
+ FTL_ARRAY_TRAIT(T, const_pointer);
+ FTL_ARRAY_TRAIT(T, const_reference);
+ FTL_ARRAY_TRAIT(T, const_iterator);
+ FTL_ARRAY_TRAIT(T, const_reverse_iterator);
- // Creates an empty vector.
- SmallVector() = default;
+ // Creates an empty vector.
+ SmallVector() = default;
- // Constructs at most N elements. See StaticVector for underlying constructors.
- template <typename Arg, typename... Args,
- typename = std::enable_if_t<!is_small_vector<remove_cvref_t<Arg>>{}>>
- SmallVector(Arg&& arg, Args&&... args)
- : vector_(std::in_place_type<Static>, std::forward<Arg>(arg),
- std::forward<Args>(args)...) {}
+ // Constructs at most N elements. See StaticVector for underlying constructors.
+ template <typename Arg, typename... Args,
+ typename = std::enable_if_t<!is_small_vector<remove_cvref_t<Arg>>{}>>
+ SmallVector(Arg&& arg, Args&&... args)
+ : vector_(std::in_place_type<Static>, std::forward<Arg>(arg), std::forward<Args>(args)...) {}
- // Copies at most N elements from a smaller convertible vector.
- template <typename U, std::size_t M, typename = std::enable_if_t<M <= N>>
- SmallVector(const SmallVector<U, M>& other)
- : SmallVector(kIteratorRange, other.begin(), other.end()) {}
+ // Copies at most N elements from a smaller convertible vector.
+ template <typename U, std::size_t M, typename = std::enable_if_t<M <= N>>
+ SmallVector(const SmallVector<U, M>& other)
+ : SmallVector(kIteratorRange, other.begin(), other.end()) {}
- void swap(SmallVector& other) { vector_.swap(other.vector_); }
+ void swap(SmallVector& other) { vector_.swap(other.vector_); }
- // Returns whether the vector is backed by static or dynamic storage.
- bool dynamic() const { return std::holds_alternative<Dynamic>(vector_); }
+ // Returns whether the vector is backed by static or dynamic storage.
+ bool dynamic() const { return std::holds_alternative<Dynamic>(vector_); }
- // Avoid std::visit as it generates a dispatch table.
-#define DISPATCH(T, F, ...) \
- T F() __VA_ARGS__ { \
- return dynamic() ? std::get<Dynamic>(vector_).F() : std::get<Static>(vector_).F(); \
- }
+ // Avoid std::visit as it generates a dispatch table.
+#define DISPATCH(T, F, ...) \
+ T F() __VA_ARGS__ { \
+ return dynamic() ? std::get<Dynamic>(vector_).F() : std::get<Static>(vector_).F(); \
+ }
- DISPATCH(size_type, max_size, const)
- DISPATCH(size_type, size, const)
- DISPATCH(bool, empty, const)
+ DISPATCH(size_type, max_size, const)
+ DISPATCH(size_type, size, const)
+ DISPATCH(bool, empty, const)
- // noexcept to suppress warning about zero variadic macro arguments.
- DISPATCH(iterator, begin, noexcept)
- DISPATCH(const_iterator, begin, const)
- DISPATCH(const_iterator, cbegin, const)
+ // noexcept to suppress warning about zero variadic macro arguments.
+ DISPATCH(iterator, begin, noexcept)
+ DISPATCH(const_iterator, begin, const)
+ DISPATCH(const_iterator, cbegin, const)
- DISPATCH(iterator, end, noexcept)
- DISPATCH(const_iterator, end, const)
- DISPATCH(const_iterator, cend, const)
+ DISPATCH(iterator, end, noexcept)
+ DISPATCH(const_iterator, end, const)
+ DISPATCH(const_iterator, cend, const)
- DISPATCH(reverse_iterator, rbegin, noexcept)
- DISPATCH(const_reverse_iterator, rbegin, const)
- DISPATCH(const_reverse_iterator, crbegin, const)
+ DISPATCH(reverse_iterator, rbegin, noexcept)
+ DISPATCH(const_reverse_iterator, rbegin, const)
+ DISPATCH(const_reverse_iterator, crbegin, const)
- DISPATCH(reverse_iterator, rend, noexcept)
- DISPATCH(const_reverse_iterator, rend, const)
- DISPATCH(const_reverse_iterator, crend, const)
+ DISPATCH(reverse_iterator, rend, noexcept)
+ DISPATCH(const_reverse_iterator, rend, const)
+ DISPATCH(const_reverse_iterator, crend, const)
- DISPATCH(iterator, last, noexcept)
- DISPATCH(const_iterator, last, const)
+ DISPATCH(iterator, last, noexcept)
+ DISPATCH(const_iterator, last, const)
- DISPATCH(reference, front, noexcept)
- DISPATCH(const_reference, front, const)
+ DISPATCH(reference, front, noexcept)
+ DISPATCH(const_reference, front, const)
- DISPATCH(reference, back, noexcept)
- DISPATCH(const_reference, back, const)
+ DISPATCH(reference, back, noexcept)
+ DISPATCH(const_reference, back, const)
#undef DISPATCH
- reference operator[](size_type i) {
- return dynamic() ? std::get<Dynamic>(vector_)[i] : std::get<Static>(vector_)[i];
+ reference operator[](size_type i) {
+ return dynamic() ? std::get<Dynamic>(vector_)[i] : std::get<Static>(vector_)[i];
+ }
+
+ const_reference operator[](size_type i) const { return const_cast<SmallVector&>(*this)[i]; }
+
+ // Replaces an element, and returns a reference to it. The iterator must be dereferenceable, so
+ // replacing at end() is erroneous.
+ //
+ // The element is emplaced via move constructor, so type T does not need to define copy/move
+ // assignment, e.g. its data members may be const.
+ //
+ // The arguments may directly or indirectly refer to the element being replaced.
+ //
+ // Iterators to the replaced element point to its replacement, and others remain valid.
+ //
+ template <typename... Args>
+ reference replace(const_iterator it, Args&&... args) {
+ if (dynamic()) {
+ return std::get<Dynamic>(vector_).replace(it, std::forward<Args>(args)...);
+ } else {
+ return std::get<Static>(vector_).replace(it, std::forward<Args>(args)...);
+ }
+ }
+
+ // Appends an element, and returns a reference to it.
+ //
+ // If the vector reaches its static or dynamic capacity, then all iterators are invalidated.
+ // Otherwise, only the end() iterator is invalidated.
+ //
+ template <typename... Args>
+ reference emplace_back(Args&&... args) {
+ constexpr auto kInsertStatic = &Static::template emplace_back<Args...>;
+ constexpr auto kInsertDynamic = &Dynamic::template emplace_back<Args...>;
+ return *insert<kInsertStatic, kInsertDynamic>(std::forward<Args>(args)...);
+ }
+
+ // Appends an element.
+ //
+ // If the vector reaches its static or dynamic capacity, then all iterators are invalidated.
+ // Otherwise, only the end() iterator is invalidated.
+ //
+ void push_back(const value_type& v) {
+ constexpr auto kInsertStatic =
+ static_cast<bool (Static::*)(const value_type&)>(&Static::push_back);
+ constexpr auto kInsertDynamic =
+ static_cast<bool (Dynamic::*)(const value_type&)>(&Dynamic::push_back);
+ insert<kInsertStatic, kInsertDynamic>(v);
+ }
+
+ void push_back(value_type&& v) {
+ constexpr auto kInsertStatic = static_cast<bool (Static::*)(value_type &&)>(&Static::push_back);
+ constexpr auto kInsertDynamic =
+ static_cast<bool (Dynamic::*)(value_type &&)>(&Dynamic::push_back);
+ insert<kInsertStatic, kInsertDynamic>(std::move(v));
+ }
+
+ // Removes the last element. The vector must not be empty, or the call is erroneous.
+ //
+ // The last() and end() iterators are invalidated.
+ //
+ void pop_back() {
+ if (dynamic()) {
+ std::get<Dynamic>(vector_).pop_back();
+ } else {
+ std::get<Static>(vector_).pop_back();
+ }
+ }
+
+ // 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.
+ //
+ // The last() and end() iterators, as well as those to the erased element, are invalidated.
+ //
+ void unstable_erase(iterator it) {
+ if (dynamic()) {
+ std::get<Dynamic>(vector_).unstable_erase(it);
+ } else {
+ std::get<Static>(vector_).unstable_erase(it);
+ }
+ }
+
+ private:
+ template <auto InsertStatic, auto InsertDynamic, typename... Args>
+ auto insert(Args&&... args) {
+ if (Dynamic* const vector = std::get_if<Dynamic>(&vector_)) {
+ return (vector->*InsertDynamic)(std::forward<Args>(args)...);
}
- const_reference operator[](size_type i) const { return const_cast<SmallVector&>(*this)[i]; }
-
- // Replaces an element, and returns a reference to it. The iterator must be dereferenceable, so
- // replacing at end() is erroneous.
- //
- // The element is emplaced via move constructor, so type T does not need to define copy/move
- // assignment, e.g. its data members may be const.
- //
- // The arguments may directly or indirectly refer to the element being replaced.
- //
- // Iterators to the replaced element point to its replacement, and others remain valid.
- //
- template <typename... Args>
- reference replace(const_iterator it, Args&&... args) {
- if (dynamic()) {
- return std::get<Dynamic>(vector_).replace(it, std::forward<Args>(args)...);
- } else {
- return std::get<Static>(vector_).replace(it, std::forward<Args>(args)...);
- }
+ auto& vector = std::get<Static>(vector_);
+ if (vector.full()) {
+ return (promote(vector).*InsertDynamic)(std::forward<Args>(args)...);
+ } else {
+ return (vector.*InsertStatic)(std::forward<Args>(args)...);
}
+ }
- // Appends an element, and returns a reference to it.
- //
- // If the vector reaches its static or dynamic capacity, then all iterators are invalidated.
- // Otherwise, only the end() iterator is invalidated.
- //
- template <typename... Args>
- reference emplace_back(Args&&... args) {
- constexpr auto kInsertStatic = &Static::template emplace_back<Args...>;
- constexpr auto kInsertDynamic = &Dynamic::template emplace_back<Args...>;
- return *insert<kInsertStatic, kInsertDynamic>(std::forward<Args>(args)...);
- }
+ Dynamic& promote(Static& static_vector) {
+ assert(static_vector.full());
- // Appends an element.
- //
- // If the vector reaches its static or dynamic capacity, then all iterators are invalidated.
- // Otherwise, only the end() iterator is invalidated.
- //
- void push_back(const value_type& v) {
- constexpr auto kInsertStatic =
- static_cast<bool (Static::*)(const value_type&)>(&Static::push_back);
- constexpr auto kInsertDynamic =
- static_cast<bool (Dynamic::*)(const value_type&)>(&Dynamic::push_back);
- insert<kInsertStatic, kInsertDynamic>(v);
- }
+ // Allocate double capacity to reduce probability of reallocation.
+ Dynamic vector;
+ vector.reserve(Static::max_size() * 2);
+ std::move(static_vector.begin(), static_vector.end(), std::back_inserter(vector));
- void push_back(value_type&& v) {
- constexpr auto kInsertStatic =
- static_cast<bool (Static::*)(value_type&&)>(&Static::push_back);
- constexpr auto kInsertDynamic =
- static_cast<bool (Dynamic::*)(value_type&&)>(&Dynamic::push_back);
- insert<kInsertStatic, kInsertDynamic>(std::move(v));
- }
+ return vector_.template emplace<Dynamic>(std::move(vector));
+ }
- // Removes the last element. The vector must not be empty, or the call is erroneous.
- //
- // The last() and end() iterators are invalidated.
- //
- void pop_back() {
- if (dynamic()) {
- std::get<Dynamic>(vector_).pop_back();
- } else {
- std::get<Static>(vector_).pop_back();
- }
- }
-
- // 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.
- //
- // The last() and end() iterators, as well as those to the erased element, are invalidated.
- //
- void unstable_erase(iterator it) {
- if (dynamic()) {
- std::get<Dynamic>(vector_).unstable_erase(it);
- } else {
- std::get<Static>(vector_).unstable_erase(it);
- }
- }
-
-private:
- template <auto InsertStatic, auto InsertDynamic, typename... Args>
- auto insert(Args&&... args) {
- if (Dynamic* const vector = std::get_if<Dynamic>(&vector_)) {
- return (vector->*InsertDynamic)(std::forward<Args>(args)...);
- }
-
- auto& vector = std::get<Static>(vector_);
- if (vector.full()) {
- return (promote(vector).*InsertDynamic)(std::forward<Args>(args)...);
- } else {
- return (vector.*InsertStatic)(std::forward<Args>(args)...);
- }
- }
-
- Dynamic& promote(Static& static_vector) {
- assert(static_vector.full());
-
- // Allocate double capacity to reduce probability of reallocation.
- Dynamic vector;
- vector.reserve(Static::max_size() * 2);
- std::move(static_vector.begin(), static_vector.end(), std::back_inserter(vector));
-
- return vector_.template emplace<Dynamic>(std::move(vector));
- }
-
- std::variant<Static, Dynamic> vector_;
+ std::variant<Static, Dynamic> vector_;
};
// Partial specialization without static storage.
@@ -273,90 +269,90 @@
class SmallVector<T, 0> final : ArrayTraits<T>,
ArrayIterators<SmallVector<T, 0>, T>,
std::vector<T> {
- using ArrayTraits<T>::construct_at;
+ using ArrayTraits<T>::construct_at;
- using Iter = ArrayIterators<SmallVector, T>;
- using Impl = std::vector<T>;
+ using Iter = ArrayIterators<SmallVector, T>;
+ using Impl = std::vector<T>;
- friend Iter;
+ friend Iter;
-public:
- FTL_ARRAY_TRAIT(T, value_type);
- FTL_ARRAY_TRAIT(T, size_type);
- FTL_ARRAY_TRAIT(T, difference_type);
+ public:
+ FTL_ARRAY_TRAIT(T, value_type);
+ FTL_ARRAY_TRAIT(T, size_type);
+ FTL_ARRAY_TRAIT(T, difference_type);
- FTL_ARRAY_TRAIT(T, pointer);
- FTL_ARRAY_TRAIT(T, reference);
- FTL_ARRAY_TRAIT(T, iterator);
- FTL_ARRAY_TRAIT(T, reverse_iterator);
+ FTL_ARRAY_TRAIT(T, pointer);
+ FTL_ARRAY_TRAIT(T, reference);
+ FTL_ARRAY_TRAIT(T, iterator);
+ FTL_ARRAY_TRAIT(T, reverse_iterator);
- FTL_ARRAY_TRAIT(T, const_pointer);
- FTL_ARRAY_TRAIT(T, const_reference);
- FTL_ARRAY_TRAIT(T, const_iterator);
- FTL_ARRAY_TRAIT(T, const_reverse_iterator);
+ FTL_ARRAY_TRAIT(T, const_pointer);
+ FTL_ARRAY_TRAIT(T, const_reference);
+ FTL_ARRAY_TRAIT(T, const_iterator);
+ FTL_ARRAY_TRAIT(T, const_reverse_iterator);
- using Impl::Impl;
+ using Impl::Impl;
- using Impl::empty;
- using Impl::max_size;
- using Impl::size;
+ using Impl::empty;
+ using Impl::max_size;
+ using Impl::size;
- using Impl::reserve;
+ using Impl::reserve;
- // std::vector iterators are not necessarily raw pointers.
- iterator begin() { return Impl::data(); }
- iterator end() { return Impl::data() + size(); }
+ // std::vector iterators are not necessarily raw pointers.
+ iterator begin() { return Impl::data(); }
+ iterator end() { return Impl::data() + size(); }
- using Iter::begin;
- using Iter::end;
+ using Iter::begin;
+ using Iter::end;
- using Iter::cbegin;
- using Iter::cend;
+ using Iter::cbegin;
+ using Iter::cend;
- using Iter::rbegin;
- using Iter::rend;
+ using Iter::rbegin;
+ using Iter::rend;
- using Iter::crbegin;
- using Iter::crend;
+ using Iter::crbegin;
+ using Iter::crend;
- using Iter::last;
+ using Iter::last;
- using Iter::back;
- using Iter::front;
+ using Iter::back;
+ using Iter::front;
- using Iter::operator[];
+ using Iter::operator[];
- template <typename... Args>
- reference replace(const_iterator it, Args&&... args) {
- value_type element{std::forward<Args>(args)...};
- std::destroy_at(it);
- // This is only safe because exceptions are disabled.
- return *construct_at(it, std::move(element));
- }
+ template <typename... Args>
+ reference replace(const_iterator it, Args&&... args) {
+ value_type element{std::forward<Args>(args)...};
+ std::destroy_at(it);
+ // This is only safe because exceptions are disabled.
+ return *construct_at(it, std::move(element));
+ }
- template <typename... Args>
- iterator emplace_back(Args&&... args) {
- return &Impl::emplace_back(std::forward<Args>(args)...);
- }
+ template <typename... Args>
+ iterator emplace_back(Args&&... args) {
+ return &Impl::emplace_back(std::forward<Args>(args)...);
+ }
- bool push_back(const value_type& v) {
- Impl::push_back(v);
- return true;
- }
+ bool push_back(const value_type& v) {
+ Impl::push_back(v);
+ return true;
+ }
- bool push_back(value_type&& v) {
- Impl::push_back(std::move(v));
- return true;
- }
+ bool push_back(value_type&& v) {
+ Impl::push_back(std::move(v));
+ return true;
+ }
- using Impl::pop_back;
+ using Impl::pop_back;
- void unstable_erase(iterator it) {
- if (it != last()) std::iter_swap(it, last());
- pop_back();
- }
+ void unstable_erase(iterator it) {
+ if (it != last()) std::iter_swap(it, last());
+ pop_back();
+ }
- void swap(SmallVector& other) { Impl::swap(other); }
+ void swap(SmallVector& other) { Impl::swap(other); }
};
template <typename>
@@ -377,7 +373,7 @@
// Deduction guide for in-place constructor.
template <typename T, std::size_t... Sizes, typename... Types>
SmallVector(InitializerList<T, std::index_sequence<Sizes...>, Types...>&&)
- -> SmallVector<T, sizeof...(Sizes)>;
+ -> SmallVector<T, sizeof...(Sizes)>;
// Deduction guide for StaticVector conversion.
template <typename T, std::size_t N>
@@ -385,7 +381,7 @@
template <typename T, std::size_t N>
inline void swap(SmallVector<T, N>& lhs, SmallVector<T, N>& rhs) {
- lhs.swap(rhs);
+ lhs.swap(rhs);
}
-} // namespace android::ftl
+} // namespace android::ftl
diff --git a/include/ftl/static_vector.h b/include/ftl/static_vector.h
index 5012175..96a1ae8 100644
--- a/include/ftl/static_vector.h
+++ b/include/ftl/static_vector.h
@@ -28,7 +28,8 @@
namespace android::ftl {
-constexpr struct IteratorRangeTag {} kIteratorRange;
+constexpr struct IteratorRangeTag {
+} kIteratorRange;
// Fixed-capacity, statically allocated counterpart of std::vector. Like std::array, StaticVector
// allocates contiguous storage for N elements of type T at compile time, but stores at most (rather
@@ -43,302 +44,299 @@
//
// Example usage:
//
-// ftl::StaticVector<char, 3> vector;
-// assert(vector.empty());
+// ftl::StaticVector<char, 3> vector;
+// assert(vector.empty());
//
-// vector = {'a', 'b'};
-// assert(vector.size() == 2u);
+// vector = {'a', 'b'};
+// assert(vector.size() == 2u);
//
-// vector.push_back('c');
-// assert(vector.full());
+// vector.push_back('c');
+// assert(vector.full());
//
-// assert(!vector.push_back('d'));
-// assert(vector.size() == 3u);
+// assert(!vector.push_back('d'));
+// assert(vector.size() == 3u);
//
-// vector.unstable_erase(vector.begin());
-// assert(vector == (ftl::StaticVector{'c', 'b'}));
+// vector.unstable_erase(vector.begin());
+// assert(vector == (ftl::StaticVector{'c', 'b'}));
//
-// vector.pop_back();
-// assert(vector.back() == 'c');
+// vector.pop_back();
+// assert(vector.back() == 'c');
//
-// const char array[] = "hi";
-// vector = ftl::StaticVector(array);
-// assert(vector == (ftl::StaticVector{'h', 'i', '\0'}));
+// const char array[] = "hi";
+// 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] == "???");
+// 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, std::size_t N>
class StaticVector final : ArrayTraits<T>,
ArrayIterators<StaticVector<T, N>, T>,
ArrayComparators<StaticVector> {
- static_assert(N > 0);
+ static_assert(N > 0);
- using ArrayTraits<T>::construct_at;
+ using ArrayTraits<T>::construct_at;
- using Iter = ArrayIterators<StaticVector, T>;
- friend Iter;
+ using Iter = ArrayIterators<StaticVector, T>;
+ friend Iter;
- // There is ambiguity when constructing from two iterator-like elements like pointers:
- // they could be an iterator range, or arguments for in-place construction. Assume the
- // latter unless they are input iterators and cannot be used to construct elements. If
- // the former is intended, the caller can pass an IteratorRangeTag to disambiguate.
- template <typename I, typename Traits = std::iterator_traits<I>>
- using is_input_iterator = std::conjunction<
- std::is_base_of<std::input_iterator_tag, typename Traits::iterator_category>,
- std::negation<std::is_constructible<T, I>>>;
+ // There is ambiguity when constructing from two iterator-like elements like pointers:
+ // they could be an iterator range, or arguments for in-place construction. Assume the
+ // latter unless they are input iterators and cannot be used to construct elements. If
+ // the former is intended, the caller can pass an IteratorRangeTag to disambiguate.
+ template <typename I, typename Traits = std::iterator_traits<I>>
+ using is_input_iterator =
+ std::conjunction<std::is_base_of<std::input_iterator_tag, typename Traits::iterator_category>,
+ std::negation<std::is_constructible<T, I>>>;
-public:
- FTL_ARRAY_TRAIT(T, value_type);
- FTL_ARRAY_TRAIT(T, size_type);
- FTL_ARRAY_TRAIT(T, difference_type);
+ public:
+ FTL_ARRAY_TRAIT(T, value_type);
+ FTL_ARRAY_TRAIT(T, size_type);
+ FTL_ARRAY_TRAIT(T, difference_type);
- FTL_ARRAY_TRAIT(T, pointer);
- FTL_ARRAY_TRAIT(T, reference);
- FTL_ARRAY_TRAIT(T, iterator);
- FTL_ARRAY_TRAIT(T, reverse_iterator);
+ FTL_ARRAY_TRAIT(T, pointer);
+ FTL_ARRAY_TRAIT(T, reference);
+ FTL_ARRAY_TRAIT(T, iterator);
+ FTL_ARRAY_TRAIT(T, reverse_iterator);
- FTL_ARRAY_TRAIT(T, const_pointer);
- FTL_ARRAY_TRAIT(T, const_reference);
- FTL_ARRAY_TRAIT(T, const_iterator);
- FTL_ARRAY_TRAIT(T, const_reverse_iterator);
+ FTL_ARRAY_TRAIT(T, const_pointer);
+ FTL_ARRAY_TRAIT(T, const_reference);
+ FTL_ARRAY_TRAIT(T, const_iterator);
+ FTL_ARRAY_TRAIT(T, const_reverse_iterator);
- // Creates an empty vector.
- StaticVector() = default;
+ // Creates an empty vector.
+ StaticVector() = default;
- // Copies and moves a vector, respectively.
- StaticVector(const StaticVector& other)
- : StaticVector(kIteratorRange, other.begin(), other.end()) {}
+ // Copies and moves a vector, respectively.
+ StaticVector(const StaticVector& other)
+ : StaticVector(kIteratorRange, other.begin(), other.end()) {}
- StaticVector(StaticVector&& other) { swap<true>(other); }
+ StaticVector(StaticVector&& other) { swap<true>(other); }
- // Copies at most N elements from a smaller convertible vector.
- template <typename U, std::size_t M, typename = std::enable_if_t<M <= N>>
- StaticVector(const StaticVector<U, M>& other)
- : StaticVector(kIteratorRange, other.begin(), other.end()) {}
+ // Copies at most N elements from a smaller convertible vector.
+ template <typename U, std::size_t M, typename = std::enable_if_t<M <= N>>
+ StaticVector(const StaticVector<U, M>& other)
+ : StaticVector(kIteratorRange, other.begin(), other.end()) {}
- // Copies at most N elements from an array.
- template <typename U, std::size_t M>
- explicit StaticVector(U (&array)[M])
- : StaticVector(kIteratorRange, std::begin(array), std::end(array)) {}
+ // Copies at most N elements from an array.
+ template <typename U, std::size_t M>
+ explicit StaticVector(U (&array)[M])
+ : StaticVector(kIteratorRange, std::begin(array), std::end(array)) {}
- // Copies at most N elements from the range [first, last).
- //
- // IteratorRangeTag disambiguates with initialization from two iterator-like elements.
- //
- template <typename Iterator, typename = std::enable_if_t<is_input_iterator<Iterator>{}>>
- StaticVector(Iterator first, Iterator last) : StaticVector(kIteratorRange, first, last) {
- using V = typename std::iterator_traits<Iterator>::value_type;
- static_assert(std::is_constructible_v<value_type, V>, "Incompatible iterator range");
+ // Copies at most N elements from the range [first, last).
+ //
+ // IteratorRangeTag disambiguates with initialization from two iterator-like elements.
+ //
+ template <typename Iterator, typename = std::enable_if_t<is_input_iterator<Iterator>{}>>
+ StaticVector(Iterator first, Iterator last) : StaticVector(kIteratorRange, first, last) {
+ using V = typename std::iterator_traits<Iterator>::value_type;
+ static_assert(std::is_constructible_v<value_type, V>, "Incompatible iterator range");
+ }
+
+ template <typename Iterator>
+ StaticVector(IteratorRangeTag, Iterator first, Iterator last)
+ : size_(std::min(max_size(), static_cast<size_type>(std::distance(first, last)))) {
+ std::uninitialized_copy(first, first + size_, 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 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 = 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 U, std::size_t Size, std::size_t... Sizes, typename... Types>
+ StaticVector(InitializerList<U, std::index_sequence<Size, Sizes...>, Types...>&& list)
+ : StaticVector(std::index_sequence<0, 0, Size>{}, std::make_index_sequence<Size>{},
+ std::index_sequence<Sizes...>{}, list.tuple) {}
+
+ ~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());
+ size_ = 0;
+ swap<true>(other);
+ return *this;
+ }
+
+ // IsEmpty enables a fast path when the vector is known to be empty at compile time.
+ template <bool IsEmpty = false>
+ void swap(StaticVector&);
+
+ static constexpr size_type max_size() { return N; }
+ size_type size() const { return size_; }
+
+ bool empty() const { return size() == 0; }
+ bool full() const { return size() == max_size(); }
+
+ iterator begin() { return std::launder(reinterpret_cast<pointer>(data_)); }
+ iterator end() { return begin() + size(); }
+
+ using Iter::begin;
+ using Iter::end;
+
+ using Iter::cbegin;
+ using Iter::cend;
+
+ using Iter::rbegin;
+ using Iter::rend;
+
+ using Iter::crbegin;
+ using Iter::crend;
+
+ using Iter::last;
+
+ using Iter::back;
+ using Iter::front;
+
+ using Iter::operator[];
+
+ // Replaces an element, and returns a reference to it. The iterator must be dereferenceable, so
+ // replacing at end() is erroneous.
+ //
+ // The element is emplaced via move constructor, so type T does not need to define copy/move
+ // assignment, e.g. its data members may be const.
+ //
+ // The arguments may directly or indirectly refer to the element being replaced.
+ //
+ // Iterators to the replaced element point to its replacement, and others remain valid.
+ //
+ template <typename... Args>
+ reference replace(const_iterator it, Args&&... args) {
+ value_type element{std::forward<Args>(args)...};
+ std::destroy_at(it);
+ // This is only safe because exceptions are disabled.
+ return *construct_at(it, std::move(element));
+ }
+
+ // 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.
+ //
+ // On success, the end() iterator is invalidated.
+ //
+ template <typename... Args>
+ iterator emplace_back(Args&&... args) {
+ if (full()) return end();
+ const iterator it = construct_at(end(), std::forward<Args>(args)...);
+ ++size_;
+ return it;
+ }
+
+ // Appends an element unless the vector is full, and returns whether the element was inserted.
+ //
+ // On success, the end() iterator is invalidated.
+ //
+ bool push_back(const value_type& v) {
+ // Two statements for sequence point.
+ const iterator it = emplace_back(v);
+ return it != end();
+ }
+
+ bool push_back(value_type&& v) {
+ // Two statements for sequence point.
+ const iterator it = emplace_back(std::move(v));
+ return it != end();
+ }
+
+ // Removes the last element. The vector must not be empty, or the call is erroneous.
+ //
+ // The last() and end() iterators are invalidated.
+ //
+ void pop_back() { unstable_erase(last()); }
+
+ // 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.
+ //
+ // The last() and end() iterators, as well as those to the erased element, are invalidated.
+ //
+ void unstable_erase(const_iterator it) {
+ std::destroy_at(it);
+ if (it != last()) {
+ // Move last element and destroy its source for destructor side effects. This is only
+ // safe because exceptions are disabled.
+ construct_at(it, std::move(back()));
+ std::destroy_at(last());
}
+ --size_;
+ }
- template <typename Iterator>
- StaticVector(IteratorRangeTag, Iterator first, Iterator last)
- : size_(std::min(max_size(), static_cast<size_type>(std::distance(first, last)))) {
- std::uninitialized_copy(first, first + size_, begin());
- }
+ private:
+ // Recursion for variadic constructor.
+ template <std::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));
+ }
- // 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");
- }
+ // Base case for variadic constructor.
+ template <std::size_t I>
+ explicit StaticVector(std::index_sequence<I>) : size_(I) {}
- // 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 = 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 U, std::size_t Size, std::size_t... Sizes, typename... Types>
- StaticVector(InitializerList<U, std::index_sequence<Size, Sizes...>, Types...>&& list)
- : StaticVector(std::index_sequence<0, 0, Size>{}, std::make_index_sequence<Size>{},
- std::index_sequence<Sizes...>{}, list.tuple) {}
+ // 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 <std::size_t I, std::size_t ArgIndex, std::size_t ArgCount, std::size_t... Indices,
+ std::size_t Size, std::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))...);
+ }
- ~StaticVector() { std::destroy(begin(), end()); }
+ // Base case for in-place constructor.
+ template <std::size_t I, std::size_t ArgIndex, std::size_t ArgCount, std::size_t... Indices,
+ typename... Args>
+ StaticVector(std::index_sequence<I, ArgIndex, ArgCount>, std::index_sequence<Indices...>,
+ std::index_sequence<>, std::tuple<Args...>& tuple)
+ : size_(I + 1) {
+ construct_at(begin() + I, std::move(std::get<ArgIndex + Indices>(tuple))...);
+ }
- StaticVector& operator=(const StaticVector& other) {
- StaticVector copy(other);
- swap(copy);
- return *this;
- }
-
- StaticVector& operator=(StaticVector&& other) {
- std::destroy(begin(), end());
- size_ = 0;
- swap<true>(other);
- return *this;
- }
-
- // IsEmpty enables a fast path when the vector is known to be empty at compile time.
- template <bool IsEmpty = false>
- void swap(StaticVector&);
-
- static constexpr size_type max_size() { return N; }
- size_type size() const { return size_; }
-
- bool empty() const { return size() == 0; }
- bool full() const { return size() == max_size(); }
-
- iterator begin() { return std::launder(reinterpret_cast<pointer>(data_)); }
- iterator end() { return begin() + size(); }
-
- using Iter::begin;
- using Iter::end;
-
- using Iter::cbegin;
- using Iter::cend;
-
- using Iter::rbegin;
- using Iter::rend;
-
- using Iter::crbegin;
- using Iter::crend;
-
- using Iter::last;
-
- using Iter::back;
- using Iter::front;
-
- using Iter::operator[];
-
- // Replaces an element, and returns a reference to it. The iterator must be dereferenceable, so
- // replacing at end() is erroneous.
- //
- // The element is emplaced via move constructor, so type T does not need to define copy/move
- // assignment, e.g. its data members may be const.
- //
- // The arguments may directly or indirectly refer to the element being replaced.
- //
- // Iterators to the replaced element point to its replacement, and others remain valid.
- //
- template <typename... Args>
- reference replace(const_iterator it, Args&&... args) {
- value_type element{std::forward<Args>(args)...};
- std::destroy_at(it);
- // This is only safe because exceptions are disabled.
- return *construct_at(it, std::move(element));
- }
-
- // 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.
- //
- // On success, the end() iterator is invalidated.
- //
- template <typename... Args>
- iterator emplace_back(Args&&... args) {
- if (full()) return end();
- const iterator it = construct_at(end(), std::forward<Args>(args)...);
- ++size_;
- return it;
- }
-
- // Appends an element unless the vector is full, and returns whether the element was inserted.
- //
- // On success, the end() iterator is invalidated.
- //
- bool push_back(const value_type& v) {
- // Two statements for sequence point.
- const iterator it = emplace_back(v);
- return it != end();
- }
-
- bool push_back(value_type&& v) {
- // Two statements for sequence point.
- const iterator it = emplace_back(std::move(v));
- return it != end();
- }
-
- // Removes the last element. The vector must not be empty, or the call is erroneous.
- //
- // The last() and end() iterators are invalidated.
- //
- void pop_back() { unstable_erase(last()); }
-
- // 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.
- //
- // The last() and end() iterators, as well as those to the erased element, are invalidated.
- //
- void unstable_erase(const_iterator it) {
- std::destroy_at(it);
- if (it != last()) {
- // Move last element and destroy its source for destructor side effects. This is only
- // safe because exceptions are disabled.
- construct_at(it, std::move(back()));
- std::destroy_at(last());
- }
- --size_;
- }
-
-private:
- // Recursion for variadic constructor.
- template <std::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 <std::size_t I>
- explicit StaticVector(std::index_sequence<I>) : size_(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 <std::size_t I, std::size_t ArgIndex, std::size_t ArgCount, std::size_t... Indices,
- std::size_t Size, std::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 <std::size_t I, std::size_t ArgIndex, std::size_t ArgCount, std::size_t... Indices,
- typename... Args>
- StaticVector(std::index_sequence<I, ArgIndex, ArgCount>, std::index_sequence<Indices...>,
- std::index_sequence<>, std::tuple<Args...>& tuple)
- : size_(I + 1) {
- construct_at(begin() + I, std::move(std::get<ArgIndex + Indices>(tuple))...);
- }
-
- size_type size_ = 0;
- std::aligned_storage_t<sizeof(value_type), alignof(value_type)> data_[N];
+ size_type size_ = 0;
+ std::aligned_storage_t<sizeof(value_type), alignof(value_type)> data_[N];
};
// Deduction guide for array constructor.
@@ -353,44 +351,44 @@
// Deduction guide for in-place constructor.
template <typename T, std::size_t... Sizes, typename... Types>
StaticVector(InitializerList<T, std::index_sequence<Sizes...>, Types...>&&)
- -> StaticVector<T, sizeof...(Sizes)>;
+ -> StaticVector<T, sizeof...(Sizes)>;
template <typename T, std::size_t N>
template <bool IsEmpty>
void StaticVector<T, N>::swap(StaticVector& other) {
- auto [to, from] = std::make_pair(this, &other);
- if (from == this) return;
+ 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());
+ // 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 (IsEmpty) {
- 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;
+ // No elements to swap if moving into an empty vector.
+ if constexpr (IsEmpty) {
+ assert(min == 0);
+ } else {
+ if (min > max) {
+ std::swap(from, to);
+ std::swap(min, max);
}
- // 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);
+ // Swap elements [0, min).
+ std::swap_ranges(begin(), begin() + min, other.begin());
- std::swap(size_, other.size_);
+ // 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(size_, other.size_);
}
template <typename T, std::size_t N>
inline void swap(StaticVector<T, N>& lhs, StaticVector<T, N>& rhs) {
- lhs.swap(rhs);
+ lhs.swap(rhs);
}
-} // namespace android::ftl
+} // namespace android::ftl