// Copyright (c) The Bitcoin Core developers

// Distributed under the MIT software license, see the accompanying

// file COPYING or http://www.opensource.org/licenses/mit-license.php.

#include <txgraph.h>

#include <cluster_linearize.h>

#include <random.h>

#include <util/bitset.h>

#include <util/check.h>

#include <util/feefrac.h>

#include <util/vector.h>

#include <compare>

#include <functional>

#include <memory>

#include <ranges>

#include <set>

#include <span>

#include <unordered_set>

#include <utility>

namespace {

using namespace cluster_linearize;

/** The maximum number of levels a TxGraph can have (0 = main, 1 = staging). */

static constexpr int MAX_LEVELS{2};

// Forward declare the TxGraph implementation class.

class TxGraphImpl;

/** Position of a DepGraphIndex within a Cluster::m_linearization. */

using LinearizationIndex = uint32_t;

/** Position of a Cluster within TxGraphImpl::ClusterSet::m_clusters. */

using ClusterSetIndex = uint32_t;

/** Quality levels for cached cluster linearizations. */

enum class QualityLevel

{

    /** This is a singleton cluster consisting of a transaction that individually exceeds the

     *  cluster size limit. It cannot be merged with anything. */

    OVERSIZED_SINGLETON,

    /** This cluster may have multiple disconnected components, which are all NEEDS_FIX. */

    NEEDS_SPLIT_FIX,

    /** This cluster may have multiple disconnected components, which are all NEEDS_RELINEARIZE. */

    NEEDS_SPLIT,

    /** This cluster may be non-topological. */

    NEEDS_FIX,

    /** This cluster has undergone changes that warrant re-linearization. */

    NEEDS_RELINEARIZE,

    /** The minimal level of linearization has been performed, but it is not known to be optimal. */

    ACCEPTABLE,

    /** The linearization is known to be optimal. */

    OPTIMAL,

    /** This cluster is not registered in any ClusterSet::m_clusters.

     *  This must be the last entry in QualityLevel as ClusterSet::m_clusters is sized using it. */

    NONE,

};

/** Information about a transaction inside TxGraphImpl::Trim. */

struct TrimTxData

{

    // Fields populated by Cluster::AppendTrimData(). These are immutable after TrimTxData

    // construction.

    /** Chunk feerate for this transaction. */

    FeePerWeight m_chunk_feerate;

    /** GraphIndex of the transaction. */

    TxGraph::GraphIndex m_index;

    /** Size of the transaction. */

    uint32_t m_tx_size;

    // Fields only used internally by TxGraphImpl::Trim():

    /** Number of unmet dependencies this transaction has. -1 if the transaction is included. */

    uint32_t m_deps_left;

    /** Number of dependencies that apply to this transaction as child. */

    uint32_t m_parent_count;

    /** Where in deps_by_child those dependencies begin. */

    uint32_t m_parent_offset;

    /** Number of dependencies that apply to this transaction as parent. */

    uint32_t m_children_count;

    /** Where in deps_by_parent those dependencies begin. */

    uint32_t m_children_offset;

    // Fields only used internally by TxGraphImpl::Trim()'s union-find implementation, and only for

    // transactions that are definitely included or definitely rejected.

    //

    // As transactions get processed, they get organized into trees which form partitions

    // representing the would-be clusters up to that point. The root of each tree is a

    // representative for that partition. See

    // https://en.wikipedia.org/wiki/Disjoint-set_data_structure.

    //

    /** Pointer to another TrimTxData, towards the root of the tree. If this is a root, m_uf_parent

     *  is equal to this itself. */

    TrimTxData* m_uf_parent;

    /** If this is a root, the total number of transactions in the partition. */

    uint32_t m_uf_count;

    /** If this is a root, the total size of transactions in the partition. */

    uint64_t m_uf_size;

};

/** A grouping of connected transactions inside a TxGraphImpl::ClusterSet. */

class Cluster

{

    friend class TxGraphImpl;

    friend class BlockBuilderImpl;

protected:

    using GraphIndex = TxGraph::GraphIndex;

    using SetType = BitSet<MAX_CLUSTER_COUNT_LIMIT>;

    /** The quality level of m_linearization. */

    QualityLevel m_quality{QualityLevel::NONE};

    /** Which position this Cluster has in TxGraphImpl::ClusterSet::m_clusters[m_quality]. */

    ClusterSetIndex m_setindex{ClusterSetIndex(-1)};

    /** Sequence number for this Cluster (for tie-breaking comparison between equal-chunk-feerate

        transactions in distinct clusters). */

    uint64_t m_sequence;

    explicit Cluster(uint64_t sequence) noexcept : m_sequence(sequence) {}

public:

    // Provide virtual destructor, for safe polymorphic usage inside std::unique_ptr.

    virtual ~Cluster() = default;

    // Cannot move or copy (would invalidate Cluster* in Locator and ClusterSet). */

    Cluster(const Cluster&) = delete;

    Cluster& operator=(const Cluster&) = delete;

    Cluster(Cluster&&) = delete;

    Cluster& operator=(Cluster&&) = delete;

    // Generic helper functions.

    /** Whether the linearization of this Cluster can be exposed. */

    bool IsAcceptable() const noexcept

    {

        return m_quality == QualityLevel::ACCEPTABLE || m_quality == QualityLevel::OPTIMAL;

    }

    /** Whether the linearization of this Cluster is topological. */

    bool IsTopological() const noexcept

    {

        return m_quality != QualityLevel::NEEDS_FIX && m_quality != QualityLevel::NEEDS_SPLIT_FIX;

    }

    /** Whether the linearization of this Cluster is optimal. */

    bool IsOptimal() const noexcept

    {

        return m_quality == QualityLevel::OPTIMAL;

    }

    /** Whether this cluster is oversized. Note that no changes that can cause oversizedness are

     *  ever applied, so the only way a materialized Cluster object can be oversized is by being

     *  an individually oversized transaction singleton. */

    bool IsOversized() const noexcept { return m_quality == QualityLevel::OVERSIZED_SINGLETON; }

    /** Whether this cluster requires splitting. */

    bool NeedsSplitting() const noexcept

    {

        return m_quality == QualityLevel::NEEDS_SPLIT || m_quality == QualityLevel::NEEDS_SPLIT_FIX;

    }

    /** Get the smallest number of transactions this Cluster is intended for. */

    virtual DepGraphIndex GetMinIntendedTxCount() const noexcept = 0;

    /** Get the maximum number of transactions this Cluster supports. */

    virtual DepGraphIndex GetMaxTxCount() const noexcept = 0;

    /** Total memory usage currently for this Cluster, including all its dynamic memory, plus Cluster

     *  structure itself, and ClusterSet::m_clusters entry. */

    virtual size_t TotalMemoryUsage() const noexcept = 0;

    /** Determine the range of DepGraphIndexes used by this Cluster. */

    virtual DepGraphIndex GetDepGraphIndexRange() const noexcept = 0;

    /** Get the number of transactions in this Cluster. */

    virtual LinearizationIndex GetTxCount() const noexcept = 0;

    /** Get the total size of the transactions in this Cluster. */

    virtual uint64_t GetTotalTxSize() const noexcept = 0;

    /** Given a DepGraphIndex into this Cluster, find the corresponding GraphIndex. */

