Add a skiplist to the CBlockIndex structure.

This allows fast (O(log n)) access to far predecessor blocks.
Use it to speed up CChain::FindFork and CChain::GetLocator.

1 files changed, 11 insertions, 1 deletions

diff --git a/src/main.h b/src/main.h
index 9487078b7..1af86b065 100644
--- a/src/main.h
+++ b/src/main.h
@@ -677,6 +677,9 @@ public:
     // pointer to the index of the predecessor of this block
     CBlockIndex* pprev;
 
+    // pointer to the index of some further predecessor of this block
+    CBlockIndex* pskip;
+
     // height of the entry in the chain. The genesis block has height 0
     int nHeight;
 
@@ -716,6 +719,7 @@ public:
     {
         phashBlock = NULL;
         pprev = NULL;
+        pskip = NULL;
         nHeight = 0;
         nFile = 0;
         nDataPos = 0;
@@ -737,6 +741,7 @@ public:
     {
         phashBlock = NULL;
         pprev = NULL;
+        pskip = NULL;
         nHeight = 0;
         nFile = 0;
         nDataPos = 0;
@@ -869,9 +874,14 @@ public:
         }
         return false;
     }
-};
 
+    // Build the skiplist pointer for this entry.
+    void BuildSkip();
 
+    // Efficiently find an ancestor of this block.
+    CBlockIndex* GetAncestor(int height);
+    const CBlockIndex* GetAncestor(int height) const;
+};
 
 /** Used to marshal pointers into hashes for db storage. */
 class CDiskBlockIndex : public CBlockIndex