1 // Copyright (c) 2009-2010 Satoshi Nakamoto
2 // Copyright (c) 2009-2014 The Bitcoin Core developers
3 // Distributed under the MIT software license, see the accompanying
4 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
11 * CChain implementation
13 void CChain::SetTip(CBlockIndex *pindex) {
18 vChain.resize(pindex->nHeight + 1);
19 while (pindex && vChain[pindex->nHeight] != pindex) {
20 vChain[pindex->nHeight] = pindex;
21 pindex = pindex->pprev;
25 CBlockLocator CChain::GetLocator(const CBlockIndex *pindex) const {
27 std::vector<uint256> vHave;
33 vHave.push_back(pindex->GetBlockHash());
34 // Stop when we have added the genesis block.
35 if (pindex->nHeight == 0)
37 // Exponentially larger steps back, plus the genesis block.
38 int nHeight = std::max(pindex->nHeight - nStep, 0);
39 if (Contains(pindex)) {
40 // Use O(1) CChain index if possible.
41 pindex = (*this)[nHeight];
43 // Otherwise, use O(log n) skiplist.
44 pindex = pindex->GetAncestor(nHeight);
46 if (vHave.size() > 10)
50 return CBlockLocator(vHave);
53 const CBlockIndex *CChain::FindFork(const CBlockIndex *pindex) const {
56 if (pindex->nHeight > Height())
57 pindex = pindex->GetAncestor(Height());
58 while (pindex && !Contains(pindex))
59 pindex = pindex->pprev;
63 /** Turn the lowest '1' bit in the binary representation of a number into a '0'. */
64 int static inline InvertLowestOne(int n) { return n & (n - 1); }
66 /** Compute what height to jump back to with the CBlockIndex::pskip pointer. */
67 int static inline GetSkipHeight(int height) {
71 // Determine which height to jump back to. Any number strictly lower than height is acceptable,
72 // but the following expression seems to perform well in simulations (max 110 steps to go back
73 // up to 2**18 blocks).
74 return (height & 1) ? InvertLowestOne(InvertLowestOne(height - 1)) + 1 : InvertLowestOne(height);
77 CBlockIndex* CBlockIndex::GetAncestor(int height)
79 if (height > nHeight || height < 0)
82 CBlockIndex* pindexWalk = this;
83 int heightWalk = nHeight;
84 while ( heightWalk > height && pindexWalk != 0 )
86 int heightSkip = GetSkipHeight(heightWalk);
87 int heightSkipPrev = GetSkipHeight(heightWalk - 1);
88 if (pindexWalk->pskip != NULL &&
89 (heightSkip == height ||
90 (heightSkip > height && !(heightSkipPrev < heightSkip - 2 &&
91 heightSkipPrev >= height)))) {
92 // Only follow pskip if pprev->pskip isn't better than pskip->pprev.
93 pindexWalk = pindexWalk->pskip;
94 heightWalk = heightSkip;
96 pindexWalk = pindexWalk->pprev;
103 const CBlockIndex* CBlockIndex::GetAncestor(int height) const
105 return const_cast<CBlockIndex*>(this)->GetAncestor(height);
108 void CBlockIndex::BuildSkip()
111 pskip = pprev->GetAncestor(GetSkipHeight(nHeight));