Introduce new per-txout CCoinsViewCache functions

The new functions are:
* CCoinsViewCache::AddCoin: Add a single COutPoint/Coin pair.
* CCoinsViewCache::SpendCoin: Remove a single COutPoint.
* AddCoins: utility function that invokes CCoinsViewCache::AddCoin for
  each output in a CTransaction.
* AccessByTxid: utility function that searches for any output with
  a given txid.
* CCoinsViewCache::AccessCoin: retrieve the Coin for a COutPoint.
* CCoinsViewCache::HaveCoins: check whether a non-empty Coin exists
  for a given COutPoint.

The AddCoin and SpendCoin methods will eventually replace ModifyCoins
and ModifyNewCoins, AddCoins will replace CCoins::FromTx, and the new
AccessCoins and HaveCoins functions will replace their per-txid
counterparts.

Note that AccessCoin for now returns a copy of the Coin object. In a
later commit it will be change to returning a const reference (which
keeps working in all call sites).

2 files changed, 116 insertions, 2 deletions

diff --git a/src/coins.cpp b/src/coins.cpp
index 02f424fad6..3ac46d0806 100644
--- a/src/coins.cpp
+++ b/src/coins.cpp
@@ -4,6 +4,7 @@
 
 #include "coins.h"
 
+#include "consensus/consensus.h"
 #include "memusage.h"
 #include "random.h"
 
@@ -70,7 +71,7 @@ size_t CCoinsViewCache::DynamicMemoryUsage() const {
     return memusage::DynamicUsage(cacheCoins) + cachedCoinsUsage;
 }
 
