aboutsummaryrefslogtreecommitdiff
path: root/src/chain.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/chain.cpp')
-rw-r--r--src/chain.cpp59
1 files changed, 59 insertions, 0 deletions
diff --git a/src/chain.cpp b/src/chain.cpp
new file mode 100644
index 0000000000..bcb497b2d4
--- /dev/null
+++ b/src/chain.cpp
@@ -0,0 +1,59 @@
+// Copyright (c) 2009-2010 Satoshi Nakamoto
+// Copyright (c) 2009-2014 The Bitcoin developers
+// Distributed under the MIT/X11 software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#include "chain.h"
+
+using namespace std;
+
+// CChain implementation
+
+CBlockIndex *CChain::SetTip(CBlockIndex *pindex) {
+ if (pindex == NULL) {
+ vChain.clear();
+ return NULL;
+ }
+ vChain.resize(pindex->nHeight + 1);
+ while (pindex && vChain[pindex->nHeight] != pindex) {
+ vChain[pindex->nHeight] = pindex;
+ pindex = pindex->pprev;
+ }
+ return pindex;
+}
+
+CBlockLocator CChain::GetLocator(const CBlockIndex *pindex) const {
+ int nStep = 1;
+ std::vector<uint256> vHave;
+ vHave.reserve(32);
+
+ if (!pindex)
+ pindex = Tip();
+ while (pindex) {
+ vHave.push_back(pindex->GetBlockHash());
+ // Stop when we have added the genesis block.
+ if (pindex->nHeight == 0)
+ break;
+ // Exponentially larger steps back, plus the genesis block.
+ int nHeight = std::max(pindex->nHeight - nStep, 0);
+ if (Contains(pindex)) {
+ // Use O(1) CChain index if possible.
+ pindex = (*this)[nHeight];
+ } else {
+ // Otherwise, use O(log n) skiplist.
+ pindex = pindex->GetAncestor(nHeight);
+ }
+ if (vHave.size() > 10)
+ nStep *= 2;
+ }
+
+ return CBlockLocator(vHave);
+}
+
+const CBlockIndex *CChain::FindFork(const CBlockIndex *pindex) const {
+ if (pindex->nHeight > Height())
+ pindex = pindex->GetAncestor(Height());
+ while (pindex && !Contains(pindex))
+ pindex = pindex->pprev;
+ return pindex;
+}