/Users/eugenesiegel/btc/bitcoin/src/util/bitdeque.h

Source (jump to first uncovered line)
// Copyright (c) 2022 The Bitcoin Core developers
// Distributed under the MIT software license, see the accompanying
// file COPYING or http://www.opensource.org/licenses/mit-license.php.

#ifndef BITCOIN_UTIL_BITDEQUE_H
#define BITCOIN_UTIL_BITDEQUE_H

#include <bitset>
#include <cstddef>
#include <deque>
#include <limits>
#include <stdexcept>
#include <tuple>

/** Class that mimics std::deque<bool>, but with std::vector<bool>'s bit packing.
 *
 * BITS_PER_WORD selects the (minimum) number of bits that are allocated at once.
 * Larger values reduce the asymptotic memory usage overhead, at the cost of
 * needing larger up-front allocations. The default is 4096 bytes.
 */
template<int BITS_PER_WORD = 4096 * 8>
class bitdeque
{
    // Internal definitions
    using word_type = std::bitset<BITS_PER_WORD>;
    using deque_type = std::deque<word_type>;
    static_assert(BITS_PER_WORD > 0);

    // Forward and friend declarations of iterator types.
    template<bool Const> class Iterator;
    template<bool Const> friend class Iterator;

    /** Iterator to a bitdeque element, const or not. */
    template<bool Const>
    class Iterator
    {
        using deque_iterator = std::conditional_t<Const, typename deque_type::const_iterator, typename deque_type::iterator>;

        deque_iterator m_it;
        int m_bitpos{0};
        Iterator(const deque_iterator& it, int bitpos) : m_it(it), m_bitpos(bitpos) {}
        friend class bitdeque;

    public:
        using iterator_category = std::random_access_iterator_tag;
        using value_type = bool;
        using pointer = void;
        using const_pointer = void;
        using reference = std::conditional_t<Const, bool, typename word_type::reference>;
        using const_reference = bool;
        using difference_type = std::ptrdiff_t;

        /** Default constructor. */
        Iterator() = default;

        /** Default copy constructor. */
        Iterator(const Iterator&) = default;

        /** Conversion from non-const to const iterator. */
        template<bool ConstArg = Const, typename = std::enable_if_t<Const && ConstArg>>
        Iterator(const Iterator<false>& x) : m_it(x.m_it), m_bitpos(x.m_bitpos) {}

        Iterator& operator+=(difference_type dist)
        {
            if (dist > 0) {
                if (dist + m_bitpos >= BITS_PER_WORD) {
                    ++m_it;
                    dist -= BITS_PER_WORD - m_bitpos;
                    m_bitpos = 0;
                }
                auto jump = dist / BITS_PER_WORD;
                m_it += jump;
                m_bitpos += dist - jump * BITS_PER_WORD;
            } else if (dist < 0) {
                dist = -dist;
                if (dist > m_bitpos) {
                    --m_it;
                    dist -= m_bitpos + 1;
                    m_bitpos = BITS_PER_WORD - 1;
                }
                auto jump = dist / BITS_PER_WORD;
                m_it -= jump;
                m_bitpos -= dist - jump * BITS_PER_WORD;
            }
            return *this;
        }

        friend difference_type operator-(const Iterator& x, const Iterator& y)
        {
            return BITS_PER_WORD * (x.m_it - y.m_it) + x.m_bitpos - y.m_bitpos;
        }

