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 {
57 if (pindex
->nHeight
> Height())
58 pindex
= pindex
->GetAncestor(Height());
59 while (pindex
&& !Contains(pindex
))
60 pindex
= pindex
->pprev
;
64 CBlockIndex
* CChain::FindLatestBefore(int64_t nTime
) const
66 std::vector
<CBlockIndex
*>::const_iterator lower
= std::lower_bound(vChain
.begin(), vChain
.end(), nTime
,
67 [](CBlockIndex
* pBlock
, const int64_t& time
) -> bool { return pBlock
->GetBlockTime() < time
; });
68 return (lower
== vChain
.end() ? NULL
: *lower
);
71 /** Turn the lowest '1' bit in the binary representation of a number into a '0'. */
72 int static inline InvertLowestOne(int n
) { return n
& (n
- 1); }
74 /** Compute what height to jump back to with the CBlockIndex::pskip pointer. */
75 int static inline GetSkipHeight(int height
) {
79 // Determine which height to jump back to. Any number strictly lower than height is acceptable,
80 // but the following expression seems to perform well in simulations (max 110 steps to go back
81 // up to 2**18 blocks).
82 return (height
& 1) ? InvertLowestOne(InvertLowestOne(height
- 1)) + 1 : InvertLowestOne(height
);
85 CBlockIndex
* CBlockIndex::GetAncestor(int height
)
87 if (height
> nHeight
|| height
< 0)
90 CBlockIndex
* pindexWalk
= this;
91 int heightWalk
= nHeight
;
92 while (heightWalk
> height
) {
93 int heightSkip
= GetSkipHeight(heightWalk
);
94 int heightSkipPrev
= GetSkipHeight(heightWalk
- 1);
95 if (pindexWalk
->pskip
!= NULL
&&
96 (heightSkip
== height
||
97 (heightSkip
> height
&& !(heightSkipPrev
< heightSkip
- 2 &&
98 heightSkipPrev
>= height
)))) {
99 // Only follow pskip if pprev->pskip isn't better than pskip->pprev.
100 pindexWalk
= pindexWalk
->pskip
;
101 heightWalk
= heightSkip
;
103 assert(pindexWalk
->pprev
);
104 pindexWalk
= pindexWalk
->pprev
;
111 const CBlockIndex
* CBlockIndex::GetAncestor(int height
) const
113 return const_cast<CBlockIndex
*>(this)->GetAncestor(height
);
116 void CBlockIndex::BuildSkip()
119 pskip
= pprev
->GetAncestor(GetSkipHeight(nHeight
));
122 arith_uint256
GetBlockProof(const CBlockIndex
& block
)
124 arith_uint256 bnTarget
;
127 bnTarget
.SetCompact(block
.nBits
, &fNegative
, &fOverflow
);
128 if (fNegative
|| fOverflow
|| bnTarget
== 0)
130 // We need to compute 2**256 / (bnTarget+1), but we can't represent 2**256
131 // as it's too large for a arith_uint256. However, as 2**256 is at least as large
132 // as bnTarget+1, it is equal to ((2**256 - bnTarget - 1) / (bnTarget+1)) + 1,
133 // or ~bnTarget / (nTarget+1) + 1.
134 return (~bnTarget
/ (bnTarget
+ 1)) + 1;
137 int64_t GetBlockProofEquivalentTime(const CBlockIndex
& to
, const CBlockIndex
& from
, const CBlockIndex
& tip
, const Consensus::Params
& params
)
141 if (to
.nChainWork
> from
.nChainWork
) {
142 r
= to
.nChainWork
- from
.nChainWork
;
144 r
= from
.nChainWork
- to
.nChainWork
;
147 r
= r
* arith_uint256(params
.nPowTargetSpacing
) / GetBlockProof(tip
);
149 return sign
* std::numeric_limits
<int64_t>::max();
151 return sign
* r
.GetLow64();