Line data Source code
1 : // Copyright (c) 2015-2020 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 <stdint.h>
10 : #include <string.h>
11 :
12 : #include <algorithm>
13 : #include <cstddef>
14 : #include <cstdlib>
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 : using element_type = T;
57 : using iterator_category = std::contiguous_iterator_tag;
58 : iterator() = default;
59 208299125 : iterator(T* ptr_) : ptr(ptr_) {}
60 132282461 : T& operator*() const { return *ptr; }
61 340518 : T* operator->() const { return ptr; }
62 2020224 : T& operator[](size_type pos) const { return ptr[pos]; }
63 4047617 : iterator& operator++() { ptr++; return *this; }
64 4040448 : iterator& operator--() { ptr--; return *this; }
65 : iterator operator++(int) { iterator copy(*this); ++(*this); return copy; }
66 : iterator operator--(int) { iterator copy(*this); --(*this); return copy; }
67 32956815 : difference_type friend operator-(iterator a, iterator b) { return (&(*a) - &(*b)); }
68 4191680 : iterator operator+(size_type n) const { return iterator(ptr + n); }
69 : iterator friend operator+(size_type n, iterator x) { return x + n; }
70 : iterator& operator+=(size_type n) { ptr += n; return *this; }
71 2028096 : iterator operator-(size_type n) const { return iterator(ptr - n); }
72 : iterator& operator-=(size_type n) { ptr -= n; return *this; }
73 : bool operator==(iterator x) const { return ptr == x.ptr; }
74 6882949 : 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 : };
80 :
81 : class reverse_iterator {
82 : T* ptr{};
83 : public:
84 : typedef Diff difference_type;
85 : typedef T value_type;
86 : typedef T* pointer;
87 : typedef T& reference;
88 : typedef std::bidirectional_iterator_tag iterator_category;
89 : reverse_iterator() = default;
90 : reverse_iterator(T* ptr_) : ptr(ptr_) {}
91 : T& operator*() const { return *ptr; }
92 : T* operator->() const { return ptr; }
93 : reverse_iterator& operator--() { ptr++; return *this; }
94 : reverse_iterator& operator++() { ptr--; return *this; }
95 : reverse_iterator operator++(int) { reverse_iterator copy(*this); ++(*this); return copy; }
96 : reverse_iterator operator--(int) { reverse_iterator copy(*this); --(*this); return copy; }
97 : bool operator==(reverse_iterator x) const { return ptr == x.ptr; }
98 : bool operator!=(reverse_iterator x) const { return ptr != x.ptr; }
99 : };
100 :
101 : class const_iterator {
102 : const T* ptr{};
103 : public:
104 : typedef Diff difference_type;
105 : typedef const T value_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 800973238 : const_iterator(const T* ptr_) : ptr(ptr_) {}
112 6795250 : const_iterator(iterator x) : ptr(&(*x)) {}
113 1736260401 : const T& operator*() const { return *ptr; }
114 18560186 : const T* operator->() const { return ptr; }
115 588448 : const T& operator[](size_type pos) const { return ptr[pos]; }
116 659524825 : const_iterator& operator++() { ptr++; return *this; }
117 4040448 : const_iterator& operator--() { ptr--; return *this; }
118 48409386 : const_iterator operator++(int) { const_iterator copy(*this); ++(*this); return copy; }
119 : const_iterator operator--(int) { const_iterator copy(*this); --(*this); return copy; }
120 184762461 : difference_type friend operator-(const_iterator a, const_iterator b) { return (&(*a) - &(*b)); }
121 12697530 : 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 13481979 : const_iterator& operator+=(size_type n) { ptr += n; return *this; }
124 530 : const_iterator operator-(size_type n) const { return const_iterator(ptr - n); }
125 : const_iterator& operator-=(size_type n) { ptr -= n; return *this; }
126 1678 : bool operator==(const_iterator x) const { return ptr == x.ptr; }
127 351116257 : bool operator!=(const_iterator x) const { return ptr != x.ptr; }
128 50361667 : 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 47426126 : 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 183449954 : alignas(char*) direct_or_indirect _union = {};
166 183449954 : 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 179172183 : T* direct_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.direct) + pos; }
172 442708032 : const T* direct_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.direct) + pos; }
173 28686612 : T* indirect_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.indirect_contents.indirect) + pos; }
174 36566190 : const T* indirect_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.indirect_contents.indirect) + pos; }
175 2127128483 : bool is_direct() const { return _size <= N; }
176 :
177 168889997 : void change_capacity(size_type new_capacity) {
178 168889997 : if (new_capacity <= N) {
179 163617280 : if (!is_direct()) {
180 73028 : T* indirect = indirect_ptr(0);
181 73028 : T* src = indirect;
182 73028 : T* dst = direct_ptr(0);
183 73028 : memcpy(dst, src, size() * sizeof(T));
184 73028 : free(indirect);
185 73028 : _size -= N + 1;
186 73028 : }
187 163617280 : } else {
188 5272717 : 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 93638 : _union.indirect_contents.indirect = static_cast<char*>(realloc(_union.indirect_contents.indirect, ((size_t)sizeof(T)) * new_capacity));
193 93638 : assert(_union.indirect_contents.indirect);
194 93638 : _union.indirect_contents.capacity = new_capacity;
195 93638 : } else {
196 5179079 : char* new_indirect = static_cast<char*>(malloc(((size_t)sizeof(T)) * new_capacity));
197 5179079 : assert(new_indirect);
198 5179079 : T* src = direct_ptr(0);
199 5179079 : T* dst = reinterpret_cast<T*>(new_indirect);
200 5179079 : memcpy(dst, src, size() * sizeof(T));
201 5179079 : _union.indirect_contents.indirect = new_indirect;
202 5179079 : _union.indirect_contents.capacity = new_capacity;
203 5179079 : _size += N + 1;
204 : }
205 : }
206 168889997 : }
207 :
208 202582487 : T* item_ptr(difference_type pos) { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
209 479275572 : const T* item_ptr(difference_type pos) const { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
210 :
211 9270623 : void fill(T* dst, ptrdiff_t count, const T& value = T{}) {
212 9270623 : std::fill_n(dst, count, value);
213 9270623 : }
214 :
215 : template<typename InputIterator>
216 6349912 : void fill(T* dst, InputIterator first, InputIterator last) {
217 195460787 : while (first != last) {
218 189110875 : new(static_cast<void*>(dst)) T(*first);
219 189110875 : ++dst;
220 189110875 : ++first;
221 : }
222 6349912 : }
223 :
224 70782230 : void fill(T* dst, const_iterator first, const_iterator last) {
225 70782230 : ptrdiff_t count = last - first;
226 70782230 : fill(dst, &*first, count);
227 70782230 : }
228 :
229 70839485 : void fill(T* dst, const T* src, ptrdiff_t count) {
230 : if (std::is_trivially_constructible<T>::value) {
231 70839485 : ::memmove(dst, src, count * sizeof(T));
232 : } else {
233 : for (ptrdiff_t i = 0; i < count; i++) {
234 : new(static_cast<void*>(dst)) T(*src);
235 : ++dst;
236 : ++src;
237 : }
238 : }
239 70839485 : }
240 :
241 : public:
242 87502 : void assign(size_type n, const T& val) {
243 87502 : clear();
244 87502 : if (capacity() < n) {
245 48110 : change_capacity(n);
246 48110 : }
247 87502 : _size += n;
248 87502 : fill(item_ptr(0), n, val);
249 87502 : }
250 :
251 : template<typename InputIterator>
252 17563730 : void assign(InputIterator first, InputIterator last) {
253 17563730 : size_type n = last - first;
254 17563730 : clear();
255 17563730 : if (capacity() < n) {
256 1232436 : change_capacity(n);
257 1232436 : }
258 17563730 : _size += n;
259 17563730 : fill(item_ptr(0), first, last);
260 17563730 : }
261 :
262 256046722 : prevector() {}
263 :
264 : explicit prevector(size_type n) {
265 : resize(n);
266 : }
267 :
268 15316766 : explicit prevector(size_type n, const T& val) {
269 7658381 : change_capacity(n);
270 7658381 : _size += n;
271 7658381 : fill(item_ptr(0), n, val);
272 15316766 : }
273 :
274 : template<typename InputIterator>
275 2457690 : prevector(InputIterator first, InputIterator last) {
276 1914402 : size_type n = last - first;
277 1914402 : change_capacity(n);
278 1914402 : _size += n;
279 1914402 : fill(item_ptr(0), first, last);
280 2457690 : }
281 :
282 57362600 : prevector(const prevector<N, T, Size, Diff>& other) {
283 46460101 : size_type n = other.size();
284 46460101 : change_capacity(n);
285 46460101 : _size += n;
286 46460101 : fill(item_ptr(0), other.begin(), other.end());
287 57362600 : }
288 :
289 21748678 : prevector(prevector<N, T, Size, Diff>&& other) noexcept
290 19980579 : : _union(std::move(other._union)), _size(other._size)
291 1768099 : {
292 19980579 : other._size = 0;
293 21748678 : }
294 :
295 15866007 : prevector& operator=(const prevector<N, T, Size, Diff>& other) {
296 15866007 : if (&other == this) {
297 12907 : return *this;
298 : }
299 15853100 : assign(other.begin(), other.end());
300 15853100 : return *this;
301 15866007 : }
302 :
303 24637577 : prevector& operator=(prevector<N, T, Size, Diff>&& other) noexcept {
304 24637577 : if (!is_direct()) {
305 45296 : free(_union.indirect_contents.indirect);
306 45296 : }
307 24637577 : _union = std::move(other._union);
308 24637577 : _size = other._size;
309 24637577 : other._size = 0;
310 24637577 : return *this;
311 : }
312 :
313 969008861 : size_type size() const {
314 969008861 : return is_direct() ? _size : _size - N - 1;
315 : }
316 :
317 48321383 : bool empty() const {
318 48321383 : return size() == 0;
319 : }
320 :
321 26774515 : iterator begin() { return iterator(item_ptr(0)); }
322 194173141 : const_iterator begin() const { return const_iterator(item_ptr(0)); }
323 49951983 : iterator end() { return iterator(item_ptr(size())); }
324 194164006 : const_iterator end() const { return const_iterator(item_ptr(size())); }
325 :
326 : reverse_iterator rbegin() { return reverse_iterator(item_ptr(size() - 1)); }
327 : const_reverse_iterator rbegin() const { return const_reverse_iterator(item_ptr(size() - 1)); }
328 : reverse_iterator rend() { return reverse_iterator(item_ptr(-1)); }
329 : const_reverse_iterator rend() const { return const_reverse_iterator(item_ptr(-1)); }
330 :
331 43141756 : size_t capacity() const {
332 43141756 : if (is_direct()) {
333 39940126 : return N;
334 : } else {
335 3201630 : return _union.indirect_contents.capacity;
336 : }
337 43141756 : }
338 :
339 16682309 : T& operator[](size_type pos) {
340 16682309 : return *item_ptr(pos);
341 : }
342 :
343 50975236 : const T& operator[](size_type pos) const {
344 50975236 : return *item_ptr(pos);
345 : }
346 :
347 132493890 : void resize(size_type new_size) {
348 132493890 : size_type cur_size = size();
349 132493890 : if (cur_size == new_size) {
350 117804218 : return;
351 : }
352 14689672 : if (cur_size > new_size) {
353 13180869 : erase(item_ptr(new_size), end());
354 13180869 : return;
355 : }
356 1508803 : if (new_size > capacity()) {
357 39581 : change_capacity(new_size);
358 39581 : }
359 1508803 : ptrdiff_t increase = new_size - cur_size;
360 1508803 : fill(item_ptr(cur_size), increase);
361 1508803 : _size += increase;
362 132493890 : }
363 :
364 4096 : void reserve(size_type new_capacity) {
365 4096 : if (new_capacity > capacity()) {
366 1792 : change_capacity(new_capacity);
367 1792 : }
368 4096 : }
369 :
370 108740726 : void shrink_to_fit() {
371 108740726 : change_capacity(size());
372 108740726 : }
373 :
374 130889346 : void clear() {
375 130889346 : resize(0);
376 130889346 : }
377 :
378 8208590 : iterator insert(iterator pos, const T& value) {
379 8208590 : size_type p = pos - begin();
380 8208590 : size_type new_size = size() + 1;
381 8208590 : if (capacity() < new_size) {
382 9533 : change_capacity(new_size + (new_size >> 1));
383 9533 : }
384 8208590 : T* ptr = item_ptr(p);
385 8208590 : memmove(ptr + 1, ptr, (size() - p) * sizeof(T));
386 8208590 : _size++;
387 8208590 : new(static_cast<void*>(ptr)) T(value);
388 8208590 : return iterator(ptr);
389 : }
390 :
391 15927 : void insert(iterator pos, size_type count, const T& value) {
392 15927 : size_type p = pos - begin();
393 15927 : size_type new_size = size() + count;
394 15927 : if (capacity() < new_size) {
395 950 : change_capacity(new_size + (new_size >> 1));
396 950 : }
397 15927 : T* ptr = item_ptr(p);
398 15927 : memmove(ptr + count, ptr, (size() - p) * sizeof(T));
399 15927 : _size += count;
400 15927 : fill(item_ptr(p), count, value);
401 15927 : }
402 :
403 : template<typename InputIterator>
404 11224744 : void insert(iterator pos, InputIterator first, InputIterator last) {
405 11224744 : size_type p = pos - begin();
406 11224744 : difference_type count = last - first;
407 11224744 : size_type new_size = size() + count;
408 11224744 : if (capacity() < new_size) {
409 2173653 : change_capacity(new_size + (new_size >> 1));
410 2173653 : }
411 11224744 : T* ptr = item_ptr(p);
412 11224744 : memmove(ptr + count, ptr, (size() - p) * sizeof(T));
413 11224744 : _size += count;
414 11224744 : fill(ptr, first, last);
415 11224744 : }
416 :
417 4385331 : inline void resize_uninitialized(size_type new_size) {
418 : // resize_uninitialized changes the size of the prevector but does not initialize it.
419 : // If size < new_size, the added elements must be initialized explicitly.
420 4385331 : if (capacity() < new_size) {
421 597119 : change_capacity(new_size);
422 597119 : _size += new_size - size();
423 597119 : return;
424 : }
425 3788212 : if (new_size < size()) {
426 3008 : erase(item_ptr(new_size), end());
427 3008 : } else {
428 3785204 : _size += new_size - size();
429 : }
430 4385331 : }
431 :
432 28608 : iterator erase(iterator pos) {
433 28608 : return erase(pos, pos + 1);
434 : }
435 :
436 13240901 : iterator erase(iterator first, iterator last) {
437 : // Erase is not allowed to the change the object's capacity. That means
438 : // that when starting with an indirectly allocated prevector with
439 : // size and capacity > N, the result may be a still indirectly allocated
440 : // prevector with size <= N and capacity > N. A shrink_to_fit() call is
441 : // necessary to switch to the (more efficient) directly allocated
442 : // representation (with capacity N and size <= N).
443 13240901 : iterator p = first;
444 13240901 : char* endp = (char*)&(*end());
445 13240901 : _size -= last - p;
446 13240901 : memmove(&(*first), &(*last), endp - ((char*)(&(*last))));
447 13240901 : return first;
448 : }
449 :
450 : template<typename... Args>
451 100033 : void emplace_back(Args&&... args) {
452 100033 : size_type new_size = size() + 1;
453 100033 : if (capacity() < new_size) {
454 26047 : change_capacity(new_size + (new_size >> 1));
455 26047 : }
456 100033 : new(item_ptr(size())) T(std::forward<Args>(args)...);
457 100033 : _size++;
458 100033 : }
459 :
460 100033 : void push_back(const T& value) {
461 100033 : emplace_back(value);
462 100033 : }
463 :
464 7872 : void pop_back() {
465 7872 : erase(end() - 1, end());
466 7872 : }
467 :
468 : T& front() {
469 : return *item_ptr(0);
470 : }
471 :
472 : const T& front() const {
473 : return *item_ptr(0);
474 : }
475 :
476 : T& back() {
477 : return *item_ptr(size() - 1);
478 : }
479 :
480 46900 : const T& back() const {
481 46900 : return *item_ptr(size() - 1);
482 : }
483 :
484 16320 : void swap(prevector<N, T, Size, Diff>& other) noexcept
485 : {
486 16320 : std::swap(_union, other._union);
487 16320 : std::swap(_size, other._size);
488 16320 : }
489 :
490 225267946 : ~prevector() {
491 203219537 : if (!is_direct()) {
492 4998757 : free(_union.indirect_contents.indirect);
493 4998465 : _union.indirect_contents.indirect = nullptr;
494 4998465 : }
495 225267350 : }
496 :
497 2648310 : bool operator==(const prevector<N, T, Size, Diff>& other) const {
498 2648310 : if (other.size() != size()) {
499 84246 : return false;
500 : }
501 2564064 : const_iterator b1 = begin();
502 2564064 : const_iterator b2 = other.begin();
503 2564064 : const_iterator e1 = end();
504 39071610 : while (b1 != e1) {
505 36527068 : if ((*b1) != (*b2)) {
506 19522 : return false;
507 : }
508 36507546 : ++b1;
509 36507546 : ++b2;
510 : }
511 2544542 : return true;
512 2648310 : }
513 :
514 526812 : bool operator!=(const prevector<N, T, Size, Diff>& other) const {
515 526812 : return !(*this == other);
516 : }
517 :
518 43012360 : bool operator<(const prevector<N, T, Size, Diff>& other) const {
519 43012360 : if (size() < other.size()) {
520 4778190 : return true;
521 : }
522 38234170 : if (size() > other.size()) {
523 682368 : return false;
524 : }
525 37551802 : const_iterator b1 = begin();
526 37551802 : const_iterator b2 = other.begin();
527 37551802 : const_iterator e1 = end();
528 304578292 : while (b1 != e1) {
529 296742507 : if ((*b1) < (*b2)) {
530 19356514 : return true;
531 : }
532 277385993 : if ((*b2) < (*b1)) {
533 10359503 : return false;
534 : }
535 267026490 : ++b1;
536 267026490 : ++b2;
537 : }
538 7835785 : return false;
539 43012360 : }
540 :
541 43579326 : size_t allocated_memory() const {
542 43579326 : if (is_direct()) {
543 42358838 : return 0;
544 : } else {
545 1220488 : return ((size_t)(sizeof(T))) * _union.indirect_contents.capacity;
546 : }
547 43579326 : }
548 :
549 1591716 : value_type* data() {
550 1591716 : return item_ptr(0);
551 : }
552 :
553 40146623 : const value_type* data() const {
554 40146623 : return item_ptr(0);
555 : }
556 :
557 : template<typename V>
558 3589151 : static void assign_to(const_iterator b, const_iterator e, V& v) {
559 : // We know that internally the iterators are pointing to continues memory, so we can directly use the pointers here
560 : // This avoids internal use of std::copy and operator++ on the iterators and instead allows efficient memcpy/memmove
561 : if (std::is_trivially_constructible<T>::value) {
562 3589151 : auto s = e - b;
563 3589151 : if (v.size() != size_t(s)) {
564 3541926 : v.resize(s);
565 3541926 : }
566 3589151 : if (!v.empty()) {
567 3541563 : ::memmove(v.data(), &*b, s);
568 3541563 : }
569 : } else {
570 : v.assign(&*b, &*e);
571 : }
572 3589151 : }
573 : };
574 :
575 : #endif // BITCOIN_PREVECTOR_H
|