    virtual GraphIndex GetClusterEntry(DepGraphIndex index) const noexcept = 0;

    /** Append a transaction with given GraphIndex at the end of this Cluster and its

     *  linearization. Return the DepGraphIndex it was placed at. */

    virtual DepGraphIndex AppendTransaction(GraphIndex graph_idx, FeePerWeight feerate) noexcept = 0;

    /** Add dependencies to a given child in this cluster. */

    virtual void AddDependencies(SetType parents, DepGraphIndex child) noexcept = 0;

    /** Invoke visit1_fn for each transaction in the cluster, in linearization order, then

     *  visit2_fn in the same order, then wipe this Cluster. */

    virtual void ExtractTransactions(const std::function<void (DepGraphIndex, GraphIndex, FeePerWeight)>& visit1_fn, const std::function<void (DepGraphIndex, GraphIndex, SetType)>& visit2_fn) noexcept = 0;

    /** Figure out what level this Cluster exists at in the graph. In most cases this is known by

     *  the caller already (see all "int level" arguments below), but not always. */

    virtual int GetLevel(const TxGraphImpl& graph) const noexcept = 0;

    /** Only called by TxGraphImpl::SwapIndexes. */

    virtual void UpdateMapping(DepGraphIndex cluster_idx, GraphIndex graph_idx) noexcept = 0;

    /** Push changes to Cluster and its linearization to the TxGraphImpl Entry objects. Main chunk

     *  information is computed if the cluster is acceptable, or when rename is set. Rename is used

     *  when called from Compact, to recompute after GraphIndexes may have changed; in this case,

     *  no chunk index objects are removed or created either. */

    virtual void Updated(TxGraphImpl& graph, int level, bool rename) noexcept = 0;

    /** Remove all chunk index entries for this cluster (level=0 only). */

    virtual void RemoveChunkData(TxGraphImpl& graph) noexcept = 0;

    /** Create a copy of this Cluster in staging, returning a pointer to it (used by PullIn). */

    virtual Cluster* CopyToStaging(TxGraphImpl& graph) const noexcept = 0;

    /** Get the list of Clusters in main that conflict with this one (which is assumed to be in staging). */

    virtual void GetConflicts(const TxGraphImpl& graph, std::vector<Cluster*>& out) const noexcept = 0;

    /** Mark all the Entry objects belonging to this staging Cluster as missing. The Cluster must be

     *  deleted immediately after. */

    virtual void MakeStagingTransactionsMissing(TxGraphImpl& graph) noexcept = 0;

    /** Remove all transactions from a (non-empty) Cluster. */

    virtual void Clear(TxGraphImpl& graph, int level) noexcept = 0;

    /** Change a Cluster's level from 1 (staging) to 0 (main). */

    virtual void MoveToMain(TxGraphImpl& graph) noexcept = 0;

    /** Minimize this Cluster's memory usage. */

    virtual void Compact() noexcept = 0;

    // Functions that implement the Cluster-specific side of internal TxGraphImpl mutations.

    /** Apply all removals from the front of to_remove that apply to this Cluster, popping them

     *  off. There must be at least one such entry. */

    virtual void ApplyRemovals(TxGraphImpl& graph, int level, std::span<GraphIndex>& to_remove) noexcept = 0;

    /** Split this cluster (must have a NEEDS_SPLIT* quality). Returns whether to delete this

     *  Cluster afterwards. */

    [[nodiscard]] virtual bool Split(TxGraphImpl& graph, int level) noexcept = 0;

    /** Move all transactions from cluster to *this (as separate components). */

    virtual void Merge(TxGraphImpl& graph, int level, Cluster& cluster) noexcept = 0;

    /** Given a span of (parent, child) pairs that all belong to this Cluster, apply them. */

    virtual void ApplyDependencies(TxGraphImpl& graph, int level, std::span<std::pair<GraphIndex, GraphIndex>> to_apply) noexcept = 0;

    /** Improve the linearization of this Cluster. Returns how much work was performed and whether

     *  the Cluster's QualityLevel improved as a result. */

    virtual std::pair<uint64_t, bool> Relinearize(TxGraphImpl& graph, int level, uint64_t max_cost) noexcept = 0;

    /** For every chunk in the cluster, append its FeeFrac to ret. */

    virtual void AppendChunkFeerates(std::vector<FeeFrac>& ret) const noexcept = 0;

    /** Add a TrimTxData entry (filling m_chunk_feerate, m_index, m_tx_size) for every

     *  transaction in the Cluster to ret. Implicit dependencies between consecutive transactions

     *  in the linearization are added to deps. Return the Cluster's total transaction size. */

    virtual uint64_t AppendTrimData(std::vector<TrimTxData>& ret, std::vector<std::pair<GraphIndex, GraphIndex>>& deps) const noexcept = 0;

    // Functions that implement the Cluster-specific side of public TxGraph functions.

    /** Process elements from the front of args that apply to this cluster, and append Refs for the

     *  union of their ancestors to output. */

    virtual void GetAncestorRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept = 0;

    /** Process elements from the front of args that apply to this cluster, and append Refs for the

     *  union of their descendants to output. */

    virtual void GetDescendantRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept = 0;

    /** Populate range with refs for the transactions in this Cluster's linearization, from

     *  position start_pos until start_pos+range.size()-1, inclusive. Returns whether that

     *  range includes the last transaction in the linearization. */

    virtual bool GetClusterRefs(TxGraphImpl& graph, std::span<TxGraph::Ref*> range, LinearizationIndex start_pos) noexcept = 0;

    /** Get the individual transaction feerate of a Cluster element. */

    virtual FeePerWeight GetIndividualFeerate(DepGraphIndex idx) noexcept = 0;

    /** Modify the fee of a Cluster element. */

    virtual void SetFee(TxGraphImpl& graph, int level, DepGraphIndex idx, int64_t fee) noexcept = 0;

    // Debugging functions.

    virtual void SanityCheck(const TxGraphImpl& graph, int level) const = 0;

};

/** An implementation of Cluster that uses a DepGraph and vectors, to support arbitrary numbers of

 *  transactions up to MAX_CLUSTER_COUNT_LIMIT. */

class GenericClusterImpl final : public Cluster

{

    friend class TxGraphImpl;

    /** The DepGraph for this cluster, holding all feerates, and ancestors/descendants. */

    DepGraph<SetType> m_depgraph;

    /** m_mapping[i] gives the GraphIndex for the position i transaction in m_depgraph. Values for

     *  positions i that do not exist in m_depgraph shouldn't ever be accessed and thus don't

     *  matter. m_mapping.size() equals m_depgraph.PositionRange(). */

    std::vector<GraphIndex> m_mapping;

    /** The current linearization of the cluster. m_linearization.size() equals

     *  m_depgraph.TxCount(). This is always kept topological. */

    std::vector<DepGraphIndex> m_linearization;

public:

    /** The smallest number of transactions this Cluster implementation is intended for. */

    static constexpr DepGraphIndex MIN_INTENDED_TX_COUNT{2};

    /** The largest number of transactions this Cluster implementation supports. */

    static constexpr DepGraphIndex MAX_TX_COUNT{SetType::Size()};

    GenericClusterImpl() noexcept = delete;

    /** Construct an empty GenericClusterImpl. */

