Method GetLinearization

src/cluster_linearize.h:1465–1605

Construct a topologically-valid linearization from the current forest state. Must be * topological. fallback_order is a comparator that defines a strong order for DepGraphIndexes * in this cluster, used to order equal-feerate transactions and chunks. * * Specifically, the resulting order consists of: * - The chunks of the current SFL state, sorted by (in decreasing order

     *   - the lowest transaction, by fallback_order, first
     */
    std::vector<DepGraphIndex> GetLinearization(const StrongComparator<DepGraphIndex> auto& fallback_order) noexcept
    {
        m_cost.GetLinearizationBegin();
        /** The output linearization. */
        std::vector<DepGraphIndex> ret;
        ret.reserve(m_set_info.size());
        /** A heap with all chunks (by set index) that can currently be included, sorted by
         *  chunk feerate (high to low), chunk size (small to large), and by least maximum element
         *  according to the fallback order (which is the second pair element). */
        std::vector<std::pair<SetIdx, TxIdx>> ready_chunks;
        /** For every chunk, indexed by SetIdx, the number of unmet dependencies the chunk has on
         *  other chunks (not including dependencies within the chunk itself). */
        std::vector<TxIdx> chunk_deps(m_set_info.size(), 0);
        /** For every transaction, indexed by TxIdx, the number of unmet dependencies the
         *  transaction has. */
        std::vector<TxIdx> tx_deps(m_tx_data.size(), 0);
        /** A heap with all transactions within the current chunk that can be included, sorted by
         *  tx feerate (high to low), tx size (small to large), and fallback order. */
        std::vector<TxIdx> ready_tx;
        // Populate chunk_deps and tx_deps.
        unsigned num_deps{0};
        for (TxIdx chl_idx : m_transaction_idxs) {
            const auto& chl_data = m_tx_data[chl_idx];
            tx_deps[chl_idx] = chl_data.parents.Count();
            num_deps += tx_deps[chl_idx];
            auto chl_chunk_idx = chl_data.chunk_idx;
            auto& chl_chunk_info = m_set_info[chl_chunk_idx];
            chunk_deps[chl_chunk_idx] += (chl_data.parents - chl_chunk_info.transactions).Count();
        }
        /** Function to compute the highest element of a chunk, by fallback_order. */
        auto max_fallback_fn = [&](SetIdx chunk_idx) noexcept {
            auto& chunk = m_set_info[chunk_idx].transactions;
            auto it = chunk.begin();
            DepGraphIndex ret = *it;
            ++it;
            while (it != chunk.end()) {
                if (fallback_order(*it, ret) > 0) ret = *it;
                ++it;
            }
            return ret;
        };
        /** Comparison function for the transaction heap. Note that it is a max-heap, so
         *  tx_cmp_fn(a, b) == true means "a appears after b in the linearization". */
        auto tx_cmp_fn = [&](const auto& a, const auto& b) noexcept {
            // Bail out for identical transactions.
            if (a == b) return false;
            // First sort by increasing transaction feerate.
            auto& a_feerate = m_depgraph.FeeRate(a);
            auto& b_feerate = m_depgraph.FeeRate(b);
            auto feerate_cmp = ByRatio{a_feerate} <=> ByRatio{b_feerate};
            if (feerate_cmp != 0) return feerate_cmp < 0;
            // Then by decreasing transaction size.
            if (a_feerate.size != b_feerate.size) {
                return a_feerate.size > b_feerate.size;
            }
            // Tie-break by decreasing fallback_order.
            auto fallback_cmp = fallback_order(a, b);
            if (fallback_cmp != 0) return fallback_cmp > 0;