Bitcoin Core 29.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 <memory>
7#include <optional>
8#include <stdint.h>
9#include <vector>
10#include <utility>
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
64 virtual ~TxGraph() = default;
70 [[nodiscard]] virtual Ref AddTransaction(const FeePerWeight& feerate) noexcept = 0;
85 virtual void RemoveTransaction(const Ref& arg) noexcept = 0;
90 virtual void AddDependency(const Ref& parent, const Ref& child) noexcept = 0;
94 virtual void SetTransactionFee(const Ref& arg, int64_t fee) noexcept = 0;
95
99 virtual void DoWork() noexcept = 0;
100
105 virtual void StartStaging() noexcept = 0;
107 virtual void AbortStaging() noexcept = 0;
109 virtual void CommitStaging() noexcept = 0;
111 virtual bool HaveStaging() const noexcept = 0;
112
119 virtual bool IsOversized(bool main_only = false) noexcept = 0;
123 virtual bool Exists(const Ref& arg, bool main_only = false) noexcept = 0;
127 virtual FeePerWeight GetIndividualFeerate(const Ref& arg) noexcept = 0;
131 virtual FeePerWeight GetMainChunkFeerate(const Ref& arg) noexcept = 0;
136 virtual std::vector<Ref*> GetCluster(const Ref& arg, bool main_only = false) noexcept = 0;
141 virtual std::vector<Ref*> GetAncestors(const Ref& arg, bool main_only = false) noexcept = 0;
146 virtual std::vector<Ref*> GetDescendants(const Ref& arg, bool main_only = false) noexcept = 0;
150 virtual std::vector<Ref*> GetAncestorsUnion(std::span<const Ref* const> args, bool main_only = false) noexcept = 0;
154 virtual std::vector<Ref*> GetDescendantsUnion(std::span<const Ref* const> args, bool main_only = false) noexcept = 0;
158 virtual GraphIndex GetTransactionCount(bool main_only = false) noexcept = 0;
161 virtual std::strong_ordering CompareMainOrder(const Ref& a, const Ref& b) noexcept = 0;
166 virtual GraphIndex CountDistinctClusters(std::span<const Ref* const>, bool main_only = false) noexcept = 0;
171 virtual std::pair<std::vector<FeeFrac>, std::vector<FeeFrac>> GetMainStagingDiagrams() noexcept = 0;
172
175 {
176 protected:
178 BlockBuilder() noexcept = default;
179 public:
181 virtual ~BlockBuilder() = default;
183 virtual std::optional<std::pair<std::vector<Ref*>, FeePerWeight>> GetCurrentChunk() noexcept = 0;
185 virtual void Include() noexcept = 0;
188 virtual void Skip() noexcept = 0;
189 };
190
194 virtual std::unique_ptr<BlockBuilder> GetBlockBuilder() noexcept = 0;
199 virtual std::pair<std::vector<Ref*>, FeePerWeight> GetWorstMainChunk() noexcept = 0;
200
202 virtual void SanityCheck() const = 0;
203
204protected:
205 // Allow TxGraph::Ref to call UpdateRef and UnlinkRef.
206 friend class TxGraph::Ref;
208 virtual void UpdateRef(GraphIndex index, Ref& new_location) noexcept = 0;
210 virtual void UnlinkRef(GraphIndex index) noexcept = 0;
211 // Allow TxGraph implementations (inheriting from it) to access Ref internals.
212 static TxGraph*& GetRefGraph(Ref& arg) noexcept { return arg.m_graph; }
213 static TxGraph* GetRefGraph(const Ref& arg) noexcept { return arg.m_graph; }
214 static GraphIndex& GetRefIndex(Ref& arg) noexcept { return arg.m_index; }
215 static GraphIndex GetRefIndex(const Ref& arg) noexcept { return arg.m_index; }
216
217public:
218 class Ref
219 {
220 // Allow TxGraph's GetRefGraph and GetRefIndex to access internals.
221 friend class TxGraph;
223 TxGraph* m_graph = nullptr;
226 public:
229 Ref() noexcept = default;
232 virtual ~Ref();
233 // Support moving a Ref.
234 Ref& operator=(Ref&& other) noexcept;
235 Ref(Ref&& other) noexcept;
236 // Do not permit copy constructing or copy assignment. A TxGraph entry can have at most one
237 // Ref pointing to it.
238 Ref& operator=(const Ref&) = delete;
239 Ref(const Ref&) = delete;
240 };
241};
242
245std::unique_ptr<TxGraph> MakeTxGraph(unsigned max_cluster_count) noexcept;
246
247#endif // BITCOIN_TXGRAPH_H
ArgsManager & args
Definition: bitcoind.cpp:277
Interface returned by GetBlockBuilder.
Definition: txgraph.h:175
BlockBuilder() noexcept=default
Make constructor non-public (use TxGraph::GetBlockBuilder()).
TxGraph * m_graph
Which Graph the Entry lives in.
Definition: txgraph.h:223
GraphIndex m_index
Index into the Graph's m_entries.
Definition: txgraph.h:225
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.
static GraphIndex GetRefIndex(const Ref &arg) noexcept
Definition: txgraph.h:215
virtual Ref AddTransaction(const FeePerWeight &feerate) noexcept=0
Construct a new transaction with the specified feerate, and return a Ref to it.
virtual std::vector< Ref * > GetDescendantsUnion(std::span< const Ref *const > args, bool main_only=false) noexcept=0
Like GetDescendants, but return the Refs for all transactions in the union of the provided arguments'...
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:214
virtual std::vector< Ref * > GetAncestors(const Ref &arg, bool main_only=false) noexcept=0
Get pointers to all ancestors of the specified transaction (including the transaction itself),...
virtual void AddDependency(const Ref &parent, const Ref &child) noexcept=0
Add a dependency between two specified transactions.
virtual std::vector< Ref * > GetCluster(const Ref &arg, bool main_only=false) noexcept=0
Get pointers to all transactions in the cluster which arg is in.
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 GraphIndex CountDistinctClusters(std::span< const Ref *const >, bool main_only=false) noexcept=0
Count the number of distinct clusters that the specified transactions belong to.
virtual void StartStaging() noexcept=0
Create a staging graph (which cannot exist already).
virtual std::vector< Ref * > GetAncestorsUnion(std::span< const Ref *const > args, bool main_only=false) noexcept=0
Like GetAncestors, but return the Refs for all transactions in the union of the provided arguments' a...
virtual void DoWork() noexcept=0
TxGraph is internally lazy, and will not compute many things until they are needed.
virtual bool Exists(const Ref &arg, bool main_only=false) noexcept=0
Determine whether arg exists in the graph (i.e., was not removed).
virtual GraphIndex GetTransactionCount(bool main_only=false) noexcept=0
Get the total number of transactions in the graph.
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:213
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, bool main_only=false) 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 bool IsOversized(bool main_only=false) noexcept=0
Determine whether the graph is oversized (contains a connected component of more than the configured ...
virtual void RemoveTransaction(const Ref &arg) noexcept=0
Remove the specified transaction.
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:212
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 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:39
Tagged wrapper around FeeFrac to avoid unit confusion.
Definition: feefrac.h:238
std::unique_ptr< TxGraph > MakeTxGraph(unsigned max_cluster_count) noexcept
Construct a new TxGraph with the specified limit on transactions within a cluster.
Definition: txgraph.cpp:2503
static constexpr unsigned MAX_CLUSTER_COUNT_LIMIT
Definition: txgraph.h:17