Inside Bitcoin

1501    for (Cluster* new_cluster : new_clusters) {
1502        new_cluster->Updated(graph, /*level=*/level, /*rename=*/false);
1503        new_cluster->Compact();
1504        graph.GetClusterSet(level).m_cluster_usage += new_cluster->TotalMemoryUsage();
1505    }
1506    // Wipe this Cluster, and return that it needs to be deleted.
1507    m_depgraph = DepGraph<SetType>{};
1508    m_mapping.clear();
1509    m_linearization.clear();
1510    return true;
1511}
1512
1513bool SingletonClusterImpl::Split(TxGraphImpl& graph, int level) noexcept
1514{
1515    Assume(NeedsSplitting());
1516    Assume(!GetTxCount());
1517    graph.GetClusterSet(level).m_cluster_usage -= TotalMemoryUsage();
1518    return true;
1519}
1520
1521void GenericClusterImpl::Merge(TxGraphImpl& graph, int level, Cluster& other) noexcept
1522{
1523    /** Vector to store the positions in this Cluster for each position in other. */
1524    std::vector<DepGraphIndex> remap(other.GetDepGraphIndexRange());
1525    // Iterate over all transactions in the other Cluster (the one being absorbed).
1526    other.ExtractTransactions([&](DepGraphIndex pos, GraphIndex idx, FeePerWeight feerate) noexcept {
1527        // Copy the transaction into this Cluster, and remember its position.
1528        auto new_pos = m_depgraph.AddTransaction(feerate);
1529        // Since this cluster must have been made hole-free before being merged into, all added
1530        // transactions should appear at the end.
1531        Assume(new_pos == m_mapping.size());
1532        remap[pos] = new_pos;
1533        m_mapping.push_back(idx);
1534        m_linearization.push_back(new_pos);
1535    }, [&](DepGraphIndex pos, GraphIndex idx, SetType other_parents) noexcept {
1536        // Copy the transaction's dependencies, translating them using remap.
1537        SetType parents;
1538        for (auto par : other_parents) {
1539            parents.Set(remap[par]);
1540        }
1541        m_depgraph.AddDependencies(parents, remap[pos]);
1542        // Update the transaction's Locator. There is no need to call Updated() to update chunk
1543        // feerates, as Updated() will be invoked by Cluster::ApplyDependencies on the resulting
1544        // merged Cluster later anyway.
1545        auto& entry = graph.m_entries[idx];
1546        // Discard any potential ChunkData prior to modifying the Cluster (as that could
1547        // invalidate its ordering).
1548        if (level == 0) graph.ClearChunkData(entry);
1549        entry.m_locator[level].SetPresent(this, remap[pos]);
1550    });
1551}
1552
1553void SingletonClusterImpl::Merge(TxGraphImpl&, int, Cluster&) noexcept
1554{
1555    // Nothing can be merged into a singleton; it should have been converted to GenericClusterImpl first.
1556    Assume(false);
1557}
1558
1559void GenericClusterImpl::ApplyDependencies(TxGraphImpl& graph, int level, std::span<std::pair<GraphIndex, GraphIndex>> to_apply) noexcept
1560{
1561    // Sort the list of dependencies to apply by child, so those can be applied in batch.
1562    std::ranges::sort(to_apply, [](auto& a, auto& b) { return a.second < b.second; });
1563    // Iterate over groups of to-be-added dependencies with the same child.
1564    auto it = to_apply.begin();
1565    while (it != to_apply.end()) {
1566        auto& first_child = graph.m_entries[it->second].m_locator[level];
1567        const auto child_idx = first_child.index;
1568        // Iterate over all to-be-added dependencies within that same child, gather the relevant
1569        // parents.
1570        SetType parents;
1571        while (it != to_apply.end()) {
1572            auto& child = graph.m_entries[it->second].m_locator[level];
1573            auto& parent = graph.m_entries[it->first].m_locator[level];
1574            Assume(child.cluster == this && parent.cluster == this);
1575            if (child.index != child_idx) break;
1576            parents.Set(parent.index);
1577            ++it;
1578        }
1579        // Push all dependencies to the underlying DepGraph. Note that this is O(N) in the size of
1580        // the cluster, regardless of the number of parents being added, so batching them together
1581        // has a performance benefit.
1582        m_depgraph.AddDependencies(parents, child_idx);
1583    }
1584
1585    // Finally set the cluster to NEEDS_FIX, so its linearization is fixed the next time it is
1586    // attempted to be made ACCEPTABLE.
1587    Assume(!NeedsSplitting());
1588    Assume(!IsOversized());
1589    graph.SetClusterQuality(level, m_quality, m_setindex, QualityLevel::NEEDS_FIX);
1590
1591    // Finally push the changes to graph.m_entries.
1592    Updated(graph, /*level=*/level, /*rename=*/false);
1593}
1594
1595void SingletonClusterImpl::ApplyDependencies(TxGraphImpl&, int, std::span<std::pair<GraphIndex, GraphIndex>>) noexcept
1596{
1597    // Nothing can actually be applied.
1598    Assume(false);
1599}
1600
1601TxGraphImpl::~TxGraphImpl() noexcept
1602{
1603    // If Refs outlive the TxGraphImpl they refer to, unlink them, so that their destructor does not
1604    // try to reach into a non-existing TxGraphImpl anymore.
1605    for (auto& entry : m_entries) {
1606        if (entry.m_ref != nullptr) {
1607            GetRefGraph(*entry.m_ref) = nullptr;
1608        }
1609    }
1610}
1611
1612std::unique_ptr<Cluster> TxGraphImpl::ExtractCluster(int level, QualityLevel quality, ClusterSetIndex setindex) noexcept
1613{
1614    Assume(quality != QualityLevel::NONE);
1615
1616    auto& clusterset = GetClusterSet(level);
1617    auto& quality_clusters = clusterset.m_clusters[int(quality)];
1618    Assume(setindex < quality_clusters.size());
1619
1620    // Extract the Cluster-owning unique_ptr.
1621    std::unique_ptr<Cluster> ret = std::move(quality_clusters[setindex]);
1622    ret->m_quality = QualityLevel::NONE;
1623    ret->m_setindex = ClusterSetIndex(-1);
1624
1625    // Clean up space in quality_cluster.
1626    auto max_setindex = quality_clusters.size() - 1;
1627    if (setindex != max_setindex) {
1628        // If the cluster was not the last element of quality_clusters, move that to take its place.
1629        quality_clusters.back()->m_setindex = setindex;
1630        quality_clusters[setindex] = std::move(quality_clusters.back());
1631    }
1632    // The last element of quality_clusters is now unused; drop it.
1633    quality_clusters.pop_back();
1634
1635    return ret;
1636}
1637
1638ClusterSetIndex TxGraphImpl::InsertCluster(int level, std::unique_ptr<Cluster>&& cluster, QualityLevel quality) noexcept
1639{
1640    // Cannot insert with quality level NONE (as that would mean not inserted).
1641    Assume(quality != QualityLevel::NONE);
1642    // The passed-in Cluster must not currently be in the TxGraphImpl.
1643    Assume(cluster->m_quality == QualityLevel::NONE);
1644
1645    // Append it at the end of the relevant TxGraphImpl::m_cluster.
1646    auto& clusterset = GetClusterSet(level);
1647    auto& quality_clusters = clusterset.m_clusters[int(quality)];
1648    ClusterSetIndex ret = quality_clusters.size();
1649    cluster->m_quality = quality;
1650    cluster->m_setindex = ret;
1651    quality_clusters.push_back(std::move(cluster));
1652    return ret;
1653}
1654
1655void TxGraphImpl::SetClusterQuality(int level, QualityLevel old_quality, ClusterSetIndex old_index, QualityLevel new_quality) noexcept
1656{
1657    Assume(new_quality != QualityLevel::NONE);
1658
1659    // Don't do anything if the quality did not change.
1660    if (old_quality == new_quality) return;
1661    // Extract the cluster from where it currently resides.
1662    auto cluster_ptr = ExtractCluster(level, old_quality, old_index);
1663    // And re-insert it where it belongs.
1664    InsertCluster(level, std::move(cluster_ptr), new_quality);
1665}
1666
1667void TxGraphImpl::DeleteCluster(Cluster& cluster, int level) noexcept
1668{
1669    // Extract the cluster from where it currently resides.
1670    auto cluster_ptr = ExtractCluster(level, cluster.m_quality, cluster.m_setindex);
1671    // And throw it away.
1672    cluster_ptr.reset();
1673}
1674
1675std::pair<Cluster*, int> TxGraphImpl::FindClusterAndLevel(GraphIndex idx, int level) const noexcept
1676{
1677    Assume(level >= 0 && level <= GetTopLevel());
1678    auto& entry = m_entries[idx];
1679    // Search the entry's locators from top to bottom.
1680    for (int l = level; l >= 0; --l) {
1681        // If the locator is missing, dig deeper; it may exist at a lower level and therefore be
1682        // implicitly existing at this level too.
1683        if (entry.m_locator[l].IsMissing()) continue;
1684        // If the locator has the entry marked as explicitly removed, stop.
1685        if (entry.m_locator[l].IsRemoved()) break;
1686        // Otherwise, we have found the topmost ClusterSet that contains this entry.
1687        return {entry.m_locator[l].cluster, l};
1688    }
1689    // If no non-empty locator was found, or an explicitly removed was hit, return nothing.
1690    return {nullptr, -1};
1691}
1692
1693Cluster* TxGraphImpl::PullIn(Cluster* cluster, int level) noexcept
1694{
1695    int to_level = GetTopLevel();
1696    Assume(to_level == 1);
1697    Assume(level <= to_level);
1698    // Copy the Cluster from main to staging, if it's not already there.
1699    if (level == 0) {
1700        // Make the Cluster Acceptable before copying. This isn't strictly necessary, but doing it
1701        // now avoids doing double work later.
1702        MakeAcceptable(*cluster, level);
1703        cluster = cluster->CopyToStaging(*this);
1704    }
1705    return cluster;
1706}
1707
1708void TxGraphImpl::ApplyRemovals(int up_to_level) noexcept
1709{
1710    Assume(up_to_level >= 0 && up_to_level <= GetTopLevel());
1711    for (int level = 0; level <= up_to_level; ++level) {
1712        auto& clusterset = GetClusterSet(level);
1713        auto& to_remove = clusterset.m_to_remove;
1714        // Skip if there is nothing to remove in this level.
1715        if (to_remove.empty()) continue;
1716        // Pull in all Clusters that are not in staging.
1717        if (level == 1) {
1718            for (GraphIndex index : to_remove) {
1719                auto [cluster, cluster_level] = FindClusterAndLevel(index, level);
1720                if (cluster != nullptr) PullIn(cluster, cluster_level);
1721            }
1722        }
1723        // Group the set of to-be-removed entries by Cluster::m_sequence.
1724        std::ranges::sort(to_remove, [&](GraphIndex a, GraphIndex b) noexcept {
1725            Cluster* cluster_a = m_entries[a].m_locator[level].cluster;
1726            Cluster* cluster_b = m_entries[b].m_locator[level].cluster;
1727            return CompareClusters(cluster_a, cluster_b) < 0;
1728        });
1729        // Process per Cluster.
1730        std::span to_remove_span{to_remove};
1731        while (!to_remove_span.empty()) {
1732            Cluster* cluster = m_entries[to_remove_span.front()].m_locator[level].cluster;
1733            if (cluster != nullptr) {
1734                // If the first to_remove_span entry's Cluster exists, hand to_remove_span to it, so it
1735                // can pop off whatever applies to it.
1736                cluster->ApplyRemovals(*this, level, to_remove_span);
1737            } else {
1738                // Otherwise, skip this already-removed entry. This may happen when
1739                // RemoveTransaction was called twice on the same Ref, for example.
1740                to_remove_span = to_remove_span.subspan(1);
1741            }
1742        }
1743        to_remove.clear();
1744    }
1745    Compact();
1746}
1747
1748void TxGraphImpl::SwapIndexes(GraphIndex a, GraphIndex b, std::vector<Cluster*>& affected_main) noexcept
1749{
1750    Assume(a < m_entries.size());