Merge #9490: Replace FindLatestBefore used by importmuti with FindEarliestAtLeast.

4b06e41 Add unit test for FindEarliestAtLeast (Suhas Daftuar)
997a98a Replace FindLatestBefore used by importmuti with FindEarliestAtLeast. (Gregory Maxwell)

6 files changed, 62 insertions, 8 deletions

diff --git a/src/chain.cpp b/src/chain.cpp
index 3cd7b33920..0f4d422b9f 100644
--- a/src/chain.cpp
+++ b/src/chain.cpp
@@ -61,10 +61,10 @@ const CBlockIndex *CChain::FindFork(const CBlockIndex *pindex) const {
     return pindex;
 }
 
-CBlockIndex* CChain::FindLatestBefore(int64_t nTime) const
+CBlockIndex* CChain::FindEarliestAtLeast(int64_t nTime) const
 {
     std::vector<CBlockIndex*>::const_iterator lower = std::lower_bound(vChain.begin(), vChain.end(), nTime,
-        [](CBlockIndex* pBlock, const int64_t& time) -> bool { return pBlock->GetBlockTime() < time; });
+        [](CBlockIndex* pBlock, const int64_t& time) -> bool { return pBlock->GetBlockTimeMax() < time; });
     return (lower == vChain.end() ? NULL : *lower);
 }
 
diff --git a/src/chain.h b/src/chain.h
index 989a71958c..acb29b667b 100644
--- a/src/chain.h
+++ b/src/chain.h
@@ -202,6 +202,9 @@ public:
     //! (memory only) Sequential id assigned to distinguish order in which blocks are received.
     int32_t nSequenceId;
 
+    //! (memory only) Maximum nTime in the chain upto and including this block.
+    unsigned int nTimeMax;
+
     void SetNull()
     {
         phashBlock = NULL;
@@ -216,6 +219,7 @@ public:
         nChainTx = 0;
         nStatus = 0;
         nSequenceId = 0;
+        nTimeMax = 0;
 
         nVersion       = 0;
         hashMerkleRoot = uint256();
@@ -281,6 +285,11 @@ public:
         return (int64_t)nTime;
     }
 
+    int64_t GetBlockTimeMax() const
+    {
+        return (int64_t)nTimeMax;
+    }
+
     enum { nMedianTimeSpan=11 };
 
     int64_t GetMedianTimePast() const
@@ -461,8 +470,8 @@ public:
     /** Find the last common block between this chain and a block index entry. */
     const CBlockIndex *FindFork(const CBlockIndex *pindex) const;
 
-    /** Find the most recent block with timestamp lower than the given. */
-    CBlockIndex* FindLatestBefore(int64_t nTime) const;
+    /** Find the earliest block with timestamp equal or greater than the given. */
+    CBlockIndex* FindEarliestAtLeast(int64_t nTime) const;
 };
 
 #endif // BITCOIN_CHAIN_H
diff --git a/src/rpc/blockchain.cpp b/src/rpc/blockchain.cpp
index bbcbde71cd..368654bfa6 100644
--- a/src/rpc/blockchain.cpp
+++ b/src/rpc/blockchain.cpp
@@ -839,9 +839,9 @@ UniValue pruneblockchain(const JSONRPCRequest& request)
     // Height value more than a billion is too high to be a block height, and
     // too low to be a block time (corresponds to timestamp from Sep 2001).
     if (heightParam > 1000000000) {
-        CBlockIndex* pindex = chainActive.FindLatestBefore(heightParam);
+        CBlockIndex* pindex = chainActive.FindEarliestAtLeast(heightParam);
         if (!pindex) {
-            throw JSONRPCError(RPC_INTERNAL_ERROR, "Could not find block before specified timestamp.");
+            throw JSONRPCError(RPC_INTERNAL_ERROR, "Could not find block with at least the specified timestamp.");
         }
         heightParam = pindex->nHeight;
     }
diff --git a/src/test/skiplist_tests.cpp b/src/test/skiplist_tests.cpp
index 5b4ef3fe7d..0b2fe0ef9d 100644
--- a/src/test/skiplist_tests.cpp
+++ b/src/test/skiplist_tests.cpp
@@ -100,4 +100,47 @@ BOOST_AUTO_TEST_CASE(getlocator_test)
     }
 }
 
