prevector.h raw
1 // Copyright (c) 2015-present The Bitcoin Core 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 BITCOIN_PREVECTOR_H
6 #define BITCOIN_PREVECTOR_H
7
8 #include <algorithm>
9 #include <cassert>
10 #include <cstdint>
11 #include <cstdlib>
12 #include <cstring>
13 #include <iterator>
14 #include <new>
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 auto operator<=>(iterator x) const { return ptr <=> x.ptr; }
76 };
77
78 class const_iterator {
79 const T* ptr{};
80 public:
81 typedef Diff difference_type;
82 typedef const T* pointer;
83 typedef const T& reference;
84 using element_type = const T;
85 using iterator_category = std::contiguous_iterator_tag;
86 const_iterator() = default;
87 const_iterator(const T* ptr_) : ptr(ptr_) {}
88 const_iterator(iterator x) : ptr(&(*x)) {}
89 const T& operator*() const { return *ptr; }
90 const T* operator->() const { return ptr; }
91 const T& operator[](size_type pos) const { return ptr[pos]; }
92 const_iterator& operator++() { ptr++; return *this; }
93 const_iterator& operator--() { ptr--; return *this; }
94 const_iterator operator++(int) { const_iterator copy(*this); ++(*this); return copy; }
95 const_iterator operator--(int) { const_iterator copy(*this); --(*this); return copy; }
96 difference_type friend operator-(const_iterator a, const_iterator b) { return (&(*a) - &(*b)); }
97 const_iterator operator+(size_type n) const { return const_iterator(ptr + n); }
98 const_iterator friend operator+(size_type n, const_iterator x) { return x + n; }
99 const_iterator& operator+=(size_type n) { ptr += n; return *this; }
100 const_iterator operator-(size_type n) const { return const_iterator(ptr - n); }
101 const_iterator& operator-=(size_type n) { ptr -= n; return *this; }
102 bool operator==(const_iterator x) const { return ptr == x.ptr; }
103 auto operator<=>(const_iterator x) const { return ptr <=> x.ptr; }
104 };
105
106 private:
107 #pragma pack(push, 1)
108 union direct_or_indirect {
109 char direct[sizeof(T) * N];
110 struct {
111 char* indirect;
112 size_type capacity;
113 } indirect_contents;
114 };
115 #pragma pack(pop)
116 alignas(char*) direct_or_indirect _union = {};
117 size_type _size = 0;
118
119 static_assert(alignof(char*) % alignof(size_type) == 0 && sizeof(char*) % alignof(size_type) == 0, "size_type cannot have more restrictive alignment requirement than pointer");
120 static_assert(alignof(char*) % alignof(T) == 0, "value_type T cannot have more restrictive alignment requirement than pointer");
121
122 T* direct_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.direct) + pos; }
123 const T* direct_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.direct) + pos; }
124 T* indirect_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.indirect_contents.indirect) + pos; }
125 const T* indirect_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.indirect_contents.indirect) + pos; }
126 bool is_direct() const { return _size <= N; }
127
128 void change_capacity(size_type new_capacity) {
129 if (new_capacity <= N) {
130 if (!is_direct()) {
131 T* indirect = indirect_ptr(0);
132 T* src = indirect;
133 T* dst = direct_ptr(0);
134 memcpy(dst, src, size() * sizeof(T));
135 free(indirect);
136 _size -= N + 1;
137 }
138 } else {
139 if (!is_direct()) {
140 /* FIXME: Because malloc/realloc here won't call new_handler if allocation fails, assert
141 success. These should instead use an allocator or new/delete so that handlers
142 are called as necessary, but performance would be slightly degraded by doing so. */
143 _union.indirect_contents.indirect = static_cast<char*>(realloc(_union.indirect_contents.indirect, ((size_t)sizeof(T)) * new_capacity));
144 assert(_union.indirect_contents.indirect);
145 _union.indirect_contents.capacity = new_capacity;
146 } else {
147 char* new_indirect = static_cast<char*>(malloc(((size_t)sizeof(T)) * new_capacity));
148 assert(new_indirect);
149 T* src = direct_ptr(0);
150 T* dst = reinterpret_cast<T*>(new_indirect);
151 memcpy(dst, src, size() * sizeof(T));
152 _union.indirect_contents.indirect = new_indirect;
153 _union.indirect_contents.capacity = new_capacity;
154 _size += N + 1;
155 }
156 }
157 }
158
159 T* item_ptr(difference_type pos) { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
160 const T* item_ptr(difference_type pos) const { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
161
162 void fill(T* dst, ptrdiff_t count, const T& value = T{}) {
163 std::fill_n(dst, count, value);
164 }
165
166 template <std::input_iterator InputIterator>
167 void fill(T* dst, InputIterator first, InputIterator last) {
168 while (first != last) {
169 new(static_cast<void*>(dst)) T(*first);
170 ++dst;
171 ++first;
172 }
173 }
174
175 public:
176 void assign(size_type n, const T& val) {
177 clear();
178 if (capacity() < n) {
179 change_capacity(n);
180 }
181 _size += n;
182 fill(item_ptr(0), n, val);
183 }
184
185 template <std::input_iterator InputIterator>
186 void assign(InputIterator first, InputIterator last) {
187 size_type n = last - first;
188 clear();
189 if (capacity() < n) {
190 change_capacity(n);
191 }
192 _size += n;
193 fill(item_ptr(0), first, last);
194 }
195
196 prevector() = default;
197
198 explicit prevector(size_type n) {
199 resize(n);
200 }
201
202 explicit prevector(size_type n, const T& val) {
203 change_capacity(n);
204 _size += n;
205 fill(item_ptr(0), n, val);
206 }
207
208 template <std::input_iterator InputIterator>
209 prevector(InputIterator first, InputIterator last) {
210 size_type n = last - first;
211 change_capacity(n);
212 _size += n;
213 fill(item_ptr(0), first, last);
214 }
215
216 prevector(const prevector<N, T, Size, Diff>& other) {
217 size_type n = other.size();
218 change_capacity(n);
219 _size += n;
220 fill(item_ptr(0), other.begin(), other.end());
221 }
222
223 prevector(prevector<N, T, Size, Diff>&& other) noexcept
224 : _union(std::move(other._union)), _size(other._size)
225 {
226 other._size = 0;
227 }
228
229 prevector& operator=(const prevector<N, T, Size, Diff>& other) {
230 if (&other == this) {
231 return *this;
232 }
233 assign(other.begin(), other.end());
234 return *this;
235 }
236
237 prevector& operator=(prevector<N, T, Size, Diff>&& other) noexcept {
238 if (!is_direct()) {
239 free(_union.indirect_contents.indirect);
240 }
241 _union = std::move(other._union);
242 _size = other._size;
243 other._size = 0;
244 return *this;
245 }
246
247 size_type size() const {
248 return is_direct() ? _size : _size - N - 1;
249 }
250
251 bool empty() const {
252 return size() == 0;
253 }
254
255 iterator begin() { return iterator(item_ptr(0)); }
256 const_iterator begin() const { return const_iterator(item_ptr(0)); }
257 iterator end() { return iterator(item_ptr(size())); }
258 const_iterator end() const { return const_iterator(item_ptr(size())); }
259
260 size_t capacity() const {
261 if (is_direct()) {
262 return N;
263 } else {
264 return _union.indirect_contents.capacity;
265 }
266 }
267
268 T& operator[](size_type pos) {
269 return *item_ptr(pos);
270 }
271
272 const T& operator[](size_type pos) const {
273 return *item_ptr(pos);
274 }
275
276 void resize(size_type new_size) {
277 size_type cur_size = size();
278 if (cur_size == new_size) {
279 return;
280 }
281 if (cur_size > new_size) {
282 erase(item_ptr(new_size), end());
283 return;
284 }
285 if (new_size > capacity()) {
286 change_capacity(new_size);
287 }
288 ptrdiff_t increase = new_size - cur_size;
289 fill(item_ptr(cur_size), increase);
290 _size += increase;
291 }
292
293 void reserve(size_type new_capacity) {
294 if (new_capacity > capacity()) {
295 change_capacity(new_capacity);
296 }
297 }
298
299 void shrink_to_fit() {
300 change_capacity(size());
301 }
302
303 void clear() {
304 resize(0);
305 }
306
307 iterator insert(iterator pos, const T& value) {
308 size_type p = pos - begin();
309 size_type new_size = size() + 1;
310 if (capacity() < new_size) {
311 change_capacity(new_size + (new_size >> 1));
312 }
313 T* ptr = item_ptr(p);
314 T* dst = ptr + 1;
315 memmove(dst, ptr, (size() - p) * sizeof(T));
316 _size++;
317 new(static_cast<void*>(ptr)) T(value);
318 return iterator(ptr);
319 }
320
321 void insert(iterator pos, size_type count, const T& value) {
322 size_type p = pos - begin();
323 size_type new_size = size() + count;
324 if (capacity() < new_size) {
325 change_capacity(new_size + (new_size >> 1));
326 }
327 T* ptr = item_ptr(p);
328 T* dst = ptr + count;
329 memmove(dst, ptr, (size() - p) * sizeof(T));
330 _size += count;
331 fill(item_ptr(p), count, value);
332 }
333
334 template <std::input_iterator InputIterator>
335 void insert(iterator pos, InputIterator first, InputIterator last) {
336 size_type p = pos - begin();
337 difference_type count = last - first;
338 size_type new_size = size() + count;
339 if (capacity() < new_size) {
340 change_capacity(new_size + (new_size >> 1));
341 }
342 T* ptr = item_ptr(p);
343 T* dst = ptr + count;
344 memmove(dst, ptr, (size() - p) * sizeof(T));
345 _size += count;
346 fill(ptr, first, last);
347 }
348
349 inline void resize_uninitialized(size_type new_size) {
350 // resize_uninitialized changes the size of the prevector but does not initialize it.
351 // If size < new_size, the added elements must be initialized explicitly.
352 if (capacity() < new_size) {
353 change_capacity(new_size);
354 _size += new_size - size();
355 return;
356 }
357 if (new_size < size()) {
358 erase(item_ptr(new_size), end());
359 } else {
360 _size += new_size - size();
361 }
362 }
363
364 iterator erase(iterator pos) {
365 return erase(pos, pos + 1);
366 }
367
368 iterator erase(iterator first, iterator last) {
369 // Erase is not allowed to the change the object's capacity. That means
370 // that when starting with an indirectly allocated prevector with
371 // size and capacity > N, the result may be a still indirectly allocated
372 // prevector with size <= N and capacity > N. A shrink_to_fit() call is
373 // necessary to switch to the (more efficient) directly allocated
374 // representation (with capacity N and size <= N).
375 iterator p = first;
376 char* endp = (char*)&(*end());
377 _size -= last - p;
378 memmove(&(*first), &(*last), endp - ((char*)(&(*last))));
379 return first;
380 }
381
382 template<typename... Args>
383 void emplace_back(Args&&... args) {
384 size_type new_size = size() + 1;
385 if (capacity() < new_size) {
386 change_capacity(new_size + (new_size >> 1));
387 }
388 new(item_ptr(size())) T(std::forward<Args>(args)...);
389 _size++;
390 }
391
392 void push_back(const T& value) {
393 emplace_back(value);
394 }
395
396 void pop_back() {
397 erase(end() - 1, end());
398 }
399
400 T& front() {
401 return *item_ptr(0);
402 }
403
404 const T& front() const {
405 return *item_ptr(0);
406 }
407
408 T& back() {
409 return *item_ptr(size() - 1);
410 }
411
412 const T& back() const {
413 return *item_ptr(size() - 1);
414 }
415
416 void swap(prevector<N, T, Size, Diff>& other) noexcept
417 {
418 std::swap(_union, other._union);
419 std::swap(_size, other._size);
420 }
421
422 ~prevector() {
423 if (!is_direct()) {
424 free(_union.indirect_contents.indirect);
425 _union.indirect_contents.indirect = nullptr;
426 }
427 }
428
429 constexpr bool operator==(const prevector& other) const {
430 return std::ranges::equal(*this, other);
431 }
432
433 bool operator<(const prevector<N, T, Size, Diff>& other) const {
434 if (size() < other.size()) {
435 return true;
436 }
437 if (size() > other.size()) {
438 return false;
439 }
440 const_iterator b1 = begin();
441 const_iterator b2 = other.begin();
442 const_iterator e1 = end();
443 while (b1 != e1) {
444 if ((*b1) < (*b2)) {
445 return true;
446 }
447 if ((*b2) < (*b1)) {
448 return false;
449 }
450 ++b1;
451 ++b2;
452 }
453 return false;
454 }
455
456 size_t allocated_memory() const {
457 if (is_direct()) {
458 return 0;
459 } else {
460 return ((size_t)(sizeof(T))) * _union.indirect_contents.capacity;
461 }
462 }
463
464 value_type* data() {
465 return item_ptr(0);
466 }
467
468 const value_type* data() const {
469 return item_ptr(0);
470 }
471 };
472
473 #endif // BITCOIN_PREVECTOR_H
474