    explicit GenericClusterImpl(uint64_t sequence) noexcept;

    size_t TotalMemoryUsage() const noexcept final;

    constexpr DepGraphIndex GetMinIntendedTxCount() const noexcept final { return MIN_INTENDED_TX_COUNT; }

    constexpr DepGraphIndex GetMaxTxCount() const noexcept final { return MAX_TX_COUNT; }

    DepGraphIndex GetDepGraphIndexRange() const noexcept final { return m_depgraph.PositionRange(); }

    LinearizationIndex GetTxCount() const noexcept final { return m_linearization.size(); }

    uint64_t GetTotalTxSize() const noexcept final;

    GraphIndex GetClusterEntry(DepGraphIndex index) const noexcept final { return m_mapping[index]; }

    DepGraphIndex AppendTransaction(GraphIndex graph_idx, FeePerWeight feerate) noexcept final;

    void AddDependencies(SetType parents, DepGraphIndex child) noexcept final;

    void ExtractTransactions(const std::function<void (DepGraphIndex, GraphIndex, FeePerWeight)>& visit1_fn, const std::function<void (DepGraphIndex, GraphIndex, SetType)>& visit2_fn) noexcept final;

    int GetLevel(const TxGraphImpl& graph) const noexcept final;

    void UpdateMapping(DepGraphIndex cluster_idx, GraphIndex graph_idx) noexcept final { m_mapping[cluster_idx] = graph_idx; }

    void Updated(TxGraphImpl& graph, int level, bool rename) noexcept final;

    void RemoveChunkData(TxGraphImpl& graph) noexcept final;

    Cluster* CopyToStaging(TxGraphImpl& graph) const noexcept final;

    void GetConflicts(const TxGraphImpl& graph, std::vector<Cluster*>& out) const noexcept final;

    void MakeStagingTransactionsMissing(TxGraphImpl& graph) noexcept final;

    void Clear(TxGraphImpl& graph, int level) noexcept final;

    void MoveToMain(TxGraphImpl& graph) noexcept final;

    void Compact() noexcept final;

    void ApplyRemovals(TxGraphImpl& graph, int level, std::span<GraphIndex>& to_remove) noexcept final;

    [[nodiscard]] bool Split(TxGraphImpl& graph, int level) noexcept final;

    void Merge(TxGraphImpl& graph, int level, Cluster& cluster) noexcept final;

    void ApplyDependencies(TxGraphImpl& graph, int level, std::span<std::pair<GraphIndex, GraphIndex>> to_apply) noexcept final;

    std::pair<uint64_t, bool> Relinearize(TxGraphImpl& graph, int level, uint64_t max_cost) noexcept final;

    void AppendChunkFeerates(std::vector<FeeFrac>& ret) const noexcept final;

    uint64_t AppendTrimData(std::vector<TrimTxData>& ret, std::vector<std::pair<GraphIndex, GraphIndex>>& deps) const noexcept final;

    void GetAncestorRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept final;

    void GetDescendantRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept final;

    bool GetClusterRefs(TxGraphImpl& graph, std::span<TxGraph::Ref*> range, LinearizationIndex start_pos) noexcept final;

    FeePerWeight GetIndividualFeerate(DepGraphIndex idx) noexcept final;

    void SetFee(TxGraphImpl& graph, int level, DepGraphIndex idx, int64_t fee) noexcept final;

    void SanityCheck(const TxGraphImpl& graph, int level) const final;

};

/** An implementation of Cluster that only supports 1 transaction. */

class SingletonClusterImpl final : public Cluster

{

    friend class TxGraphImpl;

    /** The feerate of the (singular) transaction in this Cluster. */

    FeePerWeight m_feerate;

    /** Constant to indicate that this Cluster is empty. */

    static constexpr auto NO_GRAPH_INDEX = GraphIndex(-1);

    /** The GraphIndex of the transaction. NO_GRAPH_INDEX if this Cluster is empty. */

    GraphIndex m_graph_index = NO_GRAPH_INDEX;

public:

    /** The smallest number of transactions this Cluster implementation is intended for. */

    static constexpr DepGraphIndex MIN_INTENDED_TX_COUNT{1};

    /** The largest number of transactions this Cluster implementation supports. */

    static constexpr DepGraphIndex MAX_TX_COUNT{1};

    SingletonClusterImpl() noexcept = delete;

    /** Construct an empty SingletonClusterImpl. */

    explicit SingletonClusterImpl(uint64_t sequence) noexcept : Cluster(sequence) {}

    size_t TotalMemoryUsage() const noexcept final;

    constexpr DepGraphIndex GetMinIntendedTxCount() const noexcept final { return MIN_INTENDED_TX_COUNT; }

    constexpr DepGraphIndex GetMaxTxCount() const noexcept final { return MAX_TX_COUNT; }

    LinearizationIndex GetTxCount() const noexcept final { return m_graph_index != NO_GRAPH_INDEX; }

    DepGraphIndex GetDepGraphIndexRange() const noexcept final { return GetTxCount(); }

    uint64_t GetTotalTxSize() const noexcept final { return GetTxCount() ? m_feerate.size : 0; }

    GraphIndex GetClusterEntry(DepGraphIndex index) const noexcept final { Assume(index == 0); Assume(GetTxCount()); return m_graph_index; }

    DepGraphIndex AppendTransaction(GraphIndex graph_idx, FeePerWeight feerate) noexcept final;

    void AddDependencies(SetType parents, DepGraphIndex child) noexcept final;

    void ExtractTransactions(const std::function<void (DepGraphIndex, GraphIndex, FeePerWeight)>& visit1_fn, const std::function<void (DepGraphIndex, GraphIndex, SetType)>& visit2_fn) noexcept final;

    int GetLevel(const TxGraphImpl& graph) const noexcept final;

    void UpdateMapping(DepGraphIndex cluster_idx, GraphIndex graph_idx) noexcept final { Assume(cluster_idx == 0); m_graph_index = graph_idx; }

    void Updated(TxGraphImpl& graph, int level, bool rename) noexcept final;

    void RemoveChunkData(TxGraphImpl& graph) noexcept final;

    Cluster* CopyToStaging(TxGraphImpl& graph) const noexcept final;

    void GetConflicts(const TxGraphImpl& graph, std::vector<Cluster*>& out) const noexcept final;

    void MakeStagingTransactionsMissing(TxGraphImpl& graph) noexcept final;

    void Clear(TxGraphImpl& graph, int level) noexcept final;

    void MoveToMain(TxGraphImpl& graph) noexcept final;

    void Compact() noexcept final;

    void ApplyRemovals(TxGraphImpl& graph, int level, std::span<GraphIndex>& to_remove) noexcept final;

    [[nodiscard]] bool Split(TxGraphImpl& graph, int level) noexcept final;

    void Merge(TxGraphImpl& graph, int level, Cluster& cluster) noexcept final;

    void ApplyDependencies(TxGraphImpl& graph, int level, std::span<std::pair<GraphIndex, GraphIndex>> to_apply) noexcept final;

    std::pair<uint64_t, bool> Relinearize(TxGraphImpl& graph, int level, uint64_t max_cost) noexcept final;

    void AppendChunkFeerates(std::vector<FeeFrac>& ret) const noexcept final;

