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