Bitcoin Core 28.99.0
P2P Digital Currency
Classes | Public Member Functions | Private Attributes | Friends | List of all members
cluster_linearize::DepGraph< SetType > Class Template Reference

Data structure that holds a transaction graph's preprocessed data (fee, size, ancestors, descendants). More...

#include <cluster_linearize.h>

Classes

struct  Entry
 Information about a single transaction. More...
 

Public Member Functions

 DepGraph () noexcept=default
 
 DepGraph (const DepGraph &) noexcept=default
 
 DepGraph (DepGraph &&) noexcept=default
 
DepGraphoperator= (const DepGraph &) noexcept=default
 
DepGraphoperator= (DepGraph &&) noexcept=default
 
 DepGraph (const DepGraph< SetType > &depgraph, Span< const ClusterIndex > mapping, ClusterIndex pos_range) noexcept
 Construct a DepGraph object given another DepGraph and a mapping from old to new. More...
 
const SetType & Positions () const noexcept
 Get the set of transactions positions in use. More...
 
ClusterIndex PositionRange () const noexcept
 Get the range of positions in this DepGraph. More...
 
auto TxCount () const noexcept
 Get the number of transactions in the graph. More...
 
const FeeFracFeeRate (ClusterIndex i) const noexcept
 Get the feerate of a given transaction i. More...
 
FeeFracFeeRate (ClusterIndex i) noexcept
 Get the mutable feerate of a given transaction i. More...
 
const SetType & Ancestors (ClusterIndex i) const noexcept
 Get the ancestors of a given transaction i. More...
 
const SetType & Descendants (ClusterIndex i) const noexcept
 Get the descendants of a given transaction i. More...
 
ClusterIndex AddTransaction (const FeeFrac &feefrac) noexcept
 Add a new unconnected transaction to this transaction graph (in the first available position), and return its ClusterIndex. More...
 
void RemoveTransactions (const SetType &del) noexcept
 Remove the specified positions from this DepGraph. More...
 
void AddDependencies (const SetType &parents, ClusterIndex child) noexcept
 Modify this transaction graph, adding multiple parents to a specified child. More...
 
SetType GetReducedParents (ClusterIndex i) const noexcept
 Compute the (reduced) set of parents of node i in this graph. More...
 
SetType GetReducedChildren (ClusterIndex i) const noexcept
 Compute the (reduced) set of children of node i in this graph. More...
 
FeeFrac FeeRate (const SetType &elems) const noexcept
 Compute the aggregate feerate of a set of nodes in this graph. More...
 
SetType FindConnectedComponent (const SetType &todo) const noexcept
 Find some connected component within the subset "todo" of this graph. More...
 
bool IsConnected (const SetType &subset) const noexcept
 Determine if a subset is connected. More...
 
bool IsConnected () const noexcept
 Determine if this entire graph is connected. More...
 
void AppendTopo (std::vector< ClusterIndex > &list, const SetType &select) const noexcept
 Append the entries of select to list in a topologically valid order. More...
 

Private Attributes

std::vector< Entryentries
 Data for each transaction. More...
 
SetType m_used
 Which positions are used. More...
 

Friends

bool operator== (const DepGraph &a, const DepGraph &b) noexcept
 Equality operator (primarily for testing purposes). More...
 

Detailed Description

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

Data structure that holds a transaction graph's preprocessed data (fee, size, ancestors, descendants).

Definition at line 28 of file cluster_linearize.h.

Constructor & Destructor Documentation

◆ DepGraph() [1/4]

template<typename SetType >
cluster_linearize::DepGraph< SetType >::DepGraph ( )
defaultnoexcept

◆ DepGraph() [2/4]

template<typename SetType >
cluster_linearize::DepGraph< SetType >::DepGraph ( const DepGraph< SetType > &  )
defaultnoexcept

◆ DepGraph() [3/4]

template<typename SetType >
cluster_linearize::DepGraph< SetType >::DepGraph ( DepGraph< SetType > &&  )
defaultnoexcept

◆ DepGraph() [4/4]

template<typename SetType >
cluster_linearize::DepGraph< SetType >::DepGraph ( const DepGraph< SetType > &  depgraph,
Span< const ClusterIndex mapping,
ClusterIndex  pos_range 
)
inlinenoexcept

