Data structure to encapsulate fees, sizes, and dependencies for a set of transactions. More...

#include <txgraph.h>

Classes
class	Ref

Public Types
using	GraphIndex = uint32_t
	Internal identifier for a transaction within a TxGraph. More...

Public Member Functions
virtual	~TxGraph ()=default
	Virtual destructor, so inheriting is safe. More...

virtual Ref	AddTransaction (const FeePerWeight &feerate) noexcept=0
	Construct a new transaction with the specified feerate, and return a Ref to it. More...

virtual void	RemoveTransaction (const Ref &arg) noexcept=0
	Remove the specified transaction. More...

virtual void	AddDependency (const Ref &parent, const Ref &child) noexcept=0
	Add a dependency between two specified transactions. More...

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 exists. More...

virtual void	DoWork () noexcept=0
	TxGraph is internally lazy, and will not compute many things until they are needed. More...

virtual void	StartStaging () noexcept=0
	Create a staging graph (which cannot exist already). More...

virtual void	AbortStaging () noexcept=0
	Discard the existing active staging graph (which must exist). More...

virtual void	CommitStaging () noexcept=0
	Replace the main graph with the staging graph (which must exist). More...

virtual bool	HaveStaging () const noexcept=0
	Check whether a staging graph exists. More...

virtual bool	IsOversized (bool main_only=false) noexcept=0
	Determine whether the graph is oversized (contains a connected component of more than the configured maximum cluster count). More...

virtual bool	Exists (const Ref &arg, bool main_only=false) noexcept=0
	Determine whether arg exists in the graph (i.e., was not removed). More...

virtual FeePerWeight	GetIndividualFeerate (const Ref &arg) noexcept=0
	Get the individual transaction feerate of transaction arg. More...

virtual FeePerWeight	GetMainChunkFeerate (const Ref &arg) noexcept=0
	Get the feerate of the chunk which transaction arg is in, in the main graph. More...

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

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), in unspecified order. More...

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), in unspecified order. More...

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' ancestors (each transaction is only reported once). More...

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' descendants (each transaction is only reported once). More...

virtual GraphIndex	GetTransactionCount (bool main_only=false) noexcept=0
	Get the total number of transactions in the graph. More...

virtual std::strong_ordering	CompareMainOrder (const Ref &a, const Ref &b) noexcept=0
	Compare two transactions according to their order in the main graph. More...

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

virtual void	SanityCheck () const =0
	Perform an internal consistency check on this object. More...

Protected Member Functions
virtual void	UpdateRef (GraphIndex index, Ref &new_location) noexcept=0
	Inform the TxGraph implementation that a TxGraph::Ref has moved. More...

virtual void	UnlinkRef (GraphIndex index) noexcept=0
	Inform the TxGraph implementation that a TxGraph::Ref was destroyed. More...

Static Protected Member Functions
static TxGraph *&	GetRefGraph (Ref &arg) noexcept

static TxGraph *	GetRefGraph (const Ref &arg) noexcept

static GraphIndex &	GetRefIndex (Ref &arg) noexcept

static GraphIndex	GetRefIndex (const Ref &arg) noexcept

Friends
class	TxGraph::Ref

Detailed Description

Data structure to encapsulate fees, sizes, and dependencies for a set of transactions.

Each TxGraph represents one or two such graphs ("main", and optionally "staging"), to allow for working with batches of changes that may still be discarded.

The connected components within each transaction graph are called clusters: whenever one transaction is reachable from another, through any sequence of is-parent-of or is-child-of relations, they belong to the same cluster (so clusters include parents, children, but also grandparents, siblings, cousins twice removed, ...).

For each graph, TxGraph implicitly defines an associated total ordering on its transactions (its linearization) that respects topology (parents go before their children), aiming for it to be close to the optimal order those transactions should be mined in if the goal is fee maximization, though this is a best effort only, not a strong guarantee.

For more explanation, see https://delvingbitcoin.org/t/introduction-to-cluster-linearization/1032

This linearization is partitioned into chunks: groups of transactions that according to this order would be mined together. Each chunk consists of the highest-feerate prefix of what remains of the linearization after removing previous chunks. TxGraph guarantees that the maintained linearization always results in chunks consisting of transactions that are connected. A chunk's transactions always belong to the same cluster.

The interface is designed to accommodate an implementation that only stores the transitive closure of dependencies, so if B spends C, it does not distinguish between "A spending B" and "A spending both B and C".

Definition at line 44 of file txgraph.h.

Member Typedef Documentation

◆ GraphIndex

using TxGraph::GraphIndex = uint32_t

Internal identifier for a transaction within a TxGraph.

Definition at line 48 of file txgraph.h.

Constructor & Destructor Documentation

◆ ~TxGraph()

virtual TxGraph::~TxGraph ( )

virtualdefault

Virtual destructor, so inheriting is safe.

Member Function Documentation

◆ AbortStaging()

virtual void TxGraph::AbortStaging ( )

pure virtualnoexcept

Discard the existing active staging graph (which must exist).

◆ AddDependency()

