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 <stdlib.h>
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 : public:
39 : typedef Size size_type;
40 : typedef Diff difference_type;
41 : typedef T value_type;
42 : typedef value_type& reference;
43 : typedef const value_type& const_reference;
44 : typedef value_type* pointer;
45 : typedef const value_type* const_pointer;
46 :
47 : class iterator {
48 : T* ptr;
49 : public:
50 : typedef Diff difference_type;
51 : typedef T value_type;
52 : typedef T* pointer;
53 : typedef T& reference;
54 : typedef std::random_access_iterator_tag iterator_category;
55 124273385 : iterator(T* ptr_) : ptr(ptr_) {}
56 51964878 : T& operator*() const { return *ptr; }
57 : T* operator->() const { return ptr; }
58 2183488 : T& operator[](size_type pos) { return ptr[pos]; }
59 : const T& operator[](size_type pos) const { return ptr[pos]; }
60 6011959 : iterator& operator++() { ptr++; return *this; }
61 : iterator& operator--() { ptr--; return *this; }
62 : iterator operator++(int) { iterator copy(*this); ++(*this); return copy; }
63 : iterator operator--(int) { iterator copy(*this); --(*this); return copy; }
64 18006851 : difference_type friend operator-(iterator a, iterator b) { return (&(*a) - &(*b)); }
65 4519872 : iterator operator+(size_type n) { return iterator(ptr + n); }
66 : iterator& operator+=(size_type n) { ptr += n; return *this; }
67 2189760 : iterator operator-(size_type n) { return iterator(ptr - n); }
68 : iterator& operator-=(size_type n) { ptr -= n; return *this; }
69 : bool operator==(iterator x) const { return ptr == x.ptr; }
70 6598860 : bool operator!=(iterator x) const { return ptr != x.ptr; }
71 : bool operator>=(iterator x) const { return ptr >= x.ptr; }
72 : 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 : };
76 :
77 : class reverse_iterator {
78 : T* ptr;
79 : public:
80 : typedef Diff difference_type;
81 : typedef T value_type;
82 : typedef T* pointer;
83 : typedef T& reference;
84 : typedef std::bidirectional_iterator_tag iterator_category;
85 1072128 : reverse_iterator(T* ptr_) : ptr(ptr_) {}
86 2183488 : T& operator*() { return *ptr; }
87 : const T& operator*() const { return *ptr; }
88 : T* operator->() { return ptr; }
89 : const T* operator->() const { return ptr; }
90 : reverse_iterator& operator--() { ptr++; return *this; }
91 2183488 : reverse_iterator& operator++() { ptr--; return *this; }
92 : reverse_iterator operator++(int) { reverse_iterator copy(*this); ++(*this); return copy; }
93 : reverse_iterator operator--(int) { reverse_iterator copy(*this); --(*this); return copy; }
94 : bool operator==(reverse_iterator x) const { return ptr == x.ptr; }
95 2451520 : bool operator!=(reverse_iterator x) const { return ptr != x.ptr; }
96 : };
97 :
98 : class const_iterator {
99 : const T* ptr;
100 : public:
101 : typedef Diff difference_type;
102 : typedef const T value_type;
103 : typedef const T* pointer;
104 : typedef const T& reference;
105 : typedef std::random_access_iterator_tag iterator_category;
106 746075909 : const_iterator(const T* ptr_) : ptr(ptr_) {}
107 4021789 : const_iterator(iterator x) : ptr(&(*x)) {}
108 4295327883 : const T& operator*() const { return *ptr; }
109 : const T* operator->() const { return ptr; }
110 474871 : const T& operator[](size_type pos) const { return ptr[pos]; }
111 3639285687 : const_iterator& operator++() { ptr++; return *this; }
112 : const_iterator& operator--() { ptr--; return *this; }
113 84627027 : const_iterator operator++(int) { const_iterator copy(*this); ++(*this); return copy; }
114 : const_iterator operator--(int) { const_iterator copy(*this); --(*this); return copy; }
115 264919177 : difference_type friend operator-(const_iterator a, const_iterator b) { return (&(*a) - &(*b)); }
116 17046151 : const_iterator operator+(size_type n) { return const_iterator(ptr + n); }
117 73339584 : const_iterator& operator+=(size_type n) { ptr += n; return *this; }
118 590 : const_iterator operator-(size_type n) { return const_iterator(ptr - n); }
119 : const_iterator& operator-=(size_type n) { ptr -= n; return *this; }
120 10887 : bool operator==(const_iterator x) const { return ptr == x.ptr; }
121 3591934563 : bool operator!=(const_iterator x) const { return ptr != x.ptr; }
122 85673082 : bool operator>=(const_iterator x) const { return ptr >= x.ptr; }
123 : bool operator<=(const_iterator x) const { return ptr <= x.ptr; }
124 : bool operator>(const_iterator x) const { return ptr > x.ptr; }
125 84357825 : bool operator<(const_iterator x) const { return ptr < x.ptr; }
126 : };
127 :
128 : class const_reverse_iterator {
129 : const T* ptr;
130 : public:
131 : typedef Diff difference_type;
132 : typedef const T value_type;
133 : typedef const T* pointer;
134 : typedef const T& reference;
135 : typedef std::bidirectional_iterator_tag iterator_category;
136 1072128 : const_reverse_iterator(const T* ptr_) : ptr(ptr_) {}
137 : const_reverse_iterator(reverse_iterator x) : ptr(&(*x)) {}
138 2183488 : const T& operator*() const { return *ptr; }
139 : const T* operator->() const { return ptr; }
140 : const_reverse_iterator& operator--() { ptr++; return *this; }
141 2183488 : const_reverse_iterator& operator++() { ptr--; return *this; }
142 : const_reverse_iterator operator++(int) { const_reverse_iterator copy(*this); ++(*this); return copy; }
143 : const_reverse_iterator operator--(int) { const_reverse_iterator copy(*this); --(*this); return copy; }
144 : bool operator==(const_reverse_iterator x) const { return ptr == x.ptr; }
145 2451520 : bool operator!=(const_reverse_iterator x) const { return ptr != x.ptr; }
146 : };
147 :
148 : private:
149 : #pragma pack(push, 1)
150 : union direct_or_indirect {
151 : char direct[sizeof(T) * N];
152 : struct {
153 : char* indirect;
154 : size_type capacity;
155 : } indirect_contents;
156 : };
157 : #pragma pack(pop)
158 118894598 : alignas(char*) direct_or_indirect _union = {};
159 118894598 : size_type _size = 0;
160 :
161 : static_assert(alignof(char*) % alignof(size_type) == 0 && sizeof(char*) % alignof(size_type) == 0, "size_type cannot have more restrictive alignment requirement than pointer");
162 : static_assert(alignof(char*) % alignof(T) == 0, "value_type T cannot have more restrictive alignment requirement than pointer");
163 :
164 94859674 : T* direct_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.direct) + pos; }
165 270586716 : const T* direct_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.direct) + pos; }
166 27102083 : T* indirect_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.indirect_contents.indirect) + pos; }
167 165171364 : const T* indirect_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.indirect_contents.indirect) + pos; }
168 1565937363 : bool is_direct() const { return _size <= N; }
169 :
170 102417630 : void change_capacity(size_type new_capacity) {
171 102417630 : if (new_capacity <= N) {
172 97188942 : if (!is_direct()) {
173 57234 : T* indirect = indirect_ptr(0);
174 : T* src = indirect;
175 57234 : T* dst = direct_ptr(0);
176 57234 : memcpy(dst, src, size() * sizeof(T));
177 57234 : free(indirect);
178 57234 : _size -= N + 1;
179 57234 : }
180 : } else {
181 5228828 : if (!is_direct()) {
182 : /* FIXME: Because malloc/realloc here won't call new_handler if allocation fails, assert
183 : success. These should instead use an allocator or new/delete so that handlers
184 : are called as necessary, but performance would be slightly degraded by doing so. */
185 37257 : _union.indirect_contents.indirect = static_cast<char*>(realloc(_union.indirect_contents.indirect, ((size_t)sizeof(T)) * new_capacity));
186 37257 : assert(_union.indirect_contents.indirect);
187 37257 : _union.indirect_contents.capacity = new_capacity;
188 37257 : } else {
189 5191535 : char* new_indirect = static_cast<char*>(malloc(((size_t)sizeof(T)) * new_capacity));
190 5191535 : assert(new_indirect);
191 5191936 : T* src = direct_ptr(0);
192 206206 : T* dst = reinterpret_cast<T*>(new_indirect);
193 5191936 : memcpy(dst, src, size() * sizeof(T));
194 5191936 : _union.indirect_contents.indirect = new_indirect;
195 5191936 : _union.indirect_contents.capacity = new_capacity;
196 5191936 : _size += N + 1;
197 : }
198 : }
199 102418066 : }
200 :
201 116651937 : T* item_ptr(difference_type pos) { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
202 435818470 : const T* item_ptr(difference_type pos) const { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
203 :
204 2729273 : void fill(T* dst, ptrdiff_t count, const T& value = T{}) {
205 2729273 : std::fill_n(dst, count, value);
206 2729273 : }
207 :
208 : template<typename InputIterator>
209 46344045 : void fill(T* dst, InputIterator first, InputIterator last) {
210 3458372532 : while (first != last) {
211 3412032998 : new(static_cast<void*>(dst)) T(*first);
212 3412032998 : ++dst;
213 3412032998 : ++first;
214 : }
215 46344441 : }
216 :
217 : public:
218 87377 : void assign(size_type n, const T& val) {
219 87377 : clear();
220 87377 : if (capacity() < n) {
221 48197 : change_capacity(n);
222 48197 : }
223 87377 : _size += n;
224 87377 : fill(item_ptr(0), n, val);
225 87377 : }
226 :
227 : template<typename InputIterator>
228 11282427 : void assign(InputIterator first, InputIterator last) {
229 11282427 : size_type n = last - first;
230 11282427 : clear();
231 11282427 : if (capacity() < n) {
232 673530 : change_capacity(n);
233 673530 : }
234 11282427 : _size += n;
235 11282427 : fill(item_ptr(0), first, last);
236 11282427 : }
237 :
238 79478714 : prevector() {}
239 :
240 : explicit prevector(size_type n) {
241 : resize(n);
242 : }
243 :
244 4923714 : explicit prevector(size_type n, const T& val) {
245 2461857 : change_capacity(n);
246 2461857 : _size += n;
247 2461857 : fill(item_ptr(0), n, val);
248 4923714 : }
249 :
250 : template<typename InputIterator>
251 2320501 : prevector(InputIterator first, InputIterator last) {
252 1784437 : size_type n = last - first;
253 1784437 : change_capacity(n);
254 1784437 : _size += n;
255 1784437 : fill(item_ptr(0), first, last);
256 2320501 : }
257 :
258 28318307 : prevector(const prevector<N, T, Size, Diff>& other) {
259 25920857 : size_type n = other.size();
260 25920857 : change_capacity(n);
261 25920857 : _size += n;
262 25920857 : fill(item_ptr(0), other.begin(), other.end());
263 28318307 : }
264 :
265 10604085 : prevector(prevector<N, T, Size, Diff>&& other) {
266 9985787 : swap(other);
267 10604085 : }
268 :
269 11001677 : prevector& operator=(const prevector<N, T, Size, Diff>& other) {
270 11001677 : if (&other == this) {
271 12986 : return *this;
272 : }
273 10988691 : assign(other.begin(), other.end());
274 10988691 : return *this;
275 11001677 : }
276 :
277 21167869 : prevector& operator=(prevector<N, T, Size, Diff>&& other) {
278 21167869 : swap(other);
279 21167869 : return *this;
280 : }
281 :
282 736137904 : size_type size() const {
283 736137904 : return is_direct() ? _size : _size - N - 1;
284 : }
285 :
286 31714275 : bool empty() const {
287 31714275 : return size() == 0;
288 : }
289 :
290 23226672 : iterator begin() { return iterator(item_ptr(0)); }
291 133832224 : const_iterator begin() const { return const_iterator(item_ptr(0)); }
292 21932602 : iterator end() { return iterator(item_ptr(size())); }
293 222190780 : const_iterator end() const { return const_iterator(item_ptr(size())); }
294 :
295 268032 : reverse_iterator rbegin() { return reverse_iterator(item_ptr(size() - 1)); }
296 268032 : const_reverse_iterator rbegin() const { return const_reverse_iterator(item_ptr(size() - 1)); }
297 268032 : reverse_iterator rend() { return reverse_iterator(item_ptr(-1)); }
298 268032 : const_reverse_iterator rend() const { return const_reverse_iterator(item_ptr(-1)); }
299 :
300 30309263 : size_t capacity() const {
301 30309263 : if (is_direct()) {
302 28736745 : return N;
303 : } else {
304 1572486 : return _union.indirect_contents.capacity;
305 : }
306 30309341 : }
307 :
308 10715496 : T& operator[](size_type pos) {
309 10715496 : return *item_ptr(pos);
310 : }
311 :
312 34367576 : const T& operator[](size_type pos) const {
313 34367576 : return *item_ptr(pos);
314 : }
315 :
316 82503361 : void resize(size_type new_size) {
317 82503361 : size_type cur_size = size();
318 82503361 : if (cur_size == new_size) {
319 81508414 : return;
320 : }
321 994936 : if (cur_size > new_size) {
322 831154 : erase(item_ptr(new_size), end());
323 831154 : return;
324 : }
325 163782 : if (new_size > capacity()) {
326 79704 : change_capacity(new_size);
327 79704 : }
328 163782 : ptrdiff_t increase = new_size - cur_size;
329 163782 : fill(item_ptr(cur_size), increase);
330 163782 : _size += increase;
331 82503351 : }
332 :
333 14648 : void reserve(size_type new_capacity) {
334 14648 : if (new_capacity > capacity()) {
335 907 : change_capacity(new_capacity);
336 907 : }
337 14648 : }
338 :
339 69279843 : void shrink_to_fit() {
340 69279843 : change_capacity(size());
341 69279843 : }
342 :
343 82324505 : void clear() {
344 82324505 : resize(0);
345 82324505 : }
346 :
347 9435622 : iterator insert(iterator pos, const T& value) {
348 9435622 : size_type p = pos - begin();
349 9435622 : size_type new_size = size() + 1;
350 9435622 : if (capacity() < new_size) {
351 11321 : change_capacity(new_size + (new_size >> 1));
352 11321 : }
353 9435796 : T* ptr = item_ptr(p);
354 9435796 : memmove(ptr + 1, ptr, (size() - p) * sizeof(T));
355 9435796 : _size++;
356 9435796 : new(static_cast<void*>(ptr)) T(value);
357 9435796 : return iterator(ptr);
358 9435796 : }
359 :
360 16256 : void insert(iterator pos, size_type count, const T& value) {
361 16256 : size_type p = pos - begin();
362 16256 : size_type new_size = size() + count;
363 16256 : if (capacity() < new_size) {
364 192 : change_capacity(new_size + (new_size >> 1));
365 192 : }
366 16256 : T* ptr = item_ptr(p);
367 16256 : memmove(ptr + count, ptr, (size() - p) * sizeof(T));
368 16256 : _size += count;
369 16256 : fill(item_ptr(p), count, value);
370 16256 : }
371 :
372 : template<typename InputIterator>
373 7356510 : void insert(iterator pos, InputIterator first, InputIterator last) {
374 7356510 : size_type p = pos - begin();
375 7356510 : difference_type count = last - first;
376 7356510 : size_type new_size = size() + count;
377 7356510 : if (capacity() < new_size) {
378 1226740 : change_capacity(new_size + (new_size >> 1));
379 1226740 : }
380 7356628 : T* ptr = item_ptr(p);
381 7356628 : memmove(ptr + count, ptr, (size() - p) * sizeof(T));
382 7356628 : _size += count;
383 7356628 : fill(ptr, first, last);
384 7356628 : }
385 :
386 1546008 : inline void resize_uninitialized(size_type new_size) {
387 : // resize_uninitialized changes the size of the prevector but does not initialize it.
388 : // If size < new_size, the added elements must be initialized explicitly.
389 1546008 : if (capacity() < new_size) {
390 930936 : change_capacity(new_size);
391 930936 : _size += new_size - size();
392 930936 : return;
393 : }
394 615074 : if (new_size < size()) {
395 3904 : erase(item_ptr(new_size), end());
396 3904 : } else {
397 611170 : _size += new_size - size();
398 : }
399 1546009 : }
400 :
401 28480 : iterator erase(iterator pos) {
402 28480 : return erase(pos, pos + 1);
403 : }
404 :
405 890610 : iterator erase(iterator first, iterator last) {
406 : // Erase is not allowed to the change the object's capacity. That means
407 : // that when starting with an indirectly allocated prevector with
408 : // size and capacity > N, the result may be a still indirectly allocated
409 : // prevector with size <= N and capacity > N. A shrink_to_fit() call is
410 : // necessary to switch to the (more efficient) directly allocated
411 : // representation (with capacity N and size <= N).
412 890610 : iterator p = first;
413 890610 : char* endp = (char*)&(*end());
414 : if (!std::is_trivially_destructible<T>::value) {
415 : while (p != last) {
416 : (*p).~T();
417 : _size--;
418 : ++p;
419 : }
420 : } else {
421 890610 : _size -= last - p;
422 : }
423 890610 : memmove(&(*first), &(*last), endp - ((char*)(&(*last))));
424 890610 : return first;
425 890610 : }
426 :
427 : template<typename... Args>
428 403020 : void emplace_back(Args&&... args) {
429 403020 : size_type new_size = size() + 1;
430 403020 : if (capacity() < new_size) {
431 101 : change_capacity(new_size + (new_size >> 1));
432 101 : }
433 403020 : new(item_ptr(size())) T(std::forward<Args>(args)...);
434 403020 : _size++;
435 403020 : }
436 :
437 15820 : void push_back(const T& value) {
438 15820 : emplace_back(value);
439 15820 : }
440 :
441 6272 : void pop_back() {
442 6272 : erase(end() - 1, end());
443 6272 : }
444 :
445 : T& front() {
446 : return *item_ptr(0);
447 : }
448 :
449 : const T& front() const {
450 : return *item_ptr(0);
451 : }
452 :
453 387200 : T& back() {
454 387200 : return *item_ptr(size() - 1);
455 : }
456 :
457 74605 : const T& back() const {
458 74605 : return *item_ptr(size() - 1);
459 : }
460 :
461 31896680 : void swap(prevector<N, T, Size, Diff>& other) {
462 31896680 : std::swap(_union, other._union);
463 31896680 : std::swap(_size, other._size);
464 31896680 : }
465 :
466 125622699 : ~prevector() {
467 : if (!std::is_trivially_destructible<T>::value) {
468 : clear();
469 : }
470 118883496 : if (!is_direct()) {
471 5134055 : free(_union.indirect_contents.indirect);
472 5134730 : _union.indirect_contents.indirect = nullptr;
473 5134730 : }
474 125627504 : }
475 :
476 1309859 : bool operator==(const prevector<N, T, Size, Diff>& other) const {
477 1309859 : if (other.size() != size()) {
478 60 : return false;
479 : }
480 1309799 : const_iterator b1 = begin();
481 1309799 : const_iterator b2 = other.begin();
482 1309799 : const_iterator e1 = end();
483 19076971 : while (b1 != e1) {
484 18069562 : if ((*b1) != (*b2)) {
485 302390 : return false;
486 : }
487 17767172 : ++b1;
488 17767172 : ++b2;
489 : }
490 1007409 : return true;
491 1309859 : }
492 :
493 4547 : bool operator!=(const prevector<N, T, Size, Diff>& other) const {
494 4547 : return !(*this == other);
495 : }
496 :
497 21307950 : bool operator<(const prevector<N, T, Size, Diff>& other) const {
498 21307950 : if (size() < other.size()) {
499 1237364 : return true;
500 : }
501 20070586 : if (size() > other.size()) {
502 812931 : return false;
503 : }
504 19257655 : const_iterator b1 = begin();
505 19257655 : const_iterator b2 = other.begin();
506 19257655 : const_iterator e1 = end();
507 40844388 : while (b1 != e1) {
508 40426854 : if ((*b1) < (*b2)) {
509 13476036 : return true;
510 : }
511 26950818 : if ((*b2) < (*b1)) {
512 5364085 : return false;
513 : }
514 21586733 : ++b1;
515 21586733 : ++b2;
516 : }
517 417534 : return false;
518 21307950 : }
519 :
520 26806225 : size_t allocated_memory() const {
521 26806225 : if (is_direct()) {
522 25751883 : return 0;
523 : } else {
524 1054342 : return ((size_t)(sizeof(T))) * _union.indirect_contents.capacity;
525 : }
526 26806225 : }
527 :
528 100393 : value_type* data() {
529 100393 : return item_ptr(0);
530 : }
531 :
532 44852496 : const value_type* data() const {
533 44852496 : return item_ptr(0);
534 : }
535 : };
536 :
537 : #endif // BITCOIN_PREVECTOR_H
|
