LCOV - code coverage report
Current view: top level - src - prevector.h (source / functions) Hit Total Coverage
Test: fuzz_coverage.info Lines: 176 287 61.3 %
Date: 2024-01-03 14:57:27 Functions: 62 237 26.2 %
Branches: 41 140 29.3 %

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

Generated by: LCOV version 1.14