virtual void TxGraph::AddDependency	(	const Ref &	parent,
		const Ref &	child
	)

pure virtualnoexcept

Add a dependency between two specified transactions.

If a staging graph exists, the dependency is only added there. Parent may not be a descendant of child already (but may be an ancestor of it already, in which case this is a no-op). If either transaction is already removed, this is a no-op.

◆ AddTransaction()

virtual Ref TxGraph::AddTransaction ( const FeePerWeight & feerate )

pure virtualnoexcept

Construct a new transaction with the specified feerate, and return a Ref to it.

If a staging graph exists, the new transaction is only created there. In all further calls, only Refs created by AddTransaction() are allowed to be passed to this TxGraph object (or empty Ref objects). Ref objects may outlive the TxGraph they were created for.

◆ CommitStaging()

virtual void TxGraph::CommitStaging ( )

pure virtualnoexcept

Replace the main graph with the staging graph (which must exist).

◆ CompareMainOrder()

virtual std::strong_ordering TxGraph::CompareMainOrder	(	const Ref &	a,
		const Ref &	b
	)

pure virtualnoexcept

Compare two transactions according to their order in the main graph.

Both transactions must be in the main graph. The main graph must not be oversized.

◆ CountDistinctClusters()

virtual GraphIndex TxGraph::CountDistinctClusters	(	std::span< const Ref *const >	,
		bool	main_only = `false`
	)

pure virtualnoexcept

Count the number of distinct clusters that the specified transactions belong to.

If main_only is false and a staging graph exists, staging clusters are counted. Otherwise, main clusters are counted. Refs that do not exist in the queried graph are ignored. Refs can not be null. The queried graph must not be oversized.

◆ DoWork()

virtual void TxGraph::DoWork ( )

pure virtualnoexcept

TxGraph is internally lazy, and will not compute many things until they are needed.

Calling DoWork will compute everything now, so that future operations are fast. This can be invoked while oversized.

◆ Exists()

virtual bool TxGraph::Exists	(	const Ref &	arg,
		bool	main_only = `false`
	)

pure virtualnoexcept

Determine whether arg exists in the graph (i.e., was not removed).

If main_only is false and a staging graph exists, it is queried; otherwise the main graph is queried. This is available even for oversized graphs.

◆ GetAncestors()

virtual std::vector< Ref * > TxGraph::GetAncestors	(	const Ref &	arg,
		bool	main_only = `false`
	)

pure virtualnoexcept

Get pointers to all ancestors of the specified transaction (including the transaction itself), in unspecified order.

If main_only is false and a staging graph exists, it is queried; otherwise the main graph is queried. The queried graph must not be oversized. Returns {} if arg does not exist in the graph.

◆ GetAncestorsUnion()

virtual std::vector< Ref * > TxGraph::GetAncestorsUnion	(	std::span< const Ref *const >	args,
		bool	main_only = `false`
	)

pure virtualnoexcept

Like GetAncestors, but return the Refs for all transactions in the union of the provided arguments' ancestors (each transaction is only reported once).

Refs that do not exist in the queried graph are ignored. Null refs are not allowed.

◆ GetCluster()

virtual std::vector< Ref * > TxGraph::GetCluster	(	const Ref &	arg,
		bool	main_only = `false`
	)

pure virtualnoexcept

Get pointers to all transactions in the cluster which arg is in.

The transactions are returned in graph order. If main_only is false and a staging graph exists, it is queried; otherwise the main graph is queried. The queried graph must not be oversized. Returns {} if arg does not exist in the queried graph.

◆ GetDescendants()

virtual std::vector< Ref * > TxGraph::GetDescendants	(	const Ref &	arg,
		bool	main_only = `false`
	)

pure virtualnoexcept

Get pointers to all descendants of the specified transaction (including the transaction itself), in unspecified order.

If main_only is false and a staging graph exists, it is queried; otherwise the main graph is queried. The queried graph must not be oversized. Returns {} if arg does not exist in the graph.

◆ GetDescendantsUnion()

virtual std::vector< Ref * > TxGraph::GetDescendantsUnion	(	std::span< const Ref *const >	args,
		bool	main_only = `false`
	)

pure virtualnoexcept

Like GetDescendants, but return the Refs for all transactions in the union of the provided arguments' descendants (each transaction is only reported once).

Refs that do not exist in the queried graph are ignored. Null refs are not allowed.

◆ GetIndividualFeerate()

virtual FeePerWeight TxGraph::GetIndividualFeerate ( const Ref & arg )

pure virtualnoexcept

Get the individual transaction feerate of transaction arg.

Returns the empty FeePerWeight if arg does not exist in either main or staging. This is available even for oversized graphs.

◆ GetMainChunkFeerate()

virtual FeePerWeight TxGraph::GetMainChunkFeerate ( const Ref & arg )

pure virtualnoexcept

Get the feerate of the chunk which transaction arg is in, in the main graph.

Returns the empty FeePerWeight if arg does not exist in the main graph. The main graph must not be oversized.

◆ GetRefGraph() [1/2]

static TxGraph * TxGraph::GetRefGraph ( const Ref & arg )

