prevector.h raw
1 // Copyright (c) 2015-2022 The Limenka developers
2 // Distributed under the MIT software license, see the accompanying
3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4
5 #ifndef LIMENKA_PREVECTOR_H
6 #define LIMENKA_PREVECTOR_H
7
8 #include <algorithm>
9 #include <cassert>
10 #include <cstddef>
11 #include <cstdint>
12 #include <cstdlib>
13 #include <cstring>
14 #include <iterator>
15 #include <type_traits>
16 #include <utility>
17
18 /** Implements a drop-in replacement for std::vector<T> which stores up to N
19 * elements directly (without heap allocation). The types Size and Diff are
20 * used to store element counts, and can be any unsigned + signed type.
21 *
22 * Storage layout is either:
23 * - Direct allocation:
24 * - Size _size: the number of used elements (between 0 and N)
25 * - T direct[N]: an array of N elements of type T
26 * (only the first _size are initialized).
27 * - Indirect allocation:
28 * - Size _size: the number of used elements plus N + 1
29 * - Size capacity: the number of allocated elements
30 * - T* indirect: a pointer to an array of capacity elements of type T
31 * (only the first _size are initialized).
32 *
33 * The data type T must be movable by memmove/realloc(). Once we switch to C++,
34 * move constructors can be used instead.
35 */
36 template<unsigned int N, typename T, typename Size = uint32_t, typename Diff = int32_t>
37 class prevector {
38 static_assert(std::is_trivially_copyable_v<T>);
39
40 public:
41 static constexpr unsigned int STATIC_SIZE{N};
42
43 typedef Size size_type;
44 typedef Diff difference_type;
45 typedef T value_type;
46 typedef value_type& reference;
47 typedef const value_type& const_reference;
48 typedef value_type* pointer;
49 typedef const value_type* const_pointer;
50
51 class iterator {
52 T* ptr{};
53 public:
54 typedef Diff difference_type;
55 typedef T* pointer;
56 typedef T& reference;
57 using element_type = T;
58 using iterator_category = std::contiguous_iterator_tag;
59 iterator() = default;
60 iterator(T* ptr_) : ptr(ptr_) {}
61 T& operator*() const { return *ptr; }
62 T* operator->() const { return ptr; }
63 T& operator[](size_type pos) const { return ptr[pos]; }
64 iterator& operator++() { ptr++; return *this; }
65 iterator& operator--() { ptr--; return *this; }
66 iterator operator++(int) { iterator copy(*this); ++(*this); return copy; }
67 iterator operator--(int) { iterator copy(*this); --(*this); return copy; }
68 difference_type friend operator-(iterator a, iterator b) { return (&(*a) - &(*b)); }
69 iterator operator+(size_type n) const { return iterator(ptr + n); }
70 iterator friend operator+(size_type n, iterator x) { return x + n; }
71 iterator& operator+=(size_type n) { ptr += n; return *this; }
72 iterator operator-(size_type n) const { return iterator(ptr - n); }
73 iterator& operator-=(size_type n) { ptr -= n; return *this; }
74 bool operator==(iterator x) const { return ptr == x.ptr; }
75 bool operator!=(iterator x) const { return ptr != x.ptr; }
76 bool operator>=(iterator x) const { return ptr >= x.ptr; }
77 bool operator<=(iterator x) const { return ptr <= x.ptr; }
78 bool operator>(iterator x) const { return ptr > x.ptr; }
79 bool operator<(iterator x) const { return ptr < x.ptr; }
80 };
81
82 class reverse_iterator {
83 T* ptr{};
84 public:
85 typedef Diff difference_type;
86 typedef T value_type;
87 typedef T* pointer;
88 typedef T& reference;
89 typedef std::bidirectional_iterator_tag iterator_category;
90 reverse_iterator() = default;
91 reverse_iterator(T* ptr_) : ptr(ptr_) {}
92 T& operator*() const { return *ptr; }
93 T* operator->() const { return ptr; }
94 reverse_iterator& operator--() { ptr++; return *this; }
95 reverse_iterator& operator++() { ptr--; return *this; }
96 reverse_iterator operator++(int) { reverse_iterator copy(*this); ++(*this); return copy; }
97 reverse_iterator operator--(int) { reverse_iterator copy(*this); --(*this); return copy; }
98 bool operator==(reverse_iterator x) const { return ptr == x.ptr; }
99 bool operator!=(reverse_iterator x) const { return ptr != x.ptr; }
100 };
101
102 class const_iterator {
103 const T* ptr{};
104 public:
105 typedef Diff difference_type;
106 typedef const T* pointer;
107 typedef const T& reference;
108 using element_type = const T;
109 using iterator_category = std::contiguous_iterator_tag;
110 const_iterator() = default;
111 const_iterator(const T* ptr_) : ptr(ptr_) {}
112 const_iterator(iterator x) : ptr(&(*x)) {}
113 const T& operator*() const { return *ptr; }
114 const T* operator->() const { return ptr; }
115 const T& operator[](size_type pos) const { return ptr[pos]; }
116 const_iterator& operator++() { ptr++; return *this; }
117 const_iterator& operator--() { ptr--; return *this; }
118 const_iterator operator++(int) { const_iterator copy(*this); ++(*this); return copy; }
119 const_iterator operator--(int) { const_iterator copy(*this); --(*this); return copy; }
120 difference_type friend operator-(const_iterator a, const_iterator b) { return (&(*a) - &(*b)); }
121 const_iterator operator+(size_type n) const { return const_iterator(ptr + n); }
122 const_iterator friend operator+(size_type n, const_iterator x) { return x + n; }
123 const_iterator& operator+=(size_type n) { ptr += n; return *this; }
124 const_iterator operator-(size_type n) const { return const_iterator(ptr - n); }
125 const_iterator& operator-=(size_type n) { ptr -= n; return *this; }
126 bool operator==(const_iterator x) const { return ptr == x.ptr; }
127 bool operator!=(const_iterator x) const { return ptr != x.ptr; }
128 bool operator>=(const_iterator x) const { return ptr >= x.ptr; }
129 bool operator<=(const_iterator x) const { return ptr <= x.ptr; }
130 bool operator>(const_iterator x) const { return ptr > x.ptr; }
131 bool operator<(const_iterator x) const { return ptr < x.ptr; }
132 };
133
134 class const_reverse_iterator {
135 const T* ptr{};
136 public:
137 typedef Diff difference_type;
138 typedef const T value_type;
139 typedef const T* pointer;
140 typedef const T& reference;
141 typedef std::bidirectional_iterator_tag iterator_category;
142 const_reverse_iterator() = default;
143 const_reverse_iterator(const T* ptr_) : ptr(ptr_) {}
144 const_reverse_iterator(reverse_iterator x) : ptr(&(*x)) {}
145 const T& operator*() const { return *ptr; }
146 const T* operator->() const { return ptr; }
147 const_reverse_iterator& operator--() { ptr++; return *this; }
148 const_reverse_iterator& operator++() { ptr--; return *this; }
149 const_reverse_iterator operator++(int) { const_reverse_iterator copy(*this); ++(*this); return copy; }
150 const_reverse_iterator operator--(int) { const_reverse_iterator copy(*this); --(*this); return copy; }
151 bool operator==(const_reverse_iterator x) const { return ptr == x.ptr; }
152 bool operator!=(const_reverse_iterator x) const { return ptr != x.ptr; }
153 };
154
155 private:
156 #pragma pack(push, 1)
157 union direct_or_indirect {
158 char direct[sizeof(T) * N];
159 struct {
160 char* indirect;
161 size_type capacity;
162 } indirect_contents;
163 };
164 #pragma pack(pop)
165 alignas(char*) direct_or_indirect _union = {};
166 size_type _size = 0;
167
168 static_assert(alignof(char*) % alignof(size_type) == 0 && sizeof(char*) % alignof(size_type) == 0, "size_type cannot have more restrictive alignment requirement than pointer");
169 static_assert(alignof(char*) % alignof(T) == 0, "value_type T cannot have more restrictive alignment requirement than pointer");
170
171 T* direct_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.direct) + pos; }
172 const T* direct_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.direct) + pos; }
173 T* indirect_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.indirect_contents.indirect) + pos; }
174 const T* indirect_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.indirect_contents.indirect) + pos; }
175 bool is_direct() const { return _size <= N; }
176
177 void change_capacity(size_type new_capacity) {
178 if (new_capacity <= N) {
179 if (!is_direct()) {
180 T* indirect = indirect_ptr(0);
181 T* src = indirect;
182 T* dst = direct_ptr(0);
183 memcpy(dst, src, size() * sizeof(T));
184 free(indirect);
185 _size -= N + 1;
186 }
187 } else {
188 if (!is_direct()) {
189 /* FIXME: Because malloc/realloc here won't call new_handler if allocation fails, assert
190 success. These should instead use an allocator or new/delete so that handlers
191 are called as necessary, but performance would be slightly degraded by doing so. */
192 _union.indirect_contents.indirect = static_cast<char*>(realloc(_union.indirect_contents.indirect, ((size_t)sizeof(T)) * new_capacity));
193 assert(_union.indirect_contents.indirect);
194 _union.indirect_contents.capacity = new_capacity;
195 } else {
196 char* new_indirect = static_cast<char*>(malloc(((size_t)sizeof(T)) * new_capacity));
197 assert(new_indirect);
198 T* src = direct_ptr(0);
199 T* dst = reinterpret_cast<T*>(new_indirect);
200 memcpy(dst, src, size() * sizeof(T));
201 _union.indirect_contents.indirect = new_indirect;
202 _union.indirect_contents.capacity = new_capacity;
203 _size += N + 1;
204 }
205 }
206 }
207
208 T* item_ptr(difference_type pos) { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
209 const T* item_ptr(difference_type pos) const { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
210
211 void fill(T* dst, ptrdiff_t count, const T& value = T{}) {
212 std::fill_n(dst, count, value);
213 }
214
215 template <std::input_iterator InputIterator>
216 void fill(T* dst, InputIterator first, InputIterator last) {
217 while (first != last) {
218 new(static_cast<void*>(dst)) T(*first);
219 ++dst;
220 ++first;
221 }
222 }
223
224 public:
225 void assign(size_type n, const T& val) {
226 clear();
227 if (capacity() < n) {
228 change_capacity(n);
229 }
230 _size += n;
231 fill(item_ptr(0), n, val);
232 }
233
234 template <std::input_iterator InputIterator>
235 void assign(InputIterator first, InputIterator last) {
236 size_type n = last - first;
237 clear();
238 if (capacity() < n) {
239 change_capacity(n);
240 }
241 _size += n;
242 fill(item_ptr(0), first, last);
243 }
244
245 prevector() = default;
246
247 explicit prevector(size_type n) {
248 resize(n);
249 }
250
251 explicit prevector(size_type n, const T& val) {
252 change_capacity(n);
253 _size += n;
254 fill(item_ptr(0), n, val);
255 }
256
257 template <std::input_iterator InputIterator>
258 prevector(InputIterator first, InputIterator last) {
259 size_type n = last - first;
260 change_capacity(n);
261 _size += n;
262 fill(item_ptr(0), first, last);
263 }
264
265 prevector(const prevector<N, T, Size, Diff>& other) {
266 size_type n = other.size();
267 change_capacity(n);
268 _size += n;
269 fill(item_ptr(0), other.begin(), other.end());
270 }
271
272 prevector(prevector<N, T, Size, Diff>&& other) noexcept
273 : _union(std::move(other._union)), _size(other._size)
274 {
275 other._size = 0;
276 }
277
278 prevector& operator=(const prevector<N, T, Size, Diff>& other) {
279 if (&other == this) {
280 return *this;
281 }
282 assign(other.begin(), other.end());
283 return *this;
284 }
285
286 prevector& operator=(prevector<N, T, Size, Diff>&& other) noexcept {
287 if (!is_direct()) {
288 free(_union.indirect_contents.indirect);
289 }
290 _union = std::move(other._union);
291 _size = other._size;
292 other._size = 0;
293 return *this;
294 }
295
296 size_type size() const {
297 return is_direct() ? _size : _size - N - 1;
298 }
299
300 bool empty() const {
301 return size() == 0;
302 }
303
304 iterator begin() { return iterator(item_ptr(0)); }
305 const_iterator begin() const { return const_iterator(item_ptr(0)); }
306 iterator end() { return iterator(item_ptr(size())); }
307 const_iterator end() const { return const_iterator(item_ptr(size())); }
308
309 reverse_iterator rbegin() { return reverse_iterator(item_ptr(size() - 1)); }
310 const_reverse_iterator rbegin() const { return const_reverse_iterator(item_ptr(size() - 1)); }
311 reverse_iterator rend() { return reverse_iterator(item_ptr(-1)); }
312 const_reverse_iterator rend() const { return const_reverse_iterator(item_ptr(-1)); }
313
314 size_t capacity() const {
315 if (is_direct()) {
316 return N;
317 } else {
318 return _union.indirect_contents.capacity;
319 }
320 }
321
322 T& operator[](size_type pos) {
323 return *item_ptr(pos);
324 }
325
326 const T& operator[](size_type pos) const {
327 return *item_ptr(pos);
328 }
329
330 void resize(size_type new_size) {
331 size_type cur_size = size();
332 if (cur_size == new_size) {
333 return;
334 }
335 if (cur_size > new_size) {
336 erase(item_ptr(new_size), end());
337 return;
338 }
339 if (new_size > capacity()) {
340 change_capacity(new_size);
341 }
342 ptrdiff_t increase = new_size - cur_size;
343 fill(item_ptr(cur_size), increase);
344 _size += increase;
345 }
346
347 void reserve(size_type new_capacity) {
348 if (new_capacity > capacity()) {
349 change_capacity(new_capacity);
350 }
351 }
352
353 void shrink_to_fit() {
354 change_capacity(size());
355 }
356
357 void clear() {
358 resize(0);
359 }
360
361 iterator insert(iterator pos, const T& value) {
362 size_type p = pos - begin();
363 size_type new_size = size() + 1;
364 if (capacity() < new_size) {
365 change_capacity(new_size + (new_size >> 1));
366 }
367 T* ptr = item_ptr(p);
368 T* dst = ptr + 1;
369 memmove(dst, ptr, (size() - p) * sizeof(T));
370 _size++;
371 new(static_cast<void*>(ptr)) T(value);
372 return iterator(ptr);
373 }
374
375 void insert(iterator pos, size_type count, const T& value) {
376 size_type p = pos - begin();
377 size_type new_size = size() + count;
378 if (capacity() < new_size) {
379 change_capacity(new_size + (new_size >> 1));
380 }
381 T* ptr = item_ptr(p);
382 T* dst = ptr + count;
383 memmove(dst, ptr, (size() - p) * sizeof(T));
384 _size += count;
385 fill(item_ptr(p), count, value);
386 }
387
388 template <std::input_iterator InputIterator>
389 void insert(iterator pos, InputIterator first, InputIterator last) {
390 size_type p = pos - begin();
391 difference_type count = last - first;
392 assert(count >= 0);
393 size_type new_size = size() + count;
394 if (capacity() < new_size) {
395 change_capacity(new_size + (new_size >> 1));
396 }
397 T* ptr = item_ptr(p);
398 T* dst = ptr + count;
399 memmove(dst, ptr, (size() - p) * sizeof(T));
400 _size += count;
401 fill(ptr, first, last);
402 }
403
404 inline void resize_uninitialized(size_type new_size) {
405 // resize_uninitialized changes the size of the prevector but does not initialize it.
406 // If size < new_size, the added elements must be initialized explicitly.
407 if (capacity() < new_size) {
408 change_capacity(new_size);
409 _size += new_size - size();
410 return;
411 }
412 if (new_size < size()) {
413 erase(item_ptr(new_size), end());
414 } else {
415 _size += new_size - size();
416 }
417 }
418
419 iterator erase(iterator pos) {
420 return erase(pos, pos + 1);
421 }
422
423 iterator erase(iterator first, iterator last) {
424 // Erase is not allowed to the change the object's capacity. That means
425 // that when starting with an indirectly allocated prevector with
426 // size and capacity > N, the result may be a still indirectly allocated
427 // prevector with size <= N and capacity > N. A shrink_to_fit() call is
428 // necessary to switch to the (more efficient) directly allocated
429 // representation (with capacity N and size <= N).
430 iterator p = first;
431 char* endp = (char*)&(*end());
432 _size -= last - p;
433 memmove(&(*first), &(*last), endp - ((char*)(&(*last))));
434 return first;
435 }
436
437 template<typename... Args>
438 void emplace_back(Args&&... args) {
439 size_type new_size = size() + 1;
440 if (capacity() < new_size) {
441 change_capacity(new_size + (new_size >> 1));
442 }
443 new(item_ptr(size())) T(std::forward<Args>(args)...);
444 _size++;
445 }
446
447 void push_back(const T& value) {
448 emplace_back(value);
449 }
450
451 void pop_back() {
452 erase(end() - 1, end());
453 }
454
455 T& front() {
456 return *item_ptr(0);
457 }
458
459 const T& front() const {
460 return *item_ptr(0);
461 }
462
463 T& back() {
464 return *item_ptr(size() - 1);
465 }
466
467 const T& back() const {
468 return *item_ptr(size() - 1);
469 }
470
471 void swap(prevector<N, T, Size, Diff>& other) noexcept
472 {
473 std::swap(_union, other._union);
474 std::swap(_size, other._size);
475 }
476
477 ~prevector() {
478 if (!is_direct()) {
479 free(_union.indirect_contents.indirect);
480 _union.indirect_contents.indirect = nullptr;
481 }
482 }
483
484 bool operator==(const prevector<N, T, Size, Diff>& other) const {
485 if (other.size() != size()) {
486 return false;
487 }
488 const_iterator b1 = begin();
489 const_iterator b2 = other.begin();
490 const_iterator e1 = end();
491 while (b1 != e1) {
492 if ((*b1) != (*b2)) {
493 return false;
494 }
495 ++b1;
496 ++b2;
497 }
498 return true;
499 }
500
501 bool operator!=(const prevector<N, T, Size, Diff>& other) const {
502 return !(*this == other);
503 }
504
505 bool operator<(const prevector<N, T, Size, Diff>& other) const {
506 if (size() < other.size()) {
507 return true;
508 }
509 if (size() > other.size()) {
510 return false;
511 }
512 const_iterator b1 = begin();
513 const_iterator b2 = other.begin();
514 const_iterator e1 = end();
515 while (b1 != e1) {
516 if ((*b1) < (*b2)) {
517 return true;
518 }
519 if ((*b2) < (*b1)) {
520 return false;
521 }
522 ++b1;
523 ++b2;
524 }
525 return false;
526 }
527
528 size_t allocated_memory() const {
529 if (is_direct()) {
530 return 0;
531 } else {
532 return ((size_t)(sizeof(T))) * _union.indirect_contents.capacity;
533 }
534 }
535
536 value_type* data() {
537 return item_ptr(0);
538 }
539
540 const value_type* data() const {
541 return item_ptr(0);
542 }
543 };
544
545 #endif // LIMENKA_PREVECTOR_H
546