        Iterator& operator=(const Iterator&) = default;
        Iterator& operator-=(difference_type dist) { return operator+=(-dist); }
        Iterator& operator++() { ++m_bitpos; if (m_bitpos == BITS_PER_WORD) { m_bitpos = 0; ++m_it; }; return *this; }
        Iterator operator++(int) { auto ret{*this}; operator++(); return ret; }
        Iterator& operator--() { if (m_bitpos == 0) { m_bitpos = BITS_PER_WORD; --m_it; }; --m_bitpos; return *this; }
        Iterator operator--(int) { auto ret{*this}; operator--(); return ret; }
        friend Iterator operator+(Iterator x, difference_type dist) { x += dist; return x; }
        friend Iterator operator+(difference_type dist, Iterator x) { x += dist; return x; }
        friend Iterator operator-(Iterator x, difference_type dist) { x -= dist; return x; }
        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); }
        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); }
        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); }
        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); }
        friend bool operator==(const Iterator& x, const Iterator& y) { return x.m_it == y.m_it && x.m_bitpos == y.m_bitpos; }
        friend bool operator!=(const Iterator& x, const Iterator& y) { return x.m_it != y.m_it || x.m_bitpos != y.m_bitpos; }
        reference operator*() const { return (*m_it)[m_bitpos]; }
        reference operator[](difference_type pos) const { return *(*this + pos); }
    };

public:
    using value_type = bool;
    using size_type = std::size_t;
    using difference_type = typename deque_type::difference_type;
    using reference = typename word_type::reference;
    using const_reference = bool;
    using iterator = Iterator<false>;
    using const_iterator = Iterator<true>;
    using pointer = void;
    using const_pointer = void;
    using reverse_iterator = std::reverse_iterator<iterator>;
    using const_reverse_iterator = std::reverse_iterator<const_iterator>;

private:
    /** Deque of bitsets storing the actual bit data. */
    deque_type m_deque;

    /** Number of unused bits at the front of m_deque.front(). */
    int m_pad_begin;

    /** Number of unused bits at the back of m_deque.back(). */
    int m_pad_end;

    /** Shrink the container by n bits, removing from the end. */
    void erase_back(size_type n)
    {
        if (n >= static_cast<size_type>(BITS_PER_WORD - m_pad_end)) {
            n -= BITS_PER_WORD - m_pad_end;
            m_pad_end = 0;
            m_deque.erase(m_deque.end() - 1 - (n / BITS_PER_WORD), m_deque.end());
            n %= BITS_PER_WORD;
        }
        if (n) {
            auto& last = m_deque.back();
            while (n) {
                last.reset(BITS_PER_WORD - 1 - m_pad_end);
                ++m_pad_end;
                --n;
            }
        }
    }

    /** Extend the container by n bits, adding at the end. */
    void extend_back(size_type n)
    {
        if (n > static_cast<size_type>(m_pad_end)) {
            n -= m_pad_end + 1;
            m_pad_end = BITS_PER_WORD - 1;
            m_deque.insert(m_deque.end(), 1 + (n / BITS_PER_WORD), {});
            n %= BITS_PER_WORD;
        }
        m_pad_end -= n;
    }

    /** Shrink the container by n bits, removing from the beginning. */
    void erase_front(size_type n)
    {
        if (n >= static_cast<size_type>(BITS_PER_WORD - m_pad_begin)) {
            n -= BITS_PER_WORD - m_pad_begin;
            m_pad_begin = 0;
            m_deque.erase(m_deque.begin(), m_deque.begin() + 1 + (n / BITS_PER_WORD));
            n %= BITS_PER_WORD;
        }
        if (n) {
            auto& first = m_deque.front();
            while (n) {
                first.reset(m_pad_begin);
                ++m_pad_begin;
                --n;
            }
        }
    }

    /** Extend the container by n bits, adding at the beginning. */
    void extend_front(size_type n)
    {
        if (n > static_cast<size_type>(m_pad_begin)) {
            n -= m_pad_begin + 1;
            m_pad_begin = BITS_PER_WORD - 1;
            m_deque.insert(m_deque.begin(), 1 + (n / BITS_PER_WORD), {});
            n %= BITS_PER_WORD;
        }
        m_pad_begin -= n;
    }

    /** Insert a sequence of falses anywhere in the container. */
    void insert_zeroes(size_type before, size_type count)
    {
        size_type after = size() - before;
        if (before < after) {
            extend_front(count);
            std::move(begin() + count, begin() + count + before, begin());
        } else {
            extend_back(count);
            std::move_backward(begin() + before, begin() + before + after, end());
        }
    }