    uint64_t AppendTrimData(std::vector<TrimTxData>& ret, std::vector<std::pair<GraphIndex, GraphIndex>>& deps) const noexcept final;

    void GetAncestorRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept final;

    void GetDescendantRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept final;

    bool GetClusterRefs(TxGraphImpl& graph, std::span<TxGraph::Ref*> range, LinearizationIndex start_pos) noexcept final;

    FeePerWeight GetIndividualFeerate(DepGraphIndex idx) noexcept final;

    void SetFee(TxGraphImpl& graph, int level, DepGraphIndex idx, int64_t fee) noexcept final;

    void SanityCheck(const TxGraphImpl& graph, int level) const final;

};

/** The transaction graph, including staged changes.

 *

 * The overall design of the data structure consists of 3 interlinked representations:

 * - The transactions (held as a vector of TxGraphImpl::Entry inside TxGraphImpl).

 * - The clusters (Cluster objects in per-quality vectors inside TxGraphImpl::ClusterSet).

 * - The Refs (TxGraph::Ref objects, held externally by users of the TxGraph class)

 *

 * The Clusters are kept in one or two ClusterSet objects, one for the "main" graph, and one for

 * the proposed changes ("staging"). If a transaction occurs in both, they share the same Entry,

 * but there will be a separate Cluster per graph.

 *

 * Clusters and Refs contain the index of the Entry objects they refer to, and the Entry objects

 * refer back to the Clusters and Refs the corresponding transaction is contained in.

 *

 * While redundant, this permits moving all of them independently, without invalidating things

 * or costly iteration to fix up everything:

 * - Entry objects can be moved to fill holes left by removed transactions in the Entry vector

 *   (see TxGraphImpl::Compact).

 * - Clusters can be rewritten continuously (removals can cause them to split, new dependencies

 *   can cause them to be merged).

 * - Ref objects can be held outside the class, while permitting them to be moved around, and

 *   inherited from.

 */

class TxGraphImpl final : public TxGraph

{

    friend class Cluster;

    friend class SingletonClusterImpl;

    friend class GenericClusterImpl;

    friend class BlockBuilderImpl;

private:

    /** Internal RNG. */

    FastRandomContext m_rng;

    /** This TxGraphImpl's maximum cluster count limit. */

    const DepGraphIndex m_max_cluster_count;

    /** This TxGraphImpl's maximum cluster size limit. */

    const uint64_t m_max_cluster_size;

    /** The amount of linearization work needed per cluster to be considered acceptable. */

    const uint64_t m_acceptable_cost;

    /** Fallback ordering for transactions. */

    const std::function<std::strong_ordering(const TxGraph::Ref&, const TxGraph::Ref&)> m_fallback_order;

    /** Information about one group of Clusters to be merged. */

    struct GroupEntry

    {

        /** Where the clusters to be merged start in m_group_clusters. */

        uint32_t m_cluster_offset;

        /** How many clusters to merge. */

        uint32_t m_cluster_count;

        /** Where the dependencies for this cluster group in m_deps_to_add start. */

        uint32_t m_deps_offset;

        /** How many dependencies to add. */

        uint32_t m_deps_count;

    };

    /** Information about all groups of Clusters to be merged. */

    struct GroupData

    {

        /** The groups of Clusters to be merged. */

        std::vector<GroupEntry> m_groups;

        /** Which clusters are to be merged. GroupEntry::m_cluster_offset indexes into this. */

        std::vector<Cluster*> m_group_clusters;

    };

    /** The collection of all Clusters in main or staged. */

    struct ClusterSet

    {

        /** The vectors of clusters, one vector per quality level. ClusterSetIndex indexes into each. */

        std::array<std::vector<std::unique_ptr<Cluster>>, int(QualityLevel::NONE)> m_clusters;

        /** Which removals have yet to be applied. */

        std::vector<GraphIndex> m_to_remove;

        /** Which dependencies are to be added ((parent,child) pairs). GroupData::m_deps_offset indexes

         *  into this. */

        std::vector<std::pair<GraphIndex, GraphIndex>> m_deps_to_add;

        /** Information about the merges to be performed, if known. */

        std::optional<GroupData> m_group_data = GroupData{};

        /** Which entries were removed in this ClusterSet (so they can be wiped on abort). This

         *  includes all entries which have an (R) removed locator at this level (staging only),

         *  plus optionally any transaction in m_unlinked. */

        std::vector<GraphIndex> m_removed;

        /** Total number of transactions in this graph (sum of all transaction counts in all

         *  Clusters, and for staging also those inherited from the main ClusterSet). */

        GraphIndex m_txcount{0};

        /** Total number of individually oversized transactions in the graph. */

        GraphIndex m_txcount_oversized{0};

        /** Whether this graph is oversized (if known). */

        std::optional<bool> m_oversized{false};

        /** The combined TotalMemoryUsage of all clusters in this level (only Clusters that

         *  are materialized; in staging, implicit Clusters from main are not counted), */

        size_t m_cluster_usage{0};

        ClusterSet() noexcept = default;

    };

    /** The main ClusterSet. */

    ClusterSet m_main_clusterset;

    /** The staging ClusterSet, if any. */

    std::optional<ClusterSet> m_staging_clusterset;

    /** Next sequence number to assign to created Clusters. */

    uint64_t m_next_sequence_counter{0};

    /** Information about a chunk in the main graph. */

    struct ChunkData

    {

        /** The Entry which is the last transaction of the chunk. */

        mutable GraphIndex m_graph_index;

        /** How many transactions the chunk contains (-1 = singleton tail of cluster). */

        LinearizationIndex m_chunk_count;

        ChunkData(GraphIndex graph_index, LinearizationIndex chunk_count) noexcept :

            m_graph_index{graph_index}, m_chunk_count{chunk_count} {}

    };

    /** Compare two Cluster* by their m_sequence value (while supporting nullptr). */

    static std::strong_ordering CompareClusters(Cluster* a, Cluster* b) noexcept

    {

        // The nullptr pointer compares before everything else.

        if (a == nullptr || b == nullptr) {

            return (a != nullptr) <=> (b != nullptr);

        }

        // If neither pointer is nullptr, compare the Clusters' sequence numbers.

        Assume(a == b || a->m_sequence != b->m_sequence);

        return a->m_sequence <=> b->m_sequence;

    }

    /** Compare two entries (which must both exist within the main graph). */

    std::strong_ordering CompareMainTransactions(GraphIndex a, GraphIndex b) const noexcept

