751{
752    AssertLockHeld(cs);
753    auto it{mapTx.project<0>(mapTx.get<index_by_wtxid>().find(wtxid))};
754    return it != mapTx.end() ? std::make_optional(it) : std::nullopt;
755}
756
757CTxMemPool::setEntries CTxMemPool::GetIterSet(const std::set<Txid>& hashes) const
758{
759    CTxMemPool::setEntries ret;
760    for (const auto& h : hashes) {
761        const auto mi = GetIter(h);
762        if (mi) ret.insert(*mi);
763    }
764    return ret;
765}
766
767std::vector<CTxMemPool::txiter> CTxMemPool::GetIterVec(const std::vector<Txid>& txids) const
768{
769    AssertLockHeld(cs);
770    std::vector<txiter> ret;
771    ret.reserve(txids.size());
772    for (const auto& txid : txids) {
773        const auto it{GetIter(txid)};
774        if (!it) return {};
775        ret.push_back(*it);
776    }
777    return ret;
778}
779
780bool CTxMemPool::HasNoInputsOf(const CTransaction &tx) const
781{
782    for (unsigned int i = 0; i < tx.vin.size(); i++)
783        if (exists(tx.vin[i].prevout.hash))
784            return false;
785    return true;
786}
787
788CCoinsViewMemPool::CCoinsViewMemPool(CCoinsView* baseIn, const CTxMemPool& mempoolIn) : CCoinsViewBacked(baseIn), mempool(mempoolIn) { }
789
790std::optional<Coin> CCoinsViewMemPool::GetCoin(const COutPoint& outpoint) const
791{
792    // Check to see if the inputs are made available by another tx in the package.
793    // These Coins would not be available in the underlying CoinsView.
794    if (auto it = m_temp_added.find(outpoint); it != m_temp_added.end()) {
795        return it->second;
796    }
797
798    // If an entry in the mempool exists, always return that one, as it's guaranteed to never
799    // conflict with the underlying cache, and it cannot have pruned entries (as it contains full)
800    // transactions. First checking the underlying cache risks returning a pruned entry instead.
801    CTransactionRef ptx = mempool.get(outpoint.hash);
802    if (ptx) {
803        if (outpoint.n < ptx->vout.size()) {
804            Coin coin(ptx->vout[outpoint.n], MEMPOOL_HEIGHT, false);
805            m_non_base_coins.emplace(outpoint);
806            return coin;
807        }
808        return std::nullopt;
809    }
810    return base->GetCoin(outpoint);
811}
812
813void CCoinsViewMemPool::PackageAddTransaction(const CTransactionRef& tx)
814{
815    for (unsigned int n = 0; n < tx->vout.size(); ++n) {
816        m_temp_added.emplace(COutPoint(tx->GetHash(), n), Coin(tx->vout[n], MEMPOOL_HEIGHT, false));
817        m_non_base_coins.emplace(tx->GetHash(), n);
818    }
819}
820void CCoinsViewMemPool::Reset()
821{
822    m_temp_added.clear();
823    m_non_base_coins.clear();
824}
825
826size_t CTxMemPool::DynamicMemoryUsage() const {
827    LOCK(cs);
828    // Estimate the overhead of mapTx to be 9 pointers (3 pointers per index) + an allocation, as no exact formula for boost::multi_index_contained is implemented.
829    return memusage::MallocUsage(sizeof(CTxMemPoolEntry) + 9 * sizeof(void*)) * mapTx.size() + memusage::DynamicUsage(mapNextTx) + memusage::DynamicUsage(mapDeltas) + memusage::DynamicUsage(txns_randomized) + m_txgraph->GetMainMemoryUsage() + cachedInnerUsage;
830}
831
832void CTxMemPool::RemoveUnbroadcastTx(const Txid& txid, const bool unchecked) {
833    LOCK(cs);
834
835    if (m_unbroadcast_txids.erase(txid))
836    {
837        LogDebug(BCLog::MEMPOOL, "Removed %s from set of unbroadcast txns%s", txid.GetHex(), (unchecked ? " before confirmation that txn was sent out" : ""));
838    }
839}
840
841void CTxMemPool::RemoveStaged(setEntries &stage, MemPoolRemovalReason reason) {
842    AssertLockHeld(cs);
843    for (txiter it : stage) {
844        removeUnchecked(it, reason);
845    }
846}
847
848bool CTxMemPool::CheckPolicyLimits(const CTransactionRef& tx)
849{
850    LOCK(cs);
851    // Use ChangeSet interface to check whether the cluster count
852    // limits would be violated. Note that the changeset will be destroyed
853    // when it goes out of scope.
854    auto changeset = GetChangeSet();
855    (void) changeset->StageAddition(tx, /*fee=*/0, /*time=*/0, /*entry_height=*/0, /*entry_sequence=*/0, /*spends_coinbase=*/false, /*sigops_cost=*/0, LockPoints{});
856    return changeset->CheckMemPoolPolicyLimits();
857}
858
859int CTxMemPool::Expire(std::chrono::seconds time)
860{
861    AssertLockHeld(cs);
862    Assume(!m_have_changeset);
863    indexed_transaction_set::index<entry_time>::type::iterator it = mapTx.get<entry_time>().begin();
864    setEntries toremove;
865    while (it != mapTx.get<entry_time>().end() && it->GetTime() < time) {
866        toremove.insert(mapTx.project<0>(it));
867        it++;
868    }
869    setEntries stage;
870    for (txiter removeit : toremove) {
871        CalculateDescendants(removeit, stage);
872    }
873    RemoveStaged(stage, MemPoolRemovalReason::EXPIRY);
874    return stage.size();
875}
876
877CFeeRate CTxMemPool::GetMinFee(size_t sizelimit) const {
878    LOCK(cs);
879    if (!blockSinceLastRollingFeeBump || rollingMinimumFeeRate == 0)
880        return CFeeRate(llround(rollingMinimumFeeRate));
881
882    int64_t time = GetTime();
883    if (time > lastRollingFeeUpdate + 10) {
884        double halflife = ROLLING_FEE_HALFLIFE;
885        if (DynamicMemoryUsage() < sizelimit / 4)
886            halflife /= 4;
887        else if (DynamicMemoryUsage() < sizelimit / 2)
888            halflife /= 2;
889
890        rollingMinimumFeeRate = rollingMinimumFeeRate / pow(2.0, (time - lastRollingFeeUpdate) / halflife);
891        lastRollingFeeUpdate = time;
892
893        if (rollingMinimumFeeRate < (double)m_opts.incremental_relay_feerate.GetFeePerK() / 2) {
894            rollingMinimumFeeRate = 0;
895            return CFeeRate(0);
896        }
897    }
898    return std::max(CFeeRate(llround(rollingMinimumFeeRate)), m_opts.incremental_relay_feerate);
899}
900
901void CTxMemPool::trackPackageRemoved(const CFeeRate& rate) {
902    AssertLockHeld(cs);
903    if (rate.GetFeePerK() > rollingMinimumFeeRate) {
904        rollingMinimumFeeRate = rate.GetFeePerK();
905        blockSinceLastRollingFeeBump = false;
906    }
907}
908
909void CTxMemPool::TrimToSize(size_t sizelimit, std::vector<COutPoint>* pvNoSpendsRemaining) {
910    AssertLockHeld(cs);
911    Assume(!m_have_changeset);
912
913    unsigned nTxnRemoved = 0;
914    CFeeRate maxFeeRateRemoved(0);
915
916    while (!mapTx.empty() && DynamicMemoryUsage() > sizelimit) {
917        const auto &[worst_chunk, feeperweight] = m_txgraph->GetWorstMainChunk();
918        FeePerVSize feerate = ToFeePerVSize(feeperweight);
919        CFeeRate removed{feerate.fee, feerate.size};
920
921        // We set the new mempool min fee to the feerate of the removed set, plus the
922        // "minimum reasonable fee rate" (ie some value under which we consider txn
923        // to have 0 fee). This way, we don't allow txn to enter mempool with feerate
924        // equal to txn which were removed with no block in between.
925        removed += m_opts.incremental_relay_feerate;
926        trackPackageRemoved(removed);
927        maxFeeRateRemoved = std::max(maxFeeRateRemoved, removed);
928
929        nTxnRemoved += worst_chunk.size();
930
931        std::vector<CTransaction> txn;
932        if (pvNoSpendsRemaining) {
933            txn.reserve(worst_chunk.size());
934            for (auto ref : worst_chunk) {
935                txn.emplace_back(static_cast<const CTxMemPoolEntry&>(*ref).GetTx());
936            }
937        }
938
939        setEntries stage;
940        for (auto ref : worst_chunk) {
941            stage.insert(mapTx.iterator_to(static_cast<const CTxMemPoolEntry&>(*ref)));
942        }
943        for (auto e : stage) {
944            removeUnchecked(e, MemPoolRemovalReason::SIZELIMIT);
945        }
946        if (pvNoSpendsRemaining) {
947            for (const CTransaction& tx : txn) {
948                for (const CTxIn& txin : tx.vin) {
949                    if (exists(txin.prevout.hash)) continue;
950                    pvNoSpendsRemaining->push_back(txin.prevout);
951                }
952            }
953        }
954    }
955
956    if (maxFeeRateRemoved > CFeeRate(0)) {
957        LogDebug(BCLog::MEMPOOL, "Removed %u txn, rolling minimum fee bumped to %s\n", nTxnRemoved, maxFeeRateRemoved.ToString());
958    }
959}
960
961std::tuple<size_t, size_t, CAmount> CTxMemPool::CalculateAncestorData(const CTxMemPoolEntry& entry) const
962{
963    auto ancestors = m_txgraph->GetAncestors(entry, TxGraph::Level::MAIN);
964
965    size_t ancestor_count = ancestors.size();
966    size_t ancestor_size = 0;
967    CAmount ancestor_fees = 0;
968    for (auto tx: ancestors) {
969        const CTxMemPoolEntry& anc = static_cast<const CTxMemPoolEntry&>(*tx);
970        ancestor_size += anc.GetTxSize();
971        ancestor_fees += anc.GetModifiedFee();
972    }
973    return {ancestor_count, ancestor_size, ancestor_fees};
974}
975
976std::tuple<size_t, size_t, CAmount> CTxMemPool::CalculateDescendantData(const CTxMemPoolEntry& entry) const
977{
978    auto descendants = m_txgraph->GetDescendants(entry, TxGraph::Level::MAIN);
979    size_t descendant_count = descendants.size();
980    size_t descendant_size = 0;
981    CAmount descendant_fees = 0;
982
983    for (auto tx: descendants) {
984        const CTxMemPoolEntry &desc = static_cast<const CTxMemPoolEntry&>(*tx);
985        descendant_size += desc.GetTxSize();
986        descendant_fees += desc.GetModifiedFee();
987    }
988    return {descendant_count, descendant_size, descendant_fees};
989}
990
991void CTxMemPool::GetTransactionAncestry(const Txid& txid, size_t& ancestors, size_t& cluster_count, size_t* const ancestorsize, CAmount* const ancestorfees) const {
992    LOCK(cs);
993    auto it = mapTx.find(txid);
994    ancestors = cluster_count = 0;
995    if (it != mapTx.end()) {
996        auto [ancestor_count, ancestor_size, ancestor_fees] = CalculateAncestorData(*it);
997        ancestors = ancestor_count;
998        if (ancestorsize) *ancestorsize = ancestor_size;
999        if (ancestorfees) *ancestorfees = ancestor_fees;
1000        cluster_count = m_txgraph->GetCluster(*it, TxGraph::Level::MAIN).size();