cluster_linearize Namespace Reference

Classes
class	AncestorCandidateFinder
	Class encapsulating the state needed to find the best remaining ancestor set. More...
class	DepGraph
	Data structure that holds a transaction graph's preprocessed data (fee, size, ancestors, descendants). More...
class	LinearizationChunking
	Data structure encapsulating the chunking of a linearization, permitting removal of subsets. More...
class	SearchCandidateFinder
	Class encapsulating the state needed to perform search for good candidate sets. More...
struct	SetInfo
	A set of transactions together with their aggregate feerate. More...

Typedefs
using	ClusterIndex = uint32_t
	Data type to represent transaction indices in clusters. More...

Functions
template<typename SetType >
std::vector< FeeFrac >	ChunkLinearization (const DepGraph< SetType > &depgraph, Span< const ClusterIndex > linearization) noexcept
	Compute the feerates of the chunks of linearization. More...
template<typename SetType >
std::pair< std::vector< ClusterIndex >, bool >	Linearize (const DepGraph< SetType > &depgraph, uint64_t max_iterations, uint64_t rng_seed, Span< const ClusterIndex > old_linearization={}) noexcept
	Find or improve a linearization for a cluster. More...
template<typename SetType >
void	PostLinearize (const DepGraph< SetType > &depgraph, Span< ClusterIndex > linearization)
	Improve a given linearization. More...
template<typename SetType >
std::vector< ClusterIndex >	MergeLinearizations (const DepGraph< SetType > &depgraph, Span< const ClusterIndex > lin1, Span< const ClusterIndex > lin2)
	Merge two linearizations for the same cluster into one that is as good as both. More...

Typedef Documentation

ClusterIndex

using cluster_linearize::ClusterIndex = typedef uint32_t

Data type to represent transaction indices in clusters.

Definition at line 23 of file cluster_linearize.h.

Function Documentation

ChunkLinearization()

template<typename SetType >

std::vector< FeeFrac > cluster_linearize::ChunkLinearization ( const DepGraph< SetType > &  depgraph, Span< const ClusterIndex >  linearization  )

noexcept

Compute the feerates of the chunks of linearization.

The new chunk to be added, initially a singleton.

Definition at line 374 of file cluster_linearize.h.

Here is the caller graph for this function:

Linearize()

template<typename SetType >

std::pair< std::vector< ClusterIndex >, bool > cluster_linearize::Linearize ( const DepGraph< SetType > &  depgraph, uint64_t  max_iterations, uint64_t  rng_seed, Span< const ClusterIndex >  old_linearization = {}  )

noexcept

Find or improve a linearization for a cluster.

Parameters

[in]	depgraph	Dependency graph of the cluster to be linearized.
[in]	max_iterations	Upper bound on the number of optimization steps that will be done.
[in]	rng_seed	A random number seed to control search order. This prevents peers from predicting exactly which clusters would be hard for us to linearize.
[in]	old_linearization	An existing linearization for the cluster (which must be topologically valid), or empty.

Returns

A pair of:

• The resulting linearization. It is guaranteed to be at least as good (in the feerate diagram sense) as old_linearization.
• A boolean indicating whether the result is guaranteed to be optimal.

Complexity: possibly O(N * min(max_iterations + N, sqrt(2^N))) where N=depgraph.TxCount().

Chunking of what remains of the old linearization.

Definition at line 1019 of file cluster_linearize.h.

Here is the caller graph for this function:

MergeLinearizations()

template<typename SetType >

std::vector< ClusterIndex > cluster_linearize::MergeLinearizations	(	const DepGraph< SetType > &	depgraph,
		Span< const ClusterIndex >	lin1,
		Span< const ClusterIndex >	lin2
	)

Merge two linearizations for the same cluster into one that is as good as both.

Complexity: O(N^2) where N=depgraph.TxCount(); O(N) if both inputs are identical.

Chunkings of what remains of both input linearizations.

Output linearization.

Definition at line 1302 of file cluster_linearize.h.

Here is the call graph for this function:

Here is the caller graph for this function:

PostLinearize()

template<typename SetType >

void cluster_linearize::PostLinearize	(	const DepGraph< SetType > &	depgraph,
		Span< ClusterIndex >	linearization
	)

Improve a given linearization.

Parameters

[in]	depgraph	Dependency graph of the cluster being linearized.
[in,out]	linearization	On input, an existing linearization for depgraph. On output, a potentially better linearization for the same graph.

Postlinearization guarantees:

• The resulting chunks are connected.
• If the input has a tree shape (either all transactions have at most one child, or all transactions have at most one parent), the result is optimal.
• Given a linearization L1 and a leaf transaction T in it. Let L2 be L1 with T moved to the end, optionally with its fee increased. Let L3 be the postlinearization of L2. L3 will be at least as good as L1. This means that replacing transactions with same-size higher-fee transactions will not worsen linearizations through a "drop conflicts, append new transactions, postlinearize" process.

Index of the sentinel in the entries array below.

Indicator that a group has no previous transaction.

Data structure per transaction entry.

The index of the previous transaction in this group; NO_PREV_TX if this is the first entry of a group.

Index of the first transaction in this group, possibly itself.

Index of the last transaction in the previous group. The first group (the sentinel) points back to the last group here, making it a singly-linked circular list.

All transactions in the group. Empty for the sentinel.

All dependencies of the group (descendants in even passes; ancestors in odd ones).

The combined fee/size of transactions in the group. Fee is negated in even passes.

Definition at line 1113 of file cluster_linearize.h.

Here is the call graph for this function:

Here is the caller graph for this function: