Branch data Line data Source code
# 1 : : // Copyright (c) 2015-2020 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 : : /** Implements a drop-in replacement for std::vector<T> which stores up to N
# 19 : : * elements directly (without heap allocation). The types Size and Diff are
# 20 : : * used to store element counts, and can be any unsigned + signed type.
# 21 : : *
# 22 : : * Storage layout is either:
# 23 : : * - Direct allocation:
# 24 : : * - Size _size: the number of used elements (between 0 and N)
# 25 : : * - T direct[N]: an array of N elements of type T
# 26 : : * (only the first _size are initialized).
# 27 : : * - Indirect allocation:
# 28 : : * - Size _size: the number of used elements plus N + 1
# 29 : : * - Size capacity: the number of allocated elements
# 30 : : * - T* indirect: a pointer to an array of capacity elements of type T
# 31 : : * (only the first _size are initialized).
# 32 : : *
# 33 : : * The data type T must be movable by memmove/realloc(). Once we switch to C++,
# 34 : : * move constructors can be used instead.
# 35 : : */
# 36 : : template<unsigned int N, typename T, typename Size = uint32_t, typename Diff = int32_t>
# 37 : : class prevector {
# 38 : : public:
# 39 : : typedef Size size_type;
# 40 : : typedef Diff difference_type;
# 41 : : typedef T value_type;
# 42 : : typedef value_type& reference;
# 43 : : typedef const value_type& const_reference;
# 44 : : typedef value_type* pointer;
# 45 : : typedef const value_type* const_pointer;
# 46 : :
# 47 : : class iterator {
# 48 : : T* ptr;
# 49 : : public:
# 50 : : typedef Diff difference_type;
# 51 : : typedef T value_type;
# 52 : : typedef T* pointer;
# 53 : : typedef T& reference;
# 54 : : typedef std::random_access_iterator_tag iterator_category;
# 55 : 159415214 : iterator(T* ptr_) : ptr(ptr_) {}
# 56 : 178622782 : T& operator*() const { return *ptr; }
# 57 : : T* operator->() const { return ptr; }
# 58 : 4245632 : T& operator[](size_type pos) { return ptr[pos]; }
# 59 : : const T& operator[](size_type pos) const { return ptr[pos]; }
# 60 : 12105295 : iterator& operator++() { ptr++; return *this; }
# 61 : : iterator& operator--() { ptr--; return *this; }
# 62 : : iterator operator++(int) { iterator copy(*this); ++(*this); return copy; }
# 63 : : iterator operator--(int) { iterator copy(*this); --(*this); return copy; }
# 64 : 47254292 : difference_type friend operator-(iterator a, iterator b) { return (&(*a) - &(*b)); }
# 65 : 8791552 : iterator operator+(size_type n) { return iterator(ptr + n); }
# 66 : : iterator& operator+=(size_type n) { ptr += n; return *this; }
# 67 : 4261760 : iterator operator-(size_type n) { return iterator(ptr - n); }
# 68 : : iterator& operator-=(size_type n) { ptr -= n; return *this; }
# 69 : : bool operator==(iterator x) const { return ptr == x.ptr; }
# 70 : 13371997 : 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 : : };
# 76 : :
# 77 : : class reverse_iterator {
# 78 : : T* ptr;
# 79 : : public:
# 80 : : typedef Diff difference_type;
# 81 : : typedef T value_type;
# 82 : : typedef T* pointer;
# 83 : : typedef T& reference;
# 84 : : typedef std::bidirectional_iterator_tag iterator_category;
# 85 : 1087232 : reverse_iterator(T* ptr_) : ptr(ptr_) {}
# 86 : 4245632 : T& operator*() { return *ptr; }
# 87 : : const T& operator*() const { return *ptr; }
# 88 : : T* operator->() { return ptr; }
# 89 : : const T* operator->() const { return ptr; }
# 90 : : reverse_iterator& operator--() { ptr++; return *this; }
# 91 : 4245632 : reverse_iterator& operator++() { ptr--; return *this; }
# 92 : : reverse_iterator operator++(int) { reverse_iterator copy(*this); ++(*this); return copy; }
# 93 : : reverse_iterator operator--(int) { reverse_iterator copy(*this); --(*this); return copy; }
# 94 : : bool operator==(reverse_iterator x) const { return ptr == x.ptr; }
# 95 : 4789248 : bool operator!=(reverse_iterator x) const { return ptr != x.ptr; }
# 96 : : };
# 97 : :
# 98 : : class const_iterator {
# 99 : : const T* ptr;
# 100 : : public:
# 101 : : typedef Diff difference_type;
# 102 : : typedef const T value_type;
# 103 : : typedef const T* pointer;
# 104 : : typedef const T& reference;
# 105 : : typedef std::random_access_iterator_tag iterator_category;
# 106 : 1030907019 : const_iterator(const T* ptr_) : ptr(ptr_) {}
# 107 : 2157207 : const_iterator(iterator x) : ptr(&(*x)) {}
# 108 : 7881337005 : const T& operator*() const { return *ptr; }
# 109 : : const T* operator->() const { return ptr; }
# 110 : 634091 : const T& operator[](size_type pos) const { return ptr[pos]; }
# 111 : 6446268223 : const_iterator& operator++() { ptr++; return *this; }
# 112 : : const_iterator& operator--() { ptr--; return *this; }
# 113 : 362404267 : const_iterator operator++(int) { const_iterator copy(*this); ++(*this); return copy; }
# 114 : : const_iterator operator--(int) { const_iterator copy(*this); --(*this); return copy; }
# 115 : 591665897 : difference_type friend operator-(const_iterator a, const_iterator b) { return (&(*a) - &(*b)); }
# 116 : 32653426 : const_iterator operator+(size_type n) { return const_iterator(ptr + n); }
# 117 : 89534951 : const_iterator& operator+=(size_type n) { ptr += n; return *this; }
# 118 : 1180 : const_iterator operator-(size_type n) { return const_iterator(ptr - n); }
# 119 : : const_iterator& operator-=(size_type n) { ptr -= n; return *this; }
# 120 : 16066 : bool operator==(const_iterator x) const { return ptr == x.ptr; }
# 121 : 6101550526 : bool operator!=(const_iterator x) const { return ptr != x.ptr; }
# 122 : 363725910 : 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 : 363517373 : bool operator<(const_iterator x) const { return ptr < x.ptr; }
# 126 : : };
# 127 : :
# 128 : : class const_reverse_iterator {
# 129 : : const T* ptr;
# 130 : : public:
# 131 : : typedef Diff difference_type;
# 132 : : typedef const T value_type;
# 133 : : typedef const T* pointer;
# 134 : : typedef const T& reference;
# 135 : : typedef std::bidirectional_iterator_tag iterator_category;
# 136 : 1087232 : const_reverse_iterator(const T* ptr_) : ptr(ptr_) {}
# 137 : : const_reverse_iterator(reverse_iterator x) : ptr(&(*x)) {}
# 138 : 4245632 : const T& operator*() const { return *ptr; }
# 139 : : const T* operator->() const { return ptr; }
# 140 : : const_reverse_iterator& operator--() { ptr++; return *this; }
# 141 : 4245632 : const_reverse_iterator& operator++() { ptr--; return *this; }
# 142 : : const_reverse_iterator operator++(int) { const_reverse_iterator copy(*this); ++(*this); return copy; }
# 143 : : const_reverse_iterator operator--(int) { const_reverse_iterator copy(*this); --(*this); return copy; }
# 144 : : bool operator==(const_reverse_iterator x) const { return ptr == x.ptr; }
# 145 : 4789248 : bool operator!=(const_reverse_iterator x) const { return ptr != x.ptr; }
# 146 : : };
# 147 : :
# 148 : : private:
# 149 : : #pragma pack(push, 1)
# 150 : : union direct_or_indirect {
# 151 : : char direct[sizeof(T) * N];
# 152 : : struct {
# 153 : : char* indirect;
# 154 : : size_type capacity;
# 155 : : } indirect_contents;
# 156 : : };
# 157 : : #pragma pack(pop)
# 158 : : alignas(char*) direct_or_indirect _union = {};
# 159 : : size_type _size = 0;
# 160 : :
# 161 : : static_assert(alignof(char*) % alignof(size_type) == 0 && sizeof(char*) % alignof(size_type) == 0, "size_type cannot have more restrictive alignment requirement than pointer");
# 162 : : static_assert(alignof(char*) % alignof(T) == 0, "value_type T cannot have more restrictive alignment requirement than pointer");
# 163 : :
# 164 : 183329424 : T* direct_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.direct) + pos; }
# 165 : 254847601 : const T* direct_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.direct) + pos; }
# 166 : 144805040 : T* indirect_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.indirect_contents.indirect) + pos; }
# 167 : 833311493 : const T* indirect_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.indirect_contents.indirect) + pos; }
# 168 : 3597152793 : bool is_direct() const { return _size <= N; }
# 169 : :
# 170 : 193765158 : void change_capacity(size_type new_capacity) {
# 171 [ + + ][ + + ]: 193765158 : if (new_capacity <= N) {
# [ + - ][ + - ]
# [ + + ]
# 172 [ - + ][ - + ]: 150495868 : if (!is_direct()) {
# [ + + ][ + + ]
# [ - + ]
# 173 : 13519856 : T* indirect = indirect_ptr(0);
# 174 : 13519856 : T* src = indirect;
# 175 : 13519856 : T* dst = direct_ptr(0);
# 176 : 13519856 : memcpy(dst, src, size() * sizeof(T));
# 177 : 13519856 : free(indirect);
# 178 : 13519856 : _size -= N + 1;
# 179 : 13519856 : }
# 180 : 150495868 : } else {
# 181 [ + + ][ # # ]: 43269290 : if (!is_direct()) {
# [ + + ][ # # ]
# [ - + ]
# 182 : : /* FIXME: Because malloc/realloc here won't call new_handler if allocation fails, assert
# 183 : : success. These should instead use an allocator or new/delete so that handlers
# 184 : : are called as necessary, but performance would be slightly degraded by doing so. */
# 185 : 108245 : _union.indirect_contents.indirect = static_cast<char*>(realloc(_union.indirect_contents.indirect, ((size_t)sizeof(T)) * new_capacity));
# 186 : 108245 : assert(_union.indirect_contents.indirect);
# 187 : 0 : _union.indirect_contents.capacity = new_capacity;
# 188 : 43161045 : } else {
# 189 : 43161045 : char* new_indirect = static_cast<char*>(malloc(((size_t)sizeof(T)) * new_capacity));
# 190 : 43161045 : assert(new_indirect);
# 191 : 0 : T* src = direct_ptr(0);
# 192 : 43161045 : T* dst = reinterpret_cast<T*>(new_indirect);
# 193 : 43161045 : memcpy(dst, src, size() * sizeof(T));
# 194 : 43161045 : _union.indirect_contents.indirect = new_indirect;
# 195 : 43161045 : _union.indirect_contents.capacity = new_capacity;
# 196 : 43161045 : _size += N + 1;
# 197 : 43161045 : }
# 198 : 43269290 : }
# 199 : 193765158 : }
# 200 : :
# 201 [ + + ][ + + ]: 257919665 : T* item_ptr(difference_type pos) { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
# [ + - ][ + + ]
# [ + - ]
# 202 [ + - ][ + + ]: 1088120219 : const T* item_ptr(difference_type pos) const { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
# [ + + ][ + + ]
# 203 : :
# 204 : 2943396 : void fill(T* dst, ptrdiff_t count, const T& value = T{}) {
# 205 : 2943396 : std::fill_n(dst, count, value);
# 206 : 2943396 : }
# 207 : :
# 208 : : template<typename InputIterator>
# 209 : 87605289 : void fill(T* dst, InputIterator first, InputIterator last) {
# 210 [ + + ][ + + ]: 5855299775 : while (first != last) {
# [ + + ][ + + ]
# [ + + ][ + + ]
# [ + + ][ + + ]
# [ + + ][ + + ]
# [ + + ][ + + ]
# [ + + ][ + + ]
# [ + + ][ + + ]
# 211 : 5767694486 : new(static_cast<void*>(dst)) T(*first);
# 212 : 5767694486 : ++dst;
# 213 : 5767694486 : ++first;
# 214 : 5767694486 : }
# 215 : 87605289 : }
# 216 : :
# 217 : : public:
# 218 : 173342 : void assign(size_type n, const T& val) {
# 219 : 173342 : clear();
# 220 [ - + ][ + + ]: 173342 : if (capacity() < n) {
# [ + + ]
# 221 : 94791 : change_capacity(n);
# 222 : 94791 : }
# 223 : 173342 : _size += n;
# 224 : 173342 : fill(item_ptr(0), n, val);
# 225 : 173342 : }
# 226 : :
# 227 : : template<typename InputIterator>
# 228 : 19208534 : void assign(InputIterator first, InputIterator last) {
# 229 : 19208534 : size_type n = last - first;
# 230 : 19208534 : clear();
# 231 [ - + ][ + + ]: 19208534 : if (capacity() < n) {
# [ + + ][ + + ]
# [ + + ][ + + ]
# 232 : 14439161 : change_capacity(n);
# 233 : 14439161 : }
# 234 : 19208534 : _size += n;
# 235 : 19208534 : fill(item_ptr(0), first, last);
# 236 : 19208534 : }
# 237 : :
# 238 : 129189696 : prevector() {}
# 239 : :
# 240 : : explicit prevector(size_type n) {
# 241 : : resize(n);
# 242 : : }
# 243 : :
# 244 : 2395573 : explicit prevector(size_type n, const T& val) {
# 245 : 2395573 : change_capacity(n);
# 246 : 2395573 : _size += n;
# 247 : 2395573 : fill(item_ptr(0), n, val);
# 248 : 2395573 : }
# 249 : :
# 250 : : template<typename InputIterator>
# 251 : 2735767 : prevector(InputIterator first, InputIterator last) {
# 252 : 2735767 : size_type n = last - first;
# 253 : 2735767 : change_capacity(n);
# 254 : 2735767 : _size += n;
# 255 : 2735767 : fill(item_ptr(0), first, last);
# 256 : 2735767 : }
# 257 : :
# 258 : 54837506 : prevector(const prevector<N, T, Size, Diff>& other) {
# 259 : 54837506 : size_type n = other.size();
# 260 : 54837506 : change_capacity(n);
# 261 : 54837506 : _size += n;
# 262 : 54837506 : fill(item_ptr(0), other.begin(), other.end());
# 263 : 54837506 : }
# 264 : :
# 265 : 18512256 : prevector(prevector<N, T, Size, Diff>&& other) {
# 266 : 18512256 : swap(other);
# 267 : 18512256 : }
# 268 : :
# 269 : 18756092 : prevector& operator=(const prevector<N, T, Size, Diff>& other) {
# 270 [ + + ][ - + ]: 18756092 : if (&other == this) {
# [ + + ]
# 271 : 25637 : return *this;
# 272 : 25637 : }
# 273 : 18730455 : assign(other.begin(), other.end());
# 274 : 18730455 : return *this;
# 275 : 18756092 : }
# 276 : :
# 277 : 27268374 : prevector& operator=(prevector<N, T, Size, Diff>&& other) {
# 278 : 27268374 : swap(other);
# 279 : 27268374 : return *this;
# 280 : 27268374 : }
# 281 : :
# 282 : 1744096587 : size_type size() const {
# 283 [ + + ][ + - ]: 1744096587 : return is_direct() ? _size : _size - N - 1;
# [ + - ][ + + ]
# [ + + ]
# 284 : 1744096587 : }
# 285 : :
# 286 : 52345911 : bool empty() const {
# 287 : 52345911 : return size() == 0;
# 288 : 52345911 : }
# 289 : :
# 290 : 42721689 : iterator begin() { return iterator(item_ptr(0)); }
# 291 : 177691141 : const_iterator begin() const { return const_iterator(item_ptr(0)); }
# 292 : 68008810 : iterator end() { return iterator(item_ptr(size())); }
# 293 : 820697560 : const_iterator end() const { return const_iterator(item_ptr(size())); }
# 294 : :
# 295 : 543616 : reverse_iterator rbegin() { return reverse_iterator(item_ptr(size() - 1)); }
# 296 : 543616 : const_reverse_iterator rbegin() const { return const_reverse_iterator(item_ptr(size() - 1)); }
# 297 : 543616 : reverse_iterator rend() { return reverse_iterator(item_ptr(-1)); }
# 298 : 543616 : const_reverse_iterator rend() const { return const_reverse_iterator(item_ptr(-1)); }
# 299 : :
# 300 : 52737697 : size_t capacity() const {
# 301 [ + - ][ + - ]: 52737697 : if (is_direct()) {
# [ + + ][ + + ]
# [ + + ]
# 302 : 47668362 : return N;
# 303 : 47668362 : } else {
# 304 : 5069335 : return _union.indirect_contents.capacity;
# 305 : 5069335 : }
# 306 : 52737697 : }
# 307 : :
# 308 : 19501868 : T& operator[](size_type pos) {
# 309 : 19501868 : return *item_ptr(pos);
# 310 : 19501868 : }
# 311 : :
# 312 : 41205060 : const T& operator[](size_type pos) const {
# 313 : 41205060 : return *item_ptr(pos);
# 314 : 41205060 : }
# 315 : :
# 316 : 138289609 : void resize(size_type new_size) {
# 317 : 138289609 : size_type cur_size = size();
# 318 [ - + ][ + + ]: 138289609 : if (cur_size == new_size) {
# [ + + ][ + + ]
# 319 : 122726759 : return;
# 320 : 122726759 : }
# 321 [ + + ][ - + ]: 15562850 : if (cur_size > new_size) {
# [ + + ][ + + ]
# 322 : 15219409 : erase(item_ptr(new_size), end());
# 323 : 15219409 : return;
# 324 : 15219409 : }
# 325 [ - + ][ + + ]: 343441 : if (new_size > capacity()) {
# [ + + ][ + + ]
# 326 : 132516 : change_capacity(new_size);
# 327 : 132516 : }
# 328 : 343441 : ptrdiff_t increase = new_size - cur_size;
# 329 : 343441 : fill(item_ptr(cur_size), increase);
# 330 : 343441 : _size += increase;
# 331 : 343441 : }
# 332 : :
# 333 : 8704 : void reserve(size_type new_capacity) {
# 334 [ + + ]: 8704 : if (new_capacity > capacity()) {
# 335 : 2432 : change_capacity(new_capacity);
# 336 : 2432 : }
# 337 : 8704 : }
# 338 : :
# 339 : 116719235 : void shrink_to_fit() {
# 340 : 116719235 : change_capacity(size());
# 341 : 116719235 : }
# 342 : :
# 343 : 137917722 : void clear() {
# 344 : 137917722 : resize(0);
# 345 : 137917722 : }
# 346 : :
# 347 : 20428102 : iterator insert(iterator pos, const T& value) {
# 348 : 20428102 : size_type p = pos - begin();
# 349 : 20428102 : size_type new_size = size() + 1;
# 350 [ + + ][ + + ]: 20428102 : if (capacity() < new_size) {
# 351 : 6077 : change_capacity(new_size + (new_size >> 1));
# 352 : 6077 : }
# 353 : 20428102 : T* ptr = item_ptr(p);
# 354 : 20428102 : memmove(ptr + 1, ptr, (size() - p) * sizeof(T));
# 355 : 20428102 : _size++;
# 356 : 20428102 : new(static_cast<void*>(ptr)) T(value);
# 357 : 20428102 : return iterator(ptr);
# 358 : 20428102 : }
# 359 : :
# 360 : 31104 : void insert(iterator pos, size_type count, const T& value) {
# 361 : 31104 : size_type p = pos - begin();
# 362 : 31104 : size_type new_size = size() + count;
# 363 [ + + ]: 31104 : if (capacity() < new_size) {
# 364 : 1024 : change_capacity(new_size + (new_size >> 1));
# 365 : 1024 : }
# 366 : 31104 : T* ptr = item_ptr(p);
# 367 : 31104 : memmove(ptr + count, ptr, (size() - p) * sizeof(T));
# 368 : 31104 : _size += count;
# 369 : 31104 : fill(item_ptr(p), count, value);
# 370 : 31104 : }
# 371 : :
# 372 : : template<typename InputIterator>
# 373 : 10827257 : void insert(iterator pos, InputIterator first, InputIterator last) {
# 374 : 10827257 : size_type p = pos - begin();
# 375 : 10827257 : difference_type count = last - first;
# 376 : 10827257 : size_type new_size = size() + count;
# 377 [ + + ][ - + ]: 10827257 : if (capacity() < new_size) {
# [ + + ][ + + ]
# [ - + ][ + + ]
# [ - + ][ + + ]
# 378 : 1448801 : change_capacity(new_size + (new_size >> 1));
# 379 : 1448801 : }
# 380 : 10827257 : T* ptr = item_ptr(p);
# 381 : 10827257 : memmove(ptr + count, ptr, (size() - p) * sizeof(T));
# 382 : 10827257 : _size += count;
# 383 : 10827257 : fill(ptr, first, last);
# 384 : 10827257 : }
# 385 : :
# 386 : 1623594 : inline void resize_uninitialized(size_type new_size) {
# 387 : : // resize_uninitialized changes the size of the prevector but does not initialize it.
# 388 : : // If size < new_size, the added elements must be initialized explicitly.
# 389 [ + + ][ + + ]: 1623594 : if (capacity() < new_size) {
# 390 : 940672 : change_capacity(new_size);
# 391 : 940672 : _size += new_size - size();
# 392 : 940672 : return;
# 393 : 940672 : }
# 394 [ - + ][ + + ]: 682922 : if (new_size < size()) {
# 395 : 7040 : erase(item_ptr(new_size), end());
# 396 : 675882 : } else {
# 397 : 675882 : _size += new_size - size();
# 398 : 675882 : }
# 399 : 682922 : }
# 400 : :
# 401 : 57216 : iterator erase(iterator pos) {
# 402 : 57216 : return erase(pos, pos + 1);
# 403 : 57216 : }
# 404 : :
# 405 : 15340497 : iterator erase(iterator first, iterator last) {
# 406 : : // Erase is not allowed to the change the object's capacity. That means
# 407 : : // that when starting with an indirectly allocated prevector with
# 408 : : // size and capacity > N, the result may be a still indirectly allocated
# 409 : : // prevector with size <= N and capacity > N. A shrink_to_fit() call is
# 410 : : // necessary to switch to the (more efficient) directly allocated
# 411 : : // representation (with capacity N and size <= N).
# 412 : 15340497 : iterator p = first;
# 413 : 15340497 : char* endp = (char*)&(*end());
# 414 : 15340497 : if (!std::is_trivially_destructible<T>::value) {
# 415 [ # # ][ # # ]: 0 : while (p != last) {
# [ # # ][ # # ]
# 416 : 0 : (*p).~T();
# 417 : 0 : _size--;
# 418 : 0 : ++p;
# 419 : 0 : }
# 420 : 15340497 : } else {
# 421 : 15340497 : _size -= last - p;
# 422 : 15340497 : }
# 423 : 15340497 : memmove(&(*first), &(*last), endp - ((char*)(&(*last))));
# 424 : 15340497 : return first;
# 425 : 15340497 : }
# 426 : :
# 427 : : template<typename... Args>
# 428 : 88195 : void emplace_back(Args&&... args) {
# 429 : 88195 : size_type new_size = size() + 1;
# 430 [ + + ][ + + ]: 88195 : if (capacity() < new_size) {
# 431 : 13334 : change_capacity(new_size + (new_size >> 1));
# 432 : 13334 : }
# 433 : 88195 : new(item_ptr(size())) T(std::forward<Args>(args)...);
# 434 : 88195 : _size++;
# 435 : 88195 : }
# 436 : :
# 437 : 88195 : void push_back(const T& value) {
# 438 : 88195 : emplace_back(value);
# 439 : 88195 : }
# 440 : :
# 441 : 16128 : void pop_back() {
# 442 : 16128 : erase(end() - 1, end());
# 443 : 16128 : }
# 444 : :
# 445 : : T& front() {
# 446 : : return *item_ptr(0);
# 447 : : }
# 448 : :
# 449 : : const T& front() const {
# 450 : : return *item_ptr(0);
# 451 : : }
# 452 : :
# 453 : : T& back() {
# 454 : : return *item_ptr(size() - 1);
# 455 : : }
# 456 : :
# 457 : 70806 : const T& back() const {
# 458 : 70806 : return *item_ptr(size() - 1);
# 459 : 70806 : }
# 460 : :
# 461 : 45814138 : void swap(prevector<N, T, Size, Diff>& other) {
# 462 : 45814138 : std::swap(_union, other._union);
# 463 : 45814138 : std::swap(_size, other._size);
# 464 : 45814138 : }
# 465 : :
# 466 : 207348938 : ~prevector() {
# 467 : 207348938 : if (!std::is_trivially_destructible<T>::value) {
# 468 : 0 : clear();
# 469 : 0 : }
# 470 [ + + ][ - + ]: 207348938 : if (!is_direct()) {
# [ + + ][ + + ]
# [ - + ]
# 471 : 29527186 : free(_union.indirect_contents.indirect);
# 472 : 29527186 : _union.indirect_contents.indirect = nullptr;
# 473 : 29527186 : }
# 474 : 207348938 : }
# 475 : :
# 476 : 1971737 : bool operator==(const prevector<N, T, Size, Diff>& other) const {
# 477 [ - + ][ + + ]: 1971737 : if (other.size() != size()) {
# [ - + ]
# 478 : 84 : return false;
# 479 : 84 : }
# 480 : 1971653 : const_iterator b1 = begin();
# 481 : 1971653 : const_iterator b2 = other.begin();
# 482 : 1971653 : const_iterator e1 = end();
# 483 [ + + ][ + + ]: 33351357 : while (b1 != e1) {
# [ + + ]
# 484 [ - + ][ + + ]: 31411493 : if ((*b1) != (*b2)) {
# [ + + ]
# 485 : 31789 : return false;
# 486 : 31789 : }
# 487 : 31379704 : ++b1;
# 488 : 31379704 : ++b2;
# 489 : 31379704 : }
# 490 : 1939864 : return true;
# 491 : 1971653 : }
# 492 : :
# 493 : 16933 : bool operator!=(const prevector<N, T, Size, Diff>& other) const {
# 494 : 16933 : return !(*this == other);
# 495 : 16933 : }
# 496 : :
# 497 : 55310062 : bool operator<(const prevector<N, T, Size, Diff>& other) const {
# 498 [ + + ][ - + ]: 55310062 : if (size() < other.size()) {
# 499 : 25429158 : return true;
# 500 : 25429158 : }
# 501 [ + + ][ - + ]: 29880904 : if (size() > other.size()) {
# 502 : 5140877 : return false;
# 503 : 5140877 : }
# 504 : 24740027 : const_iterator b1 = begin();
# 505 : 24740027 : const_iterator b2 = other.begin();
# 506 : 24740027 : const_iterator e1 = end();
# 507 [ + + ][ + + ]: 122988822 : while (b1 != e1) {
# 508 [ + + ][ + + ]: 120765022 : if ((*b1) < (*b2)) {
# 509 : 15238127 : return true;
# 510 : 15238127 : }
# 511 [ + + ][ + + ]: 105526895 : if ((*b2) < (*b1)) {
# 512 : 7278100 : return false;
# 513 : 7278100 : }
# 514 : 98248795 : ++b1;
# 515 : 98248795 : ++b2;
# 516 : 98248795 : }
# 517 : 2223800 : return false;
# 518 : 24740027 : }
# 519 : :
# 520 : 54703276 : size_t allocated_memory() const {
# 521 [ + + ]: 54703276 : if (is_direct()) {
# 522 : 4751282 : return 0;
# 523 : 49951994 : } else {
# 524 : 49951994 : return ((size_t)(sizeof(T))) * _union.indirect_contents.capacity;
# 525 : 49951994 : }
# 526 : 54703276 : }
# 527 : :
# 528 : 333136 : value_type* data() {
# 529 : 333136 : return item_ptr(0);
# 530 : 333136 : }
# 531 : :
# 532 : 47572211 : const value_type* data() const {
# 533 : 47572211 : return item_ptr(0);
# 534 : 47572211 : }
# 535 : : };
# 536 : :
# 537 : : #endif // BITCOIN_PREVECTOR_H
|
