Inside Bitcoin

751            }
752            if (exists) {
753                auto& clusterset = GetClusterSet(level);
754                clusterset.m_to_remove.push_back(idx);
755                // Force recomputation of grouping data.
756                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                if (level == GetTopLevel() && clusterset.m_oversized == true) {
763                    clusterset.m_oversized = std::nullopt;
764                }
765            }
766        }
767        m_unlinked.push_back(idx);
768        if (!exists_anywhere) Compact();
769    }
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    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
835TxGraphImpl::ClusterSet& TxGraphImpl::GetClusterSet(int level) noexcept
836{
837    if (level == 0) return m_main_clusterset;
838    Assume(level == 1);
839    Assume(m_staging_clusterset.has_value());
840    return *m_staging_clusterset;
841}
842
843const TxGraphImpl::ClusterSet& TxGraphImpl::GetClusterSet(int level) const noexcept
844{
845    if (level == 0) return m_main_clusterset;
846    Assume(level == 1);
847    Assume(m_staging_clusterset.has_value());
848    return *m_staging_clusterset;
849}
850
851/** Implementation of the TxGraph::BlockBuilder interface. */
852class 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
870public:
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
881void TxGraphImpl::ClearChunkData(Entry& entry) noexcept
882{
883    if (entry.m_main_chunkindex_iterator != m_main_chunkindex.end()) {
884        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        m_main_chunkindex_discarded.emplace_back(m_main_chunkindex.extract(entry.m_main_chunkindex_iterator));
888        entry.m_main_chunkindex_iterator = m_main_chunkindex.end();
889    }
890}
891
892void TxGraphImpl::CreateChunkData(GraphIndex idx, LinearizationIndex chunk_count) noexcept
893{
894    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    Assume(entry.m_ref != nullptr);
898    if (!m_main_chunkindex_discarded.empty()) {
899        // Reuse an discarded node handle.
900        auto& node = m_main_chunkindex_discarded.back().value();
901        node.m_graph_index = idx;
902        node.m_chunk_count = chunk_count;
903        auto insert_result = m_main_chunkindex.insert(std::move(m_main_chunkindex_discarded.back()));
904        Assume(insert_result.inserted);
905        entry.m_main_chunkindex_iterator = insert_result.position;
906        m_main_chunkindex_discarded.pop_back();
907    } else {
908        // Construct a new entry.
909        auto emplace_result = m_main_chunkindex.emplace(idx, chunk_count);
910        Assume(emplace_result.second);
911        entry.m_main_chunkindex_iterator = emplace_result.first;
912    }
913}
914
915size_t GenericClusterImpl::TotalMemoryUsage() const noexcept
916{
917    return // Dynamic memory allocated in this Cluster.
918           memusage::DynamicUsage(m_mapping) + memusage::DynamicUsage(m_linearization) +
919           // Dynamic memory usage inside m_depgraph.
920           m_depgraph.DynamicMemoryUsage() +
921           // Memory usage of the allocated Cluster itself.
922           memusage::MallocUsage(sizeof(GenericClusterImpl)) +
923           // Memory usage of the ClusterSet::m_clusters entry.
924           sizeof(std::unique_ptr<Cluster>);
925}
926
927size_t SingletonClusterImpl::TotalMemoryUsage() const noexcept
928{
929    return // Memory usage of the allocated SingletonClusterImpl itself.
930           memusage::MallocUsage(sizeof(SingletonClusterImpl)) +
931           // Memory usage of the ClusterSet::m_clusters entry.
932           sizeof(std::unique_ptr<Cluster>);
933}
934
935uint64_t GenericClusterImpl::GetTotalTxSize() const noexcept
936{
937    uint64_t ret{0};
938    for (auto i : m_linearization) {
939        ret += m_depgraph.FeeRate(i).size;
940    }
941    return ret;
942}
943
944DepGraphIndex GenericClusterImpl::AppendTransaction(GraphIndex graph_idx, FeePerWeight feerate) noexcept
945{
946    Assume(graph_idx != GraphIndex(-1));
947    auto ret = m_depgraph.AddTransaction(feerate);
948    m_mapping.push_back(graph_idx);
949    m_linearization.push_back(ret);
950    return ret;
951}
952
953DepGraphIndex SingletonClusterImpl::AppendTransaction(GraphIndex graph_idx, FeePerWeight feerate) noexcept
954{
955    Assume(!GetTxCount());
956    m_graph_index = graph_idx;
957    m_feerate = feerate;
958    return 0;
959}
960
961void GenericClusterImpl::AddDependencies(SetType parents, DepGraphIndex child) noexcept
962{
963    m_depgraph.AddDependencies(parents, child);
964}
965
966void SingletonClusterImpl::AddDependencies(SetType parents, DepGraphIndex child) noexcept
967{
968    // Singletons cannot have any dependencies.
969    Assume(child == 0);
970    Assume(parents == SetType{} || parents == SetType::Fill(0));
971}
972
973void GenericClusterImpl::ExtractTransactions(const std::function<void (DepGraphIndex, GraphIndex, FeePerWeight)>& visit1_fn, const std::function<void (DepGraphIndex, GraphIndex, SetType)>& visit2_fn) noexcept
974{
975    for (auto pos : m_linearization) {
976        visit1_fn(pos, m_mapping[pos], FeePerWeight::FromFeeFrac(m_depgraph.FeeRate(pos)));
977    }
978    for (auto pos : m_linearization) {
979        visit2_fn(pos, m_mapping[pos], m_depgraph.GetReducedParents(pos));
980    }
981    // Purge this Cluster, now that everything has been moved.
982    m_depgraph = DepGraph<SetType>{};
983    m_linearization.clear();
984    m_mapping.clear();
985}
986
987void SingletonClusterImpl::ExtractTransactions(const std::function<void (DepGraphIndex, GraphIndex, FeePerWeight)>& visit1_fn, const std::function<void (DepGraphIndex, GraphIndex, SetType)>& visit2_fn) noexcept
988{
989    if (GetTxCount()) {
990        visit1_fn(0, m_graph_index, m_feerate);
991        visit2_fn(0, m_graph_index, SetType{});
992        m_graph_index = NO_GRAPH_INDEX;
993    }
994}
995
996int GenericClusterImpl::GetLevel(const TxGraphImpl& graph) const noexcept
997{
998    // GetLevel() does not work for empty Clusters.
999    if (!Assume(!m_linearization.empty())) return -1;
1000