trie

package
v1.3.28 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Apr 8, 2022 License: Apache-2.0 Imports: 16 Imported by: 4

Documentation

Index

Constants

View Source 
const (
	HistoryTreeDepth = 16 // Tree height: Any value can be reached after 16 nodes (including the root node)
	ValueKeyLength   = 4  // The height of the tree in each node is 4 (to reach value after 4 nodes)
)

Variables

View Source 
var (
	ErrMismatchProof = errors.New("proof mismatched")
	ErrMissingValue  = errors.New("value missing")
	ErrMissingChild  = errors.New("child missing")
	ErrNotExist      = errors.New("not exist")
)

Functions

func CheckTrieRoot 

func CheckTrieRoot(root []byte, rootShouldBe []byte) error

func DefaultValueExpander 

func DefaultValueExpander(hashbytes []byte, adapter db.DataAdapter) ([]byte, error)

func DefaultValueHasher 

func DefaultValueHasher(value interface{}, valuebytes []byte) ([]byte, error)

func IsEmptyTrieRoot added in v1.3.6 

func IsEmptyTrieRoot(root []byte) bool

func MarshalAsMap 

func MarshalAsMap(t ITrie, w io.Writer) error

func NewNode 

func NewNode(hash []byte, generation uint64, typ reflect.Type) *node

func NewNodeWithFuncs 

func NewNodeWithFuncs(hash []byte, generation uint64, encode NodeValueEncode, decode NodeValueDecode,
	hasher NodeValueHasher, expander NodeValueExpander) *node

func NewValueIterator 

func NewValueIterator(trie *Trie) *trieValueIterator

func ToBinary 

func ToBinary(b byte, length int) ([]byte, error)

Converts a byte to a binary byte array, where each byte is 0x0 or 0x1

func ToByte 

func ToByte(bs []byte) (byte, error)

The binary byte array represented by bs is restored to a byte. Each byte of bs is 0x0 or 0x1, and supports up to 8 bits of binary

func VerifyProofChain 

func VerifyProofChain(toBeProof common.Hash, proofChain ProofChain, expected []byte) bool

Types

type BatchPutter 

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

func NewBatchPutter 

func NewBatchPutter(t *Trie, mod int) *BatchPutter

func (*BatchPutter) Count 

func (p *BatchPutter) Count() int

func (*BatchPutter) Put 

func (p *BatchPutter) Put(key []byte, value interface{}) (bool, error)

type BinaryNode 

type BinaryNode struct {
	Left  []byte
	Right []byte
}

func (*BinaryNode) HashValue 

func (n *BinaryNode) HashValue() ([]byte, error)

type ChildFlag 

type ChildFlag [2]byte

func (ChildFlag) Clone 

func (c ChildFlag) Clone() ChildFlag

func (ChildFlag) MarshalText 

func (c ChildFlag) MarshalText() ([]byte, error)

func (*ChildFlag) UnmarshalText 

func (c *ChildFlag) UnmarshalText(input []byte) error

type HistoryTree 

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

An 8-byte unsigned integer (block height) is serialized into 8 bytes in big-endian (high order first) order, and then create a complete binary tree with one nibble one level of TreeNode

func NewHistoryTree 

func NewHistoryTree(dbase db.Database, rootHash []byte, checkPrecedingNil bool) (*HistoryTree, error)

func RestoreTreeFromProofs 

func RestoreTreeFromProofs(dbase db.Database, key uint64, value []byte, proofs ProofChain) (tree *HistoryTree, err error)

func (*HistoryTree) Append 

func (h *HistoryTree) Append(key uint64, value []byte) (err error)

append at the end in order, if key != expecting, or value is empty, return ErrIllegalParams

func (*HistoryTree) CollapseBefore 

func (h *HistoryTree) CollapseBefore(key uint64) error

func (*HistoryTree) Commit 

func (h *HistoryTree) Commit() (err error)

func (HistoryTree) Expecting 

func (h HistoryTree) Expecting() uint64

func (*HistoryTree) Get 

func (h *HistoryTree) Get(key uint64) (value []byte, exist bool)

func (*HistoryTree) GetProof 

func (h *HistoryTree) GetProof(key uint64) (value []byte, proofs ProofChain, ok bool)