Construct a DepGraph object given another DepGraph and a mapping from old to new.

Parameters
depgraphThe original DepGraph that is being remapped.
mappingA Span such that mapping[i] gives the position in the new DepGraph for position i in the old depgraph. Its size must be equal to depgraph.PositionRange(). The value of mapping[i] is ignored if position i is a hole in depgraph (i.e., if !depgraph.Positions()[i]).
pos_rangeThe PositionRange() for the new DepGraph. It must equal the largest value in mapping for any used position in depgraph plus 1, or 0 if depgraph.TxCount() == 0.

Complexity: O(N^2) where N=depgraph.TxCount().

Definition at line 89 of file cluster_linearize.h.

Here is the call graph for this function:

Member Function Documentation

◆ AddDependencies()

template<typename SetType >
void cluster_linearize::DepGraph< SetType >::AddDependencies ( const SetType &  parents,
ClusterIndex  child 
)
inlinenoexcept

Modify this transaction graph, adding multiple parents to a specified child.

Complexity: O(N) where N=TxCount().

Definition at line 177 of file cluster_linearize.h.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ AddTransaction()

template<typename SetType >
ClusterIndex cluster_linearize::DepGraph< SetType >::AddTransaction ( const FeeFrac feefrac)
inlinenoexcept

Add a new unconnected transaction to this transaction graph (in the first available position), and return its ClusterIndex.

Complexity: O(1) (amortized, due to resizing of backing vector).

Definition at line 133 of file cluster_linearize.h.

Here is the caller graph for this function:

◆ Ancestors()

template<typename SetType >
const SetType & cluster_linearize::DepGraph< SetType >::Ancestors ( ClusterIndex  i) const
inlinenoexcept

Get the ancestors of a given transaction i.

Complexity: O(1).

Definition at line 124 of file cluster_linearize.h.

Here is the caller graph for this function:

◆ AppendTopo()

template<typename SetType >
void cluster_linearize::DepGraph< SetType >::AppendTopo ( std::vector< ClusterIndex > &  list,
const SetType &  select 
) const
inlinenoexcept

Append the entries of select to list in a topologically valid order.

Complexity: O(select.Count() * log(select.Count())).

Definition at line 301 of file cluster_linearize.h.

Here is the caller graph for this function:

◆ Descendants()

template<typename SetType >
const SetType & cluster_linearize::DepGraph< SetType >::Descendants ( ClusterIndex  i) const
inlinenoexcept

Get the descendants of a given transaction i.

Complexity: O(1).

Definition at line 126 of file cluster_linearize.h.

Here is the caller graph for this function:

◆ FeeRate() [1/3]

template<typename SetType >
const FeeFrac & cluster_linearize::DepGraph< SetType >::FeeRate ( ClusterIndex  i) const
inlinenoexcept

Get the feerate of a given transaction i.

Complexity: O(1).

Definition at line 120 of file cluster_linearize.h.

Here is the caller graph for this function:

◆ FeeRate() [2/3]

template<typename SetType >
FeeFrac & cluster_linearize::DepGraph< SetType >::FeeRate ( ClusterIndex  i)
inlinenoexcept

Get the mutable feerate of a given transaction i.

Complexity: O(1).

Definition at line 122 of file cluster_linearize.h.

◆ FeeRate() [3/3]

template<typename SetType >
FeeFrac cluster_linearize::DepGraph< SetType >::FeeRate ( const SetType &  elems) const
inlinenoexcept

Compute the aggregate feerate of a set of nodes in this graph.

Complexity: O(N) where N=elems.Count().

Definition at line 246 of file cluster_linearize.h.

◆ FindConnectedComponent()

template<typename SetType >
SetType cluster_linearize::DepGraph< SetType >::FindConnectedComponent ( const SetType &  todo) const
inlinenoexcept

Find some connected component within the subset "todo" of this graph.

Specifically, this finds the connected component which contains the first transaction of todo (if any).

Two transactions are considered connected if they are both in todo, and one is an ancestor of the other in the entire graph (so not just within todo), or transitively there is a path of transactions connecting them. This does mean that if todo contains a transaction and a grandparent, but misses the parent, they will still be part of the same component.

Complexity: O(ret.Count()).

Definition at line 265 of file cluster_linearize.h.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ GetReducedChildren()

