txmempool: Add ExtractBestByMiningScoreWithTopology

diff --git a/src/txmempool.cpp b/src/txmempool.cpp
index 86cbc1ad..4bb86c9b 100644
--- a/src/txmempool.cpp
+++ b/src/txmempool.cpp
@@ -553,6 +553,64 @@ void CTxMemPool::check(const CCoinsViewCache& active_coins_tip, int64_t spendhei
     assert(innerUsage == cachedInnerUsage);
 }
 
+std::vector<CTxMemPool::txiter> CTxMemPool::ExtractBestByMiningScoreWithTopology(std::vector<Wtxid>& wtxids, size_t n_to_sort) const
+{
+    /* This function takes a vector of `wtxids`, and returns the
+     * best mempool entries corresponding to those `wtxids` (by mining
+     * score/topology). It updates the input `wtxids` so that multiple
+     * calls with the same vector will drain that vector to empty.
+     *
+     * It operates under the following constraints:
+     *   - wtxids that do not correspond to a mempool entry are dropped
+     *   - the return vector contains no duplicates, either with itself
+     *     or with the updated `wtxids` input.
+     *   - the return vector will have `n_to_sort` entries (or `wtxids`
+           will become empty).
+     *   - the `wtxids` vector will be reduced by at least `n_to_sort`
+     *     entries (or will become empty).
+     */
+
+    auto cmp = [&](const auto& a, const auto& b) EXCLUSIVE_LOCKS_REQUIRED(cs) noexcept { return m_txgraph->CompareMainOrder(*a, *b) < 0; };
+
+    std::vector<txiter> res;
+
+    n_to_sort = std::min(wtxids.size(), n_to_sort);
+    if (n_to_sort > 0) {
+        res.reserve(wtxids.size());
+        std::sort(wtxids.begin(), wtxids.end());
+        for (auto it = wtxids.begin(); it != wtxids.end(); ++it) {
+            // skip duplicates
+            auto itnext = it + 1;
+            if (itnext != wtxids.end() && *it == *itnext) continue;
+
+            if (auto i{GetIter(*it)}; i.has_value()) {
+                res.push_back(i.value());
+            }
+        }
+        wtxids.clear();
+
+        if (!res.empty()) {
+            auto begin = res.begin();
+            auto end = res.end();
+            auto middle = end;
+            if (n_to_sort >= res.size()) {
+                // use regular sort when sorting everything
+                std::sort(begin, end, cmp);
+            } else {
+                middle = begin + n_to_sort;
+                std::partial_sort(begin, middle, end, cmp);
+            }
+            auto it = middle;
+            while (it != end) {
+                wtxids.push_back((*it)->GetTx().GetWitnessHash());
+                ++it;
+            }
+            res.erase(middle, end);
+        }
+    }
+    return res;
+}
+
 bool CTxMemPool::CompareMiningScoreWithTopology(const Wtxid& hasha, const Wtxid& hashb) const
 {
     /* Return `true` if hasha should be considered sooner than hashb, namely when:
diff --git a/src/txmempool.h b/src/txmempool.h
index 1a5405d5..dcc9ed87 100644
--- a/src/txmempool.h
+++ b/src/txmempool.h
@@ -331,6 +331,19 @@ public:
     void removeForReorg(CChain& chain, std::function<bool(txiter)> filter_final_and_mature) EXCLUSIVE_LOCKS_REQUIRED(cs, cs_main);
     void removeForBlock(const std::vector<CTransactionRef>& vtx, unsigned int nBlockHeight) EXCLUSIVE_LOCKS_REQUIRED(cs);
 
+    /** Look up wtxids in the mempool and (partially) sort by mining score.
+     *
+     * The @p n_to_sort best entries are removed from @p wtxids and their
+     * corresponding txiter entries are returned. In addition wtxids
+     * that are duplicates or were not found in the mempool are silently
+     * dropped from @p wtxids. The returned vector is ordered from best
+     * to worst (by CompareMainOrder). Entries remaining in @p wtxids
+     * are in unspecified order.
+     *
+     * Note that the returned `txiter` values may become invalidated once
+     * mempool.cs is released.
+     */
+    std::vector<txiter> ExtractBestByMiningScoreWithTopology(std::vector<Wtxid>& wtxids, size_t n_to_sort) const EXCLUSIVE_LOCKS_REQUIRED(cs);
     bool CompareMiningScoreWithTopology(const Wtxid& hasha, const Wtxid& hashb) const;
     bool isSpent(const COutPoint& outpoint) const;
     unsigned int GetTransactionsUpdated() const;