From 765c0b364d41e9a251c3f88cbe203645854fd790 Mon Sep 17 00:00:00 2001 From: Antoine Riard Date: Tue, 26 Mar 2019 16:46:22 +0000 Subject: refactor: combine Chain::findFirstBlockWithTime/findFirstBlockWithTimeAndHeight As suggested in #14711, pass height to CChain::FindEarliestAtLeast to simplify Chain interface by combining findFirstBlockWithTime and findFirstBlockWithTimeAndHeight into one Extend findearliestatleast_edge_test in consequence --- src/chain.cpp | 7 ++++--- src/chain.h | 4 ++-- src/interfaces/chain.cpp | 18 ++---------------- src/interfaces/chain.h | 17 ++++------------- src/rpc/blockchain.cpp | 2 +- src/test/skiplist_tests.cpp | 46 ++++++++++++++++++++++++++++----------------- src/wallet/wallet.cpp | 4 ++-- 7 files changed, 44 insertions(+), 54 deletions(-) (limited to 'src') diff --git a/src/chain.cpp b/src/chain.cpp index d462f94ab5..5520d8149a 100644 --- a/src/chain.cpp +++ b/src/chain.cpp @@ -59,10 +59,11 @@ const CBlockIndex *CChain::FindFork(const CBlockIndex *pindex) const { return pindex; } -CBlockIndex* CChain::FindEarliestAtLeast(int64_t nTime) const +CBlockIndex* CChain::FindEarliestAtLeast(int64_t nTime, int height) const { - std::vector::const_iterator lower = std::lower_bound(vChain.begin(), vChain.end(), nTime, - [](CBlockIndex* pBlock, const int64_t& time) -> bool { return pBlock->GetBlockTimeMax() < time; }); + std::pair blockparams = std::make_pair(nTime, height); + std::vector::const_iterator lower = std::lower_bound(vChain.begin(), vChain.end(), blockparams, + [](CBlockIndex* pBlock, const std::pair& blockparams) -> bool { return pBlock->GetBlockTimeMax() < blockparams.first || pBlock->nHeight < blockparams.second; }); return (lower == vChain.end() ? nullptr : *lower); } diff --git a/src/chain.h b/src/chain.h index 2b6d2d082c..dd9cc2a598 100644 --- a/src/chain.h +++ b/src/chain.h @@ -465,8 +465,8 @@ public: /** Find the last common block between this chain and a block index entry. */ const CBlockIndex *FindFork(const CBlockIndex *pindex) const; - /** Find the earliest block with timestamp equal or greater than the given. */ - CBlockIndex* FindEarliestAtLeast(int64_t nTime) const; + /** Find the earliest block with timestamp equal or greater than the given time and height equal or greater than the given height. */ + CBlockIndex* FindEarliestAtLeast(int64_t nTime, int height) const; }; #endif // BITCOIN_CHAIN_H diff --git a/src/interfaces/chain.cpp b/src/interfaces/chain.cpp index 0c765f2092..fb3f8b62e3 100644 --- a/src/interfaces/chain.cpp +++ b/src/interfaces/chain.cpp @@ -83,29 +83,15 @@ class LockImpl : public Chain::Lock CBlockIndex* block = ::chainActive[height]; return block && ((block->nStatus & BLOCK_HAVE_DATA) != 0) && block->nTx > 0; } - Optional findFirstBlockWithTime(int64_t time, uint256* hash) override + Optional findFirstBlockWithTimeAndHeight(int64_t time, int height, uint256* hash) override { - CBlockIndex* block = ::chainActive.FindEarliestAtLeast(time); + CBlockIndex* block = ::chainActive.FindEarliestAtLeast(time, height); if (block) { if (hash) *hash = block->GetBlockHash(); return block->nHeight; } return nullopt; } - Optional findFirstBlockWithTimeAndHeight(int64_t time, int height) override - { - // TODO: Could update CChain::FindEarliestAtLeast() to take a height - // parameter and use it with std::lower_bound() to make this - // implementation more efficient and allow combining - // findFirstBlockWithTime and findFirstBlockWithTimeAndHeight into one - // method. - for (CBlockIndex* block = ::chainActive[height]; block; block = ::chainActive.Next(block)) { - if (block->GetBlockTime() >= time) { - return block->nHeight; - } - } - return nullopt; - } Optional findPruned(int start_height, Optional stop_height) override { if (::fPruneMode) { diff --git a/src/interfaces/chain.h b/src/interfaces/chain.h index a9b05f27fc..069d0f7822 100644 --- a/src/interfaces/chain.h +++ b/src/interfaces/chain.h @@ -100,21 +100,12 @@ public: //! pruned), and contains transactions. virtual bool haveBlockOnDisk(int height) = 0; - //! Return height of the first block in the chain with timestamp equal - //! or greater than the given time, or nullopt if there is no block with - //! a high enough timestamp. Also return the block hash as an optional - //! output parameter (to avoid the cost of a second lookup in case this - //! information is needed.) - virtual Optional findFirstBlockWithTime(int64_t time, uint256* hash) = 0; - //! Return height of the first block in the chain with timestamp equal //! or greater than the given time and height equal or greater than the - //! given height, or nullopt if there is no such block. - //! - //! Calling this with height 0 is equivalent to calling - //! findFirstBlockWithTime, but less efficient because it requires a - //! linear instead of a binary search. - virtual Optional findFirstBlockWithTimeAndHeight(int64_t time, int height) = 0; + //! given height, or nullopt if there is no block with a high enough + //! timestamp and height. Also return the block hash as an optional output parameter + //! (to avoid the cost of a second lookup in case this information is needed.) + virtual Optional findFirstBlockWithTimeAndHeight(int64_t time, int height, uint256* hash) = 0; //! Return height of last block in the specified range which is pruned, or //! nullopt if no block in the range is pruned. Range is inclusive. diff --git a/src/rpc/blockchain.cpp b/src/rpc/blockchain.cpp index 1827aec637..a95927fc27 100644 --- a/src/rpc/blockchain.cpp +++ b/src/rpc/blockchain.cpp @@ -1007,7 +1007,7 @@ static UniValue pruneblockchain(const JSONRPCRequest& request) // too low to be a block time (corresponds to timestamp from Sep 2001). if (heightParam > 1000000000) { // Add a 2 hour buffer to include blocks which might have had old timestamps - CBlockIndex* pindex = chainActive.FindEarliestAtLeast(heightParam - TIMESTAMP_WINDOW); + CBlockIndex* pindex = chainActive.FindEarliestAtLeast(heightParam - TIMESTAMP_WINDOW, 0); if (!pindex) { throw JSONRPCError(RPC_INVALID_PARAMETER, "Could not find block with at least the specified timestamp."); } diff --git a/src/test/skiplist_tests.cpp b/src/test/skiplist_tests.cpp index 5c46976ace..a96e6daeb2 100644 --- a/src/test/skiplist_tests.cpp +++ b/src/test/skiplist_tests.cpp @@ -136,7 +136,7 @@ BOOST_AUTO_TEST_CASE(findearliestatleast_test) // Pick a random element in vBlocksMain. int r = InsecureRandRange(vBlocksMain.size()); int64_t test_time = vBlocksMain[r].nTime; - CBlockIndex *ret = chain.FindEarliestAtLeast(test_time); + CBlockIndex* ret = chain.FindEarliestAtLeast(test_time, 0); BOOST_CHECK(ret->nTimeMax >= test_time); BOOST_CHECK((ret->pprev==nullptr) || ret->pprev->nTimeMax < test_time); BOOST_CHECK(vBlocksMain[r].GetAncestor(ret->nHeight) == ret); @@ -158,22 +158,34 @@ BOOST_AUTO_TEST_CASE(findearliestatleast_edge_test) CChain chain; chain.SetTip(&blocks.back()); - BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(50)->nHeight, 0); - BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(100)->nHeight, 0); - BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(150)->nHeight, 3); - BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(200)->nHeight, 3); - BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(250)->nHeight, 6); - BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(300)->nHeight, 6); - BOOST_CHECK(!chain.FindEarliestAtLeast(350)); - - BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(0)->nHeight, 0); - BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(-1)->nHeight, 0); - - BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(std::numeric_limits::min())->nHeight, 0); - BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(-int64_t(std::numeric_limits::max()) - 1)->nHeight, 0); - BOOST_CHECK(!chain.FindEarliestAtLeast(std::numeric_limits::max())); - BOOST_CHECK(!chain.FindEarliestAtLeast(std::numeric_limits::max())); - BOOST_CHECK(!chain.FindEarliestAtLeast(int64_t(std::numeric_limits::max()) + 1)); + BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(50, 0)->nHeight, 0); + BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(100, 0)->nHeight, 0); + BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(150, 0)->nHeight, 3); + BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(200, 0)->nHeight, 3); + BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(250, 0)->nHeight, 6); + BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(300, 0)->nHeight, 6); + BOOST_CHECK(!chain.FindEarliestAtLeast(350, 0)); + + BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(0, 0)->nHeight, 0); + BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(-1, 0)->nHeight, 0); + + BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(std::numeric_limits::min(), 0)->nHeight, 0); + BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(-int64_t(std::numeric_limits::max()) - 1, 0)->nHeight, 0); + BOOST_CHECK(!chain.FindEarliestAtLeast(std::numeric_limits::max(), 0)); + BOOST_CHECK(!chain.FindEarliestAtLeast(std::numeric_limits::max(), 0)); + BOOST_CHECK(!chain.FindEarliestAtLeast(int64_t(std::numeric_limits::max()) + 1, 0)); + + BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(0, -1)->nHeight, 0); + BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(0, 0)->nHeight, 0); + BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(0, 3)->nHeight, 3); + BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(0, 8)->nHeight, 8); + BOOST_CHECK(!chain.FindEarliestAtLeast(0, 9)); + + CBlockIndex* ret1 = chain.FindEarliestAtLeast(100, 2); + BOOST_CHECK(ret1->nTimeMax >= 100 && ret1->nHeight == 2); + BOOST_CHECK(!chain.FindEarliestAtLeast(300, 9)); + CBlockIndex* ret2 = chain.FindEarliestAtLeast(200, 4); + BOOST_CHECK(ret2->nTimeMax >= 200 && ret2->nHeight == 4); } BOOST_AUTO_TEST_SUITE_END() diff --git a/src/wallet/wallet.cpp b/src/wallet/wallet.cpp index 95756f988f..fd0297bae3 100644 --- a/src/wallet/wallet.cpp +++ b/src/wallet/wallet.cpp @@ -1722,7 +1722,7 @@ int64_t CWallet::RescanFromTime(int64_t startTime, const WalletRescanReserver& r uint256 start_block; { auto locked_chain = chain().lock(); - const Optional start_height = locked_chain->findFirstBlockWithTime(startTime - TIMESTAMP_WINDOW, &start_block); + const Optional start_height = locked_chain->findFirstBlockWithTimeAndHeight(startTime - TIMESTAMP_WINDOW, 0, &start_block); const Optional tip_height = locked_chain->getHeight(); WalletLogPrintf("%s: Rescanning last %i blocks\n", __func__, tip_height && start_height ? *tip_height - *start_height + 1 : 0); } @@ -4338,7 +4338,7 @@ std::shared_ptr CWallet::CreateWalletFromFile(interfaces::Chain& chain, // No need to read and scan block if block was created before // our wallet birthday (as adjusted for block time variability) if (walletInstance->nTimeFirstKey) { - if (Optional first_block = locked_chain->findFirstBlockWithTimeAndHeight(walletInstance->nTimeFirstKey - TIMESTAMP_WINDOW, rescan_height)) { + if (Optional first_block = locked_chain->findFirstBlockWithTimeAndHeight(walletInstance->nTimeFirstKey - TIMESTAMP_WINDOW, rescan_height, nullptr)) { rescan_height = *first_block; } } -- cgit v1.2.3