storage

Documentation

Index

• Constants
• Variables
• func RootLevelFromLeafIndex(leafIndex uint64) int
• type InorderIndex
  • func FromIndexOnLevel(indexOnLevel uint64, level int) InorderIndex
  • func FromLeafIndex(leafIndex uint64) InorderIndex
  • func FromPostorder(postorder uint64) InorderIndex
  • func (i InorderIndex) IsLeaf() bool
  • func (i InorderIndex) IsLeftChild() bool
  • func (i InorderIndex) IsRightChild() bool
  • func (i InorderIndex) LeafIndexOnLevel() uint64
  • func (i InorderIndex) LeftChild() (InorderIndex, error)
  • func (i InorderIndex) LeftMostChild() InorderIndex
  • func (i InorderIndex) Level() int
  • func (i InorderIndex) Parent() InorderIndex
  • func (i InorderIndex) Postorder() uint64
  • func (i InorderIndex) RightChild() (InorderIndex, error)
  • func (i InorderIndex) RightMostChild() InorderIndex
  • func (i InorderIndex) Sibling() InorderIndex
• type KvStore
  • func NewLevelDB(name string) (KvStore, error)
• type LevelDBHelper
  • func (h *LevelDBHelper) Close() error
  • func (h *LevelDBHelper) Delete(key []byte) error
  • func (h *LevelDBHelper) Get(key []byte) ([]byte, error)
  • func (h *LevelDBHelper) Put(key, value []byte) error
• type MerkleAccumulator
  • func NewMerkleTreeStreaming(db KvStore) (MerkleAccumulator, error)
• type MerkleTreeStream
  • func (s *MerkleTreeStream) Append(hash []byte) (uint64, error)
  • func (s *MerkleTreeStream) Close() error
  • func (s *MerkleTreeStream) Digest() ([]byte, error)
  • func (s *MerkleTreeStream) Get(id uint64) ([]byte, error)
  • func (s *MerkleTreeStream) GetProof(id uint64, digest []byte) ([][]byte, error)
  • func (s *MerkleTreeStream) Search(hash []byte) (uint64, error)

Constants

const HashPlaceholder = "merkle placeholder"

HashPlaceholder used to form a hash for calculating when there is no descendant fixed

Variables

var (
	// ErrOutOfRange indicates that request is out of range
	ErrOutOfRange = fmt.Errorf("out of range")
	// ErrNotFound indicates that key is not found
	ErrNotFound = fmt.Errorf("not found")
	// ErrEmpty indicates that there is no data
	ErrEmpty = fmt.Errorf("empty")
	// ErrInvalidDigest indicates that digest is invalid
	ErrInvalidDigest = fmt.Errorf("invliad digest")
)

Functions

func RootLevelFromLeafIndex

func RootLevelFromLeafIndex(leafIndex uint64) int

RootLevelFromLeafIndex calculates the root level of a binary tree containing certain number of leaves

Types

type InorderIndex

type InorderIndex uint64

InorderIndex represents the inorder traversal index of a binary tree with limited level

func FromIndexOnLevel

func FromIndexOnLevel(indexOnLevel uint64, level int) InorderIndex

FromIndexOnLevel calculates inorder index from the index of nodes upper certain level

func FromLeafIndex

func FromLeafIndex(leafIndex uint64) InorderIndex

FromLeafIndex calculates inorder index from the index of leaves

func FromPostorder

func FromPostorder(postorder uint64) InorderIndex

FromPostorder calculates inorder index from postorder index

func (InorderIndex) IsLeaf

func (i InorderIndex) IsLeaf() bool

IsLeaf judges whether the inorder index is a leaf

func (InorderIndex) IsLeftChild

func (i InorderIndex) IsLeftChild() bool

IsLeftChild judges whether the inorder index is or can be a left child

func (InorderIndex) IsRightChild

func (i InorderIndex) IsRightChild() bool

IsRightChild judges whether the inorder index is or can be a right child

func (InorderIndex) LeafIndexOnLevel

func (i InorderIndex) LeafIndexOnLevel() uint64