func (*HistoryTree) Has 

func (h *HistoryTree) Has(key uint64) bool

func (*HistoryTree) HashValue 

func (h *HistoryTree) HashValue() ([]byte, error)

func (*HistoryTree) MergeProof 

func (h *HistoryTree) MergeProof(key uint64, value []byte, proofs ProofChain) error

Merge the proofs under the same rootHash into the tree

func (*HistoryTree) Rebase added in v1.3.14 

func (h *HistoryTree) Rebase(dbase db.Database) (*HistoryTree, error)

func (HistoryTree) String 

func (h HistoryTree) String() string

type ITrie 

type ITrie interface {
	HashValue() (hashValue []byte, err error)
	Get(key []byte) (value interface{}, ok bool)
	Put(key []byte, value interface{}) bool
	PutValue(value TrieValue) bool
	Delete(key []byte) (changed bool, oldValue interface{})
	IsDirty() bool
	Commit() error
	// According to the key, the value object corresponding to the key and its proof chain
	// are returned. ok returns whether the corresponding value is found successfully and
	// the proof is generated
	GetProof(key []byte) (value interface{}, proof ProofChain, ok bool)
	GetExistenceProof(key []byte) (exist bool, proofs ProofChain, err error)
	ValueIterator() ValueIterator
}

type KeyPart 

type KeyPart []byte

for JSON serialization method

func (KeyPart) Bytes 

func (k KeyPart) Bytes() []byte

func (KeyPart) Clone 

func (k KeyPart) Clone() KeyPart

func (KeyPart) MarshalText 

func (k KeyPart) MarshalText() ([]byte, error)

func (*KeyPart) UnmarshalText 

func (k *KeyPart) UnmarshalText(input []byte) error

type NodeHasher 

type NodeHasher struct {
	Header     NodeHeader   // NodeHeader of the node in Trie
	ValueHash  *common.Hash // hash of the node value, could be nil
	ChildHashs [][]byte     // hash value array of all non-nil children, nil if there are no children
}

func (*NodeHasher) MakeProof 

func (h *NodeHasher) MakeProof(needProof bool, ptype ProofType, index int) (nodeHash []byte, nodeProof *NodeProof, err error)

needProof: whether proof needed ptype: proof type if needProof==true If the child node is to be proved, then the index is a non-negative number and must not be greater than 15, which is used to indicate that the value of the corresponding index of ChildHashs is the target value to be prooved.

type NodeHeader 

type NodeHeader struct {
	NT           NodeType  `json:"nodetype"`
	KeyString    KeyPart   `json:"keystring"`
	ChildrenFlag ChildFlag `json:"childrenflag"`
}

NodeHeader is used to describe the node serialize value

  1. 1st byte for NodeType
  2. if node has prefix, then put compressed prefix byte slice after NodeType. (first nibble is in NodeType if the length of prefix is odd)
  3. if node has children node(s), then use 2 bytes to indicate which index of children array has node. byte[0].bit[0-7] <-> node.children[0-7], byte[1].bit[0-7] <-> node.children[8-15]

func (NodeHeader) Clone 

func (h NodeHeader) Clone() NodeHeader

func (*NodeHeader) Deserialization 

func (h *NodeHeader) Deserialization(r io.Reader) (shouldBeNil bool, err error)

func (NodeHeader) Equal added in v1.3.26 

func (h NodeHeader) Equal(o NodeHeader) bool

func (NodeHeader) HasChild 

func (h NodeHeader) HasChild(index int) bool

func (NodeHeader) HasChildren 

func (h NodeHeader) HasChildren() bool

func (*NodeHeader) HashValue 

func (h *NodeHeader) HashValue() ([]byte, error)

func (*NodeHeader) KeyHexString 

func (h *NodeHeader) KeyHexString() []byte

func (*NodeHeader) KeyToPrefix 

func (h *NodeHeader) KeyToPrefix() []byte

func (*NodeHeader) Serialization 

func (h *NodeHeader) Serialization(w io.Writer) error

func (NodeHeader) String 

func (h NodeHeader) String() string

type NodeIterator 

type NodeIterator interface {
	// Next returns next node, return nil if there's no more nodez
	Next() *node
	// Current returns last Next() returned node
	Current() *node
}

