Inside Bitcoin

1751    Assume(b < m_entries.size());
1752    // Swap the Entry objects.
1753    std::swap(m_entries[a], m_entries[b]);
1754    // Iterate over both objects.
1755    for (int i = 0; i < 2; ++i) {
1756        GraphIndex idx = i ? b : a;
1757        Entry& entry = m_entries[idx];
1758        // Update linked Ref, if any exists.
1759        if (entry.m_ref) GetRefIndex(*entry.m_ref) = idx;
1760        // Update linked chunk index entries, if any exist.
1761        if (entry.m_main_chunkindex_iterator != m_main_chunkindex.end()) {
1762            entry.m_main_chunkindex_iterator->m_graph_index = idx;
1763        }
1764        // Update the locators for both levels.
1765        for (int level = 0; level < MAX_LEVELS; ++level) {
1766            Locator& locator = entry.m_locator[level];
1767            if (locator.IsPresent()) {
1768                locator.cluster->UpdateMapping(locator.index, idx);
1769                if (level == 0) affected_main.push_back(locator.cluster);
1770            }
1771        }
1772    }
1773}
1774
1775void TxGraphImpl::Compact() noexcept
1776{
1777    // We cannot compact while any to-be-applied operations or staged removals remain as we'd need
1778    // to rewrite them. It is easier to delay the compaction until they have been applied.
1779    if (!m_main_clusterset.m_deps_to_add.empty()) return;
1780    if (!m_main_clusterset.m_to_remove.empty()) return;
1781    Assume(m_main_clusterset.m_removed.empty()); // non-staging m_removed is always empty
1782    if (m_staging_clusterset.has_value()) {
1783        if (!m_staging_clusterset->m_deps_to_add.empty()) return;
1784        if (!m_staging_clusterset->m_to_remove.empty()) return;
1785        if (!m_staging_clusterset->m_removed.empty()) return;
1786    }
1787
1788    // Release memory used by discarded ChunkData index entries.
1789    ClearShrink(m_main_chunkindex_discarded);
1790
1791    // Sort the GraphIndexes that need to be cleaned up. They are sorted in reverse, so the last
1792    // ones get processed first. This means earlier-processed GraphIndexes will not cause moving of
1793    // later-processed ones during the "swap with end of m_entries" step below (which might
1794    // invalidate them).
1795    std::ranges::sort(m_unlinked, std::greater{});
1796
1797    std::vector<Cluster*> affected_main;
1798    auto last = GraphIndex(-1);
1799    for (GraphIndex idx : m_unlinked) {
1800        // m_unlinked should never contain the same GraphIndex twice (the code below would fail
1801        // if so, because GraphIndexes get invalidated by removing them).
1802        Assume(idx != last);
1803        last = idx;
1804
1805        // Make sure the entry is unlinked.
1806        Entry& entry = m_entries[idx];
1807        Assume(entry.m_ref == nullptr);
1808        // Make sure the entry does not occur in the graph.
1809        for (int level = 0; level < MAX_LEVELS; ++level) {
1810            Assume(!entry.m_locator[level].IsPresent());
1811        }
1812
1813        // Move the entry to the end.
1814        if (idx != m_entries.size() - 1) SwapIndexes(idx, m_entries.size() - 1, affected_main);
1815        // Drop the entry for idx, now that it is at the end.
1816        m_entries.pop_back();
1817    }
1818
1819    // Update the affected clusters, to fixup Entry::m_main_max_chunk_fallback values which may
1820    // have become outdated due to the compaction above.
1821    std::ranges::sort(affected_main);
1822    affected_main.erase(std::unique(affected_main.begin(), affected_main.end()), affected_main.end());
1823    for (Cluster* cluster : affected_main) {
1824        cluster->Updated(*this, /*level=*/0, /*rename=*/true);
1825    }
1826    m_unlinked.clear();
1827}
1828
1829void TxGraphImpl::Split(Cluster& cluster, int level) noexcept
1830{
1831    // To split a Cluster, first make sure all removals are applied (as we might need to split
1832    // again afterwards otherwise).
1833    ApplyRemovals(level);
1834    bool del = cluster.Split(*this, level);
1835    if (del) {
1836        // Cluster::Split reports whether the Cluster is to be deleted.
1837        DeleteCluster(cluster, level);
1838    }
1839}
1840
1841void TxGraphImpl::SplitAll(int up_to_level) noexcept
1842{
1843    Assume(up_to_level >= 0 && up_to_level <= GetTopLevel());
1844    // Before splitting all Cluster, first make sure all removals are applied.
1845    ApplyRemovals(up_to_level);
1846    for (int level = 0; level <= up_to_level; ++level) {
1847        for (auto quality : {QualityLevel::NEEDS_SPLIT_FIX, QualityLevel::NEEDS_SPLIT}) {
1848            auto& queue = GetClusterSet(level).m_clusters[int(quality)];
1849            while (!queue.empty()) {
1850                Split(*queue.back().get(), level);
1851            }
1852        }
1853    }
1854}
1855
1856void TxGraphImpl::GroupClusters(int level) noexcept
1857{
1858    auto& clusterset = GetClusterSet(level);
1859    // If the groupings have been computed already, nothing is left to be done.
1860    if (clusterset.m_group_data.has_value()) return;
1861
1862    // Before computing which Clusters need to be merged together, first apply all removals and
1863    // split the Clusters into connected components. If we would group first, we might end up
1864    // with inefficient and/or oversized Clusters which just end up being split again anyway.
1865    SplitAll(level);
1866
1867    /** Annotated clusters: an entry for each Cluster, together with the sequence number for the
1868     *  representative for the partition it is in (initially its own, later that of the
1869     *  to-be-merged group). */
1870    std::vector<std::pair<Cluster*, uint64_t>> an_clusters;
1871    /** Annotated dependencies: an entry for each m_deps_to_add entry (excluding ones that apply
1872     *  to removed transactions), together with the sequence number of the representative root of
1873     *  Clusters it applies to (initially that of the child Cluster, later that of the
1874     *  to-be-merged group). */
1875    std::vector<std::pair<std::pair<GraphIndex, GraphIndex>, uint64_t>> an_deps;
1876
1877    // Construct an an_clusters entry for every oversized cluster, including ones from levels below,
1878    // as they may be inherited in this one.
1879    for (int level_iter = 0; level_iter <= level; ++level_iter) {
1880        for (auto& cluster : GetClusterSet(level_iter).m_clusters[int(QualityLevel::OVERSIZED_SINGLETON)]) {
1881            auto graph_idx = cluster->GetClusterEntry(0);
1882            auto cur_cluster = FindCluster(graph_idx, level);
1883            if (cur_cluster == nullptr) continue;
1884            an_clusters.emplace_back(cur_cluster, cur_cluster->m_sequence);
1885        }
1886    }
1887
1888    // Construct a an_clusters entry for every parent and child in the to-be-applied dependencies,
1889    // and an an_deps entry for each dependency to be applied.
1890    an_deps.reserve(clusterset.m_deps_to_add.size());
1891    for (const auto& [par, chl] : clusterset.m_deps_to_add) {
1892        auto par_cluster = FindCluster(par, level);
1893        auto chl_cluster = FindCluster(chl, level);
1894        // Skip dependencies for which the parent or child transaction is removed.
1895        if (par_cluster == nullptr || chl_cluster == nullptr) continue;
1896        an_clusters.emplace_back(par_cluster, par_cluster->m_sequence);
1897        // Do not include a duplicate when parent and child are identical, as it'll be removed
1898        // below anyway.
1899        if (chl_cluster != par_cluster) an_clusters.emplace_back(chl_cluster, chl_cluster->m_sequence);
1900        // Add entry to an_deps, using the child sequence number.
1901        an_deps.emplace_back(std::pair{par, chl}, chl_cluster->m_sequence);
1902    }
1903    // Sort and deduplicate an_clusters, so we end up with a sorted list of all involved Clusters
1904    // to which dependencies apply, or which are oversized.
1905    std::ranges::sort(an_clusters, [](auto& a, auto& b) noexcept { return a.second < b.second; });
1906    an_clusters.erase(std::ranges::unique(an_clusters).begin(), an_clusters.end());
1907    // Sort an_deps by applying the same order to the involved child cluster.
1908    std::ranges::sort(an_deps, [&](auto& a, auto& b) noexcept { return a.second < b.second; });
1909
1910    // Run the union-find algorithm to find partitions of the input Clusters which need to be
1911    // grouped together. See https://en.wikipedia.org/wiki/Disjoint-set_data_structure.
1912    {
1913        /** Each PartitionData entry contains information about a single input Cluster. */
1914        struct PartitionData
1915        {
1916            /** The sequence number of the cluster this holds information for. */
1917            uint64_t sequence;
1918            /** All PartitionData entries belonging to the same partition are organized in a tree.
1919             *  Each element points to its parent, or to itself if it is the root. The root is then
1920             *  a representative for the entire tree, and can be found by walking upwards from any
1921             *  element. */
1922            PartitionData* parent;
1923            /** (only if this is a root, so when parent == this) An upper bound on the height of
1924             *  tree for this partition. */
1925            unsigned rank;
1926        };
1927        /** Information about each input Cluster. Sorted by Cluster::m_sequence. */
1928        std::vector<PartitionData> partition_data;
1929
1930        /** Given a Cluster, find its corresponding PartitionData. */
1931        auto locate_fn = [&](uint64_t sequence) noexcept -> PartitionData* {
1932            auto it = std::lower_bound(partition_data.begin(), partition_data.end(), sequence,
1933                                       [](auto& a, uint64_t seq) noexcept { return a.sequence < seq; });
1934            Assume(it != partition_data.end());
1935            Assume(it->sequence == sequence);
1936            return &*it;
1937        };
1938
1939        /** Given a PartitionData, find the root of the tree it is in (its representative). */
1940        static constexpr auto find_root_fn = [](PartitionData* data) noexcept -> PartitionData* {
1941            while (data->parent != data) {
1942                // Replace pointers to parents with pointers to grandparents.
1943                // See https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Finding_set_representatives.
1944                auto par = data->parent;
1945                data->parent = par->parent;
1946                data = par;
1947            }
1948            return data;
1949        };
1950
1951        /** Given two PartitionDatas, union the partitions they are in, and return their
1952         *  representative. */
1953        static constexpr auto union_fn = [](PartitionData* arg1, PartitionData* arg2) noexcept {
1954            // Find the roots of the trees, and bail out if they are already equal (which would
1955            // mean they are in the same partition already).
1956            auto rep1 = find_root_fn(arg1);
1957            auto rep2 = find_root_fn(arg2);
1958            if (rep1 == rep2) return rep1;
1959            // Pick the lower-rank root to become a child of the higher-rank one.
1960            // See https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Union_by_rank.
1961            if (rep1->rank < rep2->rank) std::swap(rep1, rep2);
1962            rep2->parent = rep1;
1963            rep1->rank += (rep1->rank == rep2->rank);
1964            return rep1;
1965        };
1966
1967        // Start by initializing every Cluster as its own singleton partition.
1968        partition_data.resize(an_clusters.size());
1969        for (size_t i = 0; i < an_clusters.size(); ++i) {
1970            partition_data[i].sequence = an_clusters[i].first->m_sequence;
1971            partition_data[i].parent = &partition_data[i];
1972            partition_data[i].rank = 0;
1973        }
1974
1975        // Run through all parent/child pairs in an_deps, and union the partitions their Clusters
1976        // are in.
1977        Cluster* last_chl_cluster{nullptr};
1978        PartitionData* last_partition{nullptr};
1979        for (const auto& [dep, _] : an_deps) {
1980            auto [par, chl] = dep;
1981            auto par_cluster = FindCluster(par, level);
1982            auto chl_cluster = FindCluster(chl, level);
1983            Assume(chl_cluster != nullptr && par_cluster != nullptr);
1984            // Nothing to do if parent and child are in the same Cluster.
1985            if (par_cluster == chl_cluster) continue;
1986            Assume(par != chl);
1987            if (chl_cluster == last_chl_cluster) {
1988                // If the child Clusters is the same as the previous iteration, union with the
1989                // tree they were in, avoiding the need for another lookup. Note that an_deps
1990                // is sorted by child Cluster, so batches with the same child are expected.
1991                last_partition = union_fn(locate_fn(par_cluster->m_sequence), last_partition);
1992            } else {
1993                last_chl_cluster = chl_cluster;
1994                last_partition = union_fn(locate_fn(par_cluster->m_sequence), locate_fn(chl_cluster->m_sequence));
1995            }
1996        }
1997
1998        // Update the sequence numbers in an_clusters and an_deps to be those of the partition
1999        // representative.
2000        auto deps_it = an_deps.begin();