blob: 2f05a9bf028680fa16514dae12fc4de9cb9e71fc [file] [log] [blame]
Dominik Laskowski0bacf272020-10-22 14:08:27 -07001/*
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
19#include <ftl/ArrayTraits.h>
20#include <ftl/StaticVector.h>
21
22#include <algorithm>
23#include <iterator>
24#include <type_traits>
25#include <utility>
26#include <variant>
27#include <vector>
28
29namespace android::ftl {
30
31template <typename>
32struct IsSmallVector;
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//
40// SmallVector<T, 0> is a specialization that thinly wraps std::vector.
41//
42// Example usage:
43//
44// ftl::SmallVector<char, 3> vector;
45// assert(vector.empty());
46// assert(!vector.dynamic());
47//
48// vector = {'a', 'b', 'c'};
49// assert(vector.size() == 3u);
50// assert(!vector.dynamic());
51//
52// vector.push_back('d');
53// assert(vector.dynamic());
54//
55// vector.unstable_erase(vector.begin());
56// assert(vector == (ftl::SmallVector{'d', 'b', 'c'}));
57//
58// vector.pop_back();
59// assert(vector.back() == 'b');
60// assert(vector.dynamic());
61//
62// const char array[] = "hi";
63// vector = ftl::SmallVector(array);
64// assert(vector == (ftl::SmallVector{'h', 'i', '\0'}));
65// assert(!vector.dynamic());
66//
Dominik Laskowskiccd50a42020-10-30 19:56:38 -070067// ftl::SmallVector strings = ftl::init::list<std::string>("abc")
68// ("123456", 3u)
69// (3u, '?');
70// assert(strings.size() == 3u);
71// assert(!strings.dynamic());
72//
73// assert(strings[0] == "abc");
74// assert(strings[1] == "123");
75// assert(strings[2] == "???");
76//
Dominik Laskowski0bacf272020-10-22 14:08:27 -070077template <typename T, size_t N>
78class SmallVector final : ArrayTraits<T>, ArrayComparators<SmallVector> {
79 using Static = StaticVector<T, N>;
80 using Dynamic = SmallVector<T, 0>;
81
82 // TODO: Replace with std::remove_cvref_t in C++20.
83 template <typename U>
84 using remove_cvref_t = std::remove_cv_t<std::remove_reference_t<U>>;
85
86public:
87 FTL_ARRAY_TRAIT(T, value_type);
88 FTL_ARRAY_TRAIT(T, size_type);
89 FTL_ARRAY_TRAIT(T, difference_type);
90
91 FTL_ARRAY_TRAIT(T, pointer);
92 FTL_ARRAY_TRAIT(T, reference);
93 FTL_ARRAY_TRAIT(T, iterator);
94 FTL_ARRAY_TRAIT(T, reverse_iterator);
95
96 FTL_ARRAY_TRAIT(T, const_pointer);
97 FTL_ARRAY_TRAIT(T, const_reference);
98 FTL_ARRAY_TRAIT(T, const_iterator);
99 FTL_ARRAY_TRAIT(T, const_reverse_iterator);
100
101 // Creates an empty vector.
102 SmallVector() = default;
103
104 // Constructs at most N elements. See StaticVector for underlying constructors.
105 template <typename Arg, typename... Args,
106 typename = std::enable_if_t<!IsSmallVector<remove_cvref_t<Arg>>{}>>
107 SmallVector(Arg&& arg, Args&&... args)
108 : mVector(std::in_place_type<Static>, std::forward<Arg>(arg),
109 std::forward<Args>(args)...) {}
110
111 // Copies at most N elements from a smaller convertible vector.
112 template <typename U, size_t M, typename = std::enable_if_t<M <= N>>
113 SmallVector(const SmallVector<U, M>& other)
114 : SmallVector(IteratorRange, other.begin(), other.end()) {}
115
116 void swap(SmallVector& other) { mVector.swap(other.mVector); }
117
118 // Returns whether the vector is backed by static or dynamic storage.
119 bool dynamic() const { return std::holds_alternative<Dynamic>(mVector); }
120
Dominik Laskowski534b2a22020-10-26 16:31:47 -0700121 // Avoid std::visit as it generates a dispatch table.
122#define DISPATCH(T, F, ...) \
123 T F() __VA_ARGS__ { \
124 return dynamic() ? std::get<Dynamic>(mVector).F() : std::get<Static>(mVector).F(); \
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700125 }
126
Dominik Laskowski534b2a22020-10-26 16:31:47 -0700127 DISPATCH(size_type, max_size, const)
128 DISPATCH(size_type, size, const)
129 DISPATCH(bool, empty, const)
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700130
131 // noexcept to suppress warning about zero variadic macro arguments.
Dominik Laskowski534b2a22020-10-26 16:31:47 -0700132 DISPATCH(iterator, begin, noexcept)
133 DISPATCH(const_iterator, begin, const)
134 DISPATCH(const_iterator, cbegin, const)
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700135
Dominik Laskowski534b2a22020-10-26 16:31:47 -0700136 DISPATCH(iterator, end, noexcept)
137 DISPATCH(const_iterator, end, const)
138 DISPATCH(const_iterator, cend, const)
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700139
Dominik Laskowski534b2a22020-10-26 16:31:47 -0700140 DISPATCH(reverse_iterator, rbegin, noexcept)
141 DISPATCH(const_reverse_iterator, rbegin, const)
142 DISPATCH(const_reverse_iterator, crbegin, const)
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700143
Dominik Laskowski534b2a22020-10-26 16:31:47 -0700144 DISPATCH(reverse_iterator, rend, noexcept)
145 DISPATCH(const_reverse_iterator, rend, const)
146 DISPATCH(const_reverse_iterator, crend, const)
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700147
Dominik Laskowski534b2a22020-10-26 16:31:47 -0700148 DISPATCH(iterator, last, noexcept)
149 DISPATCH(const_iterator, last, const)
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700150
Dominik Laskowski534b2a22020-10-26 16:31:47 -0700151 DISPATCH(reference, front, noexcept)
152 DISPATCH(const_reference, front, const)
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700153
Dominik Laskowski534b2a22020-10-26 16:31:47 -0700154 DISPATCH(reference, back, noexcept)
155 DISPATCH(const_reference, back, const)
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700156
Dominik Laskowski534b2a22020-10-26 16:31:47 -0700157#undef DISPATCH
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700158
159 reference operator[](size_type i) {
Dominik Laskowski534b2a22020-10-26 16:31:47 -0700160 return dynamic() ? std::get<Dynamic>(mVector)[i] : std::get<Static>(mVector)[i];
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700161 }
162
Dominik Laskowski534b2a22020-10-26 16:31:47 -0700163 const_reference operator[](size_type i) const { return const_cast<SmallVector&>(*this)[i]; }
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700164
165 // Replaces an element, and returns a reference to it. The iterator must be dereferenceable, so
166 // replacing at end() is erroneous.
167 //
168 // The element is emplaced via move constructor, so type T does not need to define copy/move
169 // assignment, e.g. its data members may be const.
170 //
171 // The arguments may directly or indirectly refer to the element being replaced.
172 //
173 // Iterators to the replaced element point to its replacement, and others remain valid.
174 //
175 template <typename... Args>
176 reference replace(const_iterator it, Args&&... args) {
Dominik Laskowski534b2a22020-10-26 16:31:47 -0700177 if (dynamic()) {
178 return std::get<Dynamic>(mVector).replace(it, std::forward<Args>(args)...);
179 } else {
180 return std::get<Static>(mVector).replace(it, std::forward<Args>(args)...);
181 }
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700182 }
183
184 // Appends an element, and returns a reference to it.
185 //
186 // If the vector reaches its static or dynamic capacity, then all iterators are invalidated.
187 // Otherwise, only the end() iterator is invalidated.
188 //
189 template <typename... Args>
190 reference emplace_back(Args&&... args) {
191 constexpr auto insertStatic = &Static::template emplace_back<Args...>;
192 constexpr auto insertDynamic = &Dynamic::template emplace_back<Args...>;
193 return *insert<insertStatic, insertDynamic>(std::forward<Args>(args)...);
194 }
195
196 // Appends an element.
197 //
198 // If the vector reaches its static or dynamic capacity, then all iterators are invalidated.
199 // Otherwise, only the end() iterator is invalidated.
200 //
201 void push_back(const value_type& v) {
202 constexpr auto insertStatic =
203 static_cast<bool (Static::*)(const value_type&)>(&Static::push_back);
204 constexpr auto insertDynamic =
205 static_cast<bool (Dynamic::*)(const value_type&)>(&Dynamic::push_back);
206 insert<insertStatic, insertDynamic>(v);
207 }
208
209 void push_back(value_type&& v) {
210 constexpr auto insertStatic =
211 static_cast<bool (Static::*)(value_type&&)>(&Static::push_back);
212 constexpr auto insertDynamic =
213 static_cast<bool (Dynamic::*)(value_type&&)>(&Dynamic::push_back);
214 insert<insertStatic, insertDynamic>(std::move(v));
215 }
216
217 // Removes the last element. The vector must not be empty, or the call is erroneous.
218 //
219 // The last() and end() iterators are invalidated.
220 //
221 void pop_back() {
Dominik Laskowski534b2a22020-10-26 16:31:47 -0700222 if (dynamic()) {
223 std::get<Dynamic>(mVector).pop_back();
224 } else {
225 std::get<Static>(mVector).pop_back();
226 }
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700227 }
228
229 // Erases an element, but does not preserve order. Rather than shifting subsequent elements,
230 // this moves the last element to the slot of the erased element.
231 //
232 // The last() and end() iterators, as well as those to the erased element, are invalidated.
233 //
234 void unstable_erase(iterator it) {
Dominik Laskowski534b2a22020-10-26 16:31:47 -0700235 if (dynamic()) {
236 std::get<Dynamic>(mVector).unstable_erase(it);
237 } else {
238 std::get<Static>(mVector).unstable_erase(it);
239 }
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700240 }
241
242private:
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700243 template <auto insertStatic, auto insertDynamic, typename... Args>
244 auto insert(Args&&... args) {
Dominik Laskowski534b2a22020-10-26 16:31:47 -0700245 if (Dynamic* const vector = std::get_if<Dynamic>(&mVector)) {
246 return (vector->*insertDynamic)(std::forward<Args>(args)...);
247 }
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700248
Dominik Laskowski534b2a22020-10-26 16:31:47 -0700249 auto& vector = std::get<Static>(mVector);
250 if (vector.full()) {
251 return (promote(vector).*insertDynamic)(std::forward<Args>(args)...);
252 } else {
253 return (vector.*insertStatic)(std::forward<Args>(args)...);
254 }
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700255 }
256
257 Dynamic& promote(Static& staticVector) {
258 assert(staticVector.full());
259
260 // Allocate double capacity to reduce probability of reallocation.
261 Dynamic vector;
262 vector.reserve(Static::max_size() * 2);
263 std::move(staticVector.begin(), staticVector.end(), std::back_inserter(vector));
264
265 return mVector.template emplace<Dynamic>(std::move(vector));
266 }
267
268 std::variant<Static, Dynamic> mVector;
269};
270
271// Partial specialization without static storage.
272template <typename T>
273class SmallVector<T, 0> final : ArrayTraits<T>,
274 ArrayIterators<SmallVector<T, 0>, T>,
275 std::vector<T> {
276 using ArrayTraits<T>::construct_at;
277
278 using Iter = ArrayIterators<SmallVector, T>;
279 using Impl = std::vector<T>;
280
281 friend Iter;
282
283public:
284 FTL_ARRAY_TRAIT(T, value_type);
285 FTL_ARRAY_TRAIT(T, size_type);
286 FTL_ARRAY_TRAIT(T, difference_type);
287
288 FTL_ARRAY_TRAIT(T, pointer);
289 FTL_ARRAY_TRAIT(T, reference);
290 FTL_ARRAY_TRAIT(T, iterator);
291 FTL_ARRAY_TRAIT(T, reverse_iterator);
292
293 FTL_ARRAY_TRAIT(T, const_pointer);
294 FTL_ARRAY_TRAIT(T, const_reference);
295 FTL_ARRAY_TRAIT(T, const_iterator);
296 FTL_ARRAY_TRAIT(T, const_reverse_iterator);
297
298 using Impl::Impl;
299
300 using Impl::empty;
301 using Impl::max_size;
302 using Impl::size;
303
304 using Impl::reserve;
305
306 // std::vector iterators are not necessarily raw pointers.
307 iterator begin() { return Impl::data(); }
308 iterator end() { return Impl::data() + size(); }
309
310 using Iter::begin;
311 using Iter::end;
312
313 using Iter::cbegin;
314 using Iter::cend;
315
316 using Iter::rbegin;
317 using Iter::rend;
318
319 using Iter::crbegin;
320 using Iter::crend;
321
322 using Iter::last;
323
324 using Iter::back;
325 using Iter::front;
326
327 using Iter::operator[];
328
329 template <typename... Args>
330 reference replace(const_iterator it, Args&&... args) {
331 value_type element{std::forward<Args>(args)...};
332 std::destroy_at(it);
333 // This is only safe because exceptions are disabled.
334 return *construct_at(it, std::move(element));
335 }
336
337 template <typename... Args>
338 iterator emplace_back(Args&&... args) {
339 return &Impl::emplace_back(std::forward<Args>(args)...);
340 }
341
342 bool push_back(const value_type& v) {
343 Impl::push_back(v);
344 return true;
345 }
346
347 bool push_back(value_type&& v) {
348 Impl::push_back(std::move(v));
349 return true;
350 }
351
352 using Impl::pop_back;
353
354 void unstable_erase(iterator it) {
355 if (it != last()) std::iter_swap(it, last());
356 pop_back();
357 }
358
359 void swap(SmallVector& other) { Impl::swap(other); }
360};
361
362template <typename>
363struct IsSmallVector : std::false_type {};
364
365template <typename T, size_t N>
366struct IsSmallVector<SmallVector<T, N>> : std::true_type {};
367
368// Deduction guide for array constructor.
369template <typename T, size_t N>
370SmallVector(T (&)[N]) -> SmallVector<std::remove_cv_t<T>, N>;
371
372// Deduction guide for variadic constructor.
373template <typename T, typename... Us, typename V = std::decay_t<T>,
374 typename = std::enable_if_t<(std::is_constructible_v<V, Us> && ...)>>
375SmallVector(T&&, Us&&...) -> SmallVector<V, 1 + sizeof...(Us)>;
376
377// Deduction guide for in-place constructor.
Dominik Laskowskiccd50a42020-10-30 19:56:38 -0700378template <typename T, size_t... Sizes, typename... Types>
379SmallVector(InitializerList<T, std::index_sequence<Sizes...>, Types...>&&)
380 -> SmallVector<T, sizeof...(Sizes)>;
Dominik Laskowski0bacf272020-10-22 14:08:27 -0700381
382// Deduction guide for StaticVector conversion.
383template <typename T, size_t N>
384SmallVector(StaticVector<T, N>&&) -> SmallVector<T, N>;
385
386template <typename T, size_t N>
387inline void swap(SmallVector<T, N>& lhs, SmallVector<T, N>& rhs) {
388 lhs.swap(rhs);
389}
390
391} // namespace android::ftl