Inside Bitcoin

1// Copyright (c) 2022-present The Bitcoin Core developers
2// Distributed under the MIT software license, see the accompanying
3// file COPYING or http://www.opensource.org/licenses/mit-license.php.
4
5#ifndef BITCOIN_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#include <util/overflow.h>
15
16/** Class that mimics std::deque<bool>, but with std::vector<bool>'s bit packing.
17 *
18 * BITS_PER_WORD selects the (minimum) number of bits that are allocated at once.
19 * Larger values reduce the asymptotic memory usage overhead, at the cost of
20 * needing larger up-front allocations. The default is 4096 bytes.
21 */
22template<int BITS_PER_WORD = 4096 * 8>
23class bitdeque
24{
25    // Internal definitions
26    using word_type = std::bitset<BITS_PER_WORD>;
27    using deque_type = std::deque<word_type>;
28    static_assert(BITS_PER_WORD > 0);
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        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        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        Iterator(const Iterator<false>& x) : m_it(x.m_it), m_bitpos(x.m_bitpos) {}
63
64        Iterator& operator+=(difference_type dist)
65        {
66            if (dist > 0) {
67                if (dist + m_bitpos >= BITS_PER_WORD) {
68                    ++m_it;
69                    dist -= BITS_PER_WORD - m_bitpos;
70                    m_bitpos = 0;
71                }
72                auto jump = dist / BITS_PER_WORD;
73                m_it += jump;
74                m_bitpos += dist - jump * BITS_PER_WORD;
75            } else if (dist < 0) {
76                dist = -dist;
77                if (dist > m_bitpos) {
78                    --m_it;
79                    dist -= m_bitpos + 1;
80                    m_bitpos = BITS_PER_WORD - 1;
81                }
82                auto jump = dist / BITS_PER_WORD;
83                m_it -= jump;
84                m_bitpos -= dist - jump * BITS_PER_WORD;
85            }
86            return *this;
87        }
88
89        friend difference_type operator-(const Iterator& x, const Iterator& y)
90        {
91            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        Iterator& operator-=(difference_type dist) { return operator+=(-dist); }
96        Iterator& operator++() { ++m_bitpos; if (m_bitpos == BITS_PER_WORD) { m_bitpos = 0; ++m_it; }; return *this; }
97        Iterator operator++(int) { auto ret{*this}; operator++(); return ret; }
98        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        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        friend Iterator operator-(Iterator x, difference_type dist) { x -= dist; return x; }
103        friend auto 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 x.m_it == y.m_it && x.m_bitpos == y.m_bitpos; }
105        reference operator*() const { return (*m_it)[m_bitpos]; }
106        reference operator[](difference_type pos) const { return *(*this + pos); }
107    };
108
109public:
110    using value_type = bool;
111    using size_type = std::size_t;
112    using difference_type = typename deque_type::difference_type;
113    using reference = typename word_type::reference;
114    using const_reference = bool;
115    using iterator = Iterator<false>;
116    using const_iterator = Iterator<true>;
117    using pointer = void;
118    using const_pointer = void;
119    using reverse_iterator = std::reverse_iterator<iterator>;
120    using const_reverse_iterator = std::reverse_iterator<const_iterator>;
121
122private:
123    /** Deque of bitsets storing the actual bit data. */
124    deque_type m_deque;
125
126    /** Number of unused bits at the front of m_deque.front(). */
127    int m_pad_begin;
128
129    /** Number of unused bits at the back of m_deque.back(). */
130    int m_pad_end;
131
132    /** Shrink the container by n bits, removing from the end. */
133    void erase_back(size_type n)
134    {
135        if (n >= static_cast<size_type>(BITS_PER_WORD - m_pad_end)) {
136            n -= BITS_PER_WORD - m_pad_end;
137            m_pad_end = 0;
138            m_deque.erase(m_deque.end() - 1 - (n / BITS_PER_WORD), m_deque.end());
139            n %= BITS_PER_WORD;
140        }
141        if (n) {
142            auto& last = m_deque.back();
143            while (n) {
144                last.reset(BITS_PER_WORD - 1 - m_pad_end);
145                ++m_pad_end;
146                --n;
147            }
148        }
149    }
150
151    /** Extend the container by n bits, adding at the end. */
152    void extend_back(size_type n)
153    {
154        if (n > static_cast<size_type>(m_pad_end)) {
155            n -= m_pad_end + 1;
156            m_pad_end = BITS_PER_WORD - 1;
157            m_deque.insert(m_deque.end(), 1 + (n / BITS_PER_WORD), {});
158            n %= BITS_PER_WORD;
159        }
160        m_pad_end -= n;
161    }
162
163    /** Shrink the container by n bits, removing from the beginning. */
164    void erase_front(size_type n)
165    {
166        if (n >= static_cast<size_type>(BITS_PER_WORD - m_pad_begin)) {
167            n -= BITS_PER_WORD - m_pad_begin;
168            m_pad_begin = 0;
169            m_deque.erase(m_deque.begin(), m_deque.begin() + 1 + (n / BITS_PER_WORD));
170            n %= BITS_PER_WORD;
171        }
172        if (n) {
173            auto& first = m_deque.front();
174            while (n) {
175                first.reset(m_pad_begin);
176                ++m_pad_begin;
177                --n;
178            }
179        }
180    }
181
182    /** Extend the container by n bits, adding at the beginning. */
183    void extend_front(size_type n)
184    {
185        if (n > static_cast<size_type>(m_pad_begin)) {
186            n -= m_pad_begin + 1;
187            m_pad_begin = BITS_PER_WORD - 1;
188            m_deque.insert(m_deque.begin(), 1 + (n / BITS_PER_WORD), {});
189            n %= BITS_PER_WORD;
190        }
191        m_pad_begin -= n;
192    }
193
194    /** Insert a sequence of falses anywhere in the container. */
195    void insert_zeroes(size_type before, size_type count)
196    {
197        size_type after = size() - before;
198        if (before < after) {
199            extend_front(count);
200            std::move(begin() + count, begin() + count + before, begin());
201        } else {
202            extend_back(count);
203            std::move_backward(begin() + before, begin() + before + after, end());
204        }
205    }
206
207public:
208    /** Construct an empty container. */
209    explicit bitdeque() : m_pad_begin{0}, m_pad_end{0} {}
210
211    /** Set the container equal to count times the value of val. */
212    void assign(size_type count, bool val)
213    {
214        m_deque.clear();
215        m_deque.resize(CeilDiv(count, size_type{BITS_PER_WORD}));
216        m_pad_begin = 0;
217        m_pad_end = 0;
218        if (val) {
219            for (auto& elem : m_deque) elem.flip();
220        }
221        if (count % BITS_PER_WORD) {
222            erase_back(BITS_PER_WORD - (count % BITS_PER_WORD));
223        }
224    }
225
226    /** Construct a container containing count times the value of val. */
227    bitdeque(size_type count, bool val) { assign(count, val); }
228
229    /** Construct a container containing count false values. */
230    explicit bitdeque(size_t count) { assign(count, false); }
231
232    /** Copy constructor. */
233    bitdeque(const bitdeque&) = default;
234
235    /** Move constructor. */
236    bitdeque(bitdeque&&) noexcept = default;
237
238    /** Copy assignment operator. */
239    bitdeque& operator=(const bitdeque& other) = default;
240
241    /** Move assignment operator. */
242    bitdeque& operator=(bitdeque&& other) noexcept = default;
243
244    // Iterator functions.
245    iterator begin() noexcept { return {m_deque.begin(), m_pad_begin}; }
246    iterator end() noexcept { return iterator{m_deque.end(), 0} - m_pad_end; }
247    const_iterator begin() const noexcept { return const_iterator{m_deque.cbegin(), m_pad_begin}; }
248    const_iterator cbegin() const noexcept { return const_iterator{m_deque.cbegin(), m_pad_begin}; }
249    const_iterator end() const noexcept { return const_iterator{m_deque.cend(), 0} - m_pad_end; }
250    const_iterator cend() const noexcept { return const_iterator{m_deque.cend(), 0} - m_pad_end; }