-CCoinsMap::const_iterator CCoinsViewCache::FetchCoins(const uint256 &txid) const {
+CCoinsMap::iterator CCoinsViewCache::FetchCoins(const uint256 &txid) const {
     CCoinsMap::iterator it = cacheCoins.find(txid);
     if (it != cacheCoins.end())
         return it;
@@ -153,6 +154,58 @@ CCoinsModifier CCoinsViewCache::ModifyNewCoins(const uint256 &txid, bool coinbas
     return CCoinsModifier(*this, ret.first, 0);
 }
 
+void CCoinsViewCache::AddCoin(const COutPoint &outpoint, Coin&& coin, bool possible_overwrite) {
+    assert(!coin.IsPruned());
+    if (coin.out.scriptPubKey.IsUnspendable()) return;
+    CCoinsMap::iterator it;
+    bool inserted;
+    std::tie(it, inserted) = cacheCoins.emplace(std::piecewise_construct, std::forward_as_tuple(outpoint.hash), std::tuple<>());
+    bool fresh = false;
+    if (!inserted) {
+        cachedCoinsUsage -= it->second.coins.DynamicMemoryUsage();
+    }
+    if (!possible_overwrite) {
+        if (it->second.coins.IsAvailable(outpoint.n)) {
+            throw std::logic_error("Adding new coin that replaces non-pruned entry");
+        }
+        fresh = it->second.coins.IsPruned() && !(it->second.flags & CCoinsCacheEntry::DIRTY);
+    }
+    if (it->second.coins.vout.size() <= outpoint.n) {
+        it->second.coins.vout.resize(outpoint.n + 1);
+    }
+    it->second.coins.vout[outpoint.n] = std::move(coin.out);
+    it->second.coins.nHeight = coin.nHeight;
+    it->second.coins.fCoinBase = coin.fCoinBase;
+    it->second.flags |= CCoinsCacheEntry::DIRTY | (fresh ? CCoinsCacheEntry::FRESH : 0);
+    cachedCoinsUsage += it->second.coins.DynamicMemoryUsage();
+}
+
+void AddCoins(CCoinsViewCache& cache, const CTransaction &tx, int nHeight) {
+    bool fCoinbase = tx.IsCoinBase();
+    const uint256& txid = tx.GetHash();
+    for (size_t i = 0; i < tx.vout.size(); ++i) {
+        // Pass fCoinbase as the possible_overwrite flag to AddCoin, in order to correctly
+        // deal with the pre-BIP30 occurrances of duplicate coinbase transactions.
+        cache.AddCoin(COutPoint(txid, i), Coin(tx.vout[i], nHeight, fCoinbase), fCoinbase);
+    }
+}
+
+void CCoinsViewCache::SpendCoin(const COutPoint &outpoint, Coin* moveout) {
+    CCoinsMap::iterator it = FetchCoins(outpoint.hash);
+    if (it == cacheCoins.end()) return;
+    cachedCoinsUsage -= it->second.coins.DynamicMemoryUsage();
+    if (moveout && it->second.coins.IsAvailable(outpoint.n)) {
+        *moveout = Coin(it->second.coins.vout[outpoint.n], it->second.coins.nHeight, it->second.coins.fCoinBase);
+    }
+    it->second.coins.Spend(outpoint.n); // Ignore return value: SpendCoin has no effect if no UTXO found.
+    if (it->second.coins.IsPruned() && it->second.flags & CCoinsCacheEntry::FRESH) {
+        cacheCoins.erase(it);
+    } else {
+        cachedCoinsUsage += it->second.coins.DynamicMemoryUsage();
+        it->second.flags |= CCoinsCacheEntry::DIRTY;
+    }
+}
+
 const CCoins* CCoinsViewCache::AccessCoins(const uint256 &txid) const {
     CCoinsMap::const_iterator it = FetchCoins(txid);
     if (it == cacheCoins.end()) {
@@ -162,6 +215,18 @@ const CCoins* CCoinsViewCache::AccessCoins(const uint256 &txid) const {
     }
 }
 
+static const Coin coinEmpty;
+
+const Coin CCoinsViewCache::AccessCoin(const COutPoint &outpoint) const {
+    CCoinsMap::const_iterator it = FetchCoins(outpoint.hash);
+    if (it == cacheCoins.end() || !it->second.coins.IsAvailable(outpoint.n)) {
+        return coinEmpty;
+    } else {
+        return Coin(it->second.coins.vout[outpoint.n], it->second.coins.nHeight, it->second.coins.fCoinBase);
+    }
+}
+
+
 bool CCoinsViewCache::HaveCoins(const uint256 &txid) const {
     CCoinsMap::const_iterator it = FetchCoins(txid);
     // We're using vtx.empty() instead of IsPruned here for performance reasons,
@@ -171,6 +236,11 @@ bool CCoinsViewCache::HaveCoins(const uint256 &txid) const {
     return (it != cacheCoins.end() && !it->second.coins.vout.empty());
 }
 
+bool CCoinsViewCache::HaveCoins(const COutPoint &outpoint) const {
+    CCoinsMap::const_iterator it = FetchCoins(outpoint.hash);
+    return (it != cacheCoins.end() && it->second.coins.IsAvailable(outpoint.n));
+}
+
 bool CCoinsViewCache::HaveCoinsInCache(const uint256 &txid) const {
     CCoinsMap::const_iterator it = cacheCoins.find(txid);
     return it != cacheCoins.end();
@@ -318,3 +388,16 @@ CCoinsModifier::~CCoinsModifier()
 CCoinsViewCursor::~CCoinsViewCursor()
 {
 }
+
+static const size_t MAX_OUTPUTS_PER_BLOCK = MAX_BLOCK_BASE_SIZE /  ::GetSerializeSize(CTxOut(), SER_NETWORK, PROTOCOL_VERSION); // TODO: merge with similar definition in undo.h.
+
+const Coin AccessByTxid(const CCoinsViewCache& view, const uint256& txid)
+{
+    COutPoint iter(txid, 0);
+    while (iter.n < MAX_OUTPUTS_PER_BLOCK) {
+        const Coin& alternate = view.AccessCoin(iter);
+        if (!alternate.IsPruned()) return alternate;
+        ++iter.n;
+    }
+    return coinEmpty;
+}
diff --git a/src/coins.h b/src/coins.h
index 69c24ab45a..5879530f95 100644
--- a/src/coins.h
+++ b/src/coins.h
@@ -452,6 +452,7 @@ public:
     // Standard CCoinsView methods
     bool GetCoins(const uint256 &txid, CCoins &coins) const;
     bool HaveCoins(const uint256 &txid) const;
+    bool HaveCoins(const COutPoint &outpoint) const;
     uint256 GetBestBlock() const;
     void SetBestBlock(const uint256 &hashBlock);
     bool BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlock);
@@ -471,6 +472,14 @@ public:
     const CCoins* AccessCoins(const uint256 &txid) const;
 
     /**
+     * Return a copy of a Coin in the cache, or a pruned one if not found. This is
+     * more efficient than GetCoins. Modifications to other cache entries are
+     * allowed while accessing the returned pointer.
+     * TODO: return a reference to a Coin after changing CCoinsViewCache storage.
+     */
+    const Coin AccessCoin(const COutPoint &output) const;
+
+    /**
      * Return a modifiable reference to a CCoins. If no entry with the given
      * txid exists, a new one is created. Simultaneous modifications are not
      * allowed.
@@ -489,6 +498,19 @@ public:
     CCoinsModifier ModifyNewCoins(const uint256 &txid, bool coinbase);
 
     /**
+     * Add a coin. Set potential_overwrite to true if a non-pruned version may
+     * already exist.
+     */
+    void AddCoin(const COutPoint& outpoint, Coin&& coin, bool potential_overwrite);
+
+    /**
+     * Spend a coin. Pass moveto in order to get the deleted data.
+     * If no unspent output exists for the passed outpoint, this call
+     * has no effect.
+     */
+    void SpendCoin(const COutPoint &outpoint, Coin* moveto = nullptr);
+
+    /**
      * Push the modifications applied to this cache to its base.
      * Failure to call this method before destruction will cause the changes to be forgotten.
      * If false is returned, the state of this cache (and its backing view) will be undefined.
@@ -525,7 +547,7 @@ public:
     friend class CCoinsModifier;
 
 private:
-    CCoinsMap::const_iterator FetchCoins(const uint256 &txid) const;
+    CCoinsMap::iterator FetchCoins(const uint256 &txid) const;
 
     /**
      * By making the copy constructor private, we prevent accidentally using it when one intends to create a cache on top of a base cache.
@@ -533,4 +555,13 @@ private:
     CCoinsViewCache(const CCoinsViewCache &);
 };
 
+//! Utility function to add all of a transaction's outputs to a cache.
+// It assumes that overwrites are only possible for coinbase transactions,
+// TODO: pass in a boolean to limit these possible overwrites to known
+// (pre-BIP34) cases.
+void AddCoins(CCoinsViewCache& cache, const CTransaction& tx, int nHeight);
+
+//! Utility function to find any unspent output with a given txid.
+const Coin AccessByTxid(const CCoinsViewCache& cache, const uint256& txid);
+
 #endif // BITCOIN_COINS_H