1 // Copyright 2016 The Android Open Source Project
3 // This software is licensed under the terms of the GNU General Public
4 // License version 2, as published by the Free Software Foundation, and
5 // may be copied, distributed, and modified under those terms.
7 // This program is distributed in the hope that it will be useful,
8 // but WITHOUT ANY WARRANTY; without even the implied warranty of
9 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 // GNU General Public License for more details.
14 #include "anbox/common/type_traits.h"
17 #include <initializer_list>
19 #include <type_traits>
26 // SmallVector<T>, SmallFixedVector<T, SmallSize>
28 // This header defines a replacement for a std::vector<> that uses small buffer
29 // optimization technique - for some preset number of elements |SmallSize| it
30 // stores them inside of the object, and falls back to the dynamically allocated
31 // array only if one needs to add more elements.
32 // This is useful for the performance-critical places where common number of
33 // processed items is small, but it may still be quite large for a stack array.
35 // SmallFixedVector<> is the class you use to store elements, while
36 // SmallVector<> is its base class that erases the small size from the type.
38 // NOTE: SmallVector<> cannot guarantee std::vector<>'s iterator invalidation
39 // rules for move() and swap() operations - std::vector<>s just exchange
40 // their iterators on swap() and pass the moved ones over, while SmallVector<>
41 // may leave the iterators pointing to nowhere if they were for the in-place
44 // Currenly only a limited subset of std::vector<>'s operations is implemented,
45 // but fill free to add the ones you need.
52 // Forward-declare the 'real' small vector class.
53 template <class T, size_t S>
54 class SmallFixedVector;
57 // SmallVector<T> - an interface for a small-buffer-optimized vector.
58 // It hides the fixed size from its type, so one can use it to pass small
59 // vectors around and not leak the buffer size to all callers:
61 // void process(SmallVector<Foo>& data);
64 // SmallFixedVector<Foo, 100> aLittleBitOfFoos = ...;
65 // process(aLittleBitOfFoos);
67 // SmallFixedVector<Foo, 1000> moreFoos = ...;
72 // Make them friends so SmallFixedVector is able to refer to SmallVector's
73 // protected members in static_assert()s.
74 template <class U, size_t S>
75 friend class SmallFixedVector;
78 // Common set of type aliases.
81 using const_iterator = const T*;
83 using const_pointer = const T*;
85 using const_reference = const T&;
86 using size_type = size_t;
88 // It's ok to delete SmallVector<> through the base class - dtor() actually
89 // takes care of all living elements and the allocated memory.
90 ~SmallVector() { dtor(); }
92 // std::vector<> interface operations.
93 iterator begin() { return mBegin; }
94 const_iterator begin() const { return mBegin; }
95 const_iterator cbegin() const { return mBegin; }
97 iterator end() { return mEnd; }
98 const_iterator end() const { return mEnd; }
99 const_iterator cend() const { return mEnd; }
101 size_type size() const { return end() - begin(); }
102 size_type capacity() const { return mCapacity; }
103 bool empty() const { return begin() == end(); }
105 reference operator[](size_t i) { return *(begin() + i); }
106 const_reference operator[](size_t i) const { return *(cbegin() + i); }
108 pointer data() { return mBegin; }
109 const_pointer data() const { return mBegin; }
110 const_pointer cdata() const { return mBegin; }
112 template <class... Args>
113 void emplace_back(Args&&... args) {
114 grow_for_size(size() + 1);
115 new (mEnd) T(std::forward<Args>(args)...);
119 void push_back(const T& t) { emplace_back(t); }
120 void push_back(T&& t) { emplace_back(std::move(t)); }
123 destruct(begin(), end());
127 void reserve(size_type newCap) {
128 if (newCap <= this->capacity()) {
131 set_capacity(newCap);
134 void resize(size_type newSize) { resize_impl<true>(newSize); }
136 // This version of resizing doesn't initialize the newly allocated elements
137 // Useful for the cases when value-initialization is noticeably slow and
138 // one wants to directly construct or memcpy the elements into the resized
140 void resize_noinit(size_type newSize) { resize_impl<false>(newSize); }
142 // Returns if the current vector's buffer is dynamically allocated.
143 bool isAllocated() const { return this->cbegin() != smallBufferStart(); }
146 // Hide the default constructor so only SmallFixedVector can be
148 SmallVector() = default;
150 // Destroy all elements in the vector and free the array if it was allocated
153 this->destruct(this->begin(), this->end());
159 // Just a convenience setter function to init all members at once.
160 void init(iterator begin, iterator end, size_type capacity) {
161 this->mBegin = begin;
163 this->mCapacity = capacity;
166 // An implementation of different resizing versions.
168 void resize_impl(size_type newSize) {
169 if (newSize < this->size()) {
170 const auto newEnd = this->begin() + newSize;
171 this->destruct(newEnd, this->end());
173 } else if (newSize > this->size()) {
174 grow_for_size(newSize);
175 const auto newEnd = this->begin() + newSize;
177 std::uninitialized_fill(this->end(), newEnd, T());
183 // Templated append operation for a range of elements.
184 template <class Iter>
185 void insert_back(Iter b, Iter e) {
189 const auto newSize = this->size() + (e - b);
190 grow_for_size(newSize);
191 this->mEnd = std::uninitialized_copy(b, e, this->mEnd);
194 // Multiplicative grow for the internal array so it can hold |newSize|
196 // Doesn't change size(), only capacity().
197 void grow_for_size(size_type newSize) {
198 // Grow by 1.5x by default.
199 if (newSize > capacity()) {
200 set_capacity(std::max(newSize, capacity() + capacity() / 2));
204 // Sets the capacity() to be exacly |newCap|. Allocates the array
205 // dynamically, moves all elements over and (potentially) deallocates the
207 // Doesn't change size(), only capacity().
208 void set_capacity(size_type newCap) {
209 // Here we can only be switching to the dynamic vector, as static one
210 // always has its capacity on the maximum.
211 const auto newBegin = static_cast<T*>(malloc(sizeof(T) * newCap));
213 abort(); // what else can we do here?
216 std::uninitialized_copy(std::make_move_iterator(this->begin()),
217 std::make_move_iterator(this->end()), newBegin);
219 this->mBegin = newBegin;
221 this->mCapacity = newCap;
224 // A convenience function to call destructor for a range of elements.
225 static void destruct(T* b, T* e) {
226 if (!std::is_trivially_destructible<T>::value) {
227 for (; b != e; ++b) {
233 // By design of the class, SmallFixedVector<> will be inheriting from
234 // SmallVector<>, so its in-place storage array is going to be the very next
235 // member after the last one here.
236 // This function returns that address, and SmallFixedVector<> has a static
237 // assert to make sure it remains correct.
238 constexpr const void* smallBufferStart() const {
239 return static_cast<const void*>(&mCapacity + 1);
242 // Standard set of members for a vector - begin, end and capacity.
243 // These point to the currently used chunk of memory, no matter if it's a
244 // heap-allocated one or an in-place array.
250 // The implementation of a SmallVector with a fixed in-place size, |SmallSize|.
251 template <class T, size_t SmallSize>
252 class SmallFixedVector : public SmallVector<T> {
253 using base = SmallVector<T>;
256 // Grab these from the base class.
257 using value_type = typename base::value_type;
258 using iterator = typename base::iterator;
259 using const_iterator = typename base::const_iterator;
260 using pointer = typename base::pointer;
261 using const_pointer = typename base::const_pointer;
262 using reference = typename base::reference;
263 using const_reference = typename base::const_reference;
264 using size_type = typename base::size_type;
266 static constexpr size_type kSmallSize = SmallSize;
268 // Default constructor - set up an empty vector with capacity at full
269 // internal array size.
274 // Ctor from a range of iterators
275 template <class Iter>
276 SmallFixedVector(Iter b, Iter e) : SmallFixedVector() {
277 this->insert_back(b, e);
280 // Ctor from a range - anything that has begin and end.
281 // Note: template constructor is never a copy/move-ctor.
282 template <class Range, class = enable_if_c<!std::is_same<Range, T>::value &&
283 is_range<Range>::value>>
284 explicit SmallFixedVector(const Range& r)
285 : SmallFixedVector(std::begin(r), std::end(r)) {}
286 template <class Range, class = enable_if_c<!std::is_same<Range, T>::value &&
287 is_range<Range>::value>>
288 explicit SmallFixedVector(Range&& r)
289 : SmallFixedVector(std::make_move_iterator(std::begin(r)),
290 std::make_move_iterator(std::end(r))) {}
291 template <class U, class = enable_if_convertible<U, T>>
292 SmallFixedVector(std::initializer_list<U> list)
293 : SmallFixedVector(std::begin(list), std::end(list)) {}
295 SmallFixedVector(const SmallFixedVector& other)
296 : SmallFixedVector(other.begin(), other.end()) {}
298 SmallFixedVector(SmallFixedVector&& other) {
299 if (other.isAllocated()) {
300 // Just steal the allocated memory from the |other|.
301 this->mBegin = other.mBegin;
302 this->mEnd = other.mEnd;
303 this->mCapacity = other.mCapacity;
304 other.init_inplace();
306 // Have to move individual elements.
307 this->mBegin = mData.array;
308 this->mEnd = std::uninitialized_copy(
309 std::make_move_iterator(other.begin()),
310 std::make_move_iterator(other.end()), this->begin());
311 this->mCapacity = kSmallSize;
315 SmallFixedVector& operator=(const SmallFixedVector& other) {
316 if (&other != this) {
318 this->insert_back(other.begin(), other.end());
323 SmallFixedVector& operator=(SmallFixedVector&& other) {
324 if (other.isAllocated()) {
325 // Steal it and we're done.
327 this->mBegin = other.mBegin;
328 this->mEnd = other.mEnd;
329 this->mCapacity = other.mCapacity;
330 other.init_inplace();
334 if (this->isAllocated() && this->mCapacity < other.size()) {
335 // Not enough dynamic memory, switch to in-place.
339 // This could potentially be improved by move-assigning
340 // only needed items and destroying the rest, but
341 // destroy-all+construct-all is just simpler. For PODs it actually
342 // is even faster as it's always a single memcpy().
343 this->destruct(this->begin(), this->end());
346 // Move the whole |other| into the pre-cleaned memory
347 const auto newEnd = std::uninitialized_copy(
348 std::make_move_iterator(other.begin()),
349 std::make_move_iterator(other.end()), this->mBegin);
351 // |other| is valid as-is.
355 // Make sure we don't end up trying to move from an interface - it's just
356 // inefficient with the current code.
357 SmallFixedVector(base&& other) = delete;
358 SmallFixedVector& operator=(base&& other) = delete;
361 // A shortcut for initialization for in-place storage.
362 void init_inplace() { this->init(mData.array, mData.array, kSmallSize); }
364 // A union with empty constructor and destructor makes sure that the array
365 // elements are not default-constructed in ctor and not destructed in dtor:
366 // the class needs to be able manage their lifetime more precisely.
368 alignas(size_type) T array[kSmallSize];
375 } // namespace common