Inside Bitcoin

2751    Assume(m_main_chunkindex_observers == 0);
2752    // Find the entry, its locator, and inform its Cluster about the new feerate, if any.
2753    auto& entry = m_entries[GetRefIndex(ref)];
2754    for (int level = 0; level < MAX_LEVELS; ++level) {
2755        auto& locator = entry.m_locator[level];
2756        if (locator.IsPresent()) {
2757            locator.cluster->SetFee(*this, level, locator.index, fee);
2758        }
2759    }
2760}
2761
2762std::strong_ordering TxGraphImpl::CompareMainOrder(const Ref& a, const Ref& b) noexcept
2763{
2764    // The references must not be empty.
2765    Assume(GetRefGraph(a) == this);
2766    Assume(GetRefGraph(b) == this);
2767    // Apply dependencies in main.
2768    ApplyDependencies(0);
2769    Assume(m_main_clusterset.m_deps_to_add.empty());
2770    // Make both involved Clusters acceptable, so chunk feerates are relevant.
2771    const auto& entry_a = m_entries[GetRefIndex(a)];
2772    const auto& entry_b = m_entries[GetRefIndex(b)];
2773    const auto& locator_a = entry_a.m_locator[0];
2774    const auto& locator_b = entry_b.m_locator[0];
2775    Assume(locator_a.IsPresent());
2776    Assume(locator_b.IsPresent());
2777    MakeAcceptable(*locator_a.cluster, /*level=*/0);
2778    MakeAcceptable(*locator_b.cluster, /*level=*/0);
2779    // Invoke comparison logic.
2780    return CompareMainTransactions(GetRefIndex(a), GetRefIndex(b));
2781}
2782
2783TxGraph::GraphIndex TxGraphImpl::CountDistinctClusters(std::span<const Ref* const> refs, Level level_select) noexcept
2784{
2785    size_t level = GetSpecifiedLevel(level_select);
2786    ApplyDependencies(level);
2787    auto& clusterset = GetClusterSet(level);
2788    Assume(clusterset.m_deps_to_add.empty());
2789    // Build a vector of Clusters that the specified Refs occur in.
2790    std::vector<Cluster*> clusters;
2791    clusters.reserve(refs.size());
2792    for (const Ref* ref : refs) {
2793        Assume(ref);
2794        if (GetRefGraph(*ref) == nullptr) continue;
2795        Assume(GetRefGraph(*ref) == this);
2796        auto cluster = FindCluster(GetRefIndex(*ref), level);
2797        if (cluster != nullptr) clusters.push_back(cluster);
2798    }
2799    // Count the number of distinct elements in clusters.
2800    std::ranges::sort(clusters, [](Cluster* a, Cluster* b) noexcept { return CompareClusters(a, b) < 0; });
2801    Cluster* last{nullptr};
2802    GraphIndex ret{0};
2803    for (Cluster* cluster : clusters) {
2804        ret += (cluster != last);
2805        last = cluster;
2806    }
2807    return ret;
2808}
2809
2810std::pair<std::vector<FeeFrac>, std::vector<FeeFrac>> TxGraphImpl::GetMainStagingDiagrams() noexcept
2811{
2812    Assume(m_staging_clusterset.has_value());
2813    MakeAllAcceptable(0);
2814    Assume(m_main_clusterset.m_deps_to_add.empty()); // can only fail if main is oversized
2815    MakeAllAcceptable(1);
2816    Assume(m_staging_clusterset->m_deps_to_add.empty()); // can only fail if staging is oversized
2817    // For all Clusters in main which conflict with Clusters in staging (i.e., all that are removed
2818    // by, or replaced in, staging), gather their chunk feerates.
2819    auto main_clusters = GetConflicts();
2820    std::vector<FeeFrac> main_feerates, staging_feerates;
2821    for (Cluster* cluster : main_clusters) {
2822        cluster->AppendChunkFeerates(main_feerates);
2823    }
2824    // Do the same for the Clusters in staging themselves.
2825    for (int quality = 0; quality < int(QualityLevel::NONE); ++quality) {
2826        for (const auto& cluster : m_staging_clusterset->m_clusters[quality]) {
2827            cluster->AppendChunkFeerates(staging_feerates);
2828        }
2829    }
2830    // Sort both by decreasing feerate to obtain diagrams, and return them.
2831    std::ranges::sort(main_feerates, std::greater<ByRatioNegSize<FeeFrac>>{});
2832    std::ranges::sort(staging_feerates, std::greater<ByRatioNegSize<FeeFrac>>{});
2833    return std::make_pair(std::move(main_feerates), std::move(staging_feerates));
2834}
2835
2836void GenericClusterImpl::SanityCheck(const TxGraphImpl& graph, int level) const
2837{
2838    // There must be an m_mapping for each m_depgraph position (including holes).
2839    assert(m_depgraph.PositionRange() == m_mapping.size());
2840    // The linearization for this Cluster must contain every transaction once.
2841    assert(m_depgraph.TxCount() == m_linearization.size());
2842    // Unless a split is to be applied, the cluster cannot have any holes.
2843    if (!NeedsSplitting()) {
2844        assert(m_depgraph.Positions() == SetType::Fill(m_depgraph.TxCount()));
2845    }
2846
2847    // Compute the chunking of m_linearization.
2848    auto linchunking = ChunkLinearizationInfo(m_depgraph, m_linearization);
2849    unsigned chunk_num{0};
2850
2851    // Verify m_linearization.
2852    SetType m_done;
2853    LinearizationIndex linindex{0};
2854    DepGraphIndex chunk_pos{0}; //!< position within the current chunk
2855    assert(m_depgraph.IsAcyclic());
2856    if (m_linearization.empty()) return;
2857    FeeFrac equal_feerate_prefix = linchunking[chunk_num].feerate;
2858    for (auto lin_pos : m_linearization) {
2859        assert(lin_pos < m_mapping.size());
2860        const auto& entry = graph.m_entries[m_mapping[lin_pos]];
2861        // Check that the linearization is topological.
2862        m_done.Set(lin_pos);
2863        if (IsTopological()) {
2864            assert(m_done.IsSupersetOf(m_depgraph.Ancestors(lin_pos)));
2865        }
2866        // Check that the Entry has a locator pointing back to this Cluster & position within it.
2867        assert(entry.m_locator[level].cluster == this);
2868        assert(entry.m_locator[level].index == lin_pos);
2869        // For main-level entries, check linearization position and chunk feerate.
2870        if (level == 0 && IsAcceptable()) {
2871            assert(entry.m_main_lin_index == linindex);
2872            ++linindex;
2873            if (!linchunking[chunk_num].transactions[lin_pos]) {
2874                // First transaction of a new chunk.
2875                ++chunk_num;
2876                assert(chunk_num < linchunking.size());
2877                chunk_pos = 0;
2878                if (ByRatio{linchunking[chunk_num].feerate} < ByRatio{equal_feerate_prefix}) {
2879                    equal_feerate_prefix = linchunking[chunk_num].feerate;
2880                } else {
2881                    assert(ByRatio{linchunking[chunk_num].feerate} == ByRatio{equal_feerate_prefix});
2882                    equal_feerate_prefix += linchunking[chunk_num].feerate;
2883                }
2884            }
2885            assert(entry.m_main_chunk_feerate == linchunking[chunk_num].feerate);
2886            assert(entry.m_main_equal_feerate_chunk_prefix_size == equal_feerate_prefix.size);
2887            // Verify that an entry in the chunk index exists for every chunk-ending transaction.
2888            ++chunk_pos;
2889            if (graph.m_main_clusterset.m_to_remove.empty()) {
2890                bool is_chunk_end = (chunk_pos == linchunking[chunk_num].transactions.Count());
2891                assert((entry.m_main_chunkindex_iterator != graph.m_main_chunkindex.end()) == is_chunk_end);
2892                if (is_chunk_end) {
2893                    auto& chunk_data = *entry.m_main_chunkindex_iterator;
2894                    if (m_done == m_depgraph.Positions() && chunk_pos == 1) {
2895                        assert(chunk_data.m_chunk_count == LinearizationIndex(-1));
2896                    } else {
2897                        assert(chunk_data.m_chunk_count == chunk_pos);
2898                    }
2899                }
2900            }
2901            // If this Cluster has an acceptable quality level, its chunks must be connected.
2902            assert(m_depgraph.IsConnected(linchunking[chunk_num].transactions));
2903        }
2904    }
2905    // Verify that each element of m_depgraph occurred in m_linearization.
2906    assert(m_done == m_depgraph.Positions());
2907}
2908
2909void SingletonClusterImpl::SanityCheck(const TxGraphImpl& graph, int level) const
2910{
2911    // All singletons are optimal, oversized, or need splitting.
2912    Assume(IsOptimal() || IsOversized() || NeedsSplitting());
2913    if (GetTxCount()) {
2914        const auto& entry = graph.m_entries[m_graph_index];
2915        // Check that the Entry has a locator pointing back to this Cluster & position within it.
2916        assert(entry.m_locator[level].cluster == this);
2917        assert(entry.m_locator[level].index == 0);
2918        // For main-level entries, check linearization position and chunk feerate.
2919        if (level == 0 && IsAcceptable()) {
2920            assert(entry.m_main_lin_index == 0);
2921            assert(entry.m_main_chunk_feerate == m_feerate);
2922            assert(entry.m_main_equal_feerate_chunk_prefix_size == m_feerate.size);
2923            if (graph.m_main_clusterset.m_to_remove.empty()) {
2924                assert(entry.m_main_chunkindex_iterator != graph.m_main_chunkindex.end());
2925                auto& chunk_data = *entry.m_main_chunkindex_iterator;
2926                assert(chunk_data.m_chunk_count == LinearizationIndex(-1));
2927            }
2928        }
2929    }
2930}
2931
2932void TxGraphImpl::SanityCheck() const
2933{
2934    /** Which GraphIndexes ought to occur in m_unlinked, based on m_entries. */
2935    std::set<GraphIndex> expected_unlinked;
2936    /** Which Clusters ought to occur in ClusterSet::m_clusters, based on m_entries. */
2937    std::set<const Cluster*> expected_clusters[MAX_LEVELS];
2938    /** Which GraphIndexes ought to occur in ClusterSet::m_removed, based on m_entries. */
2939    std::set<GraphIndex> expected_removed[MAX_LEVELS];
2940    /** Which Cluster::m_sequence values have been encountered. */
2941    std::set<uint64_t> sequences;
2942    /** Which Clusters are live in ClusterSet::m_clusters up to the level being checked. */
2943    std::set<const Cluster*> live_clusters;
2944    /** Which GraphIndexes ought to occur in m_main_chunkindex, based on m_entries. */
2945    std::set<GraphIndex> expected_chunkindex;
2946    /** Whether compaction is possible in the current state. */
2947    bool compact_possible{true};
2948
2949    // Go over all Entry objects in m_entries.
2950    for (GraphIndex idx = 0; idx < m_entries.size(); ++idx) {
2951        const auto& entry = m_entries[idx];
2952        if (entry.m_ref == nullptr) {
2953            // Unlinked Entry must have indexes appear in m_unlinked.
2954            expected_unlinked.insert(idx);
2955        } else {
2956            // Every non-unlinked Entry must have a Ref that points back to it.
2957            assert(GetRefGraph(*entry.m_ref) == this);
2958            assert(GetRefIndex(*entry.m_ref) == idx);
2959        }
2960        if (entry.m_main_chunkindex_iterator != m_main_chunkindex.end()) {
2961            // Remember which entries we see a chunkindex entry for.
2962            assert(entry.m_locator[0].IsPresent());
2963            expected_chunkindex.insert(idx);
2964        }
2965        // Verify the Entry m_locators.
2966        bool was_present{false}, was_removed{false};
2967        for (int level = 0; level < MAX_LEVELS; ++level) {
2968            const auto& locator = entry.m_locator[level];
2969            // Every Locator must be in exactly one of these 3 states.
2970            assert(locator.IsMissing() + locator.IsRemoved() + locator.IsPresent() == 1);
2971            if (locator.IsPresent()) {
2972                // Once removed, a transaction cannot be revived.
2973                assert(!was_removed);
2974                // Verify that the Cluster agrees with where the Locator claims the transaction is.
2975                assert(locator.cluster->GetClusterEntry(locator.index) == idx);
2976                // Remember that we expect said Cluster to appear in the ClusterSet::m_clusters.
2977                expected_clusters[level].insert(locator.cluster);
2978                was_present = true;
2979            } else if (locator.IsRemoved()) {
2980                // Level 0 (main) cannot have IsRemoved locators (IsMissing there means non-existing).
2981                assert(level > 0);
2982                // A Locator can only be IsRemoved if it was IsPresent before, and only once.
2983                assert(was_present && !was_removed);
2984                // Remember that we expect this GraphIndex to occur in the ClusterSet::m_removed.
2985                expected_removed[level].insert(idx);
2986                was_removed = true;
2987            }
2988        }
2989    }
2990
2991    // For all levels (0 = main, 1 = staged)...
2992    for (int level = 0; level <= GetTopLevel(); ++level) {
2993        assert(level < MAX_LEVELS);
2994        auto& clusterset = GetClusterSet(level);
2995        std::set<const Cluster*> actual_clusters;
2996        size_t recomputed_cluster_usage{0};
2997
2998        // For all quality levels...
2999        for (int qual = 0; qual < int(QualityLevel::NONE); ++qual) {
3000            QualityLevel quality{qual};