diff --git a/src/chain.h b/src/chain.h --- a/src/chain.h +++ b/src/chain.h @@ -434,9 +434,10 @@ const CBlockIndex *FindFork(const CBlockIndex *pindex) const; /** - * Find the earliest block with timestamp equal or greater than the given. + * 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) const; + CBlockIndex *FindEarliestAtLeast(int64_t nTime, int height) const; }; #endif // BITCOIN_CHAIN_H diff --git a/src/chain.cpp b/src/chain.cpp --- a/src/chain.cpp +++ b/src/chain.cpp @@ -65,12 +65,15 @@ return pindex; } -CBlockIndex *CChain::FindEarliestAtLeast(int64_t nTime) 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; - }); +CBlockIndex *CChain::FindEarliestAtLeast(int64_t nTime, int height) const { + 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/interfaces/chain.h b/src/interfaces/chain.h --- a/src/interfaces/chain.h +++ b/src/interfaces/chain.h @@ -106,22 +106,14 @@ 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 + //! or greater than the given time and height equal or greater than the + //! 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 findFirstBlockWithTime(int64_t time, - BlockHash *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; + virtual Optional + findFirstBlockWithTimeAndHeight(int64_t time, int height, + BlockHash *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/interfaces/chain.cpp b/src/interfaces/chain.cpp --- a/src/interfaces/chain.cpp +++ b/src/interfaces/chain.cpp @@ -75,9 +75,11 @@ CBlockIndex *block = ::ChainActive()[height]; return block && (block->nStatus.hasData() != 0) && block->nTx > 0; } - Optional findFirstBlockWithTime(int64_t time, - BlockHash *hash) override { - CBlockIndex *block = ::ChainActive().FindEarliestAtLeast(time); + Optional + findFirstBlockWithTimeAndHeight(int64_t time, int height, + BlockHash *hash) override { + CBlockIndex *block = + ::ChainActive().FindEarliestAtLeast(time, height); if (block) { if (hash) { *hash = block->GetBlockHash(); @@ -86,21 +88,6 @@ } 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/rpc/blockchain.cpp b/src/rpc/blockchain.cpp --- a/src/rpc/blockchain.cpp +++ b/src/rpc/blockchain.cpp @@ -1071,8 +1071,8 @@ 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, diff --git a/src/test/skiplist_tests.cpp b/src/test/skiplist_tests.cpp --- a/src/test/skiplist_tests.cpp +++ b/src/test/skiplist_tests.cpp @@ -156,7 +156,7 @@ // 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); @@ -179,36 +179,45 @@ 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(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)->nHeight, 0); - BOOST_CHECK_EQUAL(chain.FindEarliestAtLeast(-1)->nHeight, 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())->nHeight, - 0); - BOOST_CHECK_EQUAL( - chain.FindEarliestAtLeast(std::numeric_limits::min()) + chain.FindEarliestAtLeast(std::numeric_limits::min(), 0) ->nHeight, 0); BOOST_CHECK_EQUAL( chain .FindEarliestAtLeast( - -int64_t(std::numeric_limits::max()) - 1) + -int64_t(std::numeric_limits::max()) - 1, 0) ->nHeight, 0); BOOST_CHECK( - !chain.FindEarliestAtLeast(std::numeric_limits::max())); - BOOST_CHECK( - !chain.FindEarliestAtLeast(std::numeric_limits::max())); + !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)); + 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 --- a/src/wallet/wallet.cpp +++ b/src/wallet/wallet.cpp @@ -1884,8 +1884,9 @@ BlockHash 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__, @@ -4763,7 +4764,7 @@ if (Optional first_block = locked_chain->findFirstBlockWithTimeAndHeight( walletInstance->nTimeFirstKey - TIMESTAMP_WINDOW, - rescan_height)) { + rescan_height, nullptr)) { rescan_height = *first_block; } }