Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 1 | /* |
| 2 | * Copyright 2020 The Android Open Source Project |
| 3 | * |
| 4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
| 5 | * you may not use this file except in compliance with the License. |
| 6 | * You may obtain a copy of the License at |
| 7 | * |
| 8 | * http://www.apache.org/licenses/LICENSE-2.0 |
| 9 | * |
| 10 | * Unless required by applicable law or agreed to in writing, software |
| 11 | * distributed under the License is distributed on an "AS IS" BASIS, |
| 12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 13 | * See the License for the specific language governing permissions and |
| 14 | * limitations under the License. |
| 15 | */ |
| 16 | |
| 17 | #pragma once |
| 18 | |
Dominik Laskowski | 04667b7 | 2021-12-15 13:14:54 -0800 | [diff] [blame] | 19 | #include <ftl/details/array_traits.h> |
Dominik Laskowski | 5444fc8 | 2020-11-24 13:41:10 -0800 | [diff] [blame] | 20 | #include <ftl/static_vector.h> |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 21 | |
| 22 | #include <algorithm> |
| 23 | #include <iterator> |
| 24 | #include <type_traits> |
| 25 | #include <utility> |
| 26 | #include <variant> |
| 27 | #include <vector> |
| 28 | |
| 29 | namespace android::ftl { |
| 30 | |
| 31 | template <typename> |
Dominik Laskowski | 5444fc8 | 2020-11-24 13:41:10 -0800 | [diff] [blame] | 32 | struct is_small_vector; |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 33 | |
| 34 | // ftl::StaticVector that promotes to std::vector when full. SmallVector is a drop-in replacement |
| 35 | // for std::vector with statically allocated storage for N elements, whose goal is to improve run |
| 36 | // time by avoiding heap allocation and increasing probability of cache hits. The standard API is |
| 37 | // augmented by an unstable_erase operation that does not preserve order, and a replace operation |
| 38 | // that destructively emplaces. |
| 39 | // |
Dominik Laskowski | 206996f | 2022-01-20 13:21:57 -0800 | [diff] [blame^] | 40 | // Unlike std::vector, T does not require copy/move assignment, so may be an object with const data |
| 41 | // members, or be const itself. |
| 42 | // |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 43 | // SmallVector<T, 0> is a specialization that thinly wraps std::vector. |
| 44 | // |
| 45 | // Example usage: |
| 46 | // |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 47 | // ftl::SmallVector<char, 3> vector; |
| 48 | // assert(vector.empty()); |
| 49 | // assert(!vector.dynamic()); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 50 | // |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 51 | // vector = {'a', 'b', 'c'}; |
| 52 | // assert(vector.size() == 3u); |
| 53 | // assert(!vector.dynamic()); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 54 | // |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 55 | // vector.push_back('d'); |
| 56 | // assert(vector.dynamic()); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 57 | // |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 58 | // vector.unstable_erase(vector.begin()); |
| 59 | // assert(vector == (ftl::SmallVector{'d', 'b', 'c'})); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 60 | // |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 61 | // vector.pop_back(); |
| 62 | // assert(vector.back() == 'b'); |
| 63 | // assert(vector.dynamic()); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 64 | // |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 65 | // const char array[] = "hi"; |
| 66 | // vector = ftl::SmallVector(array); |
| 67 | // assert(vector == (ftl::SmallVector{'h', 'i', '\0'})); |
| 68 | // assert(!vector.dynamic()); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 69 | // |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 70 | // ftl::SmallVector strings = ftl::init::list<std::string>("abc")("123456", 3u)(3u, '?'); |
| 71 | // assert(strings.size() == 3u); |
| 72 | // assert(!strings.dynamic()); |
Dominik Laskowski | ccd50a4 | 2020-10-30 19:56:38 -0700 | [diff] [blame] | 73 | // |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 74 | // assert(strings[0] == "abc"); |
| 75 | // assert(strings[1] == "123"); |
| 76 | // assert(strings[2] == "???"); |
Dominik Laskowski | ccd50a4 | 2020-10-30 19:56:38 -0700 | [diff] [blame] | 77 | // |
Dominik Laskowski | 5444fc8 | 2020-11-24 13:41:10 -0800 | [diff] [blame] | 78 | template <typename T, std::size_t N> |
Dominik Laskowski | 04667b7 | 2021-12-15 13:14:54 -0800 | [diff] [blame] | 79 | class SmallVector final : details::ArrayTraits<T>, details::ArrayComparators<SmallVector> { |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 80 | using Static = StaticVector<T, N>; |
| 81 | using Dynamic = SmallVector<T, 0>; |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 82 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 83 | // TODO: Replace with std::remove_cvref_t in C++20. |
| 84 | template <typename U> |
| 85 | using remove_cvref_t = std::remove_cv_t<std::remove_reference_t<U>>; |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 86 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 87 | public: |
| 88 | FTL_ARRAY_TRAIT(T, value_type); |
| 89 | FTL_ARRAY_TRAIT(T, size_type); |
| 90 | FTL_ARRAY_TRAIT(T, difference_type); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 91 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 92 | FTL_ARRAY_TRAIT(T, pointer); |
| 93 | FTL_ARRAY_TRAIT(T, reference); |
| 94 | FTL_ARRAY_TRAIT(T, iterator); |
| 95 | FTL_ARRAY_TRAIT(T, reverse_iterator); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 96 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 97 | FTL_ARRAY_TRAIT(T, const_pointer); |
| 98 | FTL_ARRAY_TRAIT(T, const_reference); |
| 99 | FTL_ARRAY_TRAIT(T, const_iterator); |
| 100 | FTL_ARRAY_TRAIT(T, const_reverse_iterator); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 101 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 102 | // Creates an empty vector. |
| 103 | SmallVector() = default; |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 104 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 105 | // Constructs at most N elements. See StaticVector for underlying constructors. |
| 106 | template <typename Arg, typename... Args, |
| 107 | typename = std::enable_if_t<!is_small_vector<remove_cvref_t<Arg>>{}>> |
| 108 | SmallVector(Arg&& arg, Args&&... args) |
| 109 | : vector_(std::in_place_type<Static>, std::forward<Arg>(arg), std::forward<Args>(args)...) {} |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 110 | |
Dominik Laskowski | 206996f | 2022-01-20 13:21:57 -0800 | [diff] [blame^] | 111 | // Copies or moves elements from a smaller convertible vector. |
| 112 | template <typename U, std::size_t M, typename = std::enable_if_t<(M > 0)>> |
| 113 | SmallVector(SmallVector<U, M> other) : vector_(convert(std::move(other))) {} |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 114 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 115 | void swap(SmallVector& other) { vector_.swap(other.vector_); } |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 116 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 117 | // Returns whether the vector is backed by static or dynamic storage. |
| 118 | bool dynamic() const { return std::holds_alternative<Dynamic>(vector_); } |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 119 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 120 | // Avoid std::visit as it generates a dispatch table. |
| 121 | #define DISPATCH(T, F, ...) \ |
| 122 | T F() __VA_ARGS__ { \ |
| 123 | return dynamic() ? std::get<Dynamic>(vector_).F() : std::get<Static>(vector_).F(); \ |
| 124 | } |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 125 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 126 | DISPATCH(size_type, max_size, const) |
| 127 | DISPATCH(size_type, size, const) |
| 128 | DISPATCH(bool, empty, const) |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 129 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 130 | // noexcept to suppress warning about zero variadic macro arguments. |
| 131 | DISPATCH(iterator, begin, noexcept) |
| 132 | DISPATCH(const_iterator, begin, const) |
| 133 | DISPATCH(const_iterator, cbegin, const) |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 134 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 135 | DISPATCH(iterator, end, noexcept) |
| 136 | DISPATCH(const_iterator, end, const) |
| 137 | DISPATCH(const_iterator, cend, const) |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 138 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 139 | DISPATCH(reverse_iterator, rbegin, noexcept) |
| 140 | DISPATCH(const_reverse_iterator, rbegin, const) |
| 141 | DISPATCH(const_reverse_iterator, crbegin, const) |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 142 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 143 | DISPATCH(reverse_iterator, rend, noexcept) |
| 144 | DISPATCH(const_reverse_iterator, rend, const) |
| 145 | DISPATCH(const_reverse_iterator, crend, const) |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 146 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 147 | DISPATCH(iterator, last, noexcept) |
| 148 | DISPATCH(const_iterator, last, const) |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 149 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 150 | DISPATCH(reference, front, noexcept) |
| 151 | DISPATCH(const_reference, front, const) |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 152 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 153 | DISPATCH(reference, back, noexcept) |
| 154 | DISPATCH(const_reference, back, const) |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 155 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 156 | reference operator[](size_type i) { |
| 157 | return dynamic() ? std::get<Dynamic>(vector_)[i] : std::get<Static>(vector_)[i]; |
| 158 | } |
| 159 | |
| 160 | const_reference operator[](size_type i) const { return const_cast<SmallVector&>(*this)[i]; } |
| 161 | |
| 162 | // Replaces an element, and returns a reference to it. The iterator must be dereferenceable, so |
| 163 | // replacing at end() is erroneous. |
| 164 | // |
| 165 | // The element is emplaced via move constructor, so type T does not need to define copy/move |
| 166 | // assignment, e.g. its data members may be const. |
| 167 | // |
| 168 | // The arguments may directly or indirectly refer to the element being replaced. |
| 169 | // |
| 170 | // Iterators to the replaced element point to its replacement, and others remain valid. |
| 171 | // |
| 172 | template <typename... Args> |
| 173 | reference replace(const_iterator it, Args&&... args) { |
| 174 | if (dynamic()) { |
| 175 | return std::get<Dynamic>(vector_).replace(it, std::forward<Args>(args)...); |
| 176 | } else { |
| 177 | return std::get<Static>(vector_).replace(it, std::forward<Args>(args)...); |
| 178 | } |
| 179 | } |
| 180 | |
| 181 | // Appends an element, and returns a reference to it. |
| 182 | // |
| 183 | // If the vector reaches its static or dynamic capacity, then all iterators are invalidated. |
| 184 | // Otherwise, only the end() iterator is invalidated. |
| 185 | // |
| 186 | template <typename... Args> |
| 187 | reference emplace_back(Args&&... args) { |
| 188 | constexpr auto kInsertStatic = &Static::template emplace_back<Args...>; |
| 189 | constexpr auto kInsertDynamic = &Dynamic::template emplace_back<Args...>; |
| 190 | return *insert<kInsertStatic, kInsertDynamic>(std::forward<Args>(args)...); |
| 191 | } |
| 192 | |
| 193 | // Appends an element. |
| 194 | // |
| 195 | // If the vector reaches its static or dynamic capacity, then all iterators are invalidated. |
| 196 | // Otherwise, only the end() iterator is invalidated. |
| 197 | // |
| 198 | void push_back(const value_type& v) { |
| 199 | constexpr auto kInsertStatic = |
| 200 | static_cast<bool (Static::*)(const value_type&)>(&Static::push_back); |
| 201 | constexpr auto kInsertDynamic = |
| 202 | static_cast<bool (Dynamic::*)(const value_type&)>(&Dynamic::push_back); |
| 203 | insert<kInsertStatic, kInsertDynamic>(v); |
| 204 | } |
| 205 | |
| 206 | void push_back(value_type&& v) { |
| 207 | constexpr auto kInsertStatic = static_cast<bool (Static::*)(value_type &&)>(&Static::push_back); |
| 208 | constexpr auto kInsertDynamic = |
| 209 | static_cast<bool (Dynamic::*)(value_type &&)>(&Dynamic::push_back); |
| 210 | insert<kInsertStatic, kInsertDynamic>(std::move(v)); |
| 211 | } |
| 212 | |
| 213 | // Removes the last element. The vector must not be empty, or the call is erroneous. |
| 214 | // |
| 215 | // The last() and end() iterators are invalidated. |
| 216 | // |
Dominik Laskowski | 44828ce | 2021-09-13 11:00:22 -0700 | [diff] [blame] | 217 | DISPATCH(void, pop_back, noexcept) |
| 218 | |
| 219 | // Removes all elements. |
| 220 | // |
| 221 | // All iterators are invalidated. |
| 222 | // |
| 223 | DISPATCH(void, clear, noexcept) |
| 224 | |
| 225 | #undef DISPATCH |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 226 | |
| 227 | // Erases an element, but does not preserve order. Rather than shifting subsequent elements, |
| 228 | // this moves the last element to the slot of the erased element. |
| 229 | // |
| 230 | // The last() and end() iterators, as well as those to the erased element, are invalidated. |
| 231 | // |
| 232 | void unstable_erase(iterator it) { |
| 233 | if (dynamic()) { |
| 234 | std::get<Dynamic>(vector_).unstable_erase(it); |
| 235 | } else { |
| 236 | std::get<Static>(vector_).unstable_erase(it); |
| 237 | } |
| 238 | } |
| 239 | |
Dominik Laskowski | 206996f | 2022-01-20 13:21:57 -0800 | [diff] [blame^] | 240 | // Extracts the elements as std::vector. |
| 241 | std::vector<T> promote() && { |
| 242 | if (dynamic()) { |
| 243 | return std::get<Dynamic>(std::move(vector_)).promote(); |
| 244 | } else { |
| 245 | return {std::make_move_iterator(begin()), std::make_move_iterator(end())}; |
| 246 | } |
| 247 | } |
| 248 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 249 | private: |
Dominik Laskowski | 206996f | 2022-01-20 13:21:57 -0800 | [diff] [blame^] | 250 | template <typename, std::size_t> |
| 251 | friend class SmallVector; |
| 252 | |
| 253 | template <typename U, std::size_t M> |
| 254 | static std::variant<Static, Dynamic> convert(SmallVector<U, M>&& other) { |
| 255 | using Other = SmallVector<U, M>; |
| 256 | |
| 257 | if (other.dynamic()) { |
| 258 | return std::get<typename Other::Dynamic>(std::move(other.vector_)); |
| 259 | } else { |
| 260 | return std::get<typename Other::Static>(std::move(other.vector_)); |
| 261 | } |
| 262 | } |
| 263 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 264 | template <auto InsertStatic, auto InsertDynamic, typename... Args> |
| 265 | auto insert(Args&&... args) { |
| 266 | if (Dynamic* const vector = std::get_if<Dynamic>(&vector_)) { |
| 267 | return (vector->*InsertDynamic)(std::forward<Args>(args)...); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 268 | } |
| 269 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 270 | auto& vector = std::get<Static>(vector_); |
| 271 | if (vector.full()) { |
| 272 | return (promote(vector).*InsertDynamic)(std::forward<Args>(args)...); |
| 273 | } else { |
| 274 | return (vector.*InsertStatic)(std::forward<Args>(args)...); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 275 | } |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 276 | } |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 277 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 278 | Dynamic& promote(Static& static_vector) { |
| 279 | assert(static_vector.full()); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 280 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 281 | // Allocate double capacity to reduce probability of reallocation. |
| 282 | Dynamic vector; |
| 283 | vector.reserve(Static::max_size() * 2); |
| 284 | std::move(static_vector.begin(), static_vector.end(), std::back_inserter(vector)); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 285 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 286 | return vector_.template emplace<Dynamic>(std::move(vector)); |
| 287 | } |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 288 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 289 | std::variant<Static, Dynamic> vector_; |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 290 | }; |
| 291 | |
| 292 | // Partial specialization without static storage. |
| 293 | template <typename T> |
Dominik Laskowski | 04667b7 | 2021-12-15 13:14:54 -0800 | [diff] [blame] | 294 | class SmallVector<T, 0> final : details::ArrayTraits<T>, |
Dominik Laskowski | 206996f | 2022-01-20 13:21:57 -0800 | [diff] [blame^] | 295 | details::ArrayComparators<SmallVector>, |
Dominik Laskowski | 04667b7 | 2021-12-15 13:14:54 -0800 | [diff] [blame] | 296 | details::ArrayIterators<SmallVector<T, 0>, T>, |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 297 | std::vector<T> { |
Dominik Laskowski | 206996f | 2022-01-20 13:21:57 -0800 | [diff] [blame^] | 298 | using details::ArrayTraits<T>::replace_at; |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 299 | |
Dominik Laskowski | 04667b7 | 2021-12-15 13:14:54 -0800 | [diff] [blame] | 300 | using Iter = details::ArrayIterators<SmallVector, T>; |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 301 | using Impl = std::vector<T>; |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 302 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 303 | friend Iter; |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 304 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 305 | public: |
| 306 | FTL_ARRAY_TRAIT(T, value_type); |
| 307 | FTL_ARRAY_TRAIT(T, size_type); |
| 308 | FTL_ARRAY_TRAIT(T, difference_type); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 309 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 310 | FTL_ARRAY_TRAIT(T, pointer); |
| 311 | FTL_ARRAY_TRAIT(T, reference); |
| 312 | FTL_ARRAY_TRAIT(T, iterator); |
| 313 | FTL_ARRAY_TRAIT(T, reverse_iterator); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 314 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 315 | FTL_ARRAY_TRAIT(T, const_pointer); |
| 316 | FTL_ARRAY_TRAIT(T, const_reference); |
| 317 | FTL_ARRAY_TRAIT(T, const_iterator); |
| 318 | FTL_ARRAY_TRAIT(T, const_reverse_iterator); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 319 | |
Dominik Laskowski | 206996f | 2022-01-20 13:21:57 -0800 | [diff] [blame^] | 320 | // See std::vector for underlying constructors. |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 321 | using Impl::Impl; |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 322 | |
Dominik Laskowski | 206996f | 2022-01-20 13:21:57 -0800 | [diff] [blame^] | 323 | // Copies and moves a vector, respectively. |
| 324 | SmallVector(const SmallVector&) = default; |
| 325 | SmallVector(SmallVector&&) = default; |
| 326 | |
| 327 | // Constructs elements in place. See StaticVector for underlying constructor. |
| 328 | template <typename U, std::size_t... Sizes, typename... Types> |
| 329 | SmallVector(InitializerList<U, std::index_sequence<Sizes...>, Types...>&& list) |
| 330 | : SmallVector(SmallVector<T, sizeof...(Sizes)>(std::move(list))) {} |
| 331 | |
| 332 | // Copies or moves elements from a convertible vector. |
| 333 | template <typename U, std::size_t M> |
| 334 | SmallVector(SmallVector<U, M> other) : Impl(convert(std::move(other))) {} |
| 335 | |
| 336 | SmallVector& operator=(SmallVector other) { |
| 337 | // Define copy/move assignment in terms of copy/move construction. |
| 338 | swap(other); |
| 339 | return *this; |
| 340 | } |
| 341 | |
| 342 | void swap(SmallVector& other) { Impl::swap(other); } |
| 343 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 344 | using Impl::empty; |
| 345 | using Impl::max_size; |
| 346 | using Impl::size; |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 347 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 348 | using Impl::reserve; |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 349 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 350 | // std::vector iterators are not necessarily raw pointers. |
| 351 | iterator begin() { return Impl::data(); } |
| 352 | iterator end() { return Impl::data() + size(); } |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 353 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 354 | using Iter::begin; |
| 355 | using Iter::end; |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 356 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 357 | using Iter::cbegin; |
| 358 | using Iter::cend; |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 359 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 360 | using Iter::rbegin; |
| 361 | using Iter::rend; |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 362 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 363 | using Iter::crbegin; |
| 364 | using Iter::crend; |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 365 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 366 | using Iter::last; |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 367 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 368 | using Iter::back; |
| 369 | using Iter::front; |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 370 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 371 | using Iter::operator[]; |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 372 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 373 | template <typename... Args> |
| 374 | reference replace(const_iterator it, Args&&... args) { |
Dominik Laskowski | 206996f | 2022-01-20 13:21:57 -0800 | [diff] [blame^] | 375 | return replace_at(it, std::forward<Args>(args)...); |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 376 | } |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 377 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 378 | template <typename... Args> |
| 379 | iterator emplace_back(Args&&... args) { |
| 380 | return &Impl::emplace_back(std::forward<Args>(args)...); |
| 381 | } |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 382 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 383 | bool push_back(const value_type& v) { |
| 384 | Impl::push_back(v); |
| 385 | return true; |
| 386 | } |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 387 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 388 | bool push_back(value_type&& v) { |
| 389 | Impl::push_back(std::move(v)); |
| 390 | return true; |
| 391 | } |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 392 | |
Dominik Laskowski | 44828ce | 2021-09-13 11:00:22 -0700 | [diff] [blame] | 393 | using Impl::clear; |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 394 | using Impl::pop_back; |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 395 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 396 | void unstable_erase(iterator it) { |
Dominik Laskowski | dda9bba | 2021-02-03 18:56:00 -0800 | [diff] [blame] | 397 | if (it != last()) replace(it, std::move(back())); |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 398 | pop_back(); |
| 399 | } |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 400 | |
Dominik Laskowski | 206996f | 2022-01-20 13:21:57 -0800 | [diff] [blame^] | 401 | std::vector<T> promote() && { return std::move(*this); } |
| 402 | |
| 403 | private: |
| 404 | template <typename U, std::size_t M> |
| 405 | static Impl convert(SmallVector<U, M>&& other) { |
| 406 | if constexpr (std::is_constructible_v<Impl, std::vector<U>&&>) { |
| 407 | return std::move(other).promote(); |
| 408 | } else { |
| 409 | SmallVector vector(other.size()); |
| 410 | |
| 411 | // Consistently with StaticVector, T only requires copy/move construction from U, rather than |
| 412 | // copy/move assignment. |
| 413 | auto it = vector.begin(); |
| 414 | for (auto& element : other) { |
| 415 | vector.replace(it++, std::move(element)); |
| 416 | } |
| 417 | |
| 418 | return vector; |
| 419 | } |
| 420 | } |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 421 | }; |
| 422 | |
| 423 | template <typename> |
Dominik Laskowski | 5444fc8 | 2020-11-24 13:41:10 -0800 | [diff] [blame] | 424 | struct is_small_vector : std::false_type {}; |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 425 | |
Dominik Laskowski | 5444fc8 | 2020-11-24 13:41:10 -0800 | [diff] [blame] | 426 | template <typename T, std::size_t N> |
| 427 | struct is_small_vector<SmallVector<T, N>> : std::true_type {}; |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 428 | |
| 429 | // Deduction guide for array constructor. |
Dominik Laskowski | 5444fc8 | 2020-11-24 13:41:10 -0800 | [diff] [blame] | 430 | template <typename T, std::size_t N> |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 431 | SmallVector(T (&)[N]) -> SmallVector<std::remove_cv_t<T>, N>; |
| 432 | |
| 433 | // Deduction guide for variadic constructor. |
| 434 | template <typename T, typename... Us, typename V = std::decay_t<T>, |
| 435 | typename = std::enable_if_t<(std::is_constructible_v<V, Us> && ...)>> |
| 436 | SmallVector(T&&, Us&&...) -> SmallVector<V, 1 + sizeof...(Us)>; |
| 437 | |
| 438 | // Deduction guide for in-place constructor. |
Dominik Laskowski | 5444fc8 | 2020-11-24 13:41:10 -0800 | [diff] [blame] | 439 | template <typename T, std::size_t... Sizes, typename... Types> |
Dominik Laskowski | ccd50a4 | 2020-10-30 19:56:38 -0700 | [diff] [blame] | 440 | SmallVector(InitializerList<T, std::index_sequence<Sizes...>, Types...>&&) |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 441 | -> SmallVector<T, sizeof...(Sizes)>; |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 442 | |
| 443 | // Deduction guide for StaticVector conversion. |
Dominik Laskowski | 5444fc8 | 2020-11-24 13:41:10 -0800 | [diff] [blame] | 444 | template <typename T, std::size_t N> |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 445 | SmallVector(StaticVector<T, N>&&) -> SmallVector<T, N>; |
| 446 | |
Dominik Laskowski | 5444fc8 | 2020-11-24 13:41:10 -0800 | [diff] [blame] | 447 | template <typename T, std::size_t N> |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 448 | inline void swap(SmallVector<T, N>& lhs, SmallVector<T, N>& rhs) { |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 449 | lhs.swap(rhs); |
Dominik Laskowski | 0bacf27 | 2020-10-22 14:08:27 -0700 | [diff] [blame] | 450 | } |
| 451 | |
Dominik Laskowski | e21dbed | 2020-12-04 20:51:43 -0800 | [diff] [blame] | 452 | } // namespace android::ftl |