READ THE CODE

Inside Bitcoin

The code behind the network, with room to understand it.

Stable release v32.1bitcoin/bitcoin · f0de87f04062 ↗3,020 source files · 47.5 MB stored on the server340 file guides

Release published 2026-10-28 · Snapshot fetched 2026-11-01. Latest stable release at fetch time; development branches and Git history are excluded. Only the selected code window and visible folders load here.

15,978 bytes · SHA-256 09b98a3c7cc1c60a… · View upstream ↗

1// Copyright (c) 2015-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_PREVECTOR_H
6#define BITCOIN_PREVECTOR_H
7
8#include <algorithm>
9#include <cassert>
10#include <cstdint>
11#include <cstdlib>
12#include <cstring>
13#include <iterator>
14#include <new>
15#include <type_traits>
16#include <utility>
17
18/** Implements a drop-in replacement for std::vector<T> which stores up to N
19 *  elements directly (without heap allocation). The types Size and Diff are
20 *  used to store element counts, and can be any unsigned + signed type.
21 *
22 *  Storage layout is either:
23 *  - Direct allocation:
24 *    - Size _size: the number of used elements (between 0 and N)
25 *    - T direct[N]: an array of N elements of type T
26 *      (only the first _size are initialized).
27 *  - Indirect allocation:
28 *    - Size _size: the number of used elements plus N + 1
29 *    - Size capacity: the number of allocated elements
30 *    - T* indirect: a pointer to an array of capacity elements of type T
31 *      (only the first _size are initialized).
32 *
33 *  The data type T must be movable by memmove/realloc(). Once we switch to C++,
34 *  move constructors can be used instead.
35 */
36template<unsigned int N, typename T, typename Size = uint32_t, typename Diff = int32_t>
37class prevector {
38    static_assert(std::is_trivially_copyable_v<T>);
39
40public:
41    static constexpr unsigned int STATIC_SIZE{N};
42
43    typedef Size size_type;
44    typedef Diff difference_type;
45    typedef T value_type;
46    typedef value_type& reference;
47    typedef const value_type& const_reference;
48    typedef value_type* pointer;
49    typedef const value_type* const_pointer;
50
51    class iterator {
52        T* ptr{};
53    public:
54        typedef Diff difference_type;
55        typedef T* pointer;
56        typedef T& reference;
57        using element_type = T;
58        using iterator_category = std::contiguous_iterator_tag;
59        iterator() = default;
60        iterator(T* ptr_) : ptr(ptr_) {}
61        T& operator*() const { return *ptr; }
62        T* operator->() const { return ptr; }
63        T& operator[](size_type pos) const { return ptr[pos]; }
64        iterator& operator++() { ptr++; return *this; }
65        iterator& operator--() { ptr--; return *this; }
66        iterator operator++(int) { iterator copy(*this); ++(*this); return copy; }
67        iterator operator--(int) { iterator copy(*this); --(*this); return copy; }
68        difference_type friend operator-(iterator a, iterator b) { return (&(*a) - &(*b)); }
69        iterator operator+(size_type n) const { return iterator(ptr + n); }
70        iterator friend operator+(size_type n, iterator x) { return x + n; }
71        iterator& operator+=(size_type n) { ptr += n; return *this; }
72        iterator operator-(size_type n) const { return iterator(ptr - n); }
73        iterator& operator-=(size_type n) { ptr -= n; return *this; }
74        bool operator==(iterator x) const { return ptr == x.ptr; }
75        auto operator<=>(iterator x) const { return ptr <=> x.ptr; }
76    };
77
78    class const_iterator {
79        const T* ptr{};
80    public:
81        typedef Diff difference_type;
82        typedef const T* pointer;
83        typedef const T& reference;
84        using element_type = const T;
85        using iterator_category = std::contiguous_iterator_tag;
86        const_iterator() = default;
87        const_iterator(const T* ptr_) : ptr(ptr_) {}
88        const_iterator(iterator x) : ptr(&(*x)) {}
89        const T& operator*() const { return *ptr; }
90        const T* operator->() const { return ptr; }
91        const T& operator[](size_type pos) const { return ptr[pos]; }
92        const_iterator& operator++() { ptr++; return *this; }
93        const_iterator& operator--() { ptr--; return *this; }
94        const_iterator operator++(int) { const_iterator copy(*this); ++(*this); return copy; }
95        const_iterator operator--(int) { const_iterator copy(*this); --(*this); return copy; }
96        difference_type friend operator-(const_iterator a, const_iterator b) { return (&(*a) - &(*b)); }
97        const_iterator operator+(size_type n) const { return const_iterator(ptr + n); }
98        const_iterator friend operator+(size_type n, const_iterator x) { return x + n; }
99        const_iterator& operator+=(size_type n) { ptr += n; return *this; }
100        const_iterator operator-(size_type n) const { return const_iterator(ptr - n); }
101        const_iterator& operator-=(size_type n) { ptr -= n; return *this; }
102        bool operator==(const_iterator x) const { return ptr == x.ptr; }
103        auto operator<=>(const_iterator x) const { return ptr <=> x.ptr; }
104    };
105
106private:
107#pragma pack(push, 1)
108    union direct_or_indirect {
109        char direct[sizeof(T) * N];
110        struct {
111            char* indirect;
112            size_type capacity;
113        } indirect_contents;
114    };
115#pragma pack(pop)
116    alignas(char*) direct_or_indirect _union = {};
117    size_type _size = 0;
118
119    static_assert(alignof(char*) % alignof(size_type) == 0 && sizeof(char*) % alignof(size_type) == 0, "size_type cannot have more restrictive alignment requirement than pointer");
120    static_assert(alignof(char*) % alignof(T) == 0, "value_type T cannot have more restrictive alignment requirement than pointer");
121
122    T* direct_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.direct) + pos; }
123    const T* direct_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.direct) + pos; }
124    T* indirect_ptr(difference_type pos) { return reinterpret_cast<T*>(_union.indirect_contents.indirect) + pos; }
125    const T* indirect_ptr(difference_type pos) const { return reinterpret_cast<const T*>(_union.indirect_contents.indirect) + pos; }
126    bool is_direct() const { return _size <= N; }
127
128    void change_capacity(size_type new_capacity) {
129        if (new_capacity <= N) {
130            if (!is_direct()) {
131                T* indirect = indirect_ptr(0);
132                T* src = indirect;
133                T* dst = direct_ptr(0);
134                memcpy(dst, src, size() * sizeof(T));
135                free(indirect);
136                _size -= N + 1;
137            }
138        } else {
139            if (!is_direct()) {
140                /* FIXME: Because malloc/realloc here won't call new_handler if allocation fails, assert
141                    success. These should instead use an allocator or new/delete so that handlers
142                    are called as necessary, but performance would be slightly degraded by doing so. */
143                _union.indirect_contents.indirect = static_cast<char*>(realloc(_union.indirect_contents.indirect, ((size_t)sizeof(T)) * new_capacity));
144                assert(_union.indirect_contents.indirect);
145                _union.indirect_contents.capacity = new_capacity;
146            } else {
147                char* new_indirect = static_cast<char*>(malloc(((size_t)sizeof(T)) * new_capacity));
148                assert(new_indirect);
149                T* src = direct_ptr(0);
150                T* dst = reinterpret_cast<T*>(new_indirect);
151                memcpy(dst, src, size() * sizeof(T));
152                _union.indirect_contents.indirect = new_indirect;
153                _union.indirect_contents.capacity = new_capacity;
154                _size += N + 1;
155            }
156        }
157    }
158
159    T* item_ptr(difference_type pos) { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
160    const T* item_ptr(difference_type pos) const { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
161
162    void fill(T* dst, ptrdiff_t count, const T& value = T{}) {
163        std::fill_n(dst, count, value);
164    }
165
166    template <std::input_iterator InputIterator>
167    void fill(T* dst, InputIterator first, InputIterator last) {
168        while (first != last) {
169            new(static_cast<void*>(dst)) T(*first);
170            ++dst;
171            ++first;
172        }
173    }
174
175public:
176    void assign(size_type n, const T& val) {
177        clear();
178        if (capacity() < n) {
179            change_capacity(n);
180        }
181        _size += n;
182        fill(item_ptr(0), n, val);
183    }
184
185    template <std::input_iterator InputIterator>
186    void assign(InputIterator first, InputIterator last) {
187        size_type n = last - first;
188        clear();
189        if (capacity() < n) {
190            change_capacity(n);
191        }
192        _size += n;
193        fill(item_ptr(0), first, last);
194    }
195
196    prevector() = default;
197
198    explicit prevector(size_type n) {
199        resize(n);
200    }
201
202    explicit prevector(size_type n, const T& val) {
203        change_capacity(n);
204        _size += n;
205        fill(item_ptr(0), n, val);
206    }
207
208    template <std::input_iterator InputIterator>
209    prevector(InputIterator first, InputIterator last) {
210        size_type n = last - first;
211        change_capacity(n);
212        _size += n;
213        fill(item_ptr(0), first, last);
214    }
215
216    prevector(const prevector<N, T, Size, Diff>& other) {
217        size_type n = other.size();
218        change_capacity(n);
219        _size += n;
220        fill(item_ptr(0), other.begin(),  other.end());
221    }
222
223    prevector(prevector<N, T, Size, Diff>&& other) noexcept
224        : _union(std::move(other._union)), _size(other._size)
225    {
226        other._size = 0;
227    }
228
229    prevector& operator=(const prevector<N, T, Size, Diff>& other) {
230        if (&other == this) {
231            return *this;
232        }
233        assign(other.begin(), other.end());
234        return *this;
235    }
236
237    prevector& operator=(prevector<N, T, Size, Diff>&& other) noexcept {
238        if (!is_direct()) {
239            free(_union.indirect_contents.indirect);
240        }
241        _union = std::move(other._union);
242        _size = other._size;
243        other._size = 0;
244        return *this;
245    }
246
247    size_type size() const {
248        return is_direct() ? _size : _size - N - 1;
249    }
250

src/wallet/receive.cpp

src/wallet/coinselection.cpp

src/consensus/validation.h

src/primitives/transaction.cpp

src/script/descriptor.cpp

src/bitcoin-cli.cpp

src/rpc/blockchain.cpp

src/rpc/rawtransaction.cpp

src/init.cpp

src/crypto/sha256.cpp

src/consensus/merkle.h

src/consensus/tx_check.h

src/consensus/tx_verify.h

src/policy/feerate.h

src/policy/feerate.cpp

src/primitives/transaction_identifier.h

src/chainparamsbase.h

src/chainparamsbase.cpp

src/util/moneystr.cpp

src/crypto/ripemd160.h

src/crypto/sha1.h

src/crypto/sha512.h

src/crypto/hmac_sha256.h

src/crypto/hmac_sha512.h

src/crypto/hmac_sha256.cpp

src/crypto/hmac_sha512.cpp

src/crypto/hkdf_sha256_32.h

src/crypto/hkdf_sha256_32.cpp

src/support/cleanse.h

src/support/cleanse.cpp

src/crypto/siphash.cpp

src/crypto/muhash.h

src/crypto/chacha20.h

src/crypto/poly1305.h

src/crypto/chacha20poly1305.h

src/crypto/chacha20poly1305.cpp

src/util/chaintype.cpp

src/util/obfuscation.h

src/util/byte_units.h

src/util/overflow.h

src/blockencodings.cpp

src/net_permissions.cpp

src/policy/packages.cpp

src/policy/rbf.cpp

src/policy/truc_policy.cpp

src/policy/ephemeral_policy.cpp

src/policy/settings.cpp

src/policy/policy.cpp

src/node/transaction.cpp

src/node/coin.cpp

src/rpc/client.cpp

src/rpc/external_signer.cpp

src/rpc/request.cpp

src/rpc/server_util.cpp

src/rpc/fees.cpp

src/rpc/output_script.cpp

src/rpc/rawtransaction_util.cpp

src/rpc/rawtransaction_util.h

src/rpc/register.h

src/rpc/request.h

src/rpc/server_util.h

src/rpc/protocol.h

src/rpc/server.h

src/rpc/signmessage.cpp

src/rpc/txoutproof.cpp

src/rpc/util.cpp

src/rpc/util.h

src/wallet/rpc/addresses.cpp

src/wallet/rpc/backup.cpp

src/wallet/rpc/coins.cpp

src/wallet/rpc/encrypt.cpp

src/wallet/rpc/signmessage.cpp

src/wallet/rpc/util.cpp

src/wallet/rpc/util.h

src/wallet/coincontrol.cpp

src/wallet/coincontrol.h

src/wallet/context.cpp

src/wallet/context.h

src/wallet/crypter.cpp

src/wallet/crypter.h

src/wallet/db.cpp

src/wallet/export.cpp

src/wallet/external_signer_scriptpubkeyman.cpp

src/wallet/rpc/spend.cpp

src/wallet/rpc/transactions.cpp

src/wallet/rpc/wallet.cpp

src/wallet/feebumper.cpp

src/wallet/feebumper.h

src/index/base.h

src/index/base.cpp

src/index/txindex.h

src/index/txindex.cpp

src/index/txindex_key.h

src/index/txospenderindex.h

src/index/txospenderindex.cpp

src/index/blockfilterindex.h

src/index/blockfilterindex.cpp

src/index/coinstatsindex.h

src/index/coinstatsindex.cpp

src/index/db_key.h

src/index/disktxpos.h

src/kernel/chain.cpp

src/kernel/chain.h

src/kernel/checks.cpp

src/kernel/checks.h

src/kernel/context.cpp

src/kernel/context.h

src/kernel/cs_main.cpp

src/kernel/cs_main.h

src/kernel/disconnected_transactions.cpp

src/kernel/disconnected_transactions.h

src/kernel/mempool_removal_reason.cpp

src/kernel/mempool_removal_reason.h

src/kernel/coinstats.cpp

src/kernel/coinstats.h

src/kernel/chainparams.cpp

src/kernel/chainparams.h

src/wallet/sqlite.cpp

src/wallet/sqlite.h

src/wallet/transaction.cpp

src/wallet/transaction.h

src/wallet/dump.cpp

src/wallet/dump.h

src/wallet/init.cpp

src/wallet/walletutil.cpp

src/wallet/walletutil.h

src/wallet/wallettool.cpp

src/wallet/wallettool.h

src/wallet/export.h

src/wallet/migrate.cpp

src/wallet/migrate.h

src/wallet/db.h

src/wallet/walletdb.cpp

src/wallet/interfaces.cpp

src/wallet/scriptpubkeyman.cpp

src/wallet/scriptpubkeyman.h

src/kernel/bitcoinkernel.cpp

src/kernel/bitcoinkernel.h

src/kernel/bitcoinkernel_wrapper.h

src/node/chainstate.cpp

src/node/chainstate.h

src/node/blockstorage.cpp

src/node/blockstorage.h

src/node/mempool_persist.cpp

src/node/mempool_persist.h

src/node/utxo_snapshot.cpp

src/node/utxo_snapshot.h

src/node/kernel_notifications.cpp

src/node/kernel_notifications.h

src/node/blockmanager_args.cpp

src/kernel/blockmanager_opts.h

src/util/expected.cpp

src/policy/settings.h

src/util/types.h

src/kernel/messagestartchars.h

src/kernel/warning.h

src/util/exception.h

src/common/license_info.h

src/node/coins_view_args.h

src/node/database_args.h

src/util/batchpriority.h

src/util/ui_change_type.h

src/node/coins_view_args.cpp

src/node/peerman_args.h

src/util/serfloat.h

src/node/blockmanager_args.h

src/node/database_args.cpp

src/util/overloaded.h

src/interfaces/types.h

src/node/chainstatemanager_args.h

src/node/minisketchwrapper.h

src/util/macros.h

src/util/syserror.h

src/common/run_command.h

src/util/bytevectorhash.cpp

src/node/mempool_persist_args.cpp

src/util/exec.h

src/util/rbf.h

src/crypto/hex_base.h

src/node/mempool_persist_args.h

src/interfaces/echo.h

src/util/any.h

src/util/batchpriority.cpp

src/util/threadnames.h

src/node/coin.h

src/node/mempool_args.h

src/util/asmap.h

src/util/bytevectorhash.h

src/node/context.cpp

src/util/insert.h

src/util/readwritefile.h

src/node/peerman_args.cpp

src/node/interface_ui.cpp

src/interfaces/handler.h

src/node/mining_args.h

src/util/hasher.cpp

src/common/init.h

src/kernel/mempool_limits.h

src/common/system.h

src/crypto/sha3.h

src/util/threadinterrupt.cpp

src/node/protocol_version.h

src/util/exception.cpp

src/common/messages.h

src/node/connection_types.cpp

src/util/bip32.h

src/common/license_info.cpp

src/util/stdmutex.h

src/common/run_command.cpp

src/util/check.cpp

src/util/golombrice.h

src/node/types.h

src/node/timeoffsets.h

src/util/readwritefile.cpp

src/util/fastrange.h

src/util/signalinterrupt.h

src/util/task_runner.h

src/util/syserror.cpp

src/common/interfaces.cpp

src/common/types.h

src/util/threadinterrupt.h

src/kernel/chainstatemanager_opts.h

src/node/psbt.h

src/policy/ephemeral_policy.h

src/util/trace.h

src/common/url.cpp

src/kernel/mempool_options.h

src/util/serfloat.cpp

src/kernel/notifications_interface.h

src/node/timeoffsets.cpp

src/node/warnings.cpp

src/util/hash_type.h

src/crypto/hex_base.cpp

src/node/eviction.h

src/util/tokenbucket.h

src/crypto/aes.h

src/common/pcp.h

src/util/feefrac.cpp

src/node/transaction.h

src/util/threadnames.cpp

src/common/signmessage.h

src/util/exec.cpp

src/util/signalinterrupt.cpp

Independent explanations by MyBitcoinExplorer. Not affiliated with or endorsed by Bitcoin Core. Guides are educational and do not replace the source or its tests.

Bitcoin Core source © its contributors, distributed under the MIT license. Original notices and bundled third-party licenses are retained in the source tree.