iotex-core: Index | Files | Directories

package trie

import ""


Package Files

branchnode.go branchroottrie.go extensionnode.go kvstore.go kvstoreimpl.go leafiterator.go leafnode.go trie.go trienode.go twolayertrie.go


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

func DefaultHashFunc Uses

func DefaultHashFunc(data []byte) []byte

DefaultHashFunc implements a default hash function

type HashFunc Uses

type HashFunc func([]byte) []byte

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

type Iterator Uses

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

Iterator iterates a trie

func NewLeafIterator Uses

func NewLeafIterator(tr Trie) (Iterator, error)

NewLeafIterator returns a new leaf iterator

type KVStore Uses

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 Uses

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

NewKVStore creates a new KVStore

type LeafIterator Uses

type LeafIterator struct {
    // contains filtered or unexported fields

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

func (*LeafIterator) Next Uses

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

Next moves iterator to next node

type Node Uses

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 Uses

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
    // EXTENSION is a spefic type of branch with only one child

type Option Uses

type Option func(Trie) error

Option sets parameters for SameKeyLenTrieContext construction parameter

func HashFuncOption Uses

func HashFuncOption(hashFunc HashFunc) Option

HashFuncOption sets the hash func for the trie

func KVStoreOption Uses

func KVStoreOption(kvStore KVStore) Option

KVStoreOption sets the kvStore for the trie

func KeyLengthOption Uses

func KeyLengthOption(len int) Option

KeyLengthOption sets the length of the keys saved in trie

func RootHashOption Uses

func RootHashOption(h []byte) Option

RootHashOption sets the root hash for the trie

func RootKeyOption Uses

func RootKeyOption(key string) Option

RootKeyOption sets the root key for the trie

type Trie Uses

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 Uses

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

NewTrie creates a trie with DB filename

type TwoLayerTrie Uses

type TwoLayerTrie struct {
    // contains filtered or unexported fields

TwoLayerTrie is a trie data structure with two layers

func NewTwoLayerTrie Uses

func NewTwoLayerTrie(dbForTrie KVStore, rootKey string) *TwoLayerTrie

NewTwoLayerTrie creates a two layer trie

func (*TwoLayerTrie) Delete Uses

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

Delete deletes an item in layer two

func (*TwoLayerTrie) Get Uses

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

Get returns the value in layer two

func (*TwoLayerTrie) RootHash Uses

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

RootHash returns the layer one trie root

func (*TwoLayerTrie) SetRootHash Uses

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

SetRootHash sets root hash for layer one trie

func (*TwoLayerTrie) Start Uses

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

Start starts the layer one trie

func (*TwoLayerTrie) Stop Uses

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

Stop stops the layer one trie

func (*TwoLayerTrie) Upsert Uses

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

Upsert upserts an item in layer two



Package trie imports 11 packages (graph) and is imported by 3 packages. Updated 2020-03-31. Refresh now. Tools for package owners.