Add bitdeque, an std::deque<bool> analogue that does bit packing.

5 files changed, 1014 insertions, 0 deletions

diff --git a/src/Makefile.am b/src/Makefile.am
index 18c6c25b96..89b0afe3d9 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -264,6 +264,7 @@ BITCOIN_CORE_H = \
   undo.h \
   util/asmap.h \
   util/bip32.h \
+  util/bitdeque.h \
   util/bytevectorhash.h \
   util/check.h \
   util/epochguard.h \
diff --git a/src/Makefile.test.include b/src/Makefile.test.include
index 22a95f9682..e80eb598f2 100644
--- a/src/Makefile.test.include
+++ b/src/Makefile.test.include
@@ -235,6 +235,7 @@ test_fuzz_fuzz_SOURCES = \
  test/fuzz/banman.cpp \
  test/fuzz/base_encode_decode.cpp \
  test/fuzz/bech32.cpp \
+ test/fuzz/bitdeque.cpp \
  test/fuzz/block.cpp \
  test/fuzz/block_header.cpp \
  test/fuzz/blockfilter.cpp \
diff --git a/src/test/fuzz/bitdeque.cpp b/src/test/fuzz/bitdeque.cpp
new file mode 100644
index 0000000000..01af8320b5
--- /dev/null
+++ b/src/test/fuzz/bitdeque.cpp
@@ -0,0 +1,542 @@
+// 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.
+
+#include <util/bitdeque.h>
+
+#include <random.h>
+#include <test/fuzz/FuzzedDataProvider.h>
+#include <test/fuzz/util.h>
+
+#include <deque>
+#include <vector>
+
+namespace {
+
+constexpr int LEN_BITS = 16;
+constexpr int RANDDATA_BITS = 20;
+
+using bitdeque_type = bitdeque<128>;
+
+//! Deterministic random vector of bools, for begin/end insertions to draw from.
+std::vector<bool> RANDDATA;
+
+void InitRandData()
+{
+    FastRandomContext ctx(true);
+    RANDDATA.clear();
+    for (size_t i = 0; i < (1U << RANDDATA_BITS) + (1U << LEN_BITS); ++i) {
+        RANDDATA.push_back(ctx.randbool());
+    }
+}
+
+} // namespace
+
+FUZZ_TARGET_INIT(bitdeque, InitRandData)
+{
+    FuzzedDataProvider provider(buffer.data(), buffer.size());
+    FastRandomContext ctx(true);
+
+    size_t maxlen = (1U << provider.ConsumeIntegralInRange<size_t>(0, LEN_BITS)) - 1;
+    size_t limitlen = 4 * maxlen;
+
+    std::deque<bool> deq;
+    bitdeque_type bitdeq;
+
+    const auto& cdeq = deq;
+    const auto& cbitdeq = bitdeq;
+
+    size_t initlen = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
+    while (initlen) {
+        bool val = ctx.randbool();
+        deq.push_back(val);
+        bitdeq.push_back(val);
+        --initlen;
+    }
+
+    while (provider.remaining_bytes()) {
+        {
+            assert(deq.size() == bitdeq.size());
+            auto it = deq.begin();
+            auto bitit = bitdeq.begin();
+            auto itend = deq.end();
+            while (it != itend) {
+                assert(*it == *bitit);
+                ++it;
+                ++bitit;
+            }
+        }
+
+        CallOneOf(provider,
+            [&] {
+                // constructor()
+                deq = std::deque<bool>{};
+                bitdeq = bitdeque_type{};
+            },
+            [&] {
+                // clear()
+                deq.clear();
+                bitdeq.clear();
+            },
+            [&] {
+                // resize()
+                auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
+                deq.resize(count);
+                bitdeq.resize(count);
+            },
+            [&] {
+                // assign(count, val)
+                auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
+                bool val = ctx.randbool();
+                deq.assign(count, val);
+                bitdeq.assign(count, val);
+            },
+            [&] {
+                // constructor(count, val)
+                auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
+                bool val = ctx.randbool();
+                deq = std::deque<bool>(count, val);
+                bitdeq = bitdeque_type(count, val);
+            },
+            [&] {
+                // constructor(count)
+                auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
+                deq = std::deque<bool>(count);
+                bitdeq = bitdeque_type(count);
+            },
+            [&] {
+                // construct(begin, end)
+                auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
+                auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
+                auto rand_end = rand_begin + count;
+                deq = std::deque<bool>(rand_begin, rand_end);
+                bitdeq = bitdeque_type(rand_begin, rand_end);
+            },
+            [&] {
+                // assign(begin, end)
+                auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
+                auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
+                auto rand_end = rand_begin + count;
+                deq.assign(rand_begin, rand_end);
+                bitdeq.assign(rand_begin, rand_end);
+            },
+            [&] {
+                // construct(initializer_list)
+                std::initializer_list<bool> ilist{ctx.randbool(), ctx.randbool(), ctx.randbool(), ctx.randbool(), ctx.randbool()};
+                deq = std::deque<bool>(ilist);
+                bitdeq = bitdeque_type(ilist);
+            },
+            [&] {
+                // assign(initializer_list)
+                std::initializer_list<bool> ilist{ctx.randbool(), ctx.randbool(), ctx.randbool()};
+                deq.assign(ilist);
+                bitdeq.assign(ilist);
+            },
+            [&] {
+                // operator=(const&)
+                auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
+                bool val = ctx.randbool();
+                const std::deque<bool> deq2(count, val);
+                deq = deq2;
+                const bitdeque_type bitdeq2(count, val);
+                bitdeq = bitdeq2;
+            },
+            [&] {
+                // operator=(&&)
+                auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
+                bool val = ctx.randbool();
+                std::deque<bool> deq2(count, val);
+                deq = std::move(deq2);
+                bitdeque_type bitdeq2(count, val);
+                bitdeq = std::move(bitdeq2);
+            },
+            [&] {
+                // deque swap
+                auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
+                auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
+                auto rand_end = rand_begin + count;
+                std::deque<bool> deq2(rand_begin, rand_end);
+                bitdeque_type bitdeq2(rand_begin, rand_end);
+                using std::swap;
+                assert(deq.size() == bitdeq.size());
+                assert(deq2.size() == bitdeq2.size());
+                swap(deq, deq2);
+                swap(bitdeq, bitdeq2);
+                assert(deq.size() == bitdeq.size());
+                assert(deq2.size() == bitdeq2.size());
+            },
+            [&] {
+                // deque.swap
+                auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
+                auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
+                auto rand_end = rand_begin + count;
+                std::deque<bool> deq2(rand_begin, rand_end);
+                bitdeque_type bitdeq2(rand_begin, rand_end);
+                assert(deq.size() == bitdeq.size());
+                assert(deq2.size() == bitdeq2.size());
+                deq.swap(deq2);
+                bitdeq.swap(bitdeq2);
+                assert(deq.size() == bitdeq.size());
+                assert(deq2.size() == bitdeq2.size());
+            },
+            [&] {
+                // operator=(initializer_list)
+                std::initializer_list<bool> ilist{ctx.randbool(), ctx.randbool(), ctx.randbool()};
+                deq = ilist;
+                bitdeq = ilist;
+            },
+            [&] {
+                // iterator arithmetic
+                auto pos1 = provider.ConsumeIntegralInRange<long>(0, cdeq.size());
+                auto pos2 = provider.ConsumeIntegralInRange<long>(0, cdeq.size());
+                auto it = deq.begin() + pos1;
+                auto bitit = bitdeq.begin() + pos1;
+                if ((size_t)pos1 != cdeq.size()) assert(*it == *bitit);
+                assert(it - deq.begin() == pos1);
+                assert(bitit - bitdeq.begin() == pos1);
+                if (provider.ConsumeBool()) {
+                    it += pos2 - pos1;
+                    bitit += pos2 - pos1;
+                } else {
+                    it -= pos1 - pos2;
+                    bitit -= pos1 - pos2;
+                }
+                if ((size_t)pos2 != cdeq.size()) assert(*it == *bitit);
+                assert(deq.end() - it == bitdeq.end() - bitit);
+                if (provider.ConsumeBool()) {
+                    if ((size_t)pos2 != cdeq.size()) {
+                        ++it;
+                        ++bitit;
+                    }
+                } else {
+                    if (pos2 != 0) {
+                        --it;
+                        --bitit;
+                    }
+                }
+                assert(deq.end() - it == bitdeq.end() - bitit);
+            },
+            [&] {
+                // begin() and end()
+                assert(deq.end() - deq.begin() == bitdeq.end() - bitdeq.begin());
+            },
+            [&] {
+                // begin() and end() (const)
+                assert(cdeq.end() - cdeq.begin() == cbitdeq.end() - cbitdeq.begin());
+            },
+            [&] {
+                // rbegin() and rend()
+                assert(deq.rend() - deq.rbegin() == bitdeq.rend() - bitdeq.rbegin());
+            },
+            [&] {
+                // rbegin() and rend() (const)
+                assert(cdeq.rend() - cdeq.rbegin() == cbitdeq.rend() - cbitdeq.rbegin());
+            },
+            [&] {
+                // cbegin() and cend()
+                assert(cdeq.cend() - cdeq.cbegin() == cbitdeq.cend() - cbitdeq.cbegin());
+            },
+            [&] {
+                // crbegin() and crend()
+                assert(cdeq.crend() - cdeq.crbegin() == cbitdeq.crend() - cbitdeq.crbegin());
+            },
+            [&] {
+                // size() and maxsize()
+                assert(cdeq.size() == cbitdeq.size());
+                assert(cbitdeq.size() <= cbitdeq.max_size());
+            },
+            [&] {
+                // empty
+                assert(cdeq.empty() == cbitdeq.empty());
+            },
+            [&] {
+                // at (in range) and flip
+                if (!cdeq.empty()) {
+                    size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
+                    auto& ref = deq.at(pos);
+                    auto bitref = bitdeq.at(pos);
+                    assert(ref == bitref);
+                    if (ctx.randbool()) {
+                        ref = !ref;
+                        bitref.flip();
+                    }
+                }
+            },
+            [&] {
+                // at (maybe out of range) and bit assign
+                size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() + maxlen);
+                bool newval = ctx.randbool();
+                bool throw_deq{false}, throw_bitdeq{false};
+                bool val_deq{false}, val_bitdeq{false};
+                try {
+                    auto& ref = deq.at(pos);
+                    val_deq = ref;
+                    ref = newval;
+                } catch (const std::out_of_range&) {
+                    throw_deq = true;
+                }
+                try {
+                    auto ref = bitdeq.at(pos);
+                    val_bitdeq = ref;
+                    ref = newval;
+                } catch (const std::out_of_range&) {
+                    throw_bitdeq = true;
+                }
+                assert(throw_deq == throw_bitdeq);
+                assert(throw_bitdeq == (pos >= cdeq.size()));
+                if (!throw_deq) assert(val_deq == val_bitdeq);
+            },
+            [&] {
+                // at (maybe out of range) (const)
+                size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() + maxlen);
+                bool throw_deq{false}, throw_bitdeq{false};
+                bool val_deq{false}, val_bitdeq{false};
+                try {
+                    auto& ref = cdeq.at(pos);
+                    val_deq = ref;
+                } catch (const std::out_of_range&) {
+                    throw_deq = true;
+                }
+                try {
+                    auto ref = cbitdeq.at(pos);
+                    val_bitdeq = ref;
+                } catch (const std::out_of_range&) {
+                    throw_bitdeq = true;
+                }
+                assert(throw_deq == throw_bitdeq);
+                assert(throw_bitdeq == (pos >= cdeq.size()));
+                if (!throw_deq) assert(val_deq == val_bitdeq);
+            },
+            [&] {
+                // operator[]
+                if (!cdeq.empty()) {
+                    size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
+                    assert(deq[pos] == bitdeq[pos]);
+                    if (ctx.randbool()) {
+                        deq[pos] = !deq[pos];
+                        bitdeq[pos].flip();
+                    }
+                }
+            },
+            [&] {
+                // operator[] const
+                if (!cdeq.empty()) {
+                    size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
+                    assert(deq[pos] == bitdeq[pos]);
+                }
+            },
+            [&] {
+                // front()
+                if (!cdeq.empty()) {
+                    auto& ref = deq.front();
+                    auto bitref = bitdeq.front();
+                    assert(ref == bitref);
+                    if (ctx.randbool()) {
+                        ref = !ref;
+                        bitref = !bitref;
+                    }
+                }
+            },
+            [&] {
+                // front() const
+                if (!cdeq.empty()) {
+                    auto& ref = cdeq.front();
+                    auto bitref = cbitdeq.front();
+                    assert(ref == bitref);
+                }
+            },
+            [&] {
+                // back() and swap(bool, ref)
+                if (!cdeq.empty()) {
+                    auto& ref = deq.back();
+                    auto bitref = bitdeq.back();
+                    assert(ref == bitref);
+                    if (ctx.randbool()) {
+                        ref = !ref;
+                        bitref.flip();
+                    }
+                }
+            },
+            [&] {
+                // back() const
+                if (!cdeq.empty()) {
+                    const auto& cdeq = deq;
+                    const auto& cbitdeq = bitdeq;
+                    auto& ref = cdeq.back();
+                    auto bitref = cbitdeq.back();
+                    assert(ref == bitref);
+                }
+            },
+            [&] {
+                // push_back()
+                if (cdeq.size() < limitlen) {
+                    bool val = ctx.randbool();
+                    if (cdeq.empty()) {
+                        deq.push_back(val);
+                        bitdeq.push_back(val);
+                    } else {
+                        size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
+                        auto& ref = deq[pos];
+                        auto bitref = bitdeq[pos];
+                        assert(ref == bitref);
+                        deq.push_back(val);
+                        bitdeq.push_back(val);
+                        assert(ref == bitref); // references are not invalidated
+                    }
+                }
+            },
+            [&] {
+                // push_front()
+                if (cdeq.size() < limitlen) {
+                    bool val = ctx.randbool();
+                    if (cdeq.empty()) {
+                        deq.push_front(val);
+                        bitdeq.push_front(val);
+                    } else {
+                        size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
+                        auto& ref = deq[pos];
+                        auto bitref = bitdeq[pos];
+                        assert(ref == bitref);
+                        deq.push_front(val);
+                        bitdeq.push_front(val);
+                        assert(ref == bitref); // references are not invalidated
+                    }
+                }
+            },
+            [&] {
+                // pop_back()
+                if (!cdeq.empty()) {
+                    if (cdeq.size() == 1) {
+                        deq.pop_back();
+                        bitdeq.pop_back();
+                    } else {
+                        size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 2);
+                        auto& ref = deq[pos];
+                        auto bitref = bitdeq[pos];
+                        assert(ref == bitref);
+                        deq.pop_back();
+                        bitdeq.pop_back();
+                        assert(ref == bitref); // references to other elements are not invalidated
+                    }
+                }
+            },
+            [&] {
+                // pop_front()
+                if (!cdeq.empty()) {
+                    if (cdeq.size() == 1) {
+                        deq.pop_front();
+                        bitdeq.pop_front();
+                    } else {
+                        size_t pos = provider.ConsumeIntegralInRange<size_t>(1, cdeq.size() - 1);
+                        auto& ref = deq[pos];
+                        auto bitref = bitdeq[pos];
+                        assert(ref == bitref);
+                        deq.pop_front();
+                        bitdeq.pop_front();
+                        assert(ref == bitref); // references to other elements are not invalidated
+                    }
+                }
+            },
+            [&] {
+                // erase (in middle, single)
+                if (!cdeq.empty()) {
+                    size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
+                    size_t after = cdeq.size() - 1 - before;
+                    auto it = deq.erase(cdeq.begin() + before);
+                    auto bitit = bitdeq.erase(cbitdeq.begin() + before);
+                    assert(it == cdeq.begin() + before && it == cdeq.end() - after);
+                    assert(bitit == cbitdeq.begin() + before && bitit == cbitdeq.end() - after);
+                }
+            },
+            [&] {
+                // erase (at front, range)
+                size_t count = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
+                auto it = deq.erase(cdeq.begin(), cdeq.begin() + count);
+                auto bitit = bitdeq.erase(cbitdeq.begin(), cbitdeq.begin() + count);
+                assert(it == deq.begin());
+                assert(bitit == bitdeq.begin());
+            },
+            [&] {
+                // erase (at back, range)
+                size_t count = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
+                auto it = deq.erase(cdeq.end() - count, cdeq.end());
+                auto bitit = bitdeq.erase(cbitdeq.end() - count, cbitdeq.end());
+                assert(it == deq.end());
+                assert(bitit == bitdeq.end());
+            },
+            [&] {
+                // erase (in middle, range)
+                size_t count = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
+                size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - count);
+                size_t after = cdeq.size() - count - before;
+                auto it = deq.erase(cdeq.begin() + before, cdeq.end() - after);
+                auto bitit = bitdeq.erase(cbitdeq.begin() + before, cbitdeq.end() - after);
+                assert(it == cdeq.begin() + before && it == cdeq.end() - after);
+                assert(bitit == cbitdeq.begin() + before && bitit == cbitdeq.end() - after);
+            },
+            [&] {
+                // insert/emplace (in middle, single)
+                if (cdeq.size() < limitlen) {
+                    size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
+                    bool val = ctx.randbool();
+                    bool do_emplace = provider.ConsumeBool();
+                    auto it = deq.insert(cdeq.begin() + before, val);
+                    auto bitit = do_emplace ? bitdeq.emplace(cbitdeq.begin() + before, val)
+                                            : bitdeq.insert(cbitdeq.begin() + before, val);
+                    assert(it == deq.begin() + before);
+                    assert(bitit == bitdeq.begin() + before);
+                }
+            },
+            [&] {
+                // insert (at front, begin/end)
+                if (cdeq.size() < limitlen) {
+                    size_t count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
+                    auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
+                    auto rand_end = rand_begin + count;
+                    auto it = deq.insert(cdeq.begin(), rand_begin, rand_end);
+                    auto bitit = bitdeq.insert(cbitdeq.begin(), rand_begin, rand_end);
+                    assert(it == cdeq.begin());
+                    assert(bitit == cbitdeq.begin());
+                }
+            },
+            [&] {
+                // insert (at back, begin/end)
+                if (cdeq.size() < limitlen) {
+                    size_t count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
+                    auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
+                    auto rand_end = rand_begin + count;
+                    auto it = deq.insert(cdeq.end(), rand_begin, rand_end);
+                    auto bitit = bitdeq.insert(cbitdeq.end(), rand_begin, rand_end);
+                    assert(it == cdeq.end() - count);
+                    assert(bitit == cbitdeq.end() - count);
+                }
+            },
+            [&] {
+                // insert (in middle, range)
+                if (cdeq.size() < limitlen) {
+                    size_t count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
+                    size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
+                    bool val = ctx.randbool();
+                    auto it = deq.insert(cdeq.begin() + before, count, val);
+                    auto bitit = bitdeq.insert(cbitdeq.begin() + before, count, val);
+                    assert(it == deq.begin() + before);
+                    assert(bitit == bitdeq.begin() + before);
+                }
+            },
+            [&] {
+                // insert (in middle, begin/end)
+                if (cdeq.size() < limitlen) {
+                    size_t count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
+                    size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
+                    auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
+                    auto rand_end = rand_begin + count;
+                    auto it = deq.insert(cdeq.begin() + before, rand_begin, rand_end);
+                    auto bitit = bitdeq.insert(cbitdeq.begin() + before, rand_begin, rand_end);
+                    assert(it == deq.begin() + before);
+                    assert(bitit == bitdeq.begin() + before);
+                }
+            }
+        );
+    }
+
+}
diff --git a/src/test/util_tests.cpp b/src/test/util_tests.cpp
index 70e2f89e0b..015237f43d 100644
--- a/src/test/util_tests.cpp
+++ b/src/test/util_tests.cpp
@@ -23,6 +23,7 @@
 #include <util/string.h>
 #include <util/time.h>
 #include <util/vector.h>
+#include <util/bitdeque.h>
 
 #include <array>
 #include <fstream>
diff --git a/src/util/bitdeque.h b/src/util/bitdeque.h
new file mode 100644
index 0000000000..1e34b72475
--- /dev/null
+++ b/src/util/bitdeque.h
@@ -0,0 +1,469 @@
+// 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.
+ *
+ * BlobSize 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 BlobSize = 4096 * 8>
+class bitdeque
+{
+    // Internal definitions
+    using word_type = std::bitset<BlobSize>;
+    using deque_type = std::deque<word_type>;
+    static_assert(BlobSize > 0);
+    static constexpr int BITS_PER_WORD = BlobSize;
+
+    // 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