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 48902931 : iterator(T* ptr_) : ptr(ptr_) {}
60 19481910 : T& operator*() const { return *ptr; }
61 62054 : 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 3993919 : 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 65633141 : const_iterator(const T* ptr_) : ptr(ptr_) {}
112 616779 : const_iterator(iterator x) : ptr(&(*x)) {}
113 108931284 : const T& operator*() const { return *ptr; }
114 1584925 : const T* operator->() const { return ptr; }
115 104344 : const T& operator[](size_type pos) const { return ptr[pos]; }
116 49193555 : const_iterator& operator++() { ptr++; return *this; }
117 4040448 : const_iterator& operator--() { ptr--; return *this; }
118 3271140 : const_iterator operator++(int) { const_iterator copy(*this); ++(*this); return copy; }
119 : const_iterator operator--(int) { const_iterator copy(*this); --(*this); return copy; }
120 17069027 : difference_type friend operator-(const_iterator a, const_iterator b) { return (&(*a) - &(*b)); }
121 474738 : 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 1344296 : 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 254 : bool operator==(const_iterator x) const { return ptr == x.ptr; }
127 30501877 : bool operator!=(const_iterator x) const { return ptr != x.ptr; }
128 3545105 : 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 3200246 : 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 66932837 : alignas(char*) direct_or_indirect _union = {};
166 66932837 : 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 20901984 : T* direct_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.direct) + pos; }
172 27812505 : const T* direct_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.direct) + pos; }
173 15949839 : T* indirect_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.indirect_contents.indirect) + pos; }
174 8581535 : const T* indirect_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.indirect_contents.indirect) + pos; }
175 401072637 : bool is_direct() const { return _size <= N; }
176 :
177 65747219 : void change_capacity(size_type new_capacity) {
178 65747219 : if (new_capacity <= N) {
179 64371789 : if (!is_direct()) {
180 57369 : T* indirect = indirect_ptr(0);
181 57369 : T* src = indirect;
182 57369 : T* dst = direct_ptr(0);
183 57369 : memcpy(dst, src, size() * sizeof(T));
184 57369 : free(indirect);
185 57369 : _size -= N + 1;
186 57369 : }
187 64371789 : } else {
188 1375430 : 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 16415 : _union.indirect_contents.indirect = static_cast<char*>(realloc(_union.indirect_contents.indirect, ((size_t)sizeof(T)) * new_capacity));
193 16415 : assert(_union.indirect_contents.indirect);
194 16415 : _union.indirect_contents.capacity = new_capacity;
195 16415 : } else {
196 1359015 : char* new_indirect = static_cast<char*>(malloc(((size_t)sizeof(T)) * new_capacity));
197 1359015 : assert(new_indirect);
198 1359015 : T* src = direct_ptr(0);
199 1359015 : T* dst = reinterpret_cast<T*>(new_indirect);
200 1359015 : memcpy(dst, src, size() * sizeof(T));
201 1359015 : _union.indirect_contents.indirect = new_indirect;
202 1359015 : _union.indirect_contents.capacity = new_capacity;
203 1359015 : _size += N + 1;
204 : }
205 : }
206 65747219 : }
207 :
208 35378067 : T* item_ptr(difference_type pos) { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
209 36394028 : const T* item_ptr(difference_type pos) const { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
210 :
211 224942 : void fill(T* dst, ptrdiff_t count, const T& value = T{}) {
212 224942 : std::fill_n(dst, count, value);
213 224942 : }
214 :
215 : template<typename InputIterator>
216 969373 : void fill(T* dst, InputIterator first, InputIterator last) {
217 14058139 : while (first != last) {
218 13088766 : new(static_cast<void*>(dst)) T(*first);
219 13088766 : ++dst;
220 13088766 : ++first;
221 : }
222 969373 : }
223 :
224 7477796 : void fill(T* dst, const_iterator first, const_iterator last) {
225 7477796 : ptrdiff_t count = last - first;
226 7477796 : fill(dst, &*first, count);
227 7477796 : }
228 :
229 7477800 : void fill(T* dst, const T* src, ptrdiff_t count) {
230 : if (std::is_trivially_constructible<T>::value) {
231 7477800 : ::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 7477800 : }
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 1957339 : void assign(InputIterator first, InputIterator last) {
253 1957339 : size_type n = last - first;
254 1957339 : clear();
255 1957339 : if (capacity() < n) {
256 460294 : change_capacity(n);
257 460294 : }
258 1957339 : _size += n;
259 1957339 : fill(item_ptr(0), first, last);
260 1957339 : }
261 :
262 122702575 : prevector() {}
263 :
264 : explicit prevector(size_type n) {
265 : resize(n);
266 : }
267 :
268 105326 : explicit prevector(size_type n, const T& val) {
269 52663 : change_capacity(n);
270 52663 : _size += n;
271 52663 : fill(item_ptr(0), n, val);
272 105326 : }
273 :
274 : template<typename InputIterator>
275 1163596 : prevector(InputIterator first, InputIterator last) {
276 620468 : size_type n = last - first;
277 620468 : change_capacity(n);
278 620468 : _size += n;
279 620468 : fill(item_ptr(0), first, last);
280 1163596 : }
281 :
282 5084171 : prevector(const prevector<N, T, Size, Diff>& other) {
283 4919474 : size_type n = other.size();
284 4919474 : change_capacity(n);
285 4919474 : _size += n;
286 4919474 : fill(item_ptr(0), other.begin(), other.end());
287 5084171 : }
288 :
289 1594456 : prevector(prevector<N, T, Size, Diff>&& other) noexcept
290 1592911 : : _union(std::move(other._union)), _size(other._size)
291 1545 : {
292 1592911 : other._size = 0;
293 1594456 : }
294 :
295 1955336 : prevector& operator=(const prevector<N, T, Size, Diff>& other) {
296 1955336 : if (&other == this) {
297 12907 : return *this;
298 : }
299 1942429 : assign(other.begin(), other.end());
300 1942429 : return *this;
301 1955336 : }
302 :
303 1097992 : prevector& operator=(prevector<N, T, Size, Diff>&& other) noexcept {
304 1097992 : if (!is_direct()) {
305 30510 : free(_union.indirect_contents.indirect);
306 30510 : }
307 1097992 : _union = std::move(other._union);
308 1097992 : _size = other._size;
309 1097992 : other._size = 0;
310 1097992 : return *this;
311 : }
312 :
313 186349850 : size_type size() const {
314 186349850 : return is_direct() ? _size : _size - N - 1;
315 : }
316 :
317 3725963 : bool empty() const {
318 3725963 : return size() == 0;
319 : }
320 :
321 8666992 : iterator begin() { return iterator(item_ptr(0)); }
322 15780706 : const_iterator begin() const { return const_iterator(item_ptr(0)); }
323 6865859 : iterator end() { return iterator(item_ptr(size())); }
324 16560877 : 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 5731272 : size_t capacity() const {
332 5731272 : if (is_direct()) {
333 5545275 : return N;
334 : } else {
335 185997 : return _union.indirect_contents.capacity;
336 : }
337 5731272 : }
338 :
339 8372345 : T& operator[](size_type pos) {
340 8372345 : return *item_ptr(pos);
341 : }
342 :
343 1328454 : const T& operator[](size_type pos) const {
344 1328454 : return *item_ptr(pos);
345 : }
346 :
347 61690620 : void resize(size_type new_size) {
348 61690620 : size_type cur_size = size();
349 61690620 : if (cur_size == new_size) {
350 61412275 : return;
351 : }
352 278345 : if (cur_size > new_size) {
353 209321 : erase(item_ptr(new_size), end());
354 209321 : return;
355 : }
356 69024 : if (new_size > capacity()) {
357 34352 : change_capacity(new_size);
358 34352 : }
359 69024 : ptrdiff_t increase = new_size - cur_size;
360 69024 : fill(item_ptr(cur_size), increase);
361 69024 : _size += increase;
362 61690620 : }
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 59433832 : void shrink_to_fit() {
371 59433832 : change_capacity(size());
372 59433832 : }
373 :
374 61609833 : void clear() {
375 61609833 : resize(0);
376 61609833 : }
377 :
378 2486567 : iterator insert(iterator pos, const T& value) {
379 2486567 : size_type p = pos - begin();
380 2486567 : size_type new_size = size() + 1;
381 2486567 : if (capacity() < new_size) {
382 1386 : change_capacity(new_size + (new_size >> 1));
383 1386 : }
384 2486567 : T* ptr = item_ptr(p);
385 2486567 : memmove(ptr + 1, ptr, (size() - p) * sizeof(T));
386 2486567 : _size++;
387 2486567 : new(static_cast<void*>(ptr)) T(value);
388 2486567 : return iterator(ptr);
389 : }
390 :
391 15753 : void insert(iterator pos, size_type count, const T& value) {
392 15753 : size_type p = pos - begin();
393 15753 : size_type new_size = size() + count;
394 15753 : if (capacity() < new_size) {
395 776 : change_capacity(new_size + (new_size >> 1));
396 776 : }
397 15753 : T* ptr = item_ptr(p);
398 15753 : memmove(ptr + count, ptr, (size() - p) * sizeof(T));
399 15753 : _size += count;
400 15753 : fill(item_ptr(p), count, value);
401 15753 : }
402 :
403 : template<typename InputIterator>
404 949897 : void insert(iterator pos, InputIterator first, InputIterator last) {
405 949897 : size_type p = pos - begin();
406 949897 : difference_type count = last - first;
407 949897 : size_type new_size = size() + count;
408 949897 : if (capacity() < new_size) {
409 126829 : change_capacity(new_size + (new_size >> 1));
410 126829 : }
411 949897 : T* ptr = item_ptr(p);
412 949897 : memmove(ptr + count, ptr, (size() - p) * sizeof(T));
413 949897 : _size += count;
414 949897 : fill(ptr, first, last);
415 949897 : }
416 :
417 135817 : 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 135817 : if (capacity() < new_size) {
421 46992 : change_capacity(new_size);
422 46992 : _size += new_size - size();
423 46992 : return;
424 : }
425 88825 : if (new_size < size()) {
426 3008 : erase(item_ptr(new_size), end());
427 3008 : } else {
428 85817 : _size += new_size - size();
429 : }
430 135817 : }
431 :
432 28608 : iterator erase(iterator pos) {
433 28608 : return erase(pos, pos + 1);
434 : }
435 :
436 269353 : 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 269353 : iterator p = first;
444 269353 : char* endp = (char*)&(*end());
445 269353 : _size -= last - p;
446 269353 : memmove(&(*first), &(*last), endp - ((char*)(&(*last))));
447 269353 : return first;
448 : }
449 :
450 : template<typename... Args>
451 21211 : void emplace_back(Args&&... args) {
452 21211 : size_type new_size = size() + 1;
453 21211 : if (capacity() < new_size) {
454 305 : change_capacity(new_size + (new_size >> 1));
455 305 : }
456 21211 : new(item_ptr(size())) T(std::forward<Args>(args)...);
457 21211 : _size++;
458 21211 : }
459 :
460 21211 : void push_back(const T& value) {
461 21211 : emplace_back(value);
462 21211 : }
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 2491 : const T& back() const {
481 2491 : 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 69166027 : ~prevector() {
491 68384071 : if (!is_direct()) {
492 1216389 : free(_union.indirect_contents.indirect);
493 1216395 : _union.indirect_contents.indirect = nullptr;
494 1216395 : }
495 69166027 : }
496 :
497 958985 : bool operator==(const prevector<N, T, Size, Diff>& other) const {
498 958985 : if (other.size() != size()) {
499 2803 : return false;
500 : }
501 956182 : const_iterator b1 = begin();
502 956182 : const_iterator b2 = other.begin();
503 956182 : const_iterator e1 = end();
504 16284079 : while (b1 != e1) {
505 15329209 : if ((*b1) != (*b2)) {
506 1312 : return false;
507 : }
508 15327897 : ++b1;
509 15327897 : ++b2;
510 : }
511 954870 : return true;
512 958985 : }
513 :
514 4090 : bool operator!=(const prevector<N, T, Size, Diff>& other) const {
515 4090 : return !(*this == other);
516 : }
517 :
518 5040595 : bool operator<(const prevector<N, T, Size, Diff>& other) const {
519 5040595 : if (size() < other.size()) {
520 3359655 : return true;
521 : }
522 1680940 : if (size() > other.size()) {
523 40479 : return false;
524 : }
525 1640461 : const_iterator b1 = begin();
526 1640461 : const_iterator b2 = other.begin();
527 1640461 : const_iterator e1 = end();
528 7253422 : while (b1 != e1) {
529 7237356 : if ((*b1) < (*b2)) {
530 1065583 : return true;
531 : }
532 6171773 : if ((*b2) < (*b1)) {
533 558812 : return false;
534 : }
535 5612961 : ++b1;
536 5612961 : ++b2;
537 : }
538 16066 : return false;
539 5040595 : }
540 :
541 1993156 : size_t allocated_memory() const {
542 1993156 : if (is_direct()) {
543 1082033 : return 0;
544 : } else {
545 911123 : return ((size_t)(sizeof(T))) * _union.indirect_contents.capacity;
546 : }
547 1993156 : }
548 :
549 64975 : value_type* data() {
550 64975 : return item_ptr(0);
551 : }
552 :
553 2721684 : const value_type* data() const {
554 2721684 : return item_ptr(0);
555 : }
556 :
557 : template<typename V>
558 383595 : 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 383595 : auto s = e - b;
563 383595 : if (v.size() != size_t(s)) {
564 337926 : v.resize(s);
565 337926 : }
566 383595 : if (!v.empty()) {
567 337921 : ::memmove(v.data(), &*b, s);
568 337921 : }
569 : } else {
570 : v.assign(&*b, &*e);
571 : }
572 383595 : }
573 : };
574 :
575 : #endif // BITCOIN_PREVECTOR_H
|
