Inside Bitcoin

2501}
2502
2503std::vector<TxGraph::Ref*> TxGraphImpl::GetDescendantsUnion(std::span<const Ref* const> args, Level level_select) noexcept
2504{
2505    // Apply all dependencies, as the result might be incorrect otherwise.
2506    size_t level = GetSpecifiedLevel(level_select);
2507    ApplyDependencies(level);
2508    // Ancestry cannot be known if unapplied dependencies remain.
2509    Assume(GetClusterSet(level).m_deps_to_add.empty());
2510
2511    // Translate args to matches.
2512    std::vector<std::pair<Cluster*, DepGraphIndex>> matches;
2513    matches.reserve(args.size());
2514    for (auto arg : args) {
2515        Assume(arg);
2516        // Skip empty Refs.
2517        if (GetRefGraph(*arg) == nullptr) continue;
2518        Assume(GetRefGraph(*arg) == this);
2519        // Find the Cluster the argument is in, and skip if none is found.
2520        auto [cluster, cluster_level] = FindClusterAndLevel(GetRefIndex(*arg), level);
2521        if (cluster == nullptr) continue;
2522        // Append to matches.
2523        matches.emplace_back(cluster, m_entries[GetRefIndex(*arg)].m_locator[cluster_level].index);
2524    }
2525    // Group by Cluster.
2526    std::ranges::sort(matches, [](auto& a, auto& b) noexcept { return CompareClusters(a.first, b.first) < 0; });
2527    // Dispatch to the Clusters.
2528    std::span match_span(matches);
2529    std::vector<TxGraph::Ref*> ret;
2530    while (!match_span.empty()) {
2531        match_span.front().first->GetDescendantRefs(*this, match_span, ret);
2532    }
2533    return ret;
2534}
2535
2536std::vector<TxGraph::Ref*> TxGraphImpl::GetCluster(const Ref& arg, Level level_select) noexcept
2537{
2538    // Return the empty vector if the Ref is empty (which may be indicative of the transaction
2539    // having been removed already.
2540    if (GetRefGraph(arg) == nullptr) return {};
2541    Assume(GetRefGraph(arg) == this);
2542    // Apply all removals and dependencies, as the result might be incorrect otherwise.
2543    size_t level = GetSpecifiedLevel(level_select);
2544    ApplyDependencies(level);
2545    // Cluster linearization cannot be known if unapplied dependencies remain.
2546    Assume(GetClusterSet(level).m_deps_to_add.empty());
2547    // Find the Cluster the argument is in, and return the empty vector if it isn't in any.
2548    auto [cluster, cluster_level] = FindClusterAndLevel(GetRefIndex(arg), level);
2549    if (cluster == nullptr) return {};
2550    // Make sure the Cluster has an acceptable quality level, and then dispatch to it.
2551    MakeAcceptable(*cluster, cluster_level);
2552    std::vector<TxGraph::Ref*> ret(cluster->GetTxCount());
2553    cluster->GetClusterRefs(*this, ret, 0);
2554    return ret;
2555}
2556
2557TxGraph::GraphIndex TxGraphImpl::GetTransactionCount(Level level_select) noexcept
2558{
2559    size_t level = GetSpecifiedLevel(level_select);
2560    ApplyRemovals(level);
2561    return GetClusterSet(level).m_txcount;
2562}
2563
2564FeePerWeight TxGraphImpl::GetIndividualFeerate(const Ref& arg) noexcept
2565{
2566    // Return the empty FeePerWeight if the passed Ref is empty.
2567    if (GetRefGraph(arg) == nullptr) return {};
2568    Assume(GetRefGraph(arg) == this);
2569    // Find the cluster the argument is in (the level does not matter as individual feerates will
2570    // be identical if it occurs in both), and return the empty FeePerWeight if it isn't in any.
2571    Cluster* cluster{nullptr};
2572    int level;
2573    for (level = 0; level <= GetTopLevel(); ++level) {
2574        // Apply removals, so that we can correctly report FeePerWeight{} for non-existing
2575        // transactions.
2576        ApplyRemovals(level);
2577        if (m_entries[GetRefIndex(arg)].m_locator[level].IsPresent()) {
2578            cluster = m_entries[GetRefIndex(arg)].m_locator[level].cluster;
2579            break;
2580        }
2581    }
2582    if (cluster == nullptr) return {};
2583    // Dispatch to the Cluster.
2584    return cluster->GetIndividualFeerate(m_entries[GetRefIndex(arg)].m_locator[level].index);
2585}
2586
2587FeePerWeight TxGraphImpl::GetMainChunkFeerate(const Ref& arg) noexcept
2588{
2589    // Return the empty FeePerWeight if the passed Ref is empty.
2590    if (GetRefGraph(arg) == nullptr) return {};
2591    Assume(GetRefGraph(arg) == this);
2592    // Apply all removals and dependencies, as the result might be inaccurate otherwise.
2593    ApplyDependencies(/*level=*/0);
2594    // Chunk feerates cannot be accurately known if unapplied dependencies remain.
2595    Assume(m_main_clusterset.m_deps_to_add.empty());
2596    // Find the cluster the argument is in, and return the empty FeePerWeight if it isn't in any.
2597    auto [cluster, cluster_level] = FindClusterAndLevel(GetRefIndex(arg), /*level=*/0);
2598    if (cluster == nullptr) return {};
2599    // Make sure the Cluster has an acceptable quality level, and then return the transaction's
2600    // chunk feerate.
2601    MakeAcceptable(*cluster, cluster_level);
2602    const auto& entry = m_entries[GetRefIndex(arg)];
2603    return entry.m_main_chunk_feerate;
2604}
2605
2606bool TxGraphImpl::IsOversized(Level level_select) noexcept
2607{
2608    size_t level = GetSpecifiedLevel(level_select);
2609    auto& clusterset = GetClusterSet(level);
2610    if (clusterset.m_oversized.has_value()) {
2611        // Return cached value if known.
2612        return *clusterset.m_oversized;
2613    }
2614    ApplyRemovals(level);
2615    if (clusterset.m_txcount_oversized > 0) {
2616        clusterset.m_oversized = true;
2617    } else {
2618        // Find which Clusters will need to be merged together, as that is where the oversize
2619        // property is assessed.
2620        GroupClusters(level);
2621    }
2622    Assume(clusterset.m_oversized.has_value());
2623    return *clusterset.m_oversized;
2624}
2625
2626void TxGraphImpl::StartStaging() noexcept
2627{
2628    // Staging cannot already exist.
2629    Assume(!m_staging_clusterset.has_value());
2630    // Apply all remaining dependencies in main before creating a staging graph. Once staging
2631    // exists, we cannot merge Clusters anymore (because of interference with Clusters being
2632    // pulled into staging), so to make sure all inspectors are available (if not oversized), do
2633    // all merging work now. Call SplitAll() first, so that even if ApplyDependencies does not do
2634    // any thing due to knowing the result is oversized, splitting is still performed.
2635    SplitAll(0);
2636    ApplyDependencies(0);
2637    // Construct the staging ClusterSet.
2638    m_staging_clusterset.emplace();
2639    // Copy statistics, precomputed data, and to-be-applied dependencies (only if oversized) to
2640    // the new graph. To-be-applied removals will always be empty at this point.
2641    m_staging_clusterset->m_txcount = m_main_clusterset.m_txcount;
2642    m_staging_clusterset->m_txcount_oversized = m_main_clusterset.m_txcount_oversized;
2643    m_staging_clusterset->m_deps_to_add = m_main_clusterset.m_deps_to_add;
2644    m_staging_clusterset->m_group_data = m_main_clusterset.m_group_data;
2645    m_staging_clusterset->m_oversized = m_main_clusterset.m_oversized;
2646    Assume(m_staging_clusterset->m_oversized.has_value());
2647    m_staging_clusterset->m_cluster_usage = 0;
2648}
2649
2650void TxGraphImpl::AbortStaging() noexcept
2651{
2652    // Staging must exist.
2653    Assume(m_staging_clusterset.has_value());
2654    // Mark all removed transactions as Missing (so the staging locator for these transactions
2655    // can be reused if another staging is created).
2656    for (auto idx : m_staging_clusterset->m_removed) {
2657        m_entries[idx].m_locator[1].SetMissing();
2658    }
2659    // Do the same with the non-removed transactions in staging Clusters.
2660    for (int quality = 0; quality < int(QualityLevel::NONE); ++quality) {
2661        for (auto& cluster : m_staging_clusterset->m_clusters[quality]) {
2662            cluster->MakeStagingTransactionsMissing(*this);
2663        }
2664    }
2665    // Destroy the staging ClusterSet.
2666    m_staging_clusterset.reset();
2667    Compact();
2668    if (!m_main_clusterset.m_group_data.has_value()) {
2669        // In case m_oversized in main was kept after a Ref destruction while staging exists, we
2670        // need to re-evaluate m_oversized now.
2671        if (m_main_clusterset.m_to_remove.empty() && m_main_clusterset.m_txcount_oversized > 0) {
2672            // It is possible that a Ref destruction caused a removal in main while staging existed.
2673            // In this case, m_txcount_oversized may be inaccurate.
2674            m_main_clusterset.m_oversized = true;
2675        } else {
2676            m_main_clusterset.m_oversized = std::nullopt;
2677        }
2678    }
2679}
2680
2681void TxGraphImpl::CommitStaging() noexcept
2682{
2683    // Staging must exist.
2684    Assume(m_staging_clusterset.has_value());
2685    Assume(m_main_chunkindex_observers == 0);
2686    // Get rid of removed transactions in staging before moving to main, so they do not need to be
2687    // added to the chunk index there. Doing so is impossible if they were unlinked, and thus have
2688    // no Ref anymore to pass to the fallback comparator.
2689    ApplyRemovals(/*up_to_level=*/1);
2690    // Delete all conflicting Clusters in main, to make place for moving the staging ones
2691    // there. All of these have been copied to staging in PullIn().
2692    auto conflicts = GetConflicts();
2693    for (Cluster* conflict : conflicts) {
2694        conflict->Clear(*this, /*level=*/0);
2695        DeleteCluster(*conflict, /*level=*/0);
2696    }
2697    // Mark the removed transactions as Missing (so the staging locator for these transactions
2698    // can be reused if another staging is created).
2699    for (auto idx : m_staging_clusterset->m_removed) {
2700        m_entries[idx].m_locator[1].SetMissing();
2701    }
2702    // Then move all Clusters in staging to main.
2703    for (int quality = 0; quality < int(QualityLevel::NONE); ++quality) {
2704        auto& stage_sets = m_staging_clusterset->m_clusters[quality];
2705        while (!stage_sets.empty()) {
2706            stage_sets.back()->MoveToMain(*this);
2707        }
2708    }
2709    // Move all statistics, precomputed data, and to-be-applied removals and dependencies.
2710    m_main_clusterset.m_deps_to_add = std::move(m_staging_clusterset->m_deps_to_add);
2711    m_main_clusterset.m_to_remove = std::move(m_staging_clusterset->m_to_remove);
2712    m_main_clusterset.m_group_data = std::move(m_staging_clusterset->m_group_data);
2713    m_main_clusterset.m_oversized = m_staging_clusterset->m_oversized;
2714    m_main_clusterset.m_txcount = m_staging_clusterset->m_txcount;
2715    m_main_clusterset.m_txcount_oversized = m_staging_clusterset->m_txcount_oversized;
2716    // Delete the old staging graph, after all its information was moved to main.
2717    m_staging_clusterset.reset();
2718    Compact();
2719}
2720
2721void GenericClusterImpl::SetFee(TxGraphImpl& graph, int level, DepGraphIndex idx, int64_t fee) noexcept
2722{
2723    // Make sure the specified DepGraphIndex exists in this Cluster.
2724    Assume(m_depgraph.Positions()[idx]);
2725    // Bail out if the fee isn't actually being changed.
2726    if (m_depgraph.FeeRate(idx).fee == fee) return;
2727    // Update the fee, remember that relinearization will be necessary, and update the Entries
2728    // in the same Cluster.
2729    m_depgraph.FeeRate(idx).fee = fee;
2730    if (m_quality == QualityLevel::OVERSIZED_SINGLETON) {
2731        // Nothing to do.
2732    } else if (IsAcceptable()) {
2733        graph.SetClusterQuality(level, m_quality, m_setindex, QualityLevel::NEEDS_RELINEARIZE);
2734    }
2735    Updated(graph, /*level=*/level, /*rename=*/false);
2736}
2737
2738void SingletonClusterImpl::SetFee(TxGraphImpl& graph, int level, DepGraphIndex idx, int64_t fee) noexcept
2739{
2740    Assume(GetTxCount());
2741    Assume(idx == 0);
2742    m_feerate.fee = fee;
2743    Updated(graph, /*level=*/level, /*rename=*/false);
2744}
2745
2746void TxGraphImpl::SetTransactionFee(const Ref& ref, int64_t fee) noexcept
2747{
2748    // Don't do anything if the passed Ref is empty.
2749    if (GetRefGraph(ref) == nullptr) return;
2750    Assume(GetRefGraph(ref) == this);