Page MenuHomeSource World

Basic pruning and gabbage collection support

Authored by sorpaas on Jan 1 2018, 12:08 PM.



This adds basic pruning support for the trie crate. Insert and Delete function would now return a Change struct, in which database addition and database removal can be tracked or
delayed. This allows clients to do more fancy stuff with the database without relying on a separate gabbage collector. Below is a list of commits included in this diff. Version is
bumped to 0.4 but unreleased yet.

  • [WIP] Use Change struct for merkle insert
  • [WIP] insert_by_empty
  • [WIP] GC support for insertion on a leaf node
  • [WIP] Fix insert by value
  • [WIP] All leaf and extension insertion operations
  • [WIP] Wrong method for accounting leaf values
  • [WIP] Styling fix
  • [WIP] Finish all unimplemented!() for insert
  • [WIP] Remove unused codes
  • [WIP] Primary compiling fixes after cleanup
  • [WIP] Compile the insert mod
  • [WIP] Make insert module compile
  • [WIP] Trie-level insertion implementation
  • [WIP] Initial implementation of memory trie
  • [WIP] Insert for memory trie
  • [WIP] Remove old trie tests
  • [WIP] Add back one of the old test
  • [WIP] Test simple insertion
  • [WIP] Fix a bug in node_nibble length
  • [WIP] Add old/new database assertion test
  • [WIP] Basic remove_by_value implementation
  • [WIP] Implement collapsing fns
  • [WIP] Get nonempty_node_count into a separate fn
  • [WIP] Add assertion that collapse will not meet empty value
  • [WIP] Return Option in delete_by_value
  • [WIP] Add handling in deletion of node for branch
  • [WIP] Fix compiler warnings
  • Add deletion fn in toplevel trie
  • Add deletion fn in memory trie
  • [WIP] Debugging
  • Fix tests and improve performance
  • Bump version (unreleased)
Test Plan

The old trie version 0.3 is used for testing. We use the old version to build a trie struct, and do insert/delete operations using the new version, and then check that they match and
no additional gabbage is included.

Diff Detail

rELIB rust-ethereum
Automatic diff as part of commit; lint not applicable.
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

sorpaas created this revision.Jan 1 2018, 12:08 PM
sorpaas updated this revision to Diff 44.Jan 1 2018, 12:12 PM
  • Temporarly disable dependency on local version for block
sorpaas updated this revision to Diff 45.Jan 1 2018, 12:13 PM

Diff against master

sorpaas accepted this revision.Jan 1 2018, 12:15 PM
This revision is now accepted and ready to land.Jan 1 2018, 12:15 PM
This revision was automatically updated to reflect the committed changes.