cluster_linearize::LinearizationChunking< SetType > Class Template Reference

Data structure encapsulating the chunking of a linearization, permitting removal of subsets. More...

#include <cluster_linearize.h>

Public Member Functions
	LinearizationChunking (const DepGraph< SetType > &depgraph LIFETIMEBOUND, std::span< const DepGraphIndex > lin LIFETIMEBOUND) noexcept
	Initialize a LinearizationSubset object for a given length of linearization. More...
DepGraphIndex	NumChunksLeft () const noexcept
	Determine how many chunks remain in the linearization. More...
const SetInfo< SetType > &	GetChunk (DepGraphIndex n) const noexcept
	Access a chunk. More...
void	MarkDone (SetType subset) noexcept
	Remove some subset of transactions from the linearization. More...
SetInfo< SetType >	IntersectPrefixes (const SetInfo< SetType > &subset) const noexcept
	Find the shortest intersection between subset and the prefixes of remaining chunks of the linearization that has a feerate not below subset's. More...

Private Member Functions
void	BuildChunks () noexcept
	Fill the m_chunks variable, and remove the done prefix of m_linearization. More...

Private Attributes
const DepGraph< SetType > &	m_depgraph
	The depgraph this linearization is for. More...
std::span< const DepGraphIndex >	m_linearization
	The linearization we started from, possibly with removed prefix stripped. More...
std::vector< SetInfo< SetType > >	m_chunks
	Chunk sets and their feerates, of what remains of the linearization. More...
DepGraphIndex	m_chunks_skip {0}
	How large a prefix of m_chunks corresponds to removed transactions. More...
SetType	m_todo
	Which transactions remain in the linearization. More...

Detailed Description

template<typename SetType>
class cluster_linearize::LinearizationChunking< SetType >

Data structure encapsulating the chunking of a linearization, permitting removal of subsets.

Definition at line 416 of file cluster_linearize.h.

Constructor & Destructor Documentation

LinearizationChunking()

template<typename SetType >

cluster_linearize::LinearizationChunking< SetType >::LinearizationChunking ( const DepGraph< SetType > &depgraph  LIFETIMEBOUND, std::span< const DepGraphIndex > lin  LIFETIMEBOUND  )

inlineexplicitnoexcept

Initialize a LinearizationSubset object for a given length of linearization.

Definition at line 463 of file cluster_linearize.h.

Here is the call graph for this function:

Member Function Documentation

BuildChunks()

template<typename SetType >

void cluster_linearize::LinearizationChunking< SetType >::BuildChunks ( )

inlineprivatenoexcept

Fill the m_chunks variable, and remove the done prefix of m_linearization.

Definition at line 434 of file cluster_linearize.h.

Here is the caller graph for this function:

GetChunk()

template<typename SetType >

const SetInfo< SetType > & cluster_linearize::LinearizationChunking< SetType >::GetChunk ( DepGraphIndex  n ) const

inlinenoexcept

Access a chunk.

Chunk 0 is the highest-feerate prefix of what remains.

Definition at line 477 of file cluster_linearize.h.

Here is the caller graph for this function:

IntersectPrefixes()

template<typename SetType >

SetInfo< SetType > cluster_linearize::LinearizationChunking< SetType >::IntersectPrefixes ( const SetInfo< SetType > &  subset ) const

inlinenoexcept

Find the shortest intersection between subset and the prefixes of remaining chunks of the linearization that has a feerate not below subset's.

This is a crucial operation in guaranteeing improvements to linearizations. If subset has a feerate not below GetChunk(0)'s, then moving IntersectPrefixes(subset) to the front of (what remains of) the linearization is guaranteed not to make it worse at any point.

See https://delvingbitcoin.org/t/introduction-to-cluster-linearization/1032 for background.

Definition at line 515 of file cluster_linearize.h.

Here is the call graph for this function:

Here is the caller graph for this function:

MarkDone()

template<typename SetType >

void cluster_linearize::LinearizationChunking< SetType >::MarkDone ( SetType  subset )

inlinenoexcept

Remove some subset of transactions from the linearization.

Definition at line 484 of file cluster_linearize.h.

Here is the call graph for this function:

Here is the caller graph for this function:

NumChunksLeft()

template<typename SetType >

DepGraphIndex cluster_linearize::LinearizationChunking< SetType >::NumChunksLeft ( ) const

inlinenoexcept

Determine how many chunks remain in the linearization.

Definition at line 474 of file cluster_linearize.h.

Here is the caller graph for this function:

Member Data Documentation

m_chunks

template<typename SetType >

std::vector<SetInfo<SetType> > cluster_linearize::LinearizationChunking< SetType >::m_chunks

private

Chunk sets and their feerates, of what remains of the linearization.

Definition at line 425 of file cluster_linearize.h.

m_chunks_skip

template<typename SetType >

DepGraphIndex cluster_linearize::LinearizationChunking< SetType >::m_chunks_skip {0}

private

How large a prefix of m_chunks corresponds to removed transactions.

Definition at line 428 of file cluster_linearize.h.

m_depgraph

template<typename SetType >

const DepGraph<SetType>& cluster_linearize::LinearizationChunking< SetType >::m_depgraph

private

The depgraph this linearization is for.

Definition at line 419 of file cluster_linearize.h.

m_linearization

template<typename SetType >

std::span<const DepGraphIndex> cluster_linearize::LinearizationChunking< SetType >::m_linearization

private

The linearization we started from, possibly with removed prefix stripped.

Definition at line 422 of file cluster_linearize.h.

m_todo

template<typename SetType >

SetType cluster_linearize::LinearizationChunking< SetType >::m_todo

private

Which transactions remain in the linearization.

Definition at line 431 of file cluster_linearize.h.

---

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

• src/cluster_linearize.h