Line data Source code
1 : // Copyright (c) 2015 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 PIVX_PREVECTOR_H
6 : #define PIVX_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 <iterator>
16 : #include <type_traits>
17 :
18 : #pragma pack(push, 1)
19 : /** Implements a drop-in replacement for std::vector<T> which stores up to N
20 : * elements directly (without heap allocation). The types Size and Diff are
21 : * used to store element counts, and can be any unsigned + signed type.
22 : *
23 : * Storage layout is either:
24 : * - Direct allocation:
25 : * - Size _size: the number of used elements (between 0 and N)
26 : * - T direct[N]: an array of N elements of type T
27 : * (only the first _size are initialized).
28 : * - Indirect allocation:
29 : * - Size _size: the number of used elements plus N + 1
30 : * - Size capacity: the number of allocated elements
31 : * - T* indirect: a pointer to an array of capacity elements of type T
32 : * (only the first _size are initialized).
33 : *
34 : * The data type T must be movable by memmove/realloc(). Once we switch to C++,
35 : * move constructors can be used instead.
36 : */
37 : template<unsigned int N, typename T, typename Size = uint32_t, typename Diff = int32_t>
38 : class prevector {
39 : public:
40 : typedef Size size_type;
41 : typedef Diff difference_type;
42 : typedef T value_type;
43 : typedef value_type& reference;
44 : typedef const value_type& const_reference;
45 : typedef value_type* pointer;
46 : typedef const value_type* const_pointer;
47 :
48 : class iterator {
49 : T* ptr;
50 : public:
51 : typedef Diff difference_type;
52 : typedef T value_type;
53 : typedef T* pointer;
54 : typedef T& reference;
55 : typedef std::random_access_iterator_tag iterator_category;
56 266833922 : iterator(T* ptr_) : ptr(ptr_) {}
57 5165849 : T& operator*() const { return *ptr; }
58 : T* operator->() const { return ptr; }
59 2717630 : T& operator[](size_type pos) { return ptr[pos]; }
60 : const T& operator[](size_type pos) const { return ptr[pos]; }
61 178535826 : iterator& operator++() { ptr++; return *this; }
62 : iterator& operator--() { ptr--; return *this; }
63 : iterator operator++(int) { iterator copy(*this); ++(*this); return copy; }
64 : iterator operator--(int) { iterator copy(*this); --(*this); return copy; }
65 114307054 : difference_type friend operator-(iterator a, iterator b) { return (&(*a) - &(*b)); }
66 42730221 : iterator operator+(size_type n) { return iterator(ptr + n); }
67 : iterator& operator+=(size_type n) { ptr += n; return *this; }
68 2717630 : iterator operator-(size_type n) { return iterator(ptr - n); }
69 : iterator& operator-=(size_type n) { ptr -= n; return *this; }
70 : bool operator==(iterator x) const { return ptr == x.ptr; }
71 222479412 : 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 : bool operator<(iterator x) const { return ptr < x.ptr; }
76 : };
77 :
78 : class reverse_iterator {
79 : T* ptr;
80 : public:
81 : typedef Diff difference_type;
82 : typedef T value_type;
83 : typedef T* pointer;
84 : typedef T& reference;
85 : typedef std::bidirectional_iterator_tag iterator_category;
86 : reverse_iterator(T* ptr_) : ptr(ptr_) {}
87 : T& operator*() { return *ptr; }
88 : const T& operator*() const { return *ptr; }
89 : T* operator->() { return ptr; }
90 : const T* operator->() const { return ptr; }
91 : reverse_iterator& operator--() { ptr++; return *this; }
92 : reverse_iterator& operator++() { ptr--; return *this; }
93 : reverse_iterator operator++(int) { reverse_iterator copy(*this); ++(*this); return copy; }
94 : reverse_iterator operator--(int) { reverse_iterator copy(*this); --(*this); return copy; }
95 : bool operator==(reverse_iterator x) const { return ptr == x.ptr; }
96 : bool operator!=(reverse_iterator x) const { return ptr != x.ptr; }
97 : };
98 :
99 : class const_iterator {
100 : const T* ptr;
101 : public:
102 : typedef Diff difference_type;
103 : typedef const T value_type;
104 : typedef const T* pointer;
105 : typedef const T& reference;
106 : typedef std::random_access_iterator_tag iterator_category;
107 669350138 : const_iterator(const T* ptr_) : ptr(ptr_) {}
108 42660737 : const_iterator(iterator x) : ptr(&(*x)) {}
109 2789330360 : const T& operator*() const { return *ptr; }
110 : const T* operator->() const { return ptr; }
111 2353365 : const T& operator[](size_type pos) const { return ptr[pos]; }
112 3146334530 : const_iterator& operator++() { ptr++; return *this; }
113 0 : const_iterator& operator--() { ptr--; return *this; }
114 136821930 : const_iterator operator++(int) { const_iterator copy(*this); ++(*this); return copy; }
115 : const_iterator operator--(int) { const_iterator copy(*this); --(*this); return copy; }
116 130969548 : difference_type friend operator-(const_iterator a, const_iterator b) { return (&(*a) - &(*b)); }
117 21556666 : const_iterator operator+(size_type n) { return const_iterator(ptr + n); }
118 50420614 : const_iterator& operator+=(size_type n) { ptr += n; return *this; }
119 438 : const_iterator operator-(size_type n) { return const_iterator(ptr - n); }
120 : const_iterator& operator-=(size_type n) { ptr -= n; return *this; }
121 8170 : bool operator==(const_iterator x) const { return ptr == x.ptr; }
122 2312731952 : bool operator!=(const_iterator x) const { return ptr != x.ptr; }
123 148437132 : bool operator>=(const_iterator x) const { return ptr >= x.ptr; }
124 : bool operator<=(const_iterator x) const { return ptr <= x.ptr; }
125 : bool operator>(const_iterator x) const { return ptr > x.ptr; }
126 99629780 : bool operator<(const_iterator x) const { return ptr < x.ptr; }
127 : };
128 :
129 : class const_reverse_iterator {
130 : const T* ptr;
131 : public:
132 : typedef Diff difference_type;
133 : typedef const T value_type;
134 : typedef const T* pointer;
135 : typedef const T& reference;
136 : typedef std::bidirectional_iterator_tag iterator_category;
137 : const_reverse_iterator(const T* ptr_) : ptr(ptr_) {}
138 : const_reverse_iterator(reverse_iterator x) : ptr(&(*x)) {}
139 : const T& operator*() const { return *ptr; }
140 : const T* operator->() const { return ptr; }
141 : const_reverse_iterator& operator--() { ptr++; return *this; }
142 : const_reverse_iterator& operator++() { ptr--; return *this; }
143 : const_reverse_iterator operator++(int) { const_reverse_iterator copy(*this); ++(*this); return copy; }
144 : const_reverse_iterator operator--(int) { const_reverse_iterator copy(*this); --(*this); return copy; }
145 : bool operator==(const_reverse_iterator x) const { return ptr == x.ptr; }
146 : bool operator!=(const_reverse_iterator x) const { return ptr != x.ptr; }
147 : };
148 :
149 : private:
150 : size_type _size = 0;
151 : union direct_or_indirect {
152 : char direct[sizeof(T) * N];
153 : struct {
154 : size_type capacity;
155 : char* indirect;
156 : };
157 : } _union = {};
158 :
159 638949716 : T* direct_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.direct) + pos; }
160 541734850 : const T* direct_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.direct) + pos; }
161 880708459 : T* indirect_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.indirect) + pos; }
162 134141125 : const T* indirect_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.indirect) + pos; }
163 4231126204 : bool is_direct() const { return _size <= N; }
164 :
165 169264089 : void change_capacity(size_type new_capacity) {
166 169264089 : if (new_capacity <= N) {
167 145000448 : if (!is_direct()) {
168 18418 : T* indirect = indirect_ptr(0);
169 18418 : T* src = indirect;
170 18418 : T* dst = direct_ptr(0);
171 18418 : memcpy(dst, src, size() * sizeof(T));
172 18418 : free(indirect);
173 18418 : _size -= N + 1;
174 : }
175 : } else {
176 24263648 : if (!is_direct()) {
177 : /* FIXME: Because malloc/realloc here won't call new_handler if allocation fails, assert
178 : success. These should instead use an allocator or new/delete so that handlers
179 : are called as necessary, but performance would be slightly degraded by doing so. */
180 14178 : _union.indirect = static_cast<char*>(realloc(_union.indirect, ((size_t)sizeof(T)) * new_capacity));
181 14178 : assert(_union.indirect);
182 14178 : _union.capacity = new_capacity;
183 : } else {
184 24249470 : char* new_indirect = static_cast<char*>(malloc(((size_t)sizeof(T)) * new_capacity));
185 24249470 : assert(new_indirect);
186 24249470 : T* src = direct_ptr(0);
187 24249470 : T* dst = reinterpret_cast<T*>(new_indirect);
188 24249470 : memcpy(dst, src, size() * sizeof(T));
189 24249470 : _union.indirect = new_indirect;
190 24249470 : _union.capacity = new_capacity;
191 24249470 : _size += N + 1;
192 : }
193 : }
194 169264089 : }
195 :
196 1488338760 : T* item_ptr(difference_type pos) { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
197 692771674 : const T* item_ptr(difference_type pos) const { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
198 :
199 9441868 : void fill(T* dst, ptrdiff_t count, const T& value = T{}) {
200 9444108 : std::fill_n(dst, count, value);
201 : }
202 :
203 : template<typename InputIterator>
204 81992092 : void fill(T* dst, InputIterator first, InputIterator last) {
205 2482470609 : while (first != last) {
206 2397370866 : new(static_cast<void*>(dst)) T(*first);
207 2394880183 : ++dst;
208 2479368483 : ++first;
209 : }
210 : }
211 :
212 : public:
213 24058 : void assign(size_type n, const T& val) {
214 24058 : clear();
215 24058 : if (capacity() < n) {
216 13096 : change_capacity(n);
217 : }
218 24058 : _size += n;
219 48116 : fill(item_ptr(0), n, val);
220 24058 : }
221 :
222 : template<typename InputIterator>
223 9588576 : void assign(InputIterator first, InputIterator last) {
224 9588576 : size_type n = last - first;
225 9588576 : clear();
226 9588576 : if (capacity() < n) {
227 365522 : change_capacity(n);
228 : }
229 9588576 : _size += n;
230 12079147 : fill(item_ptr(0), first, last);
231 9588576 : }
232 :
233 113998966 : prevector() {}
234 :
235 : explicit prevector(size_type n) {
236 : resize(n);
237 : }
238 :
239 3972805 : explicit prevector(size_type n, const T& val = T()) {
240 3972805 : change_capacity(n);
241 3972805 : _size += n;
242 7945620 : fill(item_ptr(0), n, val);
243 3972805 : }
244 :
245 : template<typename InputIterator>
246 7583461 : prevector(InputIterator first, InputIterator last) {
247 7583461 : size_type n = last - first;
248 7583461 : change_capacity(n);
249 7583461 : _size += n;
250 7583576 : fill(item_ptr(0), first, last);
251 7583461 : }
252 :
253 65431454 : prevector(const prevector<N, T, Size, Diff>& other) {
254 65431454 : size_type n = other.size();
255 65431454 : change_capacity(n);
256 65431454 : _size += n;
257 65431454 : fill(item_ptr(0), other.begin(), other.end());
258 65431454 : }
259 :
260 3318002 : prevector(prevector<N, T, Size, Diff>&& other) {
261 3318002 : swap(other);
262 : }
263 :
264 8990224 : prevector& operator=(const prevector<N, T, Size, Diff>& other) {
265 8990224 : if (&other == this) {
266 : return *this;
267 : }
268 17954328 : assign(other.begin(), other.end());
269 8977166 : return *this;
270 : }
271 :
272 27971464 : prevector& operator=(prevector<N, T, Size, Diff>&& other) {
273 27971464 : swap(other);
274 : return *this;
275 : }
276 :
277 1593071049 : size_type size() const {
278 656205484 : return is_direct() ? _size : _size - N - 1;
279 : }
280 :
281 172084208 : bool empty() const {
282 172084208 : return size() == 0;
283 : }
284 :
285 68592268 : iterator begin() { return iterator(item_ptr(0)); }
286 195370597 : const_iterator begin() const { return const_iterator(item_ptr(0)); }
287 201711802 : iterator end() { return iterator(item_ptr(size())); }
288 712097914 : const_iterator end() const { return const_iterator(item_ptr(size())); }
289 :
290 : reverse_iterator rbegin() { return reverse_iterator(item_ptr(size() - 1)); }
291 : const_reverse_iterator rbegin() const { return const_reverse_iterator(item_ptr(size() - 1)); }
292 : reverse_iterator rend() { return reverse_iterator(item_ptr(-1)); }
293 : const_reverse_iterator rend() const { return const_reverse_iterator(item_ptr(-1)); }
294 :
295 91042811 : size_t capacity() const {
296 15548832 : if (is_direct()) {
297 : return N;
298 : } else {
299 6791380 : return _union.capacity;
300 : }
301 : }
302 :
303 35108966 : T& operator[](size_type pos) {
304 56965988 : return *item_ptr(pos);
305 : }
306 :
307 139498411 : const T& operator[](size_type pos) const {
308 218437170 : return *item_ptr(pos);
309 : }
310 :
311 100754008 : void resize(size_type new_size) {
312 100754008 : size_type cur_size = size();
313 100754008 : if (cur_size == new_size) {
314 : return;
315 : }
316 6944248 : if (cur_size > new_size) {
317 3011796 : erase(item_ptr(new_size), end());
318 1505899 : return;
319 : }
320 5440397 : if (new_size > capacity()) {
321 634 : change_capacity(new_size);
322 : }
323 5438349 : ptrdiff_t increase = new_size - cur_size;
324 10879986 : fill(item_ptr(cur_size), increase);
325 5438349 : _size += increase;
326 : }
327 :
328 15497 : void reserve(size_type new_capacity) {
329 17872 : if (new_capacity > capacity()) {
330 257 : change_capacity(new_capacity);
331 : }
332 : }
333 :
334 80094439 : void shrink_to_fit() {
335 80094439 : change_capacity(size());
336 : }
337 :
338 95305433 : void clear() {
339 95305433 : resize(0);
340 : }
341 :
342 14984522 : iterator insert(iterator pos, const T& value) {
343 14984522 : size_type p = pos - begin();
344 14984522 : size_type new_size = size() + 1;
345 14984522 : if (capacity() < new_size) {
346 1800 : change_capacity(new_size + (new_size >> 1));
347 : }
348 29969034 : T* ptr = item_ptr(p);
349 14984522 : memmove(ptr + 1, ptr, (size() - p) * sizeof(T));
350 14984522 : _size++;
351 14984522 : new(static_cast<void*>(ptr)) T(value);
352 14984522 : return iterator(ptr);
353 : }
354 :
355 8896 : void insert(iterator pos, size_type count, const T& value) {
356 8896 : size_type p = pos - begin();
357 8896 : size_type new_size = size() + count;
358 8896 : if (capacity() < new_size) {
359 320 : change_capacity(new_size + (new_size >> 1));
360 : }
361 17792 : T* ptr = item_ptr(p);
362 8896 : memmove(ptr + count, ptr, (size() - p) * sizeof(T));
363 8896 : _size += count;
364 17792 : fill(item_ptr(p), count, value);
365 8896 : }
366 :
367 : template<typename InputIterator>
368 55701402 : void insert(iterator pos, InputIterator first, InputIterator last) {
369 55701402 : size_type p = pos - begin();
370 55701402 : difference_type count = last - first;
371 55701402 : size_type new_size = size() + count;
372 55701402 : if (capacity() < new_size) {
373 10013751 : change_capacity(new_size + (new_size >> 1));
374 : }
375 167103704 : memmove(item_ptr(p + count), item_ptr(p), (size() - p) * sizeof(T));
376 55701402 : _size += count;
377 1040144781 : while (first != last) {
378 1968889958 : new(static_cast<void*>(item_ptr(p))) T(*first);
379 984442989 : ++p;
380 1040142321 : ++first;
381 : }
382 55701402 : }
383 :
384 5265422 : inline void resize_uninitialized(size_type new_size) {
385 : // resize_uninitialized changes the size of the prevector but does not initialize it.
386 : // If size < new_size, the added elements must be initialized explicitly.
387 5265422 : if (capacity() < new_size) {
388 1786339 : change_capacity(new_size);
389 1786339 : _size += new_size - size();
390 1786339 : return;
391 : }
392 3479085 : if (new_size < size()) {
393 7296 : erase(item_ptr(new_size), end());
394 : } else {
395 3475437 : _size += new_size - size();
396 : }
397 : }
398 :
399 15104 : iterator erase(iterator pos) {
400 15104 : return erase(pos, pos + 1);
401 : }
402 :
403 1538603 : iterator erase(iterator first, iterator last) {
404 : // Erase is not allowed to the change the object's capacity. That means
405 : // that when starting with an indirectly allocated prevector with
406 : // size and capacity > N, the result may be a still indirectly allocated
407 : // prevector with size <= N and capacity > N. A shrink_to_fit() call is
408 : // necessary to switch to the (more efficient) directly allocated
409 : // representation (with capacity N and size <= N).
410 1538603 : iterator p = first;
411 1538603 : char* endp = (char*)&(*end());
412 : if (!std::is_trivially_destructible<T>::value) {
413 : while (p != last) {
414 : (*p).~T();
415 : _size--;
416 : ++p;
417 : }
418 : } else {
419 1538603 : _size -= last - p;
420 : }
421 1538603 : memmove(&(*first), &(*last), endp - ((char*)(&(*last))));
422 1538603 : return first;
423 : }
424 :
425 : template<typename... Args>
426 13691 : void emplace_back(Args&&... args) {
427 13691 : size_type new_size = size() + 1;
428 13691 : if (capacity() < new_size) {
429 99 : change_capacity(new_size + (new_size >> 1));
430 : }
431 19526 : new(item_ptr(size())) T(std::forward<Args>(args)...);
432 13691 : _size++;
433 13691 : }
434 :
435 13691 : void push_back(const T& value) {
436 13691 : emplace_back(value);
437 : }
438 :
439 3776 : void pop_back() {
440 3776 : erase(end() - 1, end());
441 3776 : }
442 :
443 : T& front() {
444 : return *item_ptr(0);
445 : }
446 :
447 : const T& front() const {
448 : return *item_ptr(0);
449 : }
450 :
451 : T& back() {
452 : return *item_ptr(size() - 1);
453 : }
454 :
455 57685 : const T& back() const {
456 115370 : return *item_ptr(size() - 1);
457 : }
458 :
459 28573815 : void swap(prevector<N, T, Size, Diff>& other) {
460 28573503 : std::swap(_union, other._union);
461 24456144 : std::swap(_size, other._size);
462 : }
463 :
464 202676226 : ~prevector() {
465 : if (!std::is_trivially_destructible<T>::value) {
466 : clear();
467 : }
468 202394493 : if (!is_direct()) {
469 24230589 : free(_union.indirect);
470 : _union.indirect = nullptr;
471 : }
472 64 : }
473 :
474 1618039 : bool operator==(const prevector<N, T, Size, Diff>& other) const {
475 1969518 : if (other.size() != size()) {
476 : return false;
477 : }
478 1613026 : const_iterator b1 = begin();
479 1613026 : const_iterator b2 = other.begin();
480 1613026 : const_iterator e1 = end();
481 29804943 : while (b1 != e1) {
482 28196121 : if ((*b1) != (*b2)) {
483 : return false;
484 : }
485 28191988 : ++b1;
486 29804943 : ++b2;
487 : }
488 : return true;
489 : }
490 :
491 33767 : bool operator!=(const prevector<N, T, Size, Diff>& other) const {
492 33767 : return !(*this == other);
493 : }
494 :
495 1315007 : bool operator<(const prevector<N, T, Size, Diff>& other) const {
496 1522215 : if (size() < other.size()) {
497 : return true;
498 : }
499 1297670 : if (size() > other.size()) {
500 : return false;
501 : }
502 1256269 : const_iterator b1 = begin();
503 1256269 : const_iterator b2 = other.begin();
504 1256269 : const_iterator e1 = end();
505 4110471 : while (b1 != e1) {
506 3746417 : if ((*b1) < (*b2)) {
507 : return true;
508 : }
509 3069190 : if ((*b2) < (*b1)) {
510 : return false;
511 : }
512 2854198 : ++b1;
513 4110471 : ++b2;
514 : }
515 : return false;
516 : }
517 :
518 29369860 : size_t allocated_memory() const {
519 29369860 : if (is_direct()) {
520 : return 0;
521 : } else {
522 1248799 : return ((size_t)(sizeof(T))) * _union.capacity;
523 : }
524 : }
525 :
526 13586 : value_type* data() {
527 13585 : return item_ptr(0);
528 : }
529 :
530 95425968 : const value_type* data() const {
531 95483447 : return item_ptr(0);
532 : }
533 : };
534 : #pragma pack(pop)
535 :
536 : #endif // PIVX_PREVECTOR_H
|
