diff options
Diffstat (limited to 'include/ftl')
| l--------- | include/ftl/.clang-format | 1 | ||||
| -rw-r--r-- | include/ftl/array_traits.h | 135 | ||||
| -rw-r--r-- | include/ftl/future.h | 109 | ||||
| -rw-r--r-- | include/ftl/initializer_list.h | 108 | ||||
| -rw-r--r-- | include/ftl/small_map.h | 203 | ||||
| -rw-r--r-- | include/ftl/small_vector.h | 387 | ||||
| -rw-r--r-- | include/ftl/static_vector.h | 394 |
7 files changed, 0 insertions, 1337 deletions
diff --git a/include/ftl/.clang-format b/include/ftl/.clang-format deleted file mode 120000 index 86b159339f..0000000000 --- a/include/ftl/.clang-format +++ /dev/null @@ -1 +0,0 @@ -../../../../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 deleted file mode 100644 index 1265fa15fe..0000000000 --- a/include/ftl/array_traits.h +++ /dev/null @@ -1,135 +0,0 @@ -/* - * Copyright 2020 The Android Open Source Project - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#pragma once - -#include <algorithm> -#include <iterator> -#include <new> -#include <type_traits> - -#define FTL_ARRAY_TRAIT(T, U) using U = typename ArrayTraits<T>::U - -namespace android::ftl { - -template <typename T> -struct ArrayTraits { - 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 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)...}; - } - } -}; - -// 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, 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); - - 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(); } - - 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 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(); } - - reference front() { return *self().begin(); } - const_reference front() const { return self().front(); } - - 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]; } -}; - -// 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 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 !(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 diff --git a/include/ftl/future.h b/include/ftl/future.h deleted file mode 100644 index dd6358fa7d..0000000000 --- a/include/ftl/future.h +++ /dev/null @@ -1,109 +0,0 @@ -/* - * 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 <future> -#include <type_traits> -#include <utility> - -namespace android::ftl { - -// Creates a future that defers a function call until its result is queried. -// -// auto future = ftl::defer([](int x) { return x + 1; }, 99); -// assert(future.get() == 100); -// -template <typename F, typename... Args> -inline auto defer(F&& f, Args&&... args) { - return std::async(std::launch::deferred, std::forward<F>(f), std::forward<Args>(args)...); -} - -// Creates a future that wraps a value. -// -// auto future = ftl::yield(42); -// assert(future.get() == 42); -// -// auto ptr = std::make_unique<char>('!'); -// auto future = ftl::yield(std::move(ptr)); -// assert(*future.get() == '!'); -// -template <typename T> -inline std::future<T> yield(T&& v) { - return defer([](T&& v) { return std::forward<T>(v); }, std::forward<T>(v)); -} - -namespace details { - -template <typename T> -struct future_result { - using type = T; -}; - -template <typename T> -struct future_result<std::future<T>> { - using type = T; -}; - -template <typename T> -using future_result_t = typename future_result<T>::type; - -// Attaches a continuation to a future. The continuation is a function that maps T to either R or -// std::future<R>. In the former case, the chain wraps the result in a future as if by ftl::yield. -// -// auto future = ftl::yield(123); -// std::future<char> futures[] = {ftl::yield('a'), ftl::yield('b')}; -// -// std::future<char> chain = -// ftl::chain(std::move(future)) -// .then([](int x) { return static_cast<std::size_t>(x % 2); }) -// .then([&futures](std::size_t i) { return std::move(futures[i]); }); -// -// assert(chain.get() == 'b'); -// -template <typename T> -struct Chain { - // Implicit conversion. - Chain(std::future<T>&& f) : future(std::move(f)) {} - operator std::future<T>&&() && { return std::move(future); } - - T get() && { return future.get(); } - - template <typename F, typename R = std::invoke_result_t<F, T>> - auto then(F&& op) && -> Chain<future_result_t<R>> { - return defer( - [](auto&& f, F&& op) { - R r = op(f.get()); - if constexpr (std::is_same_v<R, future_result_t<R>>) { - return r; - } else { - return r.get(); - } - }, - std::move(future), std::forward<F>(op)); - } - - std::future<T> future; -}; - -} // namespace details - -template <typename T> -inline auto chain(std::future<T>&& f) -> details::Chain<T> { - return std::move(f); -} - -} // namespace android::ftl diff --git a/include/ftl/initializer_list.h b/include/ftl/initializer_list.h deleted file mode 100644 index 769c09ff11..0000000000 --- a/include/ftl/initializer_list.h +++ /dev/null @@ -1,108 +0,0 @@ -/* - * 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. -// -// An 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, 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)...))}; - } - - // 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, 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)...)))}; - } - - 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/small_map.h b/include/ftl/small_map.h deleted file mode 100644 index 84c15ebdca..0000000000 --- a/include/ftl/small_map.h +++ /dev/null @@ -1,203 +0,0 @@ -/* - * 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/initializer_list.h> -#include <ftl/small_vector.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, std::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, 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(); } - - // 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 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 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 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)>; - -// 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; - - 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, 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); -} - -} // namespace android::ftl diff --git a/include/ftl/small_vector.h b/include/ftl/small_vector.h deleted file mode 100644 index cb0ae359eb..0000000000 --- a/include/ftl/small_vector.h +++ /dev/null @@ -1,387 +0,0 @@ -/* - * 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/array_traits.h> -#include <ftl/static_vector.h> - -#include <algorithm> -#include <iterator> -#include <type_traits> -#include <utility> -#include <variant> -#include <vector> - -namespace android::ftl { - -template <typename> -struct is_small_vector; - -// ftl::StaticVector that promotes to std::vector when full. SmallVector is a drop-in replacement -// for std::vector with statically allocated storage for N elements, whose goal is to improve run -// time by avoiding heap allocation and increasing probability of cache hits. The standard API is -// augmented by an unstable_erase operation that does not preserve order, and a replace operation -// that destructively emplaces. -// -// SmallVector<T, 0> is a specialization that thinly wraps std::vector. -// -// Example usage: -// -// ftl::SmallVector<char, 3> vector; -// assert(vector.empty()); -// assert(!vector.dynamic()); -// -// vector = {'a', 'b', 'c'}; -// assert(vector.size() == 3u); -// assert(!vector.dynamic()); -// -// vector.push_back('d'); -// assert(vector.dynamic()); -// -// vector.unstable_erase(vector.begin()); -// assert(vector == (ftl::SmallVector{'d', 'b', 'c'})); -// -// 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()); -// -// 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, std::size_t N> -class SmallVector final : ArrayTraits<T>, ArrayComparators<SmallVector> { - 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>>; - - 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, 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; - - // 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()) {} - - 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_); } - - // 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) - - // 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(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(iterator, last, noexcept) - DISPATCH(const_iterator, last, const) - - DISPATCH(reference, front, noexcept) - DISPATCH(const_reference, front, 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]; - } - - 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)...); - } - - 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_; -}; - -// Partial specialization without static storage. -template <typename T> -class SmallVector<T, 0> final : ArrayTraits<T>, - ArrayIterators<SmallVector<T, 0>, T>, - std::vector<T> { - using ArrayTraits<T>::construct_at; - - using Iter = ArrayIterators<SmallVector, T>; - using Impl = std::vector<T>; - - friend Iter; - - 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, 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::empty; - using Impl::max_size; - using Impl::size; - - using Impl::reserve; - - // 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::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[]; - - 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)...); - } - - 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; - } - - using Impl::pop_back; - - void unstable_erase(iterator it) { - if (it != last()) std::iter_swap(it, last()); - pop_back(); - } - - void swap(SmallVector& other) { Impl::swap(other); } -}; - -template <typename> -struct is_small_vector : std::false_type {}; - -template <typename T, std::size_t N> -struct is_small_vector<SmallVector<T, N>> : std::true_type {}; - -// Deduction guide for array constructor. -template <typename T, std::size_t N> -SmallVector(T (&)[N]) -> SmallVector<std::remove_cv_t<T>, N>; - -// Deduction guide for variadic constructor. -template <typename T, typename... Us, typename V = std::decay_t<T>, - typename = std::enable_if_t<(std::is_constructible_v<V, Us> && ...)>> -SmallVector(T&&, Us&&...) -> SmallVector<V, 1 + sizeof...(Us)>; - -// 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)>; - -// Deduction guide for StaticVector conversion. -template <typename T, std::size_t N> -SmallVector(StaticVector<T, N>&&) -> SmallVector<T, N>; - -template <typename T, std::size_t N> -inline void swap(SmallVector<T, N>& lhs, SmallVector<T, N>& rhs) { - lhs.swap(rhs); -} - -} // namespace android::ftl diff --git a/include/ftl/static_vector.h b/include/ftl/static_vector.h deleted file mode 100644 index 96a1ae853d..0000000000 --- a/include/ftl/static_vector.h +++ /dev/null @@ -1,394 +0,0 @@ -/* - * 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/array_traits.h> -#include <ftl/initializer_list.h> - -#include <algorithm> -#include <cassert> -#include <iterator> -#include <memory> -#include <type_traits> -#include <utility> - -namespace android::ftl { - -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 -// than exactly) N elements. Unlike std::array, its default constructor does not require T to have a -// default constructor, since elements are constructed in place as the vector grows. Operations that -// insert an element (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. -// -// StaticVector<T, 1> is analogous to an iterable std::optional. -// StaticVector<T, 0> is an error. -// -// Example usage: -// -// ftl::StaticVector<char, 3> vector; -// assert(vector.empty()); -// -// vector = {'a', 'b'}; -// assert(vector.size() == 2u); -// -// vector.push_back('c'); -// assert(vector.full()); -// -// assert(!vector.push_back('d')); -// assert(vector.size() == 3u); -// -// vector.unstable_erase(vector.begin()); -// assert(vector == (ftl::StaticVector{'c', 'b'})); -// -// vector.pop_back(); -// assert(vector.back() == 'c'); -// -// const char array[] = "hi"; -// vector = ftl::StaticVector(array); -// assert(vector == (ftl::StaticVector{'h', 'i', '\0'})); -// -// 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); - - using ArrayTraits<T>::construct_at; - - 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>>>; - - 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, 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; - - // Copies and moves a vector, respectively. - StaticVector(const StaticVector& other) - : StaticVector(kIteratorRange, other.begin(), other.end()) {} - - 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 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"); - } - - 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_; - } - - 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]; -}; - -// Deduction guide for array constructor. -template <typename T, std::size_t N> -StaticVector(T (&)[N]) -> StaticVector<std::remove_cv_t<T>, N>; - -// Deduction guide for variadic constructor. -template <typename T, typename... Us, typename V = std::decay_t<T>, - typename = std::enable_if_t<(std::is_constructible_v<V, Us> && ...)>> -StaticVector(T&&, Us&&...) -> StaticVector<V, 1 + sizeof...(Us)>; - -// Deduction guide for in-place constructor. -template <typename T, std::size_t... Sizes, typename... Types> -StaticVector(InitializerList<T, std::index_sequence<Sizes...>, Types...>&&) - -> 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; - - // 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; - } - - // 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); -} - -} // namespace android::ftl |