+BOOST_AUTO_TEST_CASE(findearliestatleast_test)
+{
+    std::vector<uint256> vHashMain(100000);
+    std::vector<CBlockIndex> vBlocksMain(100000);
+    for (unsigned int i=0; i<vBlocksMain.size(); i++) {
+        vHashMain[i] = ArithToUint256(i); // Set the hash equal to the height
+        vBlocksMain[i].nHeight = i;
+        vBlocksMain[i].pprev = i ? &vBlocksMain[i - 1] : NULL;
+        vBlocksMain[i].phashBlock = &vHashMain[i];
+        vBlocksMain[i].BuildSkip();
+        if (i < 10) {
+            vBlocksMain[i].nTime = i;
+            vBlocksMain[i].nTimeMax = i;
+        } else {
+            // randomly choose something in the range [MTP, MTP*2]
+            int64_t medianTimePast = vBlocksMain[i].GetMedianTimePast();
+            int r = insecure_rand() % medianTimePast;
+            vBlocksMain[i].nTime = r + medianTimePast;
+            vBlocksMain[i].nTimeMax = std::max(vBlocksMain[i].nTime, vBlocksMain[i-1].nTimeMax);
+        }
+    }
+    // Check that we set nTimeMax up correctly.
+    unsigned int curTimeMax = 0;
+    for (unsigned int i=0; i<vBlocksMain.size(); ++i) {
+        curTimeMax = std::max(curTimeMax, vBlocksMain[i].nTime);
+        BOOST_CHECK(curTimeMax == vBlocksMain[i].nTimeMax);
+    }
+
+    // Build a CChain for the main branch.
+    CChain chain;
+    chain.SetTip(&vBlocksMain.back());
+
+    // Verify that FindEarliestAtLeast is correct.
+    for (unsigned int i=0; i<10000; ++i) {
+        // Pick a random element in vBlocksMain.
+        int r = insecure_rand() % vBlocksMain.size();
+        int64_t test_time = vBlocksMain[r].nTime;
+        CBlockIndex *ret = chain.FindEarliestAtLeast(test_time);
+        BOOST_CHECK(ret->nTimeMax >= test_time);
+        BOOST_CHECK((ret->pprev==NULL) || ret->pprev->nTimeMax < test_time);
+        BOOST_CHECK(vBlocksMain[r].GetAncestor(ret->nHeight) == ret);
+    }
+}
 BOOST_AUTO_TEST_SUITE_END()
diff --git a/src/validation.cpp b/src/validation.cpp
index 426b71b6eb..9013e82ce9 100644
--- a/src/validation.cpp
+++ b/src/validation.cpp
@@ -2611,6 +2611,7 @@ CBlockIndex* AddToBlockIndex(const CBlockHeader& block)
         pindexNew->nHeight = pindexNew->pprev->nHeight + 1;
         pindexNew->BuildSkip();
     }
+    pindexNew->nTimeMax = (pindexNew->pprev ? std::max(pindexNew->pprev->nTimeMax, pindexNew->nTime) : pindexNew->nTime);
     pindexNew->nChainWork = (pindexNew->pprev ? pindexNew->pprev->nChainWork : 0) + GetBlockProof(*pindexNew);
     pindexNew->RaiseValidity(BLOCK_VALID_TREE);
     if (pindexBestHeader == NULL || pindexBestHeader->nChainWork < pindexNew->nChainWork)
@@ -3432,6 +3433,7 @@ bool static LoadBlockIndexDB(const CChainParams& chainparams)
     {
         CBlockIndex* pindex = item.second;
         pindex->nChainWork = (pindex->pprev ? pindex->pprev->nChainWork : 0) + GetBlockProof(*pindex);
+        pindex->nTimeMax = (pindex->pprev ? std::max(pindex->pprev->nTimeMax, pindex->nTime) : pindex->nTime);
         // We can link the chain of blocks for which we've received transactions at some point.
         // Pruned nodes may have deleted the block.
         if (pindex->nTx > 0) {
diff --git a/src/wallet/rpcdump.cpp b/src/wallet/rpcdump.cpp
index a1912a78ec..7d4ed70ed9 100644
--- a/src/wallet/rpcdump.cpp
+++ b/src/wallet/rpcdump.cpp
@@ -1048,8 +1048,8 @@ UniValue importmulti(const JSONRPCRequest& mainRequest)
         }
     }
 
-    if (fRescan && fRunScan && requests.size() && nLowestTimestamp <= chainActive.Tip()->GetBlockTime()) {
-        CBlockIndex* pindex = nLowestTimestamp > minimumTimestamp ? chainActive.FindLatestBefore(nLowestTimestamp) : chainActive.Genesis();
+    if (fRescan && fRunScan && requests.size() && nLowestTimestamp <= chainActive.Tip()->GetBlockTimeMax()) {
+        CBlockIndex* pindex = nLowestTimestamp > minimumTimestamp ? chainActive.FindEarliestAtLeast(nLowestTimestamp) : chainActive.Genesis();
 
         if (pindex) {
             pwalletMain->ScanForWalletTransactions(pindex, true);