Line data    Source code

       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        5731 : void CChain::SetTip(CBlockIndex *pindex) {
      14        5731 :     if (pindex == NULL) {
      15         119 :         vChain.clear();
      16        5731 :         return;
      17             :     }
      18        5612 :     vChain.resize(pindex->nHeight + 1);
      19      249998 :     while (pindex && vChain[pindex->nHeight] != pindex) {
      20      233282 :         vChain[pindex->nHeight] = pindex;
      21      116641 :         pindex = pindex->pprev;
      22             :     }
      23             : }
      24             : 
      25        4939 : CBlockLocator CChain::GetLocator(const CBlockIndex *pindex) const {
      26        4939 :     int nStep = 1;
      27             :     std::vector<uint256> vHave;
      28        4939 :     vHave.reserve(32);
      29             : 
      30        4939 :     if (!pindex)
      31          87 :         pindex = Tip();
      32       44603 :     while (pindex) {
      33       89206 :         vHave.push_back(pindex->GetBlockHash());
      34             :         // Stop when we have added the genesis block.
      35       44603 :         if (pindex->nHeight == 0)
      36             :             break;
      37             :         // Exponentially larger steps back, plus the genesis block.
      38       79328 :         int nHeight = std::max(pindex->nHeight - nStep, 0);
      39       39664 :         if (Contains(pindex)) {
      40             :             // Use O(1) CChain index if possible.
      41       37792 :             pindex = (*this)[nHeight];
      42             :         } else {
      43             :             // Otherwise, use O(log n) skiplist.
      44        1872 :             pindex = pindex->GetAncestor(nHeight);
      45             :         }
      46       79328 :         if (vHave.size() > 10)
      47       15131 :             nStep *= 2;
      48             :     }
      49             : 
      50        9878 :     return CBlockLocator(vHave);
      51             : }
      52             : 
      53        5493 : const CBlockIndex *CChain::FindFork(const CBlockIndex *pindex) const {
      54       10986 :     if (pindex->nHeight > Height())
      55       10968 :         pindex = pindex->GetAncestor(Height());
      56       11020 :     while (pindex && !Contains(pindex))
      57          48 :         pindex = pindex->pprev;
      58        5493 :     return pindex;
      59             : }
      60             : 
      61             : /** Turn the lowest '1' bit in the binary representation of a number into a '0'. */
      62     5300148 : int static inline InvertLowestOne(int n) { return n & (n - 1); }
      63             : 
      64             : /** Compute what height to jump back to with the CBlockIndex::pskip pointer. */
      65             : int static inline GetSkipHeight(int height) {
      66     3537330 :     if (height < 2)
      67             :         return 0;
      68             : 
      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     7066758 :     return (height & 1) ? InvertLowestOne(InvertLowestOne(height - 1)) + 1 : InvertLowestOne(height);
      73             : }
      74             : 
      75      504451 : CBlockIndex* CBlockIndex::GetAncestor(int height)
      76             : {
      77      504451 :     if (height > nHeight || height < 0)
      78             :         return NULL;
      79             : 
      80             :     CBlockIndex* pindexWalk = this;
      81             :     int heightWalk = nHeight;
      82     2033091 :     while (heightWalk > height) {
      83     1535388 :         int heightSkip = GetSkipHeight(heightWalk);
      84     3070776 :         int heightSkipPrev = GetSkipHeight(heightWalk - 1);
      85     1535388 :         if (pindexWalk->pskip != NULL &&
      86     1278228 :             (heightSkip == height ||
      87      582355 :              (heightSkip > height && !(heightSkipPrev < heightSkip - 2 &&
      88      181564 :                                        heightSkipPrev >= height)))) {
      89             :             // Only follow pskip if pprev->pskip isn't better than pskip->pprev.
      90             :             pindexWalk = pindexWalk->pskip;
      91             :             heightWalk = heightSkip;
      92             :         } else {
      93      757648 :             pindexWalk = pindexWalk->pprev;
      94      757648 :             heightWalk--;
      95             :         }
      96             :     }
      97      497703 :     return pindexWalk;
      98             : }
      99             : 
     100           0 : const CBlockIndex* CBlockIndex::GetAncestor(int height) const
     101             : {
     102        7356 :     return const_cast<CBlockIndex*>(this)->GetAncestor(height);
     103             : }
     104             : 
     105      466556 : void CBlockIndex::BuildSkip()
     106             : {
     107      466556 :     if (pprev)
     108      933108 :         pskip = pprev->GetAncestor(GetSkipHeight(nHeight));
     109      466844 : }