type NodeProof 

type NodeProof struct {
	PType       ProofType            `json:"type"`   // Limit the content that this node can prove, which is used to judge in proving step.
	Header      NodeHeader           `json:"header"` // Description of the current node, including: whether there is prefix, what is prefix, which child node has data, and whether there is value
	ValueHash   *common.Hash         `json:"value"`  // Hash of the value, or special prefix when proving a BlockHeader field
	ChildProofs *common.MerkleProofs `json:"merkle"` // The proofs of merkle tree of the child nodes' hashs. It does not participate in proof when it's nil.

}
  1. To prove the existence of ValueHash on leaf nodes, such as the existence of TX and SPV. Or:
  2. To prove the non-existence of a key according to the provided Header, and you need to match the key from top to bottom.
  3. When PType is ProofHeaderXXXXXXXX, to proof the corresponding field in BlockHeader: In this case, ValueHash is the special prefix of different fields, and the hash value of the field sequence number can be used to prove that this field is being proved, and ChildProofs is the proof to BlockHeader.Hash

func NewBranchNodeProof 

func NewBranchNodeProof(childIndex uint8, header NodeHeader, childProofs *common.MerkleProofs) *NodeProof

only the case of value on leaf node is supported, that is, the length of all keys is the same

func NewHdsSummaryProof 

func NewHdsSummaryProof(summary *common.Hash, proofs *common.MerkleProofs) *NodeProof

func NewHeaderPropertyProof 

func NewHeaderPropertyProof(ptype ProofType, indexHash *common.Hash, proofs *common.MerkleProofs) *NodeProof

func NewLeafNodeProof 

func NewLeafNodeProof(header NodeHeader) *NodeProof

func NewMerkleOnlyProof 

func NewMerkleOnlyProof(ptype ProofType, proofs *common.MerkleProofs) *NodeProof

func NewNodeProof 

func NewNodeProof(ptype ProofType, header NodeHeader, valueHash *common.Hash, childProofs *common.MerkleProofs) *NodeProof

func (*NodeProof) Clone 

func (n *NodeProof) Clone() *NodeProof

func (*NodeProof) Equal added in v1.3.26 

func (n *NodeProof) Equal(o *NodeProof) bool

func (*NodeProof) ExistenceHash 

func (n *NodeProof) ExistenceHash() ([]byte, error)

func (*NodeProof) ExistenceMatch 

func (n *NodeProof) ExistenceMatch(keyprefix []byte) (matched bool, valueHash *common.Hash, suffix []byte, err error)

Compare the nibbles in keyprefix with the prefix of the current node and the index of the child array to determine whether the value pointed to by the keyprefix is in the current node or its descendant node matched: true means that the target is in the current node or its desendant node valueHash: When matched = = true and exactly matches the current node, hash of value is 

returned. Otherwise, return nil

suffix: Return the remaining part of keyprefix after matching, which is used to continue 

calling this method on the child node

err: If the data is incomplete or incorrect, err will return a non nil value, and other 

return values are invalid
In this case，matched==true&&valueHash!=nil，means the target value is found,
             matched==true&&valueHash==nil，means the current node is matched and the
                                            next level needs to be matched

func (*NodeProof) InfoString added in v1.3.19 

func (n *NodeProof) InfoString(level common.IndentLevel) string

func (*NodeProof) IsHdsSummaryOf 

func (n *NodeProof) IsHdsSummaryOf(chainId common.ChainID, height common.Height) bool

func (*NodeProof) IsHeaderOf 

func (n *NodeProof) IsHeaderOf(chainId common.ChainID, height common.Height) bool

func (*NodeProof) Iterate added in v1.3.24 

func (n *NodeProof) Iterate(hashCallback func(val []byte, order bool) error) error

iterate all hash values in the current NodeProof

func (*NodeProof) Proof 

func (n *NodeProof) Proof(toBeProof common.Hash) ([]byte, error)

Calculate the proof value of a value or child node represented by toBeProof by passing through current proofing node If PType.IsProofChild(): Hash(Hash(Hash(Header), ValueHash), ChildProofs.Proof(toBeProof)) If PType.IsProofValue(): 

