Merge pull request #4470

f4b00be Add CChain::GetLocator() unit test (Pieter Wuille)
3c85d2e Fix CChain::GetLocator (Pieter Wuille)

1 files changed, 6 insertions, 8 deletions

diff --git a/src/main.cpp b/src/main.cpp
index e08b79418..86e60e4c6 100644
--- a/src/main.cpp
+++ b/src/main.cpp
@@ -423,15 +423,13 @@ CBlockLocator CChain::GetLocator(const CBlockIndex *pindex) const {
             break;
         // Exponentially larger steps back, plus the genesis block.
         int nHeight = std::max(pindex->nHeight - nStep, 0);
-        // Jump back quickly to the same height as the chain.
-        if (pindex->nHeight > nHeight)
-            pindex = pindex->GetAncestor(nHeight);
-        // In case pindex is not in this chain, iterate pindex->pprev to find blocks.
-        while (!Contains(pindex))
-            pindex = pindex->pprev;
-        // If pindex is in this chain, use direct height-based access.
-        if (pindex->nHeight > nHeight)
+        if (Contains(pindex)) {
+            // Use O(1) CChain index if possible.
             pindex = (*this)[nHeight];
+        } else {
+            // Otherwise, use O(log n) skiplist.
+            pindex = pindex->GetAncestor(nHeight);
+        }
         if (vHave.size() > 10)
             nStep *= 2;
     }