Package com.norswap.nanoeth.trees.patricia

Class PatriciaBranchNode

java.lang.Object
com.norswap.nanoeth.trees.patricia.PatriciaNode
com.norswap.nanoeth.trees.patricia.PatriciaBranchNode
Direct Known Subclasses:
MemPatriciaBranchNode, StorePatriciaBranchNode
public abstract class PatriciaBranchNode
extends PatriciaNode
Abstract base classes for branch nodes.

A branch node can have some attached value, which can happen when variable-size keys are used and there is a key that is a prefix of some other keys.

A branch has at least one child (if it has a child), or two children (otherwise) who differ in the nibble that follows the key prefix corresponding to this branch node.

  • Field Summary

    Fields inherited from class com.norswap.nanoeth.trees.patricia.PatriciaNode

    cap

  • Constructor Summary

    Constructors
    Constructor Description
    PatriciaBranchNode()  

  • Method Summary

    Modifier and Type Method Description
    PatriciaBranchNode add​(NodeStore store, Nibbles keySuffix, byte[] value)
    Returns the transformed node, after associating the given key with the given key suffix.
    int childAndValueCount()
    Returns the number of children held by this node, + 1 if value() is set.
    abstract PatriciaNode childAt​(NodeStore store, int nibble)
    Returns the child node with the given starting nibble, or null if there is no such child.
    abstract byte[] childCapAt​(int nibble)
    Returns the cap value of childAt(NodeStore, int) with parameter nibble, or null if there is no such child.
    void collectEntries​(NodeStore store, Nibbles prefix, Map<byte[],​byte[]> map)
    Adds all the entries store under this node to map, given that the prefix to reach this node is given by prefix.
    RLP compose()
    This method implements the structural composition function c (equation 197 and previous in the yellowpaper).
    abstract boolean hasChildAt​(int nibble)
    Returns true only if the branch node has a child with the given starting nibble.
    byte[] lookup​(NodeStore store, Nibbles keySuffix)
    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.
    PatriciaNode remove​(NodeStore store, Nibbles keySuffix)
    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.
    BranchStep step​(NodeStore store, Nibbles keySuffix)
    Returns a qudruplet of: this node.
    abstract byte[] value()
    Returns the value associated with this leaf node, or null if no value is associated.

    Methods inherited from class com.norswap.nanoeth.trees.patricia.PatriciaNode

    cap, merkleRoot, parse

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • PatriciaBranchNode

      public PatriciaBranchNode()

  • Method Details

    • value

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

    • hasChildAt

      public abstract boolean hasChildAt​(int nibble)
      Returns true only if the branch node has a child with the given starting nibble.

    • childAt

      @Nullable public abstract PatriciaNode childAt​(NodeStore store, int nibble)
      Returns the child node with the given starting nibble, or null if there is no such child.

    • childCapAt

      @Nullable public abstract byte[] childCapAt​(int nibble)
      Returns the cap value of childAt(NodeStore, int) with parameter nibble, or null if there is no such child.

      This is a separate method because in the abridged representation, the children's cap values are stored directly, but not the children themselves.

    • childAndValueCount

      public int childAndValueCount()
      Returns the number of children held by this node, + 1 if value() is set.

    • step

      public final 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 PatriciaBranchNode 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