diff options
-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. |