Line data Source code
1 : // Copyright (c) 2015-2022 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 <assert.h>
9 : #include <cstdlib>
10 : #include <stdint.h>
11 : #include <string.h>
12 :
13 : #include <algorithm>
14 : #include <cstddef>
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 : typedef Size size_type;
42 : typedef Diff difference_type;
43 : typedef T value_type;
44 : typedef value_type& reference;
45 : typedef const value_type& const_reference;
46 : typedef value_type* pointer;
47 : typedef const value_type* const_pointer;
48 :
49 : class iterator {
50 : T* ptr;
51 : public:
52 : typedef Diff difference_type;
53 : typedef T value_type;
54 : typedef T* pointer;
55 : typedef T& reference;
56 : typedef std::random_access_iterator_tag iterator_category;
57 3733813 : iterator(T* ptr_) : ptr(ptr_) {}
58 23729215 : T& operator*() const { return *ptr; }
59 : T* operator->() const { return ptr; }
60 : T& operator[](size_type pos) { return ptr[pos]; }
61 : const T& operator[](size_type pos) const { return ptr[pos]; }
62 207733 : iterator& operator++() { ptr++; return *this; }
63 : iterator& operator--() { ptr--; return *this; }
64 : iterator operator++(int) { iterator copy(*this); ++(*this); return copy; }
65 : iterator operator--(int) { iterator copy(*this); --(*this); return copy; }
66 1426964 : difference_type friend operator-(iterator a, iterator b) { return (&(*a) - &(*b)); }
67 0 : iterator operator+(size_type n) { return iterator(ptr + n); }
68 : iterator& operator+=(size_type n) { ptr += n; return *this; }
69 0 : iterator operator-(size_type n) { return iterator(ptr - n); }
70 : iterator& operator-=(size_type n) { ptr -= n; return *this; }
71 : bool operator==(iterator x) const { return ptr == x.ptr; }
72 20750 : bool operator!=(iterator x) const { return ptr != x.ptr; }
73 : bool operator>=(iterator x) const { return ptr >= x.ptr; }
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 : };
78 :
79 : class reverse_iterator {
80 : T* ptr;
81 : public:
82 : typedef Diff difference_type;
83 : typedef T value_type;
84 : typedef T* pointer;
85 : typedef T& reference;
86 : typedef std::bidirectional_iterator_tag iterator_category;
87 : reverse_iterator(T* ptr_) : ptr(ptr_) {}
88 : T& operator*() { return *ptr; }
89 : const T& operator*() const { return *ptr; }
90 : T* operator->() { return ptr; }
91 : const T* operator->() const { return ptr; }
92 : reverse_iterator& operator--() { ptr++; return *this; }
93 : reverse_iterator& operator++() { ptr--; return *this; }
94 : reverse_iterator operator++(int) { reverse_iterator copy(*this); ++(*this); return copy; }
95 : reverse_iterator operator--(int) { reverse_iterator copy(*this); --(*this); return copy; }
96 : bool operator==(reverse_iterator x) const { return ptr == x.ptr; }
97 : bool operator!=(reverse_iterator x) const { return ptr != x.ptr; }
98 : };
99 :
100 : class const_iterator {
101 : const T* ptr;
102 : public:
103 : typedef Diff difference_type;
104 : typedef const T value_type;
105 : typedef const T* pointer;
106 : typedef const T& reference;
107 : typedef std::random_access_iterator_tag iterator_category;
108 20138266 : const_iterator(const T* ptr_) : ptr(ptr_) {}
109 0 : const_iterator(iterator x) : ptr(&(*x)) {}
110 188761130 : const T& operator*() const { return *ptr; }
111 : const T* operator->() const { return ptr; }
112 0 : const T& operator[](size_type pos) const { return ptr[pos]; }
113 170571118 : const_iterator& operator++() { ptr++; return *this; }
114 0 : const_iterator& operator--() { ptr--; return *this; }
115 348759 : const_iterator operator++(int) { const_iterator copy(*this); ++(*this); return copy; }
116 : const_iterator operator--(int) { const_iterator copy(*this); --(*this); return copy; }
117 3274506 : difference_type friend operator-(const_iterator a, const_iterator b) { return (&(*a) - &(*b)); }
118 770432 : const_iterator operator+(size_type n) { return const_iterator(ptr + n); }
119 275198 : const_iterator& operator+=(size_type n) { ptr += n; return *this; }
120 0 : const_iterator operator-(size_type n) { return const_iterator(ptr - n); }
121 : const_iterator& operator-=(size_type n) { ptr -= n; return *this; }
122 0 : bool operator==(const_iterator x) const { return ptr == x.ptr; }
123 121417087 : bool operator!=(const_iterator x) const { return ptr != x.ptr; }
124 348759 : bool operator>=(const_iterator x) const { return ptr >= x.ptr; }
125 : bool operator<=(const_iterator x) const { return ptr <= x.ptr; }
126 : bool operator>(const_iterator x) const { return ptr > x.ptr; }
127 2106081 : bool operator<(const_iterator x) const { return ptr < x.ptr; }
128 : };
129 :
130 : class const_reverse_iterator {
131 : const T* ptr;
132 : public:
133 : typedef Diff difference_type;
134 : typedef const T value_type;
135 : typedef const T* pointer;
136 : typedef const T& reference;
137 : typedef std::bidirectional_iterator_tag iterator_category;
138 0 : const_reverse_iterator(const T* ptr_) : ptr(ptr_) {}
139 : const_reverse_iterator(reverse_iterator x) : ptr(&(*x)) {}
140 0 : const T& operator*() const { return *ptr; }
141 : const T* operator->() const { return ptr; }
142 : const_reverse_iterator& operator--() { ptr++; return *this; }
143 0 : const_reverse_iterator& operator++() { ptr--; return *this; }
144 : const_reverse_iterator operator++(int) { const_reverse_iterator copy(*this); ++(*this); return copy; }
145 : const_reverse_iterator operator--(int) { const_reverse_iterator copy(*this); --(*this); return copy; }
146 : bool operator==(const_reverse_iterator x) const { return ptr == x.ptr; }
147 0 : bool operator!=(const_reverse_iterator x) const { return ptr != x.ptr; }
148 : };
149 :
150 : private:
151 : #pragma pack(push, 1)
152 : union direct_or_indirect {
153 : char direct[sizeof(T) * N];
154 : struct {
155 : char* indirect;
156 : size_type capacity;
157 : } indirect_contents;
158 : };
159 : #pragma pack(pop)
160 6457232 : alignas(char*) direct_or_indirect _union = {};
161 6457232 : size_type _size = 0;
162 :
163 : static_assert(alignof(char*) % alignof(size_type) == 0 && sizeof(char*) % alignof(size_type) == 0, "size_type cannot have more restrictive alignment requirement than pointer");
164 : static_assert(alignof(char*) % alignof(T) == 0, "value_type T cannot have more restrictive alignment requirement than pointer");
165 :
166 7455000 : T* direct_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.direct) + pos; }
167 6390850 : const T* direct_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.direct) + pos; }
168 4874165 : T* indirect_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.indirect_contents.indirect) + pos; }
169 24455781 : const T* indirect_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.indirect_contents.indirect) + pos; }
170 122718406 : bool is_direct() const { return _size <= N; }
171 :
172 4958703 : void change_capacity(size_type new_capacity) {
173 4958703 : if (new_capacity <= N) {
174 2004064 : if (!is_direct()) {
175 7332 : T* indirect = indirect_ptr(0);
176 7332 : T* src = indirect;
177 7332 : T* dst = direct_ptr(0);
178 7332 : memcpy(dst, src, size() * sizeof(T));
179 7332 : free(indirect);
180 7332 : _size -= N + 1;
181 7332 : }
182 2004064 : } else {
183 2954639 : if (!is_direct()) {
184 : /* FIXME: Because malloc/realloc here won't call new_handler if allocation fails, assert
185 : success. These should instead use an allocator or new/delete so that handlers
186 : are called as necessary, but performance would be slightly degraded by doing so. */
187 39717 : _union.indirect_contents.indirect = static_cast<char*>(realloc(_union.indirect_contents.indirect, ((size_t)sizeof(T)) * new_capacity));
188 39717 : assert(_union.indirect_contents.indirect);
189 39717 : _union.indirect_contents.capacity = new_capacity;
190 39717 : } else {
191 2914922 : char* new_indirect = static_cast<char*>(malloc(((size_t)sizeof(T)) * new_capacity));
192 2914922 : assert(new_indirect);
193 2914922 : T* src = direct_ptr(0);
194 2914922 : T* dst = reinterpret_cast<T*>(new_indirect);
195 2914922 : memcpy(dst, src, size() * sizeof(T));
196 2914922 : _union.indirect_contents.indirect = new_indirect;
197 2914922 : _union.indirect_contents.capacity = new_capacity;
198 2914922 : _size += N + 1;
199 : }
200 : }
201 4958703 : }
202 :
203 9399579 : T* item_ptr(difference_type pos) { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
204 30846631 : const T* item_ptr(difference_type pos) const { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
205 :
206 10944 : void fill(T* dst, ptrdiff_t count, const T& value = T{}) {
207 10944 : std::fill_n(dst, count, value);
208 10944 : }
209 :
210 : template<typename InputIterator>
211 4983181 : void fill(T* dst, InputIterator first, InputIterator last) {
212 118922779 : while (first != last) {
213 113939598 : new(static_cast<void*>(dst)) T(*first);
214 113939598 : ++dst;
215 113939598 : ++first;
216 : }
217 4983181 : }
218 :
219 : public:
220 0 : void assign(size_type n, const T& val) {
221 0 : clear();
222 0 : if (capacity() < n) {
223 0 : change_capacity(n);
224 0 : }
225 0 : _size += n;
226 0 : fill(item_ptr(0), n, val);
227 0 : }
228 :
229 : template<typename InputIterator>
230 834487 : void assign(InputIterator first, InputIterator last) {
231 834487 : size_type n = last - first;
232 834487 : clear();
233 834487 : if (capacity() < n) {
234 504657 : change_capacity(n);
235 504657 : }
236 834487 : _size += n;
237 834487 : fill(item_ptr(0), first, last);
238 834487 : }
239 :
240 6432196 : prevector() {}
241 :
242 : explicit prevector(size_type n) {
243 : resize(n);
244 : }
245 :
246 16 : explicit prevector(size_type n, const T& val) {
247 16 : change_capacity(n);
248 16 : _size += n;
249 16 : fill(item_ptr(0), n, val);
250 16 : }
251 :
252 : template<typename InputIterator>
253 33392 : prevector(InputIterator first, InputIterator last) {
254 33392 : size_type n = last - first;
255 33392 : change_capacity(n);
256 33392 : _size += n;
257 33392 : fill(item_ptr(0), first, last);
258 33392 : }
259 :
260 3207726 : prevector(const prevector<N, T, Size, Diff>& other) {
261 3207726 : size_type n = other.size();
262 3207726 : change_capacity(n);
263 3207726 : _size += n;
264 3207726 : fill(item_ptr(0), other.begin(), other.end());
265 3207726 : }
266 :
267 2750694 : prevector(prevector<N, T, Size, Diff>&& other) noexcept
268 2750694 : : _union(std::move(other._union)), _size(other._size)
269 : {
270 2750694 : other._size = 0;
271 2750694 : }
272 :
273 834487 : prevector& operator=(const prevector<N, T, Size, Diff>& other) {
274 834487 : if (&other == this) {
275 0 : return *this;
276 : }
277 834487 : assign(other.begin(), other.end());
278 834487 : return *this;
279 834487 : }
280 :
281 448077 : prevector& operator=(prevector<N, T, Size, Diff>&& other) noexcept {
282 448077 : if (!is_direct()) {
283 0 : free(_union.indirect_contents.indirect);
284 0 : }
285 448077 : _union = std::move(other._union);
286 448077 : _size = other._size;
287 448077 : other._size = 0;
288 448077 : return *this;
289 : }
290 :
291 64266283 : size_type size() const {
292 64266283 : return is_direct() ? _size : _size - N - 1;
293 : }
294 :
295 6309595 : bool empty() const {
296 6309595 : return size() == 0;
297 : }
298 :
299 40869 : iterator begin() { return iterator(item_ptr(0)); }
300 8327195 : const_iterator begin() const { return const_iterator(item_ptr(0)); }
301 1533730 : iterator end() { return iterator(item_ptr(size())); }
302 10012629 : const_iterator end() const { return const_iterator(item_ptr(size())); }
303 :
304 : reverse_iterator rbegin() { return reverse_iterator(item_ptr(size() - 1)); }
305 0 : const_reverse_iterator rbegin() const { return const_reverse_iterator(item_ptr(size() - 1)); }
306 : reverse_iterator rend() { return reverse_iterator(item_ptr(-1)); }
307 0 : const_reverse_iterator rend() const { return const_reverse_iterator(item_ptr(-1)); }
308 :
309 3042960 : size_t capacity() const {
310 3042960 : if (is_direct()) {
311 2485860 : return N;
312 : } else {
313 557100 : return _union.indirect_contents.capacity;
314 : }
315 3042960 : }
316 :
317 41783 : T& operator[](size_type pos) {
318 41783 : return *item_ptr(pos);
319 : }
320 :
321 2325003 : const T& operator[](size_type pos) const {
322 2325003 : return *item_ptr(pos);
323 : }
324 :
325 2280115 : void resize(size_type new_size) {
326 2280115 : size_type cur_size = size();
327 2280115 : if (cur_size == new_size) {
328 2261855 : return;
329 : }
330 18260 : if (cur_size > new_size) {
331 7332 : erase(item_ptr(new_size), end());
332 7332 : return;
333 : }
334 10928 : if (new_size > capacity()) {
335 10928 : change_capacity(new_size);
336 10928 : }
337 10928 : ptrdiff_t increase = new_size - cur_size;
338 10928 : fill(item_ptr(cur_size), increase);
339 10928 : _size += increase;
340 2280115 : }
341 :
342 0 : void reserve(size_type new_capacity) {
343 0 : if (new_capacity > capacity()) {
344 0 : change_capacity(new_capacity);
345 0 : }
346 0 : }
347 :
348 530425 : void shrink_to_fit() {
349 530425 : change_capacity(size());
350 530425 : }
351 :
352 2269187 : void clear() {
353 2269187 : resize(0);
354 2269187 : }
355 :
356 20245 : iterator insert(iterator pos, const T& value) {
357 20245 : size_type p = pos - begin();
358 20245 : size_type new_size = size() + 1;
359 20245 : if (capacity() < new_size) {
360 0 : change_capacity(new_size + (new_size >> 1));
361 0 : }
362 20245 : T* ptr = item_ptr(p);
363 20245 : memmove(ptr + 1, ptr, (size() - p) * sizeof(T));
364 20245 : _size++;
365 20245 : new(static_cast<void*>(ptr)) T(value);
366 20245 : return iterator(ptr);
367 : }
368 :
369 0 : void insert(iterator pos, size_type count, const T& value) {
370 0 : size_type p = pos - begin();
371 0 : size_type new_size = size() + count;
372 0 : if (capacity() < new_size) {
373 0 : change_capacity(new_size + (new_size >> 1));
374 0 : }
375 0 : T* ptr = item_ptr(p);
376 0 : memmove(ptr + count, ptr, (size() - p) * sizeof(T));
377 0 : _size += count;
378 0 : fill(item_ptr(p), count, value);
379 0 : }
380 :
381 : template<typename InputIterator>
382 10306 : void insert(iterator pos, InputIterator first, InputIterator last) {
383 10306 : size_type p = pos - begin();
384 10306 : difference_type count = last - first;
385 10306 : size_type new_size = size() + count;
386 10306 : if (capacity() < new_size) {
387 26 : change_capacity(new_size + (new_size >> 1));
388 26 : }
389 10306 : T* ptr = item_ptr(p);
390 10306 : memmove(ptr + count, ptr, (size() - p) * sizeof(T));
391 10306 : _size += count;
392 10306 : fill(ptr, first, last);
393 10306 : }
394 :
395 2 : inline void resize_uninitialized(size_type new_size) {
396 : // resize_uninitialized changes the size of the prevector but does not initialize it.
397 : // If size < new_size, the added elements must be initialized explicitly.
398 2 : if (capacity() < new_size) {
399 2 : change_capacity(new_size);
400 2 : _size += new_size - size();
401 2 : return;
402 : }
403 0 : if (new_size < size()) {
404 0 : erase(item_ptr(new_size), end());
405 0 : } else {
406 0 : _size += new_size - size();
407 : }
408 2 : }
409 :
410 0 : iterator erase(iterator pos) {
411 0 : return erase(pos, pos + 1);
412 : }
413 :
414 7332 : iterator erase(iterator first, iterator last) {
415 : // Erase is not allowed to the change the object's capacity. That means
416 : // that when starting with an indirectly allocated prevector with
417 : // size and capacity > N, the result may be a still indirectly allocated
418 : // prevector with size <= N and capacity > N. A shrink_to_fit() call is
419 : // necessary to switch to the (more efficient) directly allocated
420 : // representation (with capacity N and size <= N).
421 7332 : iterator p = first;
422 7332 : char* endp = (char*)&(*end());
423 7332 : _size -= last - p;
424 7332 : memmove(&(*first), &(*last), endp - ((char*)(&(*last))));
425 7332 : return first;
426 : }
427 :
428 : template<typename... Args>
429 48 : void emplace_back(Args&&... args) {
430 48 : size_type new_size = size() + 1;
431 48 : if (capacity() < new_size) {
432 0 : change_capacity(new_size + (new_size >> 1));
433 0 : }
434 48 : new(item_ptr(size())) T(std::forward<Args>(args)...);
435 48 : _size++;
436 48 : }
437 :
438 48 : void push_back(const T& value) {
439 48 : emplace_back(value);
440 48 : }
441 :
442 0 : void pop_back() {
443 0 : erase(end() - 1, end());
444 0 : }
445 :
446 : T& front() {
447 : return *item_ptr(0);
448 : }
449 :
450 : const T& front() const {
451 : return *item_ptr(0);
452 : }
453 :
454 0 : T& back() {
455 0 : return *item_ptr(size() - 1);
456 : }
457 :
458 0 : const T& back() const {
459 0 : return *item_ptr(size() - 1);
460 : }
461 :
462 0 : void swap(prevector<N, T, Size, Diff>& other) noexcept
463 : {
464 0 : std::swap(_union, other._union);
465 0 : std::swap(_size, other._size);
466 0 : }
467 :
468 9247721 : ~prevector() {
469 9247721 : if (!is_direct()) {
470 2907590 : free(_union.indirect_contents.indirect);
471 2907590 : _union.indirect_contents.indirect = nullptr;
472 2907590 : }
473 9247721 : }
474 :
475 5234 : bool operator==(const prevector<N, T, Size, Diff>& other) const {
476 5234 : if (other.size() != size()) {
477 0 : return false;
478 : }
479 5234 : const_iterator b1 = begin();
480 5234 : const_iterator b2 = other.begin();
481 5234 : const_iterator e1 = end();
482 183190 : while (b1 != e1) {
483 177956 : if ((*b1) != (*b2)) {
484 0 : return false;
485 : }
486 177956 : ++b1;
487 177956 : ++b2;
488 : }
489 5234 : return true;
490 5234 : }
491 :
492 0 : bool operator!=(const prevector<N, T, Size, Diff>& other) const {
493 0 : return !(*this == other);
494 : }
495 :
496 0 : bool operator<(const prevector<N, T, Size, Diff>& other) const {
497 0 : if (size() < other.size()) {
498 0 : return true;
499 : }
500 0 : if (size() > other.size()) {
501 0 : return false;
502 : }
503 0 : const_iterator b1 = begin();
504 0 : const_iterator b2 = other.begin();
505 0 : const_iterator e1 = end();
506 0 : while (b1 != e1) {
507 0 : if ((*b1) < (*b2)) {
508 0 : return true;
509 : }
510 0 : if ((*b2) < (*b1)) {
511 0 : return false;
512 : }
513 0 : ++b1;
514 0 : ++b2;
515 : }
516 0 : return false;
517 0 : }
518 :
519 253023 : size_t allocated_memory() const {
520 253023 : if (is_direct()) {
521 28252 : return 0;
522 : } else {
523 224771 : return ((size_t)(sizeof(T))) * _union.indirect_contents.capacity;
524 : }
525 253023 : }
526 :
527 8910 : value_type* data() {
528 8910 : return item_ptr(0);
529 : }
530 :
531 3847775 : const value_type* data() const {
532 3847775 : return item_ptr(0);
533 : }
534 : };
535 :
536 : #endif // BITCOIN_PREVECTOR_H
|
