Method Split

src/txgraph.cpp:1439–1511

}

bool GenericClusterImpl::Split(TxGraphImpl& graph, int level) noexcept
{
    // This function can only be called when the Cluster needs splitting.
    Assume(NeedsSplitting());
    // Determine the new quality the split-off Clusters will have.
    QualityLevel new_quality = IsTopological() ? QualityLevel::NEEDS_RELINEARIZE : QualityLevel::NEEDS_FIX;
    /** Which positions are still left in this Cluster. */
    auto todo = m_depgraph.Positions();
    /** Mapping from transaction positions in this Cluster to the Cluster where it ends up, and
     *  its position therein. */
    std::vector<std::pair<Cluster*, DepGraphIndex>> remap(m_depgraph.PositionRange());
    std::vector<Cluster*> new_clusters;
    bool first{true};
    // Iterate over the connected components of this Cluster's m_depgraph.
    while (todo.Any()) {
        auto component = m_depgraph.FindConnectedComponent(todo);
        auto component_size = component.Count();
        auto split_quality = component_size <= 1 ? QualityLevel::OPTIMAL : new_quality;
        if (first && component == todo && SetType::Fill(component_size) == component && component_size >= MIN_INTENDED_TX_COUNT) {
            // The existing Cluster is an entire component, without holes. Leave it be, but update
            // its quality. If there are holes, we continue, so that the Cluster is reconstructed
            // without holes, reducing memory usage. If the component's size is below the intended
            // transaction count for this Cluster implementation, continue so that it can get
            // converted.
            Assume(todo == m_depgraph.Positions());
            graph.SetClusterQuality(level, m_quality, m_setindex, split_quality);
            // If this made the quality ACCEPTABLE or OPTIMAL, we need to compute and cache its
            // chunking.
            Updated(graph, /*level=*/level, /*rename=*/false);
            return false;
        }
        first = false;
        // Construct a new Cluster to hold the found component.
        auto new_cluster = graph.CreateEmptyCluster(component_size);
        new_clusters.push_back(new_cluster.get());
        // Remember that all the component's transactions go to this new Cluster. The positions
        // will be determined below, so use -1 for now.
        for (auto i : component) {
            remap[i] = {new_cluster.get(), DepGraphIndex(-1)};
        }
        graph.InsertCluster(level, std::move(new_cluster), split_quality);
        todo -= component;
    }
    // We have to split the Cluster up. Remove accounting for the existing one first.
    graph.GetClusterSet(level).m_cluster_usage -= TotalMemoryUsage();
    // Redistribute the transactions.
    for (auto i : m_linearization) {
        /** The cluster which transaction originally in position i is moved to. */
        Cluster* new_cluster = remap[i].first;
        // Copy the transaction to the new cluster's depgraph, and remember the position.
        remap[i].second = new_cluster->AppendTransaction(m_mapping[i], FeePerWeight::FromFeeFrac(m_depgraph.FeeRate(i)));
    }
    // Redistribute the dependencies.
    for (auto i : m_linearization) {
        /** The cluster transaction in position i is moved to. */
        Cluster* new_cluster = remap[i].first;
        // Copy its parents, translating positions.
        SetType new_parents;