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 218518320 : iterator(T* ptr_) : ptr(ptr_) {}
57 5183212 : T& operator*() const { return *ptr; }
58 : T* operator->() const { return ptr; }
59 2794300 : T& operator[](size_type pos) { return ptr[pos]; }
60 : const T& operator[](size_type pos) const { return ptr[pos]; }
61 143718816 : 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 92690659 : difference_type friend operator-(iterator a, iterator b) { return (&(*a) - &(*b)); }
66 34357133 : iterator operator+(size_type n) { return iterator(ptr + n); }
67 : iterator& operator+=(size_type n) { ptr += n; return *this; }
68 2794300 : 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 179295804 : 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 548234979 : const_iterator(const T* ptr_) : ptr(ptr_) {}
108 34286504 : const_iterator(iterator x) : ptr(&(*x)) {}
109 2539633986 : const T& operator*() const { return *ptr; }
110 : const T* operator->() const { return ptr; }
111 1928183 : const T& operator[](size_type pos) const { return ptr[pos]; }
112 2792588311 : const_iterator& operator++() { ptr++; return *this; }
113 0 : const_iterator& operator--() { ptr--; return *this; }
114 108580062 : const_iterator operator++(int) { const_iterator copy(*this); ++(*this); return copy; }
115 : const_iterator operator--(int) { const_iterator copy(*this); --(*this); return copy; }
116 104148770 : difference_type friend operator-(const_iterator a, const_iterator b) { return (&(*a) - &(*b)); }
117 17342597 : const_iterator operator+(size_type n) { return const_iterator(ptr + n); }
118 39858648 : 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 8591 : bool operator==(const_iterator x) const { return ptr == x.ptr; }
122 2126323259 : bool operator!=(const_iterator x) const { return ptr != x.ptr; }
123 117947381 : 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 77882383 : 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 519869086 : T* direct_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.direct) + pos; }
160 446111746 : const T* direct_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.direct) + pos; }
161 719469933 : T* indirect_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.indirect) + pos; }
162 112973217 : const T* indirect_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.indirect) + pos; }
163 3471345722 : bool is_direct() const { return _size <= N; }
164 :
165 143843667 : void change_capacity(size_type new_capacity) {
166 143843667 : if (new_capacity <= N) {
167 122134130 : if (!is_direct()) {
168 18605 : T* indirect = indirect_ptr(0);
169 18605 : T* src = indirect;
170 18605 : T* dst = direct_ptr(0);
171 18605 : memcpy(dst, src, size() * sizeof(T));
172 18605 : free(indirect);
173 18605 : _size -= N + 1;
174 : }
175 : } else {
176 21709590 : 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 14077 : _union.indirect = static_cast<char*>(realloc(_union.indirect, ((size_t)sizeof(T)) * new_capacity));
181 14077 : assert(_union.indirect);
182 14077 : _union.capacity = new_capacity;
183 : } else {
184 21695515 : char* new_indirect = static_cast<char*>(malloc(((size_t)sizeof(T)) * new_capacity));
185 21695515 : assert(new_indirect);
186 21695515 : T* src = direct_ptr(0);
187 21695515 : T* dst = reinterpret_cast<T*>(new_indirect);
188 21695515 : memcpy(dst, src, size() * sizeof(T));
189 21695515 : _union.indirect = new_indirect;
190 21695515 : _union.capacity = new_capacity;
191 21695515 : _size += N + 1;
192 : }
193 : }
194 143843667 : }
195 :
196 1211969272 : T* item_ptr(difference_type pos) { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
197 571811564 : const T* item_ptr(difference_type pos) const { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
198 :
199 7764758 : void fill(T* dst, ptrdiff_t count, const T& value = T{}) {
200 7768342 : std::fill_n(dst, count, value);
201 : }
202 :
203 : template<typename InputIterator>
204 74344528 : void fill(T* dst, InputIterator first, InputIterator last) {
205 2269846124 : while (first != last) {
206 2192519328 : new(static_cast<void*>(dst)) T(*first);
207 2190127179 : ++dst;
208 2266867233 : ++first;
209 : }
210 : }
211 :
212 : public:
213 24039 : void assign(size_type n, const T& val) {
214 24039 : clear();
215 24039 : if (capacity() < n) {
216 13129 : change_capacity(n);
217 : }
218 24039 : _size += n;
219 48078 : fill(item_ptr(0), n, val);
220 24039 : }
221 :
222 : template<typename InputIterator>
223 7666864 : void assign(InputIterator first, InputIterator last) {
224 7666864 : size_type n = last - first;
225 7666864 : clear();
226 7666864 : if (capacity() < n) {
227 336860 : change_capacity(n);
228 : }
229 7666864 : _size += n;
230 10058894 : fill(item_ptr(0), first, last);
231 7666864 : }
232 :
233 91511994 : prevector() {}
234 :
235 : explicit prevector(size_type n) {
236 : resize(n);
237 : }
238 :
239 3830646 : explicit prevector(size_type n, const T& val = T()) {
240 3830646 : change_capacity(n);
241 3830646 : _size += n;
242 7661302 : fill(item_ptr(0), n, val);
243 3830646 : }
244 :
245 : template<typename InputIterator>
246 6195500 : prevector(InputIterator first, InputIterator last) {
247 6195500 : size_type n = last - first;
248 6195500 : change_capacity(n);
249 6195500 : _size += n;
250 6195615 : fill(item_ptr(0), first, last);
251 6195500 : }
252 :
253 61068993 : prevector(const prevector<N, T, Size, Diff>& other) {
254 61068993 : size_type n = other.size();
255 61068993 : change_capacity(n);
256 61068993 : _size += n;
257 61068993 : fill(item_ptr(0), other.begin(), other.end());
258 61068993 : }
259 :
260 2553800 : prevector(prevector<N, T, Size, Diff>&& other) {
261 2553800 : swap(other);
262 : }
263 :
264 7092924 : prevector& operator=(const prevector<N, T, Size, Diff>& other) {
265 7092924 : if (&other == this) {
266 : return *this;
267 : }
268 14160166 : assign(other.begin(), other.end());
269 7080078 : return *this;
270 : }
271 :
272 20798418 : prevector& operator=(prevector<N, T, Size, Diff>&& other) {
273 20798418 : swap(other);
274 : return *this;
275 : }
276 :
277 1315880013 : size_type size() const {
278 555815367 : return is_direct() ? _size : _size - N - 1;
279 : }
280 :
281 145715752 : bool empty() const {
282 145715752 : return size() == 0;
283 : }
284 :
285 56141572 : iterator begin() { return iterator(item_ptr(0)); }
286 163515230 : const_iterator begin() const { return const_iterator(item_ptr(0)); }
287 166029134 : iterator end() { return iterator(item_ptr(size())); }
288 582805363 : 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 73453478 : size_t capacity() const {
296 12092052 : if (is_direct()) {
297 : return N;
298 : } else {
299 5777880 : return _union.capacity;
300 : }
301 : }
302 :
303 26567155 : T& operator[](size_type pos) {
304 44559226 : return *item_ptr(pos);
305 : }
306 :
307 106596753 : const T& operator[](size_type pos) const {
308 167988680 : return *item_ptr(pos);
309 : }
310 :
311 79124075 : void resize(size_type new_size) {
312 79124075 : size_type cur_size = size();
313 79124075 : if (cur_size == new_size) {
314 : return;
315 : }
316 5349919 : if (cur_size > new_size) {
317 2889936 : erase(item_ptr(new_size), end());
318 1444966 : return;
319 : }
320 3908217 : if (new_size > capacity()) {
321 762 : change_capacity(new_size);
322 : }
323 3904953 : ptrdiff_t increase = new_size - cur_size;
324 7815228 : fill(item_ptr(cur_size), increase);
325 3904953 : _size += increase;
326 : }
327 :
328 15182 : void reserve(size_type new_capacity) {
329 17109 : if (new_capacity > capacity()) {
330 257 : change_capacity(new_capacity);
331 : }
332 : }
333 :
334 62872345 : void shrink_to_fit() {
335 62872345 : change_capacity(size());
336 : }
337 :
338 75208294 : void clear() {
339 75208294 : resize(0);
340 : }
341 :
342 12581495 : iterator insert(iterator pos, const T& value) {
343 12581495 : size_type p = pos - begin();
344 12581495 : size_type new_size = size() + 1;
345 12581495 : if (capacity() < new_size) {
346 1160 : change_capacity(new_size + (new_size >> 1));
347 : }
348 25162990 : T* ptr = item_ptr(p);
349 12581495 : memmove(ptr + 1, ptr, (size() - p) * sizeof(T));
350 12581495 : _size++;
351 12581495 : new(static_cast<void*>(ptr)) T(value);
352 12581495 : return iterator(ptr);
353 : }
354 :
355 8704 : void insert(iterator pos, size_type count, const T& value) {
356 8704 : size_type p = pos - begin();
357 8704 : size_type new_size = size() + count;
358 8704 : if (capacity() < new_size) {
359 448 : change_capacity(new_size + (new_size >> 1));
360 : }
361 17408 : T* ptr = item_ptr(p);
362 8704 : memmove(ptr + count, ptr, (size() - p) * sizeof(T));
363 8704 : _size += count;
364 17408 : fill(item_ptr(p), count, value);
365 8704 : }
366 :
367 : template<typename InputIterator>
368 44916618 : void insert(iterator pos, InputIterator first, InputIterator last) {
369 44916618 : size_type p = pos - begin();
370 44916618 : difference_type count = last - first;
371 44916618 : size_type new_size = size() + count;
372 44916618 : if (capacity() < new_size) {
373 8110352 : change_capacity(new_size + (new_size >> 1));
374 : }
375 134750156 : memmove(item_ptr(p + count), item_ptr(p), (size() - p) * sizeof(T));
376 44916618 : _size += count;
377 840906318 : while (first != last) {
378 1591976788 : new(static_cast<void*>(item_ptr(p))) T(*first);
379 795989899 : ++p;
380 840903986 : ++first;
381 : }
382 44916618 : }
383 :
384 4319745 : 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 4319745 : if (capacity() < new_size) {
388 1413076 : change_capacity(new_size);
389 1413076 : _size += new_size - size();
390 1413076 : return;
391 : }
392 2906667 : if (new_size < size()) {
393 6912 : erase(item_ptr(new_size), end());
394 : } else {
395 2903211 : _size += new_size - size();
396 : }
397 : }
398 :
399 15040 : iterator erase(iterator pos) {
400 15040 : return erase(pos, pos + 1);
401 : }
402 :
403 1478246 : 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 1478246 : iterator p = first;
411 1478246 : 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 1478246 : _size -= last - p;
420 : }
421 1478246 : memmove(&(*first), &(*last), endp - ((char*)(&(*last))));
422 1478246 : return first;
423 : }
424 :
425 : template<typename... Args>
426 13760 : void emplace_back(Args&&... args) {
427 13760 : size_type new_size = size() + 1;
428 13760 : if (capacity() < new_size) {
429 227 : change_capacity(new_size + (new_size >> 1));
430 : }
431 19531 : new(item_ptr(size())) T(std::forward<Args>(args)...);
432 13760 : _size++;
433 13760 : }
434 :
435 13760 : void push_back(const T& value) {
436 13760 : emplace_back(value);
437 : }
438 :
439 3968 : void pop_back() {
440 3968 : erase(end() - 1, end());
441 3968 : }
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 57679 : const T& back() const {
456 115358 : return *item_ptr(size() - 1);
457 : }
458 :
459 21378302 : void swap(prevector<N, T, Size, Diff>& other) {
460 21377992 : std::swap(_union, other._union);
461 17817374 : std::swap(_size, other._size);
462 : }
463 :
464 171165309 : ~prevector() {
465 : if (!std::is_trivially_destructible<T>::value) {
466 : clear();
467 : }
468 170864844 : if (!is_direct()) {
469 21676445 : free(_union.indirect);
470 : _union.indirect = nullptr;
471 : }
472 128 : }
473 :
474 1270111 : bool operator==(const prevector<N, T, Size, Diff>& other) const {
475 1617864 : if (other.size() != size()) {
476 : return false;
477 : }
478 1265068 : const_iterator b1 = begin();
479 1265068 : const_iterator b2 = other.begin();
480 1265068 : const_iterator e1 = end();
481 20097711 : while (b1 != e1) {
482 18836624 : if ((*b1) != (*b2)) {
483 : return false;
484 : }
485 18832649 : ++b1;
486 20097711 : ++b2;
487 : }
488 : return true;
489 : }
490 :
491 36418 : bool operator!=(const prevector<N, T, Size, Diff>& other) const {
492 36418 : return !(*this == other);
493 : }
494 :
495 1331822 : bool operator<(const prevector<N, T, Size, Diff>& other) const {
496 1538103 : if (size() < other.size()) {
497 : return true;
498 : }
499 1315408 : if (size() > other.size()) {
500 : return false;
501 : }
502 1275117 : const_iterator b1 = begin();
503 1275117 : const_iterator b2 = other.begin();
504 1275117 : const_iterator e1 = end();
505 4201933 : while (b1 != e1) {
506 3821799 : if ((*b1) < (*b2)) {
507 : return true;
508 : }
509 3146400 : if ((*b2) < (*b1)) {
510 : return false;
511 : }
512 2926818 : ++b1;
513 4201933 : ++b2;
514 : }
515 : return false;
516 : }
517 :
518 20095430 : size_t allocated_memory() const {
519 20095430 : if (is_direct()) {
520 : return 0;
521 : } else {
522 743440 : return ((size_t)(sizeof(T))) * _union.capacity;
523 : }
524 : }
525 :
526 13592 : value_type* data() {
527 13591 : return item_ptr(0);
528 : }
529 :
530 84170175 : const value_type* data() const {
531 84227654 : return item_ptr(0);
532 : }
533 : };
534 : #pragma pack(pop)
535 :
536 : #endif // PIVX_PREVECTOR_H
|
