Switch CCoinsView and chainstate db from per-txid to per-txout

This patch makes several related changes:
* Changes the CCoinsView virtual methods (GetCoins, HaveCoins, ...)
  to be COutPoint/Coin-based rather than txid/CCoins-based.
* Changes the chainstate db to a new incompatible format that is also
  COutPoint/Coin based.
* Implements reconstruction code for hash_serialized_2.
* Adapts the coins_tests unit tests (thanks to Russell Yanofsky).

A side effect of the new CCoinsView model is that we can no longer
use the (unreliable) test for transaction outputs in the UTXO set
to determine whether we already have a particular transaction.

1 files changed, 33 insertions, 41 deletions

diff --git a/src/coins.h b/src/coins.h
index fcf7c47a56..ae85a199ca 100644
--- a/src/coins.h
+++ b/src/coins.h
@@ -299,28 +299,28 @@ public:
     }
 };
 
-class SaltedTxidHasher
+class SaltedOutpointHasher
 {
 private:
     /** Salt */
     const uint64_t k0, k1;
 
 public:
-    SaltedTxidHasher();
+    SaltedOutpointHasher();
 
     /**
      * This *must* return size_t. With Boost 1.46 on 32-bit systems the
      * unordered_map will behave unpredictably if the custom hasher returns a
      * uint64_t, resulting in failures when syncing the chain (#4634).
      */
-    size_t operator()(const uint256& txid) const {
-        return SipHashUint256(k0, k1, txid);
+    size_t operator()(const COutPoint& id) const {
+        return SipHashUint256Extra(k0, k1, id.hash, id.n);
     }
 };
 
 struct CCoinsCacheEntry
 {
-    CCoins coins; // The actual cached data.
+    Coin coins; // The actual cached data.
     unsigned char flags;
 
     enum Flags {
@@ -333,20 +333,21 @@ struct CCoinsCacheEntry
          */
     };
 
-    CCoinsCacheEntry() : coins(), flags(0) {}
+    CCoinsCacheEntry() : flags(0) {}
+    explicit CCoinsCacheEntry(Coin&& coin_) : coins(std::move(coin_)), flags(0) {}
 };
 
-typedef std::unordered_map<uint256, CCoinsCacheEntry, SaltedTxidHasher> CCoinsMap;
+typedef std::unordered_map<COutPoint, CCoinsCacheEntry, SaltedOutpointHasher> CCoinsMap;
 
 /** Cursor for iterating over CoinsView state */
 class CCoinsViewCursor
 {
 public:
     CCoinsViewCursor(const uint256 &hashBlockIn): hashBlock(hashBlockIn) {}
-    virtual ~CCoinsViewCursor();
+    virtual ~CCoinsViewCursor() {}
 
-    virtual bool GetKey(uint256 &key) const = 0;
-    virtual bool GetValue(CCoins &coins) const = 0;
+    virtual bool GetKey(COutPoint &key) const = 0;
+    virtual bool GetValue(Coin &coin) const = 0;
     virtual unsigned int GetValueSize() const = 0;
 
     virtual bool Valid() const = 0;
@@ -362,17 +363,17 @@ private:
 class CCoinsView
 {
 public:
-    //! Retrieve the CCoins (unspent transaction outputs) for a given txid
-    virtual bool GetCoins(const uint256 &txid, CCoins &coins) const;
+    //! Retrieve the Coin (unspent transaction output) for a given outpoint.
+    virtual bool GetCoins(const COutPoint &outpoint, Coin &coin) const;
 
-    //! Just check whether we have data for a given txid.
-    //! This may (but cannot always) return true for fully spent transactions
-    virtual bool HaveCoins(const uint256 &txid) const;
+    //! Just check whether we have data for a given outpoint.
+    //! This may (but cannot always) return true for spent outputs.
+    virtual bool HaveCoins(const COutPoint &outpoint) const;
 
     //! Retrieve the block hash whose state this CCoinsView currently represents
     virtual uint256 GetBestBlock() const;
 
-    //! Do a bulk modification (multiple CCoins changes + BestBlock change).
+    //! Do a bulk modification (multiple Coin changes + BestBlock change).
     //! The passed mapCoins can be modified.
     virtual bool BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlock);
 
@@ -395,12 +396,12 @@ protected:
 
 public:
     CCoinsViewBacked(CCoinsView *viewIn);
-    bool GetCoins(const uint256 &txid, CCoins &coins) const;
-    bool HaveCoins(const uint256 &txid) const;
-    uint256 GetBestBlock() const;
+    bool GetCoins(const COutPoint &outpoint, Coin &coin) const override;
+    bool HaveCoins(const COutPoint &outpoint) const override;
+    uint256 GetBestBlock() const override;
     void SetBackend(CCoinsView &viewIn);
-    bool BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlock);
-    CCoinsViewCursor *Cursor() const;
+    bool BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlock) override;
+    CCoinsViewCursor *Cursor() const override;
     size_t EstimateSize() const override;
 };
 
