stellar/stellard — pull request #145 by graydon (2014-10-21 18:28:07+00:00)
Title: SHAMap performance improvements (RIPD-434)

This reworks the way SHAMaps are stored, flushed, backed, and
traversed. Rather than storing the linkages in the SHAMap itself,
that information is now stored in the nodes. This makes
snapshotting much cheaper and also allows traverse work done on
behalf of one SHAMap to be used by other SHAMaps that share inner
nodes with that SHAMap.

When a SHAMap is modified, nodes are modified all the way up to the
root. This means that the modified nodes in a SHAMap can easily be
traversed for flushing. So they don't need to be separately tracked.

Summary
* Remove mTNByID
* Remove mDirtyNodes
* Much faster traverses
* Much Faster snapshots
* New algorithm for flushing
* New vistNodes/visitLeaves
* Avoid I/O if a map is unbacked