Bitcoin Core  0.19.99
P2P Digital Currency
prevector.h
Go to the documentation of this file.
1 // Copyright (c) 2015-2018 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 <assert.h>
9 #include <stdlib.h>
10 #include <stdint.h>
11 #include <string.h>
12 
13 #include <algorithm>
14 #include <cstddef>
15 #include <type_traits>
16 #include <utility>
17 
18 #pragma pack(push, 1)
19 
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  iterator(T* ptr_) : ptr(ptr_) {}
57  T& operator*() const { return *ptr; }
58  T* operator->() const { return ptr; }
59  T& operator[](size_type pos) { return ptr[pos]; }
60  const T& operator[](size_type pos) const { return ptr[pos]; }
61  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  difference_type friend operator-(iterator a, iterator b) { return (&(*a) - &(*b)); }
66  iterator operator+(size_type n) { return iterator(ptr + n); }
67  iterator& operator+=(size_type n) { ptr += n; return *this; }
68  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  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 
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 
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  const_iterator(const T* ptr_) : ptr(ptr_) {}
108  const_iterator(iterator x) : ptr(&(*x)) {}
109  const T& operator*() const { return *ptr; }
110  const T* operator->() const { return ptr; }
111  const T& operator[](size_type pos) const { return ptr[pos]; }
112  const_iterator& operator++() { ptr++; return *this; }
113  const_iterator& operator--() { ptr--; return *this; }
114  const_iterator operator++(int) { const_iterator copy(*this); ++(*this); return copy; }
115  const_iterator operator--(int) { const_iterator copy(*this); --(*this); return copy; }
116  difference_type friend operator-(const_iterator a, const_iterator b) { return (&(*a) - &(*b)); }
117  const_iterator operator+(size_type n) { return const_iterator(ptr + n); }
118  const_iterator& operator+=(size_type n) { ptr += n; return *this; }
119  const_iterator operator-(size_type n) { return const_iterator(ptr - n); }
120  const_iterator& operator-=(size_type n) { ptr -= n; return *this; }
121  bool operator==(const_iterator x) const { return ptr == x.ptr; }
122  bool operator!=(const_iterator x) const { return ptr != x.ptr; }
123  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  bool operator<(const_iterator x) const { return ptr < x.ptr; }
127  };
128 
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_) {}
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;
152  char direct[sizeof(T) * N];
153  struct {
154  size_type capacity;
155  char* indirect;
156  };
157  } _union = {};
158 
159  T* direct_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.direct) + pos; }
160  const T* direct_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.direct) + pos; }
161  T* indirect_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.indirect) + pos; }
162  const T* indirect_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.indirect) + pos; }
163  bool is_direct() const { return _size <= N; }
164 
165  void change_capacity(size_type new_capacity) {
166  if (new_capacity <= N) {
167  if (!is_direct()) {
168  T* indirect = indirect_ptr(0);
169  T* src = indirect;
170  T* dst = direct_ptr(0);
171  memcpy(dst, src, size() * sizeof(T));
172  free(indirect);
173  _size -= N + 1;
174  }
175  } else {
176  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  _union.indirect = static_cast<char*>(realloc(_union.indirect, ((size_t)sizeof(T)) * new_capacity));
181  assert(_union.indirect);
182  _union.capacity = new_capacity;
183  } else {
184  char* new_indirect = static_cast<char*>(malloc(((size_t)sizeof(T)) * new_capacity));
185  assert(new_indirect);
186  T* src = direct_ptr(0);
187  T* dst = reinterpret_cast<T*>(new_indirect);
188  memcpy(dst, src, size() * sizeof(T));
189  _union.indirect = new_indirect;
190  _union.capacity = new_capacity;
191  _size += N + 1;
192  }
193  }
194  }
195 
196  T* item_ptr(difference_type pos) { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
197  const T* item_ptr(difference_type pos) const { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
198 
199  void fill(T* dst, ptrdiff_t count, const T& value = T{}) {
200  std::fill_n(dst, count, value);
201  }
202 
203  template<typename InputIterator>
204  void fill(T* dst, InputIterator first, InputIterator last) {
205  while (first != last) {
206  new(static_cast<void*>(dst)) T(*first);
207  ++dst;
208  ++first;
209  }
210  }
211 
212 public:
213  void assign(size_type n, const T& val) {
214  clear();
215  if (capacity() < n) {
216  change_capacity(n);
217  }
218  _size += n;
219  fill(item_ptr(0), n, val);
220  }
221 
222  template<typename InputIterator>
223  void assign(InputIterator first, InputIterator last) {
224  size_type n = last - first;
225  clear();
226  if (capacity() < n) {
227  change_capacity(n);
228  }
229  _size += n;
230  fill(item_ptr(0), first, last);
231  }
232 
234 
235  explicit prevector(size_type n) {
236  resize(n);
237  }
238 
239  explicit prevector(size_type n, const T& val) {
240  change_capacity(n);
241  _size += n;
242  fill(item_ptr(0), n, val);
243  }
244 
245  template<typename InputIterator>
246  prevector(InputIterator first, InputIterator last) {
247  size_type n = last - first;
248  change_capacity(n);
249  _size += n;
250  fill(item_ptr(0), first, last);
251  }
252 
254  size_type n = other.size();
255  change_capacity(n);
256  _size += n;
257  fill(item_ptr(0), other.begin(), other.end());
258  }
259 
261  swap(other);
262  }
263 
265  if (&other == this) {
266  return *this;
267  }
268  assign(other.begin(), other.end());
269  return *this;
270  }
271 
273  swap(other);
274  return *this;
275  }
276 
277  size_type size() const {
278  return is_direct() ? _size : _size - N - 1;
279  }
280 
281  bool empty() const {
282  return size() == 0;
283  }
284 
285  iterator begin() { return iterator(item_ptr(0)); }
286  const_iterator begin() const { return const_iterator(item_ptr(0)); }
287  iterator end() { return iterator(item_ptr(size())); }
289 
294 
295  size_t capacity() const {
296  if (is_direct()) {
297  return N;
298  } else {
299  return _union.capacity;
300  }
301  }
302 
303  T& operator[](size_type pos) {
304  return *item_ptr(pos);
305  }
306 
307  const T& operator[](size_type pos) const {
308  return *item_ptr(pos);
309  }
310 
311  void resize(size_type new_size) {
312  size_type cur_size = size();
313  if (cur_size == new_size) {
314  return;
315  }
316  if (cur_size > new_size) {
317  erase(item_ptr(new_size), end());
318  return;
319  }
320  if (new_size > capacity()) {
321  change_capacity(new_size);
322  }
323  ptrdiff_t increase = new_size - cur_size;
324  fill(item_ptr(cur_size), increase);
325  _size += increase;
326  }
327 
328  void reserve(size_type new_capacity) {
329  if (new_capacity > capacity()) {
330  change_capacity(new_capacity);
331  }
332  }
333 
334  void shrink_to_fit() {
336  }
337 
338  void clear() {
339  resize(0);
340  }
341 
342  iterator insert(iterator pos, const T& value) {
343  size_type p = pos - begin();
344  size_type new_size = size() + 1;
345  if (capacity() < new_size) {
346  change_capacity(new_size + (new_size >> 1));
347  }
348  T* ptr = item_ptr(p);
349  memmove(ptr + 1, ptr, (size() - p) * sizeof(T));
350  _size++;
351  new(static_cast<void*>(ptr)) T(value);
352  return iterator(ptr);
353  }
354 
355  void insert(iterator pos, size_type count, const T& value) {
356  size_type p = pos - begin();
357  size_type new_size = size() + count;
358  if (capacity() < new_size) {
359  change_capacity(new_size + (new_size >> 1));
360  }
361  T* ptr = item_ptr(p);
362  memmove(ptr + count, ptr, (size() - p) * sizeof(T));
363  _size += count;
364  fill(item_ptr(p), count, value);
365  }
366 
367  template<typename InputIterator>
368  void insert(iterator pos, InputIterator first, InputIterator last) {
369  size_type p = pos - begin();
370  difference_type count = last - first;
371  size_type new_size = size() + count;
372  if (capacity() < new_size) {
373  change_capacity(new_size + (new_size >> 1));
374  }
375  T* ptr = item_ptr(p);
376  memmove(ptr + count, ptr, (size() - p) * sizeof(T));
377  _size += count;
378  fill(ptr, first, last);
379  }
380 
381  inline void resize_uninitialized(size_type new_size) {
382  // resize_uninitialized changes the size of the prevector but does not initialize it.
383  // If size < new_size, the added elements must be initialized explicitly.
384  if (capacity() < new_size) {
385  change_capacity(new_size);
386  _size += new_size - size();
387  return;
388  }
389  if (new_size < size()) {
390  erase(item_ptr(new_size), end());
391  } else {
392  _size += new_size - size();
393  }
394  }
395 
397  return erase(pos, pos + 1);
398  }
399 
401  // Erase is not allowed to the change the object's capacity. That means
402  // that when starting with an indirectly allocated prevector with
403  // size and capacity > N, the result may be a still indirectly allocated
404  // prevector with size <= N and capacity > N. A shrink_to_fit() call is
405  // necessary to switch to the (more efficient) directly allocated
406  // representation (with capacity N and size <= N).
407  iterator p = first;
408  char* endp = (char*)&(*end());
409  if (!std::is_trivially_destructible<T>::value) {
410  while (p != last) {
411  (*p).~T();
412  _size--;
413  ++p;
414  }
415  } else {
416  _size -= last - p;
417  }
418  memmove(&(*first), &(*last), endp - ((char*)(&(*last))));
419  return first;
420  }
421 
422  void push_back(const T& value) {
423  size_type new_size = size() + 1;
424  if (capacity() < new_size) {
425  change_capacity(new_size + (new_size >> 1));
426  }
427  new(item_ptr(size())) T(value);
428  _size++;
429  }
430 
431  void pop_back() {
432  erase(end() - 1, end());
433  }
434 
435  T& front() {
436  return *item_ptr(0);
437  }
438 
439  const T& front() const {
440  return *item_ptr(0);
441  }
442 
443  T& back() {
444  return *item_ptr(size() - 1);
445  }
446 
447  const T& back() const {
448  return *item_ptr(size() - 1);
449  }
450 
452  std::swap(_union, other._union);
453  std::swap(_size, other._size);
454  }
455 
457  if (!std::is_trivially_destructible<T>::value) {
458  clear();
459  }
460  if (!is_direct()) {
461  free(_union.indirect);
462  _union.indirect = nullptr;
463  }
464  }
465 
466  bool operator==(const prevector<N, T, Size, Diff>& other) const {
467  if (other.size() != size()) {
468  return false;
469  }
470  const_iterator b1 = begin();
471  const_iterator b2 = other.begin();
472  const_iterator e1 = end();
473  while (b1 != e1) {
474  if ((*b1) != (*b2)) {
475  return false;
476  }
477  ++b1;
478  ++b2;
479  }
480  return true;
481  }
482 
483  bool operator!=(const prevector<N, T, Size, Diff>& other) const {
484  return !(*this == other);
485  }
486 
487  bool operator<(const prevector<N, T, Size, Diff>& other) const {
488  if (size() < other.size()) {
489  return true;
490  }
491  if (size() > other.size()) {
492  return false;
493  }
494  const_iterator b1 = begin();
495  const_iterator b2 = other.begin();
496  const_iterator e1 = end();
497  while (b1 != e1) {
498  if ((*b1) < (*b2)) {
499  return true;
500  }
501  if ((*b2) < (*b1)) {
502  return false;
503  }
504  ++b1;
505  ++b2;
506  }
507  return false;
508  }
509 
510  size_t allocated_memory() const {
511  if (is_direct()) {
512  return 0;
513  } else {
514  return ((size_t)(sizeof(T))) * _union.capacity;
515  }
516  }
517 
518  value_type* data() {
519  return item_ptr(0);
520  }
521 
522  const value_type* data() const {
523  return item_ptr(0);
524  }
525 };
526 #pragma pack(pop)
527 
528 #endif // BITCOIN_PREVECTOR_H
bool operator!=(const prevector< N, T, Size, Diff > &other) const
Definition: prevector.h:483
T * direct_ptr(difference_type pos)
Definition: prevector.h:159
std::bidirectional_iterator_tag iterator_category
Definition: prevector.h:85
prevector & operator=(const prevector< N, T, Size, Diff > &other)
Definition: prevector.h:264
const value_type & const_reference
Definition: prevector.h:44
const_iterator operator--(int)
Definition: prevector.h:115
void resize(size_type new_size)
Definition: prevector.h:311
const T * operator->() const
Definition: prevector.h:90
const T & operator[](size_type pos) const
Definition: prevector.h:60
const value_type * const_pointer
Definition: prevector.h:46
void assign(size_type n, const T &val)
Definition: prevector.h:213
T * indirect_ptr(difference_type pos)
Definition: prevector.h:161
iterator operator+(size_type n)
Definition: prevector.h:66
bool operator<=(const_iterator x) const
Definition: prevector.h:124
iterator operator-(size_type n)
Definition: prevector.h:68
T & back()
Definition: prevector.h:443
prevector(prevector< N, T, Size, Diff > &&other)
Definition: prevector.h:260
void assign(InputIterator first, InputIterator last)
Definition: prevector.h:223
void shrink_to_fit()
Definition: prevector.h:334
void pop_back()
Definition: prevector.h:431
T * operator->() const
Definition: prevector.h:58
reverse_iterator operator++(int)
Definition: prevector.h:93
iterator insert(iterator pos, const T &value)
Definition: prevector.h:342
void clear()
Definition: prevector.h:338
Size size_type
Definition: prevector.h:40
reverse_iterator operator--(int)
Definition: prevector.h:94
const T & operator[](size_type pos) const
Definition: prevector.h:111
bool operator!=(iterator x) const
Definition: prevector.h:71
const_iterator & operator-=(size_type n)
Definition: prevector.h:120
const_reverse_iterator & operator--()
Definition: prevector.h:141
const_iterator & operator++()
Definition: prevector.h:112
iterator operator++(int)
Definition: prevector.h:63
void insert(iterator pos, InputIterator first, InputIterator last)
Definition: prevector.h:368
const_reverse_iterator operator--(int)
Definition: prevector.h:144
void fill(T *dst, InputIterator first, InputIterator last)
Definition: prevector.h:204
const T & back() const
Definition: prevector.h:447
const T * operator->() const
Definition: prevector.h:140
iterator operator--(int)
Definition: prevector.h:64
const value_type * data() const
Definition: prevector.h:522
const T * direct_ptr(difference_type pos) const
Definition: prevector.h:160
size_t allocated_memory() const
Definition: prevector.h:510
bool operator==(const prevector< N, T, Size, Diff > &other) const
Definition: prevector.h:466
void resize_uninitialized(size_type new_size)
Definition: prevector.h:381
size_t capacity() const
Definition: prevector.h:295
const_reverse_iterator & operator++()
Definition: prevector.h:142
bool is_direct() const
Definition: prevector.h:163
~prevector()
Definition: prevector.h:456
iterator(T *ptr_)
Definition: prevector.h:56
T & operator[](size_type pos)
Definition: prevector.h:59
bool operator==(const_reverse_iterator x) const
Definition: prevector.h:145
bool operator>=(iterator x) const
Definition: prevector.h:72
value_type * data()
Definition: prevector.h:518
prevector(const prevector< N, T, Size, Diff > &other)
Definition: prevector.h:253
const_reverse_iterator operator++(int)
Definition: prevector.h:143
bool operator>=(const_iterator x) const
Definition: prevector.h:123
void fill(T *dst, ptrdiff_t count, const T &value=T{})
Definition: prevector.h:199
T value_type
Definition: prevector.h:42
const T * item_ptr(difference_type pos) const
Definition: prevector.h:197
iterator end()
Definition: prevector.h:287
Diff difference_type
Definition: prevector.h:41
void push_back(const T &value)
Definition: prevector.h:422
T & front()
Definition: prevector.h:435
prevector & operator=(prevector< N, T, Size, Diff > &&other)
Definition: prevector.h:272
value_type * pointer
Definition: prevector.h:45
const T & operator*() const
Definition: prevector.h:109
const_reverse_iterator rend() const
Definition: prevector.h:293
const_reverse_iterator rbegin() const
Definition: prevector.h:291
T & operator[](size_type pos)
Definition: prevector.h:303
void swap(prevector< N, T, Size, Diff > &other)
Definition: prevector.h:451
bool operator<=(iterator x) const
Definition: prevector.h:73
void insert(iterator pos, size_type count, const T &value)
Definition: prevector.h:355
const_iterator operator+(size_type n)
Definition: prevector.h:117
prevector(size_type n)
Definition: prevector.h:235
reverse_iterator rend()
Definition: prevector.h:292
const_reverse_iterator(reverse_iterator x)
Definition: prevector.h:138
bool operator>(const_iterator x) const
Definition: prevector.h:125
bool operator==(iterator x) const
Definition: prevector.h:70
reverse_iterator rbegin()
Definition: prevector.h:290
char direct[sizeof(T) *N]
Definition: prevector.h:152
iterator & operator+=(size_type n)
Definition: prevector.h:67
iterator erase(iterator pos)
Definition: prevector.h:396
bool operator<(iterator x) const
Definition: prevector.h:75
const_reverse_iterator(const T *ptr_)
Definition: prevector.h:137
const T & operator[](size_type pos) const
Definition: prevector.h:307
const_iterator(iterator x)
Definition: prevector.h:108
reverse_iterator & operator++()
Definition: prevector.h:92
Implements a drop-in replacement for std::vector<T> which stores up to N elements directly (without h...
Definition: prevector.h:38
T & operator*() const
Definition: prevector.h:57
bool operator!=(const_reverse_iterator x) const
Definition: prevector.h:146
const_iterator & operator--()
Definition: prevector.h:113
bool operator==(reverse_iterator x) const
Definition: prevector.h:95
const_iterator operator-(size_type n)
Definition: prevector.h:119
void reserve(size_type new_capacity)
Definition: prevector.h:328
const T * operator->() const
Definition: prevector.h:110
void change_capacity(size_type new_capacity)
Definition: prevector.h:165
const T & front() const
Definition: prevector.h:439
prevector(InputIterator first, InputIterator last)
Definition: prevector.h:246
T * item_ptr(difference_type pos)
Definition: prevector.h:196
void * memcpy(void *a, const void *b, size_t c)
bool empty() const
Definition: prevector.h:281
bool operator>(iterator x) const
Definition: prevector.h:74
reverse_iterator & operator--()
Definition: prevector.h:91
std::random_access_iterator_tag iterator_category
Definition: prevector.h:55
union prevector::direct_or_indirect _union
const T & operator*() const
Definition: prevector.h:88
std::bidirectional_iterator_tag iterator_category
Definition: prevector.h:136
static int count
Definition: tests.c:45
const_iterator operator++(int)
Definition: prevector.h:114
iterator begin()
Definition: prevector.h:285
std::random_access_iterator_tag iterator_category
Definition: prevector.h:106
size_type size() const
Definition: prevector.h:277
iterator erase(iterator first, iterator last)
Definition: prevector.h:400
bool operator!=(const_iterator x) const
Definition: prevector.h:122
iterator & operator++()
Definition: prevector.h:61
size_type _size
Definition: prevector.h:150
difference_type friend operator-(iterator a, iterator b)
Definition: prevector.h:65
const T * indirect_ptr(difference_type pos) const
Definition: prevector.h:162
bool operator<(const_iterator x) const
Definition: prevector.h:126
prevector(size_type n, const T &val)
Definition: prevector.h:239
const_iterator end() const
Definition: prevector.h:288
iterator & operator-=(size_type n)
Definition: prevector.h:69
void * memmove(void *a, const void *b, size_t c)
const_iterator begin() const
Definition: prevector.h:286
iterator & operator--()
Definition: prevector.h:62
bool operator==(const_iterator x) const
Definition: prevector.h:121
bool operator!=(reverse_iterator x) const
Definition: prevector.h:96
const_iterator & operator+=(size_type n)
Definition: prevector.h:118
const_iterator(const T *ptr_)
Definition: prevector.h:107
value_type & reference
Definition: prevector.h:43
difference_type friend operator-(const_iterator a, const_iterator b)
Definition: prevector.h:116