@@ -416,41 +417,32 @@ protected:
     mutable uint256 hashBlock;
     mutable CCoinsMap cacheCoins;
 
-    /* Cached dynamic memory usage for the inner CCoins objects. */
+    /* Cached dynamic memory usage for the inner Coin objects. */
     mutable size_t cachedCoinsUsage;
 
 public:
     CCoinsViewCache(CCoinsView *baseIn);
 
     // Standard CCoinsView methods
-    bool GetCoins(const uint256 &txid, CCoins &coins) const;
-    bool HaveCoins(const uint256 &txid) const;
+    bool GetCoins(const COutPoint &outpoint, Coin &coin) const;
     bool HaveCoins(const COutPoint &outpoint) const;
     uint256 GetBestBlock() const;
     void SetBestBlock(const uint256 &hashBlock);
     bool BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlock);
 
     /**
-     * Check if we have the given tx already loaded in this cache.
+     * Check if we have the given utxo already loaded in this cache.
      * The semantics are the same as HaveCoins(), but no calls to
      * the backing CCoinsView are made.
      */
-    bool HaveCoinsInCache(const uint256 &txid) const;
-
-    /**
-     * Return a pointer to CCoins in the cache, or NULL if not found. This is
-     * more efficient than GetCoins. Modifications to other cache entries are
-     * allowed while accessing the returned pointer.
-     */
-    const CCoins* AccessCoins(const uint256 &txid) const;
+    bool HaveCoinsInCache(const COutPoint &outpoint) const;
 
     /**
-     * Return a copy of a Coin in the cache, or a pruned one if not found. This is
+     * Return a reference to 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;
+    const Coin& AccessCoin(const COutPoint &output) const;
 
     /**
      * Add a coin. Set potential_overwrite to true if a non-pruned version may
@@ -473,12 +465,12 @@ public:
     bool Flush();
 
     /**
-     * Removes the transaction with the given hash from the cache, if it is
+     * Removes the UTXO with the given outpoint from the cache, if it is
      * not modified.
      */
-    void Uncache(const uint256 &txid);
+    void Uncache(const COutPoint &outpoint);
 
-    //! Calculate the size of the cache (in number of transactions)
+    //! Calculate the size of the cache (in number of transaction outputs)
     unsigned int GetCacheSize() const;
 
     //! Calculate the size of the cache (in bytes)
@@ -500,7 +492,7 @@ public:
     const CTxOut &GetOutputFor(const CTxIn& input) const;
 
 private:
-    CCoinsMap::iterator FetchCoins(const uint256 &txid) const;
+    CCoinsMap::iterator FetchCoins(const COutPoint &outpoint) 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.
@@ -515,6 +507,6 @@ private:
 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);
+const Coin& AccessByTxid(const CCoinsViewCache& cache, const uint256& txid);
 
 #endif // BITCOIN_COINS_H