    {

        if (a == b) return std::strong_ordering::equal;

        Assume(a < m_entries.size() && b < m_entries.size());

        const auto& entry_a = m_entries[a];

        const auto& entry_b = m_entries[b];

        // Compare chunk feerates, and return result if it differs.

        auto feerate_cmp = ByRatio{entry_b.m_main_chunk_feerate} <=> ByRatio{entry_a.m_main_chunk_feerate};

        if (feerate_cmp != 0) return feerate_cmp;

        // Compare equal-feerate chunk prefix size for comparing equal chunk feerates. This does two

        // things: it distinguishes equal-feerate chunks within the same cluster (because later

        // ones will always have a higher prefix size), and it may distinguish equal-feerate chunks

        // from distinct clusters.

        if (entry_a.m_main_equal_feerate_chunk_prefix_size != entry_b.m_main_equal_feerate_chunk_prefix_size) {

            return entry_a.m_main_equal_feerate_chunk_prefix_size <=> entry_b.m_main_equal_feerate_chunk_prefix_size;

        }

        // Compare by maximum m_fallback_order element to order equal-feerate chunks in distinct

        // clusters, when the equal-feerate-prefix size is also the same.

        const auto& locator_a = entry_a.m_locator[0];

        const auto& locator_b = entry_b.m_locator[0];

        Assume(locator_a.IsPresent() && locator_b.IsPresent());

        if (locator_a.cluster != locator_b.cluster) {

            auto fallback_cmp = m_fallback_order(*m_entries[entry_a.m_main_max_chunk_fallback].m_ref,

                                                 *m_entries[entry_b.m_main_max_chunk_fallback].m_ref);

            if (fallback_cmp != 0) return fallback_cmp;

            // This shouldn't be reachable as m_fallback_order defines a strong ordering.

            Assume(false);

            return CompareClusters(locator_a.cluster, locator_b.cluster);

        }

        // Within a single chunk, sort by position within cluster linearization.

        return entry_a.m_main_lin_index <=> entry_b.m_main_lin_index;

    }

    /** Comparator for ChunkData objects in mining order. */

    class ChunkOrder

    {

        const TxGraphImpl* const m_graph;

    public:

        explicit ChunkOrder(const TxGraphImpl* graph) : m_graph(graph) {}

        bool operator()(const ChunkData& a, const ChunkData& b) const noexcept

        {

            return m_graph->CompareMainTransactions(a.m_graph_index, b.m_graph_index) < 0;

        }

    };

    /** Definition for the mining index type. */

    using ChunkIndex = std::set<ChunkData, ChunkOrder>;

    /** Index of ChunkData objects, indexing the last transaction in each chunk in the main

     *  graph. */

    ChunkIndex m_main_chunkindex;

    /** Number of index-observing objects in existence (BlockBuilderImpls). */

    size_t m_main_chunkindex_observers{0};

    /** Cache of discarded ChunkIndex node handles to reuse, avoiding additional allocation. */

    std::vector<ChunkIndex::node_type> m_main_chunkindex_discarded;

    /** A Locator that describes whether, where, and in which Cluster an Entry appears.

     *  Every Entry has MAX_LEVELS locators, as it may appear in one Cluster per level.

     *

     *  Each level of a Locator is in one of three states:

     *

     *  - (P)resent: actually occurs in a Cluster at that level.

     *

     *  - (M)issing:

     *    - In the main graph:    the transaction does not exist in main.

     *    - In the staging graph: the transaction's existence is the same as in main. If it doesn't

     *                            exist in main, (M) in staging means it does not exist there

     *                            either. If it does exist in main, (M) in staging means the

     *                            cluster it is in has not been modified in staging, and thus the

     *                            transaction implicitly exists in staging too (without explicit

     *                            Cluster object; see PullIn() to create it in staging too).

     *

     *  - (R)emoved: only possible in staging; it means the transaction exists in main, but is

     *               removed in staging.

     *

     * The following combinations are possible:

     * - (M,M): the transaction doesn't exist in either graph.

     * - (P,M): the transaction exists in both, but only exists explicitly in a Cluster object in

     *          main. Its existence in staging is inherited from main.

     * - (P,P): the transaction exists in both, and is materialized in both. Thus, the clusters

     *          and/or their linearizations may be different in main and staging.

     * - (M,P): the transaction is added in staging, and does not exist in main.

     * - (P,R): the transaction exists in main, but is removed in staging.

     *

     * When staging does not exist, only (M,M) and (P,M) are possible.

     */

    struct Locator

    {

        /** Which Cluster the Entry appears in (nullptr = missing). */

        Cluster* cluster{nullptr};

        /** Where in the Cluster it appears (if cluster == nullptr: 0 = missing, -1 = removed). */

        DepGraphIndex index{0};

        /** Mark this Locator as missing (= same as lower level, or non-existing if level 0). */

        void SetMissing() noexcept { cluster = nullptr; index = 0; }

        /** Mark this Locator as removed (not allowed in level 0). */

        void SetRemoved() noexcept { cluster = nullptr; index = DepGraphIndex(-1); }

        /** Mark this Locator as present, in the specified Cluster. */

        void SetPresent(Cluster* c, DepGraphIndex i) noexcept { cluster = c; index = i; }

        /** Check if this Locator is missing. */

        bool IsMissing() const noexcept { return cluster == nullptr && index == 0; }

        /** Check if this Locator is removed. */

        bool IsRemoved() const noexcept { return cluster == nullptr && index == DepGraphIndex(-1); }

        /** Check if this Locator is present (in some Cluster). */

        bool IsPresent() const noexcept { return cluster != nullptr; }

    };

    /** Internal information about each transaction in a TxGraphImpl. */

    struct Entry

    {

        /** Pointer to the corresponding Ref object if any, or nullptr if unlinked. */

        Ref* m_ref{nullptr};

        /** Iterator to the corresponding ChunkData, if any, and m_main_chunkindex.end() otherwise.

         *  This is initialized on construction of the Entry, in AddTransaction. */

        ChunkIndex::iterator m_main_chunkindex_iterator;

        /** Which Cluster and position therein this Entry appears in. ([0] = main, [1] = staged). */

        Locator m_locator[MAX_LEVELS];

        /** The chunk feerate of this transaction in main (if present in m_locator[0]). */

        FeePerWeight m_main_chunk_feerate;

        /** The equal-feerate chunk prefix size of this transaction in main. If the transaction is

         *  part of chunk C in main, then this gives the sum of the sizes of all chunks in C's

         *  cluster, whose feerate is equal to that of C, which do not appear after C itself in

         *  the cluster's linearization.

         *  This provides a way to sort equal-feerate chunks across clusters, in a way that agrees

         *  with the within-cluster chunk ordering. */

        int32_t m_main_equal_feerate_chunk_prefix_size;

        /** The position this transaction has in the main linearization (if present). */

        LinearizationIndex m_main_lin_index;

        /** Of all transactions within this transaction's chunk in main (if present there), the

         *  maximal one according to m_fallback_order. */

        GraphIndex m_main_max_chunk_fallback = GraphIndex(-1);

    };

    /** The set of all transactions (in all levels combined). GraphIndex values index into this. */

    std::vector<Entry> m_entries;

    /** Set of Entries which have no linked Ref anymore. */

    std::vector<GraphIndex> m_unlinked;

public:

    /** Construct a new TxGraphImpl with the specified limits and fallback order. */

    explicit TxGraphImpl(

        DepGraphIndex max_cluster_count,

        uint64_t max_cluster_size,

        uint64_t acceptable_cost,

        const std::function<std::strong_ordering(const TxGraph::Ref&, const TxGraph::Ref&)>& fallback_order

    ) noexcept :

        m_max_cluster_count(max_cluster_count),

        m_max_cluster_size(max_cluster_size),

        m_acceptable_cost(acceptable_cost),

        m_fallback_order(fallback_order),

        m_main_chunkindex(ChunkOrder(this))

    {

        Assume(max_cluster_count >= 1);

        Assume(max_cluster_count <= MAX_CLUSTER_COUNT_LIMIT);

    }

