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 {
54 if (pindex
->nHeight
> Height())
55 pindex
= pindex
->GetAncestor(Height());
56 while (pindex
&& !Contains(pindex
))
57 pindex
= pindex
->pprev
;
61 /** Turn the lowest '1' bit in the binary representation of a number into a '0'. */
62 int static inline InvertLowestOne(int n
) { return n
& (n
- 1); }
64 /** Compute what height to jump back to with the CBlockIndex::pskip pointer. */
65 int static inline GetSkipHeight(int height
) {
69 // Determine which height to jump back to. Any number strictly lower than height is acceptable,
70 // but the following expression seems to perform well in simulations (max 110 steps to go back
71 // up to 2**18 blocks).
72 return (height
& 1) ? InvertLowestOne(InvertLowestOne(height
- 1)) + 1 : InvertLowestOne(height
);
75 CBlockIndex
* CBlockIndex::GetAncestor(int height
)
77 if (height
> nHeight
|| height
< 0)
80 CBlockIndex
* pindexWalk
= this;
81 int heightWalk
= nHeight
;
82 while (heightWalk
> height
) {
83 int heightSkip
= GetSkipHeight(heightWalk
);
84 int heightSkipPrev
= GetSkipHeight(heightWalk
- 1);
85 if (pindexWalk
->pskip
!= NULL
&&
86 (heightSkip
== height
||
87 (heightSkip
> height
&& !(heightSkipPrev
< heightSkip
- 2 &&
88 heightSkipPrev
>= height
)))) {
89 // Only follow pskip if pprev->pskip isn't better than pskip->pprev.
90 pindexWalk
= pindexWalk
->pskip
;
91 heightWalk
= heightSkip
;
93 pindexWalk
= pindexWalk
->pprev
;
100 const CBlockIndex
* CBlockIndex::GetAncestor(int height
) const
102 return const_cast<CBlockIndex
*>(this)->GetAncestor(height
);
105 void CBlockIndex::BuildSkip()
108 pskip
= pprev
->GetAncestor(GetSkipHeight(nHeight
));