merkletrie

Documentation

Index

• Constants
• Variables
• type CommitStats
• type Committer
• type InMemoryCommitter
  • func (mc *InMemoryCommitter) LoadPage(page uint64) (content []byte, err error)
  • func (mc *InMemoryCommitter) StorePage(page uint64, content []byte) error
• type MemoryConfig
• type Stats
• type Trie
  • func MakeTrie(committer Committer, memoryConfig MemoryConfig) (*Trie, error)
  • func (mt *Trie) Add(d []byte) (bool, error)
  • func (mt *Trie) Commit() (stats CommitStats, err error)
  • func (mt *Trie) Delete(d []byte) (bool, error)
  • func (mt *Trie) Evict(commit bool) (int, error)
  • func (mt *Trie) GetStats() (stats Stats, err error)
  • func (mt *Trie) RootHash() (crypto.Digest, error)
  • func (mt *Trie) SetCommitter(committer Committer) (prevCommitter Committer)

Constants

const (
	// MerkleTreeVersion is the version of the encoded trie. If we ever want to make changes and want to have upgrade path,
	// this would give us the ability to do so.
	MerkleTreeVersion = uint64(0x1000000010000000)
	// NodePageVersion is the version of the encoded node. If we ever want to make changes and want to have upgrade path,
	// this would give us the ability to do so.
	NodePageVersion = uint64(0x1000000010000000)
)

Variables

var ErrLoadedPageMissingNode = errors.New("loaded page is missing a node")

ErrLoadedPageMissingNode is returned when a request is made for a specific node identifier, and that identifier cannot be found in neither the in-memory cache or on the persistent storage.

var ErrMismatchingElementLength = errors.New("mismatching element length")

ErrMismatchingElementLength is returned when an element is being added/removed from the trie that doesn't align with the trie's previous elements length

var ErrMismatchingPageSize = errors.New("mismatching page size")

ErrMismatchingPageSize is returned when you try to provide an existing trie a committer with a different page size than it was originally created with.

var ErrPageDecodingFailuire = errors.New("error encountered while decoding page")

ErrPageDecodingFailuire is returned if the decoding of a page has failed.

var ErrRootPageDecodingFailuire = errors.New("error encountered while decoding root page")

ErrRootPageDecodingFailuire is returned if the decoding the root page has failed.

var ErrUnableToEvictPendingCommits = errors.New("unable to evict as pending commits available")

ErrUnableToEvictPendingCommits is returned if the tree was modified and Evict was called with commit=false

Types

type CommitStats

type CommitStats struct {
	NewPageCount                int
	NewNodeCount                int
	UpdatedPageCount            int
	UpdatedNodeCount            int
	DeletedPageCount            int
	FanoutReallocatedNodeCount  int
	PackingReallocatedNodeCount int
	LoadedPages                 int
}

CommitStats provides statistics about the operation of the commit() function

type Committer

type Committer interface {
	StorePage(page uint64, content []byte) error
	LoadPage(page uint64) (content []byte, err error)
}

Committer is the interface supporting serializing tries into persistent storage.

type InMemoryCommitter

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

InMemoryCommitter is a fully function in-memory committer, supporting persistence of pages.

func (*InMemoryCommitter) LoadPage

func (mc *InMemoryCommitter) LoadPage(page uint64) (content []byte, err error)

LoadPage load a single page from an in-memory persistence.

func (*InMemoryCommitter) StorePage

func (mc *InMemoryCommitter) StorePage(page uint64, content []byte) error

StorePage stores a single page in an in-memory persistence.

type MemoryConfig

type MemoryConfig struct {
	// NodesCountPerPage defines how many nodes each page would contain
	NodesCountPerPage int64
	// CachedNodesCount defines the number of nodes we want to retain in memory between consecutive Evict calls.
	CachedNodesCount int
	// PageFillFactor defines the desired fill ratio of a created page.
	PageFillFactor float32
	// MaxChildrenPagesThreshold define the maximum number of different pages that would be used for a single node's children.
	// it's being evaluated during Commit, for all the updated nodes.
	MaxChildrenPagesThreshold uint64
}

MemoryConfig used to define the Trie object memory configuration.

type Stats

type Stats struct {
	NodesCount uint
	LeafCount  uint
	Depth      int
	Size       int
}

Stats structure is a helper for finding underlaying statistics about the trie

type Trie

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

Trie is a merkle trie intended to efficiently calculate the merkle root of unordered elements

func MakeTrie

func MakeTrie(committer Committer, memoryConfig MemoryConfig) (*Trie, error)

MakeTrie creates a merkle trie

func (*Trie) Add

func (mt *Trie) Add(d []byte) (bool, error)

Add adds the given hash to the trie. returns false if the item already exists.

func (*Trie) Commit

func (mt *Trie) Commit() (stats CommitStats, err error)

Commit stores the existings trie using the committer.

func (*Trie) Delete

func (mt *Trie) Delete(d []byte) (bool, error)

Delete deletes the given hash to the trie, if such element exists. if no such element exists, return false

func (*Trie) Evict

func (mt *Trie) Evict(commit bool) (int, error)

Evict removes elements from the cache that are no longer needed.

func (*Trie) GetStats

func (mt *Trie) GetStats() (stats Stats, err error)

GetStats return statistics about the merkle trie

func (*Trie) RootHash

func (mt *Trie) RootHash() (crypto.Digest, error)

RootHash returns the root hash of all the elements in the trie

func (*Trie) SetCommitter

func (mt *Trie) SetCommitter(committer Committer) (prevCommitter Committer)

SetCommitter set the provided committter as the current committer, and return the old one.