Bugfix: remove conflicting transactions from memory pool

When a transaction A is in the memory pool, while a transaction B
(which shares an input with A) gets accepted into a block, A was
kept forever in the memory pool.

This commit adds a CTxMemPool::removeConflicts method, which
removes transactions that conflict with a given transaction, and
all their children.

This results in less transactions in the memory pool, and faster
construction of new blocks.

2 files changed, 28 insertions, 3 deletions

diff --git a/src/main.cpp b/src/main.cpp
index e2e993a138..22a8e03638 100644
--- a/src/main.cpp
+++ b/src/main.cpp
@@ -818,7 +818,7 @@ bool CTxMemPool::addUnchecked(const uint256& hash, CTransaction &tx)
 }
 
 
-bool CTxMemPool::remove(CTransaction &tx)
+bool CTxMemPool::remove(const CTransaction &tx, bool fRecursive)
 {
     // Remove transaction from memory pool
     {
@@ -826,6 +826,13 @@ bool CTxMemPool::remove(CTransaction &tx)
         uint256 hash = tx.GetHash();
         if (mapTx.count(hash))
         {
+            if (fRecursive) {
+                for (unsigned int i = 0; i < tx.vout.size(); i++) {
+                    std::map<COutPoint, CInPoint>::iterator it = mapNextTx.find(COutPoint(hash, i));
+                    if (it != mapNextTx.end())
+                        remove(*it->second.ptx, true);
+                }
+            }
             BOOST_FOREACH(const CTxIn& txin, tx.vin)
                 mapNextTx.erase(txin.prevout);
             mapTx.erase(hash);
@@ -835,6 +842,21 @@ bool CTxMemPool::remove(CTransaction &tx)
     return true;
 }
 
+bool CTxMemPool::removeConflicts(const CTransaction &tx)
+{
+    // Remove transactions which depend on inputs of tx, recursively
+    LOCK(cs);
+    BOOST_FOREACH(const CTxIn &txin, tx.vin) {
+        std::map<COutPoint, CInPoint>::iterator it = mapNextTx.find(txin.prevout);
+        if (it != mapNextTx.end()) {
+            const CTransaction &txConflict = *it->second.ptx;
+            if (txConflict != tx)
+                remove(txConflict, true);
+        }
+    }
+    return true;
+}
+
 void CTxMemPool::clear()
 {
     LOCK(cs);
@@ -1762,8 +1784,10 @@ bool SetBestChain(CBlockIndex* pindexNew)
         tx.AcceptToMemoryPool(false);
 
     // Delete redundant memory transactions that are in the connected branch
-    BOOST_FOREACH(CTransaction& tx, vDelete)
+    BOOST_FOREACH(CTransaction& tx, vDelete) {
         mempool.remove(tx);
+        mempool.removeConflicts(tx);
+    }
 
     // Update best block in wallet (so we can detect restored wallets)
     if (!fIsInitialDownload)
diff --git a/src/main.h b/src/main.h
index 8327141266..7a164c77fb 100644
--- a/src/main.h
+++ b/src/main.h
@@ -1814,7 +1814,8 @@ public:
 
     bool accept(CTransaction &tx, bool fCheckInputs, bool* pfMissingInputs);
     bool addUnchecked(const uint256& hash, CTransaction &tx);
-    bool remove(CTransaction &tx);
+    bool remove(const CTransaction &tx, bool fRecursive = false);
+    bool removeConflicts(const CTransaction &tx);
     void clear();
     void queryHashes(std::vector<uint256>& vtxid);
     void pruneSpent(const uint256& hash, CCoins &coins);