    /** Destructor. */

    ~TxGraphImpl() noexcept;

    // Cannot move or copy (would invalidate TxGraphImpl* in Ref, MiningOrder, EvictionOrder).

    TxGraphImpl(const TxGraphImpl&) = delete;

    TxGraphImpl& operator=(const TxGraphImpl&) = delete;

    TxGraphImpl(TxGraphImpl&&) = delete;

    TxGraphImpl& operator=(TxGraphImpl&&) = delete;

    // Simple helper functions.

    /** Swap the Entry referred to by a and the one referred to by b. Gather main clusters to

     *  update afterwards. */

    void SwapIndexes(GraphIndex a, GraphIndex b, std::vector<Cluster*>& affected_main) noexcept;

    /** If idx exists in the specified level ClusterSet (explicitly, or in the level below and not

    *   removed), return the Cluster it is in. Otherwise, return nullptr. */

    Cluster* FindCluster(GraphIndex idx, int level) const noexcept { return FindClusterAndLevel(idx, level).first; }

    /** Like FindCluster, but also return what level the match was found in (-1 if not found). */

    std::pair<Cluster*, int> FindClusterAndLevel(GraphIndex idx, int level) const noexcept;

    /** Extract a Cluster from its ClusterSet, and set its quality to QualityLevel::NONE. */

    std::unique_ptr<Cluster> ExtractCluster(int level, QualityLevel quality, ClusterSetIndex setindex) noexcept;

    /** Delete a Cluster. */

    void DeleteCluster(Cluster& cluster, int level) noexcept;

    /** Insert a Cluster into its ClusterSet. */

    ClusterSetIndex InsertCluster(int level, std::unique_ptr<Cluster>&& cluster, QualityLevel quality) noexcept;

    /** Change the QualityLevel of a Cluster (identified by old_quality and old_index). */

    void SetClusterQuality(int level, QualityLevel old_quality, ClusterSetIndex old_index, QualityLevel new_quality) noexcept;

    /** Get the index of the top level ClusterSet (staging if it exists, main otherwise). */

    int GetTopLevel() const noexcept { return m_staging_clusterset.has_value(); }

    /** Get the specified level (staging if it exists and level is TOP, main otherwise). */

    int GetSpecifiedLevel(Level level) const noexcept { return level == Level::TOP && m_staging_clusterset.has_value(); }

    /** Get a reference to the ClusterSet at the specified level (which must exist). */

    ClusterSet& GetClusterSet(int level) noexcept;

    const ClusterSet& GetClusterSet(int level) const noexcept;

    /** Make a transaction not exist at a specified level. It must currently exist there.

     *  oversized_tx indicates whether the transaction is an individually-oversized one

     *  (OVERSIZED_SINGLETON). */

    void ClearLocator(int level, GraphIndex index, bool oversized_tx) noexcept;

    /** Find which Clusters in main conflict with ones in staging. */

    std::vector<Cluster*> GetConflicts() const noexcept;

    /** Clear an Entry's ChunkData. */

    void ClearChunkData(Entry& entry) noexcept;

    /** Give an Entry a ChunkData object. */

    void CreateChunkData(GraphIndex idx, LinearizationIndex chunk_count) noexcept;

    /** Create an empty GenericClusterImpl object. */

    std::unique_ptr<GenericClusterImpl> CreateEmptyGenericCluster() noexcept

    {

        return std::make_unique<GenericClusterImpl>(m_next_sequence_counter++);

    }

    /** Create an empty SingletonClusterImpl object. */

    std::unique_ptr<SingletonClusterImpl> CreateEmptySingletonCluster() noexcept

    {

        return std::make_unique<SingletonClusterImpl>(m_next_sequence_counter++);

    }

    /** Create an empty Cluster of the appropriate implementation for the specified (maximum) tx

     *  count. */

    std::unique_ptr<Cluster> CreateEmptyCluster(DepGraphIndex tx_count) noexcept

    {

        if (tx_count >= SingletonClusterImpl::MIN_INTENDED_TX_COUNT && tx_count <= SingletonClusterImpl::MAX_TX_COUNT) {

            return CreateEmptySingletonCluster();

        }

        if (tx_count >= GenericClusterImpl::MIN_INTENDED_TX_COUNT && tx_count <= GenericClusterImpl::MAX_TX_COUNT) {

            return CreateEmptyGenericCluster();

        }

        assert(false);

        return {};

    }

    // Functions for handling Refs.

    /** Only called by Ref's move constructor/assignment to update Ref locations. */

    void UpdateRef(GraphIndex idx, Ref& new_location) noexcept final

    {

        auto& entry = m_entries[idx];

        Assume(entry.m_ref != nullptr);

        entry.m_ref = &new_location;

    }

    /** Only called by Ref::~Ref to unlink Refs, and Ref's move assignment. */

    void UnlinkRef(GraphIndex idx) noexcept final

    {

        auto& entry = m_entries[idx];

        Assume(entry.m_ref != nullptr);

        Assume(m_main_chunkindex_observers == 0 || !entry.m_locator[0].IsPresent());

        // Remove all chunk index entries for the affected cluster, to avoid any chunk indexes

        // referencing unlinked/destroyed Refs.

        if (entry.m_locator[0].IsPresent()) {

            entry.m_locator[0].cluster->RemoveChunkData(*this);

        }

        entry.m_ref = nullptr;

        // Mark the transaction as to be removed in all levels where it explicitly or implicitly

        // exists.

        bool exists_anywhere{false};

        bool exists{false};

        for (int level = 0; level <= GetTopLevel(); ++level) {

            if (entry.m_locator[level].IsPresent()) {

                exists_anywhere = true;

                exists = true;

            } else if (entry.m_locator[level].IsRemoved()) {

                exists = false;

            }

            if (exists) {

                auto& clusterset = GetClusterSet(level);

                clusterset.m_to_remove.push_back(idx);

                // Force recomputation of grouping data.

                clusterset.m_group_data = std::nullopt;

                // Do not wipe the oversized state of main if staging exists. The reason for this

                // is that the alternative would mean that cluster merges may need to be applied to

                // a formerly-oversized main graph while staging exists (to satisfy chunk feerate

                // queries into main, for example), and such merges could conflict with pulls of

                // some of their constituents into staging.

                if (level == GetTopLevel() && clusterset.m_oversized == true) {

                    clusterset.m_oversized = std::nullopt;

                }

            }

        }

        m_unlinked.push_back(idx);

        if (!exists_anywhere) Compact();

    }

    // Functions related to various normalization/application steps.

    /** Get rid of unlinked Entry objects in m_entries, if possible (this changes the GraphIndex

     *  values for remaining Entry objects, so this only does something when no to-be-applied

     *  operations or staged removals referring to GraphIndexes remain). */

    void Compact() noexcept;

    /** If cluster is not in staging, copy it there, and return a pointer to it.

    *   Staging must exist, and this modifies the locators of its

    *   transactions from inherited (P,M) to explicit (P,P). */

    Cluster* PullIn(Cluster* cluster, int level) noexcept;

    /** Apply all removals queued up in m_to_remove to the relevant Clusters (which get a

     *  NEEDS_SPLIT* QualityLevel) up to the specified level. */

