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