diff options
Diffstat (limited to 'src/cluster_linearize.h')
| -rw-r--r-- | src/cluster_linearize.h | 117 |
1 files changed, 117 insertions, 0 deletions
diff --git a/src/cluster_linearize.h b/src/cluster_linearize.h index 2e230bcd63..03ee894ae3 100644 --- a/src/cluster_linearize.h +++ b/src/cluster_linearize.h @@ -5,6 +5,7 @@ #ifndef BITCOIN_CLUSTER_LINEARIZE_H #define BITCOIN_CLUSTER_LINEARIZE_H +#include <optional> #include <stdint.h> #include <vector> #include <utility> @@ -166,6 +167,122 @@ public: } }; +/** A set of transactions together with their aggregate feerate. */ +template<typename SetType> +struct SetInfo +{ + /** The transactions in the set. */ + SetType transactions; + /** Their combined fee and size. */ + FeeFrac feerate; + + /** Construct a SetInfo for a specified set and feerate. */ + SetInfo(const SetType& txn, const FeeFrac& fr) noexcept : transactions(txn), feerate(fr) {} + + /** Construct a SetInfo for a set of transactions in a depgraph. */ + explicit SetInfo(const DepGraph<SetType>& depgraph, const SetType& txn) noexcept : + transactions(txn), feerate(depgraph.FeeRate(txn)) {} + + /** Permit equality testing. */ + friend bool operator==(const SetInfo&, const SetInfo&) noexcept = default; +}; + +/** Class encapsulating the state needed to find the best remaining ancestor set. + * + * It is initialized for an entire DepGraph, and parts of the graph can be dropped by calling + * MarkDone. + * + * As long as any part of the graph remains, FindCandidateSet() can be called which will return a + * SetInfo with the highest-feerate ancestor set that remains (an ancestor set is a single + * transaction together with all its remaining ancestors). + */ +template<typename SetType> +class AncestorCandidateFinder +{ + /** Internal dependency graph. */ + const DepGraph<SetType>& m_depgraph; + /** Which transaction are left to include. */ + SetType m_todo; + /** Precomputed ancestor-set feerates (only kept up-to-date for indices in m_todo). */ + std::vector<FeeFrac> m_ancestor_set_feerates; + +public: + /** Construct an AncestorCandidateFinder for a given cluster. + * + * Complexity: O(N^2) where N=depgraph.TxCount(). + */ + AncestorCandidateFinder(const DepGraph<SetType>& depgraph LIFETIMEBOUND) noexcept : + m_depgraph(depgraph), + m_todo{SetType::Fill(depgraph.TxCount())}, + m_ancestor_set_feerates(depgraph.TxCount()) + { + // Precompute ancestor-set feerates. + for (ClusterIndex i = 0; i < depgraph.TxCount(); ++i) { + /** The remaining ancestors for transaction i. */ + SetType anc_to_add = m_depgraph.Ancestors(i); + FeeFrac anc_feerate; + // Reuse accumulated feerate from first ancestor, if usable. + Assume(anc_to_add.Any()); + ClusterIndex first = anc_to_add.First(); + if (first < i) { + anc_feerate = m_ancestor_set_feerates[first]; + Assume(!anc_feerate.IsEmpty()); + anc_to_add -= m_depgraph.Ancestors(first); + } + // Add in other ancestors (which necessarily include i itself). + Assume(anc_to_add[i]); + anc_feerate += m_depgraph.FeeRate(anc_to_add); + // Store the result. + m_ancestor_set_feerates[i] = anc_feerate; + } + } + + /** Remove a set of transactions from the set of to-be-linearized ones. + * + * The same transaction may not be MarkDone()'d twice. + * + * Complexity: O(N*M) where N=depgraph.TxCount(), M=select.Count(). + */ + void MarkDone(SetType select) noexcept + { + Assume(select.Any()); + Assume(select.IsSubsetOf(m_todo)); + m_todo -= select; + for (auto i : select) { + auto feerate = m_depgraph.FeeRate(i); + for (auto j : m_depgraph.Descendants(i) & m_todo) { + m_ancestor_set_feerates[j] -= feerate; + } + } + } + + /** Check whether any unlinearized transactions remain. */ + bool AllDone() const noexcept + { + return m_todo.None(); + } + + /** Find the best (highest-feerate, smallest among those in case of a tie) ancestor set + * among the remaining transactions. Requires !AllDone(). + * + * Complexity: O(N) where N=depgraph.TxCount(); + */ + SetInfo<SetType> FindCandidateSet() const noexcept + { + Assume(!AllDone()); + std::optional<ClusterIndex> best; + for (auto i : m_todo) { + if (best.has_value()) { + Assume(!m_ancestor_set_feerates[i].IsEmpty()); + if (!(m_ancestor_set_feerates[i] > m_ancestor_set_feerates[*best])) continue; + } + best = i; + } + Assume(best.has_value()); + return {m_depgraph.Ancestors(*best) & m_todo, m_ancestor_set_feerates[*best]}; + } +}; + } // namespace cluster_linearize #endif // BITCOIN_CLUSTER_LINEARIZE_H |