patricia

Documentation

Overview

Package patricia implements a patricia tree, or a radix tree with a radix of 2 -- creating an uneven binary tree.

Each entry is a key value pair. The key determines where the value is placed in the tree, with each bit of the key indicating a path. Values are arbitrary byte slices but only the SHA3-256 hash of the value is stored within the tree.

The nodes in the tree form an immutable persistent data structure, therefore Copy is a O(1) operation.

Index

• Variables
• func Walk(t *Tree, walkFn WalkFunc) error
• type Leaf
• type Tree
  • func Copy(t *Tree) *Tree
  • func Reconstruct(vals []Leaf) (*Tree, error)
  • func (t *Tree) Contains(bkey, val []byte) bool
  • func (t *Tree) ContainsKey(bkey []byte) bool
  • func (t *Tree) Delete(bkey []byte) error
  • func (t *Tree) Insert(bkey, val []byte) error
  • func (t *Tree) RootHash() bc.Hash
• type WalkFunc

Variables

var ErrPrefix = errors.New("key provided is a prefix to other keys")

ErrPrefix is returned from Insert or Delete if the key provided is a prefix to existing nodes.

Functions

func Walk

func Walk(t *Tree, walkFn WalkFunc) error

Walk walks the patricia tree calling walkFn for each leaf in the tree. If an error is returned by walkFn at any point, processing is stopped and the error is returned.

Types

type Leaf

type Leaf struct {
	Key  []byte
	Hash bc.Hash
}

Leaf describes a key and its corresponding hash of a value inserted into the patricia tree.

type Tree

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

Tree implements a patricia tree.

func Copy

func Copy(t *Tree) *Tree

Copy returns a new tree with the same root as this tree. It is an O(1) operation.

func Reconstruct

func Reconstruct(vals []Leaf) (*Tree, error)

Reconstruct builds a tree with the provided leaf nodes.

func (*Tree) Contains

func (t *Tree) Contains(bkey, val []byte) bool

Contains returns true if the tree contains the provided key, value pair.

func (*Tree) ContainsKey

func (t *Tree) ContainsKey(bkey []byte) bool

ContainsKey returns true if the key contains the provided key, without checking its corresponding hash.

func (*Tree) Delete

func (t *Tree) Delete(bkey []byte) error

Delete removes up to one value with a matching key. After removing the node, it will rearrange the tree to the optimal structure.

func (*Tree) Insert

func (t *Tree) Insert(bkey, val []byte) error

Insert enters data into the tree. If the key is not already present in the tree, a new node will be created and inserted, rearranging the tree to the optimal structure. If the key is present, the existing node is found and its value is updated, leaving the structure of the tree alone.

func (*Tree) RootHash

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

RootHash returns the merkle root of the tree.

type WalkFunc

type WalkFunc func(l Leaf) error

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