Method MinimizeStep

src/cluster_linearize.h:1357–1447

Try to reduce a chunk's size. Returns false if all chunks are minimal, true otherwise. */

    /** Try to reduce a chunk's size. Returns false if all chunks are minimal, true otherwise. */
    bool MinimizeStep() noexcept
    {
        // If the queue of potentially-non-minimal chunks is empty, we are done.
        if (m_nonminimal_chunks.empty()) return false;
        m_cost.MinimizeStepBegin();
        // Pop an entry from the potentially-non-minimal chunk queue.
        auto [chunk_idx, pivot_idx, flags] = m_nonminimal_chunks.front();
        m_nonminimal_chunks.pop_front();
        auto& chunk_info = m_set_info[chunk_idx];
        /** Whether to move the pivot down rather than up. */
        bool move_pivot_down = flags & 1;
        /** Whether this is already the second stage. */
        bool second_stage = flags & 2;

        // Find a random dependency whose top and bottom set feerates are equal, and which has
        // pivot in bottom set (if move_pivot_down) or in top set (if !move_pivot_down).
        std::pair<TxIdx, TxIdx> candidate_dep;
        uint64_t candidate_tiebreak{0};
        bool have_any = false;
        // Iterate over all transactions.
        for (auto tx_idx : chunk_info.transactions) {
            const auto& tx_data = m_tx_data[tx_idx];
            // Iterate over all active child dependencies of the transaction.
            for (auto child_idx : tx_data.active_children) {
                const auto& dep_top_info = m_set_info[tx_data.dep_top_idx[child_idx]];
                // Skip if this dependency does not have equal top and bottom set feerates. Note
                // that the top cannot have higher feerate than the bottom, or OptimizeSteps would
                // have dealt with it.
                if (ByRatio{dep_top_info.feerate} < ByRatio{chunk_info.feerate}) continue;
                have_any = true;
                // Skip if this dependency does not have pivot in the right place.
                if (move_pivot_down == dep_top_info.transactions[pivot_idx]) continue;
                // Remember this as our chosen dependency if it has a better tiebreak.
                uint64_t tiebreak = m_rng.rand64() | 1;
                if (tiebreak > candidate_tiebreak) {
                    candidate_tiebreak = tiebreak;
                    candidate_dep = {tx_idx, child_idx};
                }
            }
        }
        m_cost.MinimizeStepMid(/*num_txns=*/chunk_info.transactions.Count());
        // If no dependencies have equal top and bottom set feerate, this chunk is minimal.
        if (!have_any) return true;
        // If all found dependencies have the pivot in the wrong place, try moving it in the other
        // direction. If this was the second stage already, we are done.
        if (candidate_tiebreak == 0) {
            // Switch to other direction, and to second phase.
            flags ^= 3;
            if (!second_stage) m_nonminimal_chunks.emplace_back(chunk_idx, pivot_idx, flags);
            return true;
        }

        // Otherwise, deactivate the dependency that was found.
        auto [parent_chunk_idx, child_chunk_idx] = Deactivate(candidate_dep.first, candidate_dep.second);
        // Determine if there is a dependency from the new bottom to the new top (opposite from the
        // dependency that was just deactivated).
        auto& parent_reachable = m_reachable[parent_chunk_idx].first;
        auto& child_chunk_txn = m_set_info[child_chunk_idx].transactions;