LCOV - code coverage report
Current view: top level - src/util - bitdeque.h (source / functions) Hit Total Coverage
Test: fuzz_coverage.info Lines: 0 231 0.0 %
Date: 2023-11-06 23:13:05 Functions: 0 98 0.0 %
Branches: 0 102 0.0 %

           Branch data     Line data    Source code
       1                 :            : // Copyright (c) 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_UTIL_BITDEQUE_H
       6                 :            : #define BITCOIN_UTIL_BITDEQUE_H
       7                 :            : 
       8                 :            : #include <bitset>
       9                 :            : #include <cstddef>
      10                 :            : #include <deque>
      11                 :            : #include <limits>
      12                 :            : #include <stdexcept>
      13                 :            : #include <tuple>
      14                 :            : 
      15                 :            : /** Class that mimics std::deque<bool>, but with std::vector<bool>'s bit packing.
      16                 :            :  *
      17                 :            :  * BlobSize selects the (minimum) number of bits that are allocated at once.
      18                 :            :  * Larger values reduce the asymptotic memory usage overhead, at the cost of
      19                 :            :  * needing larger up-front allocations. The default is 4096 bytes.
      20                 :            :  */
      21                 :            : template<int BlobSize = 4096 * 8>
      22                 :          0 : class bitdeque
      23                 :            : {
      24                 :            :     // Internal definitions
      25                 :            :     using word_type = std::bitset<BlobSize>;
      26                 :            :     using deque_type = std::deque<word_type>;
      27                 :            :     static_assert(BlobSize > 0);
      28                 :            :     static constexpr int BITS_PER_WORD = BlobSize;
      29                 :            : 
      30                 :            :     // Forward and friend declarations of iterator types.
      31                 :            :     template<bool Const> class Iterator;
      32                 :            :     template<bool Const> friend class Iterator;
      33                 :            : 
      34                 :            :     /** Iterator to a bitdeque element, const or not. */
      35                 :            :     template<bool Const>
      36                 :            :     class Iterator
      37                 :            :     {
      38                 :            :         using deque_iterator = std::conditional_t<Const, typename deque_type::const_iterator, typename deque_type::iterator>;
      39                 :            : 
      40                 :            :         deque_iterator m_it;
      41                 :            :         int m_bitpos{0};
      42                 :          0 :         Iterator(const deque_iterator& it, int bitpos) : m_it(it), m_bitpos(bitpos) {}
      43                 :            :         friend class bitdeque;
      44                 :            : 
      45                 :            :     public:
      46                 :            :         using iterator_category = std::random_access_iterator_tag;
      47                 :            :         using value_type = bool;
      48                 :            :         using pointer = void;
      49                 :            :         using const_pointer = void;
      50                 :            :         using reference = std::conditional_t<Const, bool, typename word_type::reference>;
      51                 :            :         using const_reference = bool;
      52                 :            :         using difference_type = std::ptrdiff_t;
      53                 :            : 
      54                 :            :         /** Default constructor. */
      55                 :            :         Iterator() = default;
      56                 :            : 
      57                 :            :         /** Default copy constructor. */
      58                 :          0 :         Iterator(const Iterator&) = default;
      59                 :            : 
      60                 :            :         /** Conversion from non-const to const iterator. */
      61                 :            :         template<bool ConstArg = Const, typename = std::enable_if_t<Const && ConstArg>>
      62                 :          0 :         Iterator(const Iterator<false>& x) : m_it(x.m_it), m_bitpos(x.m_bitpos) {}
      63                 :            : 
      64                 :          0 :         Iterator& operator+=(difference_type dist)
      65                 :            :         {
      66 [ #  # ][ #  # ]:          0 :             if (dist > 0) {
      67 [ #  # ][ #  # ]:          0 :                 if (dist + m_bitpos >= BITS_PER_WORD) {
      68                 :          0 :                     ++m_it;
      69                 :          0 :                     dist -= BITS_PER_WORD - m_bitpos;
      70                 :          0 :                     m_bitpos = 0;
      71                 :          0 :                 }
      72                 :          0 :                 auto jump = dist / BITS_PER_WORD;
      73                 :          0 :                 m_it += jump;
      74                 :          0 :                 m_bitpos += dist - jump * BITS_PER_WORD;
      75 [ #  # ][ #  # ]:          0 :             } else if (dist < 0) {
      76                 :          0 :                 dist = -dist;
      77 [ #  # ][ #  # ]:          0 :                 if (dist > m_bitpos) {
      78                 :          0 :                     --m_it;
      79                 :          0 :                     dist -= m_bitpos + 1;
      80                 :          0 :                     m_bitpos = BITS_PER_WORD - 1;
      81                 :          0 :                 }
      82                 :          0 :                 auto jump = dist / BITS_PER_WORD;
      83                 :          0 :                 m_it -= jump;
      84                 :          0 :                 m_bitpos -= dist - jump * BITS_PER_WORD;
      85                 :          0 :             }
      86                 :          0 :             return *this;
      87                 :            :         }
      88                 :            : 
      89                 :          0 :         friend difference_type operator-(const Iterator& x, const Iterator& y)
      90                 :            :         {
      91                 :          0 :             return BITS_PER_WORD * (x.m_it - y.m_it) + x.m_bitpos - y.m_bitpos;
      92                 :            :         }
      93                 :            : 
      94                 :            :         Iterator& operator=(const Iterator&) = default;
      95                 :          0 :         Iterator& operator-=(difference_type dist) { return operator+=(-dist); }
      96         [ #  # ]:          0 :         Iterator& operator++() { ++m_bitpos; if (m_bitpos == BITS_PER_WORD) { m_bitpos = 0; ++m_it; }; return *this; }
      97                 :          0 :         Iterator operator++(int) { auto ret{*this}; operator++(); return ret; }
      98         [ #  # ]:          0 :         Iterator& operator--() { if (m_bitpos == 0) { m_bitpos = BITS_PER_WORD; --m_it; }; --m_bitpos; return *this; }
      99                 :            :         Iterator operator--(int) { auto ret{*this}; operator--(); return ret; }
     100                 :          0 :         friend Iterator operator+(Iterator x, difference_type dist) { x += dist; return x; }
     101                 :            :         friend Iterator operator+(difference_type dist, Iterator x) { x += dist; return x; }
     102                 :          0 :         friend Iterator operator-(Iterator x, difference_type dist) { x -= dist; return x; }
     103                 :            :         friend bool operator<(const Iterator& x, const Iterator& y) { return std::tie(x.m_it, x.m_bitpos) < std::tie(y.m_it, y.m_bitpos); }
     104                 :            :         friend bool operator>(const Iterator& x, const Iterator& y) { return std::tie(x.m_it, x.m_bitpos) > std::tie(y.m_it, y.m_bitpos); }
     105                 :            :         friend bool operator<=(const Iterator& x, const Iterator& y) { return std::tie(x.m_it, x.m_bitpos) <= std::tie(y.m_it, y.m_bitpos); }
     106                 :            :         friend bool operator>=(const Iterator& x, const Iterator& y) { return std::tie(x.m_it, x.m_bitpos) >= std::tie(y.m_it, y.m_bitpos); }
     107 [ #  # ][ #  # ]:          0 :         friend bool operator==(const Iterator& x, const Iterator& y) { return x.m_it == y.m_it && x.m_bitpos == y.m_bitpos; }
     108         [ #  # ]:          0 :         friend bool operator!=(const Iterator& x, const Iterator& y) { return x.m_it != y.m_it || x.m_bitpos != y.m_bitpos; }
     109                 :          0 :         reference operator*() const { return (*m_it)[m_bitpos]; }
     110                 :          0 :         reference operator[](difference_type pos) const { return *(*this + pos); }
     111                 :            :     };
     112                 :            : 
     113                 :            : public:
     114                 :            :     using value_type = bool;
     115                 :            :     using size_type = std::size_t;
     116                 :            :     using difference_type = typename deque_type::difference_type;
     117                 :            :     using reference = typename word_type::reference;
     118                 :            :     using const_reference = bool;
     119                 :            :     using iterator = Iterator<false>;
     120                 :            :     using const_iterator = Iterator<true>;
     121                 :            :     using pointer = void;
     122                 :            :     using const_pointer = void;
     123                 :            :     using reverse_iterator = std::reverse_iterator<iterator>;
     124                 :            :     using const_reverse_iterator = std::reverse_iterator<const_iterator>;
     125                 :            : 
     126                 :            : private:
     127                 :            :     /** Deque of bitsets storing the actual bit data. */
     128                 :            :     deque_type m_deque;
     129                 :            : 
     130                 :            :     /** Number of unused bits at the front of m_deque.front(). */
     131                 :            :     int m_pad_begin;
     132                 :            : 
     133                 :            :     /** Number of unused bits at the back of m_deque.back(). */
     134                 :            :     int m_pad_end;
     135                 :            : 
     136                 :            :     /** Shrink the container by n bits, removing from the end. */
     137                 :          0 :     void erase_back(size_type n)
     138                 :            :     {
     139         [ #  # ]:          0 :         if (n >= static_cast<size_type>(BITS_PER_WORD - m_pad_end)) {
     140                 :          0 :             n -= BITS_PER_WORD - m_pad_end;
     141                 :          0 :             m_pad_end = 0;
     142                 :          0 :             m_deque.erase(m_deque.end() - 1 - (n / BITS_PER_WORD), m_deque.end());
     143                 :          0 :             n %= BITS_PER_WORD;
     144                 :          0 :         }
     145         [ #  # ]:          0 :         if (n) {
     146                 :          0 :             auto& last = m_deque.back();
     147         [ #  # ]:          0 :             while (n) {
     148                 :          0 :                 last.reset(BITS_PER_WORD - 1 - m_pad_end);
     149                 :          0 :                 ++m_pad_end;
     150                 :          0 :                 --n;
     151                 :            :             }
     152                 :          0 :         }
     153                 :          0 :     }
     154                 :            : 
     155                 :            :     /** Extend the container by n bits, adding at the end. */
     156                 :          0 :     void extend_back(size_type n)
     157                 :            :     {
     158         [ #  # ]:          0 :         if (n > static_cast<size_type>(m_pad_end)) {
     159                 :          0 :             n -= m_pad_end + 1;
     160                 :          0 :             m_pad_end = BITS_PER_WORD - 1;
     161                 :          0 :             m_deque.insert(m_deque.end(), 1 + (n / BITS_PER_WORD), {});
     162                 :          0 :             n %= BITS_PER_WORD;
     163                 :          0 :         }
     164                 :          0 :         m_pad_end -= n;
     165                 :          0 :     }
     166                 :            : 
     167                 :            :     /** Shrink the container by n bits, removing from the beginning. */
     168                 :          0 :     void erase_front(size_type n)
     169                 :            :     {
     170         [ #  # ]:          0 :         if (n >= static_cast<size_type>(BITS_PER_WORD - m_pad_begin)) {
     171                 :          0 :             n -= BITS_PER_WORD - m_pad_begin;
     172                 :          0 :             m_pad_begin = 0;
     173                 :          0 :             m_deque.erase(m_deque.begin(), m_deque.begin() + 1 + (n / BITS_PER_WORD));
     174                 :          0 :             n %= BITS_PER_WORD;
     175                 :          0 :         }
     176         [ #  # ]:          0 :         if (n) {
     177                 :          0 :             auto& first = m_deque.front();
     178         [ #  # ]:          0 :             while (n) {
     179                 :          0 :                 first.reset(m_pad_begin);
     180                 :          0 :                 ++m_pad_begin;
     181                 :          0 :                 --n;
     182                 :            :             }
     183                 :          0 :         }
     184                 :          0 :     }
     185                 :            : 
     186                 :            :     /** Extend the container by n bits, adding at the beginning. */
     187                 :          0 :     void extend_front(size_type n)
     188                 :            :     {
     189         [ #  # ]:          0 :         if (n > static_cast<size_type>(m_pad_begin)) {
     190                 :          0 :             n -= m_pad_begin + 1;
     191                 :          0 :             m_pad_begin = BITS_PER_WORD - 1;
     192                 :          0 :             m_deque.insert(m_deque.begin(), 1 + (n / BITS_PER_WORD), {});
     193                 :          0 :             n %= BITS_PER_WORD;
     194                 :          0 :         }
     195                 :          0 :         m_pad_begin -= n;
     196                 :          0 :     }
     197                 :            : 
     198                 :            :     /** Insert a sequence of falses anywhere in the container. */
     199                 :          0 :     void insert_zeroes(size_type before, size_type count)
     200                 :            :     {
     201                 :          0 :         size_type after = size() - before;
     202         [ #  # ]:          0 :         if (before < after) {
     203                 :          0 :             extend_front(count);
     204                 :          0 :             std::move(begin() + count, begin() + count + before, begin());
     205                 :          0 :         } else {
     206                 :          0 :             extend_back(count);
     207                 :          0 :             std::move_backward(begin() + before, begin() + before + after, end());
     208                 :            :         }
     209                 :          0 :     }
     210                 :            : 
     211                 :            : public:
     212                 :            :     /** Construct an empty container. */
     213                 :          0 :     explicit bitdeque() : m_pad_begin{0}, m_pad_end{0} {}
     214                 :            : 
     215                 :            :     /** Set the container equal to count times the value of val. */
     216                 :          0 :     void assign(size_type count, bool val)
     217                 :            :     {
     218                 :          0 :         m_deque.clear();
     219                 :          0 :         m_deque.resize((count + BITS_PER_WORD - 1) / BITS_PER_WORD);
     220                 :          0 :         m_pad_begin = 0;
     221                 :          0 :         m_pad_end = 0;
     222         [ #  # ]:          0 :         if (val) {
     223         [ #  # ]:          0 :             for (auto& elem : m_deque) elem.flip();
     224                 :          0 :         }
     225         [ #  # ]:          0 :         if (count % BITS_PER_WORD) {
     226                 :          0 :             erase_back(BITS_PER_WORD - (count % BITS_PER_WORD));
     227                 :          0 :         }
     228                 :          0 :     }
     229                 :            : 
     230                 :            :     /** Construct a container containing count times the value of val. */
     231         [ #  # ]:          0 :     bitdeque(size_type count, bool val) { assign(count, val); }
     232                 :            : 
     233                 :            :     /** Construct a container containing count false values. */
     234         [ #  # ]:          0 :     explicit bitdeque(size_t count) { assign(count, false); }
     235                 :            : 
     236                 :            :     /** Copy constructor. */
     237                 :            :     bitdeque(const bitdeque&) = default;
     238                 :            : 
     239                 :            :     /** Move constructor. */
     240                 :            :     bitdeque(bitdeque&&) noexcept = default;
     241                 :            : 
     242                 :            :     /** Copy assignment operator. */
     243                 :          0 :     bitdeque& operator=(const bitdeque& other) = default;
     244                 :            : 
     245                 :            :     /** Move assignment operator. */
     246                 :          0 :     bitdeque& operator=(bitdeque&& other) noexcept = default;
     247                 :            : 
     248                 :            :     // Iterator functions.
     249         [ #  # ]:          0 :     iterator begin() noexcept { return {m_deque.begin(), m_pad_begin}; }
     250 [ #  # ][ #  # ]:          0 :     iterator end() noexcept { return iterator{m_deque.end(), 0} - m_pad_end; }
     251         [ #  # ]:          0 :     const_iterator begin() const noexcept { return const_iterator{m_deque.cbegin(), m_pad_begin}; }
     252         [ #  # ]:          0 :     const_iterator cbegin() const noexcept { return const_iterator{m_deque.cbegin(), m_pad_begin}; }
     253 [ #  # ][ #  # ]:          0 :     const_iterator end() const noexcept { return const_iterator{m_deque.cend(), 0} - m_pad_end; }
     254 [ #  # ][ #  # ]:          0 :     const_iterator cend() const noexcept { return const_iterator{m_deque.cend(), 0} - m_pad_end; }
     255                 :          0 :     reverse_iterator rbegin() noexcept { return reverse_iterator{end()}; }
     256                 :          0 :     reverse_iterator rend() noexcept { return reverse_iterator{begin()}; }
     257                 :          0 :     const_reverse_iterator rbegin() const noexcept { return const_reverse_iterator{cend()}; }
     258                 :          0 :     const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator{cend()}; }
     259                 :          0 :     const_reverse_iterator rend() const noexcept { return const_reverse_iterator{cbegin()}; }
     260                 :          0 :     const_reverse_iterator crend() const noexcept { return const_reverse_iterator{cbegin()}; }
     261                 :            : 
     262                 :            :     /** Count the number of bits in the container. */
     263                 :          0 :     size_type size() const noexcept { return m_deque.size() * BITS_PER_WORD - m_pad_begin - m_pad_end; }
     264                 :            : 
     265                 :            :     /** Determine whether the container is empty. */
     266                 :          0 :     bool empty() const noexcept
     267                 :            :     {
     268 [ #  # ][ #  # ]:          0 :         return m_deque.size() == 0 || (m_deque.size() == 1 && (m_pad_begin + m_pad_end == BITS_PER_WORD));
     269                 :            :     }
     270                 :            : 
     271                 :            :     /** Return the maximum size of the container. */
     272                 :          0 :     size_type max_size() const noexcept
     273                 :            :     {
     274         [ #  # ]:          0 :         if (m_deque.max_size() < std::numeric_limits<difference_type>::max() / BITS_PER_WORD) {
     275                 :          0 :             return m_deque.max_size() * BITS_PER_WORD;
     276                 :            :         } else {
     277                 :          0 :             return std::numeric_limits<difference_type>::max();
     278                 :            :         }
     279                 :          0 :     }
     280                 :            : 
     281                 :            :     /** Set the container equal to the bits in [first,last). */
     282                 :            :     template<typename It>
     283                 :          0 :     void assign(It first, It last)
     284                 :            :     {
     285                 :          0 :         size_type count = std::distance(first, last);
     286                 :          0 :         assign(count, false);
     287                 :          0 :         auto it = begin();
     288         [ #  # ]:          0 :         while (first != last) {
     289                 :          0 :             *(it++) = *(first++);
     290                 :            :         }
     291                 :          0 :     }
     292                 :            : 
     293                 :            :     /** Set the container equal to the bits in ilist. */
     294                 :          0 :     void assign(std::initializer_list<bool> ilist)
     295                 :            :     {
     296                 :          0 :         assign(ilist.size(), false);
     297                 :          0 :         auto it = begin();
     298                 :          0 :         auto init = ilist.begin();
     299         [ #  # ]:          0 :         while (init != ilist.end()) {
     300                 :          0 :             *(it++) = *(init++);
     301                 :            :         }
     302                 :          0 :     }
     303                 :            : 
     304                 :            :     /** Set the container equal to the bits in ilist. */
     305                 :          0 :     bitdeque& operator=(std::initializer_list<bool> ilist)
     306                 :            :     {
     307                 :          0 :         assign(ilist);
     308                 :          0 :         return *this;
     309                 :            :     }
     310                 :            : 
     311                 :            :     /** Construct a container containing the bits in [first,last). */
     312                 :            :     template<typename It>
     313         [ #  # ]:          0 :     bitdeque(It first, It last) { assign(first, last); }
     314                 :            : 
     315                 :            :     /** Construct a container containing the bits in ilist. */
     316         [ #  # ]:          0 :     bitdeque(std::initializer_list<bool> ilist) { assign(ilist); }
     317                 :            : 
     318                 :            :     // Access an element of the container, with bounds checking.
     319                 :          0 :     reference at(size_type position)
     320                 :            :     {
     321 [ #  # ][ #  # ]:          0 :         if (position >= size()) throw std::out_of_range("bitdeque::at() out of range");
     322                 :          0 :         return begin()[position];
     323                 :          0 :     }
     324                 :          0 :     const_reference at(size_type position) const
     325                 :            :     {
     326 [ #  # ][ #  # ]:          0 :         if (position >= size()) throw std::out_of_range("bitdeque::at() out of range");
     327                 :          0 :         return cbegin()[position];
     328                 :          0 :     }
     329                 :            : 
     330                 :            :     // Access elements of the container without bounds checking.
     331                 :          0 :     reference operator[](size_type position) { return begin()[position]; }
     332                 :            :     const_reference operator[](size_type position) const { return cbegin()[position]; }
     333                 :          0 :     reference front() { return *begin(); }
     334                 :          0 :     const_reference front() const { return *cbegin(); }
     335                 :          0 :     reference back() { return end()[-1]; }
     336                 :          0 :     const_reference back() const { return cend()[-1]; }
     337                 :            : 
     338                 :            :     /** Release unused memory. */
     339                 :            :     void shrink_to_fit()
     340                 :            :     {
     341                 :            :         m_deque.shrink_to_fit();
     342                 :            :     }
     343                 :            : 
     344                 :            :     /** Empty the container. */
     345                 :          0 :     void clear() noexcept
     346                 :            :     {
     347                 :          0 :         m_deque.clear();
     348                 :          0 :         m_pad_begin = m_pad_end = 0;
     349                 :          0 :     }
     350                 :            : 
     351                 :            :     // Append an element to the container.
     352                 :          0 :     void push_back(bool val)
     353                 :            :     {
     354                 :          0 :         extend_back(1);
     355                 :          0 :         back() = val;
     356                 :          0 :     }
     357                 :            :     reference emplace_back(bool val)
     358                 :            :     {
     359                 :            :         extend_back(1);
     360                 :            :         auto ref = back();
     361                 :            :         ref = val;
     362                 :            :         return ref;
     363                 :            :     }
     364                 :            : 
     365                 :            :     // Prepend an element to the container.
     366                 :          0 :     void push_front(bool val)
     367                 :            :     {
     368                 :          0 :         extend_front(1);
     369                 :          0 :         front() = val;
     370                 :          0 :     }
     371                 :            :     reference emplace_front(bool val)
     372                 :            :     {
     373                 :            :         extend_front(1);
     374                 :            :         auto ref = front();
     375                 :            :         ref = val;
     376                 :            :         return ref;
     377                 :            :     }
     378                 :            : 
     379                 :            :     // Remove the last element from the container.
     380                 :          0 :     void pop_back()
     381                 :            :     {
     382                 :          0 :         erase_back(1);
     383                 :          0 :     }
     384                 :            : 
     385                 :            :     // Remove the first element from the container.
     386                 :          0 :     void pop_front()
     387                 :            :     {
     388                 :          0 :         erase_front(1);
     389                 :          0 :     }
     390                 :            : 
     391                 :            :     /** Resize the container. */
     392                 :          0 :     void resize(size_type n)
     393                 :            :     {
     394         [ #  # ]:          0 :         if (n < size()) {
     395                 :          0 :             erase_back(size() - n);
     396                 :          0 :         } else {
     397                 :          0 :             extend_back(n - size());
     398                 :            :         }
     399                 :          0 :     }
     400                 :            : 
     401                 :            :     // Swap two containers.
     402                 :          0 :     void swap(bitdeque& other) noexcept
     403                 :            :     {
     404                 :          0 :         std::swap(m_deque, other.m_deque);
     405                 :          0 :         std::swap(m_pad_begin, other.m_pad_begin);
     406                 :          0 :         std::swap(m_pad_end, other.m_pad_end);
     407                 :          0 :     }
     408                 :          0 :     friend void swap(bitdeque& b1, bitdeque& b2) noexcept { b1.swap(b2); }
     409                 :            : 
     410                 :            :     // Erase elements from the container.
     411                 :          0 :     iterator erase(const_iterator first, const_iterator last)
     412                 :            :     {
     413                 :          0 :         size_type before = std::distance(cbegin(), first);
     414                 :          0 :         size_type dist = std::distance(first, last);
     415                 :          0 :         size_type after = std::distance(last, cend());
     416         [ #  # ]:          0 :         if (before < after) {
     417                 :          0 :             std::move_backward(begin(), begin() + before, end() - after);
     418                 :          0 :             erase_front(dist);
     419                 :          0 :             return begin() + before;
     420                 :            :         } else {
     421                 :          0 :             std::move(end() - after, end(), begin() + before);
     422                 :          0 :             erase_back(dist);
     423                 :          0 :             return end() - after;
     424                 :            :         }
     425                 :          0 :     }
     426                 :            : 
     427                 :            :     iterator erase(iterator first, iterator last) { return erase(const_iterator{first}, const_iterator{last}); }
     428                 :          0 :     iterator erase(const_iterator pos) { return erase(pos, pos + 1); }
     429                 :            :     iterator erase(iterator pos) { return erase(const_iterator{pos}, const_iterator{pos} + 1); }
     430                 :            : 
     431                 :            :     // Insert elements into the container.
     432                 :          0 :     iterator insert(const_iterator pos, bool val)
     433                 :            :     {
     434                 :          0 :         size_type before = pos - cbegin();
     435                 :          0 :         insert_zeroes(before, 1);
     436                 :          0 :         auto it = begin() + before;
     437                 :          0 :         *it = val;
     438                 :          0 :         return it;
     439                 :            :     }
     440                 :            : 
     441                 :          0 :     iterator emplace(const_iterator pos, bool val) { return insert(pos, val); }
     442                 :            : 
     443                 :          0 :     iterator insert(const_iterator pos, size_type count, bool val)
     444                 :            :     {
     445                 :          0 :         size_type before = pos - cbegin();
     446                 :          0 :         insert_zeroes(before, count);
     447                 :          0 :         auto it_begin = begin() + before;
     448                 :          0 :         auto it = it_begin;
     449                 :          0 :         auto it_end = it + count;
     450         [ #  # ]:          0 :         while (it != it_end) *(it++) = val;
     451                 :          0 :         return it_begin;
     452                 :            :     }
     453                 :            : 
     454                 :            :     template<typename It>
     455                 :          0 :     iterator insert(const_iterator pos, It first, It last)
     456                 :            :     {
     457                 :          0 :         size_type before = pos - cbegin();
     458                 :          0 :         size_type count = std::distance(first, last);
     459                 :          0 :         insert_zeroes(before, count);
     460                 :          0 :         auto it_begin = begin() + before;
     461                 :          0 :         auto it = it_begin;
     462         [ #  # ]:          0 :         while (first != last) {
     463                 :          0 :             *(it++) = *(first++);
     464                 :            :         }
     465                 :          0 :         return it_begin;
     466                 :            :     }
     467                 :            : };
     468                 :            : 
     469                 :            : #endif // BITCOIN_UTIL_BITDEQUE_H

Generated by: LCOV version 1.14