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 322687549 : iterator(T* ptr_) : ptr(ptr_) {}
57 5638639 : T& operator*() const { return *ptr; }
58 : T* operator->() const { return ptr; }
59 3160190 : T& operator[](size_type pos) { return ptr[pos]; }
60 : const T& operator[](size_type pos) const { return ptr[pos]; }
61 216422041 : 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 138681533 : difference_type friend operator-(iterator a, iterator b) { return (&(*a) - &(*b)); }
66 51715694 : iterator operator+(size_type n) { return iterator(ptr + n); }
67 : iterator& operator+=(size_type n) { ptr += n; return *this; }
68 3160190 : 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 269356237 : 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 708907721 : const_iterator(const T* ptr_) : ptr(ptr_) {}
108 51648356 : const_iterator(iterator x) : ptr(&(*x)) {}
109 3035224528 : const T& operator*() const { return *ptr; }
110 : const T* operator->() const { return ptr; }
111 2224977 : const T& operator[](size_type pos) const { return ptr[pos]; }
112 3336579488 : const_iterator& operator++() { ptr++; return *this; }
113 0 : const_iterator& operator--() { ptr--; return *this; }
114 150038718 : const_iterator operator++(int) { const_iterator copy(*this); ++(*this); return copy; }
115 : const_iterator operator--(int) { const_iterator copy(*this); --(*this); return copy; }
116 148121069 : difference_type friend operator-(const_iterator a, const_iterator b) { return (&(*a) - &(*b)); }
117 26090657 : const_iterator operator+(size_type n) { return const_iterator(ptr + n); }
118 56363117 : 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 8032 : bool operator==(const_iterator x) const { return ptr == x.ptr; }
122 2243627205 : bool operator!=(const_iterator x) const { return ptr != x.ptr; }
123 162896497 : 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 108720501 : 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 758518995 : T* direct_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.direct) + pos; }
160 552460805 : const T* direct_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.direct) + pos; }
161 1088883157 : T* indirect_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.indirect) + pos; }
162 139143438 : const T* indirect_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.indirect) + pos; }
163 4670440152 : bool is_direct() const { return _size <= N; }
164 :
165 166494468 : void change_capacity(size_type new_capacity) {
166 166494468 : if (new_capacity <= N) {
167 140281738 : if (!is_direct()) {
168 18759 : T* indirect = indirect_ptr(0);
169 18759 : T* src = indirect;
170 18759 : T* dst = direct_ptr(0);
171 18759 : memcpy(dst, src, size() * sizeof(T));
172 18759 : free(indirect);
173 18759 : _size -= N + 1;
174 : }
175 : } else {
176 26212714 : 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 13504 : _union.indirect = static_cast<char*>(realloc(_union.indirect, ((size_t)sizeof(T)) * new_capacity));
181 13504 : assert(_union.indirect);
182 13504 : _union.capacity = new_capacity;
183 : } else {
184 26199182 : char* new_indirect = static_cast<char*>(malloc(((size_t)sizeof(T)) * new_capacity));
185 26199182 : assert(new_indirect);
186 26199182 : T* src = direct_ptr(0);
187 26199182 : T* dst = reinterpret_cast<T*>(new_indirect);
188 26199182 : memcpy(dst, src, size() * sizeof(T));
189 26199182 : _union.indirect = new_indirect;
190 26199182 : _union.capacity = new_capacity;
191 26199182 : _size += N + 1;
192 : }
193 : }
194 166494468 : }
195 :
196 1812639664 : T* item_ptr(difference_type pos) { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
197 706496643 : const T* item_ptr(difference_type pos) const { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
198 :
199 11343362 : void fill(T* dst, ptrdiff_t count, const T& value = T{}) {
200 11346946 : std::fill_n(dst, count, value);
201 : }
202 :
203 : template<typename InputIterator>
204 81682347 : void fill(T* dst, InputIterator first, InputIterator last) {
205 2461960508 : while (first != last) {
206 2377087887 : new(static_cast<void*>(dst)) T(*first);
207 2374524888 : ++dst;
208 2458768107 : ++first;
209 : }
210 : }
211 :
212 : public:
213 24065 : void assign(size_type n, const T& val) {
214 24065 : clear();
215 24065 : if (capacity() < n) {
216 13302 : change_capacity(n);
217 : }
218 24065 : _size += n;
219 48130 : fill(item_ptr(0), n, val);
220 24065 : }
221 :
222 : template<typename InputIterator>
223 8745551 : void assign(InputIterator first, InputIterator last) {
224 8745551 : size_type n = last - first;
225 8745551 : clear();
226 8745551 : if (capacity() < n) {
227 382450 : change_capacity(n);
228 : }
229 8745551 : _size += n;
230 11308433 : fill(item_ptr(0), first, last);
231 8745551 : }
232 :
233 114634834 : prevector() {}
234 :
235 : explicit prevector(size_type n) {
236 : resize(n);
237 : }
238 :
239 4158576 : explicit prevector(size_type n, const T& val = T()) {
240 4158576 : change_capacity(n);
241 4158576 : _size += n;
242 8317152 : fill(item_ptr(0), n, val);
243 4158576 : }
244 :
245 : template<typename InputIterator>
246 9084185 : prevector(InputIterator first, InputIterator last) {
247 9084185 : size_type n = last - first;
248 9084185 : change_capacity(n);
249 9084185 : _size += n;
250 9084300 : fill(item_ptr(0), first, last);
251 9084185 : }
252 :
253 64482035 : prevector(const prevector<N, T, Size, Diff>& other) {
254 64482035 : size_type n = other.size();
255 64482035 : change_capacity(n);
256 64482035 : _size += n;
257 64482035 : fill(item_ptr(0), other.begin(), other.end());
258 64482035 : }
259 :
260 3013842 : prevector(prevector<N, T, Size, Diff>&& other) {
261 3013842 : swap(other);
262 : }
263 :
264 8129242 : prevector& operator=(const prevector<N, T, Size, Diff>& other) {
265 8129242 : if (&other == this) {
266 : return *this;
267 : }
268 16232268 : assign(other.begin(), other.end());
269 8116115 : return *this;
270 : }
271 :
272 26083473 : prevector& operator=(prevector<N, T, Size, Diff>&& other) {
273 26083473 : swap(other);
274 : return *this;
275 : }
276 :
277 1671202494 : size_type size() const {
278 685112254 : return is_direct() ? _size : _size - N - 1;
279 : }
280 :
281 164266529 : bool empty() const {
282 164266529 : return size() == 0;
283 : }
284 :
285 82524142 : iterator begin() { return iterator(item_ptr(0)); }
286 200651477 : const_iterator begin() const { return const_iterator(item_ptr(0)); }
287 244077544 : iterator end() { return iterator(item_ptr(size())); }
288 747908024 : 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 106595398 : size_t capacity() const {
296 16422151 : if (is_direct()) {
297 : return N;
298 : } else {
299 8479073 : return _union.capacity;
300 : }
301 : }
302 :
303 43453505 : T& operator[](size_type pos) {
304 68970966 : return *item_ptr(pos);
305 : }
306 :
307 140510686 : const T& operator[](size_type pos) const {
308 215999716 : return *item_ptr(pos);
309 : }
310 :
311 95377565 : void resize(size_type new_size) {
312 95377565 : size_type cur_size = size();
313 95377565 : if (cur_size == new_size) {
314 : return;
315 : }
316 8691317 : if (cur_size > new_size) {
317 3071046 : erase(item_ptr(new_size), end());
318 1535524 : return;
319 : }
320 7159185 : if (new_size > capacity()) {
321 762 : change_capacity(new_size);
322 : }
323 7155793 : ptrdiff_t increase = new_size - cur_size;
324 14316666 : fill(item_ptr(cur_size), increase);
325 7155793 : _size += increase;
326 : }
327 :
328 15166 : void reserve(size_type new_capacity) {
329 17157 : if (new_capacity > capacity()) {
330 321 : change_capacity(new_capacity);
331 : }
332 : }
333 :
334 74508013 : void shrink_to_fit() {
335 74508013 : change_capacity(size());
336 : }
337 :
338 88210231 : void clear() {
339 88210231 : resize(0);
340 : }
341 :
342 18168292 : iterator insert(iterator pos, const T& value) {
343 18168292 : size_type p = pos - begin();
344 18168292 : size_type new_size = size() + 1;
345 18168292 : if (capacity() < new_size) {
346 1160 : change_capacity(new_size + (new_size >> 1));
347 : }
348 36336674 : T* ptr = item_ptr(p);
349 18168292 : memmove(ptr + 1, ptr, (size() - p) * sizeof(T));
350 18168292 : _size++;
351 18168292 : new(static_cast<void*>(ptr)) T(value);
352 18168292 : return iterator(ptr);
353 : }
354 :
355 8512 : void insert(iterator pos, size_type count, const T& value) {
356 8512 : size_type p = pos - begin();
357 8512 : size_type new_size = size() + count;
358 8512 : if (capacity() < new_size) {
359 384 : change_capacity(new_size + (new_size >> 1));
360 : }
361 17024 : T* ptr = item_ptr(p);
362 8512 : memmove(ptr + count, ptr, (size() - p) * sizeof(T));
363 8512 : _size += count;
364 17024 : fill(item_ptr(p), count, value);
365 8512 : }
366 :
367 : template<typename InputIterator>
368 67873250 : void insert(iterator pos, InputIterator first, InputIterator last) {
369 67873250 : size_type p = pos - begin();
370 67873250 : difference_type count = last - first;
371 67873250 : size_type new_size = size() + count;
372 67873250 : if (capacity() < new_size) {
373 12354596 : change_capacity(new_size + (new_size >> 1));
374 : }
375 203619948 : memmove(item_ptr(p + count), item_ptr(p), (size() - p) * sizeof(T));
376 67873250 : _size += count;
377 1286239351 : while (first != last) {
378 2436728394 : new(static_cast<void*>(item_ptr(p))) T(*first);
379 1218359202 : ++p;
380 1286236763 : ++first;
381 : }
382 67873250 : }
383 :
384 4588565 : 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 4588565 : if (capacity() < new_size) {
388 1508670 : change_capacity(new_size);
389 1508670 : _size += new_size - size();
390 1508670 : return;
391 : }
392 3079898 : if (new_size < size()) {
393 9344 : erase(item_ptr(new_size), end());
394 : } else {
395 3075226 : _size += new_size - size();
396 : }
397 : }
398 :
399 15680 : iterator erase(iterator pos) {
400 15680 : return erase(pos, pos + 1);
401 : }
402 :
403 1569252 : 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 1569252 : iterator p = first;
411 1569252 : 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 1569252 : _size -= last - p;
420 : }
421 1569252 : memmove(&(*first), &(*last), endp - ((char*)(&(*last))));
422 1569252 : return first;
423 : }
424 :
425 : template<typename... Args>
426 14076 : void emplace_back(Args&&... args) {
427 14076 : size_type new_size = size() + 1;
428 14076 : if (capacity() < new_size) {
429 35 : change_capacity(new_size + (new_size >> 1));
430 : }
431 19975 : new(item_ptr(size())) T(std::forward<Args>(args)...);
432 14076 : _size++;
433 14076 : }
434 :
435 14076 : void push_back(const T& value) {
436 14076 : emplace_back(value);
437 : }
438 :
439 3456 : void pop_back() {
440 3456 : erase(end() - 1, end());
441 3456 : }
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 57678 : const T& back() const {
456 115356 : return *item_ptr(size() - 1);
457 : }
458 :
459 26704144 : void swap(prevector<N, T, Size, Diff>& other) {
460 26703847 : std::swap(_union, other._union);
461 21707456 : std::swap(_size, other._size);
462 : }
463 :
464 202499698 : ~prevector() {
465 : if (!std::is_trivially_destructible<T>::value) {
466 : clear();
467 : }
468 202181286 : if (!is_direct()) {
469 26179988 : free(_union.indirect);
470 : _union.indirect = nullptr;
471 : }
472 128 : }
473 :
474 1287943 : bool operator==(const prevector<N, T, Size, Diff>& other) const {
475 1656544 : if (other.size() != size()) {
476 : return false;
477 : }
478 1282890 : const_iterator b1 = begin();
479 1282890 : const_iterator b2 = other.begin();
480 1282890 : const_iterator e1 = end();
481 21713096 : while (b1 != e1) {
482 20434808 : if ((*b1) != (*b2)) {
483 : return false;
484 : }
485 20430218 : ++b1;
486 21713096 : ++b2;
487 : }
488 : return true;
489 : }
490 :
491 32769 : bool operator!=(const prevector<N, T, Size, Diff>& other) const {
492 32769 : return !(*this == other);
493 : }
494 :
495 1369085 : bool operator<(const prevector<N, T, Size, Diff>& other) const {
496 1576446 : if (size() < other.size()) {
497 : return true;
498 : }
499 1351573 : if (size() > other.size()) {
500 : return false;
501 : }
502 1311218 : const_iterator b1 = begin();
503 1311218 : const_iterator b2 = other.begin();
504 1311218 : const_iterator e1 = end();
505 4386789 : while (b1 != e1) {
506 3967415 : if ((*b1) < (*b2)) {
507 : return true;
508 : }
509 3289232 : if ((*b2) < (*b1)) {
510 : return false;
511 : }
512 3075575 : ++b1;
513 4386789 : ++b2;
514 : }
515 : return false;
516 : }
517 :
518 23782620 : size_t allocated_memory() const {
519 23782620 : if (is_direct()) {
520 : return 0;
521 : } else {
522 894026 : return ((size_t)(sizeof(T))) * _union.capacity;
523 : }
524 : }
525 :
526 13671 : value_type* data() {
527 13670 : return item_ptr(0);
528 : }
529 :
530 92183281 : const value_type* data() const {
531 92240760 : return item_ptr(0);
532 : }
533 : };
534 : #pragma pack(pop)
535 :
536 : #endif // PIVX_PREVECTOR_H
|
