LCOV - code coverage report
Current view: top level - src - prevector.h (source / functions) Coverage Total Hit
Test: test_bitcoin_coverage.info Lines: 100.0 % 245 245
Test Date: 2025-06-01 05:54:06 Functions: 97.7 % 88 86
Branches: 41.9 % 3622 1517

             Branch data     Line data    Source code
       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                 :             : 
      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                 :             :     static_assert(std::is_trivially_copyable_v<T>);
      39                 :             : 
      40                 :             : public:
      41                 :             :     typedef Size size_type;
      42                 :             :     typedef Diff difference_type;
      43                 :             :     typedef T value_type;
      44                 :             :     typedef value_type& reference;
      45                 :             :     typedef const value_type& const_reference;
      46                 :             :     typedef value_type* pointer;
      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                 :    18126848 :         iterator(T* ptr_) : ptr(ptr_) {}
      59                 :     4841774 :         T& operator*() const { return *ptr; }
      60                 :             :         T* operator->() const { return ptr; }
      61                 :     2099912 :         T& operator[](size_type pos) const { return ptr[pos]; }
      62                 :    39903718 :         iterator& operator++() { ptr++; return *this; }
      63                 :     2099912 :         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         [ +  - ]:     4143342 :         difference_type friend operator-(iterator a, iterator b) { return (&(*a) - &(*b)); }
      67                 :       80690 :         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                 :     2099912 :         iterator operator-(size_type n) const { return iterator(ptr - n); }
      71                 :             :         iterator& operator-=(size_type n) { ptr -= n; return *this; }
      72                 :     2366752 :         bool operator==(iterator x) const { return ptr == x.ptr; }
      73         [ +  + ]:    40245484 :         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                 :             : 
      80                 :             :     class const_iterator {
      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                 :    45619258 :         const_iterator(const T* ptr_) : ptr(ptr_) {}
      90                 :       97306 :         const_iterator(iterator x) : ptr(&(*x)) {}
      91 [ +  + ][ -  -  :    47041652 :         const T& operator*() const { return *ptr; }
          +  +  -  -  -  
                -  +  + ]
      92                 :             :         const T* operator->() const { return ptr; }
      93                 :       25617 :         const T& operator[](size_type pos) const { return ptr[pos]; }
      94   [ -  +  -  +  :   147466178 :         const_iterator& operator++() { ptr++; return *this; }
           -  + ][ +  -  
             -  +  #  # ]
      95                 :     2099912 :         const_iterator& operator--() { ptr--; return *this; }
      96         [ +  + ]:     2538375 :         const_iterator operator++(int) { const_iterator copy(*this); ++(*this); return copy; }
      97                 :             :         const_iterator operator--(int) { const_iterator copy(*this); --(*this); return copy; }
      98 [ +  - ][ +  +  :     4601180 :         difference_type friend operator-(const_iterator a, const_iterator b) { return (&(*a) - &(*b)); }
          -  -  +  -  +  
          -  +  -  +  -  
             +  -  +  + ]
           [ -  -  -  +  
           +  - ][ -  -  
             +  +  #  # ]
      99                 :      600583 :         const_iterator operator+(size_type n) const { return const_iterator(ptr + n); }
     100                 :             :         const_iterator friend operator+(size_type n, const_iterator x) { return x + n; }
     101         [ +  + ]:     1123197 :         const_iterator& operator+=(size_type n) { ptr += n; return *this; }
     102   [ +  -  +  - ]:         590 :         const_iterator operator-(size_type n) const { return const_iterator(ptr - n); }
     103                 :             :         const_iterator& operator-=(size_type n) { ptr -= n; return *this; }
     104         [ -  + ]:     2367224 :         bool operator==(const_iterator x) const { return ptr == x.ptr; }
     105         [ +  + ]:   155037526 :         bool operator!=(const_iterator x) const { return ptr != x.ptr; }
           [ +  +  +  + ]
           [ +  +  +  +  
                   +  + ]
     106         [ +  + ]:     2794150 :         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 [ +  + ][ +  +  :     2215218 :         bool operator<(const_iterator x) const { return ptr < x.ptr; }
          +  +  +  +  +  
           + ][ +  +  +  
                +  +  + ]
           [ +  +  +  + ]
     110                 :             :     };
     111                 :             : 
     112                 :             : private:
     113                 :             : #pragma pack(push, 1)
     114                 :             :     union direct_or_indirect {
     115                 :             :         char direct[sizeof(T) * N];
     116                 :             :         struct {
     117                 :             :             char* indirect;
     118                 :             :             size_type capacity;
     119                 :             :         } indirect_contents;
     120                 :             :     };
     121                 :             : #pragma pack(pop)
     122                 :             :     alignas(char*) direct_or_indirect _union = {};
     123                 :             :     size_type _size = 0;
     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                 :    20468660 :     T* direct_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.direct) + pos; }
     129                 :    48684268 :     const T* direct_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.direct) + pos; }
     130                 :     9727263 :     T* indirect_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.indirect_contents.indirect) + pos; }
     131                 :    13497585 :     const T* indirect_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.indirect_contents.indirect) + pos; }
     132                 :   252799055 :     bool is_direct() const { return _size <= N; }
     133                 :             : 
     134                 :    34837711 :     void change_capacity(size_type new_capacity) {
     135         [ +  + ]:    34837711 :         if (new_capacity <= N) {
     136         [ +  + ]:    33103330 :             if (!is_direct()) {
     137                 :       58099 :                 T* indirect = indirect_ptr(0);
     138                 :       58099 :                 T* src = indirect;
     139                 :       58099 :                 T* dst = direct_ptr(0);
     140                 :       58099 :                 memcpy(dst, src, size() * sizeof(T));
     141                 :       58099 :                 free(indirect);
     142                 :       58099 :                 _size -= N + 1;
     143                 :             :             }
     144                 :             :         } else {
     145         [ +  + ]:     1734381 :             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                 :       15131 :                 _union.indirect_contents.indirect = static_cast<char*>(realloc(_union.indirect_contents.indirect, ((size_t)sizeof(T)) * new_capacity));
     150         [ -  + ]:       15131 :                 assert(_union.indirect_contents.indirect);
     151                 :       15131 :                 _union.indirect_contents.capacity = new_capacity;
     152                 :             :             } else {
     153                 :     1719250 :                 char* new_indirect = static_cast<char*>(malloc(((size_t)sizeof(T)) * new_capacity));
     154         [ -  + ]:     1719250 :                 assert(new_indirect);
     155                 :     1719250 :                 T* src = direct_ptr(0);
     156                 :     1719250 :                 T* dst = reinterpret_cast<T*>(new_indirect);
     157                 :     1719250 :                 memcpy(dst, src, size() * sizeof(T));
     158                 :     1719250 :                 _union.indirect_contents.indirect = new_indirect;
     159                 :     1719250 :                 _union.indirect_contents.capacity = new_capacity;
     160                 :     1719250 :                 _size += N + 1;
     161                 :             :             }
     162                 :             :         }
     163                 :    34837711 :     }
     164                 :             : 
     165         [ +  + ]:    28263109 :     T* item_ptr(difference_type pos) { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
     166         [ +  + ]:    61482703 :     const T* item_ptr(difference_type pos) const { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
     167                 :             : 
     168                 :      256905 :     void fill(T* dst, ptrdiff_t count, const T& value = T{}) {
     169                 :      256905 :         std::fill_n(dst, count, value);
     170                 :             :     }
     171                 :             : 
     172                 :             :     template <std::input_iterator InputIterator>
     173                 :     7483816 :     void fill(T* dst, InputIterator first, InputIterator last) {
     174   [ +  +  +  +  :   183217084 :         while (first != last) {
             +  +  +  + ]
           [ +  +  #  #  
             #  #  #  # ]
           [ -  -  +  +  
           -  - ][ -  -  
          -  -  +  +  +  
             +  -  -  -  
           - ][ +  +  +  
          +  +  +  +  +  
          -  -  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
             #  #  #  #  
                      # ]
           [ +  +  -  - ]
           [ +  +  +  +  
          +  +  +  +  +  
          +  +  +  +  +  
          +  +  -  -  +  
          +  -  -  -  -  
             -  -  -  - ]
           [ -  -  -  -  
          +  +  +  +  +  
             +  +  +  +  
                      + ]
     175                 :   175788770 :             new(static_cast<void*>(dst)) T(*first);
     176                 :    21366613 :             ++dst;
     177                 :   175788770 :             ++first;
     178                 :             :         }
     179                 :             :     }
     180                 :             : 
     181                 :             : public:
     182                 :       87238 :     void assign(size_type n, const T& val) {
     183                 :       87238 :         clear();
     184         [ +  + ]:       87238 :         if (capacity() < n) {
     185                 :       48190 :             change_capacity(n);
     186                 :             :         }
     187                 :       87238 :         _size += n;
     188   [ +  +  +  + ]:      174476 :         fill(item_ptr(0), n, val);
     189                 :       87238 :     }
     190                 :             : 
     191                 :             :     template <std::input_iterator InputIterator>
     192                 :      351144 :     void assign(InputIterator first, InputIterator last) {
     193                 :      351144 :         size_type n = last - first;
     194                 :      351144 :         clear();
     195         [ +  + ]:      351144 :         if (capacity() < n) {
     196                 :      127288 :             change_capacity(n);
     197                 :             :         }
     198         [ +  + ]:      351144 :         _size += n;
     199         [ +  + ]:      406354 :         fill(item_ptr(0), first, last);
     200                 :      351144 :     }
     201                 :             : 
     202   [ +  -  +  - ]:    29326390 :     prevector() = default;
           [ +  -  +  -  
          +  -  +  -  +  
           -  +  - ][ +  
          -  +  -  +  -  
          +  -  +  -  +  
             -  -  -  #  
           # ][ +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
           +  - ][ +  - ]
           [ +  -  +  -  
          +  +  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
           #  #  # ][ +  
          -  +  -  +  -  
           +  - ][ +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
           #  #  # ][ +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  -  +  +  -  
          +  -  +  -  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
             #  #  #  #  
           # ][ -  -  +  
          -  +  -  +  -  
           +  - ][ +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
             -  +  -  +  
           - ][ +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
                -  +  - ]
     203                 :             : 
     204                 :             :     explicit prevector(size_type n) {
     205                 :             :         resize(n);
     206                 :             :     }
     207                 :             : 
     208                 :       60271 :     explicit prevector(size_type n, const T& val) {
     209                 :       60271 :         change_capacity(n);
     210                 :       60271 :         _size += n;
     211   [ +  -  +  - ]:      120542 :         fill(item_ptr(0), n, val);
     212                 :       60271 :     }
     213                 :             : 
     214                 :             :     template <std::input_iterator InputIterator>
     215                 :      647033 :     prevector(InputIterator first, InputIterator last) {
     216                 :      647033 :         size_type n = last - first;
     217                 :      647033 :         change_capacity(n);
     218         [ +  + ]:      647033 :         _size += n;
     219         [ +  + ]:      647325 :         fill(item_ptr(0), first, last);
     220                 :      647033 :     }
     221                 :             : 
     222                 :     5375233 :     prevector(const prevector<N, T, Size, Diff>& other) {
     223                 :     5375233 :         size_type n = other.size();
     224                 :     5375233 :         change_capacity(n);
     225                 :     5375233 :         _size += n;
     226                 :     5375233 :         fill(item_ptr(0), other.begin(),  other.end());
     227                 :     5375233 :     }
     228                 :             : 
     229                 :      812751 :     prevector(prevector<N, T, Size, Diff>&& other) noexcept
     230         [ +  - ]:      812751 :         : _union(std::move(other._union)), _size(other._size)
     231                 :             :     {
     232   [ +  -  -  -  :      719820 :         other._size = 0;
           +  - ][ +  + ]
           [ +  -  +  - ]
     233                 :             :     }
     234                 :             : 
     235                 :      349789 :     prevector& operator=(const prevector<N, T, Size, Diff>& other) {
     236         [ +  + ]:      349789 :         if (&other == this) {
     237                 :             :             return *this;
     238                 :             :         }
     239                 :      673510 :         assign(other.begin(), other.end());
     240                 :      336755 :         return *this;
     241                 :             :     }
     242                 :             : 
     243                 :     1548420 :     prevector& operator=(prevector<N, T, Size, Diff>&& other) noexcept {
     244         [ +  + ]:     1548420 :         if (!is_direct()) {
     245                 :       30992 :             free(_union.indirect_contents.indirect);
     246                 :             :         }
     247                 :     1548420 :         _union = std::move(other._union);
     248                 :     1548420 :         _size = other._size;
     249                 :     1548420 :         other._size = 0;
     250                 :     1548420 :         return *this;
     251                 :             :     }
     252                 :             : 
     253                 :   167089438 :     size_type size() const {
     254   [ +  +  +  +  :    57609824 :         return is_direct() ? _size : _size - N - 1;
           +  + ][ +  +  
          +  +  #  #  #  
          #  #  #  #  #  
           #  # ][ -  -  
          +  -  +  +  +  
          +  +  +  +  +  
          +  +  +  +  +  
           +  +  + ][ -  
          +  +  +  +  +  
             +  +  +  + ]
           [ -  -  -  -  
          -  +  -  -  -  
          -  -  -  -  -  
          -  -  -  -  -  
          -  -  -  -  +  
          -  -  -  -  -  
          -  -  -  +  +  
          -  -  -  -  -  
             -  -  -  -  
           - ][ -  -  +  
          +  -  +  -  -  
          -  -  -  +  -  
          -  -  -  -  +  
          -  -  -  -  -  
          -  -  -  -  -  
          -  -  #  #  #  
           # ][ #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
           # ][ -  -  -  
          -  -  -  -  -  
          -  -  -  -  -  
          -  -  +  -  +  
          -  -  -  -  -  
          -  -  -  -  -  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
           # ][ -  -  -  
          +  -  -  -  +  
          -  +  -  +  -  
          +  -  -  -  +  
          -  +  -  +  +  
          +  -  +  -  -  
          -  +  -  +  -  
          -  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  +  -  +  -  
          +  +  +  +  -  
          +  -  +  -  +  
          -  -  -  -  -  
          -  -  -  -  -  
          -  -  -  -  -  
          -  -  -  -  -  
           -  - ][ -  -  
             #  #  #  # ]
           [ -  +  +  +  
          +  +  +  -  +  
             +  +  +  +  
           + ][ -  +  -  
          -  +  +  -  +  
          +  +  +  +  +  
           +  +  + ][ +  
          +  +  +  +  +  
          +  +  +  +  +  
          +  -  +  +  +  
           +  + ][ -  +  
          -  -  +  +  +  
          +  +  +  +  +  
          +  +  -  -  +  
          +  +  +  +  +  
             +  +  +  + ]
           [ -  -  -  -  
          +  +  +  +  #  
          #  #  #  #  #  
           #  # ][ +  +  
          +  +  +  +  +  
          +  +  +  +  +  
          #  #  #  #  #  
          #  #  #  #  #  
             #  #  #  # ]
           [ +  +  +  +  
          +  +  +  +  +  
          +  +  +  +  +  
          +  +  +  +  +  
                +  +  + ]
     255                 :             :     }
     256                 :             : 
     257         [ +  + ]:    16933463 :     bool empty() const {
           [ +  +  +  + ]
           [ -  -  -  -  
          +  +  +  +  -  
          +  -  +  -  +  
          +  -  +  +  -  
           +  -  + ][ #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
             #  #  #  # ]
           [ +  +  -  +  
             +  +  +  + ]
           [ #  #  #  #  
           #  # ][ #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
             #  #  #  #  
           # ][ -  -  -  
          +  -  -  -  -  
          -  -  -  -  -  
          -  -  -  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  -  -  -  -  
          -  -  -  -  -  
          -  -  -  -  +  
          +  +  +  +  +  
          +  +  -  +  +  
          +  +  +  -  -  
                   -  - ]
     258         [ +  + ]:    16933463 :         return size() == 0;
           [ +  +  +  + ]
           [ -  -  -  -  
          +  +  +  -  -  
          +  -  +  +  -  
          +  -  +  +  -  
           +  +  - ][ #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
             #  #  #  # ]
           [ +  +  -  +  
             +  +  -  + ]
           [ #  #  #  #  
           #  # ][ #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
             #  #  #  #  
           # ][ -  -  +  
          -  -  -  -  -  
          -  -  -  -  -  
          -  -  -  +  -  
          -  +  +  -  -  
          +  -  +  -  +  
          -  -  -  -  -  
          -  -  -  -  -  
          -  -  -  -  +  
          +  +  +  +  +  
          +  +  -  +  +  
          +  +  +  -  -  
                   -  - ]
     259                 :             :     }
     260                 :             : 
     261   [ -  -  -  -  :    13465687 :     iterator begin() { return iterator(item_ptr(0)); }
          -  -  -  -  +  
          +  +  +  -  -  
          +  +  +  +  +  
          +  -  -  +  +  
          -  -  +  +  -  
          -  +  +  -  -  
          +  +  +  -  -  
             -  +  +  +  
           + ][ +  +  +  
          -  +  +  +  -  
          +  +  +  -  +  
             +  +  -  #  
           # ][ +  +  +  
          +  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
           # ][ +  +  +  
          -  +  +  +  +  
          #  #  #  #  #  
          #  #  #  #  #  
           #  # ][ +  +  
          +  +  +  +  +  
          +  +  +  +  +  
          +  +  +  +  +  
           + ][ -  +  +  
          -  -  +  +  -  
          -  +  +  -  -  
          +  +  -  -  +  
           +  - ][ -  +  
             #  #  #  # ]
           [ -  +  +  -  
                   +  - ]
     262   [ +  +  +  +  :    25497499 :     const_iterator begin() const { return const_iterator(item_ptr(0)); }
           +  + ][ +  +  
             +  +  #  # ]
           [ +  +  +  +  
          +  -  +  +  +  
           +  +  + ][ +  
          +  +  +  +  +  
             +  +  +  + ]
           [ +  +  #  #  
             #  #  #  # ]
           [ +  +  +  +  
          +  +  +  +  #  
           # ][ -  -  -  
          -  -  -  +  -  
          -  +  -  -  -  
           - ][ +  +  +  
          +  -  -  +  +  
          +  +  +  +  +  
             +  +  +  +  
           + ][ -  -  -  
          -  -  -  +  +  
          -  -  -  -  -  
          -  -  -  -  -  
           -  - ][ -  -  
          -  -  +  +  +  
          +  +  -  +  +  
          -  -  -  -  +  
          -  +  +  +  -  
          +  +  +  -  +  
          +  -  -  +  -  
             -  +  +  - ]
     263   [ +  +  +  + ]:    10364902 :     iterator end() { return iterator(item_ptr(size())); }
     264   [ +  +  +  + ]:    25085200 :     const_iterator end() const { return const_iterator(item_ptr(size())); }
     265                 :             : 
     266                 :     4714618 :     size_t capacity() const {
     267         [ +  + ]:     1047815 :         if (is_direct()) {
           [ -  -  -  + ]
           [ +  +  +  +  
           +  + ][ -  -  
          -  +  +  +  +  
             +  -  +  -  
                      - ]
     268                 :             :             return N;
     269                 :             :         } else {
     270                 :      193541 :             return _union.indirect_contents.capacity;
     271                 :             :         }
     272                 :             :     }
     273                 :             : 
     274   [ +  +  +  +  :     2367727 :     T& operator[](size_type pos) {
          +  +  +  +  +  
              + ][ -  + ]
           [ +  -  +  -  
          +  -  +  -  +  
           -  +  - ][ +  
          -  +  -  +  -  
          +  -  -  -  -  
          -  -  +  -  +  
          -  -  -  -  +  
                -  +  - ]
     275 [ +  + ][ -  +  :     6820768 :         return *item_ptr(pos);
          -  +  +  -  -  
           +  +  - ][ +  
          +  +  +  #  #  
           #  # ][ +  +  
          +  +  +  +  +  
          +  #  #  #  #  
             #  #  #  # ]
           [ -  -  -  -  
          -  +  +  -  -  
           +  +  - ][ +  
          -  +  -  +  -  
          +  -  +  -  +  
             -  +  -  +  
           - ][ +  -  -  
          +  +  -  -  +  
          +  -  -  +  +  
             -  #  #  #  
           # ][ -  +  +  
          -  +  +  +  +  
          +  +  +  +  +  
             +  +  +  +  
           - ][ +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  -  -  -  -  
          -  -  -  -  -  
          -  -  +  -  +  
          +  -  -  +  -  
          +  -  -  -  -  
          -  -  +  -  +  
          -  +  -  +  -  
          +  -  +  +  +  
                -  +  - ]
     276                 :             :     }
     277                 :             : 
     278         [ +  - ]:      494098 :     const T& operator[](size_type pos) const {
     279   [ +  +  +  -  :     1972222 :         return *item_ptr(pos);
          +  -  +  -  +  
           -  +  - ][ +  
          +  +  +  +  +  
          +  +  +  +  +  
          +  -  -  -  -  
          +  +  -  +  +  
          -  +  +  +  -  
          +  -  +  -  +  
          +  +  +  +  +  
          +  +  +  -  +  
          +  +  +  +  +  
                   -  + ]
           [ +  +  +  + ]
           [ -  +  +  +  
          -  -  -  -  -  
          -  -  -  -  -  
           -  - ][ +  -  
          +  -  +  +  +  
          +  +  +  +  -  
          +  +  +  +  +  
          -  +  +  +  -  
          +  +  +  -  +  
          +  +  -  +  +  
          +  -  -  +  -  
          -  +  -  +  +  
          +  -  +  +  +  
          +  +  -  +  +  
          +  +  +  -  +  
          +  +  +  +  -  
             +  +  +  - ]
           [ +  +  +  -  
          -  +  -  -  +  
          -  +  -  +  -  
          +  +  +  +  +  
          -  +  -  +  -  
          +  -  +  -  +  
          +  +  +  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
           - ][ +  +  +  
          +  +  +  +  +  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
                #  #  # ]
     280                 :             :     }
     281                 :             : 
     282         [ +  + ]:    28881126 :     void resize(size_type new_size) {
     283                 :    28881126 :         size_type cur_size = size();
     284         [ +  + ]:    28881126 :         if (cur_size == new_size) {
     285                 :             :             return;
     286                 :             :         }
     287         [ +  + ]:      280213 :         if (cur_size > new_size) {
     288         [ +  + ]:      373998 :             erase(item_ptr(new_size), end());
     289                 :      186999 :             return;
     290                 :             :         }
     291   [ +  +  +  + ]:       97182 :         if (new_size > capacity()) {
     292                 :       55198 :             change_capacity(new_size);
     293                 :             :         }
     294                 :       93214 :         ptrdiff_t increase = new_size - cur_size;
     295   [ +  +  +  - ]:      186428 :         fill(item_ptr(cur_size), increase);
     296                 :       93214 :         _size += increase;
     297                 :             :     }
     298                 :             : 
     299                 :        4127 :     void reserve(size_type new_capacity) {
     300   [ +  +  +  + ]:        6740 :         if (new_capacity > capacity()) {
     301                 :        1828 :             change_capacity(new_capacity);
     302                 :             :         }
     303                 :        4127 :     }
     304                 :             : 
     305         [ +  + ]:    28312878 :     void shrink_to_fit() {
     306                 :    28312878 :         change_capacity(size());
     307                 :    28312878 :     }
     308                 :             : 
     309                 :    28773221 :     void clear() {
     310                 :    28773221 :         resize(0);
     311                 :             :     }
     312                 :             : 
     313         [ +  + ]:     2979346 :     iterator insert(iterator pos, const T& value) {
     314         [ +  + ]:     2979346 :         size_type p = pos - begin();
     315         [ +  + ]:     2979346 :         size_type new_size = size() + 1;
     316         [ +  + ]:     2979346 :         if (capacity() < new_size) {
     317                 :        1621 :             change_capacity(new_size + (new_size >> 1));
     318                 :             :         }
     319         [ +  + ]:     2979346 :         T* ptr = item_ptr(p);
     320         [ +  + ]:     2979346 :         T* dst = ptr + 1;
     321                 :     2979346 :         memmove(dst, ptr, (size() - p) * sizeof(T));
     322                 :     2979346 :         _size++;
     323                 :     2979346 :         new(static_cast<void*>(ptr)) T(value);
     324                 :     2979346 :         return iterator(ptr);
     325                 :             :     }
     326                 :             : 
     327         [ +  + ]:       16182 :     void insert(iterator pos, size_type count, const T& value) {
     328         [ +  + ]:       16182 :         size_type p = pos - begin();
     329         [ +  + ]:       16182 :         size_type new_size = size() + count;
     330         [ +  + ]:       16182 :         if (capacity() < new_size) {
     331                 :         731 :             change_capacity(new_size + (new_size >> 1));
     332                 :             :         }
     333         [ +  + ]:       16182 :         T* ptr = item_ptr(p);
     334         [ +  + ]:       16182 :         T* dst = ptr + count;
     335         [ +  + ]:       16182 :         memmove(dst, ptr, (size() - p) * sizeof(T));
     336                 :       16182 :         _size += count;
     337   [ +  +  +  - ]:       32364 :         fill(item_ptr(p), count, value);
     338                 :       16182 :     }
     339                 :             : 
     340                 :             :     template <std::input_iterator InputIterator>
     341         [ +  + ]:     1124209 :     void insert(iterator pos, InputIterator first, InputIterator last) {
     342         [ +  + ]:     1124209 :         size_type p = pos - begin();
     343         [ +  + ]:     1124209 :         difference_type count = last - first;
     344         [ +  + ]:     1124209 :         size_type new_size = size() + count;
     345         [ +  + ]:     1124209 :         if (capacity() < new_size) {
     346                 :      201021 :             change_capacity(new_size + (new_size >> 1));
     347                 :             :         }
     348         [ +  + ]:     1124209 :         T* ptr = item_ptr(p);
     349         [ +  + ]:     1124209 :         T* dst = ptr + count;
     350                 :     1124209 :         memmove(dst, ptr, (size() - p) * sizeof(T));
     351                 :     1124209 :         _size += count;
     352                 :     1124209 :         fill(ptr, first, last);
     353                 :     1124209 :     }
     354                 :             : 
     355         [ +  + ]:       22877 :     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         [ +  + ]:       22877 :         if (capacity() < new_size) {
     359         [ +  - ]:        6009 :             change_capacity(new_size);
     360                 :        6009 :             _size += new_size - size();
     361                 :        6009 :             return;
     362                 :             :         }
     363         [ +  + ]:       16868 :         if (new_size < size()) {
     364         [ +  + ]:        6444 :             erase(item_ptr(new_size), end());
     365                 :             :         } else {
     366                 :       13646 :             _size += new_size - size();
     367                 :             :         }
     368                 :             :     }
     369                 :             : 
     370                 :       27725 :     iterator erase(iterator pos) {
     371                 :       27725 :         return erase(pos, pos + 1);
     372                 :             :     }
     373                 :             : 
     374                 :      244897 :     iterator erase(iterator first, iterator last) {
     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                 :      244897 :         iterator p = first;
     382                 :      244897 :         char* endp = (char*)&(*end());
     383                 :      244897 :         _size -= last - p;
     384                 :      244897 :         memmove(&(*first), &(*last), endp - ((char*)(&(*last))));
     385                 :      244897 :         return first;
     386                 :             :     }
     387                 :             : 
     388                 :             :     template<typename... Args>
     389         [ +  + ]:       32154 :     void emplace_back(Args&&... args) {
     390         [ +  + ]:       32154 :         size_type new_size = size() + 1;
     391         [ +  + ]:       32154 :         if (capacity() < new_size) {
     392                 :         410 :             change_capacity(new_size + (new_size >> 1));
     393                 :             :         }
     394         [ +  + ]:       32154 :         new(item_ptr(size())) T(std::forward<Args>(args)...);
     395                 :       32154 :         _size++;
     396                 :       32154 :     }
     397                 :             : 
     398                 :       32154 :     void push_back(const T& value) {
     399                 :       32154 :         emplace_back(value);
     400                 :       23799 :     }
     401                 :             : 
     402                 :        6706 :     void pop_back() {
     403                 :        6706 :         erase(end() - 1, end());
     404                 :        6706 :     }
     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   [ -  +  +  + ]:         878 :     const T& back() const {
     419   [ +  +  +  +  :        1653 :         return *item_ptr(size() - 1);
             -  +  +  - ]
     420                 :             :     }
     421                 :             : 
     422                 :       16515 :     void swap(prevector<N, T, Size, Diff>& other) noexcept
     423                 :             :     {
     424                 :       16515 :         std::swap(_union, other._union);
     425                 :       16515 :         std::swap(_size, other._size);
     426                 :             :     }
     427                 :             : 
     428                 :    37409455 :     ~prevector() {
     429         [ +  + ]:    37409455 :         if (!is_direct()) {
     430                 :     1630159 :             free(_union.indirect_contents.indirect);
     431                 :     1630159 :             _union.indirect_contents.indirect = nullptr;
     432                 :             :         }
     433                 :    37409455 :     }
     434                 :             : 
     435         [ +  + ]:      922074 :     bool operator==(const prevector<N, T, Size, Diff>& other) const {
     436   [ +  +  +  + ]:     1287876 :         if (other.size() != size()) {
     437                 :             :             return false;
     438                 :             :         }
     439         [ +  + ]:      922040 :         const_iterator b1 = begin();
     440                 :      922040 :         const_iterator b2 = other.begin();
     441                 :      922040 :         const_iterator e1 = end();
     442         [ +  + ]:    15024274 :         while (b1 != e1) {
     443         [ +  + ]:    14125675 :             if ((*b1) != (*b2)) {
     444                 :             :                 return false;
     445                 :             :             }
     446                 :    14102234 :             ++b1;
     447                 :    14102234 :             ++b2;
     448                 :             :         }
     449                 :             :         return true;
     450                 :             :     }
     451                 :             : 
     452                 :         922 :     bool operator!=(const prevector<N, T, Size, Diff>& other) const {
     453                 :         922 :         return !(*this == other);
     454                 :             :     }
     455                 :             : 
     456         [ +  + ]:     7397167 :     bool operator<(const prevector<N, T, Size, Diff>& other) const {
     457   [ +  +  +  + ]:     9170288 :         if (size() < other.size()) {
     458                 :             :             return true;
     459                 :             :         }
     460         [ +  + ]:     7394119 :         if (size() > other.size()) {
     461                 :             :             return false;
     462                 :             :         }
     463         [ +  + ]:     7393913 :         const_iterator b1 = begin();
     464                 :     7393913 :         const_iterator b2 = other.begin();
     465                 :     7393913 :         const_iterator e1 = end();
     466         [ +  + ]:    26547398 :         while (b1 != e1) {
     467         [ +  + ]:    26505152 :             if ((*b1) < (*b2)) {
     468                 :             :                 return true;
     469                 :             :             }
     470         [ +  + ]:    22440916 :             if ((*b2) < (*b1)) {
     471                 :             :                 return false;
     472                 :             :             }
     473                 :    19153485 :             ++b1;
     474                 :    19153485 :             ++b2;
     475                 :             :         }
     476                 :             :         return false;
     477                 :             :     }
     478                 :             : 
     479                 :     2204563 :     size_t allocated_memory() const {
     480   [ +  +  +  + ]:     2204563 :         if (is_direct()) {
           [ -  +  +  +  
           -  + ][ #  # ]
           [ +  +  +  +  
          +  +  +  +  +  
          +  +  +  +  +  
          +  -  +  +  +  
             +  +  +  -  
                      - ]
     481                 :             :             return 0;
     482                 :             :         } else {
     483   [ +  -  +  - ]:      999455 :             return ((size_t)(sizeof(T))) * _union.indirect_contents.capacity;
           [ -  -  +  -  
           -  - ][ #  # ]
           [ +  -  +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  +  
             -  +  -  -  
                      - ]
     484                 :             :         }
     485                 :             :     }
     486                 :             : 
     487   [ +  +  #  #  :       80774 :     value_type* data() {
                   #  # ]
           [ +  +  +  + ]
           [ +  -  -  -  
             +  +  +  - ]
           [ +  +  +  +  
          +  +  +  +  -  
           +  -  + ][ +  
          +  -  +  -  +  
          #  #  #  #  #  
           # ][ +  -  -  
          +  -  +  +  -  
          +  -  -  +  -  
          +  -  +  -  +  
           -  + ][ +  -  
          -  -  -  -  -  
          -  -  -  -  -  
          -  -  -  -  +  
          -  -  -  -  -  
          -  -  -  -  -  
             -  -  -  -  
           - ][ -  +  -  
          +  -  +  -  -  
          -  -  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
          #  #  #  #  #  
             #  #  #  # ]
     488   [ +  +  #  #  :       80773 :         return item_ptr(0);
                   #  # ]
           [ +  +  +  + ]
           [ +  +  +  +  
          +  +  +  +  +  
           +  +  + ][ +  
          +  +  -  +  -  
          #  #  #  #  #  
           # ][ -  +  +  
          -  +  -  +  -  
          -  +  +  -  -  
          +  +  -  -  +  
           +  - ][ -  +  
          -  -  -  -  -  
          -  -  +  -  -  
             -  -  -  - ]
           [ -  +  -  +  
          -  +  -  -  -  
          -  #  #  #  #  
                   #  # ]
     489                 :             :     }
     490                 :             : 
     491   [ +  +  #  #  :    16135061 :     const value_type* data() const {
             #  #  #  # ]
           [ +  +  +  +  
             +  +  +  + ]
           [ +  +  +  + ]
           [ -  -  +  +  
          -  -  -  -  -  
           -  #  # ][ #  
          #  #  #  #  #  
          #  #  #  #  #  
           # ][ #  #  #  
          #  #  #  #  #  
           #  # ][ +  -  
          +  -  +  -  +  
          -  +  -  +  -  
          +  -  +  -  -  
          +  -  +  +  +  
          +  +  +  +  +  
          -  +  -  -  -  
             -  -  -  - ]
     492         [ +  + ]:    16135320 :         return item_ptr(0);
           [ +  +  +  + ]
           [ +  -  +  +  
             +  +  +  + ]
           [ +  -  -  -  
           -  + ][ -  +  
          -  +  -  +  -  
          +  -  +  +  -  
          +  -  +  +  +  
          +  +  +  +  +  
                   +  + ]
     493                 :             :     }
     494                 :             : };
     495                 :             : 
     496                 :             : #endif // BITCOIN_PREVECTOR_H
        

Generated by: LCOV version 2.0-1