blob: b632bb23743f0829a674ebd1b3eb37a573a2aa03 [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//
67template <typename T, size_t N>
68class SmallVector final : ArrayTraits<T>, ArrayComparators<SmallVector> {
69 using Static = StaticVector<T, N>;
70 using Dynamic = SmallVector<T, 0>;
71
72 // TODO: Replace with std::remove_cvref_t in C++20.
73 template <typename U>
74 using remove_cvref_t = std::remove_cv_t<std::remove_reference_t<U>>;
75
76public:
77 FTL_ARRAY_TRAIT(T, value_type);
78 FTL_ARRAY_TRAIT(T, size_type);
79 FTL_ARRAY_TRAIT(T, difference_type);
80
81 FTL_ARRAY_TRAIT(T, pointer);
82 FTL_ARRAY_TRAIT(T, reference);
83 FTL_ARRAY_TRAIT(T, iterator);
84 FTL_ARRAY_TRAIT(T, reverse_iterator);
85
86 FTL_ARRAY_TRAIT(T, const_pointer);
87 FTL_ARRAY_TRAIT(T, const_reference);
88 FTL_ARRAY_TRAIT(T, const_iterator);
89 FTL_ARRAY_TRAIT(T, const_reverse_iterator);
90
91 // Creates an empty vector.
92 SmallVector() = default;
93
94 // Constructs at most N elements. See StaticVector for underlying constructors.
95 template <typename Arg, typename... Args,
96 typename = std::enable_if_t<!IsSmallVector<remove_cvref_t<Arg>>{}>>
97 SmallVector(Arg&& arg, Args&&... args)
98 : mVector(std::in_place_type<Static>, std::forward<Arg>(arg),
99 std::forward<Args>(args)...) {}
100
101 // Copies at most N elements from a smaller convertible vector.
102 template <typename U, size_t M, typename = std::enable_if_t<M <= N>>
103 SmallVector(const SmallVector<U, M>& other)
104 : SmallVector(IteratorRange, other.begin(), other.end()) {}
105
106 void swap(SmallVector& other) { mVector.swap(other.mVector); }
107
108 // Returns whether the vector is backed by static or dynamic storage.
109 bool dynamic() const { return std::holds_alternative<Dynamic>(mVector); }
110
111#define VISITOR(T, F, ...) \
112 T F() __VA_ARGS__ { \
113 return std::visit([](auto&& v) -> T { return v.F(); }, mVector); \
114 }
115
116 VISITOR(size_type, max_size, const)
117 VISITOR(size_type, size, const)
118 VISITOR(bool, empty, const)
119
120 // noexcept to suppress warning about zero variadic macro arguments.
121 VISITOR(iterator, begin, noexcept)
122 VISITOR(const_iterator, begin, const)
123 VISITOR(const_iterator, cbegin, const)
124
125 VISITOR(iterator, end, noexcept)
126 VISITOR(const_iterator, end, const)
127 VISITOR(const_iterator, cend, const)
128
129 VISITOR(reverse_iterator, rbegin, noexcept)
130 VISITOR(const_reverse_iterator, rbegin, const)
131 VISITOR(const_reverse_iterator, crbegin, const)
132
133 VISITOR(reverse_iterator, rend, noexcept)
134 VISITOR(const_reverse_iterator, rend, const)
135 VISITOR(const_reverse_iterator, crend, const)
136
137 VISITOR(iterator, last, noexcept)
138 VISITOR(const_iterator, last, const)
139
140 VISITOR(reference, front, noexcept)
141 VISITOR(const_reference, front, const)
142
143 VISITOR(reference, back, noexcept)
144 VISITOR(const_reference, back, const)
145
146#undef VISITOR
147
148 reference operator[](size_type i) {
149 return std::visit([i](auto& v) -> reference { return v[i]; }, mVector);
150 }
151
152 const_reference operator[](size_type i) const {
153 return std::visit([i](const auto& v) -> const_reference { return v[i]; }, mVector);
154 }
155
156 // Replaces an element, and returns a reference to it. The iterator must be dereferenceable, so
157 // replacing at end() is erroneous.
158 //
159 // The element is emplaced via move constructor, so type T does not need to define copy/move
160 // assignment, e.g. its data members may be const.
161 //
162 // The arguments may directly or indirectly refer to the element being replaced.
163 //
164 // Iterators to the replaced element point to its replacement, and others remain valid.
165 //
166 template <typename... Args>
167 reference replace(const_iterator it, Args&&... args) {
168 return std::
169 visit([it, &args...](auto& v)
170 -> reference { return v.replace(it, std::forward<Args>(args)...); },
171 mVector);
172 }
173
174 // Appends an element, and returns a reference to it.
175 //
176 // If the vector reaches its static or dynamic capacity, then all iterators are invalidated.
177 // Otherwise, only the end() iterator is invalidated.
178 //
179 template <typename... Args>
180 reference emplace_back(Args&&... args) {
181 constexpr auto insertStatic = &Static::template emplace_back<Args...>;
182 constexpr auto insertDynamic = &Dynamic::template emplace_back<Args...>;
183 return *insert<insertStatic, insertDynamic>(std::forward<Args>(args)...);
184 }
185
186 // Appends an element.
187 //
188 // If the vector reaches its static or dynamic capacity, then all iterators are invalidated.
189 // Otherwise, only the end() iterator is invalidated.
190 //
191 void push_back(const value_type& v) {
192 constexpr auto insertStatic =
193 static_cast<bool (Static::*)(const value_type&)>(&Static::push_back);
194 constexpr auto insertDynamic =
195 static_cast<bool (Dynamic::*)(const value_type&)>(&Dynamic::push_back);
196 insert<insertStatic, insertDynamic>(v);
197 }
198
199 void push_back(value_type&& v) {
200 constexpr auto insertStatic =
201 static_cast<bool (Static::*)(value_type&&)>(&Static::push_back);
202 constexpr auto insertDynamic =
203 static_cast<bool (Dynamic::*)(value_type&&)>(&Dynamic::push_back);
204 insert<insertStatic, insertDynamic>(std::move(v));
205 }
206
207 // Removes the last element. The vector must not be empty, or the call is erroneous.
208 //
209 // The last() and end() iterators are invalidated.
210 //
211 void pop_back() {
212 std::visit([](auto& v) { v.pop_back(); }, mVector);
213 }
214
215 // Erases an element, but does not preserve order. Rather than shifting subsequent elements,
216 // this moves the last element to the slot of the erased element.
217 //
218 // The last() and end() iterators, as well as those to the erased element, are invalidated.
219 //
220 void unstable_erase(iterator it) {
221 std::visit([it](auto& v) { v.unstable_erase(it); }, mVector);
222 }
223
224private:
225 template <typename... Vs>
226 struct Visitor : Vs... {};
227
228 // TODO: Remove this deduction guide in C++20.
229 template <typename... Vs>
230 Visitor(Vs...) -> Visitor<Vs...>;
231
232 template <auto insertStatic, auto insertDynamic, typename... Args>
233 auto insert(Args&&... args) {
234 return std::visit(Visitor{[this, &args...](Static& vector) {
235 if (vector.full()) {
236 return (promote(vector).*
237 insertDynamic)(std::forward<Args>(args)...);
238 }
239
240 return (vector.*insertStatic)(std::forward<Args>(args)...);
241 },
242 [&args...](Dynamic& vector) {
243 return (vector.*insertDynamic)(std::forward<Args>(args)...);
244 }},
245 mVector);
246 }
247
248 Dynamic& promote(Static& staticVector) {
249 assert(staticVector.full());
250
251 // Allocate double capacity to reduce probability of reallocation.
252 Dynamic vector;
253 vector.reserve(Static::max_size() * 2);
254 std::move(staticVector.begin(), staticVector.end(), std::back_inserter(vector));
255
256 return mVector.template emplace<Dynamic>(std::move(vector));
257 }
258
259 std::variant<Static, Dynamic> mVector;
260};
261
262// Partial specialization without static storage.
263template <typename T>
264class SmallVector<T, 0> final : ArrayTraits<T>,
265 ArrayIterators<SmallVector<T, 0>, T>,
266 std::vector<T> {
267 using ArrayTraits<T>::construct_at;
268
269 using Iter = ArrayIterators<SmallVector, T>;
270 using Impl = std::vector<T>;
271
272 friend Iter;
273
274public:
275 FTL_ARRAY_TRAIT(T, value_type);
276 FTL_ARRAY_TRAIT(T, size_type);
277 FTL_ARRAY_TRAIT(T, difference_type);
278
279 FTL_ARRAY_TRAIT(T, pointer);
280 FTL_ARRAY_TRAIT(T, reference);
281 FTL_ARRAY_TRAIT(T, iterator);
282 FTL_ARRAY_TRAIT(T, reverse_iterator);
283
284 FTL_ARRAY_TRAIT(T, const_pointer);
285 FTL_ARRAY_TRAIT(T, const_reference);
286 FTL_ARRAY_TRAIT(T, const_iterator);
287 FTL_ARRAY_TRAIT(T, const_reverse_iterator);
288
289 using Impl::Impl;
290
291 using Impl::empty;
292 using Impl::max_size;
293 using Impl::size;
294
295 using Impl::reserve;
296
297 // std::vector iterators are not necessarily raw pointers.
298 iterator begin() { return Impl::data(); }
299 iterator end() { return Impl::data() + size(); }
300
301 using Iter::begin;
302 using Iter::end;
303
304 using Iter::cbegin;
305 using Iter::cend;
306
307 using Iter::rbegin;
308 using Iter::rend;
309
310 using Iter::crbegin;
311 using Iter::crend;
312
313 using Iter::last;
314
315 using Iter::back;
316 using Iter::front;
317
318 using Iter::operator[];
319
320 template <typename... Args>
321 reference replace(const_iterator it, Args&&... args) {
322 value_type element{std::forward<Args>(args)...};
323 std::destroy_at(it);
324 // This is only safe because exceptions are disabled.
325 return *construct_at(it, std::move(element));
326 }
327
328 template <typename... Args>
329 iterator emplace_back(Args&&... args) {
330 return &Impl::emplace_back(std::forward<Args>(args)...);
331 }
332
333 bool push_back(const value_type& v) {
334 Impl::push_back(v);
335 return true;
336 }
337
338 bool push_back(value_type&& v) {
339 Impl::push_back(std::move(v));
340 return true;
341 }
342
343 using Impl::pop_back;
344
345 void unstable_erase(iterator it) {
346 if (it != last()) std::iter_swap(it, last());
347 pop_back();
348 }
349
350 void swap(SmallVector& other) { Impl::swap(other); }
351};
352
353template <typename>
354struct IsSmallVector : std::false_type {};
355
356template <typename T, size_t N>
357struct IsSmallVector<SmallVector<T, N>> : std::true_type {};
358
359// Deduction guide for array constructor.
360template <typename T, size_t N>
361SmallVector(T (&)[N]) -> SmallVector<std::remove_cv_t<T>, N>;
362
363// Deduction guide for variadic constructor.
364template <typename T, typename... Us, typename V = std::decay_t<T>,
365 typename = std::enable_if_t<(std::is_constructible_v<V, Us> && ...)>>
366SmallVector(T&&, Us&&...) -> SmallVector<V, 1 + sizeof...(Us)>;
367
368// Deduction guide for in-place constructor.
369template <typename T, typename... Us>
370SmallVector(std::in_place_type_t<T>, Us&&...) -> SmallVector<T, sizeof...(Us)>;
371
372// Deduction guide for StaticVector conversion.
373template <typename T, size_t N>
374SmallVector(StaticVector<T, N>&&) -> SmallVector<T, N>;
375
376template <typename T, size_t N>
377inline void swap(SmallVector<T, N>& lhs, SmallVector<T, N>& rhs) {
378 lhs.swap(rhs);
379}
380
381} // namespace android::ftl