inlinestaticprotectednoexcept

Definition at line 178 of file txgraph.h.

◆ GetRefGraph() [2/2]

static TxGraph *& TxGraph::GetRefGraph ( Ref & arg )

inlinestaticprotectednoexcept

Definition at line 177 of file txgraph.h.

◆ GetRefIndex() [1/2]

static GraphIndex TxGraph::GetRefIndex ( const Ref & arg )

inlinestaticprotectednoexcept

Definition at line 180 of file txgraph.h.

◆ GetRefIndex() [2/2]

static GraphIndex & TxGraph::GetRefIndex ( Ref & arg )

inlinestaticprotectednoexcept

Definition at line 179 of file txgraph.h.

◆ GetTransactionCount()

virtual GraphIndex TxGraph::GetTransactionCount ( bool main_only = false )

pure virtualnoexcept

Get the total number of transactions in the graph.

If main_only is false and a staging graph exists, it is queried; otherwise the main graph is queried. This is available even for oversized graphs.

◆ HaveStaging()

virtual bool TxGraph::HaveStaging ( ) const

pure virtualnoexcept

Check whether a staging graph exists.

◆ IsOversized()

virtual bool TxGraph::IsOversized ( bool main_only = false )

pure virtualnoexcept

Determine whether the graph is oversized (contains a connected component of more than the configured maximum cluster count).

If main_only is false and a staging graph exists, it is queried; otherwise the main graph is queried. Some of the functions below are not available for oversized graphs. The mutators above are always available. Removing a transaction by destroying its Ref while staging exists will not clear main's oversizedness until staging is aborted or committed.

◆ RemoveTransaction()

virtual void TxGraph::RemoveTransaction ( const Ref & arg )

pure virtualnoexcept

Remove the specified transaction.

If a staging graph exists, the removal only happens there. This is a no-op if the transaction was already removed.

TxGraph may internally reorder transaction removals with dependency additions for performance reasons. If together with any transaction removal all its descendants, or all its ancestors, are removed as well (which is what always happens in realistic scenarios), this reordering will not affect the behavior of TxGraph.

As an example, imagine 3 transactions A,B,C where B depends on A. If a dependency of C on B is added, and then B is deleted, C will still depend on A. If the deletion of B is reordered before the C->B dependency is added, the dependency adding has no effect. If, together with the deletion of B also either A or C is deleted, there is no distinction between the original order case and the reordered case.

◆ SanityCheck()

virtual void TxGraph::SanityCheck ( ) const

pure virtual

Perform an internal consistency check on this object.

◆ SetTransactionFee()

virtual void TxGraph::SetTransactionFee	(	const Ref &	arg,
		int64_t	fee
	)

pure virtualnoexcept

Modify the fee of the specified transaction, in both the main graph and the staging graph if it exists.

Wherever the transaction does not exist (or was removed), this has no effect.

◆ StartStaging()

virtual void TxGraph::StartStaging ( )

pure virtualnoexcept

Create a staging graph (which cannot exist already).

This acts as if a full copy of the transaction graph is made, upon which further modifications are made. This copy can be inspected, and then either discarded, or the main graph can be replaced by it by committing it.

◆ UnlinkRef()

virtual void TxGraph::UnlinkRef ( GraphIndex index )

protectedpure virtualnoexcept

Inform the TxGraph implementation that a TxGraph::Ref was destroyed.

◆ UpdateRef()

virtual void TxGraph::UpdateRef	(	GraphIndex	index,
		Ref &	new_location
	)

protectedpure virtualnoexcept

Inform the TxGraph implementation that a TxGraph::Ref has moved.

Here is the caller graph for this function:

Friends And Related Function Documentation

◆ TxGraph::Ref

friend class TxGraph::Ref

friend

Definition at line 171 of file txgraph.h.

The documentation for this class was generated from the following file:

src/txgraph.h

Classes

Public Types

Public Member Functions

Protected Member Functions

Static Protected Member Functions

Friends

Detailed Description

Member Typedef Documentation

◆ GraphIndex

Constructor & Destructor Documentation

◆ ~TxGraph()

Member Function Documentation

◆ AbortStaging()

◆ AddDependency()

◆ AddTransaction()

◆ CommitStaging()

◆ CompareMainOrder()

◆ CountDistinctClusters()

◆ DoWork()

◆ Exists()

◆ GetAncestors()

◆ GetAncestorsUnion()

◆ GetCluster()

◆ GetDescendants()

◆ GetDescendantsUnion()

◆ GetIndividualFeerate()

◆ GetMainChunkFeerate()

◆ GetRefGraph() [1/2]

◆ GetRefGraph() [2/2]

◆ GetRefIndex() [1/2]

◆ GetRefIndex() [2/2]

◆ GetTransactionCount()

◆ HaveStaging()

◆ IsOversized()

◆ RemoveTransaction()

◆ SanityCheck()

◆ SetTransactionFee()

◆ StartStaging()

◆ UnlinkRef()

◆ UpdateRef()

Friends And Related Function Documentation

◆ TxGraph::Ref