public:
    /** Construct an empty container. */
    explicit bitdeque() : m_pad_begin{0}, m_pad_end{0} {}

    /** Set the container equal to count times the value of val. */
    void assign(size_type count, bool val)
    {
        m_deque.clear();
        m_deque.resize((count + BITS_PER_WORD - 1) / BITS_PER_WORD);
        m_pad_begin = 0;
        m_pad_end = 0;
        if (val) {
            for (auto& elem : m_deque) elem.flip();
        }
        if (count % BITS_PER_WORD) {
            erase_back(BITS_PER_WORD - (count % BITS_PER_WORD));
        }
    }

    /** Construct a container containing count times the value of val. */
    bitdeque(size_type count, bool val) { assign(count, val); }

    /** Construct a container containing count false values. */
    explicit bitdeque(size_t count) { assign(count, false); }

    /** Copy constructor. */
    bitdeque(const bitdeque&) = default;

    /** Move constructor. */
    bitdeque(bitdeque&&) noexcept = default;

    /** Copy assignment operator. */
    bitdeque& operator=(const bitdeque& other) = default;

    /** Move assignment operator. */
    bitdeque& operator=(bitdeque&& other) noexcept = default;

    // Iterator functions.
    iterator begin() noexcept { return {m_deque.begin(), m_pad_begin}; }
    iterator end() noexcept { return iterator{m_deque.end(), 0} - m_pad_end; }
    const_iterator begin() const noexcept { return const_iterator{m_deque.cbegin(), m_pad_begin}; }
    const_iterator cbegin() const noexcept { return const_iterator{m_deque.cbegin(), m_pad_begin}; }
    const_iterator end() const noexcept { return const_iterator{m_deque.cend(), 0} - m_pad_end; }
    const_iterator cend() const noexcept { return const_iterator{m_deque.cend(), 0} - m_pad_end; }
    reverse_iterator rbegin() noexcept { return reverse_iterator{end()}; }
    reverse_iterator rend() noexcept { return reverse_iterator{begin()}; }
    const_reverse_iterator rbegin() const noexcept { return const_reverse_iterator{cend()}; }
    const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator{cend()}; }
    const_reverse_iterator rend() const noexcept { return const_reverse_iterator{cbegin()}; }
    const_reverse_iterator crend() const noexcept { return const_reverse_iterator{cbegin()}; }

    /** Count the number of bits in the container. */
    size_type size() const noexcept { return m_deque.size() * BITS_PER_WORD - m_pad_begin - m_pad_end; }

    /** Determine whether the container is empty. */
    bool empty() const noexcept
    {
        return m_deque.size() == 0 || (m_deque.size() == 1 && (m_pad_begin + m_pad_end == BITS_PER_WORD));
    }

    /** Return the maximum size of the container. */
    size_type max_size() const noexcept
    {
        if (m_deque.max_size() < std::numeric_limits<difference_type>::max() / BITS_PER_WORD) {
            return m_deque.max_size() * BITS_PER_WORD;
        } else {
            return std::numeric_limits<difference_type>::max();
        }
    }

    /** Set the container equal to the bits in [first,last). */
    template<typename It>
    void assign(It first, It last)
    {
        size_type count = std::distance(first, last);
        assign(count, false);
        auto it = begin();
        while (first != last) {
            *(it++) = *(first++);
        }
    }

    /** Set the container equal to the bits in ilist. */
    void assign(std::initializer_list<bool> ilist)
    {
        assign(ilist.size(), false);
        auto it = begin();
        auto init = ilist.begin();
        while (init != ilist.end()) {
            *(it++) = *(init++);
        }
    }

    /** Set the container equal to the bits in ilist. */
    bitdeque& operator=(std::initializer_list<bool> ilist)
    {
        assign(ilist);
        return *this;
    }

    /** Construct a container containing the bits in [first,last). */
    template<typename It>
    bitdeque(It first, It last) { assign(first, last); }

    /** Construct a container containing the bits in ilist. */
    bitdeque(std::initializer_list<bool> ilist) { assign(ilist); }

    // Access an element of the container, with bounds checking.
    reference at(size_type position)
    {
        if (position >= size()) throw std::out_of_range("bitdeque::at() out of range");
        return begin()[position];
    }
    const_reference at(size_type position) const
    {
        if (position >= size()) throw std::out_of_range("bitdeque::at() out of range");
        return cbegin()[position];
    }

    // Access elements of the container without bounds checking.
    reference operator[](size_type position) { return begin()[position]; }
    const_reference operator[](size_type position) const { return cbegin()[position]; }
    reference front() { return *begin(); }
    const_reference front() const { return *cbegin(); }
    reference back() { return end()[-1]; }
    const_reference back() const { return cend()[-1]; }

    /** Release unused memory. */
    void shrink_to_fit()
    {
        m_deque.shrink_to_fit();
    }

    /** Empty the container. */
    void clear() noexcept
    {
        m_deque.clear();
        m_pad_begin = m_pad_end = 0;
    }

    // Append an element to the container.
    void push_back(bool val)
    {
        extend_back(1);
        back() = val;
    }
    reference emplace_back(bool val)
    {
        extend_back(1);
        auto ref = back();
        ref = val;
        return ref;
    }

    // Prepend an element to the container.
    void push_front(bool val)
    {
        extend_front(1);
        front() = val;
    }
    reference emplace_front(bool val)
    {
        extend_front(1);
        auto ref = front();
        ref = val;
        return ref;
    }

    // Remove the last element from the container.
    void pop_back()
    {
        erase_back(1);
    }

    // Remove the first element from the container.
    void pop_front()
    {
        erase_front(1);
    }

    /** Resize the container. */
    void resize(size_type n)
    {
        if (n < size()) {
            erase_back(size() - n);
        } else {
            extend_back(n - size());
        }
    }

    // Swap two containers.
    void swap(bitdeque& other) noexcept
    {
        std::swap(m_deque, other.m_deque);
        std::swap(m_pad_begin, other.m_pad_begin);
        std::swap(m_pad_end, other.m_pad_end);
    }
    friend void swap(bitdeque& b1, bitdeque& b2) noexcept { b1.swap(b2); }

    // Erase elements from the container.
    iterator erase(const_iterator first, const_iterator last)
    {
        size_type before = std::distance(cbegin(), first);
        size_type dist = std::distance(first, last);
        size_type after = std::distance(last, cend());
        if (before < after) {
            std::move_backward(begin(), begin() + before, end() - after);
            erase_front(dist);
            return begin() + before;
        } else {
            std::move(end() - after, end(), begin() + before);
            erase_back(dist);
            return end() - after;
        }
    }

    iterator erase(iterator first, iterator last) { return erase(const_iterator{first}, const_iterator{last}); }
    iterator erase(const_iterator pos) { return erase(pos, pos + 1); }
    iterator erase(iterator pos) { return erase(const_iterator{pos}, const_iterator{pos} + 1); }

    // Insert elements into the container.
    iterator insert(const_iterator pos, bool val)
    {
        size_type before = pos - cbegin();
        insert_zeroes(before, 1);
        auto it = begin() + before;
        *it = val;
        return it;
    }

    iterator emplace(const_iterator pos, bool val) { return insert(pos, val); }

    iterator insert(const_iterator pos, size_type count, bool val)
    {
        size_type before = pos - cbegin();
        insert_zeroes(before, count);
        auto it_begin = begin() + before;
        auto it = it_begin;
        auto it_end = it + count;
        while (it != it_end) *(it++) = val;
        return it_begin;
    }

    template<typename It>
    iterator insert(const_iterator pos, It first, It last)
    {
        size_type before = pos - cbegin();
        size_type count = std::distance(first, last);
        insert_zeroes(before, count);
        auto it_begin = begin() + before;
        auto it = it_begin;
        while (first != last) {
            *(it++) = *(first++);
        }
        return it_begin;
    }
};

#endif // BITCOIN_UTIL_BITDEQUE_H

fuzz coverage

Coverage Report

Created: 2025-10-29 15:27

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