bitcoin/bitcoin — pull request #2644 by sipa (2013-05-12 13:54:09+00:00)
Title: Make FindBlockByHeight constant-time

Remove the pnext pointer in CBlockIndex, and replace it with a vBlockIndexByHeight vector (no effect on memory usage). pnext can now be replaced by vBlockIndexByHeight[nHeight+1], but FindBlockByHeight becomes constant-time.

This also means the entire mapBlockIndex structure and the block index entries in it become purely blocktree-related data, and independent from the currently active chain, potentially allowing them to be protected by separate mutexes in the future.