txgraph.h

Go to the documentation of this file.

// 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 <compare>
#include <cstdint>
#include <functional>
#include <memory>
#include <optional>
#include <utility>
#include <vector>

#include <util/feefrac.h>

#ifndef BITCOIN_TXGRAPH_H
#define BITCOIN_TXGRAPH_H

static constexpr unsigned MAX_CLUSTER_COUNT_LIMIT{64};

class TxGraph
{
public:
    using GraphIndex = uint32_t;

    class Ref;

    enum class Level {
        TOP, 
        MAIN 
    };

    virtual ~TxGraph() = default;
    virtual void AddTransaction(Ref& arg, const FeePerWeight& feerate) noexcept = 0;
    virtual void RemoveTransaction(const Ref& arg) noexcept = 0;
    virtual void AddDependency(const Ref& parent, const Ref& child) noexcept = 0;
    virtual void SetTransactionFee(const Ref& arg, int64_t fee) noexcept = 0;

    virtual bool DoWork(uint64_t max_cost) noexcept = 0;

    virtual void StartStaging() noexcept = 0;
    virtual void AbortStaging() noexcept = 0;
    virtual void CommitStaging() noexcept = 0;
    virtual bool HaveStaging() const noexcept = 0;

    virtual bool IsOversized(Level level) noexcept = 0;
    virtual bool Exists(const Ref& arg, Level level) noexcept = 0;
    virtual FeePerWeight GetIndividualFeerate(const Ref& arg) noexcept = 0;
    virtual FeePerWeight GetMainChunkFeerate(const Ref& arg) noexcept = 0;
    virtual std::vector<Ref*> GetCluster(const Ref& arg, Level level) noexcept = 0;
    virtual std::vector<Ref*> GetAncestors(const Ref& arg, Level level) noexcept = 0;
    virtual std::vector<Ref*> GetDescendants(const Ref& arg, Level level) noexcept = 0;
    virtual std::vector<Ref*> GetAncestorsUnion(std::span<const Ref* const> args, Level level) noexcept = 0;
    virtual std::vector<Ref*> GetDescendantsUnion(std::span<const Ref* const> args, Level level) noexcept = 0;
    virtual GraphIndex GetTransactionCount(Level level) noexcept = 0;
    virtual std::strong_ordering CompareMainOrder(const Ref& a, const Ref& b) noexcept = 0;
    virtual GraphIndex CountDistinctClusters(std::span<const Ref* const>, Level level) noexcept = 0;
    virtual std::pair<std::vector<FeeFrac>, std::vector<FeeFrac>> GetMainStagingDiagrams() noexcept = 0;
    virtual std::vector<Ref*> Trim() noexcept = 0;

    class BlockBuilder
    {
    protected:
        BlockBuilder() noexcept = default;
    public:
        virtual ~BlockBuilder() = default;
        virtual std::optional<std::pair<std::vector<Ref*>, FeePerWeight>> GetCurrentChunk() noexcept = 0;
        virtual void Include() noexcept = 0;
        virtual void Skip() noexcept = 0;
    };

    virtual std::unique_ptr<BlockBuilder> GetBlockBuilder() noexcept = 0;
    virtual std::pair<std::vector<Ref*>, FeePerWeight> GetWorstMainChunk() noexcept = 0;

    virtual size_t GetMainMemoryUsage() noexcept = 0;

    virtual void SanityCheck() const = 0;

protected:
    // Allow TxGraph::Ref to call UpdateRef and UnlinkRef.
    friend class TxGraph::Ref;
    virtual void UpdateRef(GraphIndex index, Ref& new_location) noexcept = 0;
    virtual void UnlinkRef(GraphIndex index) noexcept = 0;
    // Allow TxGraph implementations (inheriting from it) to access Ref internals.
    static TxGraph*& GetRefGraph(Ref& arg) noexcept { return arg.m_graph; }
    static TxGraph* GetRefGraph(const Ref& arg) noexcept { return arg.m_graph; }
    static GraphIndex& GetRefIndex(Ref& arg) noexcept { return arg.m_index; }
    static GraphIndex GetRefIndex(const Ref& arg) noexcept { return arg.m_index; }

public:
    class Ref
    {
        // Allow TxGraph's GetRefGraph and GetRefIndex to access internals.
        friend class TxGraph;
        TxGraph* m_graph = nullptr;
        GraphIndex m_index = GraphIndex(-1);
    public:
        Ref() noexcept = default;
        virtual ~Ref();
        // Support move-constructing a Ref.
        Ref& operator=(Ref&& other) noexcept = delete;
        Ref(Ref&& other) noexcept;
        // Do not permit copy constructing or copy assignment. A TxGraph entry can have at most one
        // Ref pointing to it.
        Ref& operator=(const Ref&) = delete;
        Ref(const Ref&) = delete;
    };
};

std::unique_ptr<TxGraph> MakeTxGraph(
    unsigned 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;

#endif // BITCOIN_TXGRAPH_H