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.
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.
Automatic sanity-testing: PASSED, see http://jenkins.bluematt.me/pull-tester/0fe8010a10bafd67f9131b2da034fb9cd7fc5024 for binaries and test log. This test script verifies pulls every time they are updated. It, however, dies sometimes and fails to test properly. If you are waiting on a test, please check timestamps to verify that the test.log is moving at http://jenkins.bluematt.me/pull-tester/current/ Contact BlueMatt on freenode if something looks broken.
Code looks sane and ACK-worthy. The concept is similar to something I did in pynode.
Did you actually instrument "no effect on memory usage", or is that a guess? I would like to see before and after numbers proving that :)
@jgarzik Just reasoning. For each CBlockIndex representing a node in the active chain, we remove 8 bytes from the CBlockIndex, and add 8 bytes to vBlockIndexByHeight. Actually, it should reduce memory usage slightly, as non-best-chain nodes also lose 8 bytes.