LeafIndexOnLevel returns n that i is the n-th leaf on this level

func (InorderIndex) LeftChild

func (i InorderIndex) LeftChild() (InorderIndex, error)

LeftChild returns the left child

func (InorderIndex) LeftMostChild

func (i InorderIndex) LeftMostChild() InorderIndex

LeftMostChild returns the left-most child

func (InorderIndex) Level

func (i InorderIndex) Level() int

Level calculates the level of inorder index

func (InorderIndex) Parent

func (i InorderIndex) Parent() InorderIndex

Parent returns the parent

func (InorderIndex) Postorder

func (i InorderIndex) Postorder() uint64

Postorder returns the postorder index converted from inorder index

func (InorderIndex) RightChild

func (i InorderIndex) RightChild() (InorderIndex, error)

RightChild returns the right child

func (InorderIndex) RightMostChild

func (i InorderIndex) RightMostChild() InorderIndex

RightMostChild returns the right-most child

func (InorderIndex) Sibling

func (i InorderIndex) Sibling() InorderIndex

Sibling returns the sibling

type KvStore

type KvStore interface {
	Get(key []byte) ([]byte, error)
	Put(key, value []byte) error
	Delete(key []byte) error
	Close() error
}

KvStore supports basic functions of kv store

func NewLevelDB

func NewLevelDB(name string) (KvStore, error)

NewLevelDB news or opens a level DB from specified directory

type LevelDBHelper

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

LevelDBHelper is helper of leveldb.DB

func (*LevelDBHelper) Close

func (h *LevelDBHelper) Close() error

Close closes level DB

func (*LevelDBHelper) Delete

func (h *LevelDBHelper) Delete(key []byte) error

Delete deletes a key-value from level DB

func (*LevelDBHelper) Get

func (h *LevelDBHelper) Get(key []byte) ([]byte, error)

Get gets value from level DB

func (*LevelDBHelper) Put

func (h *LevelDBHelper) Put(key, value []byte) error

Put puts a key-value to level DB

type MerkleAccumulator

type MerkleAccumulator interface {
	Append([]byte) (uint64, error)
	Get(uint64) ([]byte, error)
	Search([]byte) (uint64, error)
	Digest() ([]byte, error)
	GetProof(uint64, []byte) ([][]byte, error)
	Close() error
}

MerkleAccumulator defines core operations of merkle accumulator

func NewMerkleTreeStreaming

func NewMerkleTreeStreaming(db KvStore) (MerkleAccumulator, error)

NewMerkleTreeStreaming is only used at beginning of upchain server. The db should be only used by one MerkleTreeStream, so there is no mutex used directly here.

type MerkleTreeStream

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

MerkleTreeStream stores append-only data stream as a binary Merkle tree and supports core operations of MerkleAccumulator

func (*MerkleTreeStream) Append

func (s *MerkleTreeStream) Append(hash []byte) (uint64, error)

Append appends new hash to database layer. Append writes the database and states

func (*MerkleTreeStream) Close

func (s *MerkleTreeStream) Close() error

Close closes merkle tree streaming and lower components

func (*MerkleTreeStream) Digest

func (s *MerkleTreeStream) Digest() ([]byte, error)

Digest updates the root hash of Merkle tree and returns the root. Digest reads and may write to database and states.

func (*MerkleTreeStream) Get

func (s *MerkleTreeStream) Get(id uint64) ([]byte, error)

Get searches id in database layer to find its hash. Get only reads the database.

func (*MerkleTreeStream) GetProof

func (s *MerkleTreeStream) GetProof(id uint64, digest []byte) ([][]byte, error)

GetProof constructs a hash path who can proof the existence of data in certain id at the time of certain digest. GetProof reads and may write to database and states.

func (*MerkleTreeStream) Search

func (s *MerkleTreeStream) Search(hash []byte) (uint64, error)

Search searches hash in database layer to get the id of node. If there are several nodes contains the same hash, Search returns id of the oldest node (oldest strategy). Search reads and may write to database.