template<typename SetType >
SetType cluster_linearize::DepGraph< SetType >::GetReducedChildren ( ClusterIndex  i) const
inlinenoexcept

Compute the (reduced) set of children of node i in this graph.

This returns the minimal subset of the children of i whose descendants together equal all of i's descendants (unless i is part of a cycle of dependencies). Note that DepGraph does not store the set of children; this information is inferred from the descendant sets.

Complexity: O(N) where N=Descendants(i).Count() (which is bounded by TxCount()).

Definition at line 229 of file cluster_linearize.h.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ GetReducedParents()

template<typename SetType >
SetType cluster_linearize::DepGraph< SetType >::GetReducedParents ( ClusterIndex  i) const
inlinenoexcept

Compute the (reduced) set of parents of node i in this graph.

This returns the minimal subset of the parents of i whose ancestors together equal all of i's ancestors (unless i is part of a cycle of dependencies). Note that DepGraph does not store the set of parents; this information is inferred from the ancestor sets.

Complexity: O(N) where N=Ancestors(i).Count() (which is bounded by TxCount()).

Definition at line 208 of file cluster_linearize.h.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ IsConnected() [1/2]

template<typename SetType >
bool cluster_linearize::DepGraph< SetType >::IsConnected ( ) const
inlinenoexcept

Determine if this entire graph is connected.

Complexity: O(TxCount()).

Definition at line 295 of file cluster_linearize.h.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ IsConnected() [2/2]

template<typename SetType >
bool cluster_linearize::DepGraph< SetType >::IsConnected ( const SetType &  subset) const
inlinenoexcept

Determine if a subset is connected.

Complexity: O(subset.Count()).

Definition at line 286 of file cluster_linearize.h.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ operator=() [1/2]

template<typename SetType >
DepGraph & cluster_linearize::DepGraph< SetType >::operator= ( const DepGraph< SetType > &  )
defaultnoexcept

◆ operator=() [2/2]

template<typename SetType >
DepGraph & cluster_linearize::DepGraph< SetType >::operator= ( DepGraph< SetType > &&  )
defaultnoexcept

◆ PositionRange()

template<typename SetType >
ClusterIndex cluster_linearize::DepGraph< SetType >::PositionRange ( ) const
inlinenoexcept

Get the range of positions in this DepGraph.

All entries in Positions() are in [0, PositionRange() - 1].

Definition at line 116 of file cluster_linearize.h.

Here is the caller graph for this function:

◆ Positions()

template<typename SetType >
const SetType & cluster_linearize::DepGraph< SetType >::Positions ( ) const
inlinenoexcept

Get the set of transactions positions in use.

Complexity: O(1).

Definition at line 114 of file cluster_linearize.h.

Here is the caller graph for this function:

◆ RemoveTransactions()

template<typename SetType >
void cluster_linearize::DepGraph< SetType >::RemoveTransactions ( const SetType &  del)
inlinenoexcept

Remove the specified positions from this DepGraph.

The specified positions will no longer be part of Positions(), and dependencies with them are removed. Note that due to DepGraph only tracking ancestors/descendants (and not direct dependencies), if a parent is removed while a grandparent remains, the grandparent will remain an ancestor.

Complexity: O(N) where N=TxCount().

Definition at line 157 of file cluster_linearize.h.

Here is the caller graph for this function:

◆ TxCount()

template<typename SetType >
auto cluster_linearize::DepGraph< SetType >::TxCount ( ) const
inlinenoexcept

Get the number of transactions in the graph.

Complexity: O(1).

Definition at line 118 of file cluster_linearize.h.

Here is the caller graph for this function:

Friends And Related Function Documentation

◆ operator==

template<typename SetType >
bool operator== ( const DepGraph< SetType > &  a,
const DepGraph< SetType > &  b 
)
friend

Equality operator (primarily for testing purposes).

Definition at line 57 of file cluster_linearize.h.

Member Data Documentation

◆ entries

template<typename SetType >
std::vector<Entry> cluster_linearize::DepGraph< SetType >::entries
private

Data for each transaction.

Definition at line 50 of file cluster_linearize.h.

◆ m_used

template<typename SetType >
SetType cluster_linearize::DepGraph< SetType >::m_used
private

Which positions are used.

Definition at line 53 of file cluster_linearize.h.


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