    void ApplyRemovals(int up_to_level) noexcept;

    /** Split an individual cluster. */

    void Split(Cluster& cluster, int level) noexcept;

    /** Split all clusters that need splitting up to the specified level. */

    void SplitAll(int up_to_level) noexcept;

    /** Populate m_group_data based on m_deps_to_add in the specified level. */

    void GroupClusters(int level) noexcept;

    /** Merge the specified clusters. */

    void Merge(std::span<Cluster*> to_merge, int level) noexcept;

    /** Apply all m_deps_to_add to the relevant Clusters in the specified level. */

    void ApplyDependencies(int level) noexcept;

    /** Make a specified Cluster have quality ACCEPTABLE or OPTIMAL. */

    void MakeAcceptable(Cluster& cluster, int level) noexcept;

    /** Make all Clusters at the specified level have quality ACCEPTABLE or OPTIMAL. */

    void MakeAllAcceptable(int level) noexcept;

    // Implementations for the public TxGraph interface.

    void AddTransaction(Ref& arg, const FeePerWeight& feerate) noexcept final;

    void RemoveTransaction(const Ref& arg) noexcept final;

    void AddDependency(const Ref& parent, const Ref& child) noexcept final;

    void SetTransactionFee(const Ref&, int64_t fee) noexcept final;

    bool DoWork(uint64_t max_cost) noexcept final;

    void StartStaging() noexcept final;

    void CommitStaging() noexcept final;

    void AbortStaging() noexcept final;

    bool HaveStaging() const noexcept final { return m_staging_clusterset.has_value(); }

    bool Exists(const Ref& arg, Level level) noexcept final;

    FeePerWeight GetMainChunkFeerate(const Ref& arg) noexcept final;

    FeePerWeight GetIndividualFeerate(const Ref& arg) noexcept final;

    std::vector<Ref*> GetCluster(const Ref& arg, Level level) noexcept final;

    std::vector<Ref*> GetAncestors(const Ref& arg, Level level) noexcept final;

    std::vector<Ref*> GetDescendants(const Ref& arg, Level level) noexcept final;

    std::vector<Ref*> GetAncestorsUnion(std::span<const Ref* const> args, Level level) noexcept final;

    std::vector<Ref*> GetDescendantsUnion(std::span<const Ref* const> args, Level level) noexcept final;

    GraphIndex GetTransactionCount(Level level) noexcept final;

    bool IsOversized(Level level) noexcept final;

    std::strong_ordering CompareMainOrder(const Ref& a, const Ref& b) noexcept final;

    GraphIndex CountDistinctClusters(std::span<const Ref* const> refs, Level level) noexcept final;

    std::pair<std::vector<FeeFrac>, std::vector<FeeFrac>> GetMainStagingDiagrams() noexcept final;

    std::vector<Ref*> Trim() noexcept final;

    std::unique_ptr<BlockBuilder> GetBlockBuilder() noexcept final;

    std::pair<std::vector<Ref*>, FeePerWeight> GetWorstMainChunk() noexcept final;

    size_t GetMainMemoryUsage() noexcept final;

    void SanityCheck() const final;

};

TxGraphImpl::ClusterSet& TxGraphImpl::GetClusterSet(int level) noexcept

{

    if (level == 0) return m_main_clusterset;

    Assume(level == 1);

    Assume(m_staging_clusterset.has_value());

    return *m_staging_clusterset;

}

const TxGraphImpl::ClusterSet& TxGraphImpl::GetClusterSet(int level) const noexcept

{

    if (level == 0) return m_main_clusterset;

    Assume(level == 1);

    Assume(m_staging_clusterset.has_value());

    return *m_staging_clusterset;

}

/** Implementation of the TxGraph::BlockBuilder interface. */

class BlockBuilderImpl final : public TxGraph::BlockBuilder

{

    /** Which TxGraphImpl this object is doing block building for. It will have its

     *  m_main_chunkindex_observers incremented as long as this BlockBuilderImpl exists. */

    TxGraphImpl* const m_graph;

    /** Cluster sequence numbers which we're not including further transactions from. */

    std::unordered_set<uint64_t> m_excluded_clusters;

    /** Iterator to the current chunk in the chunk index. end() if nothing further remains. */

    TxGraphImpl::ChunkIndex::const_iterator m_cur_iter;

    /** Which cluster the current chunk belongs to, so we can exclude further transactions from it

     *  when that chunk is skipped. */

    Cluster* m_cur_cluster;

    /** Whether we know that m_cur_iter points to the last chunk of m_cur_cluster. */

    bool m_known_end_of_cluster;

    // Move m_cur_iter / m_cur_cluster to the next acceptable chunk.

    void Next() noexcept;

public:

    /** Construct a new BlockBuilderImpl to build blocks for the provided graph. */

    BlockBuilderImpl(TxGraphImpl& graph) noexcept;

    // Implement the public interface.

    ~BlockBuilderImpl() final;

    std::optional<std::pair<std::vector<TxGraph::Ref*>, FeePerWeight>> GetCurrentChunk() noexcept final;

    void Include() noexcept final;

