Inside Bitcoin

2251    cluster_ptr->Updated(*this, /*level=*/level, /*rename=*/false);
2252    clusterset.m_cluster_usage += cluster_ptr->TotalMemoryUsage();
2253    ++clusterset.m_txcount;
2254    // Deal with individually oversized transactions.
2255    if (oversized) {
2256        ++clusterset.m_txcount_oversized;
2257        clusterset.m_oversized = true;
2258        clusterset.m_group_data = std::nullopt;
2259    }
2260}
2261
2262void TxGraphImpl::RemoveTransaction(const Ref& arg) noexcept
2263{
2264    // Don't do anything if the Ref is empty (which may be indicative of the transaction already
2265    // having been removed).
2266    if (GetRefGraph(arg) == nullptr) return;
2267    Assume(GetRefGraph(arg) == this);
2268    Assume(m_main_chunkindex_observers == 0 || GetTopLevel() != 0);
2269    // Find the Cluster the transaction is in, and stop if it isn't in any.
2270    int level = GetTopLevel();
2271    auto cluster = FindCluster(GetRefIndex(arg), level);
2272    if (cluster == nullptr) return;
2273    // Remember that the transaction is to be removed.
2274    auto& clusterset = GetClusterSet(level);
2275    clusterset.m_to_remove.push_back(GetRefIndex(arg));
2276    // Wipe m_group_data (as it will need to be recomputed).
2277    clusterset.m_group_data.reset();
2278    if (clusterset.m_oversized == true) clusterset.m_oversized = std::nullopt;
2279}
2280
2281void TxGraphImpl::AddDependency(const Ref& parent, const Ref& child) noexcept
2282{
2283    // Don't do anything if either Ref is empty (which may be indicative of it having already been
2284    // removed).
2285    if (GetRefGraph(parent) == nullptr || GetRefGraph(child) == nullptr) return;
2286    Assume(GetRefGraph(parent) == this && GetRefGraph(child) == this);
2287    Assume(m_main_chunkindex_observers == 0 || GetTopLevel() != 0);
2288    // Don't do anything if this is a dependency on self.
2289    if (GetRefIndex(parent) == GetRefIndex(child)) return;
2290    // Find the Cluster the parent and child transaction are in, and stop if either appears to be
2291    // already removed.
2292    int level = GetTopLevel();
2293    auto par_cluster = FindCluster(GetRefIndex(parent), level);
2294    if (par_cluster == nullptr) return;
2295    auto chl_cluster = FindCluster(GetRefIndex(child), level);
2296    if (chl_cluster == nullptr) return;
2297    // Remember that this dependency is to be applied.
2298    auto& clusterset = GetClusterSet(level);
2299    clusterset.m_deps_to_add.emplace_back(GetRefIndex(parent), GetRefIndex(child));
2300    // Wipe m_group_data (as it will need to be recomputed).
2301    clusterset.m_group_data.reset();
2302    if (clusterset.m_oversized == false) clusterset.m_oversized = std::nullopt;
2303}
2304
2305bool TxGraphImpl::Exists(const Ref& arg, Level level_select) noexcept
2306{
2307    if (GetRefGraph(arg) == nullptr) return false;
2308    Assume(GetRefGraph(arg) == this);
2309    size_t level = GetSpecifiedLevel(level_select);
2310    // Make sure the transaction isn't scheduled for removal.
2311    ApplyRemovals(level);
2312    auto cluster = FindCluster(GetRefIndex(arg), level);
2313    return cluster != nullptr;
2314}
2315
2316void GenericClusterImpl::GetAncestorRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept
2317{
2318    /** The union of all ancestors to be returned. */
2319    SetType ancestors_union;
2320    // Process elements from the front of args, as long as they apply.
2321    while (!args.empty()) {
2322        if (args.front().first != this) break;
2323        ancestors_union |= m_depgraph.Ancestors(args.front().second);
2324        args = args.subspan(1);
2325    }
2326    Assume(ancestors_union.Any());
2327    // Translate all ancestors (in arbitrary order) to Refs (if they have any), and return them.
2328    for (auto idx : ancestors_union) {
2329        const auto& entry = graph.m_entries[m_mapping[idx]];
2330        Assume(entry.m_ref != nullptr);
2331        output.push_back(entry.m_ref);
2332    }
2333}
2334
2335void SingletonClusterImpl::GetAncestorRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept
2336{
2337    Assume(GetTxCount());
2338    while (!args.empty()) {
2339        if (args.front().first != this) break;
2340        args = args.subspan(1);
2341    }
2342    const auto& entry = graph.m_entries[m_graph_index];
2343    Assume(entry.m_ref != nullptr);
2344    output.push_back(entry.m_ref);
2345}
2346
2347void GenericClusterImpl::GetDescendantRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept
2348{
2349    /** The union of all descendants to be returned. */
2350    SetType descendants_union;
2351    // Process elements from the front of args, as long as they apply.
2352    while (!args.empty()) {
2353        if (args.front().first != this) break;
2354        descendants_union |= m_depgraph.Descendants(args.front().second);
2355        args = args.subspan(1);
2356    }
2357    Assume(descendants_union.Any());
2358    // Translate all descendants (in arbitrary order) to Refs (if they have any), and return them.
2359    for (auto idx : descendants_union) {
2360        const auto& entry = graph.m_entries[m_mapping[idx]];
2361        Assume(entry.m_ref != nullptr);
2362        output.push_back(entry.m_ref);
2363    }
2364}
2365
2366void SingletonClusterImpl::GetDescendantRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept
2367{
2368    // In a singleton cluster, the ancestors or descendants are always just the entire cluster.
2369    GetAncestorRefs(graph, args, output);
2370}
2371
2372bool GenericClusterImpl::GetClusterRefs(TxGraphImpl& graph, std::span<TxGraph::Ref*> range, LinearizationIndex start_pos) noexcept
2373{
2374    // Translate the transactions in the Cluster (in linearization order, starting at start_pos in
2375    // the linearization) to Refs, and fill them in range.
2376    for (auto& ref : range) {
2377        Assume(start_pos < m_linearization.size());
2378        const auto& entry = graph.m_entries[m_mapping[m_linearization[start_pos++]]];
2379        Assume(entry.m_ref != nullptr);
2380        ref = entry.m_ref;
2381    }
2382    // Return whether start_pos has advanced to the end of the Cluster.
2383    return start_pos == m_linearization.size();
2384}
2385
2386bool SingletonClusterImpl::GetClusterRefs(TxGraphImpl& graph, std::span<TxGraph::Ref*> range, LinearizationIndex start_pos) noexcept
2387{
2388    Assume(!range.empty());
2389    Assume(GetTxCount());
2390    Assume(start_pos == 0);
2391    const auto& entry = graph.m_entries[m_graph_index];
2392    Assume(entry.m_ref != nullptr);
2393    range[0] = entry.m_ref;
2394    return true;
2395}
2396
2397FeePerWeight GenericClusterImpl::GetIndividualFeerate(DepGraphIndex idx) noexcept
2398{
2399    return FeePerWeight::FromFeeFrac(m_depgraph.FeeRate(idx));
2400}
2401
2402FeePerWeight SingletonClusterImpl::GetIndividualFeerate(DepGraphIndex idx) noexcept
2403{
2404    Assume(GetTxCount());
2405    Assume(idx == 0);
2406    return m_feerate;
2407}
2408
2409void GenericClusterImpl::MakeStagingTransactionsMissing(TxGraphImpl& graph) noexcept
2410{
2411    // Mark all transactions of a Cluster missing, needed when aborting staging, so that the
2412    // corresponding Locators don't retain references into aborted Clusters.
2413    for (auto ci : m_linearization) {
2414        GraphIndex idx = m_mapping[ci];
2415        auto& entry = graph.m_entries[idx];
2416        entry.m_locator[1].SetMissing();
2417    }
2418}
2419
2420void SingletonClusterImpl::MakeStagingTransactionsMissing(TxGraphImpl& graph) noexcept
2421{
2422    if (GetTxCount()) {
2423        auto& entry = graph.m_entries[m_graph_index];
2424        entry.m_locator[1].SetMissing();
2425    }
2426}
2427
2428std::vector<TxGraph::Ref*> TxGraphImpl::GetAncestors(const Ref& arg, Level level_select) noexcept
2429{
2430    // Return the empty vector if the Ref is empty.
2431    if (GetRefGraph(arg) == nullptr) return {};
2432    Assume(GetRefGraph(arg) == this);
2433    // Apply all removals and dependencies, as the result might be incorrect otherwise.
2434    size_t level = GetSpecifiedLevel(level_select);
2435    ApplyDependencies(level);
2436    // Ancestry cannot be known if unapplied dependencies remain.
2437    Assume(GetClusterSet(level).m_deps_to_add.empty());
2438    // Find the Cluster the argument is in, and return the empty vector if it isn't in any.
2439    auto [cluster, cluster_level] = FindClusterAndLevel(GetRefIndex(arg), level);
2440    if (cluster == nullptr) return {};
2441    // Dispatch to the Cluster.
2442    std::pair<Cluster*, DepGraphIndex> match = {cluster, m_entries[GetRefIndex(arg)].m_locator[cluster_level].index};
2443    auto matches = std::span(&match, 1);
2444    std::vector<TxGraph::Ref*> ret;
2445    cluster->GetAncestorRefs(*this, matches, ret);
2446    return ret;
2447}
2448
2449std::vector<TxGraph::Ref*> TxGraphImpl::GetDescendants(const Ref& arg, Level level_select) noexcept
2450{
2451    // Return the empty vector if the Ref is empty.
2452    if (GetRefGraph(arg) == nullptr) return {};
2453    Assume(GetRefGraph(arg) == this);
2454    // Apply all removals and dependencies, as the result might be incorrect otherwise.
2455    size_t level = GetSpecifiedLevel(level_select);
2456    ApplyDependencies(level);
2457    // Ancestry cannot be known if unapplied dependencies remain.
2458    Assume(GetClusterSet(level).m_deps_to_add.empty());
2459    // Find the Cluster the argument is in, and return the empty vector if it isn't in any.
2460    auto [cluster, cluster_level] = FindClusterAndLevel(GetRefIndex(arg), level);
2461    if (cluster == nullptr) return {};
2462    // Dispatch to the Cluster.
2463    std::pair<Cluster*, DepGraphIndex> match = {cluster, m_entries[GetRefIndex(arg)].m_locator[cluster_level].index};
2464    auto matches = std::span(&match, 1);
2465    std::vector<TxGraph::Ref*> ret;
2466    cluster->GetDescendantRefs(*this, matches, ret);
2467    return ret;
2468}
2469
2470std::vector<TxGraph::Ref*> TxGraphImpl::GetAncestorsUnion(std::span<const Ref* const> args, Level level_select) noexcept
2471{
2472    // Apply all dependencies, as the result might be incorrect otherwise.
2473    size_t level = GetSpecifiedLevel(level_select);
2474    ApplyDependencies(level);
2475    // Ancestry cannot be known if unapplied dependencies remain.
2476    Assume(GetClusterSet(level).m_deps_to_add.empty());
2477
2478    // Translate args to matches.
2479    std::vector<std::pair<Cluster*, DepGraphIndex>> matches;
2480    matches.reserve(args.size());
2481    for (auto arg : args) {
2482        Assume(arg);
2483        // Skip empty Refs.
2484        if (GetRefGraph(*arg) == nullptr) continue;
2485        Assume(GetRefGraph(*arg) == this);
2486        // Find the Cluster the argument is in, and skip if none is found.
2487        auto [cluster, cluster_level] = FindClusterAndLevel(GetRefIndex(*arg), level);
2488        if (cluster == nullptr) continue;
2489        // Append to matches.
2490        matches.emplace_back(cluster, m_entries[GetRefIndex(*arg)].m_locator[cluster_level].index);
2491    }
2492    // Group by Cluster.
2493    std::ranges::sort(matches, [](auto& a, auto& b) noexcept { return CompareClusters(a.first, b.first) < 0; });
2494    // Dispatch to the Clusters.
2495    std::span match_span(matches);
2496    std::vector<TxGraph::Ref*> ret;
2497    while (!match_span.empty()) {
2498        match_span.front().first->GetAncestorRefs(*this, match_span, ret);
2499    }
2500    return ret;