142 lines
4.4 KiB
C++
142 lines
4.4 KiB
C++
/*
|
|
* This file is part of the Flowee project
|
|
* Copyright (c) 2009-2010 Satoshi Nakamoto
|
|
* Copyright (c) 2009-2014 The Bitcoin Core developers
|
|
* Copyright (C) 2019 Tom Zander <tom@flowee.org>
|
|
*
|
|
* This program is free software: you can redistribute it and/or modify
|
|
* it under the terms of the GNU General Public License as published by
|
|
* the Free Software Foundation, either version 3 of the License, or
|
|
* (at your option) any later version.
|
|
*
|
|
* This program is distributed in the hope that it will be useful,
|
|
* but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
* GNU General Public License for more details.
|
|
*
|
|
* You should have received a copy of the GNU General Public License
|
|
* along with this program. If not, see <http://www.gnu.org/licenses/>.
|
|
*/
|
|
|
|
#include "chain.h"
|
|
|
|
/**
|
|
* CChain implementation
|
|
*/
|
|
CChain::CChain()
|
|
: m_tip(nullptr)
|
|
{
|
|
}
|
|
|
|
CChain::CChain(const CChain &o)
|
|
: m_chain(o.m_chain),
|
|
m_tip(o.m_tip.load())
|
|
{
|
|
}
|
|
|
|
void CChain::SetTip(CBlockIndex *pindex) {
|
|
std::lock_guard<std::recursive_mutex> lock(m_lock);
|
|
if (pindex == nullptr) {
|
|
m_chain.clear();
|
|
m_tip = nullptr;
|
|
return;
|
|
}
|
|
m_chain.resize(pindex->nHeight + 1);
|
|
m_tip = pindex;
|
|
while (pindex && m_chain[pindex->nHeight] != pindex) {
|
|
m_chain[pindex->nHeight] = pindex;
|
|
pindex = pindex->pprev;
|
|
}
|
|
}
|
|
|
|
CBlockLocator CChain::GetLocator(const CBlockIndex *pindex) const {
|
|
std::lock_guard<std::recursive_mutex> lock(m_lock);
|
|
int nStep = 1;
|
|
std::vector<uint256> vHave;
|
|
vHave.reserve(32);
|
|
|
|
if (!pindex)
|
|
pindex = Tip();
|
|
while (pindex) {
|
|
vHave.push_back(pindex->GetBlockHash());
|
|
// Stop when we have added the genesis block.
|
|
if (pindex->nHeight == 0)
|
|
break;
|
|
// Exponentially larger steps back, plus the genesis block.
|
|
const int nHeight = std::max(pindex->nHeight - nStep, 0);
|
|
if (nHeight < (int) m_chain.size() && m_chain[nHeight] == pindex) {
|
|
// Use O(1) CChain index if possible.
|
|
pindex = m_chain[nHeight];
|
|
} else {
|
|
// Otherwise, use O(log n) skiplist.
|
|
pindex = pindex->GetAncestor(nHeight);
|
|
}
|
|
if (vHave.size() > 10)
|
|
nStep *= 2;
|
|
}
|
|
|
|
return CBlockLocator(vHave);
|
|
}
|
|
|
|
const CBlockIndex *CChain::FindFork(const CBlockIndex *pindex) const {
|
|
std::lock_guard<std::recursive_mutex> lock(m_lock);
|
|
if (pindex == nullptr) {
|
|
return nullptr;
|
|
}
|
|
if (pindex->nHeight > Height())
|
|
pindex = pindex->GetAncestor(Height());
|
|
while (pindex && !Contains(pindex))
|
|
pindex = pindex->pprev;
|
|
return pindex;
|
|
}
|
|
|
|
/** Turn the lowest '1' bit in the binary representation of a number into a '0'. */
|
|
int static inline InvertLowestOne(int n) { return n & (n - 1); }
|
|
|
|
/** Compute what height to jump back to with the CBlockIndex::pskip pointer. */
|
|
int static inline GetSkipHeight(int height) {
|
|
if (height < 2)
|
|
return 0;
|
|
|
|
// Determine which height to jump back to. Any number strictly lower than height is acceptable,
|
|
// but the following expression seems to perform well in simulations (max 110 steps to go back
|
|
// up to 2**18 blocks).
|
|
return (height & 1) ? InvertLowestOne(InvertLowestOne(height - 1)) + 1 : InvertLowestOne(height);
|
|
}
|
|
|
|
CBlockIndex* CBlockIndex::GetAncestor(int height)
|
|
{
|
|
if (height > nHeight || height < 0)
|
|
return nullptr;
|
|
|
|
CBlockIndex* pindexWalk = this;
|
|
int heightWalk = nHeight;
|
|
while (heightWalk > height) {
|
|
int heightSkip = GetSkipHeight(heightWalk);
|
|
int heightSkipPrev = GetSkipHeight(heightWalk - 1);
|
|
if (pindexWalk->pskip != nullptr &&
|
|
(heightSkip == height ||
|
|
(heightSkip > height && !(heightSkipPrev < heightSkip - 2 &&
|
|
heightSkipPrev >= height)))) {
|
|
// Only follow pskip if pprev->pskip isn't better than pskip->pprev.
|
|
pindexWalk = pindexWalk->pskip;
|
|
heightWalk = heightSkip;
|
|
} else {
|
|
pindexWalk = pindexWalk->pprev;
|
|
heightWalk--;
|
|
}
|
|
}
|
|
return pindexWalk;
|
|
}
|
|
|
|
const CBlockIndex* CBlockIndex::GetAncestor(int height) const
|
|
{
|
|
return const_cast<CBlockIndex*>(this)->GetAncestor(height);
|
|
}
|
|
|
|
void CBlockIndex::BuildSkip()
|
|
{
|
|
if (pprev)
|
|
pskip = pprev->GetAncestor(GetSkipHeight(nHeight));
|
|
}
|