bitcoin/bitcoin — pull request #2814 by petertodd (2013-07-04 10:29:04+00:00)
Title: Child-pays-for-parent mempool

Calculates total uncommitted fees and transaction size required to include the transaction in a block for all transactions in the mempool. Cost is O(1) for mempool.accept() and limited to O(n) when a new block changes what transactions are in the mempool, either due to them being mined, conflicts, or reinstated by a re-org.

I haven't changed the mining code yet, and this is most useful with stuff like mempool expiration so it's not ready to be actually pulled yet. (mainly I want to see what the pulltester thinks) Note that this is a safe implementation, not a 100% accurate one, for reasons mentioned in CMemPoolTx::calcPrioritySums() In addition the memoized approach can't directly handle the case where a transaction with a lot of outputs is made worthwhile to mine because of multiple children.