aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorPieter Wuille <pieter.wuille@gmail.com>2017-01-13 15:48:28 -0800
committerPieter Wuille <pieter.wuille@gmail.com>2017-01-13 16:06:05 -0800
commite126d0c12ca66278d9e7b12187c5ff4fc02a7e6c (patch)
treeffbb05a46f5727d1a6f653682288af9600869938
parent3908fc4728059719bed0e1c7b1c8b388c2d4a8da (diff)
parent4b06e41c309123c4eefce0d3578c01efe1ae10df (diff)
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)
-rw-r--r--src/chain.cpp4
-rw-r--r--src/chain.h13
-rw-r--r--src/rpc/blockchain.cpp4
-rw-r--r--src/test/skiplist_tests.cpp43
-rw-r--r--src/validation.cpp2
-rw-r--r--src/wallet/rpcdump.cpp4
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);