    void Skip() noexcept final;

};

void TxGraphImpl::ClearChunkData(Entry& entry) noexcept

{

    if (entry.m_main_chunkindex_iterator != m_main_chunkindex.end()) {

        Assume(m_main_chunkindex_observers == 0);

        // If the Entry has a non-empty m_main_chunkindex_iterator, extract it, and move the handle

        // to the cache of discarded chunkindex entries.

        m_main_chunkindex_discarded.emplace_back(m_main_chunkindex.extract(entry.m_main_chunkindex_iterator));

        entry.m_main_chunkindex_iterator = m_main_chunkindex.end();

    }

}

void TxGraphImpl::CreateChunkData(GraphIndex idx, LinearizationIndex chunk_count) noexcept

{

    auto& entry = m_entries[idx];

    // Make sure to not create chunk data for unlinked entries, which would make invoking

    // m_fallback_order on them impossible.

    Assume(entry.m_ref != nullptr);

    if (!m_main_chunkindex_discarded.empty()) {

        // Reuse an discarded node handle.

        auto& node = m_main_chunkindex_discarded.back().value();

        node.m_graph_index = idx;

        node.m_chunk_count = chunk_count;

        auto insert_result = m_main_chunkindex.insert(std::move(m_main_chunkindex_discarded.back()));

        Assume(insert_result.inserted);

        entry.m_main_chunkindex_iterator = insert_result.position;

        m_main_chunkindex_discarded.pop_back();

    } else {

        // Construct a new entry.

        auto emplace_result = m_main_chunkindex.emplace(idx, chunk_count);

        Assume(emplace_result.second);

        entry.m_main_chunkindex_iterator = emplace_result.first;

    }

}

size_t GenericClusterImpl::TotalMemoryUsage() const noexcept

{

    return // Dynamic memory allocated in this Cluster.

           memusage::DynamicUsage(m_mapping) + memusage::DynamicUsage(m_linearization) +

           // Dynamic memory usage inside m_depgraph.

           m_depgraph.DynamicMemoryUsage() +

           // Memory usage of the allocated Cluster itself.

           memusage::MallocUsage(sizeof(GenericClusterImpl)) +

           // Memory usage of the ClusterSet::m_clusters entry.

           sizeof(std::unique_ptr<Cluster>);

}

size_t SingletonClusterImpl::TotalMemoryUsage() const noexcept

{

    return // Memory usage of the allocated SingletonClusterImpl itself.

           memusage::MallocUsage(sizeof(SingletonClusterImpl)) +

           // Memory usage of the ClusterSet::m_clusters entry.

           sizeof(std::unique_ptr<Cluster>);

}

uint64_t GenericClusterImpl::GetTotalTxSize() const noexcept

{

    uint64_t ret{0};

    for (auto i : m_linearization) {

        ret += m_depgraph.FeeRate(i).size;

    }

    return ret;

}

DepGraphIndex GenericClusterImpl::AppendTransaction(GraphIndex graph_idx, FeePerWeight feerate) noexcept

{

    Assume(graph_idx != GraphIndex(-1));

    auto ret = m_depgraph.AddTransaction(feerate);

    m_mapping.push_back(graph_idx);

    m_linearization.push_back(ret);

    return ret;

}

DepGraphIndex SingletonClusterImpl::AppendTransaction(GraphIndex graph_idx, FeePerWeight feerate) noexcept

{

    Assume(!GetTxCount());

    m_graph_index = graph_idx;

    m_feerate = feerate;

    return 0;

}

void GenericClusterImpl::AddDependencies(SetType parents, DepGraphIndex child) noexcept

{

    m_depgraph.AddDependencies(parents, child);

}

void SingletonClusterImpl::AddDependencies(SetType parents, DepGraphIndex child) noexcept

{

    // Singletons cannot have any dependencies.

    Assume(child == 0);

    Assume(parents == SetType{} || parents == SetType::Fill(0));

}

void GenericClusterImpl::ExtractTransactions(const std::function<void (DepGraphIndex, GraphIndex, FeePerWeight)>& visit1_fn, const std::function<void (DepGraphIndex, GraphIndex, SetType)>& visit2_fn) noexcept

{

    for (auto pos : m_linearization) {

        visit1_fn(pos, m_mapping[pos], FeePerWeight::FromFeeFrac(m_depgraph.FeeRate(pos)));

    }

    for (auto pos : m_linearization) {

        visit2_fn(pos, m_mapping[pos], m_depgraph.GetReducedParents(pos));

    }

    // Purge this Cluster, now that everything has been moved.

    m_depgraph = DepGraph<SetType>{};

    m_linearization.clear();

    m_mapping.clear();

}

void SingletonClusterImpl::ExtractTransactions(const std::function<void (DepGraphIndex, GraphIndex, FeePerWeight)>& visit1_fn, const std::function<void (DepGraphIndex, GraphIndex, SetType)>& visit2_fn) noexcept

{

    if (GetTxCount()) {

        visit1_fn(0, m_graph_index, m_feerate);

        visit2_fn(0, m_graph_index, SetType{});

        m_graph_index = NO_GRAPH_INDEX;

    }

}

int GenericClusterImpl::GetLevel(const TxGraphImpl& graph) const noexcept

{

    // GetLevel() does not work for empty Clusters.

    if (!Assume(!m_linearization.empty())) return -1;

    // Pick an arbitrary Entry that occurs in this Cluster.

    const auto& entry = graph.m_entries[m_mapping[m_linearization.front()]];

    // See if there is a level whose Locator matches this Cluster, if so return that level.

    for (int level = 0; level < MAX_LEVELS; ++level) {

        if (entry.m_locator[level].cluster == this) return level;

    }

    // Given that we started with an Entry that occurs in this Cluster, one of its Locators must

    // point back to it.

    assert(false);

    return -1;

}

int SingletonClusterImpl::GetLevel(const TxGraphImpl& graph) const noexcept

{

    // GetLevel() does not work for empty Clusters.

    if (!Assume(GetTxCount())) return -1;

    // Get the Entry in this Cluster.

    const auto& entry = graph.m_entries[m_graph_index];

    // See if there is a level whose Locator matches this Cluster, if so return that level.

    for (int level = 0; level < MAX_LEVELS; ++level) {

        if (entry.m_locator[level].cluster == this) return level;

    }

    // Given that we started with an Entry that occurs in this Cluster, one of its Locators must

    // point back to it.

    assert(false);

    return -1;

}

void TxGraphImpl::ClearLocator(int level, GraphIndex idx, bool oversized_tx) noexcept

{

    auto& entry = m_entries[idx];

    auto& clusterset = GetClusterSet(level);

    Assume(entry.m_locator[level].IsPresent());

    // Change the locator from Present to Missing or Removed.

    if (level == 0 || !entry.m_locator[level - 1].IsPresent()) {

        entry.m_locator[level].SetMissing();

    } else {

        entry.m_locator[level].SetRemoved();

        clusterset.m_removed.push_back(idx);

    }

    // Update the transaction count.

    --clusterset.m_txcount;

    clusterset.m_txcount_oversized -= oversized_tx;

    // If clearing main, adjust the status of Locators of this transaction in staging, if it exists.

    if (level == 0 && GetTopLevel() == 1) {

        if (entry.m_locator[1].IsRemoved()) {

            entry.m_locator[1].SetMissing();

        } else if (!entry.m_locator[1].IsPresent()) {

            --m_staging_clusterset->m_txcount;

            m_staging_clusterset->m_txcount_oversized -= oversized_tx;

        }

    }

    if (level == 0) ClearChunkData(entry);

}

void GenericClusterImpl::RemoveChunkData(TxGraphImpl& graph) noexcept

{

    for (DepGraphIndex idx : m_linearization) {

        auto& entry = graph.m_entries[m_mapping[idx]];

        graph.ClearChunkData(entry);

    }

}

void SingletonClusterImpl::RemoveChunkData(TxGraphImpl& graph) noexcept

{

    if (GetTxCount() == 0) return;

    auto& entry = graph.m_entries[m_graph_index];

    graph.ClearChunkData(entry);

}

void GenericClusterImpl::Updated(TxGraphImpl& graph, int level, bool rename) noexcept

{

    // Update all the Locators for this Cluster's Entry objects.

    for (DepGraphIndex idx : m_linearization) {

        auto& entry = graph.m_entries[m_mapping[idx]];

        // Discard any potential ChunkData prior to modifying the Cluster (as that could

        // invalidate its ordering).

        if (level == 0 && !rename) graph.ClearChunkData(entry);

        entry.m_locator[level].SetPresent(this, idx);

    }

    // If this is for the main graph (level = 0), and the Cluster's quality is ACCEPTABLE or

    // OPTIMAL, compute its chunking and store its information in the Entry's m_main_lin_index

    // and m_main_chunk_feerate. These fields are only accessed after making the entire graph

    // ACCEPTABLE, so it is pointless to compute these if we haven't reached that quality level

    // yet.

    // When rename=true, this is always performed for level 0, to make sure the values inside the

    // entries remain consistent with the chunk index (otherwise unrelated chunk index operations

    // could cause the index to become corrupted, by inserting elements in the wrong place).

    if (level == 0 && (rename || IsAcceptable())) {

        auto chunking = ChunkLinearizationInfo(m_depgraph, m_linearization);

        LinearizationIndex lin_idx{0};

        /** The sum of all chunk feerate FeeFracs with the same feerate as the current chunk,

         *  up to and including the current chunk. */