patricia

Documentation

Overview

Package patricia computes the Merkle Patricia Tree Hash of a set of bit strings, as described in the Chain Protocol spec. See https://chain.com/docs/protocol/specifications/data#merkle-patricia-tree. Because a patricia tree (a radix tree with a radix of 2) provides efficient incremental updates, so does the Merkle Patricia Tree Hash computation, making this structure suitable for the blockchain full-state commitment.

Type Tree represents a set, where the elements are bit strings. The set must be prefix-free -- no item can be a prefix of any other -- enforced by Insert. The length of each bit string must also be a multiple of eight, because the interface uses []byte to represent an item.

The nodes in the tree form an immutable persistent data structure. It is okay to copy a Tree struct, which contains the root of the tree, to obtain a new tree with the same contents. The time to make such a copy is independent of the size of the tree.

Index

• func Walk(t *Tree, walkFn WalkFunc) error
• type Tree
  • func (t *Tree) Contains(item []byte) bool
  • func (t *Tree) Delete(item []byte)
  • func (t *Tree) Insert(item []byte) error
  • func (t *Tree) RootHash() bc.Hash
• type WalkFunc

Functions

func Walk

func Walk(t *Tree, walkFn WalkFunc) error

Walk walks t calling walkFn for each item. If an error is returned by walkFn at any point, processing is stopped and the error is returned.

Types

type Tree

type Tree struct {
	// contains filtered or unexported fields
}

Tree implements a patricia tree.

func (*Tree) Contains

func (t *Tree) Contains(item []byte) bool

Contains returns whether t contains item.

func (*Tree) Delete

func (t *Tree) Delete(item []byte)

Delete removes item from t, if present.

func (*Tree) Insert

func (t *Tree) Insert(item []byte) error

Insert inserts item into t.

It is an error for item to be a prefix of an element in t or to contain an element in t as a prefix. If item itself is already in t, Insert does nothing (and this is not an error).

func (*Tree) RootHash

func (t *Tree) RootHash() bc.Hash

RootHash returns the Merkle root of the tree.

type WalkFunc

type WalkFunc func(item []byte) error

WalkFunc is the type of the function called for each item visited by Walk. If an error is returned, processing stops.