diff options
author | mrbandrews <bandrewsny@gmail.com> | 2016-04-18 12:10:47 -0400 |
---|---|---|
committer | mrbandrews <bandrewsny@gmail.com> | 2016-04-18 12:10:47 -0400 |
commit | 87049e832d97d4f2808c0b479b21fc7b16c86934 (patch) | |
tree | d1528ef2e4db364e3c080fbd69785cc04f576f2d /src/rpc/blockchain.cpp | |
parent | 1b2460bd5824170ab85757e35f81197199cce9d6 (diff) | |
download | bitcoin-87049e832d97d4f2808c0b479b21fc7b16c86934.tar.xz |
Speed up getchaintips.
Diffstat (limited to 'src/rpc/blockchain.cpp')
-rw-r--r-- | src/rpc/blockchain.cpp | 29 |
1 files changed, 21 insertions, 8 deletions
diff --git a/src/rpc/blockchain.cpp b/src/rpc/blockchain.cpp index 34637b9f7e..3db827d9ae 100644 --- a/src/rpc/blockchain.cpp +++ b/src/rpc/blockchain.cpp @@ -760,17 +760,30 @@ UniValue getchaintips(const UniValue& params, bool fHelp) LOCK(cs_main); - /* Build up a list of chain tips. We start with the list of all - known blocks, and successively remove blocks that appear as pprev - of another block. */ + /* + * Idea: the set of chain tips is chainActive.tip, plus orphan blocks which do not have another orphan building off of them. + * Algorithm: + * - Make one pass through mapBlockIndex, picking out the orphan blocks, and also storing a set of the orphan block's pprev pointers. + * - Iterate through the orphan blocks. If the block isn't pointed to by another orphan, it is a chain tip. + * - add chainActive.Tip() + */ std::set<const CBlockIndex*, CompareBlocksByHeight> setTips; - BOOST_FOREACH(const PAIRTYPE(const uint256, CBlockIndex*)& item, mapBlockIndex) - setTips.insert(item.second); + std::set<const CBlockIndex*> setOrphans; + std::set<const CBlockIndex*> setPrevs; + BOOST_FOREACH(const PAIRTYPE(const uint256, CBlockIndex*)& item, mapBlockIndex) { - const CBlockIndex* pprev = item.second->pprev; - if (pprev) - setTips.erase(pprev); + if (!chainActive.Contains(item.second)) { + setOrphans.insert(item.second); + setPrevs.insert(item.second->pprev); + } + } + + for (std::set<const CBlockIndex*>::iterator it = setOrphans.begin(); it != setOrphans.end(); ++it) + { + if (setPrevs.erase(*it) == 0) { + setTips.insert(*it); + } } // Always report the currently active tip. |