Package com.norswap.nanoeth.trees.patricia

Class PatriciaExtensionNode

java.lang.Object
com.norswap.nanoeth.trees.patricia.PatriciaNode
com.norswap.nanoeth.trees.patricia.PatriciaExtensionNode
Direct Known Subclasses:
MemPatriciaExtensionNode, StorePatriciaExtensionNode
public abstract class PatriciaExtensionNode
extends PatriciaNode
A an extension node in the patricia tree represents a shared sequence of nibbles between multiples keys (a "key fragment"). This is a (yellowpaper-mandated) compression method that avoids having a chain of single-child branch nodes. It can also happen that the key fragment is only a single nibble-long, since we use extension nodes when there is only one child (as it is more space-efficient than using a branch node — again, is is yellowpaper-mandated).

The node holds the key fragment and a child node, which is normally always a branch node.

  • Constructor Details

    • PatriciaExtensionNode

      public PatriciaExtensionNode()

  • Method Details

    • value

      @Nullable public byte[] value()
      Description copied from class: PatriciaNode
      Returns the value associated with the node, or null if no value is associated.
      Specified by:
      value in class PatriciaNode

    • keyFragment

      public abstract Nibbles keyFragment()
      Returns the key fragment associated with this node.

    • child

      public abstract PatriciaBranchNode child​(NodeStore store)
      Returns the child node of this extension node. This should always be a branch node.

    • childCap

      public abstract byte[] childCap()
      Returns the cap value of child(NodeStore).

      This is a separate method because in the abridged representation, the child's cap value is stored directly, but not the child itself.

    • step

      public BranchStep step​(NodeStore store, Nibbles keySuffix)
      Description copied from class: PatriciaNode
      Returns a qudruplet of:
      1. this node.
      2. the child in which to look for the value for the given key suffix (or equivalently, the child to modify to insert a value to be associated with the given key suffix). Can be null if no such child exists.
      3. the number of nibbles shared between this node and the key suffix. For leaf and extension node, this will be the length of the shared prefix the key suffix and the node's key fragment. For branch nodes, this will be 0 if the returned node is this and 1 otherwise.
      4. the number of nibbles left in the key suffix after deducting the shared nibbles.
      Specified by:
      step in class PatriciaNode

    • lookup

      public byte[] lookup​(NodeStore store, Nibbles keySuffix)
      Description copied from class: PatriciaNode
      Lookup the entry with the given key suffix, the suffix of a sequence of nibbles, where the missing prefix was used to reach the present node.

      This must handle empty nibble sequences.

      Specified by:
      lookup in class PatriciaNode

    • add

      public PatriciaNode add​(NodeStore store, Nibbles keySuffix, byte[] value)
      Description copied from class: PatriciaNode
      Returns the transformed node, after associating the given key with the given key suffix.

      This must handle empty nibble sequences.

      The method must add its return value to the store, and remove the current node from the store. Any other node added/removed from the tree in the process must similarly be added/removed from the store.

      Specified by:
      add in class PatriciaNode

    • remove

      public PatriciaNode remove​(NodeStore store, Nibbles keySuffix)
      Description copied from class: PatriciaNode
      Returns the transformed node, after removing the entry for the given key suffix (if any), or returns null if the removal of the key means that the node itself must disappear.

      This must handle empty nibble sequences.

      The method must add its return value to the store, and remove the current node from the store. Any other node added/removed from the tree in the process must similarly be added/removed from the store.

      Specified by:
      remove in class PatriciaNode

    • compose

      public final RLP compose()
      Description copied from class: PatriciaNode
      This method implements the structural composition function c (equation 197 and previous in the yellowpaper). See the README of this package for more information.
      Specified by:
      compose in class PatriciaNode

    • collectEntries

      public void collectEntries​(NodeStore store, Nibbles prefix, Map<byte[],​byte[]> map)
      Description copied from class: PatriciaNode
      Adds all the entries store under this node to map, given that the prefix to reach this node is given by prefix.
      Specified by:
      collectEntries in class PatriciaNode