Repository: bitcoin/bitcoin
File: src/txmempool.cpp (C++)

Code before:
bool TestLockPointValidity(CChain& active_chain, const LockPoints& lp)
{
    AssertLockHeld(cs_main);
    // If there are relative lock times then the maxInputBlock will be set
    // If there are no relative lock times, the LockPoints don't depend on the chain
    if (lp.maxInputBlock) {
        // Check whether active_chain is an extension of the block at which the LockPoints
        // calculation was valid.  If not LockPoints are no longer valid
        if (!active_chain.Contains(lp.maxInputBlock)) {
            return false;
        }
    }

    // LockPoints still valid
    return true;
}

std::vector<CTxMemPoolEntry::CTxMemPoolEntryRef> CTxMemPool::GetChildren(const CTxMemPoolEntry& entry) const
{
    std::vector<CTxMemPoolEntry::CTxMemPoolEntryRef> ret;
    const auto& hash = entry.GetTx().GetHash();
    {
        LOCK(cs);
        auto iter = mapNextTx.lower_bound(COutPoint(hash, 0));
        for (; iter != mapNextTx.end() && iter->first->hash == hash; ++iter) {
            ret.push_back(*(iter->second));
        }
    }
    static constexpr auto cmp_fn = [](auto& a, auto& b) noexcept { return std::less{}(&a, &b); };
    std::ranges::sort(ret, cmp_fn);
    auto removed = std::ranges::unique(ret, cmp_fn);
    ret.erase(removed.begin(), removed.end());
    return ret;
}

std::vector<CTxMemPoolEntry::CTxMemPoolEntryRef> CTxMemPool::GetParents(const CTxMemPoolEntry& entry) const
{
    LOCK(cs);
    std::vector<CTxMemPoolEntry::CTxMemPoolEntryRef> ret;
    std::set<Txid> inputs;
    for (const auto& txin : entry.GetTx().vin) {
        inputs.insert(txin.prevout.hash);
    }
    for (const auto& hash : inputs) {
        std::optional<txiter> piter = GetIter(hash);
        if (piter) {
            ret.emplace_back(**piter);
        }
    }
    return ret;
}

Review comment (bug):
We expect to have at most `64` children here, right?
https://github.com/bitcoin/bitcoin/blob/ade0397f59f2fb59ab0e4ebb39869ac343cc54ee/src/txgraph.h#L17
If that's the case, wouldn't a quadratic algo be simpler?
```C++
std::vector<CTxMemPoolEntry::CTxMemPoolEntryRef> CTxMemPool::GetChildren(const CTxMemPoolEntry& entry) const
{
    LOCK(cs);
    std::vector<CTxMemPoolEntry::CTxMemPoolEntryRef> ret;
    const auto hash{entry.GetTx().GetHash()};
    for (auto it{mapNextTx.lower_bound(COutPoint(hash, 0))}; it != mapNextTx.end() && it->first->hash == hash; ++it) {
        const auto& child{*it->second};
        if (std::ranges::none_of(ret, [&](auto& ref) { return &ref.get() == &child; })) {
            ret.emplace_back(child);
        }
    }
    return ret;
}
```

This would also fix the `MempoolCheck` benchmark failure (which indicates no speed regression locally)

Code after:
bool TestLockPointValidity(CChain& active_chain, const LockPoints& lp)
{
    AssertLockHeld(cs_main);
    // If there are relative lock times then the maxInputBlock will be set
    // If there are no relative lock times, the LockPoints don't depend on the chain
    if (lp.maxInputBlock) {
        // Check whether active_chain is an extension of the block at which the LockPoints
        // calculation was valid.  If not LockPoints are no longer valid
        if (!active_chain.Contains(lp.maxInputBlock)) {
            return false;
        }
    }

    // LockPoints still valid
    return true;
}

std::vector<CTxMemPoolEntry::CTxMemPoolEntryRef> CTxMemPool::GetChildren(const CTxMemPoolEntry& entry) const
{
    std::vector<CTxMemPoolEntry::CTxMemPoolEntryRef> ret;
    const auto& hash = entry.GetTx().GetHash();
    {
        LOCK(cs);
        auto iter = mapNextTx.lower_bound(COutPoint(hash, 0));
        for (; iter != mapNextTx.end() && iter->first->hash == hash; ++iter) {
            ret.emplace_back(*(iter->second));
        }
    }
    std::ranges::sort(ret, CompareIteratorByHash{});
    auto removed = std::ranges::unique(ret, [](auto& a, auto& b) noexcept { return &a.get() == &b.get(); });
    ret.erase(removed.begin(), removed.end());
    return ret;
}

std::vector<CTxMemPoolEntry::CTxMemPoolEntryRef> CTxMemPool::GetParents(const CTxMemPoolEntry& entry) const
{
    LOCK(cs);
    std::vector<CTxMemPoolEntry::CTxMemPoolEntryRef> ret;
    std::set<Txid> inputs;
    for (const auto& txin : entry.GetTx().vin) {
        inputs.insert(txin.prevout.hash);
    }
    for (const auto& hash : inputs) {
        std::optional<txiter> piter = GetIter(hash);
        if (piter) {
            ret.emplace_back(**piter);
        }
    }
    return ret;
}