if ChildProofs.Len() > 1 : error
if ChildProofs.Len() == 1 : Hash(Hash(Hash(Header), toBeProof), ChildProofs.Hashs[0])
if ChildProofs.Len() == 0 : Hash(Hash(Header), toBeProof)

If PType.IsProofMerkleOnly(): ChildProofs.Proof(toBeProof) If PType.IsProofHeaderProperty(): ChildProofs.Proof(Hash(ValueHash, toBeProof)), in this case, 

ValueHash is the hash value of the sequence number of the
corresponding field

If PType.IsProofHdsSummary(): ChildProofs.Proof(Hash(ValueHash, toBeProof)), in this case, 

ValueHash is the hash of the chain+Height corresponding to the
summary

func (*NodeProof) String 

func (n *NodeProof) String() string

type NodeSelector 

type NodeSelector func(*Trie, *node) bool

The selector of the current node, when it returns true, will cause the depth traversal program to return the current node to the caller Since there is a lock when calling this method, please note that the external lock will be affected, resulting in deadlock

type NodeType 

type NodeType byte

NodeType is a byte which used to describe the node type bit[7]: 1 if prefix is not nil bit[6]: 1 if children array is not empty bit[5]: 1 if value is not nil bit[4]: when bit[7]=1, 1 if prefix length is odd, 0 if prefix length is even bit[3-0]: when bit[4]=1, first byte of prefix, otherwise=0x0

func (NodeType) FirstPrefix 

func (t NodeType) FirstPrefix() byte

func (NodeType) HasChildren 

func (t NodeType) HasChildren() bool

func (NodeType) HasPrefix 

func (t NodeType) HasPrefix() bool

func (NodeType) HasValue 

func (t NodeType) HasValue() bool

func (NodeType) PrefixOddLength 

func (t NodeType) PrefixOddLength() bool

func (NodeType) String 

func (t NodeType) String() string

type NodeValueDecode 

type NodeValueDecode func(r io.Reader) (o interface{}, err error)

NodeValueDecode decode the byte stream load from io.Reader into an object and return it

type NodeValueEncode 

type NodeValueEncode func(o interface{}, w io.Writer) error

NodeValueEncode encode the first parameter and write the result into io.Writer

type NodeValueExpander 

type NodeValueExpander func(hashBytes []byte, adapter db.DataAdapter) (valueBytes []byte, err error)

NodeValueExpander expands node value

type NodeValueHasher 

type NodeValueHasher func(value interface{}, valueBytes []byte) (hashBytes []byte, err error)

NodeValueHasher hashes the input parameter and return the hashed value returnd value length must equals common.HashLength

type Proof 

type Proof struct {
	ToBeProof *common.Hash // hash value of the object to be proved
	Proofs    ProofChain   // Proof chain, each proof node includes proof type and proof value
}

evidence for something

func (Proof) Exist 

func (p Proof) Exist(keyprefix []byte) (*common.Hash, error)

func (Proof) Proof 

func (p Proof) Proof() ([]byte, error)

type ProofChain 

type ProofChain []*NodeProof

in the order of the proof tree from bottom to top

func (ProofChain) BigKey added in v1.3.19 

func (c ProofChain) BigKey() *big.Int

func (ProofChain) Clone 

func (c ProofChain) Clone() ProofChain

func (ProofChain) Equal added in v1.3.26 

func (c ProofChain) Equal(o ProofChain) bool

func (ProofChain) Exist 

func (c ProofChain) Exist(keyprefix []byte) (*common.Hash, error)

Whether the value pointed by keyprefix (the nibbles of the key, can be converted back to the binary array of the key through prefixtokey) exists non-nil: exist, return hash of the value, nil：not exist If the data is incomplete or incorrect, err will return a non nil value, the return value of *common.Hash is invalid

func (ProofChain) ExistenceHash 

func (c ProofChain) ExistenceHash() (rootHash []byte, err error)

When the current proof chain is proofing existence, this method returns the root hash of the trie that generates the proof chain

func (ProofChain) HistoryProof added in v1.3.26 

func (c ProofChain) HistoryProof(height common.Height, hob []byte) ([]byte, error)

func (ProofChain) InfoString added in v1.3.19 

func (c ProofChain) InfoString(level common.IndentLevel) string

func (ProofChain) IsExist 

