trie

Documentation

Index

• Variables
• func DefaultHashFunc(data []byte) []byte
• type HashFunc
• type Iterator
  • func NewLeafIterator(tr Trie) (Iterator, error)
• type KVStore
  • func NewKVStore(bucket string, dao db.KVStoreBasic) (KVStore, error)
• type LeafIterator
  • func (li *LeafIterator) Next() ([]byte, []byte, error)
• type Node
• type NodeType
• type Option
  • func HashFuncOption(hashFunc HashFunc) Option
  • func KVStoreOption(kvStore KVStore) Option
  • func KeyLengthOption(len int) Option
  • func RootHashOption(h []byte) Option
  • func RootKeyOption(key string) Option
• type Trie
  • func NewTrie(options ...Option) (Trie, error)
• type TwoLayerTrie
  • func NewTwoLayerTrie(dbForTrie KVStore, rootKey string) *TwoLayerTrie
  • func (tlt *TwoLayerTrie) Delete(layerOneKey []byte, layerTwoKey []byte) error
  • func (tlt *TwoLayerTrie) Get(layerOneKey []byte, layerTwoKey []byte) ([]byte, error)
  • func (tlt *TwoLayerTrie) RootHash() []byte
  • func (tlt *TwoLayerTrie) SetRootHash(rh []byte) error
  • func (tlt *TwoLayerTrie) Start(ctx context.Context) error
  • func (tlt *TwoLayerTrie) Stop(ctx context.Context) error
  • func (tlt *TwoLayerTrie) Upsert(layerOneKey []byte, layerTwoKey []byte, value []byte) error

Variables

var (
	// ErrInvalidTrie indicates something wrong causing invalid operation
	ErrInvalidTrie = errors.New("invalid trie operation")

	// ErrNotExist indicates entry does not exist
	ErrNotExist = errors.New("not exist in trie")
)

var ErrEndOfIterator = errors.New("hit the end of the iterator, no more item")

ErrEndOfIterator defines an error which will be returned

Functions

func DefaultHashFunc

func DefaultHashFunc(data []byte) []byte

DefaultHashFunc implements a default hash function

Types

type HashFunc

type HashFunc func([]byte) []byte

HashFunc defines a function to generate the hash which will be used as key in db

type Iterator

type Iterator interface {
	Next() ([]byte, []byte, error)
}

Iterator iterates a trie

func NewLeafIterator

func NewLeafIterator(tr Trie) (Iterator, error)

NewLeafIterator returns a new leaf iterator

type KVStore

type KVStore interface {
	// Start starts the KVStore
	Start(context.Context) error
	// Stop stops the KVStore
	Stop(context.Context) error
	// Put puts key, value pair into KVStore
	Put([]byte, []byte) error
	// Delete deletes record from KVStore by key
	Delete([]byte) error
	// Get gets the value from KVStore by key
	Get([]byte) ([]byte, error)
}

KVStore defines an interface for storing trie data as key-value pair

func NewKVStore

func NewKVStore(bucket string, dao db.KVStoreBasic) (KVStore, error)

NewKVStore creates a new KVStore

type LeafIterator

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

LeafIterator defines an iterator to go through all the leaves under given node

func (*LeafIterator) Next

func (li *LeafIterator) Next() ([]byte, []byte, error)

Next moves iterator to next node

type Node

type Node interface {
	// Type returns the type of a node
	Type() NodeType
	// Key returns the key of a node, only leaf has key
	Key() []byte
	// Value returns the value of a node, only leaf has value
	Value() []byte
	// contains filtered or unexported methods
}

Node defines the interface of a trie node Note: all the key-value pairs should be of the same length of keys

type NodeType

type NodeType int

NodeType is the type of a trie node

const (
	// BRANCH is an internal node type of length 1 and multiple child
	BRANCH NodeType = iota + 1
	// LEAF is a leaf node with value
	LEAF
	// EXTENSION is a spefic type of branch with only one child
	EXTENSION
)

type Option

type Option func(Trie) error

Option sets parameters for SameKeyLenTrieContext construction parameter

func HashFuncOption

func HashFuncOption(hashFunc HashFunc) Option

HashFuncOption sets the hash func for the trie

func KVStoreOption

func KVStoreOption(kvStore KVStore) Option

KVStoreOption sets the kvStore for the trie

func KeyLengthOption

func KeyLengthOption(len int) Option

KeyLengthOption sets the length of the keys saved in trie

func RootHashOption

func RootHashOption(h []byte) Option

RootHashOption sets the root hash for the trie

func RootKeyOption

func RootKeyOption(key string) Option

RootKeyOption sets the root key for the trie

type Trie

type Trie interface {
	// Start starts the trie and the corresponding dependencies
	Start(context.Context) error
	// Stop stops the trie
	Stop(context.Context) error
	// Upsert inserts a new entry
	Upsert([]byte, []byte) error
	// Get retrieves an existing entry
	Get([]byte) ([]byte, error)
	// Delete deletes an entry
	Delete([]byte) error
	// RootHash returns trie's root hash
	RootHash() []byte
	// SetRootHash sets a new root to trie
	SetRootHash([]byte) error
	// IsEmpty returns true is this is an empty trie
	IsEmpty() bool
	// DB returns the KVStore storing the node data
	DB() KVStore
	// contains filtered or unexported methods
}

Trie is the interface of Merkle Patricia Trie

func NewTrie

func NewTrie(options ...Option) (Trie, error)

NewTrie creates a trie with DB filename

type TwoLayerTrie

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

TwoLayerTrie is a trie data structure with two layers

func NewTwoLayerTrie

func NewTwoLayerTrie(dbForTrie KVStore, rootKey string) *TwoLayerTrie

NewTwoLayerTrie creates a two layer trie

func (*TwoLayerTrie) Delete

func (tlt *TwoLayerTrie) Delete(layerOneKey []byte, layerTwoKey []byte) error

Delete deletes an item in layer two

func (*TwoLayerTrie) Get

func (tlt *TwoLayerTrie) Get(layerOneKey []byte, layerTwoKey []byte) ([]byte, error)

Get returns the value in layer two

func (*TwoLayerTrie) RootHash

func (tlt *TwoLayerTrie) RootHash() []byte

RootHash returns the layer one trie root

func (*TwoLayerTrie) SetRootHash

func (tlt *TwoLayerTrie) SetRootHash(rh []byte) error

SetRootHash sets root hash for layer one trie

func (*TwoLayerTrie) Start

func (tlt *TwoLayerTrie) Start(ctx context.Context) error

Start starts the layer one trie

func (*TwoLayerTrie) Stop

func (tlt *TwoLayerTrie) Stop(ctx context.Context) error

Stop stops the layer one trie

func (*TwoLayerTrie) Upsert

func (tlt *TwoLayerTrie) Upsert(layerOneKey []byte, layerTwoKey []byte, value []byte) error

Upsert upserts an item in layer two