Bitcoin Core 30.99.0
P2P Digital Currency
txgraph.h
Go to the documentation of this file.
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#include <compare>
6#include <cstdint>
7#include <memory>
8#include <optional>
9#include <utility>
10#include <vector>
11
12#include <util/feefrac.h>
13
14#ifndef BITCOIN_TXGRAPH_H
15#define BITCOIN_TXGRAPH_H
16
17static constexpr unsigned MAX_CLUSTER_COUNT_LIMIT{64};
18
47{
48public:
50 using GraphIndex = uint32_t;
51
61 class Ref;
62
63 enum class Level {
64 TOP,
65 MAIN
66 };
67
69 virtual ~TxGraph() = default;
75 [[nodiscard]] virtual Ref AddTransaction(const FeePerWeight& feerate) noexcept = 0;
90 virtual void RemoveTransaction(const Ref& arg) noexcept = 0;
95 virtual void AddDependency(const Ref& parent, const Ref& child) noexcept = 0;
99 virtual void SetTransactionFee(const Ref& arg, int64_t fee) noexcept = 0;
100
105 virtual bool DoWork(uint64_t iters) noexcept = 0;
106
111 virtual void StartStaging() noexcept = 0;
113 virtual void AbortStaging() noexcept = 0;
115 virtual void CommitStaging() noexcept = 0;
117 virtual bool HaveStaging() const noexcept = 0;
118
124 virtual bool IsOversized(Level level) noexcept = 0;
127 virtual bool Exists(const Ref& arg, Level level) noexcept = 0;
131 virtual FeePerWeight GetIndividualFeerate(const Ref& arg) noexcept = 0;
135 virtual FeePerWeight GetMainChunkFeerate(const Ref& arg) noexcept = 0;
139 virtual std::vector<Ref*> GetCluster(const Ref& arg, Level level) noexcept = 0;
143 virtual std::vector<Ref*> GetAncestors(const Ref& arg, Level level) noexcept = 0;
147 virtual std::vector<Ref*> GetDescendants(const Ref& arg, Level level) noexcept = 0;
151 virtual std::vector<Ref*> GetAncestorsUnion(std::span<const Ref* const> args, Level level) noexcept = 0;
155 virtual std::vector<Ref*> GetDescendantsUnion(std::span<const Ref* const> args, Level level) noexcept = 0;
158 virtual GraphIndex GetTransactionCount(Level level) noexcept = 0;
161 virtual std::strong_ordering CompareMainOrder(const Ref& a, const Ref& b) noexcept = 0;
165 virtual GraphIndex CountDistinctClusters(std::span<const Ref* const>, Level level) noexcept = 0;
170 virtual std::pair<std::vector<FeeFrac>, std::vector<FeeFrac>> GetMainStagingDiagrams() noexcept = 0;
175 virtual std::vector<Ref*> Trim() noexcept = 0;
176
179 {
180 protected:
182 BlockBuilder() noexcept = default;
183 public:
185 virtual ~BlockBuilder() = default;
187 virtual std::optional<std::pair<std::vector<Ref*>, FeePerWeight>> GetCurrentChunk() noexcept = 0;
189 virtual void Include() noexcept = 0;
192 virtual void Skip() noexcept = 0;
193 };
194
198 virtual std::unique_ptr<BlockBuilder> GetBlockBuilder() noexcept = 0;
203 virtual std::pair<std::vector<Ref*>, FeePerWeight> GetWorstMainChunk() noexcept = 0;
204
206 virtual void SanityCheck() const = 0;
207
208protected:
209 // Allow TxGraph::Ref to call UpdateRef and UnlinkRef.
210 friend class TxGraph::Ref;
212 virtual void UpdateRef(GraphIndex index, Ref& new_location) noexcept = 0;
214 virtual void UnlinkRef(GraphIndex index) noexcept = 0;
215 // Allow TxGraph implementations (inheriting from it) to access Ref internals.
216 static TxGraph*& GetRefGraph(Ref& arg) noexcept { return arg.m_graph; }
217 static TxGraph* GetRefGraph(const Ref& arg) noexcept { return arg.m_graph; }
218 static GraphIndex& GetRefIndex(Ref& arg) noexcept { return arg.m_index; }
219 static GraphIndex GetRefIndex(const Ref& arg) noexcept { return arg.m_index; }
220
221public:
222 class Ref
223 {
224 // Allow TxGraph's GetRefGraph and GetRefIndex to access internals.
225 friend class TxGraph;
227 TxGraph* m_graph = nullptr;
230 public:
233 Ref() noexcept = default;
236 virtual ~Ref();
237 // Support moving a Ref.
238 Ref& operator=(Ref&& other) noexcept;
239 Ref(Ref&& other) noexcept;
240 // Do not permit copy constructing or copy assignment. A TxGraph entry can have at most one
241 // Ref pointing to it.
242 Ref& operator=(const Ref&) = delete;
243 Ref(const Ref&) = delete;
244 };
245};
246
251std::unique_ptr<TxGraph> MakeTxGraph(unsigned max_cluster_count, uint64_t max_cluster_size, uint64_t acceptable_iters) noexcept;
252
253#endif // BITCOIN_TXGRAPH_H
ArgsManager & args
Definition: bitcoind.cpp:277
Interface returned by GetBlockBuilder.
Definition: txgraph.h:179
BlockBuilder() noexcept=default
Make constructor non-public (use TxGraph::GetBlockBuilder()).
TxGraph * m_graph
Which Graph the Entry lives in.
Definition: txgraph.h:227
GraphIndex m_index
Index into the Graph's m_entries.
Definition: txgraph.h:229
Ref() noexcept=default
Construct an empty Ref.
Data structure to encapsulate fees, sizes, and dependencies for a set of transactions.
Definition: txgraph.h:47
virtual void UpdateRef(GraphIndex index, Ref &new_location) noexcept=0
Inform the TxGraph implementation that a TxGraph::Ref has moved.
virtual std::vector< Ref * > GetDescendantsUnion(std::span< const Ref *const > args, Level level) noexcept=0
Like GetDescendants, but return the Refs for all transactions in the union of the provided arguments'...
static GraphIndex GetRefIndex(const Ref &arg) noexcept
Definition: txgraph.h:219
virtual Ref AddTransaction(const FeePerWeight &feerate) noexcept=0
Construct a new transaction with the specified feerate, and return a Ref to it.
virtual GraphIndex CountDistinctClusters(std::span< const Ref *const >, Level level) noexcept=0
Count the number of distinct clusters that the specified transactions belong to.
virtual bool Exists(const Ref &arg, Level level) noexcept=0
Determine whether arg exists in the graph (i.e., was not removed).
virtual void SetTransactionFee(const Ref &arg, int64_t fee) noexcept=0
Modify the fee of the specified transaction, in both the main graph and the staging graph if it exist...
static GraphIndex & GetRefIndex(Ref &arg) noexcept
Definition: txgraph.h:218
virtual std::vector< Ref * > GetCluster(const Ref &arg, Level level) noexcept=0
Get pointers to all transactions in the cluster which arg is in.
virtual GraphIndex GetTransactionCount(Level level) noexcept=0
Get the total number of transactions in the graph.
virtual void AddDependency(const Ref &parent, const Ref &child) noexcept=0
Add a dependency between two specified transactions.
virtual std::pair< std::vector< Ref * >, FeePerWeight > GetWorstMainChunk() noexcept=0
Get the last chunk in the main graph, i.e., the last chunk that would be returned by a BlockBuilder c...
virtual void StartStaging() noexcept=0
Create a staging graph (which cannot exist already).
virtual std::vector< Ref * > GetAncestors(const Ref &arg, Level level) noexcept=0
Get pointers to all ancestors of the specified transaction (including the transaction itself),...
virtual bool DoWork(uint64_t iters) noexcept=0
TxGraph is internally lazy, and will not compute many things until they are needed.
virtual void CommitStaging() noexcept=0
Replace the main graph with the staging graph (which must exist).
virtual bool HaveStaging() const noexcept=0
Check whether a staging graph exists.
static TxGraph * GetRefGraph(const Ref &arg) noexcept
Definition: txgraph.h:217
virtual FeePerWeight GetMainChunkFeerate(const Ref &arg) noexcept=0
Get the feerate of the chunk which transaction arg is in, in the main graph.
virtual std::vector< Ref * > GetDescendants(const Ref &arg, Level level) noexcept=0
Get pointers to all descendants of the specified transaction (including the transaction itself),...
virtual void SanityCheck() const =0
Perform an internal consistency check on this object.
virtual std::vector< Ref * > Trim() noexcept=0
Remove transactions (including their own descendants) according to a fast but best-effort strategy su...
virtual void RemoveTransaction(const Ref &arg) noexcept=0
Remove the specified transaction.
virtual std::vector< Ref * > GetAncestorsUnion(std::span< const Ref *const > args, Level level) noexcept=0
Like GetAncestors, but return the Refs for all transactions in the union of the provided arguments' a...
virtual std::pair< std::vector< FeeFrac >, std::vector< FeeFrac > > GetMainStagingDiagrams() noexcept=0
For both main and staging (which must both exist and not be oversized), return the combined respectiv...
virtual FeePerWeight GetIndividualFeerate(const Ref &arg) noexcept=0
Get the individual transaction feerate of transaction arg.
virtual ~TxGraph()=default
Virtual destructor, so inheriting is safe.
static TxGraph *& GetRefGraph(Ref &arg) noexcept
Definition: txgraph.h:216
uint32_t GraphIndex
Internal identifier for a transaction within a TxGraph.
Definition: txgraph.h:50
virtual std::strong_ordering CompareMainOrder(const Ref &a, const Ref &b) noexcept=0
Compare two transactions according to their order in the main graph.
virtual void AbortStaging() noexcept=0
Discard the existing active staging graph (which must exist).
virtual std::unique_ptr< BlockBuilder > GetBlockBuilder() noexcept=0
Construct a block builder, drawing chunks in order, from the main graph, which cannot be oversized.
virtual bool IsOversized(Level level) noexcept=0
Determine whether the graph is oversized (contains a connected component of more than the configured ...
virtual void UnlinkRef(GraphIndex index) noexcept=0
Inform the TxGraph implementation that a TxGraph::Ref was destroyed.
uint64_t fee
Data structure storing a fee and size, ordered by increasing fee/size.
Definition: feefrac.h:40
Tagged wrapper around FeeFrac to avoid unit confusion.
Definition: feefrac.h:239
static constexpr unsigned MAX_CLUSTER_COUNT_LIMIT
Definition: txgraph.h:17
std::unique_ptr< TxGraph > MakeTxGraph(unsigned max_cluster_count, uint64_t max_cluster_size, uint64_t acceptable_iters) noexcept
Construct a new TxGraph with the specified limit on the number of transactions within a cluster,...
Definition: txgraph.cpp:2943