func (c ProofChain) IsExist(key []byte) (bool, error)

whether the value indicated by the key exists in the trie that generates the proofchain

func (ProofChain) Iterate added in v1.3.24 

func (c ProofChain) Iterate(hashCallback func(val []byte, order bool) error) error

func (ProofChain) Key 

func (c ProofChain) Key() (uint64, bool)

func (ProofChain) Proof 

func (c ProofChain) Proof(toBeProof common.Hash) ([]byte, error)

Calculate the hash value from toBeProof through the whole proof chain

func (ProofChain) ToMerkles added in v1.3.24 

func (c ProofChain) ToMerkles() (*common.MerkleProofs, error)

type ProofType 

type ProofType uint8

0-15: to proof a child node 16: to proof node value 254: to proof existence 255: merkle trie proof 

const (
	// 0x00 ~ 0x0F The index of the child node for the node to proof
	ProofValue      ProofType = 0x10 // To prove the value of the current node, valueHash should be nil
	ProofHdsSummary ProofType = 0x11 // Prove each summary in the packaged Hds, HdsRoot=Merkle{[]Hash{Hash(ChainID(4bytes)+Height(8bytes)), Header.Hash}}
	ProofExistence  ProofType = 0xFE // To prove whether the value of a key exists
	ProofMerkleOnly ProofType = 0xFF // Hash only child nodes without Header and Value. Used to support simple

	ProofHeaderDeltas    ProofType = 0x20 // To proof header balance delta (deltas generated in local chain)
	ProofHeaderHistory   ProofType = 0x21 // To proof header history hash
	ProofHeaderStateRoot ProofType = 0x23 // To proof header state root
	ProofHeaderVCCRoot   ProofType = 0x24 // To proof header VCC root
	ProofHeaderCCCRoot   ProofType = 0x25 // To proof header Cashed root
	ProofHeaderHdsRoot   ProofType = 0x26 // To proof header Headers root

	ProofHeaderBase  ProofType = 0x30 // proof header type = ProofHeaderBase + models.BH* (Header column index)
	ProofHeaderLimit           = ProofHeaderBase + 33
)

func (ProofType) IsProofChild 

func (p ProofType) IsProofChild() bool

func (ProofType) IsProofExistence 

func (p ProofType) IsProofExistence() bool

func (ProofType) IsProofHdsSummary 

func (p ProofType) IsProofHdsSummary() bool

func (ProofType) IsProofHeaderProperty 

func (p ProofType) IsProofHeaderProperty() (headerIndex int, ok bool)

func (ProofType) IsProofMerkleOnly 

func (p ProofType) IsProofMerkleOnly() bool

func (ProofType) IsProofValue 

func (p ProofType) IsProofValue() bool

func (ProofType) String 

func (p ProofType) String() string

type Revertable 

type Revertable interface {
	ITrie
	LiveValueIterator() ValueIterator
	PreHashValue() ([]byte, error)
	PreCommit() ([]byte, error)
	Rollback()
}

type RevertableTrie 

type RevertableTrie struct {
	Origin *Trie // committed value
	Live   *Trie // not committed value
	// contains filtered or unexported fields
}

func (*RevertableTrie) CheckPoint 

func (r *RevertableTrie) CheckPoint() (chkpt int, root []byte, err error)

persiste the current live and return: chkpt: sequence number of current checkpoint root: live root hash when creating checkpoint err: when it is not nil, chkpt and root are not available

func (*RevertableTrie) Commit 

func (r *RevertableTrie) Commit() error

func (*RevertableTrie) Copy 

func (r *RevertableTrie) Copy() *RevertableTrie

func (*RevertableTrie) Delete 

func (r *RevertableTrie) Delete(key []byte) (changed bool, oldValue interface{})

func (*RevertableTrie) Get 

func (r *RevertableTrie) Get(key []byte) (value interface{}, ok bool)

func (*RevertableTrie) GetExistenceProof 

func (r *RevertableTrie) GetExistenceProof(key []byte) (exist bool, proofs ProofChain, err error)

func (*RevertableTrie) GetLive 

func (r *RevertableTrie) GetLive(key []byte) (value interface{}, ok bool)

func (*RevertableTrie) GetProof 

