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 server440 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.

104,128 bytes · SHA-256 c193753b288c587a… · View upstream ↗

1// Copyright (c) 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_CLUSTER_LINEARIZE_H
6#define BITCOIN_CLUSTER_LINEARIZE_H
7
8#include <algorithm>
9#include <cstdint>
10#include <numeric>
11#include <optional>
12#include <ranges>
13#include <utility>
14#include <vector>
15
16#include <attributes.h>
17#include <memusage.h>
18#include <random.h>
19#include <span.h>
20#include <util/feefrac.h>
21#include <util/vecdeque.h>
22
23namespace cluster_linearize {
24
25/** Data type to represent transaction indices in DepGraphs and the clusters they represent. */
26using DepGraphIndex = uint32_t;
27
28/** Data structure that holds a transaction graph's preprocessed data (fee, size, ancestors,
29 *  descendants). */
30template<typename SetType>
31class DepGraph
32{
33    /** Information about a single transaction. */
34    struct Entry
35    {
36        /** Fee and size of transaction itself. */
37        FeeFrac feerate;
38        /** All ancestors of the transaction (including itself). */
39        SetType ancestors;
40        /** All descendants of the transaction (including itself). */
41        SetType descendants;
42
43        /** Equality operator (primarily for testing purposes). */
44        friend bool operator==(const Entry&, const Entry&) noexcept = default;
45
46        /** Construct an empty entry. */
47        Entry() noexcept = default;
48        /** Construct an entry with a given feerate, ancestor set, descendant set. */
49        Entry(const FeeFrac& f, const SetType& a, const SetType& d) noexcept : feerate(f), ancestors(a), descendants(d) {}
50    };
51
52    /** Data for each transaction. */
53    std::vector<Entry> entries;
54
55    /** Which positions are used. */
56    SetType m_used;
57
58public:
59    /** Equality operator (primarily for testing purposes). */
60    friend bool operator==(const DepGraph& a, const DepGraph& b) noexcept
61    {
62        if (a.m_used != b.m_used) return false;
63        // Only compare the used positions within the entries vector.
64        for (auto idx : a.m_used) {
65            if (a.entries[idx] != b.entries[idx]) return false;
66        }
67        return true;
68    }
69
70    // Default constructors.
71    DepGraph() noexcept = default;
72    DepGraph(const DepGraph&) noexcept = default;
73    DepGraph(DepGraph&&) noexcept = default;
74    DepGraph& operator=(const DepGraph&) noexcept = default;
75    DepGraph& operator=(DepGraph&&) noexcept = default;
76
77    /** Construct a DepGraph object given another DepGraph and a mapping from old to new.
78     *
79     * @param depgraph   The original DepGraph that is being remapped.
80     *
81     * @param mapping    A span such that mapping[i] gives the position in the new DepGraph
82     *                   for position i in the old depgraph. Its size must be equal to
83     *                   depgraph.PositionRange(). The value of mapping[i] is ignored if
84     *                   position i is a hole in depgraph (i.e., if !depgraph.Positions()[i]).
85     *
86     * @param pos_range  The PositionRange() for the new DepGraph. It must equal the largest
87     *                   value in mapping for any used position in depgraph plus 1, or 0 if
88     *                   depgraph.TxCount() == 0.
89     *
90     * Complexity: O(N^2) where N=depgraph.TxCount().
91     */
92    DepGraph(const DepGraph<SetType>& depgraph, std::span<const DepGraphIndex> mapping, DepGraphIndex pos_range) noexcept : entries(pos_range)
93    {
94        Assume(mapping.size() == depgraph.PositionRange());
95        Assume((pos_range == 0) == (depgraph.TxCount() == 0));
96        for (DepGraphIndex i : depgraph.Positions()) {
97            auto new_idx = mapping[i];
98            Assume(new_idx < pos_range);
99            // Add transaction.
100            entries[new_idx].ancestors = SetType::Singleton(new_idx);
101            entries[new_idx].descendants = SetType::Singleton(new_idx);
102            m_used.Set(new_idx);
103            // Fill in fee and size.
104            entries[new_idx].feerate = depgraph.entries[i].feerate;
105        }
106        for (DepGraphIndex i : depgraph.Positions()) {
107            // Fill in dependencies by mapping direct parents.
108            SetType parents;
109            for (auto j : depgraph.GetReducedParents(i)) parents.Set(mapping[j]);
110            AddDependencies(parents, mapping[i]);
111        }
112        // Verify that the provided pos_range was correct (no unused positions at the end).
113        Assume(m_used.None() ? (pos_range == 0) : (pos_range == m_used.Last() + 1));
114    }
115
116    /** Get the set of transactions positions in use. Complexity: O(1). */
117    const SetType& Positions() const noexcept { return m_used; }
118    /** Get the range of positions in this DepGraph. All entries in Positions() are in [0, PositionRange() - 1]. */
119    DepGraphIndex PositionRange() const noexcept { return entries.size(); }
120    /** Get the number of transactions in the graph. Complexity: O(1). */
121    auto TxCount() const noexcept { return m_used.Count(); }
122    /** Get the feerate of a given transaction i. Complexity: O(1). */
123    const FeeFrac& FeeRate(DepGraphIndex i) const noexcept { return entries[i].feerate; }
124    /** Get the mutable feerate of a given transaction i. Complexity: O(1). */
125    FeeFrac& FeeRate(DepGraphIndex i) noexcept { return entries[i].feerate; }
126    /** Get the ancestors of a given transaction i. Complexity: O(1). */
127    const SetType& Ancestors(DepGraphIndex i) const noexcept { return entries[i].ancestors; }
128    /** Get the descendants of a given transaction i. Complexity: O(1). */
129    const SetType& Descendants(DepGraphIndex i) const noexcept { return entries[i].descendants; }
130
131    /** Add a new unconnected transaction to this transaction graph (in the first available
132     *  position), and return its DepGraphIndex.
133     *
134     * Complexity: O(1) (amortized, due to resizing of backing vector).
135     */
136    DepGraphIndex AddTransaction(const FeeFrac& feefrac) noexcept
137    {
138        static constexpr auto ALL_POSITIONS = SetType::Fill(SetType::Size());
139        auto available = ALL_POSITIONS - m_used;
140        Assume(available.Any());
141        DepGraphIndex new_idx = available.First();
142        if (new_idx == entries.size()) {
143            entries.emplace_back(feefrac, SetType::Singleton(new_idx), SetType::Singleton(new_idx));
144        } else {
145            entries[new_idx] = Entry(feefrac, SetType::Singleton(new_idx), SetType::Singleton(new_idx));
146        }
147        m_used.Set(new_idx);
148        return new_idx;
149    }
150
151    /** Remove the specified positions from this DepGraph.
152     *
153     * The specified positions will no longer be part of Positions(), and dependencies with them are
154     * removed. Note that due to DepGraph only tracking ancestors/descendants (and not direct
155     * dependencies), if a parent is removed while a grandparent remains, the grandparent will
156     * remain an ancestor.
157     *
158     * Complexity: O(N) where N=TxCount().
159     */
160    void RemoveTransactions(const SetType& del) noexcept
161    {
162        m_used -= del;
163        // Remove now-unused trailing entries.
164        while (!entries.empty() && !m_used[entries.size() - 1]) {
165            entries.pop_back();
166        }
167        // Remove the deleted transactions from ancestors/descendants of other transactions. Note
168        // that the deleted positions will retain old feerate and dependency information. This does
169        // not matter as they will be overwritten by AddTransaction if they get used again.
170        for (auto& entry : entries) {
171            entry.ancestors &= m_used;
172            entry.descendants &= m_used;
173        }
174    }
175
176    /** Modify this transaction graph, adding multiple parents to a specified child.
177     *
178     * Complexity: O(N) where N=TxCount().
179     */
180    void AddDependencies(const SetType& parents, DepGraphIndex child) noexcept
181    {
182        Assume(m_used[child]);
183        Assume(parents.IsSubsetOf(m_used));
184        // Compute the ancestors of parents that are not already ancestors of child.
185        SetType par_anc;
186        for (auto par : parents - Ancestors(child)) {
187            par_anc |= Ancestors(par);
188        }
189        par_anc -= Ancestors(child);
190        // Bail out if there are no such ancestors.
191        if (par_anc.None()) return;
192        // To each such ancestor, add as descendants the descendants of the child.
193        const auto& chl_des = entries[child].descendants;
194        for (auto anc_of_par : par_anc) {
195            entries[anc_of_par].descendants |= chl_des;
196        }
197        // To each descendant of the child, add those ancestors.
198        for (auto dec_of_chl : Descendants(child)) {
199            entries[dec_of_chl].ancestors |= par_anc;
200        }
201    }
202
203    /** Compute the (reduced) set of parents of node i in this graph.
204     *
205     * This returns the minimal subset of the parents of i whose ancestors together equal all of
206     * i's ancestors (unless i is part of a cycle of dependencies). Note that DepGraph does not
207     * store the set of parents; this information is inferred from the ancestor sets.
208     *
209     * Complexity: O(N) where N=Ancestors(i).Count() (which is bounded by TxCount()).
210     */
211    SetType GetReducedParents(DepGraphIndex i) const noexcept
212    {
213        SetType parents = Ancestors(i);
214        parents.Reset(i);
215        for (auto parent : parents) {
216            if (parents[parent]) {
217                parents -= Ancestors(parent);
218                parents.Set(parent);
219            }
220        }
221        return parents;
222    }
223
224    /** Compute the (reduced) set of children of node i in this graph.
225     *
226     * This returns the minimal subset of the children of i whose descendants together equal all of
227     * i's descendants (unless i is part of a cycle of dependencies). Note that DepGraph does not
228     * store the set of children; this information is inferred from the descendant sets.
229     *
230     * Complexity: O(N) where N=Descendants(i).Count() (which is bounded by TxCount()).
231     */
232    SetType GetReducedChildren(DepGraphIndex i) const noexcept
233    {
234        SetType children = Descendants(i);
235        children.Reset(i);
236        for (auto child : children) {
237            if (children[child]) {
238                children -= Descendants(child);
239                children.Set(child);
240            }
241        }
242        return children;
243    }
244
245    /** Compute the aggregate feerate of a set of nodes in this graph.
246     *
247     * Complexity: O(N) where N=elems.Count().
248     **/
249    FeeFrac FeeRate(const SetType& elems) const noexcept
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

src/clientversion.cpp

src/common/signmessage.cpp

src/compat/assumptions.h

src/compat/byteswap.h

src/deploymentinfo.cpp

src/deploymentinfo.h

src/deploymentstatus.cpp

src/deploymentstatus.h

src/dummywallet.cpp

src/external_signer.h

src/init/bitcoin-gui.cpp

src/init/bitcoin-node.cpp

src/init/bitcoin-qt.cpp

src/init/bitcoin-wallet.cpp

src/init/bitcoind.cpp

src/init/common.h

src/interfaces/init.h

src/interfaces/ipc.h

src/key_io.h

src/logging/categories.h

src/logging/timer.h

src/mapport.h

src/musig.h

src/net_permissions.h

src/netgroup.h

src/netmessagemaker.h

src/node/chainstatemanager_args.cpp

src/node/connection_types.h

src/node/context.h

src/node/interface_ui.h

src/node/mempool_args.cpp

src/node/mining_args.cpp

src/node/minisketchwrapper.cpp

src/node/txreconciliation.h

src/policy/fees/estimator_args.cpp

src/policy/fees/estimator_args.h

src/policy/fees/estimator_man.cpp

src/policy/fees/estimator_man.h

src/policy/packages.h

src/policy/rbf.h

src/policy/truc_policy.h

src/pow.h

src/primitives/block.cpp

src/randomenv.h

src/rest.h

src/script/keyorigin.h

src/script/parsing.cpp

src/script/parsing.h

src/script/script_error.h

src/script/sigcache.cpp

src/script/sigcache.h

src/script/solver.h

src/script/verify_flags.h

src/semaphore_grant.h

src/signet.h

src/span.h

src/support/allocators/secure.h

src/support/allocators/zeroafterfree.h

src/util/tokenpipe.cpp

src/util/translation.h

src/util/vector.h

src/versionbits.h

src/versionbits_impl.h

src/wallet/external_signer_scriptpubkeyman.h

src/wallet/fees.h

src/wallet/load.h

src/wallet/receive.h

src/wallet/rpc/wallet.h

src/wallet/types.h

src/walletinitinterface.h

src/zmq/zmqabstractnotifier.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.