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 : 113981631 : iterator(T* ptr_) : ptr(ptr_) {}
# 56 : 91698350 : T& operator*() const { return *ptr; }
# 57 : : T* operator->() const { return ptr; }
# 58 : 4209152 : T& operator[](size_type pos) { return ptr[pos]; }
# 59 : : const T& operator[](size_type pos) const { return ptr[pos]; }
# 60 : 10944266 : 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 : 32158284 : difference_type friend operator-(iterator a, iterator b) { return (&(*a) - &(*b)); }
# 65 : 8715392 : iterator operator+(size_type n) { return iterator(ptr + n); }
# 66 : : iterator& operator+=(size_type n) { ptr += n; return *this; }
# 67 : 4223104 : 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 : 12099015 : 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 : 1064704 : reverse_iterator(T* ptr_) : ptr(ptr_) {}
# 86 : 4209152 : 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 : 4209152 : 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 : 4741504 : 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 :24309218860 : const_iterator(const T* ptr_) : ptr(ptr_) {}
# 107 : 2837593 : const_iterator(iterator x) : ptr(&(*x)) {}
# 108 :55927589508 : const T& operator*() const { return *ptr; }
# 109 : : const T* operator->() const { return ptr; }
# 110 : 677552 : const T& operator[](size_type pos) const { return ptr[pos]; }
# 111 :21188902055 : const_iterator& operator++() { ptr++; return *this; }
# 112 : : const_iterator& operator--() { ptr--; return *this; }
# 113 : 391045667 : const_iterator operator++(int) { const_iterator copy(*this); ++(*this); return copy; }
# 114 : : const_iterator operator--(int) { const_iterator copy(*this); --(*this); return copy; }
# 115 : 603841354 : difference_type friend operator-(const_iterator a, const_iterator b) { return (&(*a) - &(*b)); }
# 116 : 29336816 : const_iterator operator+(size_type n) { return const_iterator(ptr + n); }
# 117 : 80923940 : 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 : 11418 : bool operator==(const_iterator x) const { return ptr == x.ptr; }
# 121 :20274662860 : bool operator!=(const_iterator x) const { return ptr != x.ptr; }
# 122 : 392620659 : 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 : 391942389 : 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 : 1064704 : const_reverse_iterator(const T* ptr_) : ptr(ptr_) {}
# 137 : : const_reverse_iterator(reverse_iterator x) : ptr(&(*x)) {}
# 138 : 4209152 : const T& operator*() const { return *ptr; }
# 139 : : const T* operator->() const { return ptr; }
# 140 : : const_reverse_iterator& operator--() { ptr++; return *this; }
# 141 : 4209152 : 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 : 4741504 : 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 : 153719893 : T* direct_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.direct) + pos; }
# 165 :23972996919 : const T* direct_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.direct) + pos; }
# 166 : 46415346 : T* indirect_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.indirect_contents.indirect) + pos; }
# 167 : 768834675 : const T* indirect_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.indirect_contents.indirect) + pos; }
# 168 :66237534138 : bool is_direct() const { return _size <= N; }
# 169 : :
# 170 : 143157275 : void change_capacity(size_type new_capacity) {
# 171 [ + + ][ + + ]: 143157275 : if (new_capacity <= N) {
# [ + - ][ + + ]
# [ + - ]
# 172 [ + + ][ + + ]: 136401143 : if (!is_direct()) {
# [ - + ][ - + ]
# [ - + ]
# 173 : 115521 : T* indirect = indirect_ptr(0);
# 174 : 115521 : T* src = indirect;
# 175 : 115521 : T* dst = direct_ptr(0);
# 176 : 115521 : memcpy(dst, src, size() * sizeof(T));
# 177 : 115521 : free(indirect);
# 178 : 115521 : _size -= N + 1;
# 179 : 115521 : }
# 180 : 136401143 : } else {
# 181 [ + + ][ + + ]: 6756132 : 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 : 74705 : _union.indirect_contents.indirect = static_cast<char*>(realloc(_union.indirect_contents.indirect, ((size_t)sizeof(T)) * new_capacity));
# 186 : 74705 : assert(_union.indirect_contents.indirect);
# 187 : 74705 : _union.indirect_contents.capacity = new_capacity;
# 188 : 6681427 : } else {
# 189 : 6681427 : char* new_indirect = static_cast<char*>(malloc(((size_t)sizeof(T)) * new_capacity));
# 190 : 6681427 : assert(new_indirect);
# 191 : 6681427 : T* src = direct_ptr(0);
# 192 : 6681427 : T* dst = reinterpret_cast<T*>(new_indirect);
# 193 : 6681427 : memcpy(dst, src, size() * sizeof(T));
# 194 : 6681427 : _union.indirect_contents.indirect = new_indirect;
# 195 : 6681427 : _union.indirect_contents.capacity = new_capacity;
# 196 : 6681427 : _size += N + 1;
# 197 : 6681427 : }
# 198 : 6756132 : }
# 199 : 143157275 : }
# 200 : :
# 201 [ + + ][ + - ]: 193210104 : T* item_ptr(difference_type pos) { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
# [ + + ][ + + ]
# [ + - ]
# 202 [ + - ][ + + ]:24741962902 : const T* item_ptr(difference_type pos) const { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
# [ + + ][ + + ]
# 203 : :
# 204 : 2792150 : void fill(T* dst, ptrdiff_t count, const T& value = T{}) {
# 205 : 2792150 : std::fill_n(dst, count, value);
# 206 : 2792150 : }
# 207 : :
# 208 : : template<typename InputIterator>
# 209 : 68275598 : void fill(T* dst, InputIterator first, InputIterator last) {
# 210 [ + + ][ + + ]: 3993059773 : while (first != last) {
# [ + + ][ + + ]
# [ + + ][ + + ]
# [ + + ][ + + ]
# [ + + ][ + + ]
# [ + + ][ + + ]
# [ + + ][ + + ]
# [ + + ][ + + ]
# 211 : 3924784175 : new(static_cast<void*>(dst)) T(*first);
# 212 : 3924784175 : ++dst;
# 213 : 3924784175 : ++first;
# 214 : 3924784175 : }
# 215 : 68275598 : }
# 216 : :
# 217 : : public:
# 218 : 173408 : void assign(size_type n, const T& val) {
# 219 : 173408 : clear();
# 220 [ + + ][ + + ]: 173408 : if (capacity() < n) {
# [ - + ]
# 221 : 94937 : change_capacity(n);
# 222 : 94937 : }
# 223 : 173408 : _size += n;
# 224 : 173408 : fill(item_ptr(0), n, val);
# 225 : 173408 : }
# 226 : :
# 227 : : template<typename InputIterator>
# 228 : 14785345 : void assign(InputIterator first, InputIterator last) {
# 229 : 14785345 : size_type n = last - first;
# 230 : 14785345 : clear();
# 231 [ + + ][ + + ]: 14785345 : if (capacity() < n) {
# [ + + ][ - + ]
# [ + + ][ + + ]
# 232 : 1009242 : change_capacity(n);
# 233 : 1009242 : }
# 234 : 14785345 : _size += n;
# 235 : 14785345 : fill(item_ptr(0), first, last);
# 236 : 14785345 : }
# 237 : :
# 238 : 115350720 : prevector() {}
# 239 : :
# 240 : : explicit prevector(size_type n) {
# 241 : : resize(n);
# 242 : : }
# 243 : :
# 244 : 2148235 : explicit prevector(size_type n, const T& val) {
# 245 : 2148235 : change_capacity(n);
# 246 : 2148235 : _size += n;
# 247 : 2148235 : fill(item_ptr(0), n, val);
# 248 : 2148235 : }
# 249 : :
# 250 : : template<typename InputIterator>
# 251 : 3145495 : prevector(InputIterator first, InputIterator last) {
# 252 : 3145495 : size_type n = last - first;
# 253 : 3145495 : change_capacity(n);
# 254 : 3145495 : _size += n;
# 255 : 3145495 : fill(item_ptr(0), first, last);
# 256 : 3145495 : }
# 257 : :
# 258 : 39030754 : prevector(const prevector<N, T, Size, Diff>& other) {
# 259 : 39030754 : size_type n = other.size();
# 260 : 39030754 : change_capacity(n);
# 261 : 39030754 : _size += n;
# 262 : 39030754 : fill(item_ptr(0), other.begin(), other.end());
# 263 : 39030754 : }
# 264 : :
# 265 : 12035610 : prevector(prevector<N, T, Size, Diff>&& other) {
# 266 : 12035610 : swap(other);
# 267 : 12035610 : }
# 268 : :
# 269 : 14420391 : prevector& operator=(const prevector<N, T, Size, Diff>& other) {
# 270 [ + + ][ - + ]: 14420391 : if (&other == this) {
# [ + + ]
# 271 : 25927 : return *this;
# 272 : 25927 : }
# 273 : 14394464 : assign(other.begin(), other.end());
# 274 : 14394464 : return *this;
# 275 : 14394464 : }
# 276 : :
# 277 : 23250607 : prevector& operator=(prevector<N, T, Size, Diff>&& other) {
# 278 : 23250607 : swap(other);
# 279 : 23250607 : return *this;
# 280 : 23250607 : }
# 281 : :
# 282 :40913092219 : size_type size() const {
# 283 [ + - ][ + + ]:40913092219 : return is_direct() ? _size : _size - N - 1;
# [ + + ][ + - ]
# [ + + ]
# 284 :40913092219 : }
# 285 : :
# 286 : 53198279 : bool empty() const {
# 287 : 53198279 : return size() == 0;
# 288 : 53198279 : }
# 289 : :
# 290 : 41973149 : iterator begin() { return iterator(item_ptr(0)); }
# 291 :15677741342 : const_iterator begin() const { return const_iterator(item_ptr(0)); }
# 292 : 38981071 : iterator end() { return iterator(item_ptr(size())); }
# 293 : 8602324425 : const_iterator end() const { return const_iterator(item_ptr(size())); }
# 294 : :
# 295 : 532352 : reverse_iterator rbegin() { return reverse_iterator(item_ptr(size() - 1)); }
# 296 : 532352 : const_reverse_iterator rbegin() const { return const_reverse_iterator(item_ptr(size() - 1)); }
# 297 : 532352 : reverse_iterator rend() { return reverse_iterator(item_ptr(-1)); }
# 298 : 532352 : const_reverse_iterator rend() const { return const_reverse_iterator(item_ptr(-1)); }
# 299 : :
# 300 : 47346461 : size_t capacity() const {
# 301 [ + + ][ + + ]: 47346461 : if (is_direct()) {
# [ + + ][ + - ]
# [ + - ]
# 302 : 45288813 : return N;
# 303 : 45288813 : } else {
# 304 : 2057648 : return _union.indirect_contents.capacity;
# 305 : 2057648 : }
# 306 : 47346461 : }
# 307 : :
# 308 : 19549092 : T& operator[](size_type pos) {
# 309 : 19549092 : return *item_ptr(pos);
# 310 : 19549092 : }
# 311 : :
# 312 : 113328694 : const T& operator[](size_type pos) const {
# 313 : 113328694 : return *item_ptr(pos);
# 314 : 113328694 : }
# 315 : :
# 316 : 112125862 : void resize(size_type new_size) {
# 317 : 112125862 : size_type cur_size = size();
# 318 [ + + ][ - + ]: 112125862 : if (cur_size == new_size) {
# [ + + ][ + + ]
# 319 : 110508547 : return;
# 320 : 110508547 : }
# 321 [ - + ][ + + ]: 1617315 : if (cur_size > new_size) {
# [ + + ][ + + ]
# 322 : 1178444 : erase(item_ptr(new_size), end());
# 323 : 1178444 : return;
# 324 : 1178444 : }
# 325 [ + + ][ - + ]: 438871 : if (new_size > capacity()) {
# [ + + ][ + + ]
# 326 : 119147 : change_capacity(new_size);
# 327 : 119147 : }
# 328 : 438871 : ptrdiff_t increase = new_size - cur_size;
# 329 : 438871 : fill(item_ptr(cur_size), increase);
# 330 : 438871 : _size += increase;
# 331 : 438871 : }
# 332 : :
# 333 : 7936 : void reserve(size_type new_capacity) {
# 334 [ + + ]: 7936 : if (new_capacity > capacity()) {
# 335 : 1920 : change_capacity(new_capacity);
# 336 : 1920 : }
# 337 : 7936 : }
# 338 : :
# 339 : 94957977 : void shrink_to_fit() {
# 340 : 94957977 : change_capacity(size());
# 341 : 94957977 : }
# 342 : :
# 343 : 111663106 : void clear() {
# 344 : 111663106 : resize(0);
# 345 : 111663106 : }
# 346 : :
# 347 : 18924939 : iterator insert(iterator pos, const T& value) {
# 348 : 18924939 : size_type p = pos - begin();
# 349 : 18924939 : size_type new_size = size() + 1;
# 350 [ + + ][ + + ]: 18924939 : if (capacity() < new_size) {
# 351 : 6216 : change_capacity(new_size + (new_size >> 1));
# 352 : 6216 : }
# 353 : 18924939 : T* ptr = item_ptr(p);
# 354 : 18924939 : memmove(ptr + 1, ptr, (size() - p) * sizeof(T));
# 355 : 18924939 : _size++;
# 356 : 18924939 : new(static_cast<void*>(ptr)) T(value);
# 357 : 18924939 : return iterator(ptr);
# 358 : 18924939 : }
# 359 : :
# 360 : 31744 : void insert(iterator pos, size_type count, const T& value) {
# 361 : 31744 : size_type p = pos - begin();
# 362 : 31744 : size_type new_size = size() + count;
# 363 [ + + ]: 31744 : if (capacity() < new_size) {
# 364 : 1152 : change_capacity(new_size + (new_size >> 1));
# 365 : 1152 : }
# 366 : 31744 : T* ptr = item_ptr(p);
# 367 : 31744 : memmove(ptr + count, ptr, (size() - p) * sizeof(T));
# 368 : 31744 : _size += count;
# 369 : 31744 : fill(item_ptr(p), count, value);
# 370 : 31744 : }
# 371 : :
# 372 : : template<typename InputIterator>
# 373 : 11314272 : void insert(iterator pos, InputIterator first, InputIterator last) {
# 374 : 11314272 : size_type p = pos - begin();
# 375 : 11314272 : difference_type count = last - first;
# 376 : 11314272 : size_type new_size = size() + count;
# 377 [ + + ][ - + ]: 11314272 : if (capacity() < new_size) {
# [ - + ][ + + ]
# [ + + ][ - + ]
# [ + + ]
# 378 : 1733386 : change_capacity(new_size + (new_size >> 1));
# 379 : 1733386 : }
# 380 : 11314272 : T* ptr = item_ptr(p);
# 381 : 11314272 : memmove(ptr + count, ptr, (size() - p) * sizeof(T));
# 382 : 11314272 : _size += count;
# 383 : 11314272 : fill(ptr, first, last);
# 384 : 11314272 : }
# 385 : :
# 386 : 1599719 : 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 [ + + ][ + + ]: 1599719 : if (capacity() < new_size) {
# 390 : 900392 : change_capacity(new_size);
# 391 : 900392 : _size += new_size - size();
# 392 : 900392 : return;
# 393 : 900392 : }
# 394 [ + + ][ - + ]: 699327 : if (new_size < size()) {
# 395 : 7424 : erase(item_ptr(new_size), end());
# 396 : 691903 : } else {
# 397 : 691903 : _size += new_size - size();
# 398 : 691903 : }
# 399 : 699327 : }
# 400 : :
# 401 : 56192 : iterator erase(iterator pos) {
# 402 : 56192 : return erase(pos, pos + 1);
# 403 : 56192 : }
# 404 : :
# 405 : 1295564 : 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 : 1295564 : iterator p = first;
# 413 : 1295564 : char* endp = (char*)&(*end());
# 414 : 1295564 : 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 : 1295564 : } else {
# 421 : 1295564 : _size -= last - p;
# 422 : 1295564 : }
# 423 : 1295564 : memmove(&(*first), &(*last), endp - ((char*)(&(*last))));
# 424 : 1295564 : return first;
# 425 : 1295564 : }
# 426 : :
# 427 : : template<typename... Args>
# 428 : 60745 : void emplace_back(Args&&... args) {
# 429 : 60745 : size_type new_size = size() + 1;
# 430 [ + + ][ + + ]: 60745 : if (capacity() < new_size) {
# 431 : 10849 : change_capacity(new_size + (new_size >> 1));
# 432 : 10849 : }
# 433 : 60745 : new(item_ptr(size())) T(std::forward<Args>(args)...);
# 434 : 60745 : _size++;
# 435 : 60745 : }
# 436 : :
# 437 : 60745 : void push_back(const T& value) {
# 438 : 60745 : emplace_back(value);
# 439 : 60745 : }
# 440 : :
# 441 : 13952 : void pop_back() {
# 442 : 13952 : erase(end() - 1, end());
# 443 : 13952 : }
# 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 : 74044 : const T& back() const {
# 458 : 74044 : return *item_ptr(size() - 1);
# 459 : 74044 : }
# 460 : :
# 461 : 35311345 : void swap(prevector<N, T, Size, Diff>& other) {
# 462 : 35311345 : std::swap(_union, other._union);
# 463 : 35311345 : std::swap(_size, other._size);
# 464 : 35311345 : }
# 465 : :
# 466 : 171276974 : ~prevector() {
# 467 : 171276974 : if (!std::is_trivially_destructible<T>::value) {
# 468 : 0 : clear();
# 469 : 0 : }
# 470 [ + + ][ - + ]: 171276974 : if (!is_direct()) {
# [ + + ][ - + ]
# [ + + ]
# 471 : 6451138 : free(_union.indirect_contents.indirect);
# 472 : 6451138 : _union.indirect_contents.indirect = nullptr;
# 473 : 6451138 : }
# 474 : 171276974 : }
# 475 : :
# 476 : 1883267 : bool operator==(const prevector<N, T, Size, Diff>& other) const {
# 477 [ - + ][ + + ]: 1883267 : if (other.size() != size()) {
# [ - + ]
# 478 : 96 : return false;
# 479 : 96 : }
# 480 : 1883171 : const_iterator b1 = begin();
# 481 : 1883171 : const_iterator b2 = other.begin();
# 482 : 1883171 : const_iterator e1 = end();
# 483 [ + + ][ + + ]: 33883593 : while (b1 != e1) {
# [ + + ]
# 484 [ + + ][ - + ]: 32001597 : if ((*b1) != (*b2)) {
# [ + + ]
# 485 : 1175 : return false;
# 486 : 1175 : }
# 487 : 32000422 : ++b1;
# 488 : 32000422 : ++b2;
# 489 : 32000422 : }
# 490 : 1883171 : return true;
# 491 : 1883171 : }
# 492 : :
# 493 : 10141 : bool operator!=(const prevector<N, T, Size, Diff>& other) const {
# 494 : 10141 : return !(*this == other);
# 495 : 10141 : }
# 496 : :
# 497 : 7779180849 : bool operator<(const prevector<N, T, Size, Diff>& other) const {
# 498 [ + + ][ - + ]: 7779180849 : if (size() < other.size()) {
# 499 : 5619020 : return true;
# 500 : 5619020 : }
# 501 [ - + ][ + + ]: 7773561829 : if (size() > other.size()) {
# 502 : 1998829 : return false;
# 503 : 1998829 : }
# 504 : 7771563000 : const_iterator b1 = begin();
# 505 : 7771563000 : const_iterator b2 = other.begin();
# 506 : 7771563000 : const_iterator e1 = end();
# 507 [ + + ][ + + ]:16126793736 : while (b1 != e1) {
# 508 [ + + ][ + + ]:14982432644 : if ((*b1) < (*b2)) {
# 509 : 4866030877 : return true;
# 510 : 4866030877 : }
# 511 [ + + ][ + + ]:10116401767 : if ((*b2) < (*b1)) {
# 512 : 1761171031 : return false;
# 513 : 1761171031 : }
# 514 : 8355230736 : ++b1;
# 515 : 8355230736 : ++b2;
# 516 : 8355230736 : }
# 517 : 7771563000 : return false;
# 518 : 7771563000 : }
# 519 : :
# 520 : 30162774 : size_t allocated_memory() const {
# 521 [ + + ]: 30162774 : if (is_direct()) {
# 522 : 28466073 : return 0;
# 523 : 28466073 : } else {
# 524 : 1696701 : return ((size_t)(sizeof(T))) * _union.indirect_contents.capacity;
# 525 : 1696701 : }
# 526 : 30162774 : }
# 527 : :
# 528 : 424928 : value_type* data() {
# 529 : 424928 : return item_ptr(0);
# 530 : 424928 : }
# 531 : :
# 532 : 347704462 : const value_type* data() const {
# 533 : 347704462 : return item_ptr(0);
# 534 : 347704462 : }
# 535 : : };
# 536 : :
# 537 : : #endif // BITCOIN_PREVECTOR_H
|
