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 306421499 : iterator(T* ptr_) : ptr(ptr_) {}
57 5273473 : T& operator*() const { return *ptr; }
58 : T* operator->() const { return ptr; }
59 2797700 : T& operator[](size_type pos) { return ptr[pos]; }
60 : const T& operator[](size_type pos) const { return ptr[pos]; }
61 204329290 : 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 131714018 : difference_type friend operator-(iterator a, iterator b) { return (&(*a) - &(*b)); }
66 48902755 : iterator operator+(size_type n) { return iterator(ptr + n); }
67 : iterator& operator+=(size_type n) { ptr += n; return *this; }
68 2797700 : 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 254449626 : 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 652998749 : const_iterator(const T* ptr_) : ptr(ptr_) {}
108 48833721 : const_iterator(iterator x) : ptr(&(*x)) {}
109 2949020305 : const T& operator*() const { return *ptr; }
110 : const T* operator->() const { return ptr; }
111 1954073 : const T& operator[](size_type pos) const { return ptr[pos]; }
112 3190484751 : const_iterator& operator++() { ptr++; return *this; }
113 0 : const_iterator& operator--() { ptr--; return *this; }
114 137551604 : const_iterator operator++(int) { const_iterator copy(*this); ++(*this); return copy; }
115 : const_iterator operator--(int) { const_iterator copy(*this); --(*this); return copy; }
116 137125046 : difference_type friend operator-(const_iterator a, const_iterator b) { return (&(*a) - &(*b)); }
117 24668081 : const_iterator operator+(size_type n) { return const_iterator(ptr + n); }
118 51898818 : 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 7886 : bool operator==(const_iterator x) const { return ptr == x.ptr; }
122 2141321246 : bool operator!=(const_iterator x) const { return ptr != x.ptr; }
123 149396595 : 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 99229720 : 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 717158317 : T* direct_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.direct) + pos; }
160 504323226 : const T* direct_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.direct) + pos; }
161 1041395214 : T* indirect_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.indirect) + pos; }
162 128786297 : const T* indirect_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.indirect) + pos; }
163 4385386074 : bool is_direct() const { return _size <= N; }
164 :
165 161194680 : void change_capacity(size_type new_capacity) {
166 161194680 : if (new_capacity <= N) {
167 135937806 : if (!is_direct()) {
168 18946 : T* indirect = indirect_ptr(0);
169 18946 : T* src = indirect;
170 18946 : T* dst = direct_ptr(0);
171 18946 : memcpy(dst, src, size() * sizeof(T));
172 18946 : free(indirect);
173 18946 : _size -= N + 1;
174 : }
175 : } else {
176 25256927 : 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 12163 : _union.indirect = static_cast<char*>(realloc(_union.indirect, ((size_t)sizeof(T)) * new_capacity));
181 12163 : assert(_union.indirect);
182 12163 : _union.capacity = new_capacity;
183 : } else {
184 25244836 : char* new_indirect = static_cast<char*>(malloc(((size_t)sizeof(T)) * new_capacity));
185 25244836 : assert(new_indirect);
186 25244836 : T* src = direct_ptr(0);
187 25244836 : T* dst = reinterpret_cast<T*>(new_indirect);
188 25244836 : memcpy(dst, src, size() * sizeof(T));
189 25244836 : _union.indirect = new_indirect;
190 25244836 : _union.capacity = new_capacity;
191 25244836 : _size += N + 1;
192 : }
193 : }
194 161194680 : }
195 :
196 1725208711 : T* item_ptr(difference_type pos) { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
197 645198900 : const T* item_ptr(difference_type pos) const { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
198 :
199 10713103 : void fill(T* dst, ptrdiff_t count, const T& value = T{}) {
200 10716303 : std::fill_n(dst, count, value);
201 : }
202 :
203 : template<typename InputIterator>
204 77635475 : void fill(T* dst, InputIterator first, InputIterator last) {
205 2351781636 : while (first != last) {
206 2270983798 : new(static_cast<void*>(dst)) T(*first);
207 2268439589 : ++dst;
208 2348612645 : ++first;
209 : }
210 : }
211 :
212 : public:
213 24028 : void assign(size_type n, const T& val) {
214 24028 : clear();
215 24028 : if (capacity() < n) {
216 13198 : change_capacity(n);
217 : }
218 24028 : _size += n;
219 48056 : fill(item_ptr(0), n, val);
220 24028 : }
221 :
222 : template<typename InputIterator>
223 7526017 : void assign(InputIterator first, InputIterator last) {
224 7526017 : size_type n = last - first;
225 7526017 : clear();
226 7526017 : if (capacity() < n) {
227 384274 : change_capacity(n);
228 : }
229 7526017 : _size += n;
230 10070103 : fill(item_ptr(0), first, last);
231 7526017 : }
232 :
233 111405257 : prevector() {}
234 :
235 : explicit prevector(size_type n) {
236 : resize(n);
237 : }
238 :
239 4088644 : explicit prevector(size_type n, const T& val = T()) {
240 4088644 : change_capacity(n);
241 4088644 : _size += n;
242 8177288 : fill(item_ptr(0), n, val);
243 4088644 : }
244 :
245 : template<typename InputIterator>
246 8614995 : prevector(InputIterator first, InputIterator last) {
247 8614995 : size_type n = last - first;
248 8614995 : change_capacity(n);
249 8614995 : _size += n;
250 8615110 : fill(item_ptr(0), first, last);
251 8614995 : }
252 :
253 62119158 : prevector(const prevector<N, T, Size, Diff>& other) {
254 62119158 : size_type n = other.size();
255 62119158 : change_capacity(n);
256 62119158 : _size += n;
257 62119158 : fill(item_ptr(0), other.begin(), other.end());
258 62119158 : }
259 :
260 2481137 : prevector(prevector<N, T, Size, Diff>&& other) {
261 2481137 : swap(other);
262 : }
263 :
264 6914364 : prevector& operator=(const prevector<N, T, Size, Diff>& other) {
265 6914364 : if (&other == this) {
266 : return *this;
267 : }
268 13802524 : assign(other.begin(), other.end());
269 6901258 : return *this;
270 : }
271 :
272 22296546 : prevector& operator=(prevector<N, T, Size, Diff>&& other) {
273 22296546 : swap(other);
274 : return *this;
275 : }
276 :
277 1557621727 : size_type size() const {
278 638524847 : return is_direct() ? _size : _size - N - 1;
279 : }
280 :
281 149187283 : bool empty() const {
282 149187283 : return size() == 0;
283 : }
284 :
285 77946489 : iterator begin() { return iterator(item_ptr(0)); }
286 185511575 : const_iterator begin() const { return const_iterator(item_ptr(0)); }
287 232020241 : iterator end() { return iterator(item_ptr(size())); }
288 687069375 : 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 100156645 : size_t capacity() const {
296 14641975 : if (is_direct()) {
297 : return N;
298 : } else {
299 8278919 : return _union.capacity;
300 : }
301 : }
302 :
303 39789235 : T& operator[](size_type pos) {
304 62938276 : return *item_ptr(pos);
305 : }
306 :
307 122714497 : const T& operator[](size_type pos) const {
308 188158292 : return *item_ptr(pos);
309 : }
310 :
311 91460211 : void resize(size_type new_size) {
312 91460211 : size_type cur_size = size();
313 91460211 : if (cur_size == new_size) {
314 : return;
315 : }
316 8129664 : if (cur_size > new_size) {
317 3067810 : erase(item_ptr(new_size), end());
318 1533905 : return;
319 : }
320 6598383 : if (new_size > capacity()) {
321 762 : change_capacity(new_size);
322 : }
323 6595759 : ptrdiff_t increase = new_size - cur_size;
324 13196470 : fill(item_ptr(cur_size), increase);
325 6595759 : _size += increase;
326 : }
327 :
328 14690 : void reserve(size_type new_capacity) {
329 16169 : if (new_capacity > capacity()) {
330 449 : change_capacity(new_capacity);
331 : }
332 : }
333 :
334 72875704 : void shrink_to_fit() {
335 72875704 : change_capacity(size());
336 : }
337 :
338 84853275 : void clear() {
339 84853275 : resize(0);
340 : }
341 :
342 17500752 : iterator insert(iterator pos, const T& value) {
343 17500752 : size_type p = pos - begin();
344 17500752 : size_type new_size = size() + 1;
345 17500752 : if (capacity() < new_size) {
346 969 : change_capacity(new_size + (new_size >> 1));
347 : }
348 35001404 : T* ptr = item_ptr(p);
349 17500752 : memmove(ptr + 1, ptr, (size() - p) * sizeof(T));
350 17500752 : _size++;
351 17500752 : new(static_cast<void*>(ptr)) T(value);
352 17500752 : return iterator(ptr);
353 : }
354 :
355 7872 : void insert(iterator pos, size_type count, const T& value) {
356 7872 : size_type p = pos - begin();
357 7872 : size_type new_size = size() + count;
358 7872 : if (capacity() < new_size) {
359 128 : change_capacity(new_size + (new_size >> 1));
360 : }
361 15744 : T* ptr = item_ptr(p);
362 7872 : memmove(ptr + count, ptr, (size() - p) * sizeof(T));
363 7872 : _size += count;
364 15744 : fill(item_ptr(p), count, value);
365 7872 : }
366 :
367 : template<typename InputIterator>
368 64390701 : void insert(iterator pos, InputIterator first, InputIterator last) {
369 64390701 : size_type p = pos - begin();
370 64390701 : difference_type count = last - first;
371 64390701 : size_type new_size = size() + count;
372 64390701 : if (capacity() < new_size) {
373 11786701 : change_capacity(new_size + (new_size >> 1));
374 : }
375 193172300 : memmove(item_ptr(p + count), item_ptr(p), (size() - p) * sizeof(T));
376 64390701 : _size += count;
377 1227001670 : while (first != last) {
378 2325218542 : new(static_cast<void*>(item_ptr(p))) T(*first);
379 1162610771 : ++p;
380 1226999594 : ++first;
381 : }
382 64390701 : }
383 :
384 4082141 : 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 4082141 : if (capacity() < new_size) {
388 1309756 : change_capacity(new_size);
389 1309756 : _size += new_size - size();
390 1309756 : return;
391 : }
392 2772383 : if (new_size < size()) {
393 6400 : erase(item_ptr(new_size), end());
394 : } else {
395 2769183 : _size += new_size - size();
396 : }
397 : }
398 :
399 16704 : iterator erase(iterator pos) {
400 16704 : return erase(pos, pos + 1);
401 : }
402 :
403 1567889 : 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 1567889 : iterator p = first;
411 1567889 : 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 1567889 : _size -= last - p;
420 : }
421 1567889 : memmove(&(*first), &(*last), endp - ((char*)(&(*last))));
422 1567889 : return first;
423 : }
424 :
425 : template<typename... Args>
426 13075 : void emplace_back(Args&&... args) {
427 13075 : size_type new_size = size() + 1;
428 13075 : if (capacity() < new_size) {
429 35 : change_capacity(new_size + (new_size >> 1));
430 : }
431 18334 : new(item_ptr(size())) T(std::forward<Args>(args)...);
432 13075 : _size++;
433 13075 : }
434 :
435 13075 : void push_back(const T& value) {
436 13075 : emplace_back(value);
437 : }
438 :
439 3648 : void pop_back() {
440 3648 : erase(end() - 1, end());
441 3648 : }
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 57681 : const T& back() const {
456 115362 : return *item_ptr(size() - 1);
457 : }
458 :
459 22912633 : void swap(prevector<N, T, Size, Diff>& other) {
460 22912346 : std::swap(_union, other._union);
461 18023982 : std::swap(_size, other._size);
462 : }
463 :
464 194396802 : ~prevector() {
465 : if (!std::is_trivially_destructible<T>::value) {
466 : clear();
467 : }
468 194111825 : if (!is_direct()) {
469 25225368 : free(_union.indirect);
470 : _union.indirect = nullptr;
471 : }
472 128 : }
473 :
474 1098504 : bool operator==(const prevector<N, T, Size, Diff>& other) const {
475 1423481 : if (other.size() != size()) {
476 : return false;
477 : }
478 1093529 : const_iterator b1 = begin();
479 1093529 : const_iterator b2 = other.begin();
480 1093529 : const_iterator e1 = end();
481 16545590 : while (b1 != e1) {
482 15456546 : if ((*b1) != (*b2)) {
483 : return false;
484 : }
485 15452057 : ++b1;
486 16545590 : ++b2;
487 : }
488 : return true;
489 : }
490 :
491 31147 : bool operator!=(const prevector<N, T, Size, Diff>& other) const {
492 31147 : return !(*this == other);
493 : }
494 :
495 1335194 : bool operator<(const prevector<N, T, Size, Diff>& other) const {
496 1542017 : if (size() < other.size()) {
497 : return true;
498 : }
499 1318212 : if (size() > other.size()) {
500 : return false;
501 : }
502 1277446 : const_iterator b1 = begin();
503 1277446 : const_iterator b2 = other.begin();
504 1277446 : const_iterator e1 = end();
505 4211289 : while (b1 != e1) {
506 3828805 : if ((*b1) < (*b2)) {
507 : return true;
508 : }
509 3149376 : if ((*b2) < (*b1)) {
510 : return false;
511 : }
512 2933840 : ++b1;
513 4211289 : ++b2;
514 : }
515 : return false;
516 : }
517 :
518 18424290 : size_t allocated_memory() const {
519 18424290 : if (is_direct()) {
520 : return 0;
521 : } else {
522 688260 : return ((size_t)(sizeof(T))) * _union.capacity;
523 : }
524 : }
525 :
526 13597 : value_type* data() {
527 13596 : return item_ptr(0);
528 : }
529 :
530 85691077 : const value_type* data() const {
531 85748557 : return item_ptr(0);
532 : }
533 : };
534 : #pragma pack(pop)
535 :
536 : #endif // PIVX_PREVECTOR_H
|
