]> Git Repo - VerusCoin.git/blob - src/chain.cpp
merge dev; tests broken, need to use wallet for block rewards
[VerusCoin.git] / src / chain.cpp
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.
5
6 #include "chain.h"
7
8 using namespace std;
9
10 /**
11  * CChain implementation
12  */
13 void CChain::SetTip(CBlockIndex *pindex) {
14     if (pindex == NULL) {
15         vChain.clear();
16         return;
17     }
18     vChain.resize(pindex->nHeight + 1);
19     while (pindex && vChain[pindex->nHeight] != pindex) {
20         vChain[pindex->nHeight] = pindex;
21         pindex = pindex->pprev;
22     }
23 }
24
25 CBlockLocator CChain::GetLocator(const CBlockIndex *pindex) const {
26     int nStep = 1;
27     std::vector<uint256> vHave;
28     vHave.reserve(32);
29
30     if (!pindex)
31         pindex = Tip();
32     while (pindex) {
33         vHave.push_back(pindex->GetBlockHash());
34         // Stop when we have added the genesis block.
35         if (pindex->nHeight == 0)
36             break;
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];
42         } else {
43             // Otherwise, use O(log n) skiplist.
44             pindex = pindex->GetAncestor(nHeight);
45         }
46         if (vHave.size() > 10)
47             nStep *= 2;
48     }
49
50     return CBlockLocator(vHave);
51 }
52
53 const CBlockIndex *CChain::FindFork(const CBlockIndex *pindex) const {
54     if ( pindex == 0 )
55         return(0);
56     if (pindex->nHeight > Height())
57         pindex = pindex->GetAncestor(Height());
58     while (pindex && !Contains(pindex))
59         pindex = pindex->pprev;
60     return pindex;
61 }
62
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); }
65
66 /** Compute what height to jump back to with the CBlockIndex::pskip pointer. */
67 int static inline GetSkipHeight(int height) {
68     if (height < 2)
69         return 0;
70
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);
75 }
76
77 CBlockIndex* CBlockIndex::GetAncestor(int height)
78 {
79     if (height > nHeight || height < 0)
80         return NULL;
81
82     CBlockIndex* pindexWalk = this;
83     int heightWalk = nHeight;
84     while ( heightWalk > height && pindexWalk != 0 )
85     {
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;
95         } else {
96             pindexWalk = pindexWalk->pprev;
97             heightWalk--;
98         }
99     }
100     return pindexWalk;
101 }
102
103 const CBlockIndex* CBlockIndex::GetAncestor(int height) const
104 {
105     return const_cast<CBlockIndex*>(this)->GetAncestor(height);
106 }
107
108 void CBlockIndex::BuildSkip()
109 {
110     if (pprev)
111         pskip = pprev->GetAncestor(GetSkipHeight(nHeight));
112 }
This page took 0.030031 seconds and 4 git commands to generate.