diff options
Diffstat (limited to 'include/ftl/static_vector.h')
| -rw-r--r-- | include/ftl/static_vector.h | 394 |
1 files changed, 394 insertions, 0 deletions
diff --git a/include/ftl/static_vector.h b/include/ftl/static_vector.h new file mode 100644 index 0000000000..96a1ae853d --- /dev/null +++ b/include/ftl/static_vector.h @@ -0,0 +1,394 @@ +/* + * 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 |