Package com.norswap.nanoeth.trees.patricia

Interface NodeStore

All Known Implementing Classes:
MapNodeStore, TreeNodeStore
public interface NodeStore
Interface for a node store underlying a modified Merkle patricia tree.

This interface defines two types of method. First, factory methods to create implementations of PatriciaNode satisfying certain constraints, and which are able to work with the implemented store.

Second, data access methods to add, remove and retrieve nodes from the store.

It is expected a node store will only interact with nodes it is compatible with. Whenever a method in this interface receives a node parameter, it is free to assume it is from an implementation it supports.

Currently, this is implemented by MapNodeStore, which uses a in-memory hash map as store, and TreeNodeStore which represents a tree without store (i.e. each node has direct references to its children), so the data access method are no-ops or throw exceptions (the reason why there is a store at all is that we wish to share logic between tree and store implementations, and implementing a store for store-less trees makes this much easier.

  • Method Details

    • leafNode

      default PatriciaLeafNode leafNode​(Nibbles keySuffix, byte[] value)
      Creates a new leaf node with the given key suffix and value.

      The returned value must be added to the store.

    • extensionNode

      PatriciaExtensionNode extensionNode​(Nibbles keyFragment, PatriciaBranchNode child)
      Returns a new extension node with the given key fragment and child node.

      The returned value must be added to the store, nothing should be done with the child.

    • branchNode

      PatriciaBranchNode branchNode​(Pair<Nibbles,​PatriciaNode>... pairs)
      Returns a new branch node with the give children.

      If the nibbles part of a pair is empty, the child must be a leaf node, and its value will be used as the value of the branch node. Otherwise the node will be inserted into the new branch node, potentially after being extended as an extension node or longer leaf node to accomodate the remaining nibbles past the first (which is "consumed" by the branch node).

      The returned value must be added to the store, nothing should be done with the children.

    • withValue

      PatriciaBranchNode withValue​(PatriciaBranchNode branch, @Nullable @Retained byte[] value)
      Returns a copy of branch with its value set to value (possibly null).

      The returned value must be added to the store, while branch must be removed from the store if not null.

    • withChild

      PatriciaBranchNode withChild​(PatriciaBranchNode branch, int nibble, @Nullable PatriciaNode child)
      Returns a copy of branch with its child for the given nibble set to child.

      child is allowed to be null, but it is the responsability of the caller to ensure that the returned node is valid (i.e. has at a least a child and a value or two children).

      The returned value must be added to the store, while branch must be removed from the store. Nothing should be done with the child.

    • prepend

      default PatriciaNode prepend​(Nibbles nibbles, PatriciaNode node)
      Returns a new node that corresponds to the node that the given nibbles prepended. This results in a single node of the same type for leaf and extension nodes, and for an extension node holding the original node for branch nodes.

      The returned value must be added to the store, while node must be removed from the store if it does not become a child of the result.

    • getNode

      @Nullable PatriciaNode getNode​(byte[] cap)
      Return a node from its cap value, or null if no such node exists.

    • addNode

      <T extends PatriciaNode> T addNode​(T node)
      Adds a node to the store the returns it.

    • removeNode

      void removeNode​(PatriciaNode node)
      Removes the node from the store.

      The behaviour is implementation-defined, and in particular, this does not guarantee that after calling this method getNode(node.cap()) will return null.

      The major example is that for the chain state, reorgs are possible, so we want to keep old nodes around. However, we might want to record which block removed which nodes, so that we may eventually prune the tree.