func (r *RevertableTrie) GetProof(key []byte) (value interface{}, proof ProofChain, ok bool)

func (*RevertableTrie) HashValue 

func (r *RevertableTrie) HashValue() (hashValue []byte, err error)

func (*RevertableTrie) IsDirty 

func (r *RevertableTrie) IsDirty() bool

func (*RevertableTrie) LiveValueIterator 

func (r *RevertableTrie) LiveValueIterator() ValueIterator

func (*RevertableTrie) PreCommit 

func (r *RevertableTrie) PreCommit() ([]byte, error)

func (*RevertableTrie) PreHashValue 

func (r *RevertableTrie) PreHashValue() ([]byte, error)

func (*RevertableTrie) Put 

func (r *RevertableTrie) Put(key []byte, value interface{}) bool

func (*RevertableTrie) PutValue 

func (r *RevertableTrie) PutValue(value TrieValue) bool

func (*RevertableTrie) Rebase added in v1.3.14 

func (r *RevertableTrie) Rebase(dbase db.Database) (*RevertableTrie, error)

func (*RevertableTrie) RevertTo 

func (r *RevertableTrie) RevertTo(checkPoint int, root []byte) error

Roll back live to the specified checkpoint and return possible errors It can succeed only when the value of checkpoint matches the value of root hash with that in the record. Otherwise, the failure reason is returned

func (*RevertableTrie) Rollback 

func (r *RevertableTrie) Rollback()

func (*RevertableTrie) SetTo 

func (r *RevertableTrie) SetTo(newTrie *Trie) error

func (*RevertableTrie) ValueIterator 

func (r *RevertableTrie) ValueIterator() ValueIterator

type SmallCombinedTrie 

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

Trie with ITrie as value

func NewCombinedTrie 

func NewCombinedTrie(adapter db.DataAdapter) *SmallCombinedTrie

func (*SmallCombinedTrie) Commit 

func (c *SmallCombinedTrie) Commit() error

func (*SmallCombinedTrie) Delete 

func (c *SmallCombinedTrie) Delete(key []byte) (changed bool, oldValue interface{})

func (*SmallCombinedTrie) Get 

func (c *SmallCombinedTrie) Get(key []byte) (interface{}, bool)

func (*SmallCombinedTrie) GetExistenceProof 

func (c *SmallCombinedTrie) GetExistenceProof(key []byte) (exist bool, proofs ProofChain, err error)

func (*SmallCombinedTrie) GetProof 

func (c *SmallCombinedTrie) GetProof(key []byte) (value interface{}, proof ProofChain, ok bool)

