Bitcoin Core 28.99.0
P2P Digital Currency
|
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 | |
DepGraph & | operator= (const DepGraph &) noexcept=default |
DepGraph & | operator= (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 FeeFrac & | FeeRate (ClusterIndex i) const noexcept |
Get the feerate of a given transaction i. More... | |
FeeFrac & | FeeRate (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< Entry > | entries |
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... | |
Data structure that holds a transaction graph's preprocessed data (fee, size, ancestors, descendants).
Definition at line 28 of file cluster_linearize.h.
|
defaultnoexcept |
|
defaultnoexcept |
|
defaultnoexcept |
|
inlinenoexcept |
Construct a DepGraph object given another DepGraph and a mapping from old to new.
depgraph | The original DepGraph that is being remapped. |
mapping | A 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_range | The 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.
|
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.
|
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.
|
inlinenoexcept |
Get the ancestors of a given transaction i.
Complexity: O(1).
Definition at line 124 of file cluster_linearize.h.
|
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.
|
inlinenoexcept |
Get the descendants of a given transaction i.
Complexity: O(1).
Definition at line 126 of file cluster_linearize.h.
|
inlinenoexcept |
Get the feerate of a given transaction i.
Complexity: O(1).
Definition at line 120 of file cluster_linearize.h.
|
inlinenoexcept |
Get the mutable feerate of a given transaction i.
Complexity: O(1).
Definition at line 122 of file cluster_linearize.h.
|
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.
|
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.
|
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.
|
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.
|
inlinenoexcept |
Determine if this entire graph is connected.
Complexity: O(TxCount()).
Definition at line 295 of file cluster_linearize.h.
|
inlinenoexcept |
Determine if a subset is connected.
Complexity: O(subset.Count()).
Definition at line 286 of file cluster_linearize.h.
|
defaultnoexcept |
|
defaultnoexcept |
|
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.
|
inlinenoexcept |
Get the set of transactions positions in use.
Complexity: O(1).
Definition at line 114 of file cluster_linearize.h.
|
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.
|
inlinenoexcept |
Get the number of transactions in the graph.
Complexity: O(1).
Definition at line 118 of file cluster_linearize.h.
|
friend |
Equality operator (primarily for testing purposes).
Definition at line 57 of file cluster_linearize.h.
|
private |
Data for each transaction.
Definition at line 50 of file cluster_linearize.h.
|
private |
Which positions are used.
Definition at line 53 of file cluster_linearize.h.