LCOV - code coverage report
Current view: top level - src - txgraph.cpp (source / functions) Coverage Total Hit
Test: total_coverage.info Lines: 95.1 % 1630 1550
Test Date: 2026-11-21 06:10:03 Functions: 95.3 % 148 141
Branches: 73.3 % 1572 1153

             Branch data     Line data    Source code
       1                 :             : // Copyright (c) The Bitcoin Core developers
       2                 :             : // Distributed under the MIT software license, see the accompanying
       3                 :             : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
       4                 :             : 
       5                 :             : #include <txgraph.h>
       6                 :             : 
       7                 :             : #include <cluster_linearize.h>
       8                 :             : #include <random.h>
       9                 :             : #include <util/bitset.h>
      10                 :             : #include <util/check.h>
      11                 :             : #include <util/feefrac.h>
      12                 :             : #include <util/vector.h>
      13                 :             : 
      14                 :             : #include <compare>
      15                 :             : #include <functional>
      16                 :             : #include <memory>
      17                 :             : #include <ranges>
      18                 :             : #include <set>
      19                 :             : #include <span>
      20                 :             : #include <unordered_set>
      21                 :             : #include <utility>
      22                 :             : #include <vector>
      23                 :             : 
      24                 :             : namespace {
      25                 :             : 
      26                 :             : using namespace cluster_linearize;
      27                 :             : 
      28                 :             : /** The maximum number of levels a TxGraph can have (0 = main, 1 = staging). */
      29                 :             : static constexpr int MAX_LEVELS{2};
      30                 :             : 
      31                 :             : // Forward declare the TxGraph implementation class.
      32                 :             : class TxGraphImpl;
      33                 :             : 
      34                 :             : /** Position of a DepGraphIndex within a Cluster::m_linearization. */
      35                 :             : using LinearizationIndex = uint32_t;
      36                 :             : /** Position of a Cluster within TxGraphImpl::ClusterSet::m_clusters. */
      37                 :             : using ClusterSetIndex = uint32_t;
      38                 :             : 
      39                 :             : /** Quality levels for cached cluster linearizations. */
      40                 :             : enum class QualityLevel
      41                 :             : {
      42                 :             :     /** This is a singleton cluster consisting of a transaction that individually exceeds the
      43                 :             :      *  cluster size limit. It cannot be merged with anything. */
      44                 :             :     OVERSIZED_SINGLETON,
      45                 :             :     /** This cluster may have multiple disconnected components, which are all NEEDS_FIX. */
      46                 :             :     NEEDS_SPLIT_FIX,
      47                 :             :     /** This cluster may have multiple disconnected components, which are all NEEDS_RELINEARIZE. */
      48                 :             :     NEEDS_SPLIT,
      49                 :             :     /** This cluster may be non-topological. */
      50                 :             :     NEEDS_FIX,
      51                 :             :     /** This cluster has undergone changes that warrant re-linearization. */
      52                 :             :     NEEDS_RELINEARIZE,
      53                 :             :     /** The minimal level of linearization has been performed, but it is not known to be optimal. */
      54                 :             :     ACCEPTABLE,
      55                 :             :     /** The linearization is known to be optimal. */
      56                 :             :     OPTIMAL,
      57                 :             :     /** This cluster is not registered in any ClusterSet::m_clusters.
      58                 :             :      *  This must be the last entry in QualityLevel as ClusterSet::m_clusters is sized using it. */
      59                 :             :     NONE,
      60                 :             : };
      61                 :             : 
      62                 :             : /** Information about a transaction inside TxGraphImpl::Trim. */
      63                 :       64217 : struct TrimTxData
      64                 :             : {
      65                 :             :     // Fields populated by Cluster::AppendTrimData(). These are immutable after TrimTxData
      66                 :             :     // construction.
      67                 :             :     /** Chunk feerate for this transaction. */
      68                 :             :     FeePerWeight m_chunk_feerate;
      69                 :             :     /** GraphIndex of the transaction. */
      70                 :             :     TxGraph::GraphIndex m_index;
      71                 :             :     /** Size of the transaction. */
      72                 :             :     uint32_t m_tx_size;
      73                 :             : 
      74                 :             :     // Fields only used internally by TxGraphImpl::Trim():
      75                 :             :     /** Number of unmet dependencies this transaction has. -1 if the transaction is included. */
      76                 :             :     uint32_t m_deps_left;
      77                 :             :     /** Number of dependencies that apply to this transaction as child. */
      78                 :             :     uint32_t m_parent_count;
      79                 :             :     /** Where in deps_by_child those dependencies begin. */
      80                 :             :     uint32_t m_parent_offset;
      81                 :             :     /** Number of dependencies that apply to this transaction as parent. */
      82                 :             :     uint32_t m_children_count;
      83                 :             :     /** Where in deps_by_parent those dependencies begin. */
      84                 :             :     uint32_t m_children_offset;
      85                 :             : 
      86                 :             :     // Fields only used internally by TxGraphImpl::Trim()'s union-find implementation, and only for
      87                 :             :     // transactions that are definitely included or definitely rejected.
      88                 :             :     //
      89                 :             :     // As transactions get processed, they get organized into trees which form partitions
      90                 :             :     // representing the would-be clusters up to that point. The root of each tree is a
      91                 :             :     // representative for that partition. See
      92                 :             :     // https://en.wikipedia.org/wiki/Disjoint-set_data_structure.
      93                 :             :     //
      94                 :             :     /** Pointer to another TrimTxData, towards the root of the tree. If this is a root, m_uf_parent
      95                 :             :      *  is equal to this itself. */
      96                 :             :     TrimTxData* m_uf_parent;
      97                 :             :     /** If this is a root, the total number of transactions in the partition. */
      98                 :             :     uint32_t m_uf_count;
      99                 :             :     /** If this is a root, the total size of transactions in the partition. */
     100                 :             :     uint64_t m_uf_size;
     101                 :             : };
     102                 :             : 
     103                 :             : /** A grouping of connected transactions inside a TxGraphImpl::ClusterSet. */
     104                 :             : class Cluster
     105                 :             : {
     106                 :             :     friend class TxGraphImpl;
     107                 :             :     friend class BlockBuilderImpl;
     108                 :             : 
     109                 :             : protected:
     110                 :             :     using GraphIndex = TxGraph::GraphIndex;
     111                 :             :     using SetType = BitSet<MAX_CLUSTER_COUNT_LIMIT>;
     112                 :             :     /** The quality level of m_linearization. */
     113                 :             :     QualityLevel m_quality{QualityLevel::NONE};
     114                 :             :     /** Which position this Cluster has in TxGraphImpl::ClusterSet::m_clusters[m_quality]. */
     115                 :             :     ClusterSetIndex m_setindex{ClusterSetIndex(-1)};
     116                 :             :     /** Sequence number for this Cluster (for tie-breaking comparison between equal-chunk-feerate
     117                 :             :         transactions in distinct clusters). */
     118                 :             :     uint64_t m_sequence;
     119                 :             : 
     120                 :      139642 :     explicit Cluster(uint64_t sequence) noexcept : m_sequence(sequence) {}
     121                 :             : 
     122                 :             : public:
     123                 :             :     // Provide virtual destructor, for safe polymorphic usage inside std::unique_ptr.
     124                 :           0 :     virtual ~Cluster() = default;
     125                 :             : 
     126                 :             :     // Cannot move or copy (would invalidate Cluster* in Locator and ClusterSet). */
     127                 :             :     Cluster(const Cluster&) = delete;
     128                 :             :     Cluster& operator=(const Cluster&) = delete;
     129                 :             :     Cluster(Cluster&&) = delete;
     130                 :             :     Cluster& operator=(Cluster&&) = delete;
     131                 :             : 
     132                 :             :     // Generic helper functions.
     133                 :             : 
     134                 :             :     /** Whether the linearization of this Cluster can be exposed. */
     135                 :   330930804 :     bool IsAcceptable() const noexcept
     136                 :             :     {
     137                 :   330930804 :         return m_quality == QualityLevel::ACCEPTABLE || m_quality == QualityLevel::OPTIMAL;
     138                 :             :     }
     139                 :             :     /** Whether the linearization of this Cluster is topological. */
     140                 :      412977 :     bool IsTopological() const noexcept
     141                 :             :     {
     142                 :      412977 :         return m_quality != QualityLevel::NEEDS_FIX && m_quality != QualityLevel::NEEDS_SPLIT_FIX;
     143                 :             :     }
     144                 :             :     /** Whether the linearization of this Cluster is optimal. */
     145                 :    12080673 :     bool IsOptimal() const noexcept
     146                 :             :     {
     147                 :    12080673 :         return m_quality == QualityLevel::OPTIMAL;
     148                 :             :     }
     149                 :             :     /** Whether this cluster is oversized. Note that no changes that can cause oversizedness are
     150                 :             :      *  ever applied, so the only way a materialized Cluster object can be oversized is by being
     151                 :             :      *  an individually oversized transaction singleton. */
     152                 :    24288030 :     bool IsOversized() const noexcept { return m_quality == QualityLevel::OVERSIZED_SINGLETON; }
     153                 :             :     /** Whether this cluster requires splitting. */
     154                 :   330540105 :     bool NeedsSplitting() const noexcept
     155                 :             :     {
     156                 :   330540105 :         return m_quality == QualityLevel::NEEDS_SPLIT || m_quality == QualityLevel::NEEDS_SPLIT_FIX;
     157                 :             :     }
     158                 :             : 
     159                 :             :     /** Get the smallest number of transactions this Cluster is intended for. */
     160                 :             :     virtual DepGraphIndex GetMinIntendedTxCount() const noexcept = 0;
     161                 :             :     /** Get the maximum number of transactions this Cluster supports. */
     162                 :             :     virtual DepGraphIndex GetMaxTxCount() const noexcept = 0;
     163                 :             :     /** Total memory usage currently for this Cluster, including all its dynamic memory, plus Cluster
     164                 :             :      *  structure itself, and ClusterSet::m_clusters entry. */
     165                 :             :     virtual size_t TotalMemoryUsage() const noexcept = 0;
     166                 :             :     /** Determine the range of DepGraphIndexes used by this Cluster. */
     167                 :             :     virtual DepGraphIndex GetDepGraphIndexRange() const noexcept = 0;
     168                 :             :     /** Get the number of transactions in this Cluster. */
     169                 :             :     virtual LinearizationIndex GetTxCount() const noexcept = 0;
     170                 :             :     /** Get the total size of the transactions in this Cluster. */
     171                 :             :     virtual uint64_t GetTotalTxSize() const noexcept = 0;
     172                 :             :     /** Given a DepGraphIndex into this Cluster, find the corresponding GraphIndex. */
     173                 :             :     virtual GraphIndex GetClusterEntry(DepGraphIndex index) const noexcept = 0;
     174                 :             :     /** Append a transaction with given GraphIndex at the end of this Cluster and its
     175                 :             :      *  linearization. Return the DepGraphIndex it was placed at. */
     176                 :             :     virtual DepGraphIndex AppendTransaction(GraphIndex graph_idx, FeePerWeight feerate) noexcept = 0;
     177                 :             :     /** Add dependencies to a given child in this cluster. */
     178                 :             :     virtual void AddDependencies(SetType parents, DepGraphIndex child) noexcept = 0;
     179                 :             :     /** Invoke visit1_fn for each transaction in the cluster, in linearization order, then
     180                 :             :      *  visit2_fn in the same order, then wipe this Cluster. */
     181                 :             :     virtual void ExtractTransactions(const std::function<void (DepGraphIndex, GraphIndex, FeePerWeight)>& visit1_fn, const std::function<void (DepGraphIndex, GraphIndex, SetType)>& visit2_fn) noexcept = 0;
     182                 :             :     /** Figure out what level this Cluster exists at in the graph. In most cases this is known by
     183                 :             :      *  the caller already (see all "int level" arguments below), but not always. */
     184                 :             :     virtual int GetLevel(const TxGraphImpl& graph) const noexcept = 0;
     185                 :             :     /** Only called by TxGraphImpl::SwapIndexes. */
     186                 :             :     virtual void UpdateMapping(DepGraphIndex cluster_idx, GraphIndex graph_idx) noexcept = 0;
     187                 :             :     /** Push changes to Cluster and its linearization to the TxGraphImpl Entry objects. Main chunk
     188                 :             :      *  information is computed if the cluster is acceptable, or when rename is set. Rename is used
     189                 :             :      *  when called from Compact, to recompute after GraphIndexes may have changed; in this case,
     190                 :             :      *  no chunk index objects are removed or created either. */
     191                 :             :     virtual void Updated(TxGraphImpl& graph, int level, bool rename) noexcept = 0;
     192                 :             :     /** Remove all chunk index entries for this cluster (level=0 only). */
     193                 :             :     virtual void RemoveChunkData(TxGraphImpl& graph) noexcept = 0;
     194                 :             :     /** Create a copy of this Cluster in staging, returning a pointer to it (used by PullIn). */
     195                 :             :     virtual Cluster* CopyToStaging(TxGraphImpl& graph) const noexcept = 0;
     196                 :             :     /** Get the list of Clusters in main that conflict with this one (which is assumed to be in staging). */
     197                 :             :     virtual void GetConflicts(const TxGraphImpl& graph, std::vector<Cluster*>& out) const noexcept = 0;
     198                 :             :     /** Mark all the Entry objects belonging to this staging Cluster as missing. The Cluster must be
     199                 :             :      *  deleted immediately after. */
     200                 :             :     virtual void MakeStagingTransactionsMissing(TxGraphImpl& graph) noexcept = 0;
     201                 :             :     /** Remove all transactions from a (non-empty) Cluster. */
     202                 :             :     virtual void Clear(TxGraphImpl& graph, int level) noexcept = 0;
     203                 :             :     /** Change a Cluster's level from 1 (staging) to 0 (main). */
     204                 :             :     virtual void MoveToMain(TxGraphImpl& graph) noexcept = 0;
     205                 :             :     /** Minimize this Cluster's memory usage. */
     206                 :             :     virtual void Compact() noexcept = 0;
     207                 :             : 
     208                 :             :     // Functions that implement the Cluster-specific side of internal TxGraphImpl mutations.
     209                 :             : 
     210                 :             :     /** Apply all removals from the front of to_remove that apply to this Cluster, popping them
     211                 :             :      *  off. There must be at least one such entry. */
     212                 :             :     virtual void ApplyRemovals(TxGraphImpl& graph, int level, std::span<GraphIndex>& to_remove) noexcept = 0;
     213                 :             :     /** Split this cluster (must have a NEEDS_SPLIT* quality). Returns whether to delete this
     214                 :             :      *  Cluster afterwards. */
     215                 :             :     [[nodiscard]] virtual bool Split(TxGraphImpl& graph, int level) noexcept = 0;
     216                 :             :     /** Move all transactions from cluster to *this (as separate components). */
     217                 :             :     virtual void Merge(TxGraphImpl& graph, int level, Cluster& cluster) noexcept = 0;
     218                 :             :     /** Given a span of (parent, child) pairs that all belong to this Cluster, apply them. */
     219                 :             :     virtual void ApplyDependencies(TxGraphImpl& graph, int level, std::span<std::pair<GraphIndex, GraphIndex>> to_apply) noexcept = 0;
     220                 :             :     /** Improve the linearization of this Cluster. Returns how much work was performed and whether
     221                 :             :      *  the Cluster's QualityLevel improved as a result. */
     222                 :             :     virtual std::pair<uint64_t, bool> Relinearize(TxGraphImpl& graph, int level, uint64_t max_cost) noexcept = 0;
     223                 :             :     /** For every chunk in the cluster, append its FeeFrac to ret. */
     224                 :             :     virtual void AppendChunkFeerates(std::vector<FeeFrac>& ret) const noexcept = 0;
     225                 :             :     /** Add a TrimTxData entry (filling m_chunk_feerate, m_index, m_tx_size) for every
     226                 :             :      *  transaction in the Cluster to ret. Implicit dependencies between consecutive transactions
     227                 :             :      *  in the linearization are added to deps. Return the Cluster's total transaction size. */
     228                 :             :     virtual uint64_t AppendTrimData(std::vector<TrimTxData>& ret, std::vector<std::pair<GraphIndex, GraphIndex>>& deps) const noexcept = 0;
     229                 :             : 
     230                 :             :     // Functions that implement the Cluster-specific side of public TxGraph functions.
     231                 :             : 
     232                 :             :     /** Process elements from the front of args that apply to this cluster, and append Refs for the
     233                 :             :      *  union of their ancestors to output. */
     234                 :             :     virtual void GetAncestorRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept = 0;
     235                 :             :     /** Process elements from the front of args that apply to this cluster, and append Refs for the
     236                 :             :      *  union of their descendants to output. */
     237                 :             :     virtual void GetDescendantRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept = 0;
     238                 :             :     /** Populate range with refs for the transactions in this Cluster's linearization, from
     239                 :             :      *  position start_pos until start_pos+range.size()-1, inclusive. Returns whether that
     240                 :             :      *  range includes the last transaction in the linearization. */
     241                 :             :     virtual bool GetClusterRefs(TxGraphImpl& graph, std::span<TxGraph::Ref*> range, LinearizationIndex start_pos) noexcept = 0;
     242                 :             :     /** Get the individual transaction feerate of a Cluster element. */
     243                 :             :     virtual FeePerWeight GetIndividualFeerate(DepGraphIndex idx) noexcept = 0;
     244                 :             :     /** Modify the fee of a Cluster element. */
     245                 :             :     virtual void SetFee(TxGraphImpl& graph, int level, DepGraphIndex idx, int64_t fee) noexcept = 0;
     246                 :             : 
     247                 :             :     // Debugging functions.
     248                 :             : 
     249                 :             :     virtual void SanityCheck(const TxGraphImpl& graph, int level) const = 0;
     250                 :             : };
     251                 :             : 
     252                 :             : /** An implementation of Cluster that uses a DepGraph and vectors, to support arbitrary numbers of
     253                 :             :  *  transactions up to MAX_CLUSTER_COUNT_LIMIT. */
     254                 :             : class GenericClusterImpl final : public Cluster
     255                 :             : {
     256                 :             :     friend class TxGraphImpl;
     257                 :             :     /** The DepGraph for this cluster, holding all feerates, and ancestors/descendants. */
     258                 :             :     DepGraph<SetType> m_depgraph;
     259                 :             :     /** m_mapping[i] gives the GraphIndex for the position i transaction in m_depgraph. Values for
     260                 :             :      *  positions i that do not exist in m_depgraph shouldn't ever be accessed and thus don't
     261                 :             :      *  matter. m_mapping.size() equals m_depgraph.PositionRange(). */
     262                 :             :     std::vector<GraphIndex> m_mapping;
     263                 :             :     /** The current linearization of the cluster. m_linearization.size() equals
     264                 :             :      *  m_depgraph.TxCount(). This is always kept topological. */
     265                 :             :     std::vector<DepGraphIndex> m_linearization;
     266                 :             : 
     267                 :             : public:
     268                 :             :     /** The smallest number of transactions this Cluster implementation is intended for. */
     269                 :             :     static constexpr DepGraphIndex MIN_INTENDED_TX_COUNT{2};
     270                 :             :     /** The largest number of transactions this Cluster implementation supports. */
     271                 :             :     static constexpr DepGraphIndex MAX_TX_COUNT{SetType::Size()};
     272                 :             : 
     273                 :             :     GenericClusterImpl() noexcept = delete;
     274                 :             :     /** Construct an empty GenericClusterImpl. */
     275                 :             :     explicit GenericClusterImpl(uint64_t sequence) noexcept;
     276                 :             : 
     277                 :             :     size_t TotalMemoryUsage() const noexcept final;
     278                 :       69329 :     constexpr DepGraphIndex GetMinIntendedTxCount() const noexcept final { return MIN_INTENDED_TX_COUNT; }
     279                 :       73862 :     constexpr DepGraphIndex GetMaxTxCount() const noexcept final { return MAX_TX_COUNT; }
     280         [ -  + ]:          11 :     DepGraphIndex GetDepGraphIndexRange() const noexcept final { return m_depgraph.PositionRange(); }
     281         [ -  + ]:      376883 :     LinearizationIndex GetTxCount() const noexcept final { return m_linearization.size(); }
     282                 :             :     uint64_t GetTotalTxSize() const noexcept final;
     283                 :      404481 :     GraphIndex GetClusterEntry(DepGraphIndex index) const noexcept final { return m_mapping[index]; }
     284                 :             :     DepGraphIndex AppendTransaction(GraphIndex graph_idx, FeePerWeight feerate) noexcept final;
     285                 :             :     void AddDependencies(SetType parents, DepGraphIndex child) noexcept final;
     286                 :             :     void ExtractTransactions(const std::function<void (DepGraphIndex, GraphIndex, FeePerWeight)>& visit1_fn, const std::function<void (DepGraphIndex, GraphIndex, SetType)>& visit2_fn) noexcept final;
     287                 :             :     int GetLevel(const TxGraphImpl& graph) const noexcept final;
     288                 :         835 :     void UpdateMapping(DepGraphIndex cluster_idx, GraphIndex graph_idx) noexcept final { m_mapping[cluster_idx] = graph_idx; }
     289                 :             :     void Updated(TxGraphImpl& graph, int level, bool rename) noexcept final;
     290                 :             :     void RemoveChunkData(TxGraphImpl& graph) noexcept final;
     291                 :             :     Cluster* CopyToStaging(TxGraphImpl& graph) const noexcept final;
     292                 :             :     void GetConflicts(const TxGraphImpl& graph, std::vector<Cluster*>& out) const noexcept final;
     293                 :             :     void MakeStagingTransactionsMissing(TxGraphImpl& graph) noexcept final;
     294                 :             :     void Clear(TxGraphImpl& graph, int level) noexcept final;
     295                 :             :     void MoveToMain(TxGraphImpl& graph) noexcept final;
     296                 :             :     void Compact() noexcept final;
     297                 :             :     void ApplyRemovals(TxGraphImpl& graph, int level, std::span<GraphIndex>& to_remove) noexcept final;
     298                 :             :     [[nodiscard]] bool Split(TxGraphImpl& graph, int level) noexcept final;
     299                 :             :     void Merge(TxGraphImpl& graph, int level, Cluster& cluster) noexcept final;
     300                 :             :     void ApplyDependencies(TxGraphImpl& graph, int level, std::span<std::pair<GraphIndex, GraphIndex>> to_apply) noexcept final;
     301                 :             :     std::pair<uint64_t, bool> Relinearize(TxGraphImpl& graph, int level, uint64_t max_cost) noexcept final;
     302                 :             :     void AppendChunkFeerates(std::vector<FeeFrac>& ret) const noexcept final;
     303                 :             :     uint64_t AppendTrimData(std::vector<TrimTxData>& ret, std::vector<std::pair<GraphIndex, GraphIndex>>& deps) const noexcept final;
     304                 :             :     void GetAncestorRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept final;
     305                 :             :     void GetDescendantRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept final;
     306                 :             :     bool GetClusterRefs(TxGraphImpl& graph, std::span<TxGraph::Ref*> range, LinearizationIndex start_pos) noexcept final;
     307                 :             :     FeePerWeight GetIndividualFeerate(DepGraphIndex idx) noexcept final;
     308                 :             :     void SetFee(TxGraphImpl& graph, int level, DepGraphIndex idx, int64_t fee) noexcept final;
     309                 :             :     void SanityCheck(const TxGraphImpl& graph, int level) const final;
     310                 :             : };
     311                 :             : 
     312                 :             : /** An implementation of Cluster that only supports 1 transaction. */
     313                 :           0 : class SingletonClusterImpl final : public Cluster
     314                 :             : {
     315                 :             :     friend class TxGraphImpl;
     316                 :             : 
     317                 :             :     /** The feerate of the (singular) transaction in this Cluster. */
     318                 :             :     FeePerWeight m_feerate;
     319                 :             :     /** Constant to indicate that this Cluster is empty. */
     320                 :             :     static constexpr auto NO_GRAPH_INDEX = GraphIndex(-1);
     321                 :             :     /** The GraphIndex of the transaction. NO_GRAPH_INDEX if this Cluster is empty. */
     322                 :             :     GraphIndex m_graph_index = NO_GRAPH_INDEX;
     323                 :             : 
     324                 :             : public:
     325                 :             :     /** The smallest number of transactions this Cluster implementation is intended for. */
     326                 :             :     static constexpr DepGraphIndex MIN_INTENDED_TX_COUNT{1};
     327                 :             :     /** The largest number of transactions this Cluster implementation supports. */
     328                 :             :     static constexpr DepGraphIndex MAX_TX_COUNT{1};
     329                 :             : 
     330                 :             :     SingletonClusterImpl() noexcept = delete;
     331                 :             :     /** Construct an empty SingletonClusterImpl. */
     332                 :      137882 :     explicit SingletonClusterImpl(uint64_t sequence) noexcept : Cluster(sequence) {}
     333                 :             : 
     334                 :             :     size_t TotalMemoryUsage() const noexcept final;
     335                 :    12074674 :     constexpr DepGraphIndex GetMinIntendedTxCount() const noexcept final { return MIN_INTENDED_TX_COUNT; }
     336                 :    12076106 :     constexpr DepGraphIndex GetMaxTxCount() const noexcept final { return MAX_TX_COUNT; }
     337                 :    97463754 :     LinearizationIndex GetTxCount() const noexcept final { return m_graph_index != NO_GRAPH_INDEX; }
     338                 :        7920 :     DepGraphIndex GetDepGraphIndexRange() const noexcept final { return GetTxCount(); }
     339         [ +  + ]:    12214277 :     uint64_t GetTotalTxSize() const noexcept final { return GetTxCount() ? m_feerate.size : 0; }
     340                 :    12074680 :     GraphIndex GetClusterEntry(DepGraphIndex index) const noexcept final { Assume(index == 0); Assume(GetTxCount()); return m_graph_index; }
     341                 :             :     DepGraphIndex AppendTransaction(GraphIndex graph_idx, FeePerWeight feerate) noexcept final;
     342                 :             :     void AddDependencies(SetType parents, DepGraphIndex child) noexcept final;
     343                 :             :     void ExtractTransactions(const std::function<void (DepGraphIndex, GraphIndex, FeePerWeight)>& visit1_fn, const std::function<void (DepGraphIndex, GraphIndex, SetType)>& visit2_fn) noexcept final;
     344                 :             :     int GetLevel(const TxGraphImpl& graph) const noexcept final;
     345                 :       14594 :     void UpdateMapping(DepGraphIndex cluster_idx, GraphIndex graph_idx) noexcept final { Assume(cluster_idx == 0); m_graph_index = graph_idx; }
     346                 :             :     void Updated(TxGraphImpl& graph, int level, bool rename) noexcept final;
     347                 :             :     void RemoveChunkData(TxGraphImpl& graph) noexcept final;
     348                 :             :     Cluster* CopyToStaging(TxGraphImpl& graph) const noexcept final;
     349                 :             :     void GetConflicts(const TxGraphImpl& graph, std::vector<Cluster*>& out) const noexcept final;
     350                 :             :     void MakeStagingTransactionsMissing(TxGraphImpl& graph) noexcept final;
     351                 :             :     void Clear(TxGraphImpl& graph, int level) noexcept final;
     352                 :             :     void MoveToMain(TxGraphImpl& graph) noexcept final;
     353                 :             :     void Compact() noexcept final;
     354                 :             :     void ApplyRemovals(TxGraphImpl& graph, int level, std::span<GraphIndex>& to_remove) noexcept final;
     355                 :             :     [[nodiscard]] bool Split(TxGraphImpl& graph, int level) noexcept final;
     356                 :             :     void Merge(TxGraphImpl& graph, int level, Cluster& cluster) noexcept final;
     357                 :             :     void ApplyDependencies(TxGraphImpl& graph, int level, std::span<std::pair<GraphIndex, GraphIndex>> to_apply) noexcept final;
     358                 :             :     std::pair<uint64_t, bool> Relinearize(TxGraphImpl& graph, int level, uint64_t max_cost) noexcept final;
     359                 :             :     void AppendChunkFeerates(std::vector<FeeFrac>& ret) const noexcept final;
     360                 :             :     uint64_t AppendTrimData(std::vector<TrimTxData>& ret, std::vector<std::pair<GraphIndex, GraphIndex>>& deps) const noexcept final;
     361                 :             :     void GetAncestorRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept final;
     362                 :             :     void GetDescendantRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept final;
     363                 :             :     bool GetClusterRefs(TxGraphImpl& graph, std::span<TxGraph::Ref*> range, LinearizationIndex start_pos) noexcept final;
     364                 :             :     FeePerWeight GetIndividualFeerate(DepGraphIndex idx) noexcept final;
     365                 :             :     void SetFee(TxGraphImpl& graph, int level, DepGraphIndex idx, int64_t fee) noexcept final;
     366                 :             :     void SanityCheck(const TxGraphImpl& graph, int level) const final;
     367                 :             : };
     368                 :             : 
     369                 :             : /** The transaction graph, including staged changes.
     370                 :             :  *
     371                 :             :  * The overall design of the data structure consists of 3 interlinked representations:
     372                 :             :  * - The transactions (held as a vector of TxGraphImpl::Entry inside TxGraphImpl).
     373                 :             :  * - The clusters (Cluster objects in per-quality vectors inside TxGraphImpl::ClusterSet).
     374                 :             :  * - The Refs (TxGraph::Ref objects, held externally by users of the TxGraph class)
     375                 :             :  *
     376                 :             :  * The Clusters are kept in one or two ClusterSet objects, one for the "main" graph, and one for
     377                 :             :  * the proposed changes ("staging"). If a transaction occurs in both, they share the same Entry,
     378                 :             :  * but there will be a separate Cluster per graph.
     379                 :             :  *
     380                 :             :  * Clusters and Refs contain the index of the Entry objects they refer to, and the Entry objects
     381                 :             :  * refer back to the Clusters and Refs the corresponding transaction is contained in.
     382                 :             :  *
     383                 :             :  * While redundant, this permits moving all of them independently, without invalidating things
     384                 :             :  * or costly iteration to fix up everything:
     385                 :             :  * - Entry objects can be moved to fill holes left by removed transactions in the Entry vector
     386                 :             :  *   (see TxGraphImpl::Compact).
     387                 :             :  * - Clusters can be rewritten continuously (removals can cause them to split, new dependencies
     388                 :             :  *   can cause them to be merged).
     389                 :             :  * - Ref objects can be held outside the class, while permitting them to be moved around, and
     390                 :             :  *   inherited from.
     391                 :             :  */
     392                 :             : class TxGraphImpl final : public TxGraph
     393                 :             : {
     394                 :             :     friend class Cluster;
     395                 :             :     friend class SingletonClusterImpl;
     396                 :             :     friend class GenericClusterImpl;
     397                 :             :     friend class BlockBuilderImpl;
     398                 :             : private:
     399                 :             :     /** Internal RNG. */
     400                 :             :     FastRandomContext m_rng;
     401                 :             :     /** This TxGraphImpl's maximum cluster count limit. */
     402                 :             :     const DepGraphIndex m_max_cluster_count;
     403                 :             :     /** This TxGraphImpl's maximum cluster size limit. */
     404                 :             :     const uint64_t m_max_cluster_size;
     405                 :             :     /** The amount of linearization work needed per cluster to be considered acceptable. */
     406                 :             :     const uint64_t m_acceptable_cost;
     407                 :             :     /** Fallback ordering for transactions. */
     408                 :             :     const std::function<std::strong_ordering(const TxGraph::Ref&, const TxGraph::Ref&)> m_fallback_order;
     409                 :             : 
     410                 :             :     /** Information about one group of Clusters to be merged. */
     411                 :             :     struct GroupEntry
     412                 :             :     {
     413                 :             :         /** Where the clusters to be merged start in m_group_clusters. */
     414                 :             :         uint32_t m_cluster_offset;
     415                 :             :         /** How many clusters to merge. */
     416                 :             :         uint32_t m_cluster_count;
     417                 :             :         /** Where the dependencies for this cluster group in m_deps_to_add start. */
     418                 :             :         uint32_t m_deps_offset;
     419                 :             :         /** How many dependencies to add. */
     420                 :             :         uint32_t m_deps_count;
     421                 :             :     };
     422                 :             : 
     423                 :             :     /** Information about all groups of Clusters to be merged. */
     424                 :      100624 :     struct GroupData
     425                 :             :     {
     426                 :             :         /** The groups of Clusters to be merged. */
     427                 :             :         std::vector<GroupEntry> m_groups;
     428                 :             :         /** Which clusters are to be merged. GroupEntry::m_cluster_offset indexes into this. */
     429                 :             :         std::vector<Cluster*> m_group_clusters;
     430                 :             :     };
     431                 :             : 
     432                 :             :     /** The collection of all Clusters in main or staged. */
     433                 :             :     struct ClusterSet
     434                 :             :     {
     435                 :             :         /** The vectors of clusters, one vector per quality level. ClusterSetIndex indexes into each. */
     436                 :             :         std::array<std::vector<std::unique_ptr<Cluster>>, int(QualityLevel::NONE)> m_clusters;
     437                 :             :         /** Which removals have yet to be applied. */
     438                 :             :         std::vector<GraphIndex> m_to_remove;
     439                 :             :         /** Which dependencies are to be added ((parent,child) pairs). GroupData::m_deps_offset indexes
     440                 :             :          *  into this. */
     441                 :             :         std::vector<std::pair<GraphIndex, GraphIndex>> m_deps_to_add;
     442                 :             :         /** Information about the merges to be performed, if known. */
     443                 :             :         std::optional<GroupData> m_group_data = GroupData{};
     444                 :             :         /** Which entries were removed in this ClusterSet (so they can be wiped on abort). This
     445                 :             :          *  includes all entries which have an (R) removed locator at this level (staging only),
     446                 :             :          *  plus optionally any transaction in m_unlinked. */
     447                 :             :         std::vector<GraphIndex> m_removed;
     448                 :             :         /** Total number of transactions in this graph (sum of all transaction counts in all
     449                 :             :          *  Clusters, and for staging also those inherited from the main ClusterSet). */
     450                 :             :         GraphIndex m_txcount{0};
     451                 :             :         /** Total number of individually oversized transactions in the graph. */
     452                 :             :         GraphIndex m_txcount_oversized{0};
     453                 :             :         /** Whether this graph is oversized (if known). */
     454                 :             :         std::optional<bool> m_oversized{false};
     455                 :             :         /** The combined TotalMemoryUsage of all clusters in this level (only Clusters that
     456                 :             :          *  are materialized; in staging, implicit Clusters from main are not counted), */
     457                 :             :         size_t m_cluster_usage{0};
     458                 :             : 
     459                 :       72555 :         ClusterSet() noexcept = default;
     460                 :             :     };
     461                 :             : 
     462                 :             :     /** The main ClusterSet. */
     463                 :             :     ClusterSet m_main_clusterset;
     464                 :             :     /** The staging ClusterSet, if any. */
     465                 :             :     std::optional<ClusterSet> m_staging_clusterset;
     466                 :             :     /** Next sequence number to assign to created Clusters. */
     467                 :             :     uint64_t m_next_sequence_counter{0};
     468                 :             : 
     469                 :             :     /** Information about a chunk in the main graph. */
     470                 :             :     struct ChunkData
     471                 :             :     {
     472                 :             :         /** The Entry which is the last transaction of the chunk. */
     473                 :             :         mutable GraphIndex m_graph_index;
     474                 :             :         /** How many transactions the chunk contains (-1 = singleton tail of cluster). */
     475                 :             :         LinearizationIndex m_chunk_count;
     476                 :             : 
     477                 :      173582 :         ChunkData(GraphIndex graph_index, LinearizationIndex chunk_count) noexcept :
     478                 :      173582 :             m_graph_index{graph_index}, m_chunk_count{chunk_count} {}
     479                 :             :     };
     480                 :             : 
     481                 :             :     /** Compare two Cluster* by their m_sequence value (while supporting nullptr). */
     482                 :      180733 :     static std::strong_ordering CompareClusters(Cluster* a, Cluster* b) noexcept
     483                 :             :     {
     484                 :             :         // The nullptr pointer compares before everything else.
     485         [ -  + ]:      180733 :         if (a == nullptr || b == nullptr) {
     486   [ #  #  #  # ]:           0 :             return (a != nullptr) <=> (b != nullptr);
     487                 :             :         }
     488                 :             :         // If neither pointer is nullptr, compare the Clusters' sequence numbers.
     489         [ +  + ]:      180733 :         Assume(a == b || a->m_sequence != b->m_sequence);
     490   [ +  +  +  + ]:      180733 :         return a->m_sequence <=> b->m_sequence;
     491                 :             :     }
     492                 :             : 
     493                 :             :     /** Compare two entries (which must both exist within the main graph). */
     494                 :   161189050 :     std::strong_ordering CompareMainTransactions(GraphIndex a, GraphIndex b) const noexcept
     495                 :             :     {
     496         [ -  + ]:   161189050 :         if (a == b) return std::strong_ordering::equal;
     497   [ -  +  +  -  :   161189050 :         Assume(a < m_entries.size() && b < m_entries.size());
                   +  + ]
     498         [ +  + ]:   161189050 :         const auto& entry_a = m_entries[a];
     499                 :   161189050 :         const auto& entry_b = m_entries[b];
     500                 :             :         // Compare chunk feerates, and return result if it differs.
     501         [ +  + ]:   161189050 :         auto feerate_cmp = ByRatio{entry_b.m_main_chunk_feerate} <=> ByRatio{entry_a.m_main_chunk_feerate};
     502         [ +  + ]:   161189050 :         if (feerate_cmp != 0) return feerate_cmp;
     503                 :             :         // Compare equal-feerate chunk prefix size for comparing equal chunk feerates. This does two
     504                 :             :         // things: it distinguishes equal-feerate chunks within the same cluster (because later
     505                 :             :         // ones will always have a higher prefix size), and it may distinguish equal-feerate chunks
     506                 :             :         // from distinct clusters.
     507         [ +  + ]:    89787104 :         if (entry_a.m_main_equal_feerate_chunk_prefix_size != entry_b.m_main_equal_feerate_chunk_prefix_size) {
     508         [ +  + ]:     1667031 :             return entry_a.m_main_equal_feerate_chunk_prefix_size <=> entry_b.m_main_equal_feerate_chunk_prefix_size;
     509                 :             :         }
     510                 :             :         // Compare by maximum m_fallback_order element to order equal-feerate chunks in distinct
     511                 :             :         // clusters, when the equal-feerate-prefix size is also the same.
     512                 :    88120073 :         const auto& locator_a = entry_a.m_locator[0];
     513                 :    88120073 :         const auto& locator_b = entry_b.m_locator[0];
     514         [ +  + ]:    88120073 :         Assume(locator_a.IsPresent() && locator_b.IsPresent());
     515         [ +  + ]:    88120073 :         if (locator_a.cluster != locator_b.cluster) {
     516                 :    86982212 :             auto fallback_cmp = m_fallback_order(*m_entries[entry_a.m_main_max_chunk_fallback].m_ref,
     517                 :    86982212 :                                                  *m_entries[entry_b.m_main_max_chunk_fallback].m_ref);
     518         [ +  - ]:    86982212 :             if (fallback_cmp != 0) return fallback_cmp;
     519                 :             :             // This shouldn't be reachable as m_fallback_order defines a strong ordering.
     520                 :           0 :             Assume(false);
     521                 :           0 :             return CompareClusters(locator_a.cluster, locator_b.cluster);
     522                 :             :         }
     523                 :             :         // Within a single chunk, sort by position within cluster linearization.
     524   [ +  -  +  + ]:     1137861 :         return entry_a.m_main_lin_index <=> entry_b.m_main_lin_index;
     525                 :             :     }
     526                 :             : 
     527                 :             :     /** Comparator for ChunkData objects in mining order. */
     528                 :             :     class ChunkOrder
     529                 :             :     {
     530                 :             :         const TxGraphImpl* const m_graph;
     531                 :             :     public:
     532                 :        1413 :         explicit ChunkOrder(const TxGraphImpl* graph) : m_graph(graph) {}
     533                 :             : 
     534                 :     2136921 :         bool operator()(const ChunkData& a, const ChunkData& b) const noexcept
     535                 :             :         {
     536                 :     2136921 :             return m_graph->CompareMainTransactions(a.m_graph_index, b.m_graph_index) < 0;
     537                 :             :         }
     538                 :             :     };
     539                 :             : 
     540                 :             :     /** Definition for the mining index type. */
     541                 :             :     using ChunkIndex = std::set<ChunkData, ChunkOrder>;
     542                 :             : 
     543                 :             :     /** Index of ChunkData objects, indexing the last transaction in each chunk in the main
     544                 :             :      *  graph. */
     545                 :             :     ChunkIndex m_main_chunkindex;
     546                 :             :     /** Number of index-observing objects in existence (BlockBuilderImpls). */
     547                 :             :     size_t m_main_chunkindex_observers{0};
     548                 :             :     /** Cache of discarded ChunkIndex node handles to reuse, avoiding additional allocation. */
     549                 :             :     std::vector<ChunkIndex::node_type> m_main_chunkindex_discarded;
     550                 :             : 
     551                 :             :     /** A Locator that describes whether, where, and in which Cluster an Entry appears.
     552                 :             :      *  Every Entry has MAX_LEVELS locators, as it may appear in one Cluster per level.
     553                 :             :      *
     554                 :             :      *  Each level of a Locator is in one of three states:
     555                 :             :      *
     556                 :             :      *  - (P)resent: actually occurs in a Cluster at that level.
     557                 :             :      *
     558                 :             :      *  - (M)issing:
     559                 :             :      *    - In the main graph:    the transaction does not exist in main.
     560                 :             :      *    - In the staging graph: the transaction's existence is the same as in main. If it doesn't
     561                 :             :      *                            exist in main, (M) in staging means it does not exist there
     562                 :             :      *                            either. If it does exist in main, (M) in staging means the
     563                 :             :      *                            cluster it is in has not been modified in staging, and thus the
     564                 :             :      *                            transaction implicitly exists in staging too (without explicit
     565                 :             :      *                            Cluster object; see PullIn() to create it in staging too).
     566                 :             :      *
     567                 :             :      *  - (R)emoved: only possible in staging; it means the transaction exists in main, but is
     568                 :             :      *               removed in staging.
     569                 :             :      *
     570                 :             :      * The following combinations are possible:
     571                 :             :      * - (M,M): the transaction doesn't exist in either graph.
     572                 :             :      * - (P,M): the transaction exists in both, but only exists explicitly in a Cluster object in
     573                 :             :      *          main. Its existence in staging is inherited from main.
     574                 :             :      * - (P,P): the transaction exists in both, and is materialized in both. Thus, the clusters
     575                 :             :      *          and/or their linearizations may be different in main and staging.
     576                 :             :      * - (M,P): the transaction is added in staging, and does not exist in main.
     577                 :             :      * - (P,R): the transaction exists in main, but is removed in staging.
     578                 :             :      *
     579                 :             :      * When staging does not exist, only (M,M) and (P,M) are possible.
     580                 :             :      */
     581                 :             :     struct Locator
     582                 :             :     {
     583                 :             :         /** Which Cluster the Entry appears in (nullptr = missing). */
     584                 :             :         Cluster* cluster{nullptr};
     585                 :             :         /** Where in the Cluster it appears (if cluster == nullptr: 0 = missing, -1 = removed). */
     586                 :             :         DepGraphIndex index{0};
     587                 :             : 
     588                 :             :         /** Mark this Locator as missing (= same as lower level, or non-existing if level 0). */
     589                 :        2177 :         void SetMissing() noexcept { cluster = nullptr; index = 0; }
     590                 :             :         /** Mark this Locator as removed (not allowed in level 0). */
     591                 :        2177 :         void SetRemoved() noexcept { cluster = nullptr; index = DepGraphIndex(-1); }
     592                 :             :         /** Mark this Locator as present, in the specified Cluster. */
     593                 :      384985 :         void SetPresent(Cluster* c, DepGraphIndex i) noexcept { cluster = c; index = i; }
     594                 :             :         /** Check if this Locator is missing. */
     595   [ -  +  +  + ]:    12515213 :         bool IsMissing() const noexcept { return cluster == nullptr && index == 0; }
     596                 :             :         /** Check if this Locator is removed. */
     597   [ +  -  -  +  :    12480764 :         bool IsRemoved() const noexcept { return cluster == nullptr && index == DepGraphIndex(-1); }
                   -  + ]
     598                 :             :         /** Check if this Locator is present (in some Cluster). */
     599   [ -  +  +  - ]:    88120084 :         bool IsPresent() const noexcept { return cluster != nullptr; }
     600                 :             :     };
     601                 :             : 
     602                 :             :     /** Internal information about each transaction in a TxGraphImpl. */
     603                 :      136084 :     struct Entry
     604                 :             :     {
     605                 :             :         /** Pointer to the corresponding Ref object if any, or nullptr if unlinked. */
     606                 :             :         Ref* m_ref{nullptr};
     607                 :             :         /** Iterator to the corresponding ChunkData, if any, and m_main_chunkindex.end() otherwise.
     608                 :             :          *  This is initialized on construction of the Entry, in AddTransaction. */
     609                 :             :         ChunkIndex::iterator m_main_chunkindex_iterator;
     610                 :             :         /** Which Cluster and position therein this Entry appears in. ([0] = main, [1] = staged). */
     611                 :             :         Locator m_locator[MAX_LEVELS];
     612                 :             :         /** The chunk feerate of this transaction in main (if present in m_locator[0]). */
     613                 :             :         FeePerWeight m_main_chunk_feerate;
     614                 :             :         /** The equal-feerate chunk prefix size of this transaction in main. If the transaction is
     615                 :             :          *  part of chunk C in main, then this gives the sum of the sizes of all chunks in C's
     616                 :             :          *  cluster, whose feerate is equal to that of C, which do not appear after C itself in
     617                 :             :          *  the cluster's linearization.
     618                 :             :          *  This provides a way to sort equal-feerate chunks across clusters, in a way that agrees
     619                 :             :          *  with the within-cluster chunk ordering. */
     620                 :             :         int32_t m_main_equal_feerate_chunk_prefix_size;
     621                 :             :         /** The position this transaction has in the main linearization (if present). */
     622                 :             :         LinearizationIndex m_main_lin_index;
     623                 :             :         /** Of all transactions within this transaction's chunk in main (if present there), the
     624                 :             :          *  maximal one according to m_fallback_order. */
     625                 :             :         GraphIndex m_main_max_chunk_fallback = GraphIndex(-1);
     626                 :             :     };
     627                 :             : 
     628                 :             :     /** The set of all transactions (in all levels combined). GraphIndex values index into this. */
     629                 :             :     std::vector<Entry> m_entries;
     630                 :             : 
     631                 :             :     /** Set of Entries which have no linked Ref anymore. */
     632                 :             :     std::vector<GraphIndex> m_unlinked;
     633                 :             : 
     634                 :             : public:
     635                 :             :     /** Construct a new TxGraphImpl with the specified limits and fallback order. */
     636                 :        1413 :     explicit TxGraphImpl(
     637                 :             :         DepGraphIndex max_cluster_count,
     638                 :             :         uint64_t max_cluster_size,
     639                 :             :         uint64_t acceptable_cost,
     640                 :             :         const std::function<std::strong_ordering(const TxGraph::Ref&, const TxGraph::Ref&)>& fallback_order
     641                 :        1413 :     ) noexcept :
     642                 :        1413 :         m_max_cluster_count(max_cluster_count),
     643                 :        1413 :         m_max_cluster_size(max_cluster_size),
     644                 :        1413 :         m_acceptable_cost(acceptable_cost),
     645                 :        1413 :         m_fallback_order(fallback_order),
     646                 :        2826 :         m_main_chunkindex(ChunkOrder(this))
     647                 :             :     {
     648                 :        1413 :         Assume(max_cluster_count >= 1);
     649                 :        1413 :         Assume(max_cluster_count <= MAX_CLUSTER_COUNT_LIMIT);
     650                 :        1413 :     }
     651                 :             : 
     652                 :             :     /** Destructor. */
     653                 :             :     ~TxGraphImpl() noexcept;
     654                 :             : 
     655                 :             :     // Cannot move or copy (would invalidate TxGraphImpl* in Ref, MiningOrder, EvictionOrder).
     656                 :             :     TxGraphImpl(const TxGraphImpl&) = delete;
     657                 :             :     TxGraphImpl& operator=(const TxGraphImpl&) = delete;
     658                 :             :     TxGraphImpl(TxGraphImpl&&) = delete;
     659                 :             :     TxGraphImpl& operator=(TxGraphImpl&&) = delete;
     660                 :             : 
     661                 :             :     // Simple helper functions.
     662                 :             : 
     663                 :             :     /** Swap the Entry referred to by a and the one referred to by b. Gather main clusters to
     664                 :             :      *  update afterwards. */
     665                 :             :     void SwapIndexes(GraphIndex a, GraphIndex b, std::vector<Cluster*>& affected_main) noexcept;
     666                 :             :     /** If idx exists in the specified level ClusterSet (explicitly, or in the level below and not
     667                 :             :     *   removed), return the Cluster it is in. Otherwise, return nullptr. */
     668                 :      719660 :     Cluster* FindCluster(GraphIndex idx, int level) const noexcept { return FindClusterAndLevel(idx, level).first; }
     669                 :             :     /** Like FindCluster, but also return what level the match was found in (-1 if not found). */
     670                 :             :     std::pair<Cluster*, int> FindClusterAndLevel(GraphIndex idx, int level) const noexcept;
     671                 :             :     /** Extract a Cluster from its ClusterSet, and set its quality to QualityLevel::NONE. */
     672                 :             :     std::unique_ptr<Cluster> ExtractCluster(int level, QualityLevel quality, ClusterSetIndex setindex) noexcept;
     673                 :             :     /** Delete a Cluster. */
     674                 :             :     void DeleteCluster(Cluster& cluster, int level) noexcept;
     675                 :             :     /** Insert a Cluster into its ClusterSet. */
     676                 :             :     ClusterSetIndex InsertCluster(int level, std::unique_ptr<Cluster>&& cluster, QualityLevel quality) noexcept;
     677                 :             :     /** Change the QualityLevel of a Cluster (identified by old_quality and old_index). */
     678                 :             :     void SetClusterQuality(int level, QualityLevel old_quality, ClusterSetIndex old_index, QualityLevel new_quality) noexcept;
     679                 :             :     /** Get the index of the top level ClusterSet (staging if it exists, main otherwise). */
     680         [ +  + ]:     2753182 :     int GetTopLevel() const noexcept { return m_staging_clusterset.has_value(); }
     681                 :             :     /** Get the specified level (staging if it exists and level is TOP, main otherwise). */
     682   [ -  -  +  +  :       73781 :     int GetSpecifiedLevel(Level level) const noexcept { return level == Level::TOP && m_staging_clusterset.has_value(); }
          +  +  -  -  -  
          -  -  -  -  -  
             -  -  +  + ]
     683                 :             :     /** Get a reference to the ClusterSet at the specified level (which must exist). */
     684                 :             :     ClusterSet& GetClusterSet(int level) noexcept;
     685                 :             :     const ClusterSet& GetClusterSet(int level) const noexcept;
     686                 :             :     /** Make a transaction not exist at a specified level. It must currently exist there.
     687                 :             :      *  oversized_tx indicates whether the transaction is an individually-oversized one
     688                 :             :      *  (OVERSIZED_SINGLETON). */
     689                 :             :     void ClearLocator(int level, GraphIndex index, bool oversized_tx) noexcept;
     690                 :             :     /** Find which Clusters in main conflict with ones in staging. */
     691                 :             :     std::vector<Cluster*> GetConflicts() const noexcept;
     692                 :             :     /** Clear an Entry's ChunkData. */
     693                 :             :     void ClearChunkData(Entry& entry) noexcept;
     694                 :             :     /** Give an Entry a ChunkData object. */
     695                 :             :     void CreateChunkData(GraphIndex idx, LinearizationIndex chunk_count) noexcept;
     696                 :             :     /** Create an empty GenericClusterImpl object. */
     697                 :        1760 :     std::unique_ptr<GenericClusterImpl> CreateEmptyGenericCluster() noexcept
     698                 :             :     {
     699                 :        1760 :         return std::make_unique<GenericClusterImpl>(m_next_sequence_counter++);
     700                 :             :     }
     701                 :             :     /** Create an empty SingletonClusterImpl object. */
     702                 :      137882 :     std::unique_ptr<SingletonClusterImpl> CreateEmptySingletonCluster() noexcept
     703                 :             :     {
     704                 :      137882 :         return std::make_unique<SingletonClusterImpl>(m_next_sequence_counter++);
     705                 :             :     }
     706                 :             :     /** Create an empty Cluster of the appropriate implementation for the specified (maximum) tx
     707                 :             :      *  count. */
     708                 :      137895 :     std::unique_ptr<Cluster> CreateEmptyCluster(DepGraphIndex tx_count) noexcept
     709                 :             :     {
     710         [ +  + ]:      137895 :         if (tx_count >= SingletonClusterImpl::MIN_INTENDED_TX_COUNT && tx_count <= SingletonClusterImpl::MAX_TX_COUNT) {
     711                 :      136467 :             return CreateEmptySingletonCluster();
     712                 :             :         }
     713         [ +  - ]:        1428 :         if (tx_count >= GenericClusterImpl::MIN_INTENDED_TX_COUNT && tx_count <= GenericClusterImpl::MAX_TX_COUNT) {
     714         [ -  + ]:        1428 :             return CreateEmptyGenericCluster();
     715                 :             :         }
     716                 :           0 :         AssertUnreachable();
     717                 :             :     }
     718                 :             : 
     719                 :             :     // Functions for handling Refs.
     720                 :             : 
     721                 :             :     /** Only called by Ref's move constructor/assignment to update Ref locations. */
     722                 :       65561 :     void UpdateRef(GraphIndex idx, Ref& new_location) noexcept final
     723                 :             :     {
     724                 :       65561 :         auto& entry = m_entries[idx];
     725                 :       65561 :         Assume(entry.m_ref != nullptr);
     726                 :       65561 :         entry.m_ref = &new_location;
     727                 :       65561 :     }
     728                 :             : 
     729                 :             :     /** Only called by Ref::~Ref to unlink Refs, and Ref's move assignment. */
     730                 :       72073 :     void UnlinkRef(GraphIndex idx) noexcept final
     731                 :             :     {
     732         [ -  + ]:       72073 :         auto& entry = m_entries[idx];
     733         [ -  + ]:       72073 :         Assume(entry.m_ref != nullptr);
     734   [ -  +  +  + ]:       72073 :         Assume(m_main_chunkindex_observers == 0 || !entry.m_locator[0].IsPresent());
     735                 :             :         // Remove all chunk index entries for the affected cluster, to avoid any chunk indexes
     736                 :             :         // referencing unlinked/destroyed Refs.
     737         [ +  + ]:       72073 :         if (entry.m_locator[0].IsPresent()) {
     738                 :       46125 :             entry.m_locator[0].cluster->RemoveChunkData(*this);
     739                 :             :         }
     740                 :       72073 :         entry.m_ref = nullptr;
     741                 :             :         // Mark the transaction as to be removed in all levels where it explicitly or implicitly
     742                 :             :         // exists.
     743                 :       72073 :         bool exists_anywhere{false};
     744                 :       72073 :         bool exists{false};
     745         [ +  + ]:      144146 :         for (int level = 0; level <= GetTopLevel(); ++level) {
     746         [ +  + ]:       72073 :             if (entry.m_locator[level].IsPresent()) {
     747                 :             :                 exists_anywhere = true;
     748                 :             :                 exists = true;
     749         [ +  - ]:       25948 :             } else if (entry.m_locator[level].IsRemoved()) {
     750                 :             :                 exists = false;
     751                 :             :             }
     752         [ -  + ]:       25948 :             if (exists) {
     753                 :       46125 :                 auto& clusterset = GetClusterSet(level);
     754                 :       46125 :                 clusterset.m_to_remove.push_back(idx);
     755                 :             :                 // Force recomputation of grouping data.
     756         [ +  + ]:       46125 :                 clusterset.m_group_data = std::nullopt;
     757                 :             :                 // Do not wipe the oversized state of main if staging exists. The reason for this
     758                 :             :                 // is that the alternative would mean that cluster merges may need to be applied to
     759                 :             :                 // a formerly-oversized main graph while staging exists (to satisfy chunk feerate
     760                 :             :                 // queries into main, for example), and such merges could conflict with pulls of
     761                 :             :                 // some of their constituents into staging.
     762   [ +  -  +  - ]:      118198 :                 if (level == GetTopLevel() && clusterset.m_oversized == true) {
     763                 :           0 :                     clusterset.m_oversized = std::nullopt;
     764                 :             :                 }
     765                 :             :             }
     766                 :             :         }
     767                 :       72073 :         m_unlinked.push_back(idx);
     768         [ +  + ]:       72073 :         if (!exists_anywhere) Compact();
     769                 :       72073 :     }
     770                 :             : 
     771                 :             :     // Functions related to various normalization/application steps.
     772                 :             :     /** Get rid of unlinked Entry objects in m_entries, if possible (this changes the GraphIndex
     773                 :             :      *  values for remaining Entry objects, so this only does something when no to-be-applied
     774                 :             :      *  operations or staged removals referring to GraphIndexes remain). */
     775                 :             :     void Compact() noexcept;
     776                 :             :     /** If cluster is not in staging, copy it there, and return a pointer to it.
     777                 :             :     *   Staging must exist, and this modifies the locators of its
     778                 :             :     *   transactions from inherited (P,M) to explicit (P,P). */
     779                 :             :     Cluster* PullIn(Cluster* cluster, int level) noexcept;
     780                 :             :     /** Apply all removals queued up in m_to_remove to the relevant Clusters (which get a
     781                 :             :      *  NEEDS_SPLIT* QualityLevel) up to the specified level. */
     782                 :             :     void ApplyRemovals(int up_to_level) noexcept;
     783                 :             :     /** Split an individual cluster. */
     784                 :             :     void Split(Cluster& cluster, int level) noexcept;
     785                 :             :     /** Split all clusters that need splitting up to the specified level. */
     786                 :             :     void SplitAll(int up_to_level) noexcept;
     787                 :             :     /** Populate m_group_data based on m_deps_to_add in the specified level. */
     788                 :             :     void GroupClusters(int level) noexcept;
     789                 :             :     /** Merge the specified clusters. */
     790                 :             :     void Merge(std::span<Cluster*> to_merge, int level) noexcept;
     791                 :             :     /** Apply all m_deps_to_add to the relevant Clusters in the specified level. */
     792                 :             :     void ApplyDependencies(int level) noexcept;
     793                 :             :     /** Make a specified Cluster have quality ACCEPTABLE or OPTIMAL. */
     794                 :             :     void MakeAcceptable(Cluster& cluster, int level) noexcept;
     795                 :             :     /** Make all Clusters at the specified level have quality ACCEPTABLE or OPTIMAL. */
     796                 :             :     void MakeAllAcceptable(int level) noexcept;
     797                 :             : 
     798                 :             :     // Implementations for the public TxGraph interface.
     799                 :             : 
     800                 :             :     void AddTransaction(Ref& arg, const FeePerWeight& feerate) noexcept final;
     801                 :             :     void RemoveTransaction(const Ref& arg) noexcept final;
     802                 :             :     void AddDependency(const Ref& parent, const Ref& child) noexcept final;
     803                 :             :     void SetTransactionFee(const Ref&, int64_t fee) noexcept final;
     804                 :             : 
     805                 :             :     bool DoWork(uint64_t max_cost) noexcept final;
     806                 :             : 
     807                 :             :     void StartStaging() noexcept final;
     808                 :             :     void CommitStaging() noexcept final;
     809                 :             :     void AbortStaging() noexcept final;
     810                 :       71143 :     bool HaveStaging() const noexcept final { return m_staging_clusterset.has_value(); }
     811                 :             : 
     812                 :             :     bool Exists(const Ref& arg, Level level) noexcept final;
     813                 :             :     FeePerWeight GetMainChunkFeerate(const Ref& arg) noexcept final;
     814                 :             :     FeePerWeight GetIndividualFeerate(const Ref& arg) noexcept final;
     815                 :             :     std::vector<Ref*> GetCluster(const Ref& arg, Level level) noexcept final;
     816                 :             :     std::vector<Ref*> GetAncestors(const Ref& arg, Level level) noexcept final;
     817                 :             :     std::vector<Ref*> GetDescendants(const Ref& arg, Level level) noexcept final;
     818                 :             :     std::vector<Ref*> GetAncestorsUnion(std::span<const Ref* const> args, Level level) noexcept final;
     819                 :             :     std::vector<Ref*> GetDescendantsUnion(std::span<const Ref* const> args, Level level) noexcept final;
     820                 :             :     GraphIndex GetTransactionCount(Level level) noexcept final;
     821                 :             :     bool IsOversized(Level level) noexcept final;
     822                 :             :     std::strong_ordering CompareMainOrder(const Ref& a, const Ref& b) noexcept final;
     823                 :             :     GraphIndex CountDistinctClusters(std::span<const Ref* const> refs, Level level) noexcept final;
     824                 :             :     std::pair<std::vector<FeeFrac>, std::vector<FeeFrac>> GetMainStagingDiagrams() noexcept final;
     825                 :             :     std::vector<Ref*> Trim() noexcept final;
     826                 :             : 
     827                 :             :     std::unique_ptr<BlockBuilder> GetBlockBuilder() noexcept final;
     828                 :             :     std::pair<std::vector<Ref*>, FeePerWeight> GetWorstMainChunk() noexcept final;
     829                 :             : 
     830                 :             :     size_t GetMainMemoryUsage() noexcept final;
     831                 :             : 
     832                 :             :     void SanityCheck() const final;
     833                 :             : };
     834                 :             : 
     835                 :   325534851 : TxGraphImpl::ClusterSet& TxGraphImpl::GetClusterSet(int level) noexcept
     836                 :             : {
     837         [ +  + ]:   325534851 :     if (level == 0) return m_main_clusterset;
     838                 :      442257 :     Assume(level == 1);
     839                 :      442257 :     Assume(m_staging_clusterset.has_value());
     840                 :      442257 :     return *m_staging_clusterset;
     841                 :             : }
     842                 :             : 
     843                 :      224028 : const TxGraphImpl::ClusterSet& TxGraphImpl::GetClusterSet(int level) const noexcept
     844                 :             : {
     845         [ +  + ]:      224028 :     if (level == 0) return m_main_clusterset;
     846                 :       48682 :     Assume(level == 1);
     847                 :       48682 :     Assume(m_staging_clusterset.has_value());
     848                 :       48682 :     return *m_staging_clusterset;
     849                 :             : }
     850                 :             : 
     851                 :             : /** Implementation of the TxGraph::BlockBuilder interface. */
     852                 :             : class BlockBuilderImpl final : public TxGraph::BlockBuilder
     853                 :             : {
     854                 :             :     /** Which TxGraphImpl this object is doing block building for. It will have its
     855                 :             :      *  m_main_chunkindex_observers incremented as long as this BlockBuilderImpl exists. */
     856                 :             :     TxGraphImpl* const m_graph;
     857                 :             :     /** Cluster sequence numbers which we're not including further transactions from. */
     858                 :             :     std::unordered_set<uint64_t> m_excluded_clusters;
     859                 :             :     /** Iterator to the current chunk in the chunk index. end() if nothing further remains. */
     860                 :             :     TxGraphImpl::ChunkIndex::const_iterator m_cur_iter;
     861                 :             :     /** Which cluster the current chunk belongs to, so we can exclude further transactions from it
     862                 :             :      *  when that chunk is skipped. */
     863                 :             :     Cluster* m_cur_cluster;
     864                 :             :     /** Whether we know that m_cur_iter points to the last chunk of m_cur_cluster. */
     865                 :             :     bool m_known_end_of_cluster;
     866                 :             : 
     867                 :             :     // Move m_cur_iter / m_cur_cluster to the next acceptable chunk.
     868                 :             :     void Next() noexcept;
     869                 :             : 
     870                 :             : public:
     871                 :             :     /** Construct a new BlockBuilderImpl to build blocks for the provided graph. */
     872                 :             :     BlockBuilderImpl(TxGraphImpl& graph) noexcept;
     873                 :             : 
     874                 :             :     // Implement the public interface.
     875                 :             :     ~BlockBuilderImpl() final;
     876                 :             :     std::optional<std::pair<std::vector<TxGraph::Ref*>, FeePerWeight>> GetCurrentChunk() noexcept final;
     877                 :             :     void Include() noexcept final;
     878                 :             :     void Skip() noexcept final;
     879                 :             : };
     880                 :             : 
     881                 :      528624 : void TxGraphImpl::ClearChunkData(Entry& entry) noexcept
     882                 :             : {
     883         [ +  + ]:      528624 :     if (entry.m_main_chunkindex_iterator != m_main_chunkindex.end()) {
     884                 :      110901 :         Assume(m_main_chunkindex_observers == 0);
     885                 :             :         // If the Entry has a non-empty m_main_chunkindex_iterator, extract it, and move the handle
     886                 :             :         // to the cache of discarded chunkindex entries.
     887                 :      110901 :         m_main_chunkindex_discarded.emplace_back(m_main_chunkindex.extract(entry.m_main_chunkindex_iterator));
     888                 :      110901 :         entry.m_main_chunkindex_iterator = m_main_chunkindex.end();
     889                 :             :     }
     890                 :      528624 : }
     891                 :             : 
     892                 :      174901 : void TxGraphImpl::CreateChunkData(GraphIndex idx, LinearizationIndex chunk_count) noexcept
     893                 :             : {
     894         [ +  + ]:      174901 :     auto& entry = m_entries[idx];
     895                 :             :     // Make sure to not create chunk data for unlinked entries, which would make invoking
     896                 :             :     // m_fallback_order on them impossible.
     897         [ +  + ]:      174901 :     Assume(entry.m_ref != nullptr);
     898         [ +  + ]:      174901 :     if (!m_main_chunkindex_discarded.empty()) {
     899                 :             :         // Reuse an discarded node handle.
     900                 :        1319 :         auto& node = m_main_chunkindex_discarded.back().value();
     901                 :        1319 :         node.m_graph_index = idx;
     902                 :        1319 :         node.m_chunk_count = chunk_count;
     903                 :        1319 :         auto insert_result = m_main_chunkindex.insert(std::move(m_main_chunkindex_discarded.back()));
     904                 :        1319 :         Assume(insert_result.inserted);
     905                 :        1319 :         entry.m_main_chunkindex_iterator = insert_result.position;
     906                 :        1319 :         m_main_chunkindex_discarded.pop_back();
     907                 :        1319 :     } else {
     908                 :             :         // Construct a new entry.
     909                 :      173582 :         auto emplace_result = m_main_chunkindex.emplace(idx, chunk_count);
     910                 :      173582 :         Assume(emplace_result.second);
     911                 :      173582 :         entry.m_main_chunkindex_iterator = emplace_result.first;
     912                 :             :     }
     913                 :      174901 : }
     914                 :             : 
     915                 :       84248 : size_t GenericClusterImpl::TotalMemoryUsage() const noexcept
     916                 :             : {
     917                 :       84248 :     return // Dynamic memory allocated in this Cluster.
     918   [ -  +  -  + ]:      168496 :            memusage::DynamicUsage(m_mapping) + memusage::DynamicUsage(m_linearization) +
     919                 :             :            // Dynamic memory usage inside m_depgraph.
     920         [ -  + ]:       84248 :            m_depgraph.DynamicMemoryUsage() +
     921                 :             :            // Memory usage of the allocated Cluster itself.
     922                 :       84248 :            memusage::MallocUsage(sizeof(GenericClusterImpl)) +
     923                 :             :            // Memory usage of the ClusterSet::m_clusters entry.
     924                 :       84248 :            sizeof(std::unique_ptr<Cluster>);
     925                 :             : }
     926                 :             : 
     927                 :    12291068 : size_t SingletonClusterImpl::TotalMemoryUsage() const noexcept
     928                 :             : {
     929                 :    12291068 :     return // Memory usage of the allocated SingletonClusterImpl itself.
     930                 :    12291068 :            memusage::MallocUsage(sizeof(SingletonClusterImpl)) +
     931                 :             :            // Memory usage of the ClusterSet::m_clusters entry.
     932                 :    12291068 :            sizeof(std::unique_ptr<Cluster>);
     933                 :             : }
     934                 :             : 
     935                 :       74874 : uint64_t GenericClusterImpl::GetTotalTxSize() const noexcept
     936                 :             : {
     937                 :       74874 :     uint64_t ret{0};
     938         [ +  + ]:      566314 :     for (auto i : m_linearization) {
     939                 :      491440 :         ret += m_depgraph.FeeRate(i).size;
     940                 :             :     }
     941                 :       74874 :     return ret;
     942                 :             : }
     943                 :             : 
     944                 :          17 : DepGraphIndex GenericClusterImpl::AppendTransaction(GraphIndex graph_idx, FeePerWeight feerate) noexcept
     945                 :             : {
     946                 :          17 :     Assume(graph_idx != GraphIndex(-1));
     947                 :          17 :     auto ret = m_depgraph.AddTransaction(feerate);
     948                 :          17 :     m_mapping.push_back(graph_idx);
     949                 :          17 :     m_linearization.push_back(ret);
     950                 :          17 :     return ret;
     951                 :             : }
     952                 :             : 
     953                 :      136467 : DepGraphIndex SingletonClusterImpl::AppendTransaction(GraphIndex graph_idx, FeePerWeight feerate) noexcept
     954                 :             : {
     955                 :      136467 :     Assume(!GetTxCount());
     956                 :      136467 :     m_graph_index = graph_idx;
     957                 :      136467 :     m_feerate = feerate;
     958                 :      136467 :     return 0;
     959                 :             : }
     960                 :             : 
     961                 :          17 : void GenericClusterImpl::AddDependencies(SetType parents, DepGraphIndex child) noexcept
     962                 :             : {
     963                 :          17 :     m_depgraph.AddDependencies(parents, child);
     964                 :          17 : }
     965                 :             : 
     966                 :         383 : void SingletonClusterImpl::AddDependencies(SetType parents, DepGraphIndex child) noexcept
     967                 :             : {
     968                 :             :     // Singletons cannot have any dependencies.
     969         [ -  + ]:         383 :     Assume(child == 0);
     970         [ -  + ]:         383 :     Assume(parents == SetType{} || parents == SetType::Fill(0));
     971                 :         383 : }
     972                 :             : 
     973                 :          11 : void GenericClusterImpl::ExtractTransactions(const std::function<void (DepGraphIndex, GraphIndex, FeePerWeight)>& visit1_fn, const std::function<void (DepGraphIndex, GraphIndex, SetType)>& visit2_fn) noexcept
     974                 :             : {
     975         [ +  + ]:          47 :     for (auto pos : m_linearization) {
     976                 :          36 :         visit1_fn(pos, m_mapping[pos], FeePerWeight::FromFeeFrac(m_depgraph.FeeRate(pos)));
     977                 :             :     }
     978         [ +  + ]:          47 :     for (auto pos : m_linearization) {
     979                 :          36 :         visit2_fn(pos, m_mapping[pos], m_depgraph.GetReducedParents(pos));
     980                 :             :     }
     981                 :             :     // Purge this Cluster, now that everything has been moved.
     982                 :          11 :     m_depgraph = DepGraph<SetType>{};
     983         [ +  - ]:          11 :     m_linearization.clear();
     984         [ +  - ]:          11 :     m_mapping.clear();
     985                 :          11 : }
     986                 :             : 
     987                 :        7920 : void SingletonClusterImpl::ExtractTransactions(const std::function<void (DepGraphIndex, GraphIndex, FeePerWeight)>& visit1_fn, const std::function<void (DepGraphIndex, GraphIndex, SetType)>& visit2_fn) noexcept
     988                 :             : {
     989         [ +  - ]:        7920 :     if (GetTxCount()) {
     990                 :        7920 :         visit1_fn(0, m_graph_index, m_feerate);
     991                 :        7920 :         visit2_fn(0, m_graph_index, SetType{});
     992                 :        7920 :         m_graph_index = NO_GRAPH_INDEX;
     993                 :             :     }
     994                 :        7920 : }
     995                 :             : 
     996                 :       69352 : int GenericClusterImpl::GetLevel(const TxGraphImpl& graph) const noexcept
     997                 :             : {
     998                 :             :     // GetLevel() does not work for empty Clusters.
     999         [ +  - ]:       69352 :     if (!Assume(!m_linearization.empty())) return -1;
    1000                 :             : 
    1001                 :             :     // Pick an arbitrary Entry that occurs in this Cluster.
    1002                 :       69352 :     const auto& entry = graph.m_entries[m_mapping[m_linearization.front()]];
    1003                 :             :     // See if there is a level whose Locator matches this Cluster, if so return that level.
    1004         [ +  - ]:       69374 :     for (int level = 0; level < MAX_LEVELS; ++level) {
    1005         [ +  + ]:       69374 :         if (entry.m_locator[level].cluster == this) return level;
    1006                 :             :     }
    1007                 :             :     // Given that we started with an Entry that occurs in this Cluster, one of its Locators must
    1008                 :             :     // point back to it.
    1009                 :           0 :     AssertUnreachable();
    1010                 :             : }
    1011                 :             : 
    1012                 :    12139174 : int SingletonClusterImpl::GetLevel(const TxGraphImpl& graph) const noexcept
    1013                 :             : {
    1014                 :             :     // GetLevel() does not work for empty Clusters.
    1015         [ +  - ]:    12139174 :     if (!Assume(GetTxCount())) return -1;
    1016                 :             : 
    1017                 :             :     // Get the Entry in this Cluster.
    1018                 :    12139174 :     const auto& entry = graph.m_entries[m_graph_index];
    1019                 :             :     // See if there is a level whose Locator matches this Cluster, if so return that level.
    1020         [ +  - ]:    12139454 :     for (int level = 0; level < MAX_LEVELS; ++level) {
    1021         [ +  + ]:    12139454 :         if (entry.m_locator[level].cluster == this) return level;
    1022                 :             :     }
    1023                 :             :     // Given that we started with an Entry that occurs in this Cluster, one of its Locators must
    1024                 :             :     // point back to it.
    1025                 :           0 :     AssertUnreachable();
    1026                 :             : }
    1027                 :             : 
    1028                 :       29675 : void TxGraphImpl::ClearLocator(int level, GraphIndex idx, bool oversized_tx) noexcept
    1029                 :             : {
    1030         [ +  + ]:       29675 :     auto& entry = m_entries[idx];
    1031                 :       29675 :     auto& clusterset = GetClusterSet(level);
    1032         [ +  + ]:       29675 :     Assume(entry.m_locator[level].IsPresent());
    1033                 :             :     // Change the locator from Present to Missing or Removed.
    1034   [ +  +  -  + ]:       29675 :     if (level == 0 || !entry.m_locator[level - 1].IsPresent()) {
    1035                 :       27498 :         entry.m_locator[level].SetMissing();
    1036                 :             :     } else {
    1037                 :        2177 :         entry.m_locator[level].SetRemoved();
    1038                 :        2177 :         clusterset.m_removed.push_back(idx);
    1039                 :             :     }
    1040                 :             :     // Update the transaction count.
    1041                 :       29675 :     --clusterset.m_txcount;
    1042                 :       29675 :     clusterset.m_txcount_oversized -= oversized_tx;
    1043                 :             :     // If clearing main, adjust the status of Locators of this transaction in staging, if it exists.
    1044   [ +  +  +  + ]:       29675 :     if (level == 0 && GetTopLevel() == 1) {
    1045         [ +  + ]:        2124 :         if (entry.m_locator[1].IsRemoved()) {
    1046                 :        1580 :             entry.m_locator[1].SetMissing();
    1047         [ -  + ]:         544 :         } else if (!entry.m_locator[1].IsPresent()) {
    1048                 :           0 :             --m_staging_clusterset->m_txcount;
    1049                 :           0 :             m_staging_clusterset->m_txcount_oversized -= oversized_tx;
    1050                 :             :         }
    1051                 :             :     }
    1052         [ +  + ]:       29675 :     if (level == 0) ClearChunkData(entry);
    1053                 :       29675 : }
    1054                 :             : 
    1055                 :        6978 : void GenericClusterImpl::RemoveChunkData(TxGraphImpl& graph) noexcept
    1056                 :             : {
    1057         [ +  + ]:      176781 :     for (DepGraphIndex idx : m_linearization) {
    1058                 :      169803 :         auto& entry = graph.m_entries[m_mapping[idx]];
    1059                 :      169803 :         graph.ClearChunkData(entry);
    1060                 :             :     }
    1061                 :        6978 : }
    1062                 :             : 
    1063                 :       39147 : void SingletonClusterImpl::RemoveChunkData(TxGraphImpl& graph) noexcept
    1064                 :             : {
    1065         [ +  - ]:       39147 :     if (GetTxCount() == 0) return;
    1066                 :       39147 :     auto& entry = graph.m_entries[m_graph_index];
    1067                 :       39147 :     graph.ClearChunkData(entry);
    1068                 :             : }
    1069                 :             : 
    1070                 :       14362 : void GenericClusterImpl::Updated(TxGraphImpl& graph, int level, bool rename) noexcept
    1071                 :             : {
    1072                 :             :     // Update all the Locators for this Cluster's Entry objects.
    1073         [ +  + ]:      195568 :     for (DepGraphIndex idx : m_linearization) {
    1074         [ +  + ]:      181206 :         auto& entry = graph.m_entries[m_mapping[idx]];
    1075                 :             :         // Discard any potential ChunkData prior to modifying the Cluster (as that could
    1076                 :             :         // invalidate its ordering).
    1077         [ +  + ]:      181206 :         if (level == 0 && !rename) graph.ClearChunkData(entry);
    1078                 :      181206 :         entry.m_locator[level].SetPresent(this, idx);
    1079                 :             :     }
    1080                 :             :     // If this is for the main graph (level = 0), and the Cluster's quality is ACCEPTABLE or
    1081                 :             :     // OPTIMAL, compute its chunking and store its information in the Entry's m_main_lin_index
    1082                 :             :     // and m_main_chunk_feerate. These fields are only accessed after making the entire graph
    1083                 :             :     // ACCEPTABLE, so it is pointless to compute these if we haven't reached that quality level
    1084                 :             :     // yet.
    1085                 :             :     // When rename=true, this is always performed for level 0, to make sure the values inside the
    1086                 :             :     // entries remain consistent with the chunk index (otherwise unrelated chunk index operations
    1087                 :             :     // could cause the index to become corrupted, by inserting elements in the wrong place).
    1088   [ +  +  +  +  :       14362 :     if (level == 0 && (rename || IsAcceptable())) {
                   +  + ]
    1089         [ -  + ]:        6676 :         auto chunking = ChunkLinearizationInfo(m_depgraph, m_linearization);
    1090                 :        6676 :         LinearizationIndex lin_idx{0};
    1091                 :             :         /** The sum of all chunk feerate FeeFracs with the same feerate as the current chunk,
    1092                 :             :          *  up to and including the current chunk. */
    1093                 :        6676 :         FeeFrac equal_feerate_chunk_feerate;
    1094                 :             :         // Iterate over the chunks.
    1095   [ -  +  +  + ]:       73577 :         for (unsigned chunk_idx = 0; chunk_idx < chunking.size(); ++chunk_idx) {
    1096         [ +  + ]:       66901 :             auto& chunk = chunking[chunk_idx];
    1097         [ +  + ]:       66901 :             auto chunk_count = chunk.transactions.Count();
    1098         [ +  + ]:       66901 :             Assume(chunk_count > 0);
    1099                 :             :             // Update equal_feerate_chunk_feerate to include this chunk, starting over when the
    1100                 :             :             // feerate changed.
    1101         [ +  + ]:       66901 :             if (ByRatio{chunk.feerate} < ByRatio{equal_feerate_chunk_feerate}) {
    1102                 :        3292 :                 equal_feerate_chunk_feerate = chunk.feerate;
    1103                 :             :             } else {
    1104                 :             :                 // Note that this is adding fees to fees, and sizes to sizes, so the overall
    1105                 :             :                 // ratio remains the same; it's just accounting for the size of the added chunk.
    1106                 :       63609 :                 equal_feerate_chunk_feerate += chunk.feerate;
    1107                 :             :             }
    1108                 :             :             // Determine the m_fallback_order maximum transaction in the chunk.
    1109         [ +  - ]:       66901 :             auto it = chunk.transactions.begin();
    1110                 :       66901 :             GraphIndex max_element = m_mapping[*it];
    1111                 :       66901 :             ++it;
    1112         [ +  + ]:      158161 :             while (it != chunk.transactions.end()) {
    1113                 :       24359 :                 GraphIndex this_element = m_mapping[*it];
    1114         [ +  + ]:       24359 :                 if (graph.m_fallback_order(*graph.m_entries[this_element].m_ref, *graph.m_entries[max_element].m_ref) > 0) {
    1115                 :        2904 :                     max_element = this_element;
    1116                 :             :                 }
    1117                 :       24359 :                 ++it;
    1118                 :             :             }
    1119                 :             :             // Iterate over the transactions in the linearization, which must match those in chunk.
    1120                 :       91260 :             while (true) {
    1121         [ +  + ]:       91260 :                 DepGraphIndex idx = m_linearization[lin_idx];
    1122                 :       91260 :                 GraphIndex graph_idx = m_mapping[idx];
    1123                 :       91260 :                 auto& entry = graph.m_entries[graph_idx];
    1124                 :       91260 :                 entry.m_main_lin_index = lin_idx++;
    1125         [ +  + ]:       91260 :                 entry.m_main_chunk_feerate = FeePerWeight::FromFeeFrac(chunk.feerate);
    1126                 :       91260 :                 entry.m_main_equal_feerate_chunk_prefix_size = equal_feerate_chunk_feerate.size;
    1127                 :       91260 :                 entry.m_main_max_chunk_fallback = max_element;
    1128         [ +  + ]:       91260 :                 Assume(chunk.transactions[idx]);
    1129         [ +  + ]:       91260 :                 chunk.transactions.Reset(idx);
    1130         [ +  + ]:       91260 :                 if (chunk.transactions.None()) {
    1131                 :             :                     // Last transaction in the chunk.
    1132   [ +  +  -  +  :       66901 :                     if (chunk_count == 1 && chunk_idx + 1 == chunking.size()) {
                   +  + ]
    1133                 :             :                         // If this is the final chunk of the cluster, and it contains just a single
    1134                 :             :                         // transaction (which will always be true for the very common singleton
    1135                 :             :                         // clusters), store the special value -1 as chunk count.
    1136                 :             :                         chunk_count = LinearizationIndex(-1);
    1137                 :             :                     }
    1138         [ +  + ]:       66901 :                     if (!rename) graph.CreateChunkData(graph_idx, chunk_count);
    1139                 :       66901 :                     break;
    1140                 :             :                 }
    1141                 :             :             }
    1142                 :             :         }
    1143                 :        6676 :     }
    1144                 :       14362 : }
    1145                 :             : 
    1146                 :      195823 : void SingletonClusterImpl::Updated(TxGraphImpl& graph, int level, bool rename) noexcept
    1147                 :             : {
    1148                 :             :     // Don't do anything if this is empty.
    1149         [ +  - ]:      195823 :     if (GetTxCount() == 0) return;
    1150                 :             : 
    1151         [ +  + ]:      195823 :     auto& entry = graph.m_entries[m_graph_index];
    1152                 :             :     // Discard any potential ChunkData prior to modifying the Cluster (as that could
    1153                 :             :     // invalidate its ordering).
    1154         [ +  + ]:      195823 :     if (level == 0 && !rename) graph.ClearChunkData(entry);
    1155                 :      195823 :     entry.m_locator[level].SetPresent(this, 0);
    1156                 :             :     // If this is for the main graph (level = 0), compute its chunking and store its information in
    1157                 :             :     // the Entry's m_main_lin_index and m_main_chunk_feerate.
    1158   [ +  +  +  +  :      195823 :     if (level == 0 && (rename || IsAcceptable())) {
                   +  + ]
    1159                 :      122329 :         entry.m_main_lin_index = 0;
    1160                 :      122329 :         entry.m_main_chunk_feerate = m_feerate;
    1161                 :      122329 :         entry.m_main_equal_feerate_chunk_prefix_size = m_feerate.size;
    1162                 :      122329 :         entry.m_main_max_chunk_fallback = m_graph_index;
    1163                 :             :         // Always use the special LinearizationIndex(-1), indicating singleton chunk at end of
    1164                 :             :         // Cluster, here.
    1165         [ +  + ]:      122329 :         if (!rename) graph.CreateChunkData(m_graph_index, LinearizationIndex(-1));
    1166                 :             :     }
    1167                 :             : }
    1168                 :             : 
    1169                 :         135 : void GenericClusterImpl::GetConflicts(const TxGraphImpl& graph, std::vector<Cluster*>& out) const noexcept
    1170                 :             : {
    1171         [ +  + ]:        1383 :     for (auto i : m_linearization) {
    1172         [ +  + ]:        1248 :         auto& entry = graph.m_entries[m_mapping[i]];
    1173                 :             :         // For every transaction Entry in this Cluster, if it also exists in a lower-level Cluster,
    1174                 :             :         // then that Cluster conflicts.
    1175         [ +  + ]:        1248 :         if (entry.m_locator[0].IsPresent()) {
    1176                 :        1088 :             out.push_back(entry.m_locator[0].cluster);
    1177                 :             :         }
    1178                 :             :     }
    1179                 :         135 : }
    1180                 :             : 
    1181                 :       48736 : void SingletonClusterImpl::GetConflicts(const TxGraphImpl& graph, std::vector<Cluster*>& out) const noexcept
    1182                 :             : {
    1183                 :             :     // Empty clusters have no conflicts.
    1184         [ +  - ]:       48736 :     if (GetTxCount() == 0) return;
    1185                 :             : 
    1186         [ +  + ]:       48736 :     auto& entry = graph.m_entries[m_graph_index];
    1187                 :             :     // If the transaction in this Cluster also exists in a lower-level Cluster, then that Cluster
    1188                 :             :     // conflicts.
    1189         [ +  + ]:       48736 :     if (entry.m_locator[0].IsPresent()) {
    1190                 :         130 :         out.push_back(entry.m_locator[0].cluster);
    1191                 :             :     }
    1192                 :             : }
    1193                 :             : 
    1194                 :       48682 : std::vector<Cluster*> TxGraphImpl::GetConflicts() const noexcept
    1195                 :             : {
    1196                 :       48682 :     Assume(GetTopLevel() == 1);
    1197                 :       48682 :     auto& clusterset = GetClusterSet(1);
    1198                 :       48682 :     std::vector<Cluster*> ret;
    1199                 :             :     // All main Clusters containing transactions in m_removed (so (P,R) ones) are conflicts.
    1200         [ +  + ]:       52428 :     for (auto i : clusterset.m_removed) {
    1201         [ +  - ]:        3746 :         auto& entry = m_entries[i];
    1202         [ +  - ]:        3746 :         if (entry.m_locator[0].IsPresent()) {
    1203                 :        3746 :             ret.push_back(entry.m_locator[0].cluster);
    1204                 :             :         }
    1205                 :             :     }
    1206                 :             :     // Then go over all Clusters at this level, and find their conflicts (the (P,P) ones).
    1207         [ +  + ]:      389456 :     for (int quality = 0; quality < int(QualityLevel::NONE); ++quality) {
    1208                 :      340774 :         auto& clusters = clusterset.m_clusters[quality];
    1209         [ +  + ]:      389645 :         for (const auto& cluster : clusters) {
    1210                 :       48871 :             cluster->GetConflicts(*this, ret);
    1211                 :             :         }
    1212                 :             :     }
    1213                 :             :     // Deduplicate the result (the same Cluster may appear multiple times).
    1214                 :       48682 :     std::ranges::sort(ret, [](Cluster* a, Cluster* b) noexcept { return CompareClusters(a, b) < 0; });
    1215                 :       48682 :     ret.erase(std::ranges::unique(ret).begin(), ret.end());
    1216                 :       48682 :     return ret;
    1217                 :             : }
    1218                 :             : 
    1219                 :         332 : Cluster* GenericClusterImpl::CopyToStaging(TxGraphImpl& graph) const noexcept
    1220                 :             : {
    1221                 :             :     // Construct an empty Cluster.
    1222                 :         332 :     auto ret = graph.CreateEmptyGenericCluster();
    1223                 :         332 :     auto ptr = ret.get();
    1224                 :             :     // Copy depgraph, mapping, and linearization.
    1225                 :         332 :     ptr->m_depgraph = m_depgraph;
    1226                 :         332 :     ptr->m_mapping = m_mapping;
    1227                 :         332 :     ptr->m_linearization = m_linearization;
    1228                 :             :     // Insert the new Cluster into the graph.
    1229                 :         332 :     graph.InsertCluster(/*level=*/1, std::move(ret), m_quality);
    1230                 :             :     // Update its Locators.
    1231                 :         332 :     ptr->Updated(graph, /*level=*/1, /*rename=*/false);
    1232                 :             :     // Update memory usage.
    1233                 :         332 :     graph.GetClusterSet(/*level=*/1).m_cluster_usage += ptr->TotalMemoryUsage();
    1234         [ -  + ]:         332 :     return ptr;
    1235                 :         332 : }
    1236                 :             : 
    1237                 :        1415 : Cluster* SingletonClusterImpl::CopyToStaging(TxGraphImpl& graph) const noexcept
    1238                 :             : {
    1239                 :             :     // Construct an empty Cluster.
    1240                 :        1415 :     auto ret = graph.CreateEmptySingletonCluster();
    1241                 :        1415 :     auto ptr = ret.get();
    1242                 :             :     // Copy data.
    1243                 :        1415 :     ptr->m_graph_index = m_graph_index;
    1244                 :        1415 :     ptr->m_feerate = m_feerate;
    1245                 :             :     // Insert the new Cluster into the graph.
    1246                 :        1415 :     graph.InsertCluster(/*level=*/1, std::move(ret), m_quality);
    1247                 :             :     // Update its Locators.
    1248                 :        1415 :     ptr->Updated(graph, /*level=*/1, /*rename=*/false);
    1249                 :             :     // Update memory usage.
    1250                 :        1415 :     graph.GetClusterSet(/*level=*/1).m_cluster_usage += ptr->TotalMemoryUsage();
    1251                 :        2830 :     return ptr;
    1252                 :        1415 : }
    1253                 :             : 
    1254                 :        1255 : void GenericClusterImpl::ApplyRemovals(TxGraphImpl& graph, int level, std::span<GraphIndex>& to_remove) noexcept
    1255                 :             : {
    1256                 :             :     // Iterate over the prefix of to_remove that applies to this cluster.
    1257                 :        1255 :     Assume(!to_remove.empty());
    1258                 :        1255 :     SetType todo;
    1259                 :        1255 :     graph.GetClusterSet(level).m_cluster_usage -= TotalMemoryUsage();
    1260                 :        6147 :     do {
    1261         [ -  + ]:        6147 :         GraphIndex idx = to_remove.front();
    1262   [ -  +  +  + ]:        6147 :         Assume(idx < graph.m_entries.size());
    1263         [ +  + ]:        6147 :         auto& entry = graph.m_entries[idx];
    1264                 :             :         auto& locator = entry.m_locator[level];
    1265                 :             :         // Stop once we hit an entry that applies to another Cluster.
    1266         [ +  + ]:        6147 :         if (locator.cluster != this) break;
    1267                 :             :         // - Remember it in a set of to-remove DepGraphIndexes.
    1268         [ +  + ]:        5377 :         todo.Set(locator.index);
    1269                 :             :         // - Remove from m_mapping. This isn't strictly necessary as unused positions in m_mapping
    1270                 :             :         //   are just never accessed, but set it to -1 here to increase the ability to detect a bug
    1271                 :             :         //   that causes it to be accessed regardless.
    1272         [ +  + ]:        5377 :         m_mapping[locator.index] = GraphIndex(-1);
    1273                 :             :         // - Remove its linearization index from the Entry (if in main).
    1274         [ +  + ]:        5377 :         if (level == 0) {
    1275                 :        4612 :             entry.m_main_lin_index = LinearizationIndex(-1);
    1276                 :             :         }
    1277                 :             :         // - Mark it as missing/removed in the Entry's locator.
    1278                 :        5377 :         graph.ClearLocator(level, idx, m_quality == QualityLevel::OVERSIZED_SINGLETON);
    1279         [ +  + ]:        5377 :         to_remove = to_remove.subspan(1);
    1280         [ +  + ]:        5377 :     } while(!to_remove.empty());
    1281                 :             : 
    1282                 :        1255 :     Assume(todo.Any());
    1283                 :             :     // Wipe from the Cluster's DepGraph (this is O(n) regardless of the number of entries
    1284                 :             :     // removed, so we benefit from batching all the removals).
    1285                 :        1255 :     m_depgraph.RemoveTransactions(todo);
    1286         [ -  + ]:        1255 :     m_mapping.resize(m_depgraph.PositionRange());
    1287                 :             : 
    1288                 :             :     // Filter removed transactions out of m_linearization.
    1289                 :        1255 :     std::erase_if(m_linearization, [&](auto pos) { return todo[pos]; });
    1290                 :             : 
    1291                 :        1255 :     Compact();
    1292                 :        1255 :     graph.GetClusterSet(level).m_cluster_usage += TotalMemoryUsage();
    1293         [ +  + ]:        1255 :     auto new_quality = IsTopological() ? QualityLevel::NEEDS_SPLIT : QualityLevel::NEEDS_SPLIT_FIX;
    1294                 :        1255 :     graph.SetClusterQuality(level, m_quality, m_setindex, new_quality);
    1295                 :        1255 :     Updated(graph, /*level=*/level, /*rename=*/false);
    1296                 :        1255 : }
    1297                 :             : 
    1298                 :       22174 : void SingletonClusterImpl::ApplyRemovals(TxGraphImpl& graph, int level, std::span<GraphIndex>& to_remove) noexcept
    1299                 :             : {
    1300                 :             :     // We can only remove the one transaction this Cluster has.
    1301                 :       22174 :     Assume(!to_remove.empty());
    1302                 :       22174 :     Assume(GetTxCount());
    1303                 :       22174 :     Assume(to_remove.front() == m_graph_index);
    1304                 :             :     // Pop all copies of m_graph_index from the front of to_remove (at least one, but there may be
    1305                 :             :     // multiple).
    1306                 :       22174 :     do {
    1307         [ +  + ]:       22174 :         to_remove = to_remove.subspan(1);
    1308   [ +  +  +  -  :       41129 :     } while (!to_remove.empty() && to_remove.front() == m_graph_index);
                   -  + ]
    1309                 :             :     // Clear this cluster.
    1310                 :       22174 :     graph.ClearLocator(level, m_graph_index, m_quality == QualityLevel::OVERSIZED_SINGLETON);
    1311                 :       22174 :     m_graph_index = NO_GRAPH_INDEX;
    1312                 :       22174 :     graph.SetClusterQuality(level, m_quality, m_setindex, QualityLevel::NEEDS_SPLIT);
    1313                 :             :     // No need to account for m_cluster_usage changes here, as SingletonClusterImpl has constant
    1314                 :             :     // memory usage.
    1315                 :       22174 : }
    1316                 :             : 
    1317                 :         230 : void GenericClusterImpl::Clear(TxGraphImpl& graph, int level) noexcept
    1318                 :             : {
    1319         [ -  + ]:         230 :     Assume(GetTxCount());
    1320                 :         230 :     graph.GetClusterSet(level).m_cluster_usage -= TotalMemoryUsage();
    1321         [ +  + ]:        1325 :     for (auto i : m_linearization) {
    1322                 :        1095 :         graph.ClearLocator(level, m_mapping[i], m_quality == QualityLevel::OVERSIZED_SINGLETON);
    1323                 :             :     }
    1324                 :         230 :     m_depgraph = {};
    1325         [ +  - ]:         230 :     m_linearization.clear();
    1326         [ +  - ]:         230 :     m_mapping.clear();
    1327                 :         230 : }
    1328                 :             : 
    1329                 :        1029 : void SingletonClusterImpl::Clear(TxGraphImpl& graph, int level) noexcept
    1330                 :             : {
    1331                 :        1029 :     Assume(GetTxCount());
    1332                 :        1029 :     graph.GetClusterSet(level).m_cluster_usage -= TotalMemoryUsage();
    1333                 :        1029 :     graph.ClearLocator(level, m_graph_index, m_quality == QualityLevel::OVERSIZED_SINGLETON);
    1334                 :        1029 :     m_graph_index = NO_GRAPH_INDEX;
    1335                 :        1029 : }
    1336                 :             : 
    1337                 :          56 : void GenericClusterImpl::MoveToMain(TxGraphImpl& graph) noexcept
    1338                 :             : {
    1339         [ +  + ]:         614 :     for (auto i : m_linearization) {
    1340                 :         558 :         GraphIndex idx = m_mapping[i];
    1341                 :         558 :         auto& entry = graph.m_entries[idx];
    1342                 :         558 :         entry.m_locator[1].SetMissing();
    1343                 :             :     }
    1344                 :          56 :     auto quality = m_quality;
    1345                 :             :     // Subtract memory usage from staging and add it to main.
    1346                 :          56 :     graph.GetClusterSet(/*level=*/1).m_cluster_usage -= TotalMemoryUsage();
    1347                 :          56 :     graph.GetClusterSet(/*level=*/0).m_cluster_usage += TotalMemoryUsage();
    1348                 :             :     // Remove cluster itself from staging and add it to main.
    1349                 :          56 :     auto cluster = graph.ExtractCluster(1, quality, m_setindex);
    1350                 :          56 :     graph.InsertCluster(/*level=*/0, std::move(cluster), quality);
    1351                 :          56 :     Updated(graph, /*level=*/0, /*rename=*/false);
    1352                 :          56 : }
    1353                 :             : 
    1354                 :       47397 : void SingletonClusterImpl::MoveToMain(TxGraphImpl& graph) noexcept
    1355                 :             : {
    1356         [ +  - ]:       47397 :     if (GetTxCount()) {
    1357                 :       47397 :         auto& entry = graph.m_entries[m_graph_index];
    1358                 :       47397 :         entry.m_locator[1].SetMissing();
    1359                 :             :     }
    1360                 :       47397 :     auto quality = m_quality;
    1361                 :       47397 :     graph.GetClusterSet(/*level=*/1).m_cluster_usage -= TotalMemoryUsage();
    1362                 :       47397 :     auto cluster = graph.ExtractCluster(/*level=*/1, quality, m_setindex);
    1363                 :       47397 :     graph.InsertCluster(/*level=*/0, std::move(cluster), quality);
    1364                 :       47397 :     graph.GetClusterSet(/*level=*/0).m_cluster_usage += TotalMemoryUsage();
    1365                 :       47397 :     Updated(graph, /*level=*/0, /*rename=*/false);
    1366                 :       47397 : }
    1367                 :             : 
    1368                 :        7215 : void GenericClusterImpl::Compact() noexcept
    1369                 :             : {
    1370                 :        7215 :     m_linearization.shrink_to_fit();
    1371                 :        7215 :     m_mapping.shrink_to_fit();
    1372                 :        7215 :     m_depgraph.Compact();
    1373                 :        7215 : }
    1374                 :             : 
    1375                 :         383 : void SingletonClusterImpl::Compact() noexcept
    1376                 :             : {
    1377                 :             :     // Nothing to compact; SingletonClusterImpl is constant size.
    1378                 :         383 : }
    1379                 :             : 
    1380                 :         410 : void GenericClusterImpl::AppendChunkFeerates(std::vector<FeeFrac>& ret) const noexcept
    1381                 :             : {
    1382         [ -  + ]:         410 :     auto chunk_feerates = ChunkLinearization(m_depgraph, m_linearization);
    1383   [ -  +  -  + ]:         410 :     ret.reserve(ret.size() + chunk_feerates.size());
    1384                 :         410 :     ret.insert(ret.end(), chunk_feerates.begin(), chunk_feerates.end());
    1385                 :         410 : }
    1386                 :             : 
    1387                 :        2744 : void SingletonClusterImpl::AppendChunkFeerates(std::vector<FeeFrac>& ret) const noexcept
    1388                 :             : {
    1389         [ +  - ]:        2744 :     if (GetTxCount()) {
    1390                 :        2744 :         ret.push_back(m_feerate);
    1391                 :             :     }
    1392                 :        2744 : }
    1393                 :             : 
    1394                 :           0 : uint64_t GenericClusterImpl::AppendTrimData(std::vector<TrimTxData>& ret, std::vector<std::pair<GraphIndex, GraphIndex>>& deps) const noexcept
    1395                 :             : {
    1396         [ #  # ]:           0 :     Assume(IsAcceptable());
    1397         [ #  # ]:           0 :     auto linchunking = ChunkLinearizationInfo(m_depgraph, m_linearization);
    1398                 :           0 :     LinearizationIndex pos{0};
    1399                 :           0 :     uint64_t size{0};
    1400                 :           0 :     auto prev_index = GraphIndex(-1);
    1401                 :             :     // Iterate over the chunks of this cluster's linearization.
    1402         [ #  # ]:           0 :     for (const auto& [chunk, chunk_feerate] : linchunking) {
    1403                 :             :         // Iterate over the transactions of that chunk, in linearization order.
    1404                 :           0 :         auto chunk_tx_count = chunk.Count();
    1405         [ #  # ]:           0 :         for (unsigned j = 0; j < chunk_tx_count; ++j) {
    1406                 :           0 :             auto cluster_idx = m_linearization[pos];
    1407                 :             :             // The transaction must appear in the chunk.
    1408                 :           0 :             Assume(chunk[cluster_idx]);
    1409                 :             :             // Construct a new element in ret.
    1410                 :           0 :             auto& entry = ret.emplace_back();
    1411         [ #  # ]:           0 :             entry.m_chunk_feerate = FeePerWeight::FromFeeFrac(chunk_feerate);
    1412         [ #  # ]:           0 :             entry.m_index = m_mapping[cluster_idx];
    1413                 :             :             // If this is not the first transaction of the cluster linearization, it has an
    1414                 :             :             // implicit dependency on its predecessor.
    1415         [ #  # ]:           0 :             if (pos != 0) deps.emplace_back(prev_index, entry.m_index);
    1416                 :           0 :             prev_index = entry.m_index;
    1417                 :           0 :             entry.m_tx_size = m_depgraph.FeeRate(cluster_idx).size;
    1418                 :           0 :             size += entry.m_tx_size;
    1419                 :           0 :             ++pos;
    1420                 :             :         }
    1421                 :             :     }
    1422                 :           0 :     return size;
    1423                 :           0 : }
    1424                 :             : 
    1425                 :       64217 : uint64_t SingletonClusterImpl::AppendTrimData(std::vector<TrimTxData>& ret, std::vector<std::pair<GraphIndex, GraphIndex>>& deps) const noexcept
    1426                 :             : {
    1427         [ +  - ]:       64217 :     if (!GetTxCount()) return 0;
    1428                 :       64217 :     auto& entry = ret.emplace_back();
    1429                 :       64217 :     entry.m_chunk_feerate = m_feerate;
    1430                 :       64217 :     entry.m_index = m_graph_index;
    1431                 :       64217 :     entry.m_tx_size = m_feerate.size;
    1432                 :       64217 :     return m_feerate.size;
    1433                 :             : }
    1434                 :             : 
    1435                 :        1253 : bool GenericClusterImpl::Split(TxGraphImpl& graph, int level) noexcept
    1436                 :             : {
    1437                 :             :     // This function can only be called when the Cluster needs splitting.
    1438         [ +  + ]:        1253 :     Assume(NeedsSplitting());
    1439                 :             :     // Determine the new quality the split-off Clusters will have.
    1440         [ +  + ]:        1253 :     QualityLevel new_quality = IsTopological() ? QualityLevel::NEEDS_RELINEARIZE : QualityLevel::NEEDS_FIX;
    1441                 :             :     /** Which positions are still left in this Cluster. */
    1442                 :        1253 :     auto todo = m_depgraph.Positions();
    1443                 :             :     /** Mapping from transaction positions in this Cluster to the Cluster where it ends up, and
    1444                 :             :      *  its position therein. */
    1445         [ -  + ]:        1253 :     std::vector<std::pair<Cluster*, DepGraphIndex>> remap(m_depgraph.PositionRange());
    1446                 :        1253 :     std::vector<Cluster*> new_clusters;
    1447                 :        1253 :     bool first{true};
    1448                 :             :     // Iterate over the connected components of this Cluster's m_depgraph.
    1449         [ +  + ]:        1643 :     while (todo.Any()) {
    1450                 :         412 :         auto component = m_depgraph.FindConnectedComponent(todo);
    1451         [ +  + ]:         412 :         auto component_size = component.Count();
    1452         [ +  + ]:         412 :         auto split_quality = component_size <= 1 ? QualityLevel::OPTIMAL : new_quality;
    1453   [ +  +  +  +  :         626 :         if (first && component == todo && SetType::Fill(component_size) == component && component_size >= MIN_INTENDED_TX_COUNT) {
                   +  + ]
    1454                 :             :             // The existing Cluster is an entire component, without holes. Leave it be, but update
    1455                 :             :             // its quality. If there are holes, we continue, so that the Cluster is reconstructed
    1456                 :             :             // without holes, reducing memory usage. If the component's size is below the intended
    1457                 :             :             // transaction count for this Cluster implementation, continue so that it can get
    1458                 :             :             // converted.
    1459                 :          22 :             Assume(todo == m_depgraph.Positions());
    1460                 :          22 :             graph.SetClusterQuality(level, m_quality, m_setindex, split_quality);
    1461                 :             :             // If this made the quality ACCEPTABLE or OPTIMAL, we need to compute and cache its
    1462                 :             :             // chunking.
    1463                 :          22 :             Updated(graph, /*level=*/level, /*rename=*/false);
    1464                 :          22 :             return false;
    1465                 :             :         }
    1466                 :         390 :         first = false;
    1467                 :             :         // Construct a new Cluster to hold the found component.
    1468                 :         390 :         auto new_cluster = graph.CreateEmptyCluster(component_size);
    1469                 :         390 :         new_clusters.push_back(new_cluster.get());
    1470                 :             :         // Remember that all the component's transactions go to this new Cluster. The positions
    1471                 :             :         // will be determined below, so use -1 for now.
    1472   [ +  -  +  + ]:        1180 :         for (auto i : component) {
    1473                 :         400 :             remap[i] = {new_cluster.get(), DepGraphIndex(-1)};
    1474                 :             :         }
    1475                 :         390 :         graph.InsertCluster(level, std::move(new_cluster), split_quality);
    1476                 :         390 :         todo -= component;
    1477                 :         390 :     }
    1478                 :             :     // We have to split the Cluster up. Remove accounting for the existing one first.
    1479                 :        1231 :     graph.GetClusterSet(level).m_cluster_usage -= TotalMemoryUsage();
    1480                 :             :     // Redistribute the transactions.
    1481         [ +  + ]:        1631 :     for (auto i : m_linearization) {
    1482                 :             :         /** The cluster which transaction originally in position i is moved to. */
    1483                 :         400 :         Cluster* new_cluster = remap[i].first;
    1484                 :             :         // Copy the transaction to the new cluster's depgraph, and remember the position.
    1485                 :         400 :         remap[i].second = new_cluster->AppendTransaction(m_mapping[i], FeePerWeight::FromFeeFrac(m_depgraph.FeeRate(i)));
    1486                 :             :     }
    1487                 :             :     // Redistribute the dependencies.
    1488         [ +  + ]:        1631 :     for (auto i : m_linearization) {
    1489                 :             :         /** The cluster transaction in position i is moved to. */
    1490                 :         400 :         Cluster* new_cluster = remap[i].first;
    1491                 :             :         // Copy its parents, translating positions.
    1492                 :         400 :         SetType new_parents;
    1493   [ +  +  +  + ]:         420 :         for (auto par : m_depgraph.GetReducedParents(i)) new_parents.Set(remap[par].second);
    1494                 :         400 :         new_cluster->AddDependencies(new_parents, remap[i].second);
    1495                 :             :     }
    1496                 :             :     // Update all the Locators of moved transactions, and memory usage.
    1497         [ +  + ]:        1621 :     for (Cluster* new_cluster : new_clusters) {
    1498                 :         390 :         new_cluster->Updated(graph, /*level=*/level, /*rename=*/false);
    1499                 :         390 :         new_cluster->Compact();
    1500                 :         390 :         graph.GetClusterSet(level).m_cluster_usage += new_cluster->TotalMemoryUsage();
    1501                 :             :     }
    1502                 :             :     // Wipe this Cluster, and return that it needs to be deleted.
    1503                 :        1231 :     m_depgraph = DepGraph<SetType>{};
    1504         [ +  + ]:        1231 :     m_mapping.clear();
    1505         [ +  + ]:        1453 :     m_linearization.clear();
    1506                 :             :     return true;
    1507                 :        1253 : }
    1508                 :             : 
    1509                 :       22155 : bool SingletonClusterImpl::Split(TxGraphImpl& graph, int level) noexcept
    1510                 :             : {
    1511                 :       22155 :     Assume(NeedsSplitting());
    1512                 :       22155 :     Assume(!GetTxCount());
    1513                 :       22155 :     graph.GetClusterSet(level).m_cluster_usage -= TotalMemoryUsage();
    1514                 :       22155 :     return true;
    1515                 :             : }
    1516                 :             : 
    1517                 :        7931 : void GenericClusterImpl::Merge(TxGraphImpl& graph, int level, Cluster& other) noexcept
    1518                 :             : {
    1519                 :             :     /** Vector to store the positions in this Cluster for each position in other. */
    1520                 :        7931 :     std::vector<DepGraphIndex> remap(other.GetDepGraphIndexRange());
    1521                 :             :     // Iterate over all transactions in the other Cluster (the one being absorbed).
    1522                 :        7931 :     other.ExtractTransactions([&](DepGraphIndex pos, GraphIndex idx, FeePerWeight feerate) noexcept {
    1523                 :             :         // Copy the transaction into this Cluster, and remember its position.
    1524                 :        7956 :         auto new_pos = m_depgraph.AddTransaction(feerate);
    1525                 :             :         // Since this cluster must have been made hole-free before being merged into, all added
    1526                 :             :         // transactions should appear at the end.
    1527         [ -  + ]:        7956 :         Assume(new_pos == m_mapping.size());
    1528                 :        7956 :         remap[pos] = new_pos;
    1529                 :        7956 :         m_mapping.push_back(idx);
    1530                 :        7956 :         m_linearization.push_back(new_pos);
    1531                 :       15862 :     }, [&](DepGraphIndex pos, GraphIndex idx, SetType other_parents) noexcept {
    1532                 :             :         // Copy the transaction's dependencies, translating them using remap.
    1533                 :        7956 :         SetType parents;
    1534   [ +  +  +  + ]:        8006 :         for (auto par : other_parents) {
    1535                 :          25 :             parents.Set(remap[par]);
    1536                 :             :         }
    1537                 :        7956 :         m_depgraph.AddDependencies(parents, remap[pos]);
    1538                 :             :         // Update the transaction's Locator. There is no need to call Updated() to update chunk
    1539                 :             :         // feerates, as Updated() will be invoked by Cluster::ApplyDependencies on the resulting
    1540                 :             :         // merged Cluster later anyway.
    1541         [ +  + ]:        7956 :         auto& entry = graph.m_entries[idx];
    1542                 :             :         // Discard any potential ChunkData prior to modifying the Cluster (as that could
    1543                 :             :         // invalidate its ordering).
    1544         [ +  + ]:        7956 :         if (level == 0) graph.ClearChunkData(entry);
    1545                 :        7956 :         entry.m_locator[level].SetPresent(this, remap[pos]);
    1546                 :        7956 :     });
    1547                 :        7931 : }
    1548                 :             : 
    1549                 :           0 : void SingletonClusterImpl::Merge(TxGraphImpl&, int, Cluster&) noexcept
    1550                 :             : {
    1551                 :             :     // Nothing can be merged into a singleton; it should have been converted to GenericClusterImpl first.
    1552                 :           0 :     Assume(false);
    1553                 :           0 : }
    1554                 :             : 
    1555                 :        5974 : void GenericClusterImpl::ApplyDependencies(TxGraphImpl& graph, int level, std::span<std::pair<GraphIndex, GraphIndex>> to_apply) noexcept
    1556                 :             : {
    1557                 :             :     // Sort the list of dependencies to apply by child, so those can be applied in batch.
    1558   [ -  -  -  -  :       34774 :     std::ranges::sort(to_apply, [](auto& a, auto& b) { return a.second < b.second; });
          +  +  +  +  +  
          +  +  +  +  +  
          +  +  +  +  +  
             +  -  -  +  
                      + ]
    1559                 :             :     // Iterate over groups of to-be-added dependencies with the same child.
    1560                 :        5974 :     auto it = to_apply.begin();
    1561         [ +  + ]:       12310 :     while (it != to_apply.end()) {
    1562                 :        6336 :         auto& first_child = graph.m_entries[it->second].m_locator[level];
    1563                 :        6336 :         const auto child_idx = first_child.index;
    1564                 :             :         // Iterate over all to-be-added dependencies within that same child, gather the relevant
    1565                 :             :         // parents.
    1566                 :        6336 :         SetType parents;
    1567         [ +  + ]:       17060 :         while (it != to_apply.end()) {
    1568         [ +  + ]:       11086 :             auto& child = graph.m_entries[it->second].m_locator[level];
    1569                 :       11086 :             auto& parent = graph.m_entries[it->first].m_locator[level];
    1570         [ +  + ]:       11086 :             Assume(child.cluster == this && parent.cluster == this);
    1571         [ +  + ]:       11086 :             if (child.index != child_idx) break;
    1572                 :       10724 :             parents.Set(parent.index);
    1573                 :       10724 :             ++it;
    1574                 :             :         }
    1575                 :             :         // Push all dependencies to the underlying DepGraph. Note that this is O(N) in the size of
    1576                 :             :         // the cluster, regardless of the number of parents being added, so batching them together
    1577                 :             :         // has a performance benefit.
    1578                 :        6336 :         m_depgraph.AddDependencies(parents, child_idx);
    1579                 :             :     }
    1580                 :             : 
    1581                 :             :     // Finally set the cluster to NEEDS_FIX, so its linearization is fixed the next time it is
    1582                 :             :     // attempted to be made ACCEPTABLE.
    1583                 :        5974 :     Assume(!NeedsSplitting());
    1584                 :        5974 :     Assume(!IsOversized());
    1585                 :        5974 :     graph.SetClusterQuality(level, m_quality, m_setindex, QualityLevel::NEEDS_FIX);
    1586                 :             : 
    1587                 :             :     // Finally push the changes to graph.m_entries.
    1588                 :        5974 :     Updated(graph, /*level=*/level, /*rename=*/false);
    1589                 :        5974 : }
    1590                 :             : 
    1591                 :           0 : void SingletonClusterImpl::ApplyDependencies(TxGraphImpl&, int, std::span<std::pair<GraphIndex, GraphIndex>>) noexcept
    1592                 :             : {
    1593                 :             :     // Nothing can actually be applied.
    1594                 :           0 :     Assume(false);
    1595                 :           0 : }
    1596                 :             : 
    1597                 :        2826 : TxGraphImpl::~TxGraphImpl() noexcept
    1598                 :             : {
    1599                 :             :     // If Refs outlive the TxGraphImpl they refer to, unlink them, so that their destructor does not
    1600                 :             :     // try to reach into a non-existing TxGraphImpl anymore.
    1601         [ +  + ]:       86208 :     for (auto& entry : m_entries) {
    1602         [ +  + ]:       84795 :         if (entry.m_ref != nullptr) {
    1603                 :       64011 :             GetRefGraph(*entry.m_ref) = nullptr;
    1604                 :             :         }
    1605                 :             :     }
    1606                 :        4239 : }
    1607                 :             : 
    1608                 :      115453 : std::unique_ptr<Cluster> TxGraphImpl::ExtractCluster(int level, QualityLevel quality, ClusterSetIndex setindex) noexcept
    1609                 :             : {
    1610         [ -  + ]:      115453 :     Assume(quality != QualityLevel::NONE);
    1611                 :             : 
    1612                 :      115453 :     auto& clusterset = GetClusterSet(level);
    1613         [ -  + ]:      115453 :     auto& quality_clusters = clusterset.m_clusters[int(quality)];
    1614   [ -  +  -  + ]:      115453 :     Assume(setindex < quality_clusters.size());
    1615                 :             : 
    1616                 :             :     // Extract the Cluster-owning unique_ptr.
    1617         [ -  + ]:      115453 :     std::unique_ptr<Cluster> ret = std::move(quality_clusters[setindex]);
    1618         [ -  + ]:      115453 :     ret->m_quality = QualityLevel::NONE;
    1619                 :      115453 :     ret->m_setindex = ClusterSetIndex(-1);
    1620                 :             : 
    1621                 :             :     // Clean up space in quality_cluster.
    1622         [ -  + ]:      115453 :     auto max_setindex = quality_clusters.size() - 1;
    1623         [ +  + ]:      115453 :     if (setindex != max_setindex) {
    1624                 :             :         // If the cluster was not the last element of quality_clusters, move that to take its place.
    1625                 :       21602 :         quality_clusters.back()->m_setindex = setindex;
    1626                 :       21602 :         quality_clusters[setindex] = std::move(quality_clusters.back());
    1627                 :             :     }
    1628                 :             :     // The last element of quality_clusters is now unused; drop it.
    1629                 :      115453 :     quality_clusters.pop_back();
    1630                 :             : 
    1631                 :      115453 :     return ret;
    1632                 :             : }
    1633                 :             : 
    1634                 :      222519 : ClusterSetIndex TxGraphImpl::InsertCluster(int level, std::unique_ptr<Cluster>&& cluster, QualityLevel quality) noexcept
    1635                 :             : {
    1636                 :             :     // Cannot insert with quality level NONE (as that would mean not inserted).
    1637         [ -  + ]:      222519 :     Assume(quality != QualityLevel::NONE);
    1638                 :             :     // The passed-in Cluster must not currently be in the TxGraphImpl.
    1639         [ -  + ]:      222519 :     Assume(cluster->m_quality == QualityLevel::NONE);
    1640                 :             : 
    1641                 :             :     // Append it at the end of the relevant TxGraphImpl::m_cluster.
    1642                 :      222519 :     auto& clusterset = GetClusterSet(level);
    1643         [ -  + ]:      222519 :     auto& quality_clusters = clusterset.m_clusters[int(quality)];
    1644         [ -  + ]:      222519 :     ClusterSetIndex ret = quality_clusters.size();
    1645                 :      222519 :     cluster->m_quality = quality;
    1646                 :      222519 :     cluster->m_setindex = ret;
    1647                 :      222519 :     quality_clusters.push_back(std::move(cluster));
    1648                 :      222519 :     return ret;
    1649                 :             : }
    1650                 :             : 
    1651                 :       35425 : void TxGraphImpl::SetClusterQuality(int level, QualityLevel old_quality, ClusterSetIndex old_index, QualityLevel new_quality) noexcept
    1652                 :             : {
    1653         [ +  + ]:       35425 :     Assume(new_quality != QualityLevel::NONE);
    1654                 :             : 
    1655                 :             :     // Don't do anything if the quality did not change.
    1656         [ +  + ]:       35425 :     if (old_quality == new_quality) return;
    1657                 :             :     // Extract the cluster from where it currently resides.
    1658                 :       35424 :     auto cluster_ptr = ExtractCluster(level, old_quality, old_index);
    1659                 :             :     // And re-insert it where it belongs.
    1660                 :       35424 :     InsertCluster(level, std::move(cluster_ptr), new_quality);
    1661                 :       35424 : }
    1662                 :             : 
    1663                 :       32576 : void TxGraphImpl::DeleteCluster(Cluster& cluster, int level) noexcept
    1664                 :             : {
    1665                 :             :     // Extract the cluster from where it currently resides.
    1666                 :       32576 :     auto cluster_ptr = ExtractCluster(level, cluster.m_quality, cluster.m_setindex);
    1667                 :             :     // And throw it away.
    1668         [ +  - ]:       32576 :     cluster_ptr.reset();
    1669                 :       32576 : }
    1670                 :             : 
    1671                 :     1375132 : std::pair<Cluster*, int> TxGraphImpl::FindClusterAndLevel(GraphIndex idx, int level) const noexcept
    1672                 :             : {
    1673         [ +  - ]:     1375132 :     Assume(level >= 0 && level <= GetTopLevel());
    1674                 :     1375132 :     auto& entry = m_entries[idx];
    1675                 :             :     // Search the entry's locators from top to bottom.
    1676         [ +  + ]:     1411161 :     for (int l = level; l >= 0; --l) {
    1677                 :             :         // If the locator is missing, dig deeper; it may exist at a lower level and therefore be
    1678                 :             :         // implicitly existing at this level too.
    1679         [ +  + ]:     1445870 :         if (entry.m_locator[l].IsMissing()) continue;
    1680                 :             :         // If the locator has the entry marked as explicitly removed, stop.
    1681         [ +  + ]:     1373812 :         if (entry.m_locator[l].IsRemoved()) break;
    1682                 :             :         // Otherwise, we have found the topmost ClusterSet that contains this entry.
    1683                 :     1373807 :         return {entry.m_locator[l].cluster, l};
    1684                 :             :     }
    1685                 :             :     // If no non-empty locator was found, or an explicitly removed was hit, return nothing.
    1686                 :        1325 :     return {nullptr, -1};
    1687                 :             : }
    1688                 :             : 
    1689                 :        2482 : Cluster* TxGraphImpl::PullIn(Cluster* cluster, int level) noexcept
    1690                 :             : {
    1691         [ +  + ]:        2482 :     int to_level = GetTopLevel();
    1692         [ +  + ]:        2482 :     Assume(to_level == 1);
    1693                 :        2482 :     Assume(level <= to_level);
    1694                 :             :     // Copy the Cluster from main to staging, if it's not already there.
    1695         [ +  + ]:        2482 :     if (level == 0) {
    1696                 :             :         // Make the Cluster Acceptable before copying. This isn't strictly necessary, but doing it
    1697                 :             :         // now avoids doing double work later.
    1698                 :        1747 :         MakeAcceptable(*cluster, level);
    1699                 :        1747 :         cluster = cluster->CopyToStaging(*this);
    1700                 :             :     }
    1701                 :        2482 :     return cluster;
    1702                 :             : }
    1703                 :             : 
    1704                 :      714576 : void TxGraphImpl::ApplyRemovals(int up_to_level) noexcept
    1705                 :             : {
    1706         [ +  - ]:      714576 :     Assume(up_to_level >= 0 && up_to_level <= GetTopLevel());
    1707         [ +  + ]:     1494519 :     for (int level = 0; level <= up_to_level; ++level) {
    1708                 :      779943 :         auto& clusterset = GetClusterSet(level);
    1709                 :      779943 :         auto& to_remove = clusterset.m_to_remove;
    1710                 :             :         // Skip if there is nothing to remove in this level.
    1711         [ +  + ]:      779943 :         if (to_remove.empty()) continue;
    1712                 :             :         // Pull in all Clusters that are not in staging.
    1713         [ +  + ]:        3704 :         if (level == 1) {
    1714         [ +  + ]:        3527 :             for (GraphIndex index : to_remove) {
    1715         [ +  - ]:        2177 :                 auto [cluster, cluster_level] = FindClusterAndLevel(index, level);
    1716         [ +  - ]:        2177 :                 if (cluster != nullptr) PullIn(cluster, cluster_level);
    1717                 :             :             }
    1718                 :             :         }
    1719                 :             :         // Group the set of to-be-removed entries by Cluster::m_sequence.
    1720                 :        3704 :         std::ranges::sort(to_remove, [&](GraphIndex a, GraphIndex b) noexcept {
    1721                 :      155544 :             Cluster* cluster_a = m_entries[a].m_locator[level].cluster;
    1722                 :      155544 :             Cluster* cluster_b = m_entries[b].m_locator[level].cluster;
    1723                 :      155544 :             return CompareClusters(cluster_a, cluster_b) < 0;
    1724                 :             :         });
    1725                 :             :         // Process per Cluster.
    1726         [ -  + ]:        3704 :         std::span to_remove_span{to_remove};
    1727         [ +  + ]:       27133 :         while (!to_remove_span.empty()) {
    1728         [ +  - ]:       23429 :             Cluster* cluster = m_entries[to_remove_span.front()].m_locator[level].cluster;
    1729         [ +  - ]:       23429 :             if (cluster != nullptr) {
    1730                 :             :                 // If the first to_remove_span entry's Cluster exists, hand to_remove_span to it, so it
    1731                 :             :                 // can pop off whatever applies to it.
    1732                 :       23429 :                 cluster->ApplyRemovals(*this, level, to_remove_span);
    1733                 :             :             } else {
    1734                 :             :                 // Otherwise, skip this already-removed entry. This may happen when
    1735                 :             :                 // RemoveTransaction was called twice on the same Ref, for example.
    1736                 :           0 :                 to_remove_span = to_remove_span.subspan(1);
    1737                 :             :             }
    1738                 :             :         }
    1739         [ +  - ]:      783647 :         to_remove.clear();
    1740                 :             :     }
    1741                 :      714576 :     Compact();
    1742                 :      714576 : }
    1743                 :             : 
    1744                 :       16234 : void TxGraphImpl::SwapIndexes(GraphIndex a, GraphIndex b, std::vector<Cluster*>& affected_main) noexcept
    1745                 :             : {
    1746         [ -  + ]:       16234 :     Assume(a < m_entries.size());
    1747                 :       16234 :     Assume(b < m_entries.size());
    1748                 :             :     // Swap the Entry objects.
    1749                 :       16234 :     std::swap(m_entries[a], m_entries[b]);
    1750                 :             :     // Iterate over both objects.
    1751         [ +  + ]:       48702 :     for (int i = 0; i < 2; ++i) {
    1752         [ +  + ]:       32468 :         GraphIndex idx = i ? b : a;
    1753         [ +  + ]:       32468 :         Entry& entry = m_entries[idx];
    1754                 :             :         // Update linked Ref, if any exists.
    1755         [ +  + ]:       32468 :         if (entry.m_ref) GetRefIndex(*entry.m_ref) = idx;
    1756                 :             :         // Update linked chunk index entries, if any exist.
    1757         [ +  + ]:       32468 :         if (entry.m_main_chunkindex_iterator != m_main_chunkindex.end()) {
    1758                 :       15123 :             entry.m_main_chunkindex_iterator->m_graph_index = idx;
    1759                 :             :         }
    1760                 :             :         // Update the locators for both levels.
    1761         [ +  + ]:       97404 :         for (int level = 0; level < MAX_LEVELS; ++level) {
    1762                 :       64936 :             Locator& locator = entry.m_locator[level];
    1763         [ +  + ]:       64936 :             if (locator.IsPresent()) {
    1764                 :       15429 :                 locator.cluster->UpdateMapping(locator.index, idx);
    1765         [ +  - ]:       15429 :                 if (level == 0) affected_main.push_back(locator.cluster);
    1766                 :             :             }
    1767                 :             :         }
    1768                 :             :     }
    1769                 :       16234 : }
    1770                 :             : 
    1771                 :      828584 : void TxGraphImpl::Compact() noexcept
    1772                 :             : {
    1773                 :             :     // We cannot compact while any to-be-applied operations or staged removals remain as we'd need
    1774                 :             :     // to rewrite them. It is easier to delay the compaction until they have been applied.
    1775         [ +  + ]:      828584 :     if (!m_main_clusterset.m_deps_to_add.empty()) return;
    1776         [ +  + ]:      822637 :     if (!m_main_clusterset.m_to_remove.empty()) return;
    1777         [ +  + ]:      822628 :     Assume(m_main_clusterset.m_removed.empty()); // non-staging m_removed is always empty
    1778         [ +  + ]:      822628 :     if (m_staging_clusterset.has_value()) {
    1779         [ +  + ]:       74215 :         if (!m_staging_clusterset->m_deps_to_add.empty()) return;
    1780         [ +  + ]:       45652 :         if (!m_staging_clusterset->m_to_remove.empty()) return;
    1781         [ +  + ]:       45651 :         if (!m_staging_clusterset->m_removed.empty()) return;
    1782                 :             :     }
    1783                 :             : 
    1784                 :             :     // Release memory used by discarded ChunkData index entries.
    1785                 :      789170 :     ClearShrink(m_main_chunkindex_discarded);
    1786                 :             : 
    1787                 :             :     // Sort the GraphIndexes that need to be cleaned up. They are sorted in reverse, so the last
    1788                 :             :     // ones get processed first. This means earlier-processed GraphIndexes will not cause moving of
    1789                 :             :     // later-processed ones during the "swap with end of m_entries" step below (which might
    1790                 :             :     // invalidate them).
    1791                 :      789170 :     std::ranges::sort(m_unlinked, std::greater{});
    1792                 :             : 
    1793                 :      789170 :     std::vector<Cluster*> affected_main;
    1794                 :      789170 :     auto last = GraphIndex(-1);
    1795         [ +  + ]:      840459 :     for (GraphIndex idx : m_unlinked) {
    1796                 :             :         // m_unlinked should never contain the same GraphIndex twice (the code below would fail
    1797                 :             :         // if so, because GraphIndexes get invalidated by removing them).
    1798                 :       51289 :         Assume(idx != last);
    1799                 :       51289 :         last = idx;
    1800                 :             : 
    1801                 :             :         // Make sure the entry is unlinked.
    1802                 :       51289 :         Entry& entry = m_entries[idx];
    1803                 :       51289 :         Assume(entry.m_ref == nullptr);
    1804                 :             :         // Make sure the entry does not occur in the graph.
    1805         [ +  + ]:      153867 :         for (int level = 0; level < MAX_LEVELS; ++level) {
    1806                 :      102578 :             Assume(!entry.m_locator[level].IsPresent());
    1807                 :             :         }
    1808                 :             : 
    1809                 :             :         // Move the entry to the end.
    1810   [ -  +  +  + ]:       51289 :         if (idx != m_entries.size() - 1) SwapIndexes(idx, m_entries.size() - 1, affected_main);
    1811                 :             :         // Drop the entry for idx, now that it is at the end.
    1812                 :       51289 :         m_entries.pop_back();
    1813                 :             :     }
    1814                 :             : 
    1815                 :             :     // Update the affected clusters, to fixup Entry::m_main_max_chunk_fallback values which may
    1816                 :             :     // have become outdated due to the compaction above.
    1817                 :      789170 :     std::ranges::sort(affected_main);
    1818                 :      789170 :     affected_main.erase(std::unique(affected_main.begin(), affected_main.end()), affected_main.end());
    1819         [ +  + ]:      800139 :     for (Cluster* cluster : affected_main) {
    1820                 :       10969 :         cluster->Updated(*this, /*level=*/0, /*rename=*/true);
    1821                 :             :     }
    1822         [ +  + ]:      817455 :     m_unlinked.clear();
    1823                 :      789170 : }
    1824                 :             : 
    1825                 :       23408 : void TxGraphImpl::Split(Cluster& cluster, int level) noexcept
    1826                 :             : {
    1827                 :             :     // To split a Cluster, first make sure all removals are applied (as we might need to split
    1828                 :             :     // again afterwards otherwise).
    1829                 :       23408 :     ApplyRemovals(level);
    1830                 :       23408 :     bool del = cluster.Split(*this, level);
    1831         [ +  + ]:       23408 :     if (del) {
    1832                 :             :         // Cluster::Split reports whether the Cluster is to be deleted.
    1833                 :       23386 :         DeleteCluster(cluster, level);
    1834                 :             :     }
    1835                 :       23408 : }
    1836                 :             : 
    1837                 :      635976 : void TxGraphImpl::SplitAll(int up_to_level) noexcept
    1838                 :             : {
    1839         [ +  - ]:      635976 :     Assume(up_to_level >= 0 && up_to_level <= GetTopLevel());
    1840                 :             :     // Before splitting all Cluster, first make sure all removals are applied.
    1841                 :      635976 :     ApplyRemovals(up_to_level);
    1842         [ +  + ]:     1280718 :     for (int level = 0; level <= up_to_level; ++level) {
    1843         [ +  + ]:     1934226 :         for (auto quality : {QualityLevel::NEEDS_SPLIT_FIX, QualityLevel::NEEDS_SPLIT}) {
    1844                 :     1289484 :             auto& queue = GetClusterSet(level).m_clusters[int(quality)];
    1845         [ +  + ]:     1312892 :             while (!queue.empty()) {
    1846                 :       23408 :                 Split(*queue.back().get(), level);
    1847                 :             :             }
    1848                 :             :         }
    1849                 :             :     }
    1850                 :      635976 : }
    1851                 :             : 
    1852                 :   160838919 : void TxGraphImpl::GroupClusters(int level) noexcept
    1853                 :             : {
    1854                 :   160838919 :     auto& clusterset = GetClusterSet(level);
    1855                 :             :     // If the groupings have been computed already, nothing is left to be done.
    1856         [ +  + ]:   160838919 :     if (clusterset.m_group_data.has_value()) return;
    1857                 :             : 
    1858                 :             :     // Before computing which Clusters need to be merged together, first apply all removals and
    1859                 :             :     // split the Clusters into connected components. If we would group first, we might end up
    1860                 :             :     // with inefficient and/or oversized Clusters which just end up being split again anyway.
    1861                 :       11151 :     SplitAll(level);
    1862                 :             : 
    1863                 :             :     /** Annotated clusters: an entry for each Cluster, together with the sequence number for the
    1864                 :             :      *  representative for the partition it is in (initially its own, later that of the
    1865                 :             :      *  to-be-merged group). */
    1866                 :       11151 :     std::vector<std::pair<Cluster*, uint64_t>> an_clusters;
    1867                 :             :     /** Annotated dependencies: an entry for each m_deps_to_add entry (excluding ones that apply
    1868                 :             :      *  to removed transactions), together with the sequence number of the representative root of
    1869                 :             :      *  Clusters it applies to (initially that of the child Cluster, later that of the
    1870                 :             :      *  to-be-merged group). */
    1871                 :       11151 :     std::vector<std::pair<std::pair<GraphIndex, GraphIndex>, uint64_t>> an_deps;
    1872                 :             : 
    1873                 :             :     // Construct an an_clusters entry for every oversized cluster, including ones from levels below,
    1874                 :             :     // as they may be inherited in this one.
    1875         [ +  + ]:       31068 :     for (int level_iter = 0; level_iter <= level; ++level_iter) {
    1876         [ +  + ]:       19923 :         for (auto& cluster : GetClusterSet(level_iter).m_clusters[int(QualityLevel::OVERSIZED_SINGLETON)]) {
    1877                 :           6 :             auto graph_idx = cluster->GetClusterEntry(0);
    1878                 :           6 :             auto cur_cluster = FindCluster(graph_idx, level);
    1879         [ -  + ]:           6 :             if (cur_cluster == nullptr) continue;
    1880                 :           6 :             an_clusters.emplace_back(cur_cluster, cur_cluster->m_sequence);
    1881                 :             :         }
    1882                 :             :     }
    1883                 :             : 
    1884                 :             :     // Construct a an_clusters entry for every parent and child in the to-be-applied dependencies,
    1885                 :             :     // and an an_deps entry for each dependency to be applied.
    1886         [ -  + ]:       11151 :     an_deps.reserve(clusterset.m_deps_to_add.size());
    1887   [ +  +  +  + ]:      151829 :     for (const auto& [par, chl] : clusterset.m_deps_to_add) {
    1888                 :      140678 :         auto par_cluster = FindCluster(par, level);
    1889                 :      140678 :         auto chl_cluster = FindCluster(chl, level);
    1890                 :             :         // Skip dependencies for which the parent or child transaction is removed.
    1891   [ +  +  -  + ]:      140678 :         if (par_cluster == nullptr || chl_cluster == nullptr) continue;
    1892                 :      140673 :         an_clusters.emplace_back(par_cluster, par_cluster->m_sequence);
    1893                 :             :         // Do not include a duplicate when parent and child are identical, as it'll be removed
    1894                 :             :         // below anyway.
    1895         [ +  + ]:      140673 :         if (chl_cluster != par_cluster) an_clusters.emplace_back(chl_cluster, chl_cluster->m_sequence);
    1896                 :             :         // Add entry to an_deps, using the child sequence number.
    1897                 :      140673 :         an_deps.emplace_back(std::pair{par, chl}, chl_cluster->m_sequence);
    1898                 :             :     }
    1899                 :             :     // Sort and deduplicate an_clusters, so we end up with a sorted list of all involved Clusters
    1900                 :             :     // to which dependencies apply, or which are oversized.
    1901   [ +  +  +  +  :     4905001 :     std::ranges::sort(an_clusters, [](auto& a, auto& b) noexcept { return a.second < b.second; });
          +  +  +  +  +  
          +  +  +  +  +  
          +  +  +  +  +  
             +  -  -  +  
                      + ]
    1902                 :       11151 :     an_clusters.erase(std::ranges::unique(an_clusters).begin(), an_clusters.end());
    1903                 :             :     // Sort an_deps by applying the same order to the involved child cluster.
    1904   [ -  -  -  -  :     2352630 :     std::ranges::sort(an_deps, [&](auto& a, auto& b) noexcept { return a.second < b.second; });
          +  +  +  +  +  
          +  +  +  +  +  
          +  +  +  +  +  
             +  -  -  +  
                      + ]
    1905                 :             : 
    1906                 :             :     // Run the union-find algorithm to find partitions of the input Clusters which need to be
    1907                 :             :     // grouped together. See https://en.wikipedia.org/wiki/Disjoint-set_data_structure.
    1908                 :       11151 :     {
    1909                 :             :         /** Each PartitionData entry contains information about a single input Cluster. */
    1910                 :       11151 :         struct PartitionData
    1911                 :             :         {
    1912                 :             :             /** The sequence number of the cluster this holds information for. */
    1913                 :             :             uint64_t sequence;
    1914                 :             :             /** All PartitionData entries belonging to the same partition are organized in a tree.
    1915                 :             :              *  Each element points to its parent, or to itself if it is the root. The root is then
    1916                 :             :              *  a representative for the entire tree, and can be found by walking upwards from any
    1917                 :             :              *  element. */
    1918                 :             :             PartitionData* parent;
    1919                 :             :             /** (only if this is a root, so when parent == this) An upper bound on the height of
    1920                 :             :              *  tree for this partition. */
    1921                 :             :             unsigned rank;
    1922                 :             :         };
    1923                 :             :         /** Information about each input Cluster. Sorted by Cluster::m_sequence. */
    1924                 :       11151 :         std::vector<PartitionData> partition_data;
    1925                 :             : 
    1926                 :             :         /** Given a Cluster, find its corresponding PartitionData. */
    1927                 :      284169 :         auto locate_fn = [&](uint64_t sequence) noexcept -> PartitionData* {
    1928                 :      273018 :             auto it = std::lower_bound(partition_data.begin(), partition_data.end(), sequence,
    1929         [ +  + ]:     4090800 :                                        [](auto& a, uint64_t seq) noexcept { return a.sequence < seq; });
    1930                 :      273018 :             Assume(it != partition_data.end());
    1931                 :      273018 :             Assume(it->sequence == sequence);
    1932                 :      273018 :             return &*it;
    1933                 :       11151 :         };
    1934                 :             : 
    1935                 :             :         /** Given a PartitionData, find the root of the tree it is in (its representative). */
    1936                 :      295428 :         static constexpr auto find_root_fn = [](PartitionData* data) noexcept -> PartitionData* {
    1937   [ +  +  +  + ]:      485674 :             while (data->parent != data) {
    1938                 :             :                 // Replace pointers to parents with pointers to grandparents.
    1939                 :             :                 // See https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Finding_set_representatives.
    1940                 :      323397 :                 auto par = data->parent;
    1941                 :      323397 :                 data->parent = par->parent;
    1942                 :      323397 :                 data = par;
    1943                 :             :             }
    1944                 :      284277 :             return data;
    1945                 :             :         };
    1946                 :             : 
    1947                 :             :         /** Given two PartitionDatas, union the partitions they are in, and return their
    1948                 :             :          *  representative. */
    1949                 :      150280 :         static constexpr auto union_fn = [](PartitionData* arg1, PartitionData* arg2) noexcept {
    1950                 :             :             // Find the roots of the trees, and bail out if they are already equal (which would
    1951                 :             :             // mean they are in the same partition already).
    1952         [ +  + ]:      400258 :             auto rep1 = find_root_fn(arg1);
    1953                 :      139129 :             auto rep2 = find_root_fn(arg2);
    1954         [ +  + ]:      139129 :             if (rep1 == rep2) return rep1;
    1955                 :             :             // Pick the lower-rank root to become a child of the higher-rank one.
    1956                 :             :             // See https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Union_by_rank.
    1957         [ +  + ]:      136393 :             if (rep1->rank < rep2->rank) std::swap(rep1, rep2);
    1958                 :      136393 :             rep2->parent = rep1;
    1959                 :      136393 :             rep1->rank += (rep1->rank == rep2->rank);
    1960                 :      136393 :             return rep1;
    1961                 :             :         };
    1962                 :             : 
    1963                 :             :         // Start by initializing every Cluster as its own singleton partition.
    1964         [ -  + ]:       11151 :         partition_data.resize(an_clusters.size());
    1965   [ -  +  +  + ]:      156299 :         for (size_t i = 0; i < an_clusters.size(); ++i) {
    1966                 :      145148 :             partition_data[i].sequence = an_clusters[i].first->m_sequence;
    1967                 :      145148 :             partition_data[i].parent = &partition_data[i];
    1968                 :      145148 :             partition_data[i].rank = 0;
    1969                 :             :         }
    1970                 :             : 
    1971                 :             :         // Run through all parent/child pairs in an_deps, and union the partitions their Clusters
    1972                 :             :         // are in.
    1973                 :       11151 :         Cluster* last_chl_cluster{nullptr};
    1974                 :       11151 :         PartitionData* last_partition{nullptr};
    1975   [ +  +  +  + ]:      151824 :         for (const auto& [dep, _] : an_deps) {
    1976         [ +  + ]:      140673 :             auto [par, chl] = dep;
    1977                 :      140673 :             auto par_cluster = FindCluster(par, level);
    1978                 :      140673 :             auto chl_cluster = FindCluster(chl, level);
    1979         [ +  + ]:      140673 :             Assume(chl_cluster != nullptr && par_cluster != nullptr);
    1980                 :             :             // Nothing to do if parent and child are in the same Cluster.
    1981         [ +  + ]:      140673 :             if (par_cluster == chl_cluster) continue;
    1982         [ +  + ]:      139129 :             Assume(par != chl);
    1983         [ +  + ]:      139129 :             if (chl_cluster == last_chl_cluster) {
    1984                 :             :                 // If the child Clusters is the same as the previous iteration, union with the
    1985                 :             :                 // tree they were in, avoiding the need for another lookup. Note that an_deps
    1986                 :             :                 // is sorted by child Cluster, so batches with the same child are expected.
    1987                 :        5240 :                 last_partition = union_fn(locate_fn(par_cluster->m_sequence), last_partition);
    1988                 :             :             } else {
    1989                 :      133889 :                 last_chl_cluster = chl_cluster;
    1990                 :      133889 :                 last_partition = union_fn(locate_fn(par_cluster->m_sequence), locate_fn(chl_cluster->m_sequence));
    1991                 :             :             }
    1992                 :             :         }
    1993                 :             : 
    1994                 :             :         // Update the sequence numbers in an_clusters and an_deps to be those of the partition
    1995                 :             :         // representative.
    1996                 :       11151 :         auto deps_it = an_deps.begin();
    1997   [ -  +  +  + ]:      156299 :         for (size_t i = 0; i < partition_data.size(); ++i) {
    1998                 :      145148 :             auto& data = partition_data[i];
    1999                 :             :             // Find the sequence of the representative of the partition Cluster i is in, and store
    2000                 :             :             // it with the Cluster.
    2001                 :      145148 :             auto rep_seq = find_root_fn(&data)->sequence;
    2002                 :      145148 :             an_clusters[i].second = rep_seq;
    2003                 :             :             // Find all dependencies whose child Cluster is Cluster i, and annotate them with rep.
    2004         [ +  + ]:      285821 :             while (deps_it != an_deps.end()) {
    2005         [ +  + ]:      277708 :                 auto [par, chl] = deps_it->first;
    2006                 :      277708 :                 auto chl_cluster = FindCluster(chl, level);
    2007         [ +  + ]:      277708 :                 Assume(chl_cluster != nullptr);
    2008         [ +  + ]:      277708 :                 if (chl_cluster->m_sequence > data.sequence) break;
    2009                 :      140673 :                 deps_it->second = rep_seq;
    2010                 :      140673 :                 ++deps_it;
    2011                 :             :             }
    2012                 :             :         }
    2013                 :       11151 :     }
    2014                 :             : 
    2015                 :             :     // Sort both an_clusters and an_deps by sequence number of the representative of the
    2016                 :             :     // partition they are in, grouping all those applying to the same partition together.
    2017   [ -  -  -  -  :     1806349 :     std::ranges::sort(an_deps, [](auto& a, auto& b) noexcept { return a.second < b.second; });
          +  +  +  +  +  
          +  +  +  +  +  
          +  +  +  +  +  
             +  -  -  +  
                      + ]
    2018   [ +  +  +  +  :     1799856 :     std::ranges::sort(an_clusters, [](auto& a, auto& b) noexcept { return a.second < b.second; });
          +  +  +  +  +  
          +  +  +  +  +  
          +  +  +  +  +  
             +  -  -  +  
                      + ]
    2019                 :             : 
    2020                 :             :     // Translate the resulting cluster groups to the m_group_data structure, and the dependencies
    2021                 :             :     // back to m_deps_to_add.
    2022                 :       11151 :     clusterset.m_group_data = GroupData{};
    2023         [ -  + ]:       11151 :     clusterset.m_group_data->m_group_clusters.reserve(an_clusters.size());
    2024         [ +  + ]:       11151 :     clusterset.m_deps_to_add.clear();
    2025         [ -  + ]:       11151 :     clusterset.m_deps_to_add.reserve(an_deps.size());
    2026                 :       11151 :     clusterset.m_oversized = false;
    2027                 :       11151 :     auto an_deps_it = an_deps.begin();
    2028                 :       11151 :     auto an_clusters_it = an_clusters.begin();
    2029         [ +  + ]:       19906 :     while (an_clusters_it != an_clusters.end()) {
    2030                 :             :         // Process all clusters/dependencies belonging to the partition with representative rep.
    2031                 :        8755 :         auto rep = an_clusters_it->second;
    2032                 :             :         // Create and initialize a new GroupData entry for the partition.
    2033                 :        8755 :         auto& new_entry = clusterset.m_group_data->m_groups.emplace_back();
    2034         [ -  + ]:        8755 :         new_entry.m_cluster_offset = clusterset.m_group_data->m_group_clusters.size();
    2035                 :        8755 :         new_entry.m_cluster_count = 0;
    2036         [ -  + ]:        8755 :         new_entry.m_deps_offset = clusterset.m_deps_to_add.size();
    2037                 :        8755 :         new_entry.m_deps_count = 0;
    2038                 :        8755 :         uint32_t total_count{0};
    2039                 :        8755 :         uint64_t total_size{0};
    2040                 :             :         // Add all its clusters to it (copying those from an_clusters to m_group_clusters).
    2041   [ +  +  +  + ]:      153903 :         while (an_clusters_it != an_clusters.end() && an_clusters_it->second == rep) {
    2042                 :      145148 :             clusterset.m_group_data->m_group_clusters.push_back(an_clusters_it->first);
    2043                 :      145148 :             total_count += an_clusters_it->first->GetTxCount();
    2044                 :      145148 :             total_size += an_clusters_it->first->GetTotalTxSize();
    2045                 :      145148 :             ++an_clusters_it;
    2046                 :      145148 :             ++new_entry.m_cluster_count;
    2047                 :             :         }
    2048                 :             :         // Add all its dependencies to it (copying those back from an_deps to m_deps_to_add).
    2049   [ +  +  +  + ]:      149428 :         while (an_deps_it != an_deps.end() && an_deps_it->second == rep) {
    2050                 :      140673 :             clusterset.m_deps_to_add.push_back(an_deps_it->first);
    2051                 :      140673 :             ++an_deps_it;
    2052                 :      140673 :             ++new_entry.m_deps_count;
    2053                 :             :         }
    2054                 :             :         // Detect oversizedness.
    2055   [ +  +  +  + ]:        8755 :         if (total_count > m_max_cluster_count || total_size > m_max_cluster_size) {
    2056                 :         146 :             clusterset.m_oversized = true;
    2057                 :             :         }
    2058                 :             :     }
    2059                 :       11151 :     Assume(an_deps_it == an_deps.end());
    2060                 :       11151 :     Assume(an_clusters_it == an_clusters.end());
    2061                 :       11151 :     Compact();
    2062                 :       11151 : }
    2063                 :             : 
    2064                 :        5974 : void TxGraphImpl::Merge(std::span<Cluster*> to_merge, int level) noexcept
    2065                 :             : {
    2066         [ +  + ]:        5974 :     Assume(!to_merge.empty());
    2067                 :             :     // Nothing to do if a group consists of just a single Cluster.
    2068         [ +  + ]:        5974 :     if (to_merge.size() == 1) return;
    2069                 :             : 
    2070                 :             :     // Move the largest Cluster to the front of to_merge. As all transactions in other to-be-merged
    2071                 :             :     // Clusters will be moved to that one, putting the largest one first minimizes the number of
    2072                 :             :     // moves.
    2073                 :        5953 :     size_t max_size_pos{0};
    2074                 :        5953 :     DepGraphIndex max_size = to_merge[max_size_pos]->GetTxCount();
    2075                 :        5953 :     GetClusterSet(level).m_cluster_usage -= to_merge[max_size_pos]->TotalMemoryUsage();
    2076                 :        5953 :     DepGraphIndex total_size = max_size;
    2077         [ +  + ]:       12463 :     for (size_t i = 1; i < to_merge.size(); ++i) {
    2078                 :        6510 :         GetClusterSet(level).m_cluster_usage -= to_merge[i]->TotalMemoryUsage();
    2079                 :        6510 :         DepGraphIndex size = to_merge[i]->GetTxCount();
    2080                 :        6510 :         total_size += size;
    2081         [ +  + ]:        6510 :         if (size > max_size) {
    2082                 :          66 :             max_size_pos = i;
    2083                 :          66 :             max_size = size;
    2084                 :             :         }
    2085                 :             :     }
    2086         [ +  + ]:        5953 :     if (max_size_pos != 0) std::swap(to_merge[0], to_merge[max_size_pos]);
    2087                 :             : 
    2088                 :        5953 :     size_t start_idx = 1;
    2089                 :        5953 :     Cluster* into_cluster = to_merge[0];
    2090         [ +  + ]:        5953 :     if (total_size > into_cluster->GetMaxTxCount()) {
    2091                 :             :         // The into_merge cluster is too small to fit all transactions being merged. Construct a
    2092                 :             :         // a new Cluster using an implementation that matches the total size, and merge everything
    2093                 :             :         // in there.
    2094                 :        1421 :         auto new_cluster = CreateEmptyCluster(total_size);
    2095                 :        1421 :         into_cluster = new_cluster.get();
    2096                 :        1421 :         InsertCluster(level, std::move(new_cluster), QualityLevel::OPTIMAL);
    2097                 :        1421 :         start_idx = 0;
    2098                 :        1421 :     }
    2099                 :             : 
    2100                 :             :     // Merge all further Clusters in the group into the result (first one, or new one), and delete
    2101                 :             :     // them.
    2102         [ +  + ]:       13884 :     for (size_t i = start_idx; i < to_merge.size(); ++i) {
    2103                 :        7931 :         into_cluster->Merge(*this, level, *to_merge[i]);
    2104                 :        7931 :         DeleteCluster(*to_merge[i], level);
    2105                 :             :     }
    2106                 :        5953 :     into_cluster->Compact();
    2107                 :        5953 :     GetClusterSet(level).m_cluster_usage += into_cluster->TotalMemoryUsage();
    2108                 :             : }
    2109                 :             : 
    2110                 :   160831374 : void TxGraphImpl::ApplyDependencies(int level) noexcept
    2111                 :             : {
    2112                 :   160831374 :     auto& clusterset = GetClusterSet(level);
    2113                 :             :     // Do not bother computing groups if we already know the result will be oversized.
    2114         [ +  + ]:   160831374 :     if (clusterset.m_oversized == true) return;
    2115                 :             :     // Compute the groups of to-be-merged Clusters (which also applies all removals, and splits).
    2116                 :   160831374 :     GroupClusters(level);
    2117         [ +  + ]:   160831374 :     Assume(clusterset.m_group_data.has_value());
    2118                 :             :     // Nothing to do if there are no dependencies to be added.
    2119         [ +  + ]:   160831374 :     if (clusterset.m_deps_to_add.empty()) return;
    2120                 :             :     // Dependencies cannot be applied if it would result in oversized clusters.
    2121         [ +  - ]:        5767 :     if (clusterset.m_oversized == true) return;
    2122                 :             : 
    2123                 :             :     // For each group of to-be-merged Clusters.
    2124         [ +  + ]:       11741 :     for (const auto& group_entry : clusterset.m_group_data->m_groups) {
    2125         [ -  + ]:        5974 :         auto cluster_span = std::span{clusterset.m_group_data->m_group_clusters}
    2126         [ +  + ]:        5974 :                                 .subspan(group_entry.m_cluster_offset, group_entry.m_cluster_count);
    2127                 :             :         // Pull in all the Clusters that contain dependencies.
    2128         [ +  + ]:        5974 :         if (level == 1) {
    2129         [ +  + ]:         384 :             for (Cluster*& cluster : cluster_span) {
    2130                 :         305 :                 cluster = PullIn(cluster, cluster->GetLevel(*this));
    2131                 :             :             }
    2132                 :             :         }
    2133                 :             :         // Invoke Merge() to merge them into a single Cluster.
    2134                 :        5974 :         Merge(cluster_span, level);
    2135                 :             :         // Actually apply all to-be-added dependencies (all parents and children from this grouping
    2136                 :             :         // belong to the same Cluster at this point because of the merging above).
    2137         [ -  + ]:        5974 :         auto deps_span = std::span{clusterset.m_deps_to_add}
    2138                 :        5974 :                              .subspan(group_entry.m_deps_offset, group_entry.m_deps_count);
    2139                 :        5974 :         Assume(!deps_span.empty());
    2140                 :        5974 :         const auto& loc = m_entries[deps_span[0].second].m_locator[level];
    2141                 :        5974 :         Assume(loc.IsPresent());
    2142                 :        5974 :         loc.cluster->ApplyDependencies(*this, level, deps_span);
    2143                 :             :     }
    2144                 :             : 
    2145                 :             :     // Wipe the list of to-be-added dependencies now that they are applied.
    2146         [ +  - ]:        5767 :     clusterset.m_deps_to_add.clear();
    2147                 :        5767 :     Compact();
    2148                 :             :     // Also no further Cluster mergings are needed (note that we clear, but don't set to
    2149                 :             :     // std::nullopt, as that would imply the groupings are unknown).
    2150                 :       11534 :     clusterset.m_group_data = GroupData{};
    2151                 :             : }
    2152                 :             : 
    2153                 :        5988 : std::pair<uint64_t, bool> GenericClusterImpl::Relinearize(TxGraphImpl& graph, int level, uint64_t max_cost) noexcept
    2154                 :             : {
    2155                 :             :     // We can only relinearize Clusters that do not need splitting.
    2156         [ -  + ]:        5988 :     Assume(!NeedsSplitting());
    2157                 :             :     // No work is required for Clusters which are already optimally linearized.
    2158         [ -  + ]:        5988 :     if (IsOptimal()) return {0, false};
    2159                 :             :     // Invoke the actual linearization algorithm (passing in the existing one).
    2160                 :        5988 :     uint64_t rng_seed = graph.m_rng.rand64();
    2161                 :       95054 :     const auto fallback_order = [&](DepGraphIndex a, DepGraphIndex b) noexcept {
    2162                 :       89066 :         const auto ref_a = graph.m_entries[m_mapping[a]].m_ref;
    2163                 :       89066 :         const auto ref_b = graph.m_entries[m_mapping[b]].m_ref;
    2164                 :       89066 :         return graph.m_fallback_order(*ref_a, *ref_b);
    2165                 :        5988 :     };
    2166         [ -  + ]:        5988 :     auto [linearization, optimal, cost] = Linearize(
    2167                 :        5988 :         /*depgraph=*/m_depgraph,
    2168                 :             :         /*max_cost=*/max_cost,
    2169                 :             :         /*rng_seed=*/rng_seed,
    2170                 :             :         /*fallback_order=*/fallback_order,
    2171                 :       11976 :         /*old_linearization=*/m_linearization,
    2172   [ -  +  -  + ]:        5988 :         /*is_topological=*/IsTopological());
    2173                 :             :     // Postlinearize to improve the linearization (if optimal, only the sub-chunk order).
    2174                 :             :     // This also guarantees that all chunks are connected (even when non-optimal).
    2175         [ -  + ]:        5988 :     PostLinearize(m_depgraph, linearization);
    2176                 :             :     // Update the linearization.
    2177                 :        5988 :     m_linearization = std::move(linearization);
    2178                 :             :     // Update the Cluster's quality.
    2179                 :        5988 :     bool improved = false;
    2180         [ +  - ]:        5988 :     if (optimal) {
    2181                 :        5988 :         graph.SetClusterQuality(level, m_quality, m_setindex, QualityLevel::OPTIMAL);
    2182                 :        5988 :         improved = true;
    2183   [ #  #  #  # ]:           0 :     } else if (max_cost >= graph.m_acceptable_cost && !IsAcceptable()) {
    2184                 :           0 :         graph.SetClusterQuality(level, m_quality, m_setindex, QualityLevel::ACCEPTABLE);
    2185                 :           0 :         improved = true;
    2186         [ #  # ]:           0 :     } else if (!IsTopological()) {
    2187                 :           0 :         graph.SetClusterQuality(level, m_quality, m_setindex, QualityLevel::NEEDS_RELINEARIZE);
    2188                 :           0 :         improved = true;
    2189                 :             :     }
    2190                 :             :     // Update the Entry objects.
    2191                 :        5988 :     Updated(graph, /*level=*/level, /*rename=*/false);
    2192                 :        5988 :     return {cost, improved};
    2193                 :        5988 : }
    2194                 :             : 
    2195                 :           0 : std::pair<uint64_t, bool> SingletonClusterImpl::Relinearize(TxGraphImpl& graph, int level, uint64_t max_cost) noexcept
    2196                 :             : {
    2197                 :             :     // All singletons are optimal, oversized, or need splitting. Each of these precludes
    2198                 :             :     // Relinearize from being called.
    2199                 :           0 :     AssertUnreachable();
    2200                 :             : }
    2201                 :             : 
    2202                 :   318326749 : void TxGraphImpl::MakeAcceptable(Cluster& cluster, int level) noexcept
    2203                 :             : {
    2204                 :             :     // Relinearize the Cluster if needed.
    2205   [ +  -  +  +  :   318326749 :     if (!cluster.NeedsSplitting() && !cluster.IsAcceptable() && !cluster.IsOversized()) {
                   +  + ]
    2206                 :          92 :         cluster.Relinearize(*this, level, m_acceptable_cost);
    2207                 :             :     }
    2208                 :   318326749 : }
    2209                 :             : 
    2210                 :      217161 : void TxGraphImpl::MakeAllAcceptable(int level) noexcept
    2211                 :             : {
    2212                 :      217161 :     ApplyDependencies(level);
    2213                 :      217161 :     auto& clusterset = GetClusterSet(level);
    2214         [ +  - ]:      217161 :     if (clusterset.m_oversized == true) return;
    2215         [ +  + ]:      651483 :     for (auto quality : {QualityLevel::NEEDS_FIX, QualityLevel::NEEDS_RELINEARIZE}) {
    2216                 :      434322 :         auto& queue = clusterset.m_clusters[int(quality)];
    2217         [ +  + ]:      434405 :         while (!queue.empty()) {
    2218                 :          83 :             MakeAcceptable(*queue.back().get(), level);
    2219                 :             :         }
    2220                 :             :     }
    2221                 :             : }
    2222                 :             : 
    2223                 :        1760 : GenericClusterImpl::GenericClusterImpl(uint64_t sequence) noexcept : Cluster{sequence} {}
    2224                 :             : 
    2225                 :      136084 : void TxGraphImpl::AddTransaction(Ref& arg, const FeePerWeight& feerate) noexcept
    2226                 :             : {
    2227   [ -  +  -  + ]:      136084 :     Assume(m_main_chunkindex_observers == 0 || GetTopLevel() != 0);
    2228                 :      136084 :     Assume(feerate.size > 0);
    2229                 :      136084 :     Assume(GetRefGraph(arg) == nullptr);
    2230                 :             :     // Construct a new Entry, and link it with the Ref.
    2231         [ -  + ]:      136084 :     auto idx = m_entries.size();
    2232                 :      136084 :     m_entries.emplace_back();
    2233                 :      136084 :     auto& entry = m_entries.back();
    2234                 :      136084 :     entry.m_main_chunkindex_iterator = m_main_chunkindex.end();
    2235                 :      136084 :     entry.m_ref = &arg;
    2236                 :      136084 :     GetRefGraph(arg) = this;
    2237                 :      136084 :     GetRefIndex(arg) = idx;
    2238                 :             :     // Construct a new singleton Cluster (which is necessarily optimally linearized).
    2239                 :      136084 :     bool oversized = uint64_t(feerate.size) > m_max_cluster_size;
    2240                 :      136084 :     auto cluster = CreateEmptyCluster(1);
    2241                 :      136084 :     cluster->AppendTransaction(idx, feerate);
    2242         [ +  + ]:      136084 :     auto cluster_ptr = cluster.get();
    2243         [ +  + ]:      136084 :     int level = GetTopLevel();
    2244                 :      136084 :     auto& clusterset = GetClusterSet(level);
    2245         [ +  + ]:      272159 :     InsertCluster(level, std::move(cluster), oversized ? QualityLevel::OVERSIZED_SINGLETON : QualityLevel::OPTIMAL);
    2246                 :      136084 :     cluster_ptr->Updated(*this, /*level=*/level, /*rename=*/false);
    2247                 :      136084 :     clusterset.m_cluster_usage += cluster_ptr->TotalMemoryUsage();
    2248                 :      136084 :     ++clusterset.m_txcount;
    2249                 :             :     // Deal with individually oversized transactions.
    2250         [ +  + ]:      136084 :     if (oversized) {
    2251                 :           9 :         ++clusterset.m_txcount_oversized;
    2252                 :           9 :         clusterset.m_oversized = true;
    2253         [ +  + ]:           9 :         clusterset.m_group_data = std::nullopt;
    2254                 :             :     }
    2255                 :      136084 : }
    2256                 :             : 
    2257                 :        2188 : void TxGraphImpl::RemoveTransaction(const Ref& arg) noexcept
    2258                 :             : {
    2259                 :             :     // Don't do anything if the Ref is empty (which may be indicative of the transaction already
    2260                 :             :     // having been removed).
    2261         [ +  - ]:        2188 :     if (GetRefGraph(arg) == nullptr) return;
    2262         [ -  + ]:        2188 :     Assume(GetRefGraph(arg) == this);
    2263   [ -  +  +  - ]:        2188 :     Assume(m_main_chunkindex_observers == 0 || GetTopLevel() != 0);
    2264                 :             :     // Find the Cluster the transaction is in, and stop if it isn't in any.
    2265         [ +  - ]:        2188 :     int level = GetTopLevel();
    2266         [ +  - ]:        2188 :     auto cluster = FindCluster(GetRefIndex(arg), level);
    2267         [ +  - ]:        2188 :     if (cluster == nullptr) return;
    2268                 :             :     // Remember that the transaction is to be removed.
    2269                 :        2188 :     auto& clusterset = GetClusterSet(level);
    2270                 :        2188 :     clusterset.m_to_remove.push_back(GetRefIndex(arg));
    2271                 :             :     // Wipe m_group_data (as it will need to be recomputed).
    2272         [ +  + ]:        2188 :     clusterset.m_group_data.reset();
    2273         [ +  - ]:        2188 :     if (clusterset.m_oversized == true) clusterset.m_oversized = std::nullopt;
    2274                 :             : }
    2275                 :             : 
    2276                 :       77678 : void TxGraphImpl::AddDependency(const Ref& parent, const Ref& child) noexcept
    2277                 :             : {
    2278                 :             :     // Don't do anything if either Ref is empty (which may be indicative of it having already been
    2279                 :             :     // removed).
    2280   [ +  -  +  - ]:       77678 :     if (GetRefGraph(parent) == nullptr || GetRefGraph(child) == nullptr) return;
    2281         [ -  + ]:       77678 :     Assume(GetRefGraph(parent) == this && GetRefGraph(child) == this);
    2282   [ -  +  +  - ]:       77678 :     Assume(m_main_chunkindex_observers == 0 || GetTopLevel() != 0);
    2283                 :             :     // Don't do anything if this is a dependency on self.
    2284         [ +  - ]:       77678 :     if (GetRefIndex(parent) == GetRefIndex(child)) return;
    2285                 :             :     // Find the Cluster the parent and child transaction are in, and stop if either appears to be
    2286                 :             :     // already removed.
    2287         [ +  - ]:       77678 :     int level = GetTopLevel();
    2288                 :       77678 :     auto par_cluster = FindCluster(GetRefIndex(parent), level);
    2289         [ +  - ]:       77678 :     if (par_cluster == nullptr) return;
    2290                 :       77678 :     auto chl_cluster = FindCluster(GetRefIndex(child), level);
    2291         [ +  - ]:       77678 :     if (chl_cluster == nullptr) return;
    2292                 :             :     // Remember that this dependency is to be applied.
    2293                 :       77678 :     auto& clusterset = GetClusterSet(level);
    2294                 :       77678 :     clusterset.m_deps_to_add.emplace_back(GetRefIndex(parent), GetRefIndex(child));
    2295                 :             :     // Wipe m_group_data (as it will need to be recomputed).
    2296         [ +  + ]:       77678 :     clusterset.m_group_data.reset();
    2297         [ +  + ]:       85223 :     if (clusterset.m_oversized == false) clusterset.m_oversized = std::nullopt;
    2298                 :             : }
    2299                 :             : 
    2300                 :         302 : bool TxGraphImpl::Exists(const Ref& arg, Level level_select) noexcept
    2301                 :             : {
    2302         [ +  - ]:         302 :     if (GetRefGraph(arg) == nullptr) return false;
    2303         [ +  - ]:         302 :     Assume(GetRefGraph(arg) == this);
    2304         [ +  - ]:         302 :     size_t level = GetSpecifiedLevel(level_select);
    2305                 :             :     // Make sure the transaction isn't scheduled for removal.
    2306                 :         302 :     ApplyRemovals(level);
    2307                 :         302 :     auto cluster = FindCluster(GetRefIndex(arg), level);
    2308                 :         302 :     return cluster != nullptr;
    2309                 :             : }
    2310                 :             : 
    2311                 :       45945 : void GenericClusterImpl::GetAncestorRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept
    2312                 :             : {
    2313                 :             :     /** The union of all ancestors to be returned. */
    2314                 :       45945 :     SetType ancestors_union;
    2315                 :             :     // Process elements from the front of args, as long as they apply.
    2316         [ +  + ]:       91890 :     while (!args.empty()) {
    2317         [ +  - ]:       45945 :         if (args.front().first != this) break;
    2318                 :       45945 :         ancestors_union |= m_depgraph.Ancestors(args.front().second);
    2319                 :       45945 :         args = args.subspan(1);
    2320                 :             :     }
    2321         [ +  - ]:       45945 :     Assume(ancestors_union.Any());
    2322                 :             :     // Translate all ancestors (in arbitrary order) to Refs (if they have any), and return them.
    2323   [ +  -  +  + ]:      357082 :     for (auto idx : ancestors_union) {
    2324                 :      265192 :         const auto& entry = graph.m_entries[m_mapping[idx]];
    2325                 :      265192 :         Assume(entry.m_ref != nullptr);
    2326                 :      265192 :         output.push_back(entry.m_ref);
    2327                 :             :     }
    2328                 :       45945 : }
    2329                 :             : 
    2330                 :      121502 : void SingletonClusterImpl::GetAncestorRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept
    2331                 :             : {
    2332                 :      121502 :     Assume(GetTxCount());
    2333         [ +  + ]:      243004 :     while (!args.empty()) {
    2334         [ +  - ]:      121502 :         if (args.front().first != this) break;
    2335                 :      121502 :         args = args.subspan(1);
    2336                 :             :     }
    2337                 :      121502 :     const auto& entry = graph.m_entries[m_graph_index];
    2338                 :      121502 :     Assume(entry.m_ref != nullptr);
    2339                 :      121502 :     output.push_back(entry.m_ref);
    2340                 :      121502 : }
    2341                 :             : 
    2342                 :       46741 : void GenericClusterImpl::GetDescendantRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept
    2343                 :             : {
    2344                 :             :     /** The union of all descendants to be returned. */
    2345                 :       46741 :     SetType descendants_union;
    2346                 :             :     // Process elements from the front of args, as long as they apply.
    2347         [ +  + ]:       93482 :     while (!args.empty()) {
    2348         [ +  + ]:       46743 :         if (args.front().first != this) break;
    2349                 :       46741 :         descendants_union |= m_depgraph.Descendants(args.front().second);
    2350                 :       46741 :         args = args.subspan(1);
    2351                 :             :     }
    2352         [ +  - ]:       46741 :     Assume(descendants_union.Any());
    2353                 :             :     // Translate all descendants (in arbitrary order) to Refs (if they have any), and return them.
    2354   [ +  -  +  + ]:      497984 :     for (auto idx : descendants_union) {
    2355                 :      404502 :         const auto& entry = graph.m_entries[m_mapping[idx]];
    2356                 :      404502 :         Assume(entry.m_ref != nullptr);
    2357                 :      404502 :         output.push_back(entry.m_ref);
    2358                 :             :     }
    2359                 :       46741 : }
    2360                 :             : 
    2361                 :       42805 : void SingletonClusterImpl::GetDescendantRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept
    2362                 :             : {
    2363                 :             :     // In a singleton cluster, the ancestors or descendants are always just the entire cluster.
    2364                 :       42805 :     GetAncestorRefs(graph, args, output);
    2365                 :       42805 : }
    2366                 :             : 
    2367                 :      224440 : bool GenericClusterImpl::GetClusterRefs(TxGraphImpl& graph, std::span<TxGraph::Ref*> range, LinearizationIndex start_pos) noexcept
    2368                 :             : {
    2369                 :             :     // Translate the transactions in the Cluster (in linearization order, starting at start_pos in
    2370                 :             :     // the linearization) to Refs, and fill them in range.
    2371         [ +  + ]:      665042 :     for (auto& ref : range) {
    2372         [ -  + ]:      440602 :         Assume(start_pos < m_linearization.size());
    2373                 :      440602 :         const auto& entry = graph.m_entries[m_mapping[m_linearization[start_pos++]]];
    2374                 :      440602 :         Assume(entry.m_ref != nullptr);
    2375                 :      440602 :         ref = entry.m_ref;
    2376                 :             :     }
    2377                 :             :     // Return whether start_pos has advanced to the end of the Cluster.
    2378         [ -  + ]:      224440 :     return start_pos == m_linearization.size();
    2379                 :             : }
    2380                 :             : 
    2381                 :       76409 : bool SingletonClusterImpl::GetClusterRefs(TxGraphImpl& graph, std::span<TxGraph::Ref*> range, LinearizationIndex start_pos) noexcept
    2382                 :             : {
    2383                 :       76409 :     Assume(!range.empty());
    2384                 :       76409 :     Assume(GetTxCount());
    2385                 :       76409 :     Assume(start_pos == 0);
    2386                 :       76409 :     const auto& entry = graph.m_entries[m_graph_index];
    2387                 :       76409 :     Assume(entry.m_ref != nullptr);
    2388                 :       76409 :     range[0] = entry.m_ref;
    2389                 :       76409 :     return true;
    2390                 :             : }
    2391                 :             : 
    2392                 :           9 : FeePerWeight GenericClusterImpl::GetIndividualFeerate(DepGraphIndex idx) noexcept
    2393                 :             : {
    2394                 :           9 :     return FeePerWeight::FromFeeFrac(m_depgraph.FeeRate(idx));
    2395                 :             : }
    2396                 :             : 
    2397                 :           2 : FeePerWeight SingletonClusterImpl::GetIndividualFeerate(DepGraphIndex idx) noexcept
    2398                 :             : {
    2399                 :           2 :     Assume(GetTxCount());
    2400                 :           2 :     Assume(idx == 0);
    2401                 :           2 :     return m_feerate;
    2402                 :             : }
    2403                 :             : 
    2404                 :          24 : void GenericClusterImpl::MakeStagingTransactionsMissing(TxGraphImpl& graph) noexcept
    2405                 :             : {
    2406                 :             :     // Mark all transactions of a Cluster missing, needed when aborting staging, so that the
    2407                 :             :     // corresponding Locators don't retain references into aborted Clusters.
    2408         [ +  + ]:         157 :     for (auto ci : m_linearization) {
    2409                 :         133 :         GraphIndex idx = m_mapping[ci];
    2410                 :         133 :         auto& entry = graph.m_entries[idx];
    2411                 :         133 :         entry.m_locator[1].SetMissing();
    2412                 :             :     }
    2413                 :          24 : }
    2414                 :             : 
    2415                 :       24355 : void SingletonClusterImpl::MakeStagingTransactionsMissing(TxGraphImpl& graph) noexcept
    2416                 :             : {
    2417         [ +  - ]:       24355 :     if (GetTxCount()) {
    2418                 :       24355 :         auto& entry = graph.m_entries[m_graph_index];
    2419                 :       24355 :         entry.m_locator[1].SetMissing();
    2420                 :             :     }
    2421                 :       24355 : }
    2422                 :             : 
    2423                 :      125954 : std::vector<TxGraph::Ref*> TxGraphImpl::GetAncestors(const Ref& arg, Level level_select) noexcept
    2424                 :             : {
    2425                 :             :     // Return the empty vector if the Ref is empty.
    2426         [ -  + ]:      125954 :     if (GetRefGraph(arg) == nullptr) return {};
    2427         [ -  + ]:      125954 :     Assume(GetRefGraph(arg) == this);
    2428                 :             :     // Apply all removals and dependencies, as the result might be incorrect otherwise.
    2429         [ -  + ]:      125954 :     size_t level = GetSpecifiedLevel(level_select);
    2430                 :      125954 :     ApplyDependencies(level);
    2431                 :             :     // Ancestry cannot be known if unapplied dependencies remain.
    2432         [ +  + ]:      125954 :     Assume(GetClusterSet(level).m_deps_to_add.empty());
    2433                 :             :     // Find the Cluster the argument is in, and return the empty vector if it isn't in any.
    2434         [ +  + ]:      125954 :     auto [cluster, cluster_level] = FindClusterAndLevel(GetRefIndex(arg), level);
    2435         [ +  + ]:      125954 :     if (cluster == nullptr) return {};
    2436                 :             :     // Dispatch to the Cluster.
    2437                 :      124642 :     std::pair<Cluster*, DepGraphIndex> match = {cluster, m_entries[GetRefIndex(arg)].m_locator[cluster_level].index};
    2438                 :      124642 :     auto matches = std::span(&match, 1);
    2439                 :      124642 :     std::vector<TxGraph::Ref*> ret;
    2440                 :      124642 :     cluster->GetAncestorRefs(*this, matches, ret);
    2441                 :      124642 :     return ret;
    2442                 :      124642 : }
    2443                 :             : 
    2444                 :       89462 : std::vector<TxGraph::Ref*> TxGraphImpl::GetDescendants(const Ref& arg, Level level_select) noexcept
    2445                 :             : {
    2446                 :             :     // Return the empty vector if the Ref is empty.
    2447         [ -  + ]:       89462 :     if (GetRefGraph(arg) == nullptr) return {};
    2448         [ -  + ]:       89462 :     Assume(GetRefGraph(arg) == this);
    2449                 :             :     // Apply all removals and dependencies, as the result might be incorrect otherwise.
    2450         [ -  + ]:       89462 :     size_t level = GetSpecifiedLevel(level_select);
    2451                 :       89462 :     ApplyDependencies(level);
    2452                 :             :     // Ancestry cannot be known if unapplied dependencies remain.
    2453         [ -  + ]:       89462 :     Assume(GetClusterSet(level).m_deps_to_add.empty());
    2454                 :             :     // Find the Cluster the argument is in, and return the empty vector if it isn't in any.
    2455         [ -  + ]:       89462 :     auto [cluster, cluster_level] = FindClusterAndLevel(GetRefIndex(arg), level);
    2456         [ -  + ]:       89462 :     if (cluster == nullptr) return {};
    2457                 :             :     // Dispatch to the Cluster.
    2458                 :       89462 :     std::pair<Cluster*, DepGraphIndex> match = {cluster, m_entries[GetRefIndex(arg)].m_locator[cluster_level].index};
    2459                 :       89462 :     auto matches = std::span(&match, 1);
    2460                 :       89462 :     std::vector<TxGraph::Ref*> ret;
    2461                 :       89462 :     cluster->GetDescendantRefs(*this, matches, ret);
    2462                 :       89462 :     return ret;
    2463                 :       89462 : }
    2464                 :             : 
    2465                 :           0 : std::vector<TxGraph::Ref*> TxGraphImpl::GetAncestorsUnion(std::span<const Ref* const> args, Level level_select) noexcept
    2466                 :             : {
    2467                 :             :     // Apply all dependencies, as the result might be incorrect otherwise.
    2468         [ #  # ]:           0 :     size_t level = GetSpecifiedLevel(level_select);
    2469                 :           0 :     ApplyDependencies(level);
    2470                 :             :     // Ancestry cannot be known if unapplied dependencies remain.
    2471                 :           0 :     Assume(GetClusterSet(level).m_deps_to_add.empty());
    2472                 :             : 
    2473                 :             :     // Translate args to matches.
    2474                 :           0 :     std::vector<std::pair<Cluster*, DepGraphIndex>> matches;
    2475                 :           0 :     matches.reserve(args.size());
    2476         [ #  # ]:           0 :     for (auto arg : args) {
    2477         [ #  # ]:           0 :         Assume(arg);
    2478                 :             :         // Skip empty Refs.
    2479         [ #  # ]:           0 :         if (GetRefGraph(*arg) == nullptr) continue;
    2480         [ #  # ]:           0 :         Assume(GetRefGraph(*arg) == this);
    2481                 :             :         // Find the Cluster the argument is in, and skip if none is found.
    2482         [ #  # ]:           0 :         auto [cluster, cluster_level] = FindClusterAndLevel(GetRefIndex(*arg), level);
    2483         [ #  # ]:           0 :         if (cluster == nullptr) continue;
    2484                 :             :         // Append to matches.
    2485                 :           0 :         matches.emplace_back(cluster, m_entries[GetRefIndex(*arg)].m_locator[cluster_level].index);
    2486                 :             :     }
    2487                 :             :     // Group by Cluster.
    2488                 :           0 :     std::ranges::sort(matches, [](auto& a, auto& b) noexcept { return CompareClusters(a.first, b.first) < 0; });
    2489                 :             :     // Dispatch to the Clusters.
    2490         [ #  # ]:           0 :     std::span match_span(matches);
    2491                 :           0 :     std::vector<TxGraph::Ref*> ret;
    2492         [ #  # ]:           0 :     while (!match_span.empty()) {
    2493                 :           0 :         match_span.front().first->GetAncestorRefs(*this, match_span, ret);
    2494                 :             :     }
    2495                 :           0 :     return ret;
    2496                 :           0 : }
    2497                 :             : 
    2498                 :       17308 : std::vector<TxGraph::Ref*> TxGraphImpl::GetDescendantsUnion(std::span<const Ref* const> args, Level level_select) noexcept
    2499                 :             : {
    2500                 :             :     // Apply all dependencies, as the result might be incorrect otherwise.
    2501         [ -  + ]:       17308 :     size_t level = GetSpecifiedLevel(level_select);
    2502                 :       17308 :     ApplyDependencies(level);
    2503                 :             :     // Ancestry cannot be known if unapplied dependencies remain.
    2504                 :       17308 :     Assume(GetClusterSet(level).m_deps_to_add.empty());
    2505                 :             : 
    2506                 :             :     // Translate args to matches.
    2507                 :       17308 :     std::vector<std::pair<Cluster*, DepGraphIndex>> matches;
    2508                 :       17308 :     matches.reserve(args.size());
    2509         [ +  + ]:       17392 :     for (auto arg : args) {
    2510         [ -  + ]:          84 :         Assume(arg);
    2511                 :             :         // Skip empty Refs.
    2512         [ -  + ]:          84 :         if (GetRefGraph(*arg) == nullptr) continue;
    2513         [ -  + ]:          84 :         Assume(GetRefGraph(*arg) == this);
    2514                 :             :         // Find the Cluster the argument is in, and skip if none is found.
    2515         [ -  + ]:          84 :         auto [cluster, cluster_level] = FindClusterAndLevel(GetRefIndex(*arg), level);
    2516         [ -  + ]:          84 :         if (cluster == nullptr) continue;
    2517                 :             :         // Append to matches.
    2518                 :          84 :         matches.emplace_back(cluster, m_entries[GetRefIndex(*arg)].m_locator[cluster_level].index);
    2519                 :             :     }
    2520                 :             :     // Group by Cluster.
    2521                 :       17308 :     std::ranges::sort(matches, [](auto& a, auto& b) noexcept { return CompareClusters(a.first, b.first) < 0; });
    2522                 :             :     // Dispatch to the Clusters.
    2523         [ -  + ]:       17308 :     std::span match_span(matches);
    2524                 :       17308 :     std::vector<TxGraph::Ref*> ret;
    2525         [ +  + ]:       17392 :     while (!match_span.empty()) {
    2526                 :          84 :         match_span.front().first->GetDescendantRefs(*this, match_span, ret);
    2527                 :             :     }
    2528                 :       17308 :     return ret;
    2529                 :       17308 : }
    2530                 :             : 
    2531                 :       96556 : std::vector<TxGraph::Ref*> TxGraphImpl::GetCluster(const Ref& arg, Level level_select) noexcept
    2532                 :             : {
    2533                 :             :     // Return the empty vector if the Ref is empty (which may be indicative of the transaction
    2534                 :             :     // having been removed already.
    2535         [ -  + ]:       96556 :     if (GetRefGraph(arg) == nullptr) return {};
    2536         [ -  + ]:       96556 :     Assume(GetRefGraph(arg) == this);
    2537                 :             :     // Apply all removals and dependencies, as the result might be incorrect otherwise.
    2538         [ -  + ]:       96556 :     size_t level = GetSpecifiedLevel(level_select);
    2539                 :       96556 :     ApplyDependencies(level);
    2540                 :             :     // Cluster linearization cannot be known if unapplied dependencies remain.
    2541         [ -  + ]:       96556 :     Assume(GetClusterSet(level).m_deps_to_add.empty());
    2542                 :             :     // Find the Cluster the argument is in, and return the empty vector if it isn't in any.
    2543         [ -  + ]:       96556 :     auto [cluster, cluster_level] = FindClusterAndLevel(GetRefIndex(arg), level);
    2544         [ -  + ]:       96556 :     if (cluster == nullptr) return {};
    2545                 :             :     // Make sure the Cluster has an acceptable quality level, and then dispatch to it.
    2546                 :       96556 :     MakeAcceptable(*cluster, cluster_level);
    2547         [ -  + ]:       96556 :     std::vector<TxGraph::Ref*> ret(cluster->GetTxCount());
    2548         [ -  + ]:       96556 :     cluster->GetClusterRefs(*this, ret, 0);
    2549                 :       96556 :     return ret;
    2550                 :       96556 : }
    2551                 :             : 
    2552                 :          23 : TxGraph::GraphIndex TxGraphImpl::GetTransactionCount(Level level_select) noexcept
    2553                 :             : {
    2554         [ +  + ]:          23 :     size_t level = GetSpecifiedLevel(level_select);
    2555                 :          23 :     ApplyRemovals(level);
    2556                 :          23 :     return GetClusterSet(level).m_txcount;
    2557                 :             : }
    2558                 :             : 
    2559                 :          11 : FeePerWeight TxGraphImpl::GetIndividualFeerate(const Ref& arg) noexcept
    2560                 :             : {
    2561                 :             :     // Return the empty FeePerWeight if the passed Ref is empty.
    2562         [ -  + ]:          11 :     if (GetRefGraph(arg) == nullptr) return {};
    2563                 :          11 :     Assume(GetRefGraph(arg) == this);
    2564                 :             :     // Find the cluster the argument is in (the level does not matter as individual feerates will
    2565                 :             :     // be identical if it occurs in both), and return the empty FeePerWeight if it isn't in any.
    2566                 :          11 :     Cluster* cluster{nullptr};
    2567                 :          11 :     int level;
    2568         [ +  - ]:          11 :     for (level = 0; level <= GetTopLevel(); ++level) {
    2569                 :             :         // Apply removals, so that we can correctly report FeePerWeight{} for non-existing
    2570                 :             :         // transactions.
    2571                 :          11 :         ApplyRemovals(level);
    2572         [ -  + ]:          11 :         if (m_entries[GetRefIndex(arg)].m_locator[level].IsPresent()) {
    2573                 :             :             cluster = m_entries[GetRefIndex(arg)].m_locator[level].cluster;
    2574                 :             :             break;
    2575                 :             :         }
    2576                 :             :     }
    2577         [ -  + ]:          11 :     if (cluster == nullptr) return {};
    2578                 :             :     // Dispatch to the Cluster.
    2579                 :          11 :     return cluster->GetIndividualFeerate(m_entries[GetRefIndex(arg)].m_locator[level].index);
    2580                 :             : }
    2581                 :             : 
    2582                 :       59888 : FeePerWeight TxGraphImpl::GetMainChunkFeerate(const Ref& arg) noexcept
    2583                 :             : {
    2584                 :             :     // Return the empty FeePerWeight if the passed Ref is empty.
    2585         [ -  + ]:       59888 :     if (GetRefGraph(arg) == nullptr) return {};
    2586                 :       59888 :     Assume(GetRefGraph(arg) == this);
    2587                 :             :     // Apply all removals and dependencies, as the result might be inaccurate otherwise.
    2588                 :       59888 :     ApplyDependencies(/*level=*/0);
    2589                 :             :     // Chunk feerates cannot be accurately known if unapplied dependencies remain.
    2590         [ -  + ]:       59888 :     Assume(m_main_clusterset.m_deps_to_add.empty());
    2591                 :             :     // Find the cluster the argument is in, and return the empty FeePerWeight if it isn't in any.
    2592         [ -  + ]:       59888 :     auto [cluster, cluster_level] = FindClusterAndLevel(GetRefIndex(arg), /*level=*/0);
    2593         [ -  + ]:       59888 :     if (cluster == nullptr) return {};
    2594                 :             :     // Make sure the Cluster has an acceptable quality level, and then return the transaction's
    2595                 :             :     // chunk feerate.
    2596                 :       59888 :     MakeAcceptable(*cluster, cluster_level);
    2597                 :       59888 :     const auto& entry = m_entries[GetRefIndex(arg)];
    2598                 :       59888 :     return entry.m_main_chunk_feerate;
    2599                 :             : }
    2600                 :             : 
    2601                 :      250189 : bool TxGraphImpl::IsOversized(Level level_select) noexcept
    2602                 :             : {
    2603         [ +  + ]:      250189 :     size_t level = GetSpecifiedLevel(level_select);
    2604                 :      250189 :     auto& clusterset = GetClusterSet(level);
    2605         [ +  + ]:      250189 :     if (clusterset.m_oversized.has_value()) {
    2606                 :             :         // Return cached value if known.
    2607                 :      242676 :         return *clusterset.m_oversized;
    2608                 :             :     }
    2609                 :        7513 :     ApplyRemovals(level);
    2610         [ -  + ]:        7513 :     if (clusterset.m_txcount_oversized > 0) {
    2611                 :           0 :         clusterset.m_oversized = true;
    2612                 :             :     } else {
    2613                 :             :         // Find which Clusters will need to be merged together, as that is where the oversize
    2614                 :             :         // property is assessed.
    2615                 :        7513 :         GroupClusters(level);
    2616                 :             :     }
    2617                 :        7513 :     Assume(clusterset.m_oversized.has_value());
    2618                 :        7513 :     return *clusterset.m_oversized;
    2619                 :             : }
    2620                 :             : 
    2621                 :       71142 : void TxGraphImpl::StartStaging() noexcept
    2622                 :             : {
    2623                 :             :     // Staging cannot already exist.
    2624                 :       71142 :     Assume(!m_staging_clusterset.has_value());
    2625                 :             :     // Apply all remaining dependencies in main before creating a staging graph. Once staging
    2626                 :             :     // exists, we cannot merge Clusters anymore (because of interference with Clusters being
    2627                 :             :     // pulled into staging), so to make sure all inspectors are available (if not oversized), do
    2628                 :             :     // all merging work now. Call SplitAll() first, so that even if ApplyDependencies does not do
    2629                 :             :     // any thing due to knowing the result is oversized, splitting is still performed.
    2630                 :       71142 :     SplitAll(0);
    2631                 :       71142 :     ApplyDependencies(0);
    2632                 :             :     // Construct the staging ClusterSet.
    2633                 :       71142 :     m_staging_clusterset.emplace();
    2634                 :             :     // Copy statistics, precomputed data, and to-be-applied dependencies (only if oversized) to
    2635                 :             :     // the new graph. To-be-applied removals will always be empty at this point.
    2636                 :       71142 :     m_staging_clusterset->m_txcount = m_main_clusterset.m_txcount;
    2637                 :       71142 :     m_staging_clusterset->m_txcount_oversized = m_main_clusterset.m_txcount_oversized;
    2638                 :       71142 :     m_staging_clusterset->m_deps_to_add = m_main_clusterset.m_deps_to_add;
    2639                 :       71142 :     m_staging_clusterset->m_group_data = m_main_clusterset.m_group_data;
    2640                 :       71142 :     m_staging_clusterset->m_oversized = m_main_clusterset.m_oversized;
    2641                 :       71142 :     Assume(m_staging_clusterset->m_oversized.has_value());
    2642                 :       71142 :     m_staging_clusterset->m_cluster_usage = 0;
    2643                 :       71142 : }
    2644                 :             : 
    2645                 :       23799 : void TxGraphImpl::AbortStaging() noexcept
    2646                 :             : {
    2647                 :             :     // Staging must exist.
    2648                 :       23799 :     Assume(m_staging_clusterset.has_value());
    2649                 :             :     // Mark all removed transactions as Missing (so the staging locator for these transactions
    2650                 :             :     // can be reused if another staging is created).
    2651         [ +  + ]:       24396 :     for (auto idx : m_staging_clusterset->m_removed) {
    2652                 :         597 :         m_entries[idx].m_locator[1].SetMissing();
    2653                 :             :     }
    2654                 :             :     // Do the same with the non-removed transactions in staging Clusters.
    2655         [ +  + ]:      190392 :     for (int quality = 0; quality < int(QualityLevel::NONE); ++quality) {
    2656         [ +  + ]:      190972 :         for (auto& cluster : m_staging_clusterset->m_clusters[quality]) {
    2657                 :       24379 :             cluster->MakeStagingTransactionsMissing(*this);
    2658                 :             :         }
    2659                 :             :     }
    2660                 :             :     // Destroy the staging ClusterSet.
    2661                 :       23799 :     m_staging_clusterset.reset();
    2662                 :       23799 :     Compact();
    2663         [ -  + ]:       23799 :     if (!m_main_clusterset.m_group_data.has_value()) {
    2664                 :             :         // In case m_oversized in main was kept after a Ref destruction while staging exists, we
    2665                 :             :         // need to re-evaluate m_oversized now.
    2666   [ #  #  #  # ]:           0 :         if (m_main_clusterset.m_to_remove.empty() && m_main_clusterset.m_txcount_oversized > 0) {
    2667                 :             :             // It is possible that a Ref destruction caused a removal in main while staging existed.
    2668                 :             :             // In this case, m_txcount_oversized may be inaccurate.
    2669                 :           0 :             m_main_clusterset.m_oversized = true;
    2670                 :             :         } else {
    2671         [ #  # ]:           0 :             m_main_clusterset.m_oversized = std::nullopt;
    2672                 :             :         }
    2673                 :             :     }
    2674                 :       23799 : }
    2675                 :             : 
    2676                 :       47343 : void TxGraphImpl::CommitStaging() noexcept
    2677                 :             : {
    2678                 :             :     // Staging must exist.
    2679                 :       47343 :     Assume(m_staging_clusterset.has_value());
    2680                 :       47343 :     Assume(m_main_chunkindex_observers == 0);
    2681                 :             :     // Get rid of removed transactions in staging before moving to main, so they do not need to be
    2682                 :             :     // added to the chunk index there. Doing so is impossible if they were unlinked, and thus have
    2683                 :             :     // no Ref anymore to pass to the fallback comparator.
    2684                 :       47343 :     ApplyRemovals(/*up_to_level=*/1);
    2685                 :             :     // Delete all conflicting Clusters in main, to make place for moving the staging ones
    2686                 :             :     // there. All of these have been copied to staging in PullIn().
    2687                 :       47343 :     auto conflicts = GetConflicts();
    2688         [ +  + ]:       48602 :     for (Cluster* conflict : conflicts) {
    2689                 :        1259 :         conflict->Clear(*this, /*level=*/0);
    2690                 :        1259 :         DeleteCluster(*conflict, /*level=*/0);
    2691                 :             :     }
    2692                 :             :     // Mark the removed transactions as Missing (so the staging locator for these transactions
    2693                 :             :     // can be reused if another staging is created).
    2694         [ +  + ]:       48923 :     for (auto idx : m_staging_clusterset->m_removed) {
    2695                 :        1580 :         m_entries[idx].m_locator[1].SetMissing();
    2696                 :             :     }
    2697                 :             :     // Then move all Clusters in staging to main.
    2698         [ +  + ]:      378744 :     for (int quality = 0; quality < int(QualityLevel::NONE); ++quality) {
    2699                 :      331401 :         auto& stage_sets = m_staging_clusterset->m_clusters[quality];
    2700         [ +  + ]:      378854 :         while (!stage_sets.empty()) {
    2701                 :       47453 :             stage_sets.back()->MoveToMain(*this);
    2702                 :             :         }
    2703                 :             :     }
    2704                 :             :     // Move all statistics, precomputed data, and to-be-applied removals and dependencies.
    2705                 :       47343 :     m_main_clusterset.m_deps_to_add = std::move(m_staging_clusterset->m_deps_to_add);
    2706                 :       47343 :     m_main_clusterset.m_to_remove = std::move(m_staging_clusterset->m_to_remove);
    2707                 :       47343 :     m_main_clusterset.m_group_data = std::move(m_staging_clusterset->m_group_data);
    2708                 :       47343 :     m_main_clusterset.m_oversized = m_staging_clusterset->m_oversized;
    2709                 :       47343 :     m_main_clusterset.m_txcount = m_staging_clusterset->m_txcount;
    2710                 :       47343 :     m_main_clusterset.m_txcount_oversized = m_staging_clusterset->m_txcount_oversized;
    2711                 :             :     // Delete the old staging graph, after all its information was moved to main.
    2712                 :       47343 :     m_staging_clusterset.reset();
    2713                 :       47343 :     Compact();
    2714                 :       47343 : }
    2715                 :             : 
    2716                 :          16 : void GenericClusterImpl::SetFee(TxGraphImpl& graph, int level, DepGraphIndex idx, int64_t fee) noexcept
    2717                 :             : {
    2718                 :             :     // Make sure the specified DepGraphIndex exists in this Cluster.
    2719         [ +  - ]:          16 :     Assume(m_depgraph.Positions()[idx]);
    2720                 :             :     // Bail out if the fee isn't actually being changed.
    2721         [ +  - ]:          16 :     if (m_depgraph.FeeRate(idx).fee == fee) return;
    2722                 :             :     // Update the fee, remember that relinearization will be necessary, and update the Entries
    2723                 :             :     // in the same Cluster.
    2724         [ +  - ]:          16 :     m_depgraph.FeeRate(idx).fee = fee;
    2725         [ +  - ]:          16 :     if (m_quality == QualityLevel::OVERSIZED_SINGLETON) {
    2726                 :             :         // Nothing to do.
    2727         [ +  + ]:          16 :     } else if (IsAcceptable()) {
    2728                 :          12 :         graph.SetClusterQuality(level, m_quality, m_setindex, QualityLevel::NEEDS_RELINEARIZE);
    2729                 :             :     }
    2730                 :          16 :     Updated(graph, /*level=*/level, /*rename=*/false);
    2731                 :             : }
    2732                 :             : 
    2733                 :         287 : void SingletonClusterImpl::SetFee(TxGraphImpl& graph, int level, DepGraphIndex idx, int64_t fee) noexcept
    2734                 :             : {
    2735                 :         287 :     Assume(GetTxCount());
    2736                 :         287 :     Assume(idx == 0);
    2737                 :         287 :     m_feerate.fee = fee;
    2738                 :         287 :     Updated(graph, /*level=*/level, /*rename=*/false);
    2739                 :         287 : }
    2740                 :             : 
    2741                 :         303 : void TxGraphImpl::SetTransactionFee(const Ref& ref, int64_t fee) noexcept
    2742                 :             : {
    2743                 :             :     // Don't do anything if the passed Ref is empty.
    2744         [ +  - ]:         303 :     if (GetRefGraph(ref) == nullptr) return;
    2745                 :         303 :     Assume(GetRefGraph(ref) == this);
    2746                 :         303 :     Assume(m_main_chunkindex_observers == 0);
    2747                 :             :     // Find the entry, its locator, and inform its Cluster about the new feerate, if any.
    2748                 :         303 :     auto& entry = m_entries[GetRefIndex(ref)];
    2749         [ +  + ]:         909 :     for (int level = 0; level < MAX_LEVELS; ++level) {
    2750                 :         606 :         auto& locator = entry.m_locator[level];
    2751         [ +  + ]:         606 :         if (locator.IsPresent()) {
    2752                 :         303 :             locator.cluster->SetFee(*this, level, locator.index, fee);
    2753                 :             :         }
    2754                 :             :     }
    2755                 :             : }
    2756                 :             : 
    2757                 :   159052129 : std::strong_ordering TxGraphImpl::CompareMainOrder(const Ref& a, const Ref& b) noexcept
    2758                 :             : {
    2759                 :             :     // The references must not be empty.
    2760                 :   159052129 :     Assume(GetRefGraph(a) == this);
    2761                 :   159052129 :     Assume(GetRefGraph(b) == this);
    2762                 :             :     // Apply dependencies in main.
    2763                 :   159052129 :     ApplyDependencies(0);
    2764                 :   159052129 :     Assume(m_main_clusterset.m_deps_to_add.empty());
    2765                 :             :     // Make both involved Clusters acceptable, so chunk feerates are relevant.
    2766                 :   159052129 :     const auto& entry_a = m_entries[GetRefIndex(a)];
    2767                 :   159052129 :     const auto& entry_b = m_entries[GetRefIndex(b)];
    2768                 :   159052129 :     const auto& locator_a = entry_a.m_locator[0];
    2769                 :   159052129 :     const auto& locator_b = entry_b.m_locator[0];
    2770                 :   159052129 :     Assume(locator_a.IsPresent());
    2771                 :   159052129 :     Assume(locator_b.IsPresent());
    2772                 :   159052129 :     MakeAcceptable(*locator_a.cluster, /*level=*/0);
    2773                 :   159052129 :     MakeAcceptable(*locator_b.cluster, /*level=*/0);
    2774                 :             :     // Invoke comparison logic.
    2775                 :   159052129 :     return CompareMainTransactions(GetRefIndex(a), GetRefIndex(b));
    2776                 :             : }
    2777                 :             : 
    2778                 :        1395 : TxGraph::GraphIndex TxGraphImpl::CountDistinctClusters(std::span<const Ref* const> refs, Level level_select) noexcept
    2779                 :             : {
    2780         [ -  + ]:        1395 :     size_t level = GetSpecifiedLevel(level_select);
    2781                 :        1395 :     ApplyDependencies(level);
    2782                 :        1395 :     auto& clusterset = GetClusterSet(level);
    2783                 :        1395 :     Assume(clusterset.m_deps_to_add.empty());
    2784                 :             :     // Build a vector of Clusters that the specified Refs occur in.
    2785                 :        1395 :     std::vector<Cluster*> clusters;
    2786                 :        1395 :     clusters.reserve(refs.size());
    2787         [ +  + ]:        4144 :     for (const Ref* ref : refs) {
    2788         [ -  + ]:        2749 :         Assume(ref);
    2789         [ -  + ]:        2749 :         if (GetRefGraph(*ref) == nullptr) continue;
    2790         [ +  - ]:        2749 :         Assume(GetRefGraph(*ref) == this);
    2791         [ +  - ]:        2749 :         auto cluster = FindCluster(GetRefIndex(*ref), level);
    2792         [ +  - ]:        2749 :         if (cluster != nullptr) clusters.push_back(cluster);
    2793                 :             :     }
    2794                 :             :     // Count the number of distinct elements in clusters.
    2795                 :        1395 :     std::ranges::sort(clusters, [](Cluster* a, Cluster* b) noexcept { return CompareClusters(a, b) < 0; });
    2796                 :        1395 :     Cluster* last{nullptr};
    2797                 :        1395 :     GraphIndex ret{0};
    2798         [ +  + ]:        4144 :     for (Cluster* cluster : clusters) {
    2799                 :        2749 :         ret += (cluster != last);
    2800                 :        2749 :         last = cluster;
    2801                 :             :     }
    2802                 :        1395 :     return ret;
    2803                 :        1395 : }
    2804                 :             : 
    2805                 :        1339 : std::pair<std::vector<FeeFrac>, std::vector<FeeFrac>> TxGraphImpl::GetMainStagingDiagrams() noexcept
    2806                 :             : {
    2807                 :        1339 :     Assume(m_staging_clusterset.has_value());
    2808                 :        1339 :     MakeAllAcceptable(0);
    2809                 :        1339 :     Assume(m_main_clusterset.m_deps_to_add.empty()); // can only fail if main is oversized
    2810                 :        1339 :     MakeAllAcceptable(1);
    2811                 :        1339 :     Assume(m_staging_clusterset->m_deps_to_add.empty()); // can only fail if staging is oversized
    2812                 :             :     // For all Clusters in main which conflict with Clusters in staging (i.e., all that are removed
    2813                 :             :     // by, or replaced in, staging), gather their chunk feerates.
    2814                 :        1339 :     auto main_clusters = GetConflicts();
    2815                 :        1339 :     std::vector<FeeFrac> main_feerates, staging_feerates;
    2816         [ +  + ]:        3075 :     for (Cluster* cluster : main_clusters) {
    2817                 :        1736 :         cluster->AppendChunkFeerates(main_feerates);
    2818                 :             :     }
    2819                 :             :     // Do the same for the Clusters in staging themselves.
    2820         [ +  + ]:       10712 :     for (int quality = 0; quality < int(QualityLevel::NONE); ++quality) {
    2821         [ +  + ]:       10791 :         for (const auto& cluster : m_staging_clusterset->m_clusters[quality]) {
    2822                 :        1418 :             cluster->AppendChunkFeerates(staging_feerates);
    2823                 :             :         }
    2824                 :             :     }
    2825                 :             :     // Sort both by decreasing feerate to obtain diagrams, and return them.
    2826                 :        1339 :     std::ranges::sort(main_feerates, std::greater<ByRatioNegSize<FeeFrac>>{});
    2827                 :        1339 :     std::ranges::sort(staging_feerates, std::greater<ByRatioNegSize<FeeFrac>>{});
    2828                 :        1339 :     return std::make_pair(std::move(main_feerates), std::move(staging_feerates));
    2829                 :        1339 : }
    2830                 :             : 
    2831                 :       69330 : void GenericClusterImpl::SanityCheck(const TxGraphImpl& graph, int level) const
    2832                 :             : {
    2833                 :             :     // There must be an m_mapping for each m_depgraph position (including holes).
    2834   [ -  +  -  +  :       69330 :     assert(m_depgraph.PositionRange() == m_mapping.size());
                   -  + ]
    2835                 :             :     // The linearization for this Cluster must contain every transaction once.
    2836   [ -  +  -  + ]:       69330 :     assert(m_depgraph.TxCount() == m_linearization.size());
    2837                 :             :     // Unless a split is to be applied, the cluster cannot have any holes.
    2838         [ +  + ]:       69330 :     if (!NeedsSplitting()) {
    2839         [ -  + ]:       69329 :         assert(m_depgraph.Positions() == SetType::Fill(m_depgraph.TxCount()));
    2840                 :             :     }
    2841                 :             : 
    2842                 :             :     // Compute the chunking of m_linearization.
    2843                 :       69330 :     auto linchunking = ChunkLinearizationInfo(m_depgraph, m_linearization);
    2844                 :       69330 :     unsigned chunk_num{0};
    2845                 :             : 
    2846                 :             :     // Verify m_linearization.
    2847                 :       69330 :     SetType m_done;
    2848                 :       69330 :     LinearizationIndex linindex{0};
    2849                 :       69330 :     DepGraphIndex chunk_pos{0}; //!< position within the current chunk
    2850         [ -  + ]:       69330 :     assert(m_depgraph.IsAcyclic());
    2851         [ -  + ]:       69330 :     if (m_linearization.empty()) return;
    2852                 :       69330 :     FeeFrac equal_feerate_prefix = linchunking[chunk_num].feerate;
    2853         [ +  + ]:      473811 :     for (auto lin_pos : m_linearization) {
    2854   [ -  +  -  + ]:      404481 :         assert(lin_pos < m_mapping.size());
    2855         [ +  - ]:      404481 :         const auto& entry = graph.m_entries[m_mapping[lin_pos]];
    2856                 :             :         // Check that the linearization is topological.
    2857         [ +  - ]:      404481 :         m_done.Set(lin_pos);
    2858         [ +  - ]:      404481 :         if (IsTopological()) {
    2859         [ -  + ]:      404481 :             assert(m_done.IsSupersetOf(m_depgraph.Ancestors(lin_pos)));
    2860                 :             :         }
    2861                 :             :         // Check that the Entry has a locator pointing back to this Cluster & position within it.
    2862         [ -  + ]:      404481 :         assert(entry.m_locator[level].cluster == this);
    2863         [ -  + ]:      404481 :         assert(entry.m_locator[level].index == lin_pos);
    2864                 :             :         // For main-level entries, check linearization position and chunk feerate.
    2865   [ +  -  +  + ]:      404481 :         if (level == 0 && IsAcceptable()) {
    2866         [ -  + ]:      404480 :             assert(entry.m_main_lin_index == linindex);
    2867                 :      404480 :             ++linindex;
    2868         [ +  + ]:      404480 :             if (!linchunking[chunk_num].transactions[lin_pos]) {
    2869                 :             :                 // First transaction of a new chunk.
    2870                 :      189418 :                 ++chunk_num;
    2871   [ -  +  -  + ]:      189418 :                 assert(chunk_num < linchunking.size());
    2872                 :      189418 :                 chunk_pos = 0;
    2873         [ +  + ]:      189418 :                 if (ByRatio{linchunking[chunk_num].feerate} < ByRatio{equal_feerate_prefix}) {
    2874                 :        8751 :                     equal_feerate_prefix = linchunking[chunk_num].feerate;
    2875                 :             :                 } else {
    2876         [ -  + ]:      180667 :                     assert(ByRatio{linchunking[chunk_num].feerate} == ByRatio{equal_feerate_prefix});
    2877                 :      180667 :                     equal_feerate_prefix += linchunking[chunk_num].feerate;
    2878                 :             :                 }
    2879                 :             :             }
    2880         [ +  - ]:      404480 :             assert(entry.m_main_chunk_feerate == linchunking[chunk_num].feerate);
    2881         [ -  + ]:      404480 :             assert(entry.m_main_equal_feerate_chunk_prefix_size == equal_feerate_prefix.size);
    2882                 :             :             // Verify that an entry in the chunk index exists for every chunk-ending transaction.
    2883                 :      404480 :             ++chunk_pos;
    2884         [ +  - ]:      404480 :             if (graph.m_main_clusterset.m_to_remove.empty()) {
    2885         [ -  + ]:      404480 :                 bool is_chunk_end = (chunk_pos == linchunking[chunk_num].transactions.Count());
    2886         [ -  + ]:      404480 :                 assert((entry.m_main_chunkindex_iterator != graph.m_main_chunkindex.end()) == is_chunk_end);
    2887         [ +  + ]:      404480 :                 if (is_chunk_end) {
    2888         [ +  + ]:      258747 :                     auto& chunk_data = *entry.m_main_chunkindex_iterator;
    2889   [ +  +  +  + ]:      258747 :                     if (m_done == m_depgraph.Positions() && chunk_pos == 1) {
    2890         [ -  + ]:       58788 :                         assert(chunk_data.m_chunk_count == LinearizationIndex(-1));
    2891                 :             :                     } else {
    2892         [ -  + ]:      199959 :                         assert(chunk_data.m_chunk_count == chunk_pos);
    2893                 :             :                     }
    2894                 :             :                 }
    2895                 :             :             }
    2896                 :             :             // If this Cluster has an acceptable quality level, its chunks must be connected.
    2897         [ -  + ]:      404480 :             assert(m_depgraph.IsConnected(linchunking[chunk_num].transactions));
    2898                 :             :         }
    2899                 :             :     }
    2900                 :             :     // Verify that each element of m_depgraph occurred in m_linearization.
    2901         [ -  + ]:       69330 :     assert(m_done == m_depgraph.Positions());
    2902                 :       69330 : }
    2903                 :             : 
    2904                 :    12074685 : void SingletonClusterImpl::SanityCheck(const TxGraphImpl& graph, int level) const
    2905                 :             : {
    2906                 :             :     // All singletons are optimal, oversized, or need splitting.
    2907   [ +  +  +  +  :    12074685 :     Assume(IsOptimal() || IsOversized() || NeedsSplitting());
                   +  + ]
    2908         [ +  + ]:    12074685 :     if (GetTxCount()) {
    2909         [ -  + ]:    12074674 :         const auto& entry = graph.m_entries[m_graph_index];
    2910                 :             :         // Check that the Entry has a locator pointing back to this Cluster & position within it.
    2911         [ -  + ]:    12074674 :         assert(entry.m_locator[level].cluster == this);
    2912         [ -  + ]:    12074674 :         assert(entry.m_locator[level].index == 0);
    2913                 :             :         // For main-level entries, check linearization position and chunk feerate.
    2914   [ +  -  +  + ]:    12074674 :         if (level == 0 && IsAcceptable()) {
    2915         [ -  + ]:    12074662 :             assert(entry.m_main_lin_index == 0);
    2916         [ +  - ]:    12074662 :             assert(entry.m_main_chunk_feerate == m_feerate);
    2917         [ -  + ]:    12074662 :             assert(entry.m_main_equal_feerate_chunk_prefix_size == m_feerate.size);
    2918         [ +  + ]:    12074662 :             if (graph.m_main_clusterset.m_to_remove.empty()) {
    2919         [ -  + ]:    12074368 :                 assert(entry.m_main_chunkindex_iterator != graph.m_main_chunkindex.end());
    2920         [ -  + ]:    12074368 :                 auto& chunk_data = *entry.m_main_chunkindex_iterator;
    2921         [ -  + ]:    12074368 :                 assert(chunk_data.m_chunk_count == LinearizationIndex(-1));
    2922                 :             :             }
    2923                 :             :         }
    2924                 :             :     }
    2925                 :    12074685 : }
    2926                 :             : 
    2927                 :      175346 : void TxGraphImpl::SanityCheck() const
    2928                 :             : {
    2929                 :             :     /** Which GraphIndexes ought to occur in m_unlinked, based on m_entries. */
    2930                 :      175346 :     std::set<GraphIndex> expected_unlinked;
    2931                 :             :     /** Which Clusters ought to occur in ClusterSet::m_clusters, based on m_entries. */
    2932         [ +  + ]:      876730 :     std::set<const Cluster*> expected_clusters[MAX_LEVELS];
    2933                 :             :     /** Which GraphIndexes ought to occur in ClusterSet::m_removed, based on m_entries. */
    2934         [ +  + ]:      876730 :     std::set<GraphIndex> expected_removed[MAX_LEVELS];
    2935                 :             :     /** Which Cluster::m_sequence values have been encountered. */
    2936                 :      175346 :     std::set<uint64_t> sequences;
    2937                 :             :     /** Which Clusters are live in ClusterSet::m_clusters up to the level being checked. */
    2938                 :      175346 :     std::set<const Cluster*> live_clusters;
    2939                 :             :     /** Which GraphIndexes ought to occur in m_main_chunkindex, based on m_entries. */
    2940                 :      175346 :     std::set<GraphIndex> expected_chunkindex;
    2941                 :             :     /** Whether compaction is possible in the current state. */
    2942                 :      175346 :     bool compact_possible{true};
    2943                 :             : 
    2944                 :             :     // Go over all Entry objects in m_entries.
    2945   [ -  +  +  + ]:    12654513 :     for (GraphIndex idx = 0; idx < m_entries.size(); ++idx) {
    2946         [ -  + ]:    12479167 :         const auto& entry = m_entries[idx];
    2947         [ -  + ]:    12479167 :         if (entry.m_ref == nullptr) {
    2948                 :             :             // Unlinked Entry must have indexes appear in m_unlinked.
    2949         [ #  # ]:           0 :             expected_unlinked.insert(idx);
    2950                 :             :         } else {
    2951                 :             :             // Every non-unlinked Entry must have a Ref that points back to it.
    2952         [ -  + ]:    12479167 :             assert(GetRefGraph(*entry.m_ref) == this);
    2953         [ -  + ]:    12479167 :             assert(GetRefIndex(*entry.m_ref) == idx);
    2954                 :             :         }
    2955         [ +  + ]:    12479167 :         if (entry.m_main_chunkindex_iterator != m_main_chunkindex.end()) {
    2956                 :             :             // Remember which entries we see a chunkindex entry for.
    2957         [ -  + ]:    12333409 :             assert(entry.m_locator[0].IsPresent());
    2958         [ +  - ]:    12333409 :             expected_chunkindex.insert(idx);
    2959                 :             :         }
    2960                 :             :         // Verify the Entry m_locators.
    2961                 :             :         bool was_present{false}, was_removed{false};
    2962         [ +  + ]:    37437501 :         for (int level = 0; level < MAX_LEVELS; ++level) {
    2963                 :    24958334 :             const auto& locator = entry.m_locator[level];
    2964                 :             :             // Every Locator must be in exactly one of these 3 states.
    2965   [ +  +  +  +  :    74875002 :             assert(locator.IsMissing() + locator.IsRemoved() + locator.IsPresent() == 1);
                   -  + ]
    2966         [ +  + ]:    24958334 :             if (locator.IsPresent()) {
    2967                 :             :                 // Once removed, a transaction cannot be revived.
    2968         [ -  + ]:    12479155 :                 assert(!was_removed);
    2969                 :             :                 // Verify that the Cluster agrees with where the Locator claims the transaction is.
    2970         [ -  + ]:    12479155 :                 assert(locator.cluster->GetClusterEntry(locator.index) == idx);
    2971                 :             :                 // Remember that we expect said Cluster to appear in the ClusterSet::m_clusters.
    2972         [ +  - ]:    12479155 :                 expected_clusters[level].insert(locator.cluster);
    2973                 :             :                 was_present = true;
    2974         [ -  + ]:    24958334 :             } else if (locator.IsRemoved()) {
    2975                 :             :                 // Level 0 (main) cannot have IsRemoved locators (IsMissing there means non-existing).
    2976         [ #  # ]:           0 :                 assert(level > 0);
    2977                 :             :                 // A Locator can only be IsRemoved if it was IsPresent before, and only once.
    2978         [ #  # ]:           0 :                 assert(was_present && !was_removed);
    2979                 :             :                 // Remember that we expect this GraphIndex to occur in the ClusterSet::m_removed.
    2980         [ #  # ]:           0 :                 expected_removed[level].insert(idx);
    2981                 :             :                 was_removed = true;
    2982                 :             :             }
    2983                 :             :         }
    2984                 :             :     }
    2985                 :             : 
    2986                 :             :     // For all levels (0 = main, 1 = staged)...
    2987         [ +  + ]:      350692 :     for (int level = 0; level <= GetTopLevel(); ++level) {
    2988                 :      175346 :         assert(level < MAX_LEVELS);
    2989                 :      175346 :         auto& clusterset = GetClusterSet(level);
    2990                 :      175346 :         std::set<const Cluster*> actual_clusters;
    2991                 :      175346 :         size_t recomputed_cluster_usage{0};
    2992                 :             : 
    2993                 :             :         // For all quality levels...
    2994         [ +  + ]:     1402768 :         for (int qual = 0; qual < int(QualityLevel::NONE); ++qual) {
    2995                 :     1227422 :             QualityLevel quality{qual};
    2996                 :     1227422 :             const auto& quality_clusters = clusterset.m_clusters[qual];
    2997                 :             :             // ... for all clusters in them ...
    2998   [ -  +  +  + ]:    13371437 :             for (ClusterSetIndex setindex = 0; setindex < quality_clusters.size(); ++setindex) {
    2999         [ +  - ]:    12144015 :                 const auto& cluster = *quality_clusters[setindex];
    3000         [ +  - ]:    12144015 :                 live_clusters.insert(&cluster);
    3001                 :             :                 // The number of transactions in a Cluster cannot exceed m_max_cluster_count.
    3002         [ -  + ]:    12144015 :                 assert(cluster.GetTxCount() <= m_max_cluster_count);
    3003                 :             :                 // The level must match the Cluster's own idea of what level it is in (but GetLevel
    3004                 :             :                 // can only be called for non-empty Clusters).
    3005   [ +  +  -  + ]:    12144015 :                 assert(cluster.GetTxCount() == 0 || level == cluster.GetLevel(*this));
    3006                 :             :                 // The sum of their sizes cannot exceed m_max_cluster_size, unless it is an
    3007                 :             :                 // individually oversized transaction singleton. Note that groups of to-be-merged
    3008                 :             :                 // clusters which would exceed this limit are marked oversized, which means they
    3009                 :             :                 // are never applied.
    3010   [ +  +  -  + ]:    12144015 :                 assert(cluster.IsOversized() || cluster.GetTotalTxSize() <= m_max_cluster_size);
    3011                 :             :                 // OVERSIZED clusters are singletons.
    3012   [ +  +  -  + ]:    12144015 :                 assert(!cluster.IsOversized() || cluster.GetTxCount() == 1);
    3013                 :             :                 // Transaction counts cannot exceed the Cluster implementation's maximum
    3014                 :             :                 // supported transactions count.
    3015         [ -  + ]:    12144015 :                 assert(cluster.GetTxCount() <= cluster.GetMaxTxCount());
    3016                 :             :                 // Unless a Split is yet to be applied, the number of transactions must not be
    3017                 :             :                 // below the Cluster implementation's intended transaction count.
    3018         [ +  + ]:    12144015 :                 if (!cluster.NeedsSplitting()) {
    3019         [ -  + ]:    12144003 :                     assert(cluster.GetTxCount() >= cluster.GetMinIntendedTxCount());
    3020                 :             :                 }
    3021                 :             : 
    3022                 :             :                 // Check the sequence number.
    3023         [ -  + ]:    12144015 :                 assert(cluster.m_sequence < m_next_sequence_counter);
    3024         [ -  + ]:    12144015 :                 assert(!sequences.contains(cluster.m_sequence));
    3025         [ +  - ]:    12144015 :                 sequences.insert(cluster.m_sequence);
    3026                 :             :                 // Remember we saw this Cluster (only if it is non-empty; empty Clusters aren't
    3027                 :             :                 // expected to be referenced by the Entry vector).
    3028         [ +  + ]:    12144015 :                 if (cluster.GetTxCount() != 0) {
    3029         [ +  - ]:    12144004 :                     actual_clusters.insert(&cluster);
    3030                 :             :                 }
    3031                 :             :                 // Sanity check the cluster, according to the Cluster's internal rules.
    3032         [ +  - ]:    12144015 :                 cluster.SanityCheck(*this, level);
    3033                 :             :                 // Check that the cluster's quality and setindex matches its position in the quality list.
    3034         [ -  + ]:    12144015 :                 assert(cluster.m_quality == quality);
    3035         [ -  + ]:    12144015 :                 assert(cluster.m_setindex == setindex);
    3036                 :             :                 // Count memory usage.
    3037                 :    12144015 :                 recomputed_cluster_usage += cluster.TotalMemoryUsage();
    3038                 :             :             }
    3039                 :             :         }
    3040                 :             : 
    3041                 :             :         // Verify memory usage.
    3042         [ -  + ]:      175346 :         assert(clusterset.m_cluster_usage == recomputed_cluster_usage);
    3043                 :             : 
    3044                 :             :         // Verify that all to-be-removed transactions have valid identifiers.
    3045         [ +  + ]:      175354 :         for (GraphIndex idx : clusterset.m_to_remove) {
    3046   [ -  +  -  + ]:           8 :             assert(idx < m_entries.size());
    3047                 :             :             // We cannot assert that all m_to_remove transactions are still present: ~Ref on a
    3048                 :             :             // (P,M) transaction (present in main, inherited in staging) will cause an m_to_remove
    3049                 :             :             // addition in both main and staging, but a subsequence ApplyRemovals in main will
    3050                 :             :             // cause it to disappear from staging too, leaving the m_to_remove in place.
    3051                 :             :         }
    3052                 :             : 
    3053                 :             :         // Verify that all to-be-added dependencies have valid identifiers.
    3054   [ -  +  +  + ]:      366762 :         for (auto [par_idx, chl_idx] : clusterset.m_deps_to_add) {
    3055         [ -  + ]:      191416 :             assert(par_idx != chl_idx);
    3056   [ -  +  -  + ]:      191416 :             assert(par_idx < m_entries.size());
    3057         [ -  + ]:      191416 :             assert(chl_idx < m_entries.size());
    3058                 :             :         }
    3059                 :             : 
    3060                 :             :         // Verify that the actually encountered clusters match the ones occurring in Entry vector.
    3061         [ -  + ]:      175346 :         assert(actual_clusters == expected_clusters[level]);
    3062                 :             : 
    3063                 :             :         // Validate m_group_data cluster pointers refer to live clusters at this
    3064                 :             :         // level or below (staging group data may reference not-yet-pulled-in
    3065                 :             :         // main clusters).
    3066         [ +  + ]:      175346 :         if (clusterset.m_group_data.has_value()) {
    3067         [ -  + ]:      175336 :             for (const Cluster* cl : clusterset.m_group_data->m_group_clusters) {
    3068         [ #  # ]:           0 :                 assert(live_clusters.contains(cl));
    3069         [ #  # ]:           0 :                 assert(cl->GetTxCount() > 0);
    3070         [ #  # ]:           0 :                 assert(FindCluster(cl->GetClusterEntry(0), level) == cl);
    3071                 :             :             }
    3072                 :             :         }
    3073                 :             :         // Verify that the contents of m_removed matches what was expected based on the Entry vector.
    3074         [ +  - ]:      175346 :         std::set<GraphIndex> actual_removed(clusterset.m_removed.begin(), clusterset.m_removed.end());
    3075         [ -  + ]:      175346 :         for (auto i : expected_unlinked) {
    3076                 :             :             // If a transaction exists in both main and staging, and is removed from staging (adding
    3077                 :             :             // it to m_removed there), and consequently destroyed (wiping the locator completely),
    3078                 :             :             // it can remain in m_removed despite not having an IsRemoved() locator. Exclude those
    3079                 :             :             // transactions from the comparison here.
    3080                 :           0 :             actual_removed.erase(i);
    3081                 :           0 :             expected_removed[level].erase(i);
    3082                 :             :         }
    3083                 :             : 
    3084         [ -  + ]:      175346 :         assert(actual_removed == expected_removed[level]);
    3085                 :             : 
    3086                 :             :         // If any GraphIndex entries remain in this ClusterSet, compact is not possible.
    3087         [ +  + ]:      175346 :         if (!clusterset.m_deps_to_add.empty()) compact_possible = false;
    3088         [ +  + ]:      175346 :         if (!clusterset.m_to_remove.empty()) compact_possible = false;
    3089         [ -  + ]:      175346 :         if (!clusterset.m_removed.empty()) compact_possible = false;
    3090                 :             : 
    3091                 :             :         // For non-top levels, m_oversized must be known (as it cannot change until the level
    3092                 :             :         // on top is gone).
    3093   [ -  +  -  - ]:      175346 :         if (level < GetTopLevel()) assert(clusterset.m_oversized.has_value());
    3094                 :      175346 :     }
    3095                 :             : 
    3096                 :             :     // Verify that the contents of m_unlinked matches what was expected based on the Entry vector.
    3097         [ +  - ]:      175346 :     std::set<GraphIndex> actual_unlinked(m_unlinked.begin(), m_unlinked.end());
    3098         [ -  + ]:      175346 :     assert(actual_unlinked == expected_unlinked);
    3099                 :             : 
    3100                 :             :     // If compaction was possible, it should have been performed already, and m_unlinked must be
    3101                 :             :     // empty (to prevent memory leaks due to an ever-growing m_entries vector).
    3102         [ +  + ]:      175346 :     if (compact_possible) {
    3103         [ -  + ]:      175338 :         assert(actual_unlinked.empty());
    3104                 :             :     }
    3105                 :             : 
    3106                 :             :     // Finally, check the chunk index.
    3107                 :      175346 :     std::set<GraphIndex> actual_chunkindex;
    3108                 :      175346 :     FeeFrac last_chunk_feerate;
    3109         [ +  + ]:    12508755 :     for (const auto& chunk : m_main_chunkindex) {
    3110                 :    12333409 :         GraphIndex idx = chunk.m_graph_index;
    3111         [ +  - ]:    12333409 :         actual_chunkindex.insert(idx);
    3112         [ +  + ]:    12333409 :         auto chunk_feerate = m_entries[idx].m_main_chunk_feerate;
    3113         [ +  + ]:    12333409 :         if (!last_chunk_feerate.IsEmpty()) {
    3114         [ -  + ]:    12296061 :             assert(ByRatio{last_chunk_feerate} >= ByRatio{FeeFrac{chunk_feerate}});
    3115                 :             :         }
    3116                 :    12333409 :         last_chunk_feerate = chunk_feerate;
    3117                 :             :     }
    3118         [ -  + ]:      175346 :     assert(actual_chunkindex == expected_chunkindex);
    3119   [ +  +  +  +  :     1227422 : }
             -  -  -  - ]
    3120                 :             : 
    3121                 :      182232 : bool TxGraphImpl::DoWork(uint64_t max_cost) noexcept
    3122                 :             : {
    3123                 :      182232 :     uint64_t cost_done{0};
    3124                 :             :     // First linearize everything in NEEDS_RELINEARIZE to an acceptable level. If more budget
    3125                 :             :     // remains after that, try to make everything optimal.
    3126         [ +  + ]:      728928 :     for (QualityLevel quality : {QualityLevel::NEEDS_FIX, QualityLevel::NEEDS_RELINEARIZE, QualityLevel::ACCEPTABLE}) {
    3127                 :             :         // First linearize staging, if it exists, then main.
    3128         [ +  + ]:     1093392 :         for (int level = GetTopLevel(); level >= 0; --level) {
    3129                 :             :             // Do not modify main if it has any observers.
    3130   [ +  -  -  + ]:      546696 :             if (level == 0 && m_main_chunkindex_observers != 0) continue;
    3131                 :      546696 :             ApplyDependencies(level);
    3132                 :      546696 :             auto& clusterset = GetClusterSet(level);
    3133                 :             :             // Do not modify oversized levels.
    3134         [ +  - ]:      546696 :             if (clusterset.m_oversized == true) continue;
    3135                 :      546696 :             auto& queue = clusterset.m_clusters[int(quality)];
    3136         [ +  + ]:      552592 :             while (!queue.empty()) {
    3137         [ +  - ]:        5896 :                 if (cost_done >= max_cost) return false;
    3138                 :             :                 // Randomize the order in which we process, so that if the first cluster somehow
    3139                 :             :                 // needs more work than what max_cost allows, we don't keep spending it on the same
    3140                 :             :                 // one.
    3141         [ -  + ]:        5896 :                 auto pos = m_rng.randrange<size_t>(queue.size());
    3142                 :        5896 :                 auto cost_now = max_cost - cost_done;
    3143         [ +  - ]:        5896 :                 if (quality == QualityLevel::NEEDS_FIX || quality == QualityLevel::NEEDS_RELINEARIZE) {
    3144                 :             :                     // If we're working with clusters that need relinearization still, only perform
    3145                 :             :                     // up to m_acceptable_cost work. If they become ACCEPTABLE, and we still
    3146                 :             :                     // have budget after all other clusters are ACCEPTABLE too, we'll spend the
    3147                 :             :                     // remaining budget on trying to make them OPTIMAL.
    3148         [ -  + ]:        5896 :                     cost_now = std::min(cost_now, m_acceptable_cost);
    3149                 :             :                 }
    3150         [ +  - ]:        5896 :                 auto [cost, improved] = queue[pos].get()->Relinearize(*this, level, cost_now);
    3151                 :        5896 :                 cost_done += cost;
    3152                 :             :                 // If no improvement was made to the Cluster, it means we've essentially run out of
    3153                 :             :                 // budget. Even though it may be the case that cost_done < max_cost still, the
    3154                 :             :                 // linearizer decided there wasn't enough budget left to attempt anything with.
    3155                 :             :                 // To avoid an infinite loop that keeps trying clusters with minuscule budgets,
    3156                 :             :                 // stop here too.
    3157         [ +  - ]:        5896 :                 if (!improved) return false;
    3158                 :             :             }
    3159                 :             :         }
    3160                 :             :     }
    3161                 :             :     // All possible work has been performed, so we can return true. Note that this does *not* mean
    3162                 :             :     // that all clusters are optimally linearized now. It may be that there is nothing to do left
    3163                 :             :     // because all non-optimal clusters are in oversized and/or observer-bearing levels.
    3164                 :             :     return true;
    3165                 :             : }
    3166                 :             : 
    3167                 :    12235756 : void BlockBuilderImpl::Next() noexcept
    3168                 :             : {
    3169                 :             :     // Don't do anything if we're already done.
    3170         [ +  - ]:    12235756 :     if (m_cur_iter == m_graph->m_main_chunkindex.end()) return;
    3171                 :    12235769 :     while (true) {
    3172                 :             :         // Advance the pointer, and stop if we reach the end.
    3173         [ +  + ]:    12235769 :         ++m_cur_iter;
    3174                 :    12235769 :         m_cur_cluster = nullptr;
    3175         [ +  + ]:    12235769 :         if (m_cur_iter == m_graph->m_main_chunkindex.end()) break;
    3176                 :             :         // Find the cluster pointed to by m_cur_iter.
    3177                 :    12197007 :         const auto& chunk_data = *m_cur_iter;
    3178                 :    12197007 :         const auto& chunk_end_entry = m_graph->m_entries[chunk_data.m_graph_index];
    3179                 :    12197007 :         m_cur_cluster = chunk_end_entry.m_locator[0].cluster;
    3180                 :    12197007 :         m_known_end_of_cluster = false;
    3181                 :             :         // If we previously skipped a chunk from this cluster we cannot include more from it.
    3182         [ +  + ]:    12197007 :         if (!m_excluded_clusters.contains(m_cur_cluster->m_sequence)) break;
    3183                 :             :     }
    3184                 :             : }
    3185                 :             : 
    3186                 :    12450165 : std::optional<std::pair<std::vector<TxGraph::Ref*>, FeePerWeight>> BlockBuilderImpl::GetCurrentChunk() noexcept
    3187                 :             : {
    3188                 :    12450165 :     std::optional<std::pair<std::vector<TxGraph::Ref*>, FeePerWeight>> ret;
    3189                 :             :     // Populate the return value if we are not done.
    3190         [ +  + ]:    12450165 :     if (m_cur_iter != m_graph->m_main_chunkindex.end()) {
    3191                 :    12235802 :         ret.emplace();
    3192         [ +  + ]:    12235802 :         const auto& chunk_data = *m_cur_iter;
    3193         [ +  + ]:    12235802 :         const auto& chunk_end_entry = m_graph->m_entries[chunk_data.m_graph_index];
    3194         [ +  + ]:    12235802 :         if (chunk_data.m_chunk_count == LinearizationIndex(-1)) {
    3195                 :             :             // Special case in case just a single transaction remains, avoiding the need to
    3196                 :             :             // dispatch to and dereference Cluster.
    3197                 :    12031515 :             ret->first.resize(1);
    3198                 :    12031515 :             Assume(chunk_end_entry.m_ref != nullptr);
    3199                 :    12031515 :             ret->first[0] = chunk_end_entry.m_ref;
    3200                 :    12031515 :             m_known_end_of_cluster = true;
    3201                 :             :         } else {
    3202                 :      204287 :             Assume(m_cur_cluster);
    3203                 :      204287 :             ret->first.resize(chunk_data.m_chunk_count);
    3204                 :      204287 :             auto start_pos = chunk_end_entry.m_main_lin_index + 1 - chunk_data.m_chunk_count;
    3205         [ -  + ]:      204287 :             m_known_end_of_cluster = m_cur_cluster->GetClusterRefs(*m_graph, ret->first, start_pos);
    3206                 :             :             // If the chunk size was 1 and at end of cluster, then the special case above should
    3207                 :             :             // have been used.
    3208                 :      204287 :             Assume(!m_known_end_of_cluster || chunk_data.m_chunk_count > 1);
    3209                 :             :         }
    3210                 :    12235802 :         ret->second = chunk_end_entry.m_main_chunk_feerate;
    3211                 :             :     }
    3212                 :    12450165 :     return ret;
    3213                 :             : }
    3214                 :             : 
    3215                 :      214430 : BlockBuilderImpl::BlockBuilderImpl(TxGraphImpl& graph) noexcept : m_graph(&graph)
    3216                 :             : {
    3217                 :             :     // Make sure all clusters in main are up to date, and acceptable.
    3218                 :      214430 :     m_graph->MakeAllAcceptable(0);
    3219                 :             :     // There cannot remain any inapplicable dependencies (only possible if main is oversized).
    3220         [ +  + ]:      214430 :     Assume(m_graph->m_main_clusterset.m_deps_to_add.empty());
    3221                 :             :     // Remember that this object is observing the graph's index, so that we can detect concurrent
    3222                 :             :     // modifications.
    3223                 :      214430 :     ++m_graph->m_main_chunkindex_observers;
    3224                 :             :     // Find the first chunk.
    3225         [ +  + ]:      214430 :     m_cur_iter = m_graph->m_main_chunkindex.begin();
    3226                 :      214430 :     m_cur_cluster = nullptr;
    3227         [ +  + ]:      214430 :     if (m_cur_iter != m_graph->m_main_chunkindex.end()) {
    3228                 :             :         // Find the cluster pointed to by m_cur_iter.
    3229                 :       38829 :         const auto& chunk_data = *m_cur_iter;
    3230                 :       38829 :         const auto& chunk_end_entry = m_graph->m_entries[chunk_data.m_graph_index];
    3231                 :       38829 :         m_cur_cluster = chunk_end_entry.m_locator[0].cluster;
    3232                 :             :     }
    3233                 :      214430 : }
    3234                 :             : 
    3235                 :      428860 : BlockBuilderImpl::~BlockBuilderImpl()
    3236                 :             : {
    3237                 :      214430 :     Assume(m_graph->m_main_chunkindex_observers > 0);
    3238                 :             :     // Permit modifications to the main graph again after destroying the BlockBuilderImpl.
    3239                 :      214430 :     --m_graph->m_main_chunkindex_observers;
    3240                 :      428860 : }
    3241                 :             : 
    3242                 :    12191864 : void BlockBuilderImpl::Include() noexcept
    3243                 :             : {
    3244                 :             :     // The actual inclusion of the chunk is done by the calling code. All we have to do is switch
    3245                 :             :     // to the next chunk.
    3246                 :    12191864 :     Next();
    3247                 :    12191864 : }
    3248                 :             : 
    3249                 :       43892 : void BlockBuilderImpl::Skip() noexcept
    3250                 :             : {
    3251                 :             :     // When skipping a chunk we need to not include anything more of the cluster, as that could make
    3252                 :             :     // the result topologically invalid. However, don't do this if the chunk is known to be the last
    3253                 :             :     // chunk of the cluster. This may significantly reduce the size of m_excluded_clusters,
    3254                 :             :     // especially when many singleton clusters are ignored.
    3255   [ +  -  +  + ]:       43892 :     if (m_cur_cluster != nullptr && !m_known_end_of_cluster) {
    3256                 :           1 :         m_excluded_clusters.insert(m_cur_cluster->m_sequence);
    3257                 :             :     }
    3258                 :       43892 :     Next();
    3259                 :       43892 : }
    3260                 :             : 
    3261                 :      214430 : std::unique_ptr<TxGraph::BlockBuilder> TxGraphImpl::GetBlockBuilder() noexcept
    3262                 :             : {
    3263         [ -  + ]:      214430 :     return std::make_unique<BlockBuilderImpl>(*this);
    3264                 :             : }
    3265                 :             : 
    3266                 :          53 : std::pair<std::vector<TxGraph::Ref*>, FeePerWeight> TxGraphImpl::GetWorstMainChunk() noexcept
    3267                 :             : {
    3268                 :          53 :     std::pair<std::vector<Ref*>, FeePerWeight> ret;
    3269                 :             :     // Make sure all clusters in main are up to date, and acceptable.
    3270                 :          53 :     MakeAllAcceptable(0);
    3271         [ +  - ]:          53 :     Assume(m_main_clusterset.m_deps_to_add.empty());
    3272                 :             :     // If the graph is not empty, populate ret.
    3273         [ +  - ]:          53 :     if (!m_main_chunkindex.empty()) {
    3274         [ +  + ]:          53 :         const auto& chunk_data = *m_main_chunkindex.rbegin();
    3275         [ +  + ]:          53 :         const auto& chunk_end_entry = m_entries[chunk_data.m_graph_index];
    3276                 :          53 :         Cluster* cluster = chunk_end_entry.m_locator[0].cluster;
    3277         [ +  + ]:          53 :         if (chunk_data.m_chunk_count == LinearizationIndex(-1) || chunk_data.m_chunk_count == 1)  {
    3278                 :             :             // Special case for singletons.
    3279                 :          47 :             ret.first.resize(1);
    3280                 :          47 :             Assume(chunk_end_entry.m_ref != nullptr);
    3281                 :          47 :             ret.first[0] = chunk_end_entry.m_ref;
    3282                 :             :         } else {
    3283                 :           6 :             ret.first.resize(chunk_data.m_chunk_count);
    3284                 :           6 :             auto start_pos = chunk_end_entry.m_main_lin_index + 1 - chunk_data.m_chunk_count;
    3285         [ -  + ]:           6 :             cluster->GetClusterRefs(*this, ret.first, start_pos);
    3286                 :           6 :             std::reverse(ret.first.begin(), ret.first.end());
    3287                 :             :         }
    3288                 :          53 :         ret.second = chunk_end_entry.m_main_chunk_feerate;
    3289                 :             :     }
    3290                 :          53 :     return ret;
    3291                 :             : }
    3292                 :             : 
    3293                 :        2917 : std::vector<TxGraph::Ref*> TxGraphImpl::Trim() noexcept
    3294                 :             : {
    3295         [ +  + ]:        2917 :     int level = GetTopLevel();
    3296         [ +  + ]:        2917 :     Assume(m_main_chunkindex_observers == 0 || level != 0);
    3297                 :        2917 :     std::vector<TxGraph::Ref*> ret;
    3298                 :             : 
    3299                 :             :     // Compute the groups of to-be-merged Clusters (which also applies all removals, and splits).
    3300                 :        2917 :     auto& clusterset = GetClusterSet(level);
    3301         [ +  + ]:        2917 :     if (clusterset.m_oversized == false) return ret;
    3302                 :          32 :     GroupClusters(level);
    3303         [ +  - ]:          32 :     Assume(clusterset.m_group_data.has_value());
    3304                 :             :     // Nothing to do if not oversized.
    3305                 :          32 :     Assume(clusterset.m_oversized.has_value());
    3306         [ +  - ]:          32 :     if (clusterset.m_oversized == false) return ret;
    3307                 :             : 
    3308                 :             :     // In this function, would-be clusters (as precomputed in m_group_data by GroupClusters) are
    3309                 :             :     // trimmed by removing transactions in them such that the resulting clusters satisfy the size
    3310                 :             :     // and count limits.
    3311                 :             :     //
    3312                 :             :     // It works by defining for each would-be cluster a rudimentary linearization: at every point
    3313                 :             :     // the highest-chunk-feerate remaining transaction is picked among those with no unmet
    3314                 :             :     // dependencies. "Dependency" here means either a to-be-added dependency (m_deps_to_add), or
    3315                 :             :     // an implicit dependency added between any two consecutive transaction in their current
    3316                 :             :     // cluster linearization. So it can be seen as a "merge sort" of the chunks of the clusters,
    3317                 :             :     // but respecting the dependencies being added.
    3318                 :             :     //
    3319                 :             :     // This rudimentary linearization is computed lazily, by putting all eligible (no unmet
    3320                 :             :     // dependencies) transactions in a heap, and popping the highest-feerate one from it. Along the
    3321                 :             :     // way, the counts and sizes of the would-be clusters up to that point are tracked (by
    3322                 :             :     // partitioning the involved transactions using a union-find structure). Any transaction whose
    3323                 :             :     // addition would cause a violation is removed, along with all their descendants.
    3324                 :             :     //
    3325                 :             :     // A next invocation of GroupClusters (after applying the removals) will compute the new
    3326                 :             :     // resulting clusters, and none of them will violate the limits.
    3327                 :             : 
    3328                 :             :     /** All dependencies (both to be added ones, and implicit ones between consecutive transactions
    3329                 :             :      *  in existing cluster linearizations), sorted by parent. */
    3330                 :           4 :     std::vector<std::pair<GraphIndex, GraphIndex>> deps_by_parent;
    3331                 :             :     /** Same, but sorted by child. */
    3332                 :           4 :     std::vector<std::pair<GraphIndex, GraphIndex>> deps_by_child;
    3333                 :             :     /** Information about all transactions involved in a Cluster group to be trimmed, sorted by
    3334                 :             :      *  GraphIndex. It contains entries both for transactions that have already been included,
    3335                 :             :      *  and ones that have not yet been. */
    3336                 :           4 :     std::vector<TrimTxData> trim_data;
    3337                 :             :     /** Iterators into trim_data, treated as a max heap according to cmp_fn below. Each entry is
    3338                 :             :      *  a transaction that has not yet been included yet, but all its ancestors have. */
    3339                 :           4 :     std::vector<std::vector<TrimTxData>::iterator> trim_heap;
    3340                 :             :     /** The list of representatives of the partitions a given transaction depends on. */
    3341                 :           4 :     std::vector<TrimTxData*> current_deps;
    3342                 :             : 
    3343                 :             :     /** Function to define the ordering of trim_heap. */
    3344                 :     1084529 :     static constexpr auto cmp_fn = [](auto a, auto b) noexcept {
    3345                 :             :         // Sort by increasing chunk feerate, and then by decreasing size.
    3346                 :             :         // We do not need to sort by cluster or within clusters, because due to the implicit
    3347                 :             :         // dependency between consecutive linearization elements, no two transactions from the
    3348                 :             :         // same Cluster will ever simultaneously be in the heap.
    3349                 :     1084525 :         return ByRatioNegSize{a->m_chunk_feerate} < ByRatioNegSize{b->m_chunk_feerate};
    3350                 :             :     };
    3351                 :             : 
    3352                 :             :     /** Given a TrimTxData entry, find the representative of the partition it is in. */
    3353                 :      127308 :     static constexpr auto find_fn = [](TrimTxData* arg) noexcept {
    3354   [ +  +  -  + ]:      189351 :         while (arg != arg->m_uf_parent) {
    3355                 :             :             // Replace pointer to parent with pointer to grandparent (path splitting).
    3356                 :             :             // See https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Finding_set_representatives.
    3357                 :       62047 :             auto par = arg->m_uf_parent;
    3358                 :       62047 :             arg->m_uf_parent = par->m_uf_parent;
    3359                 :       62047 :             arg = par;
    3360                 :             :         }
    3361                 :      127304 :         return arg;
    3362                 :             :     };
    3363                 :             : 
    3364                 :             :     /** Given two TrimTxData entries, union the partitions they are in, and return the
    3365                 :             :      *  representative. */
    3366                 :       63100 :     static constexpr auto union_fn = [](TrimTxData* arg1, TrimTxData* arg2) noexcept {
    3367                 :             :         // Replace arg1 and arg2 by their representatives.
    3368         [ -  + ]:      126192 :         auto rep1 = find_fn(arg1);
    3369                 :       63096 :         auto rep2 = find_fn(arg2);
    3370                 :             :         // Bail out if both representatives are the same, because that means arg1 and arg2 are in
    3371                 :             :         // the same partition already.
    3372         [ +  - ]:       63096 :         if (rep1 == rep2) return rep1;
    3373                 :             :         // Pick the lower-count root to become a child of the higher-count one.
    3374                 :             :         // See https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Union_by_size.
    3375         [ +  + ]:       63096 :         if (rep1->m_uf_count < rep2->m_uf_count) std::swap(rep1, rep2);
    3376                 :       63096 :         rep2->m_uf_parent = rep1;
    3377                 :             :         // Add the statistics of arg2 (which is no longer a representative) to those of arg1 (which
    3378                 :             :         // is now the representative for both).
    3379                 :       63096 :         rep1->m_uf_size += rep2->m_uf_size;
    3380                 :       63096 :         rep1->m_uf_count += rep2->m_uf_count;
    3381                 :       63096 :         return rep1;
    3382                 :             :     };
    3383                 :             : 
    3384                 :             :     /** Get iterator to TrimTxData entry for a given index. */
    3385                 :      128420 :     auto locate_fn = [&](GraphIndex index) noexcept {
    3386                 :      128416 :         auto it = std::lower_bound(trim_data.begin(), trim_data.end(), index, [](TrimTxData& elem, GraphIndex idx) noexcept {
    3387         [ +  + ]:     2048000 :             return elem.m_index < idx;
    3388                 :             :         });
    3389         [ +  - ]:      128416 :         Assume(it != trim_data.end() && it->m_index == index);
    3390                 :      128416 :         return it;
    3391                 :           4 :     };
    3392                 :             : 
    3393                 :             :     // For each group of to-be-merged Clusters.
    3394         [ +  + ]:          13 :     for (const auto& group_data : clusterset.m_group_data->m_groups) {
    3395         [ +  + ]:           9 :         trim_data.clear();
    3396         [ -  + ]:           9 :         trim_heap.clear();
    3397         [ -  + ]:           9 :         deps_by_child.clear();
    3398         [ -  + ]:           9 :         deps_by_parent.clear();
    3399                 :             : 
    3400                 :             :         // Gather trim data and implicit dependency data from all involved Clusters.
    3401         [ -  + ]:           9 :         auto cluster_span = std::span{clusterset.m_group_data->m_group_clusters}
    3402                 :           9 :                                 .subspan(group_data.m_cluster_offset, group_data.m_cluster_count);
    3403                 :           9 :         uint64_t size{0};
    3404         [ +  + ]:       64226 :         for (Cluster* cluster : cluster_span) {
    3405                 :       64217 :             MakeAcceptable(*cluster, cluster->GetLevel(*this));
    3406                 :       64217 :             size += cluster->AppendTrimData(trim_data, deps_by_child);
    3407                 :             :         }
    3408                 :             :         // If this group of Clusters does not violate any limits, continue to the next group.
    3409   [ -  +  +  +  :           9 :         if (trim_data.size() <= m_max_cluster_count && size <= m_max_cluster_size) continue;
                   +  - ]
    3410                 :             :         // Sort the trim data by GraphIndex. In what follows, we will treat this sorted vector as
    3411                 :             :         // a map from GraphIndex to TrimTxData via locate_fn, and its ordering will not change
    3412                 :             :         // anymore.
    3413   [ +  +  +  +  :     1315115 :         std::ranges::sort(trim_data, [](auto& a, auto& b) noexcept { return a.m_index < b.m_index; });
          +  +  +  +  +  
          +  +  +  +  +  
          +  +  +  +  +  
             +  -  -  +  
                      + ]
    3414                 :             : 
    3415                 :             :         // Add the explicitly added dependencies to deps_by_child.
    3416                 :           9 :         deps_by_child.insert(deps_by_child.end(),
    3417                 :           9 :                              clusterset.m_deps_to_add.begin() + group_data.m_deps_offset,
    3418                 :           9 :                              clusterset.m_deps_to_add.begin() + group_data.m_deps_offset + group_data.m_deps_count);
    3419                 :             : 
    3420                 :             :         // Sort deps_by_child by child transaction GraphIndex. The order will not be changed
    3421                 :             :         // anymore after this.
    3422   [ +  +  +  +  :     1453049 :         std::ranges::sort(deps_by_child, [](auto& a, auto& b) noexcept { return a.second < b.second; });
          +  +  +  +  +  
          +  +  +  +  +  
          +  +  +  +  +  
             +  -  -  +  
                      + ]
    3423                 :             :         // Fill m_parents_count and m_parents_offset in trim_data, as well as m_deps_left, and
    3424                 :             :         // initially populate trim_heap. Because of the sort above, all dependencies involving the
    3425                 :             :         // same child are grouped together, so a single linear scan suffices.
    3426                 :           9 :         auto deps_it = deps_by_child.begin();
    3427         [ +  + ]:       64226 :         for (auto trim_it = trim_data.begin(); trim_it != trim_data.end(); ++trim_it) {
    3428                 :       64217 :             trim_it->m_parent_offset = deps_it - deps_by_child.begin();
    3429                 :       64217 :             trim_it->m_deps_left = 0;
    3430   [ +  +  +  + ]:      128425 :             while (deps_it != deps_by_child.end() && deps_it->second == trim_it->m_index) {
    3431                 :       64208 :                 ++trim_it->m_deps_left;
    3432                 :       64208 :                 ++deps_it;
    3433                 :             :             }
    3434                 :       64217 :             trim_it->m_parent_count = trim_it->m_deps_left;
    3435                 :             :             // If this transaction has no unmet dependencies, and is not oversized, add it to the
    3436                 :             :             // heap (just append for now, the heapification happens below).
    3437   [ +  +  +  + ]:       64217 :             if (trim_it->m_deps_left == 0 && trim_it->m_tx_size <= m_max_cluster_size) {
    3438                 :        1150 :                 trim_heap.push_back(trim_it);
    3439                 :             :             }
    3440                 :             :         }
    3441                 :           9 :         Assume(deps_it == deps_by_child.end());
    3442                 :             : 
    3443                 :             :         // Construct deps_by_parent, sorted by parent transaction GraphIndex. The order will not be
    3444                 :             :         // changed anymore after this.
    3445                 :           9 :         deps_by_parent = deps_by_child;
    3446   [ +  +  +  +  :     1748590 :         std::ranges::sort(deps_by_parent, [](auto& a, auto& b) noexcept { return a.first < b.first; });
          +  +  +  +  +  
          +  +  +  +  +  
          +  +  +  +  +  
             +  -  -  +  
                      + ]
    3447                 :             :         // Fill m_children_offset and m_children_count in trim_data. Because of the sort above, all
    3448                 :             :         // dependencies involving the same parent are grouped together, so a single linear scan
    3449                 :             :         // suffices.
    3450                 :           9 :         deps_it = deps_by_parent.begin();
    3451         [ +  + ]:       64226 :         for (auto& trim_entry : trim_data) {
    3452                 :       64217 :             trim_entry.m_children_count = 0;
    3453                 :       64217 :             trim_entry.m_children_offset = deps_it - deps_by_parent.begin();
    3454   [ +  +  +  + ]:      128425 :             while (deps_it != deps_by_parent.end() && deps_it->first == trim_entry.m_index) {
    3455                 :       64208 :                 ++trim_entry.m_children_count;
    3456                 :       64208 :                 ++deps_it;
    3457                 :             :             }
    3458                 :             :         }
    3459                 :           9 :         Assume(deps_it == deps_by_parent.end());
    3460                 :             : 
    3461                 :             :         // Build a heap of all transactions with 0 unmet dependencies.
    3462                 :           9 :         std::make_heap(trim_heap.begin(), trim_heap.end(), cmp_fn);
    3463                 :             : 
    3464                 :             :         // Iterate over to-be-included transactions, and convert them to included transactions, or
    3465                 :             :         // skip them if adding them would violate resource limits of the would-be cluster.
    3466                 :             :         //
    3467                 :             :         // It is possible that the heap empties without ever hitting either cluster limit, in case
    3468                 :             :         // the implied graph (to be added dependencies plus implicit dependency between each
    3469                 :             :         // original transaction and its predecessor in the linearization it came from) contains
    3470                 :             :         // cycles. Such cycles will be removed entirely, because each of the transactions in the
    3471                 :             :         // cycle permanently have unmet dependencies. However, this cannot occur in real scenarios
    3472                 :             :         // where Trim() is called to deal with reorganizations that would violate cluster limits,
    3473                 :             :         // as all added dependencies are in the same direction (from old mempool transactions to
    3474                 :             :         // new from-block transactions); cycles require dependencies in both directions to be
    3475                 :             :         // added.
    3476         [ +  + ]:       64229 :         while (!trim_heap.empty()) {
    3477                 :             :             // Move the best remaining transaction to the end of trim_heap.
    3478                 :       64211 :             std::pop_heap(trim_heap.begin(), trim_heap.end(), cmp_fn);
    3479                 :             :             // Pop it, and find its TrimTxData.
    3480         [ +  + ]:       64211 :             auto& entry = *trim_heap.back();
    3481         [ +  + ]:       64211 :             trim_heap.pop_back();
    3482                 :             : 
    3483                 :             :             // Initialize it as a singleton partition.
    3484                 :       64211 :             entry.m_uf_parent = &entry;
    3485                 :       64211 :             entry.m_uf_count = 1;
    3486                 :       64211 :             entry.m_uf_size = entry.m_tx_size;
    3487                 :             : 
    3488                 :             :             // Find the distinct transaction partitions this entry depends on.
    3489         [ +  + ]:       64211 :             current_deps.clear();
    3490   [ -  +  +  + ]:      128419 :             for (auto& [par, chl] : std::span{deps_by_child}.subspan(entry.m_parent_offset, entry.m_parent_count)) {
    3491                 :       64208 :                 Assume(chl == entry.m_index);
    3492                 :      128416 :                 current_deps.push_back(find_fn(&*locate_fn(par)));
    3493                 :             :             }
    3494                 :       64211 :             std::ranges::sort(current_deps);
    3495                 :       64211 :             current_deps.erase(std::ranges::unique(current_deps).begin(), current_deps.end());
    3496                 :             : 
    3497                 :             :             // Compute resource counts.
    3498                 :       64211 :             uint32_t new_count = 1;
    3499                 :       64211 :             uint64_t new_size = entry.m_tx_size;
    3500         [ +  + ]:      128419 :             for (TrimTxData* ptr : current_deps) {
    3501                 :       64208 :                 new_count += ptr->m_uf_count;
    3502                 :       64208 :                 new_size += ptr->m_uf_size;
    3503                 :             :             }
    3504                 :             :             // Skip the entry if this would violate any limit.
    3505   [ +  +  -  + ]:       64211 :             if (new_count > m_max_cluster_count || new_size > m_max_cluster_size) continue;
    3506                 :             : 
    3507                 :             :             // Union the partitions this transaction and all its dependencies are in together.
    3508                 :       64198 :             auto rep = &entry;
    3509         [ +  + ]:      127294 :             for (TrimTxData* ptr : current_deps) rep = union_fn(ptr, rep);
    3510                 :             :             // Mark the entry as included (so the loop below will not remove the transaction).
    3511                 :       64198 :             entry.m_deps_left = uint32_t(-1);
    3512                 :             :             // Mark each to-be-added dependency involving this transaction as parent satisfied.
    3513   [ -  +  +  + ]:      128406 :             for (auto& [par, chl] : std::span{deps_by_parent}.subspan(entry.m_children_offset, entry.m_children_count)) {
    3514                 :       64208 :                 Assume(par == entry.m_index);
    3515                 :       64208 :                 auto chl_it = locate_fn(chl);
    3516                 :             :                 // Reduce the number of unmet dependencies of chl_it, and if that brings the number
    3517                 :             :                 // to zero, add it to the heap of includable transactions.
    3518         [ +  + ]:       64208 :                 Assume(chl_it->m_deps_left > 0);
    3519         [ +  + ]:       64208 :                 if (--chl_it->m_deps_left == 0) {
    3520                 :       63061 :                     trim_heap.push_back(chl_it);
    3521                 :       63061 :                     std::push_heap(trim_heap.begin(), trim_heap.end(), cmp_fn);
    3522                 :             :                 }
    3523                 :             :             }
    3524                 :             :         }
    3525                 :             : 
    3526                 :             :         // Remove all the transactions that were not processed above. Because nothing gets
    3527                 :             :         // processed until/unless all its dependencies are met, this automatically guarantees
    3528                 :             :         // that if a transaction is removed, all its descendants, or would-be descendants, are
    3529                 :             :         // removed as well.
    3530         [ +  + ]:       64226 :         for (const auto& trim_entry : trim_data) {
    3531         [ +  + ]:       64217 :             if (trim_entry.m_deps_left != uint32_t(-1)) {
    3532                 :          19 :                 ret.push_back(m_entries[trim_entry.m_index].m_ref);
    3533                 :          19 :                 clusterset.m_to_remove.push_back(trim_entry.m_index);
    3534                 :             :             }
    3535                 :             :         }
    3536                 :             :     }
    3537         [ +  - ]:           4 :     clusterset.m_group_data.reset();
    3538                 :           4 :     clusterset.m_oversized = false;
    3539                 :           4 :     Assume(!ret.empty());
    3540                 :           4 :     return ret;
    3541                 :           4 : }
    3542                 :             : 
    3543                 :      553683 : size_t TxGraphImpl::GetMainMemoryUsage() noexcept
    3544                 :             : {
    3545                 :             :     // Make sure splits/merges are applied, as memory usage may not be representative otherwise.
    3546                 :      553683 :     SplitAll(/*up_to_level=*/0);
    3547                 :      553683 :     ApplyDependencies(/*level=*/0);
    3548                 :             :     // Compute memory usage
    3549                 :      553683 :     size_t usage = /* From clusters */
    3550                 :      553683 :                    m_main_clusterset.m_cluster_usage +
    3551                 :             :                    /* From Entry objects. */
    3552                 :      553683 :                    sizeof(Entry) * m_main_clusterset.m_txcount +
    3553                 :             :                    /* From the chunk index. */
    3554                 :      553683 :                    memusage::DynamicUsage(m_main_chunkindex);
    3555                 :      553683 :     return usage;
    3556                 :             : }
    3557                 :             : 
    3558                 :             : } // namespace
    3559                 :             : 
    3560                 :      410992 : TxGraph::Ref::~Ref()
    3561                 :             : {
    3562         [ +  + ]:      410992 :     if (m_graph) {
    3563                 :             :         // Inform the TxGraph about the Ref being destroyed.
    3564                 :       72073 :         m_graph->UnlinkRef(m_index);
    3565                 :       72073 :         m_graph = nullptr;
    3566                 :             :     }
    3567                 :      410992 : }
    3568                 :             : 
    3569                 :       74161 : TxGraph::Ref::Ref(Ref&& other) noexcept
    3570                 :             : {
    3571                 :             :     // Inform the TxGraph of other that its Ref is being moved.
    3572         [ +  + ]:       74161 :     if (other.m_graph) other.m_graph->UpdateRef(other.m_index, *this);
    3573                 :             :     // Actually move the contents.
    3574                 :       74161 :     std::swap(m_graph, other.m_graph);
    3575                 :       74161 :     std::swap(m_index, other.m_index);
    3576                 :       74161 : }
    3577                 :             : 
    3578                 :        1413 : std::unique_ptr<TxGraph> MakeTxGraph(
    3579                 :             :     unsigned max_cluster_count,
    3580                 :             :     uint64_t max_cluster_size,
    3581                 :             :     uint64_t acceptable_cost,
    3582                 :             :     const std::function<std::strong_ordering(const TxGraph::Ref&, const TxGraph::Ref&)>& fallback_order) noexcept
    3583                 :             : {
    3584         [ -  + ]:        1413 :     return std::make_unique<TxGraphImpl>(
    3585                 :             :         /*max_cluster_count=*/max_cluster_count,
    3586                 :             :         /*max_cluster_size=*/max_cluster_size,
    3587                 :             :         /*acceptable_cost=*/acceptable_cost,
    3588         [ -  + ]:        1413 :         /*fallback_order=*/fallback_order);
    3589                 :             : }
        

Generated by: LCOV version 2.0-1