Bitcoin Core 29.99.0
P2P Digital Currency
prevector.h
Go to the documentation of this file.
1// Copyright (c) 2015-present 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 <algorithm>
9#include <cassert>
10#include <cstddef>
11#include <cstdint>
12#include <cstdlib>
13#include <cstring>
14#include <iterator>
15#include <type_traits>
16#include <utility>
17
36template<unsigned int N, typename T, typename Size = uint32_t, typename Diff = int32_t>
37class prevector {
38 static_assert(std::is_trivially_copyable_v<T>);
39
40public:
41 static constexpr unsigned int STATIC_SIZE{N};
42
43 typedef Size size_type;
44 typedef Diff difference_type;
45 typedef T value_type;
49 typedef const value_type* const_pointer;
50
51 class iterator {
52 T* ptr{};
53 public:
54 typedef Diff difference_type;
55 typedef T* pointer;
56 typedef T& reference;
57 using element_type = T;
58 using iterator_category = std::contiguous_iterator_tag;
59 iterator() = default;
60 iterator(T* ptr_) : ptr(ptr_) {}
61 T& operator*() const { return *ptr; }
62 T* operator->() const { return ptr; }
63 T& operator[](size_type pos) const { return ptr[pos]; }
64 iterator& operator++() { ptr++; return *this; }
65 iterator& operator--() { ptr--; return *this; }
66 iterator operator++(int) { iterator copy(*this); ++(*this); return copy; }
67 iterator operator--(int) { iterator copy(*this); --(*this); return copy; }
68 difference_type friend operator-(iterator a, iterator b) { return (&(*a) - &(*b)); }
69 iterator operator+(size_type n) const { return iterator(ptr + n); }
70 iterator friend operator+(size_type n, iterator x) { return x + n; }
71 iterator& operator+=(size_type n) { ptr += n; return *this; }
72 iterator operator-(size_type n) const { return iterator(ptr - n); }
73 iterator& operator-=(size_type n) { ptr -= n; return *this; }
74 bool operator==(iterator x) const { return ptr == x.ptr; }
75 bool operator!=(iterator x) const { return ptr != x.ptr; }
76 bool operator>=(iterator x) const { return ptr >= x.ptr; }
77 bool operator<=(iterator x) const { return ptr <= x.ptr; }
78 bool operator>(iterator x) const { return ptr > x.ptr; }
79 bool operator<(iterator x) const { return ptr < x.ptr; }
80 };
81
83 const T* ptr{};
84 public:
85 typedef Diff difference_type;
86 typedef const T* pointer;
87 typedef const T& reference;
88 using element_type = const T;
89 using iterator_category = std::contiguous_iterator_tag;
90 const_iterator() = default;
91 const_iterator(const T* ptr_) : ptr(ptr_) {}
93 const T& operator*() const { return *ptr; }
94 const T* operator->() const { return ptr; }
95 const T& operator[](size_type pos) const { return ptr[pos]; }
96 const_iterator& operator++() { ptr++; return *this; }
97 const_iterator& operator--() { ptr--; return *this; }
98 const_iterator operator++(int) { const_iterator copy(*this); ++(*this); return copy; }
99 const_iterator operator--(int) { const_iterator copy(*this); --(*this); return copy; }
100 difference_type friend operator-(const_iterator a, const_iterator b) { return (&(*a) - &(*b)); }
102 const_iterator friend operator+(size_type n, const_iterator x) { return x + n; }
103 const_iterator& operator+=(size_type n) { ptr += n; return *this; }
105 const_iterator& operator-=(size_type n) { ptr -= n; return *this; }
106 bool operator==(const_iterator x) const { return ptr == x.ptr; }
107 bool operator!=(const_iterator x) const { return ptr != x.ptr; }
108 bool operator>=(const_iterator x) const { return ptr >= x.ptr; }
109 bool operator<=(const_iterator x) const { return ptr <= x.ptr; }
110 bool operator>(const_iterator x) const { return ptr > x.ptr; }
111 bool operator<(const_iterator x) const { return ptr < x.ptr; }
112 };
113
114private:
115#pragma pack(push, 1)
117 char direct[sizeof(T) * N];
118 struct {
119 char* indirect;
122 };
123#pragma pack(pop)
124 alignas(char*) direct_or_indirect _union = {};
126
127 static_assert(alignof(char*) % alignof(size_type) == 0 && sizeof(char*) % alignof(size_type) == 0, "size_type cannot have more restrictive alignment requirement than pointer");
128 static_assert(alignof(char*) % alignof(T) == 0, "value_type T cannot have more restrictive alignment requirement than pointer");
129
130 T* direct_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.direct) + pos; }
131 const T* direct_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.direct) + pos; }
132 T* indirect_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.indirect_contents.indirect) + pos; }
133 const T* indirect_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.indirect_contents.indirect) + pos; }
134 bool is_direct() const { return _size <= N; }
135
136 void change_capacity(size_type new_capacity) {
137 if (new_capacity <= N) {
138 if (!is_direct()) {
139 T* indirect = indirect_ptr(0);
140 T* src = indirect;
141 T* dst = direct_ptr(0);
142 memcpy(dst, src, size() * sizeof(T));
143 free(indirect);
144 _size -= N + 1;
145 }
146 } else {
147 if (!is_direct()) {
148 /* FIXME: Because malloc/realloc here won't call new_handler if allocation fails, assert
149 success. These should instead use an allocator or new/delete so that handlers
150 are called as necessary, but performance would be slightly degraded by doing so. */
151 _union.indirect_contents.indirect = static_cast<char*>(realloc(_union.indirect_contents.indirect, ((size_t)sizeof(T)) * new_capacity));
153 _union.indirect_contents.capacity = new_capacity;
154 } else {
155 char* new_indirect = static_cast<char*>(malloc(((size_t)sizeof(T)) * new_capacity));
156 assert(new_indirect);
157 T* src = direct_ptr(0);
158 T* dst = reinterpret_cast<T*>(new_indirect);
159 memcpy(dst, src, size() * sizeof(T));
160 _union.indirect_contents.indirect = new_indirect;
161 _union.indirect_contents.capacity = new_capacity;
162 _size += N + 1;
163 }
164 }
165 }
166
167 T* item_ptr(difference_type pos) { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
168 const T* item_ptr(difference_type pos) const { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
169
170 void fill(T* dst, ptrdiff_t count, const T& value = T{}) {
171 std::fill_n(dst, count, value);
172 }
173
174 template <std::input_iterator InputIterator>
175 void fill(T* dst, InputIterator first, InputIterator last) {
176 while (first != last) {
177 new(static_cast<void*>(dst)) T(*first);
178 ++dst;
179 ++first;
180 }
181 }
182
183public:
184 void assign(size_type n, const T& val) {
185 clear();
186 if (capacity() < n) {
188 }
189 _size += n;
190 fill(item_ptr(0), n, val);
191 }
192
193 template <std::input_iterator InputIterator>
194 void assign(InputIterator first, InputIterator last) {
195 size_type n = last - first;
196 clear();
197 if (capacity() < n) {
199 }
200 _size += n;
201 fill(item_ptr(0), first, last);
202 }
203
204 prevector() = default;
205
206 explicit prevector(size_type n) {
207 resize(n);
208 }
209
210 explicit prevector(size_type n, const T& val) {
212 _size += n;
213 fill(item_ptr(0), n, val);
214 }
215
216 template <std::input_iterator InputIterator>
217 prevector(InputIterator first, InputIterator last) {
218 size_type n = last - first;
220 _size += n;
221 fill(item_ptr(0), first, last);
222 }
223
225 size_type n = other.size();
227 _size += n;
228 fill(item_ptr(0), other.begin(), other.end());
229 }
230
232 : _union(std::move(other._union)), _size(other._size)
233 {
234 other._size = 0;
235 }
236
238 if (&other == this) {
239 return *this;
240 }
241 assign(other.begin(), other.end());
242 return *this;
243 }
244
246 if (!is_direct()) {
248 }
249 _union = std::move(other._union);
250 _size = other._size;
251 other._size = 0;
252 return *this;
253 }
254
255 size_type size() const {
256 return is_direct() ? _size : _size - N - 1;
257 }
258
259 bool empty() const {
260 return size() == 0;
261 }
262
263 iterator begin() { return iterator(item_ptr(0)); }
267
268 size_t capacity() const {
269 if (is_direct()) {
270 return N;
271 } else {
273 }
274 }
275
277 return *item_ptr(pos);
278 }
279
280 const T& operator[](size_type pos) const {
281 return *item_ptr(pos);
282 }
283
284 void resize(size_type new_size) {
285 size_type cur_size = size();
286 if (cur_size == new_size) {
287 return;
288 }
289 if (cur_size > new_size) {
290 erase(item_ptr(new_size), end());
291 return;
292 }
293 if (new_size > capacity()) {
294 change_capacity(new_size);
295 }
296 ptrdiff_t increase = new_size - cur_size;
297 fill(item_ptr(cur_size), increase);
298 _size += increase;
299 }
300
301 void reserve(size_type new_capacity) {
302 if (new_capacity > capacity()) {
303 change_capacity(new_capacity);
304 }
305 }
306
309 }
310
311 void clear() {
312 resize(0);
313 }
314
315 iterator insert(iterator pos, const T& value) {
316 size_type p = pos - begin();
317 size_type new_size = size() + 1;
318 if (capacity() < new_size) {
319 change_capacity(new_size + (new_size >> 1));
320 }
321 T* ptr = item_ptr(p);
322 T* dst = ptr + 1;
323 memmove(dst, ptr, (size() - p) * sizeof(T));
324 _size++;
325 new(static_cast<void*>(ptr)) T(value);
326 return iterator(ptr);
327 }
328
329 void insert(iterator pos, size_type count, const T& value) {
330 size_type p = pos - begin();
331 size_type new_size = size() + count;
332 if (capacity() < new_size) {
333 change_capacity(new_size + (new_size >> 1));
334 }
335 T* ptr = item_ptr(p);
336 T* dst = ptr + count;
337 memmove(dst, ptr, (size() - p) * sizeof(T));
338 _size += count;
339 fill(item_ptr(p), count, value);
340 }
341
342 template <std::input_iterator InputIterator>
343 void insert(iterator pos, InputIterator first, InputIterator last) {
344 size_type p = pos - begin();
345 difference_type count = last - first;
346 size_type new_size = size() + count;
347 if (capacity() < new_size) {
348 change_capacity(new_size + (new_size >> 1));
349 }
350 T* ptr = item_ptr(p);
351 T* dst = ptr + count;
352 memmove(dst, ptr, (size() - p) * sizeof(T));
353 _size += count;
354 fill(ptr, first, last);
355 }
356
357 inline void resize_uninitialized(size_type new_size) {
358 // resize_uninitialized changes the size of the prevector but does not initialize it.
359 // If size < new_size, the added elements must be initialized explicitly.
360 if (capacity() < new_size) {
361 change_capacity(new_size);
362 _size += new_size - size();
363 return;
364 }
365 if (new_size < size()) {
366 erase(item_ptr(new_size), end());
367 } else {
368 _size += new_size - size();
369 }
370 }
371
373 return erase(pos, pos + 1);
374 }
375
377 // Erase is not allowed to the change the object's capacity. That means
378 // that when starting with an indirectly allocated prevector with
379 // size and capacity > N, the result may be a still indirectly allocated
380 // prevector with size <= N and capacity > N. A shrink_to_fit() call is
381 // necessary to switch to the (more efficient) directly allocated
382 // representation (with capacity N and size <= N).
383 iterator p = first;
384 char* endp = (char*)&(*end());
385 _size -= last - p;
386 memmove(&(*first), &(*last), endp - ((char*)(&(*last))));
387 return first;
388 }
389
390 template<typename... Args>
391 void emplace_back(Args&&... args) {
392 size_type new_size = size() + 1;
393 if (capacity() < new_size) {
394 change_capacity(new_size + (new_size >> 1));
395 }
396 new(item_ptr(size())) T(std::forward<Args>(args)...);
397 _size++;
398 }
399
400 void push_back(const T& value) {
401 emplace_back(value);
402 }
403
404 void pop_back() {
405 erase(end() - 1, end());
406 }
407
408 T& front() {
409 return *item_ptr(0);
410 }
411
412 const T& front() const {
413 return *item_ptr(0);
414 }
415
416 T& back() {
417 return *item_ptr(size() - 1);
418 }
419
420 const T& back() const {
421 return *item_ptr(size() - 1);
422 }
423
424 void swap(prevector<N, T, Size, Diff>& other) noexcept
425 {
426 std::swap(_union, other._union);
427 std::swap(_size, other._size);
428 }
429
431 if (!is_direct()) {
434 }
435 }
436
437 bool operator==(const prevector<N, T, Size, Diff>& other) const {
438 if (other.size() != size()) {
439 return false;
440 }
441 const_iterator b1 = begin();
442 const_iterator b2 = other.begin();
443 const_iterator e1 = end();
444 while (b1 != e1) {
445 if ((*b1) != (*b2)) {
446 return false;
447 }
448 ++b1;
449 ++b2;
450 }
451 return true;
452 }
453
454 bool operator!=(const prevector<N, T, Size, Diff>& other) const {
455 return !(*this == other);
456 }
457
458 bool operator<(const prevector<N, T, Size, Diff>& other) const {
459 if (size() < other.size()) {
460 return true;
461 }
462 if (size() > other.size()) {
463 return false;
464 }
465 const_iterator b1 = begin();
466 const_iterator b2 = other.begin();
467 const_iterator e1 = end();
468 while (b1 != e1) {
469 if ((*b1) < (*b2)) {
470 return true;
471 }
472 if ((*b2) < (*b1)) {
473 return false;
474 }
475 ++b1;
476 ++b2;
477 }
478 return false;
479 }
480
481 size_t allocated_memory() const {
482 if (is_direct()) {
483 return 0;
484 } else {
485 return ((size_t)(sizeof(T))) * _union.indirect_contents.capacity;
486 }
487 }
488
490 return item_ptr(0);
491 }
492
493 const value_type* data() const {
494 return item_ptr(0);
495 }
496};
497
498#endif // BITCOIN_PREVECTOR_H
ArgsManager & args
Definition: bitcoind.cpp:277
bool operator==(const_iterator x) const
Definition: prevector.h:106
const_iterator & operator++()
Definition: prevector.h:96
const_iterator & operator+=(size_type n)
Definition: prevector.h:103
const_iterator friend operator+(size_type n, const_iterator x)
Definition: prevector.h:102
bool operator<(const_iterator x) const
Definition: prevector.h:111
const_iterator & operator-=(size_type n)
Definition: prevector.h:105
const_iterator operator--(int)
Definition: prevector.h:99
bool operator<=(const_iterator x) const
Definition: prevector.h:109
const_iterator operator++(int)
Definition: prevector.h:98
const_iterator(const T *ptr_)
Definition: prevector.h:91
const T * operator->() const
Definition: prevector.h:94
difference_type friend operator-(const_iterator a, const_iterator b)
Definition: prevector.h:100
bool operator!=(const_iterator x) const
Definition: prevector.h:107
const_iterator operator-(size_type n) const
Definition: prevector.h:104
bool operator>=(const_iterator x) const
Definition: prevector.h:108
const_iterator & operator--()
Definition: prevector.h:97
const T & operator*() const
Definition: prevector.h:93
const_iterator operator+(size_type n) const
Definition: prevector.h:101
std::contiguous_iterator_tag iterator_category
Definition: prevector.h:89
const T & operator[](size_type pos) const
Definition: prevector.h:95
bool operator>(const_iterator x) const
Definition: prevector.h:110
const_iterator(iterator x)
Definition: prevector.h:92
std::contiguous_iterator_tag iterator_category
Definition: prevector.h:58
bool operator<(iterator x) const
Definition: prevector.h:79
bool operator==(iterator x) const
Definition: prevector.h:74
difference_type friend operator-(iterator a, iterator b)
Definition: prevector.h:68
iterator operator-(size_type n) const
Definition: prevector.h:72
T & operator[](size_type pos) const
Definition: prevector.h:63
bool operator!=(iterator x) const
Definition: prevector.h:75
iterator & operator++()
Definition: prevector.h:64
iterator operator--(int)
Definition: prevector.h:67
bool operator<=(iterator x) const
Definition: prevector.h:77
bool operator>=(iterator x) const
Definition: prevector.h:76
T & operator*() const
Definition: prevector.h:61
iterator & operator+=(size_type n)
Definition: prevector.h:71
iterator operator+(size_type n) const
Definition: prevector.h:69
T * operator->() const
Definition: prevector.h:62
iterator & operator-=(size_type n)
Definition: prevector.h:73
iterator operator++(int)
Definition: prevector.h:66
bool operator>(iterator x) const
Definition: prevector.h:78
iterator & operator--()
Definition: prevector.h:65
iterator friend operator+(size_type n, iterator x)
Definition: prevector.h:70
iterator(T *ptr_)
Definition: prevector.h:60
Implements a drop-in replacement for std::vector<T> which stores up to N elements directly (without h...
Definition: prevector.h:37
bool empty() const
Definition: prevector.h:259
prevector(size_type n)
Definition: prevector.h:206
void change_capacity(size_type new_capacity)
Definition: prevector.h:136
void fill(T *dst, ptrdiff_t count, const T &value=T{})
Definition: prevector.h:170
void pop_back()
Definition: prevector.h:404
iterator erase(iterator first, iterator last)
Definition: prevector.h:376
prevector(InputIterator first, InputIterator last)
Definition: prevector.h:217
void swap(prevector< N, T, Size, Diff > &other) noexcept
Definition: prevector.h:424
prevector & operator=(prevector< N, T, Size, Diff > &&other) noexcept
Definition: prevector.h:245
Diff difference_type
Definition: prevector.h:44
const value_type & const_reference
Definition: prevector.h:47
size_type _size
Definition: prevector.h:125
void shrink_to_fit()
Definition: prevector.h:307
void clear()
Definition: prevector.h:311
value_type & reference
Definition: prevector.h:46
~prevector()
Definition: prevector.h:430
size_type size() const
Definition: prevector.h:255
T & front()
Definition: prevector.h:408
bool operator==(const prevector< N, T, Size, Diff > &other) const
Definition: prevector.h:437
iterator erase(iterator pos)
Definition: prevector.h:372
prevector(size_type n, const T &val)
Definition: prevector.h:210
void fill(T *dst, InputIterator first, InputIterator last)
Definition: prevector.h:175
Size size_type
Definition: prevector.h:43
const T * indirect_ptr(difference_type pos) const
Definition: prevector.h:133
size_t capacity() const
Definition: prevector.h:268
T * direct_ptr(difference_type pos)
Definition: prevector.h:130
const_iterator end() const
Definition: prevector.h:266
const T & front() const
Definition: prevector.h:412
direct_or_indirect _union
Definition: prevector.h:124
void assign(InputIterator first, InputIterator last)
Definition: prevector.h:194
void emplace_back(Args &&... args)
Definition: prevector.h:391
bool is_direct() const
Definition: prevector.h:134
T & back()
Definition: prevector.h:416
void insert(iterator pos, InputIterator first, InputIterator last)
Definition: prevector.h:343
const T * item_ptr(difference_type pos) const
Definition: prevector.h:168
bool operator<(const prevector< N, T, Size, Diff > &other) const
Definition: prevector.h:458
value_type * data()
Definition: prevector.h:489
iterator begin()
Definition: prevector.h:263
T value_type
Definition: prevector.h:45
iterator end()
Definition: prevector.h:265
prevector()=default
const value_type * data() const
Definition: prevector.h:493
static constexpr unsigned int STATIC_SIZE
Definition: prevector.h:41
bool operator!=(const prevector< N, T, Size, Diff > &other) const
Definition: prevector.h:454
const T & back() const
Definition: prevector.h:420
void reserve(size_type new_capacity)
Definition: prevector.h:301
prevector(const prevector< N, T, Size, Diff > &other)
Definition: prevector.h:224
const T & operator[](size_type pos) const
Definition: prevector.h:280
const T * direct_ptr(difference_type pos) const
Definition: prevector.h:131
void resize_uninitialized(size_type new_size)
Definition: prevector.h:357
T * item_ptr(difference_type pos)
Definition: prevector.h:167
T * indirect_ptr(difference_type pos)
Definition: prevector.h:132
prevector & operator=(const prevector< N, T, Size, Diff > &other)
Definition: prevector.h:237
void resize(size_type new_size)
Definition: prevector.h:284
size_t allocated_memory() const
Definition: prevector.h:481
iterator insert(iterator pos, const T &value)
Definition: prevector.h:315
value_type * pointer
Definition: prevector.h:48
prevector(prevector< N, T, Size, Diff > &&other) noexcept
Definition: prevector.h:231
const value_type * const_pointer
Definition: prevector.h:49
void assign(size_type n, const T &val)
Definition: prevector.h:184
void insert(iterator pos, size_type count, const T &value)
Definition: prevector.h:329
void push_back(const T &value)
Definition: prevector.h:400
const_iterator begin() const
Definition: prevector.h:264
T & operator[](size_type pos)
Definition: prevector.h:276
static int count
struct prevector::direct_or_indirect::@2 indirect_contents
char direct[sizeof(T) *N]
Definition: prevector.h:117
assert(!tx.IsCoinBase())