Maintaining pending transactions

501            // Check whether its inputs are marked in mapNextTx.
502            auto it3 = mapNextTx.find(txin.prevout);
503            assert(it3 != mapNextTx.end());
504            assert(it3->first == &txin.prevout);
505            assert(&it3->second->GetTx() == &tx);
506        }
507        auto comp = [](const CTxMemPoolEntry& a, const CTxMemPoolEntry& b) -> bool {
508            return a.GetTx().GetHash() == b.GetTx().GetHash();
509        };
510        for (auto &txentry : GetParents(*it)) {
511            setParentsStored.insert(dynamic_cast<const CTxMemPoolEntry&>(txentry.get()));
512        }
513        assert(setParentCheck.size() == setParentsStored.size());
514        assert(std::equal(setParentCheck.begin(), setParentCheck.end(), setParentsStored.begin(), comp));
515
516        // Check children against mapNextTx
517        std::set<CTxMemPoolEntry::CTxMemPoolEntryRef, CompareIteratorByHash> setChildrenCheck;
518        std::set<CTxMemPoolEntry::CTxMemPoolEntryRef, CompareIteratorByHash> setChildrenStored;
519        auto iter = mapNextTx.lower_bound(COutPoint(it->GetTx().GetHash(), 0));
520        for (; iter != mapNextTx.end() && iter->first->hash == it->GetTx().GetHash(); ++iter) {
521            txiter childit = iter->second;
522            assert(childit != mapTx.end()); // mapNextTx points to in-mempool transactions
523            setChildrenCheck.insert(*childit);
524        }
525        for (auto &txentry : GetChildren(*it)) {
526            setChildrenStored.insert(dynamic_cast<const CTxMemPoolEntry&>(txentry.get()));
527        }
528        assert(setChildrenCheck.size() == setChildrenStored.size());
529        assert(std::equal(setChildrenCheck.begin(), setChildrenCheck.end(), setChildrenStored.begin(), comp));
530
531        TxValidationState dummy_state; // Not used. CheckTxInputs() should always pass
532        CAmount txfee = 0;
533        assert(!tx.IsCoinBase());
534        assert(Consensus::CheckTxInputs(tx, dummy_state, mempoolDuplicate, spendheight, txfee));
535        for (const auto& input: tx.vin) mempoolDuplicate.SpendCoin(input.prevout);
536        AddCoins(mempoolDuplicate, tx, std::numeric_limits<int>::max());
537    }
538    for (auto it = mapNextTx.cbegin(); it != mapNextTx.cend(); it++) {
539        indexed_transaction_set::const_iterator it2 = it->second;
540        assert(it2 != mapTx.end());
541    }
542
543    ++diagram_iter;
544    assert(diagram_iter == diagram.cend());
545
546    assert(totalTxSize == checkTotal);
547    assert(m_total_fee == check_total_fee);
548    assert(diagram.back().fee == check_total_modified_fee);
549    assert(diagram.back().size == check_total_adjusted_weight);
550    assert(innerUsage == cachedInnerUsage);
551}
552
553std::vector<CTxMemPool::txiter> CTxMemPool::ExtractBestByMiningScoreWithTopology(std::vector<Wtxid>& wtxids, size_t n_to_sort) const
554{
555    /* This function takes a vector of `wtxids`, and returns the
556     * best mempool entries corresponding to those `wtxids` (by mining
557     * score/topology). It updates the input `wtxids` so that multiple
558     * calls with the same vector will drain that vector to empty.
559     *
560     * It operates under the following constraints:
561     *   - wtxids that do not correspond to a mempool entry are dropped
562     *   - the return vector contains no duplicates, either with itself
563     *     or with the updated `wtxids` input.
564     *   - the return vector will have `n_to_sort` entries (or `wtxids`
565           will become empty).
566     *   - the `wtxids` vector will be reduced by at least `n_to_sort`
567     *     entries (or will become empty).
568     */
569
570    auto cmp = [&](const auto& a, const auto& b) EXCLUSIVE_LOCKS_REQUIRED(cs) noexcept { return m_txgraph->CompareMainOrder(*a, *b) < 0; };
571
572    std::vector<txiter> res;
573
574    n_to_sort = std::min(wtxids.size(), n_to_sort);
575    if (n_to_sort > 0) {
576        res.reserve(wtxids.size());
577        std::sort(wtxids.begin(), wtxids.end());
578        for (auto it = wtxids.begin(); it != wtxids.end(); ++it) {
579            // skip duplicates
580            auto itnext = it + 1;
581            if (itnext != wtxids.end() && *it == *itnext) continue;
582
583            if (auto i{GetIter(*it)}; i.has_value()) {
584                res.push_back(i.value());
585            }
586        }
587        wtxids.clear();
588
589        if (!res.empty()) {
590            auto begin = res.begin();
591            auto end = res.end();
592            auto middle = end;
593            if (n_to_sort >= res.size()) {
594                // use regular sort when sorting everything
595                std::sort(begin, end, cmp);
596            } else {
597                middle = begin + n_to_sort;
598                std::partial_sort(begin, middle, end, cmp);
599            }
600            auto it = middle;
601            while (it != end) {
602                wtxids.push_back((*it)->GetTx().GetWitnessHash());
603                ++it;
604            }
605            res.erase(middle, end);
606        }
607    }
608    return res;
609}
610
611std::vector<CTxMemPool::indexed_transaction_set::const_iterator> CTxMemPool::GetSortedScoreWithTopology() const
612{
613    std::vector<indexed_transaction_set::const_iterator> iters;
614    AssertLockHeld(cs);
615
616    iters.reserve(mapTx.size());
617
618    for (indexed_transaction_set::iterator mi = mapTx.begin(); mi != mapTx.end(); ++mi) {
619        iters.push_back(mi);
620    }
621    std::sort(iters.begin(), iters.end(), [this](const auto& a, const auto& b) EXCLUSIVE_LOCKS_REQUIRED(cs) noexcept {
622        return m_txgraph->CompareMainOrder(*a, *b) < 0;
623    });
624    return iters;
625}
626
627std::vector<CTxMemPoolEntryRef> CTxMemPool::entryAll() const
628{
629    AssertLockHeld(cs);
630
631    std::vector<CTxMemPoolEntryRef> ret;
632    ret.reserve(mapTx.size());
633    for (const auto& it : GetSortedScoreWithTopology()) {
634        ret.emplace_back(*it);
635    }
636    return ret;
637}
638
639std::vector<TxMempoolInfo> CTxMemPool::infoAll() const
640{
641    LOCK(cs);
642    auto iters = GetSortedScoreWithTopology();
643
644    std::vector<TxMempoolInfo> ret;
645    ret.reserve(mapTx.size());
646    for (auto it : iters) {
647        ret.push_back(GetInfo(it));
648    }
649
650    return ret;
651}
652
653const CTxMemPoolEntry* CTxMemPool::GetEntry(const Txid& txid) const
654{
655    AssertLockHeld(cs);
656    const auto i = mapTx.find(txid);
657    return i == mapTx.end() ? nullptr : &(*i);
658}
659
660CTransactionRef CTxMemPool::get(const Txid& hash) const
661{
662    LOCK(cs);
663    indexed_transaction_set::const_iterator i = mapTx.find(hash);
664    if (i == mapTx.end())
665        return nullptr;
666    return i->GetSharedTx();
667}
668
669CTransactionRef CTxMemPool::get(const Wtxid& hash) const
670{
671    LOCK(cs);
672    const auto& wtxid_map{mapTx.get<index_by_wtxid>()};
673    const auto it{wtxid_map.find(hash)};
674    if (it == wtxid_map.end()) return nullptr;
675    return it->GetSharedTx();
676}
677
678void CTxMemPool::PrioritiseTransaction(const Txid& hash, const CAmount& nFeeDelta)
679{
680    {
681        LOCK(cs);
682        CAmount &delta = mapDeltas[hash];
683        delta = SaturatingAdd(delta, nFeeDelta);
684        txiter it = mapTx.find(hash);
685        if (it != mapTx.end()) {
686            // PrioritiseTransaction calls stack on previous ones. Set the new
687            // transaction fee to be current modified fee + feedelta.
688            it->UpdateModifiedFee(nFeeDelta);
689            m_txgraph->SetTransactionFee(*it, it->GetModifiedFee());
690            ++nTransactionsUpdated;
691        }
692        if (delta == 0) {
693            mapDeltas.erase(hash);
694            LogInfo("PrioritiseTransaction: %s (%sin mempool) delta cleared\n", hash.ToString(), it == mapTx.end() ? "not " : "");
695        } else {
696            LogInfo("PrioritiseTransaction: %s (%sin mempool) fee += %s, new delta=%s\n",
697                      hash.ToString(),
698                      it == mapTx.end() ? "not " : "",
699                      FormatMoney(nFeeDelta),
700                      FormatMoney(delta));
701        }
702    }
703}
704
705void CTxMemPool::ApplyDelta(const Txid& hash, CAmount &nFeeDelta) const
706{
707    AssertLockHeld(cs);
708    std::map<Txid, CAmount>::const_iterator pos = mapDeltas.find(hash);
709    if (pos == mapDeltas.end())
710        return;
711    const CAmount &delta = pos->second;
712    nFeeDelta += delta;
713}
714
715void CTxMemPool::ClearPrioritisation(const Txid& hash)
716{
717    AssertLockHeld(cs);
718    mapDeltas.erase(hash);
719}
720
721std::vector<CTxMemPool::delta_info> CTxMemPool::GetPrioritisedTransactions() const
722{
723    AssertLockNotHeld(cs);
724    LOCK(cs);
725    std::vector<delta_info> result;
726    result.reserve(mapDeltas.size());
727    for (const auto& [txid, delta] : mapDeltas) {
728        const auto iter{mapTx.find(txid)};
729        const bool in_mempool{iter != mapTx.end()};
730        std::optional<CAmount> modified_fee;
731        if (in_mempool) modified_fee = iter->GetModifiedFee();
732        result.emplace_back(delta_info{in_mempool, delta, modified_fee, txid});
733    }
734    return result;
735}
736
737const CTransaction* CTxMemPool::GetConflictTx(const COutPoint& prevout) const
738{
739    const auto it = mapNextTx.find(prevout);
740    return it == mapNextTx.end() ? nullptr : &(it->second->GetTx());
741}
742
743std::optional<CTxMemPool::txiter> CTxMemPool::GetIter(const Txid& txid) const
744{
745    AssertLockHeld(cs);
746    auto it = mapTx.find(txid);
747    return it != mapTx.end() ? std::make_optional(it) : std::nullopt;
748}
749
750std::optional<CTxMemPool::txiter> CTxMemPool::GetIter(const Wtxid& wtxid) const