Bitcoin ABC  0.22.13
P2P Digital Currency
blockindex.cpp
Go to the documentation of this file.
1 // Copyright (c) 2009-2020 The Bitcoin developers
2 // Distributed under the MIT software license, see the accompanying
3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 
5 #include <blockindex.h>
6 
10 static inline int InvertLowestOne(int n) {
11  return n & (n - 1);
12 }
13 
15 static inline int GetSkipHeight(int height) {
16  if (height < 2) {
17  return 0;
18  }
19 
20  // Determine which height to jump back to. Any number strictly lower than
21  // height is acceptable, but the following expression seems to perform well
22  // in simulations (max 110 steps to go back up to 2**18 blocks).
23  return (height & 1) ? InvertLowestOne(InvertLowestOne(height - 1)) + 1
24  : InvertLowestOne(height);
25 }
26 
28  if (pprev == nullptr) {
29  nChainTx = nTx;
30  nChainSize = nSize;
31  return true;
32  }
33 
34  if (pprev->HaveTxsDownloaded()) {
37  return true;
38  }
39 
40  nChainTx = 0;
41  nChainSize = 0;
42  return false;
43 }
44 
45 const CBlockIndex *CBlockIndex::GetAncestor(int height) const {
46  if (height > nHeight || height < 0) {
47  return nullptr;
48  }
49 
50  const CBlockIndex *pindexWalk = this;
51  int heightWalk = nHeight;
52  while (heightWalk > height) {
53  int heightSkip = GetSkipHeight(heightWalk);
54  int heightSkipPrev = GetSkipHeight(heightWalk - 1);
55  if (pindexWalk->pskip != nullptr &&
56  (heightSkip == height ||
57  (heightSkip > height && !(heightSkipPrev < heightSkip - 2 &&
58  heightSkipPrev >= height)))) {
59  // Only follow pskip if pprev->pskip isn't better than pskip->pprev.
60  pindexWalk = pindexWalk->pskip;
61  heightWalk = heightSkip;
62  } else {
63  assert(pindexWalk->pprev);
64  pindexWalk = pindexWalk->pprev;
65  heightWalk--;
66  }
67  }
68  return pindexWalk;
69 }
70 
72  return const_cast<CBlockIndex *>(
73  const_cast<const CBlockIndex *>(this)->GetAncestor(height));
74 }
75 
77  if (pprev) {
79  }
80 }
CBlockIndex * pskip
pointer to the index of some further predecessor of this block
Definition: blockindex.h:33
CBlockIndex * pprev
pointer to the index of the predecessor of this block
Definition: blockindex.h:30
uint64_t nChainSize
(memory only) Size of all blocks in the chain up to and including this block.
Definition: blockindex.h:72
unsigned int nChainTx
(memory only) Number of transactions in the chain up to and including this block. ...
Definition: blockindex.h:67
static int GetSkipHeight(int height)
Compute what height to jump back to with the CBlockIndex::pskip pointer.
Definition: blockindex.cpp:15
bool UpdateChainStats()
Update chain tx stats.
Definition: blockindex.cpp:27
void BuildSkip()
Build the skiplist pointer for this entry.
Definition: blockindex.cpp:76
unsigned int nSize
Size of this block.
Definition: blockindex.h:59
The block chain is a tree shaped structure starting with the genesis block at the root...
Definition: blockindex.h:23
int nHeight
height of the entry in the chain. The genesis block has height 0
Definition: blockindex.h:36
CBlockIndex * GetAncestor(int height)
Efficiently find an ancestor of this block.
Definition: blockindex.cpp:71
static int InvertLowestOne(int n)
Turn the lowest &#39;1&#39; bit in the binary representation of a number into a &#39;0&#39;.
Definition: blockindex.cpp:10
bool HaveTxsDownloaded() const
Check whether this block&#39;s and all previous blocks&#39; transactions have been downloaded (and stored to ...
Definition: blockindex.h:158
unsigned int nTx
Number of transactions in this block.
Definition: blockindex.h:54