1 /*
2 * Copyright 2019 The libgav1 Authors
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 // libgav1::Vector implementation
18
19 #ifndef LIBGAV1_SRC_UTILS_VECTOR_H_
20 #define LIBGAV1_SRC_UTILS_VECTOR_H_
21
22 #include <cassert>
23 #include <cstddef>
24 #include <cstdlib>
25 #include <cstring>
26 #include <iterator>
27 #include <new>
28 #include <type_traits>
29 #include <utility>
30
31 #include "src/utils/compiler_attributes.h"
32
33 namespace libgav1 {
34 namespace internal {
35
36 static constexpr size_t kMinVectorAllocation = 16;
37
38 // Returns the smallest power of two greater or equal to 'value'.
NextPow2(size_t value)39 inline size_t NextPow2(size_t value) {
40 if (value == 0) return 0;
41 --value;
42 for (size_t i = 1; i < sizeof(size_t) * 8; i *= 2) value |= value >> i;
43 return value + 1;
44 }
45
46 // Returns the smallest capacity greater or equal to 'value'.
NextCapacity(size_t value)47 inline size_t NextCapacity(size_t value) {
48 if (value == 0) return 0;
49 if (value <= kMinVectorAllocation) return kMinVectorAllocation;
50 return NextPow2(value);
51 }
52
53 //------------------------------------------------------------------------------
54 // Data structure equivalent to std::vector but returning false and to its last
55 // valid state on memory allocation failure.
56 // std::vector with a custom allocator does not fill this need without
57 // exceptions.
58
59 template <typename T>
60 class VectorBase {
61 public:
62 using iterator = T*;
63 using const_iterator = const T*;
64
65 VectorBase() noexcept = default;
66 // Move only.
67 VectorBase(const VectorBase&) = delete;
68 VectorBase& operator=(const VectorBase&) = delete;
VectorBase(VectorBase && other)69 VectorBase(VectorBase&& other) noexcept
70 : items_(other.items_),
71 capacity_(other.capacity_),
72 num_items_(other.num_items_) {
73 other.items_ = nullptr;
74 other.capacity_ = 0;
75 other.num_items_ = 0;
76 }
77 VectorBase& operator=(VectorBase&& other) noexcept {
78 if (this != &other) {
79 clear();
80 free(items_);
81 items_ = other.items_;
82 capacity_ = other.capacity_;
83 num_items_ = other.num_items_;
84 other.items_ = nullptr;
85 other.capacity_ = 0;
86 other.num_items_ = 0;
87 }
88 return *this;
89 }
~VectorBase()90 ~VectorBase() {
91 clear();
92 free(items_);
93 }
94
95 // Reallocates just enough memory if needed so that 'new_cap' items can fit.
reserve(size_t new_cap)96 LIBGAV1_MUST_USE_RESULT bool reserve(size_t new_cap) {
97 if (capacity_ < new_cap) {
98 T* const new_items = static_cast<T*>(malloc(new_cap * sizeof(T)));
99 if (new_items == nullptr) return false;
100 if (num_items_ > 0) {
101 if (std::is_trivial<T>::value) {
102 // Cast |new_items| and |items_| to void* to avoid the GCC
103 // -Wclass-memaccess warning and additionally the
104 // bugprone-undefined-memory-manipulation clang-tidy warning. The
105 // memcpy is safe because T is a trivial type.
106 memcpy(static_cast<void*>(new_items),
107 static_cast<const void*>(items_), num_items_ * sizeof(T));
108 } else {
109 for (size_t i = 0; i < num_items_; ++i) {
110 new (&new_items[i]) T(std::move(items_[i]));
111 items_[i].~T();
112 }
113 }
114 }
115 free(items_);
116 items_ = new_items;
117 capacity_ = new_cap;
118 }
119 return true;
120 }
121
122 // Reallocates less memory so that only the existing items can fit.
shrink_to_fit()123 bool shrink_to_fit() {
124 if (capacity_ == num_items_) return true;
125 if (num_items_ == 0) {
126 free(items_);
127 items_ = nullptr;
128 capacity_ = 0;
129 return true;
130 }
131 const size_t previous_capacity = capacity_;
132 capacity_ = 0; // Force reserve() to allocate and copy.
133 if (reserve(num_items_)) return true;
134 capacity_ = previous_capacity;
135 return false;
136 }
137
138 // Constructs a new item by copy constructor. May reallocate if
139 // 'resize_if_needed'.
140 LIBGAV1_MUST_USE_RESULT bool push_back(const T& value,
141 bool resize_if_needed = true) {
142 if (num_items_ >= capacity_ &&
143 (!resize_if_needed ||
144 !reserve(internal::NextCapacity(num_items_ + 1)))) {
145 return false;
146 }
147 new (&items_[num_items_]) T(value);
148 ++num_items_;
149 return true;
150 }
151
152 // Constructs a new item by copy constructor. reserve() must have been called
153 // with a sufficient capacity.
154 //
155 // WARNING: No error checking is performed.
push_back_unchecked(const T & value)156 void push_back_unchecked(const T& value) {
157 assert(num_items_ < capacity_);
158 new (&items_[num_items_]) T(value);
159 ++num_items_;
160 }
161
162 // Constructs a new item by move constructor. May reallocate if
163 // 'resize_if_needed'.
164 LIBGAV1_MUST_USE_RESULT bool push_back(T&& value,
165 bool resize_if_needed = true) {
166 if (num_items_ >= capacity_ &&
167 (!resize_if_needed ||
168 !reserve(internal::NextCapacity(num_items_ + 1)))) {
169 return false;
170 }
171 new (&items_[num_items_]) T(std::move(value));
172 ++num_items_;
173 return true;
174 }
175
176 // Constructs a new item by move constructor. reserve() must have been called
177 // with a sufficient capacity.
178 //
179 // WARNING: No error checking is performed.
push_back_unchecked(T && value)180 void push_back_unchecked(T&& value) {
181 assert(num_items_ < capacity_);
182 new (&items_[num_items_]) T(std::move(value));
183 ++num_items_;
184 }
185
186 // Constructs a new item in place by forwarding the arguments args... to the
187 // constructor. May reallocate.
188 template <typename... Args>
emplace_back(Args &&...args)189 LIBGAV1_MUST_USE_RESULT bool emplace_back(Args&&... args) {
190 if (num_items_ >= capacity_ &&
191 !reserve(internal::NextCapacity(num_items_ + 1))) {
192 return false;
193 }
194 new (&items_[num_items_]) T(std::forward<Args>(args)...);
195 ++num_items_;
196 return true;
197 }
198
199 // Destructs the last item.
pop_back()200 void pop_back() {
201 --num_items_;
202 items_[num_items_].~T();
203 }
204
205 // Destructs the item at 'pos'.
erase(iterator pos)206 void erase(iterator pos) { erase(pos, pos + 1); }
207
208 // Destructs the items in [first,last).
erase(iterator first,iterator last)209 void erase(iterator first, iterator last) {
210 for (iterator it = first; it != last; ++it) it->~T();
211 if (last != end()) {
212 if (std::is_trivial<T>::value) {
213 // Cast |first| and |last| to void* to avoid the GCC
214 // -Wclass-memaccess warning and additionally the
215 // bugprone-undefined-memory-manipulation clang-tidy warning. The
216 // memmove is safe because T is a trivial type.
217 memmove(static_cast<void*>(first), static_cast<const void*>(last),
218 (end() - last) * sizeof(T));
219 } else {
220 for (iterator it_src = last, it_dst = first; it_src != end();
221 ++it_src, ++it_dst) {
222 new (it_dst) T(std::move(*it_src));
223 it_src->~T();
224 }
225 }
226 }
227 num_items_ -= std::distance(first, last);
228 }
229
230 // Destructs all the items.
clear()231 void clear() { erase(begin(), end()); }
232
233 // Destroys (including deallocating) all the items.
reset()234 void reset() {
235 clear();
236 if (!shrink_to_fit()) assert(false);
237 }
238
239 // Accessors
empty()240 bool empty() const { return (num_items_ == 0); }
size()241 size_t size() const { return num_items_; }
capacity()242 size_t capacity() const { return capacity_; }
243
data()244 T* data() { return items_; }
front()245 T& front() { return items_[0]; }
back()246 T& back() { return items_[num_items_ - 1]; }
247 T& operator[](size_t i) { return items_[i]; }
at(size_t i)248 T& at(size_t i) { return items_[i]; }
data()249 const T* data() const { return items_; }
front()250 const T& front() const { return items_[0]; }
back()251 const T& back() const { return items_[num_items_ - 1]; }
252 const T& operator[](size_t i) const { return items_[i]; }
at(size_t i)253 const T& at(size_t i) const { return items_[i]; }
254
begin()255 iterator begin() { return &items_[0]; }
begin()256 const_iterator begin() const { return &items_[0]; }
end()257 iterator end() { return &items_[num_items_]; }
end()258 const_iterator end() const { return &items_[num_items_]; }
259
swap(VectorBase & b)260 void swap(VectorBase& b) {
261 // Although not necessary here, adding "using std::swap;" and then calling
262 // swap() without namespace qualification is recommended. See Effective
263 // C++, Item 25.
264 using std::swap;
265 swap(items_, b.items_);
266 swap(capacity_, b.capacity_);
267 swap(num_items_, b.num_items_);
268 }
269
270 protected:
271 T* items_ = nullptr;
272 size_t capacity_ = 0;
273 size_t num_items_ = 0;
274 };
275
276 } // namespace internal
277
278 //------------------------------------------------------------------------------
279
280 // Vector class that does *NOT* construct the content on resize().
281 // Should be reserved to plain old data.
282 template <typename T>
283 class VectorNoCtor : public internal::VectorBase<T> {
284 public:
285 // Creates or destructs items so that 'new_num_items' exist.
286 // Allocated memory grows every power-of-two items.
resize(size_t new_num_items)287 LIBGAV1_MUST_USE_RESULT bool resize(size_t new_num_items) {
288 using super = internal::VectorBase<T>;
289 if (super::num_items_ < new_num_items) {
290 if (super::capacity_ < new_num_items) {
291 if (!super::reserve(internal::NextCapacity(new_num_items))) {
292 return false;
293 }
294 }
295 super::num_items_ = new_num_items;
296 } else {
297 while (super::num_items_ > new_num_items) {
298 --super::num_items_;
299 super::items_[super::num_items_].~T();
300 }
301 }
302 return true;
303 }
304 };
305
306 // This generic vector class will call the constructors.
307 template <typename T>
308 class Vector : public internal::VectorBase<T> {
309 public:
310 // Constructs or destructs items so that 'new_num_items' exist.
311 // Allocated memory grows every power-of-two items.
resize(size_t new_num_items)312 LIBGAV1_MUST_USE_RESULT bool resize(size_t new_num_items) {
313 using super = internal::VectorBase<T>;
314 if (super::num_items_ < new_num_items) {
315 if (super::capacity_ < new_num_items) {
316 if (!super::reserve(internal::NextCapacity(new_num_items))) {
317 return false;
318 }
319 }
320 while (super::num_items_ < new_num_items) {
321 new (&super::items_[super::num_items_]) T();
322 ++super::num_items_;
323 }
324 } else {
325 while (super::num_items_ > new_num_items) {
326 --super::num_items_;
327 super::items_[super::num_items_].~T();
328 }
329 }
330 return true;
331 }
332 };
333
334 //------------------------------------------------------------------------------
335
336 // Define non-member swap() functions in the namespace in which VectorNoCtor
337 // and Vector are implemented. See Effective C++, Item 25.
338
339 template <typename T>
swap(VectorNoCtor<T> & a,VectorNoCtor<T> & b)340 void swap(VectorNoCtor<T>& a, VectorNoCtor<T>& b) {
341 a.swap(b);
342 }
343
344 template <typename T>
swap(Vector<T> & a,Vector<T> & b)345 void swap(Vector<T>& a, Vector<T>& b) {
346 a.swap(b);
347 }
348
349 //------------------------------------------------------------------------------
350
351 } // namespace libgav1
352
353 #endif // LIBGAV1_SRC_UTILS_VECTOR_H_
354