func (c *SmallCombinedTrie) GetProof(key []byte) (value interface{}, proof common.ProofHash, ok bool) {

func (*SmallCombinedTrie) HashValue 

func (c *SmallCombinedTrie) HashValue() (hashValue []byte, err error)

func (*SmallCombinedTrie) InitTrie 

func (c *SmallCombinedTrie) InitTrie(rootHash []byte, nadapter db.DataAdapter, vadapter db.DataAdapter,
	encode NodeValueEncode, decode NodeValueDecode, hasher NodeValueHasher, expander NodeValueExpander) error

func (*SmallCombinedTrie) IsDirty 

func (c *SmallCombinedTrie) IsDirty() bool

func (*SmallCombinedTrie) Keys 

func (c *SmallCombinedTrie) Keys() []string

func (*SmallCombinedTrie) Marshal 

func (c *SmallCombinedTrie) Marshal(w io.Writer) error

func (*SmallCombinedTrie) Put 

func (c *SmallCombinedTrie) Put(key []byte, value interface{}) bool

func (*SmallCombinedTrie) PutValue 

func (c *SmallCombinedTrie) PutValue(value TrieValue) bool

func (*SmallCombinedTrie) ValueIterator 

func (c *SmallCombinedTrie) ValueIterator() ValueIterator

type SyncTrie 

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

func NewSyncTrie 

func NewSyncTrie(t ITrie) *SyncTrie

func (*SyncTrie) Commit 

func (s *SyncTrie) Commit() error

func (*SyncTrie) Delete 

func (s *SyncTrie) Delete(key []byte) (changed bool, oldValue interface{})

func (*SyncTrie) Get 

func (s *SyncTrie) Get(key []byte) (value interface{}, ok bool)

func (*SyncTrie) GetExistenceProof 

func (s *SyncTrie) GetExistenceProof(key []byte) (exist bool, proofs ProofChain, err error)

func (*SyncTrie) GetProof 

func (s *SyncTrie) GetProof(key []byte) (value interface{}, proof ProofChain, ok bool)

func (*SyncTrie) HashValue 

func (s *SyncTrie) HashValue() (hashValue []byte, err error)

func (*SyncTrie) IsDirty 

func (s *SyncTrie) IsDirty() bool

func (*SyncTrie) Put 

func (s *SyncTrie) Put(key []byte, value interface{}) bool

func (*SyncTrie) PutValue 

func (s *SyncTrie) PutValue(value TrieValue) bool

func (*SyncTrie) ValueIterator 

func (s *SyncTrie) ValueIterator() ValueIterator

type TreeNode 

type TreeNode struct {
	Branchs  map[string][]byte         // key (binary prefix code string) - > hash of lower level
	Children [childrenLength]*TreeNode // current node is a non-leaf node: the index corresponds to the child node, not used with Leafs in the same time
	Leafs    [childrenLength][]byte    // current node is a leaf node: hash value of leaf node, index is the last nibble of the key in binary tree, not used with Children in the same time
	// contains filtered or unexported fields
}

In order to be able to serialize and deserialize, there can be no undetermined type (interface{}, or interfaces), so it cannot be made into an infinite level tree.

Each treenode is a 4-level complete binary tree composed of up to 16 child nodes.

In branchs, use "" as the key to store the root hash of the current node, and "0" to store the root hash of all binary subtrees prefixed with 0. Similarly, "1", "00", "01", "10", "11", "000", "001", "010", "011", "100", "101", "110" and "111" are the root hash of subtrees prefixed with themselves

Leafs stores the hash values of all leaf nodes

func NewNodeByProof 

func NewNodeByProof(adapter db.DataAdapter, index int, value []byte, child *TreeNode,
	proof *common.MerkleProofs) (rn *TreeNode, err error)

When value is a legal hash value, a new leaf node is generated. Otherwise, when the child is not nil, a new non leaf node is generated.

func NewTreeNode 

func NewTreeNode() *TreeNode

func (*TreeNode) AppendChild 

func (n *TreeNode) AppendChild(index int, child *TreeNode) error

func (*TreeNode) Collapse 

func (n *TreeNode) Collapse(adapter db.DataAdapter) error

func (*TreeNode) Deserialization 

func (n *TreeNode) Deserialization(r io.Reader) (shouldBeNil bool, err error)

func (*TreeNode) Expand 

func (n *TreeNode) Expand(adapter db.DataAdapter) error

func (*TreeNode) HashAtPrefix 

func (n *TreeNode) HashAtPrefix(prefix []byte) (hashAtPrefix []byte, leftIsNil bool, rightIsNil bool, err error)

Computes the root hash of the subtree indicated by the specified prefix If there are no nodes under the subtree, return nil If a node is missing in any step, NilHash is used instead leftIsNil, rightIsNil returns whether the left and right children are nil values when calculating the current node hash, and if err is not nil, the two values are meaningless.

func (*TreeNode) HashValue 

func (n *TreeNode) HashValue() ([]byte, error)

func (*TreeNode) IsLeaf 

func (n *TreeNode) IsLeaf() bool

func (*TreeNode) LeafHash 

func (n *TreeNode) LeafHash(index int) (leafHash []byte, err error)

func (TreeNode) MakeFullString 

func (n TreeNode) MakeFullString(recursive bool) string

func (*TreeNode) MakeProof 

func (n *TreeNode) MakeProof(index int) (rootHash []byte, toBeProof []byte, proof *common.MerkleProofs, err error)

generate merkle proof by specified index rootHash: root hash of current node toBeProof: hash of prooved position (specified by index) proof: merkle proof

func (*TreeNode) MergeProof 

func (n *TreeNode) MergeProof(adapter db.DataAdapter, index int, value []byte, child *TreeNode,
	proof *common.MerkleProofs) error

func (TreeNode) NoneRecursiveString 

func (n TreeNode) NoneRecursiveString() string

func (*TreeNode) PutChild 

func (n *TreeNode) PutChild(index int, child *TreeNode) error

It is only used when generating incomplete nodes, such as recovery of proof

func (*TreeNode) PutValue 

func (n *TreeNode) PutValue(adapter db.DataAdapter, prefix []byte, hashs []byte) error

func (*TreeNode) Reset 

func (n *TreeNode) Reset()

func (*TreeNode) RightmostChild 

func (n *TreeNode) RightmostChild(checkPrecedingNil bool) (index int, child *TreeNode)

func (*TreeNode) RightmostLeaf 

func (n *TreeNode) RightmostLeaf(checkPrecedingNil bool) (index int, leaf []byte)

func (*TreeNode) Serialization 

func (n *TreeNode) Serialization(w io.Writer) error

func (TreeNode) String 

func (n TreeNode) String() string

type Trie 

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

func NewTrie 

func NewTrie(hash []byte, nadapter db.DataAdapter, vadapter db.DataAdapter, valueType reflect.Type,
	hasher NodeValueHasher, expander NodeValueExpander) *Trie

func NewTrieWithValueCodec 

func NewTrieWithValueCodec(hash []byte, nadapter db.DataAdapter, vadapter db.DataAdapter,
	encode NodeValueEncode, decode NodeValueDecode) *Trie

func NewTrieWithValueFuncs 

func NewTrieWithValueFuncs(hash []byte, nadapter db.DataAdapter, vadapter db.DataAdapter,
	encode NodeValueEncode, decode NodeValueDecode, hasher NodeValueHasher, expander NodeValueExpander) *Trie

func NewTrieWithValueType 

func NewTrieWithValueType(hash []byte, nadapter db.DataAdapter, vadapter db.DataAdapter, valueType reflect.Type) *Trie

func (*Trie) Clone 

func (t *Trie) Clone() *Trie

func (*Trie) Collapse 

func (t *Trie) Collapse() error

func (*Trie) Commit 

func (t *Trie) Commit() error

func (*Trie) Count 

func (t *Trie) Count() int

func (*Trie) Delete 

func (t *Trie) Delete(key []byte) (changed bool, oldValue interface{})

func (*Trie) Get 

func (t *Trie) Get(key []byte) (interface{}, bool)

func (*Trie) GetExistenceProof 

func (t *Trie) GetExistenceProof(key []byte) (exist bool, proofs ProofChain, err error)

func (*Trie) GetProof 

func (t *Trie) GetProof(key []byte) (val interface{}, proof ProofChain, ok bool)

func (*Trie) HashValue 

func (t *Trie) HashValue() ([]byte, error)

func (*Trie) Inherit 

func (t *Trie) Inherit(root []byte) *Trie

func (*Trie) IsDirty 

func (t *Trie) IsDirty() bool

func (*Trie) IsEmpty 

func (t *Trie) IsEmpty() bool

func (*Trie) IterateAll 

func (t *Trie) IterateAll(noNil bool, callback func(key []byte, value interface{}) (shouldContinue bool))

func (*Trie) Marshal 

func (t *Trie) Marshal(w io.Writer) error

func (*Trie) PrintValues added in v1.3.6 

func (t *Trie) PrintValues() string

func (*Trie) Put 

func (t *Trie) Put(key []byte, value interface{}) bool

func (*Trie) PutValue 

func (t *Trie) PutValue(value TrieValue) bool

func (*Trie) Rebase added in v1.3.14 

func (t *Trie) Rebase(dbase db.Database) (*Trie, error)

func (*Trie) String 

func (t *Trie) String() string

func (*Trie) SubTrie 

func (t *Trie) SubTrie(keyPrefix []byte) *Trie

func (*Trie) UnmarshalNewTrie 

func (t *Trie) UnmarshalNewTrie(r io.Reader, valueType reflect.Type, keyFunc func(interface{}) []byte) (*Trie, error)

func (*Trie) ValueIterator 

func (t *Trie) ValueIterator() ValueIterator

func (*Trie) ValueString 

func (t *Trie) ValueString() string

type TrieValue 

type TrieValue interface {
	Key() []byte
}

type ValueIterator 

type ValueIterator interface {
	Next() bool
	Current() (key []byte, value interface{})
}

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.