Documentation
¶
Index ¶
- Constants
- Variables
- func RootLevelFromLeafIndex(leafIndex uint64) int
- type 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
- type LevelDBHelper
- type MerkleAccumulator
- 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 ¶
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) 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 ¶
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) 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.
Source Files