trie

package
v1.0.0 Latest Latest
Warning

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

 Go to latest Published: Jan 6, 2021 License: Apache-2.0 Imports: 15 Imported by: 4

Documentation

Index

Constants

View Source 
const (
	HistoryTreeDepth = 16 // 树高度: 任意值都经历16个节点（包括根节点）才能到达
	ValueKeyLength   = 4  // 每个节点内的树高为4（经历4个节点到达value）
)

Variables

View Source 
var (
	ErrMismatchProof = errors.New("proof mismatched")
	ErrMissingValue  = errors.New("value missing")
	ErrMissingChild  = errors.New("child missing")
	ErrNotExist      = errors.New("not exist")
)
View Source 
var (
	EmptyNodeHashSlice []byte
	EmptyNodeHash      common.Hash
)

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 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 ProofableMap 

func ProofableMap(typ ProofType) (int, bool)

func ToBinary 

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

将一个byte转为2进制的byte数组，其中每个byte是0x0或0x1

func ToByte 

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

将bs代表的2进制byte数组恢复为一个byte，bs的每个字节是0x0或0x1，最多支持8位2进制

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
}

将一个8字节无符号整数（区块高度）按big-endian（即高位在前）序序列化为8个字节， 然后按每半个字节（nibble）一级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)

按序在最后添加，如果key != expecting，或value为空值，则返回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

将同一rootHash下的证明合并到树中

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
	// 根据key，返回key对应的value对象及其证明链。ok返回是否成功找到对应value并且生成证明
	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

为了增加json序列化方法

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   // Trie节点的NodeHeader
	ValueHash  *common.Hash // 节点Value的Hash，可以为nil
	ChildHashs [][]byte     // 节点所有非nil孩子的Hash值数组，没有孩子时数组为空
}

func (*NodeHasher) MakeProof 

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

needProof: 是否需要证明 ptype: needProof==true时，证明类型 如果要证明的是孩子节点，则index是一个非负数，并且一定不会大于15，用来表示要生成ChildHashs对应下标的值的证明

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) 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"`   // 限定本节点能够证明的内容，在证明到最后一步时用来判断。
	Header      NodeHeader           `json:"header"` // 当前节点的描述，包括：是否有Prefix，prefix是什么，哪个孩子节点有数据，是否有Value
	ValueHash   *common.Hash         `json:"value"`  // 如果Value存在时，value的Hash值，不存在则为nil
	ChildProofs *common.MerkleProofs `json:"merkle"` // 由孩子节点的Hash组成的MerkleTree的证明序列，可以为nil, 为nil时不进行Hash(叶子结点)

}
  1. 可以证明叶子节点上ValueHash的存在性，如Tx和SPV的存在证明。或：
  2. 可以根据提供的Header，证明某个Key的不存在性，需要从上到下匹配Key。
  3. 当PType为ProofHeaderxxxxxxx时，证明BlockHeader中对应的字段: ValueHash为不同字段的特殊前缀，字段序列号的Hash值，可以用来证明当前证明的就是这个字段； ChildProofs为生成BlockHeader.Hash的证明

func NewBranchNodeProof 

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

这里仅支持value在叶子结点上的情况，也就是所有key的长度一样

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

index: 限定本节点能够证明的内容。0-15: 要证明的部分是本节点的孩子节点；16-255: 要证明的部分是本节点的Value

func (*NodeProof) Clone 

func (n *NodeProof) Clone() *NodeProof

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)

将半字节化的keyprefix与当前节点的prefix、孩子数组下标比较，判断所查keyprefix指向的value是否在当前节点或后代节点中 matched: true表示所查在当前节点或后代节点中 valueHash: 当matched==true时，且正好匹配当前节点，则返回value的Hash。否则返回nil suffix: 返回匹配之后的剩余部分，用来对孩子节点继续调用本方法 err: 如果因为数据不全或不对，造成无法判断时，err则会返回非nil值，此时其他返回值无效 当err为nil时，matched==true&&valueHash!=nil，说明找到了对应的value， 

matched==true&&valueHash==nil，说明当前节点匹配，需要继续匹配下一级

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) Proof 

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

计算由toBeProof表示的某Value或子节点存在经过本节点后的hash值 如果 PType.IsProofChild(): Hash(Hash(Hash(Header), ValueHash), ChildProofs.Proof(toBeProof)) 如果 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)

如果 PType.IsProofMerkleOnly(): ChildProofs.Proof(toBeProof) 如果 PType.IsProofHeaderProperty(): ChildProofs.Proof(Hash(ValueHash, toBeProof))，此时ValueHash为对应字段的序列号的Hash值 如果 PType.IsProofHdsSummary(): ChildProofs.Proof(Hash(ValueHash, toBeProof))，此时ValueHash为对应Summary的所在链+高度的Hash

func (*NodeProof) String 

func (n *NodeProof) String() string

type NodeSelector 

type NodeSelector func(*Trie, *node) bool

当前节点的选择器，返回true时会使得深度遍历程序把当前节点返回给调用者 由于调用此方法时有锁，所以请注意出现会影响外部的锁，从而导致死锁

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
	Proofs    ProofChain   // 证明链，每一步都包括证明类型和证明的值
}

证明

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

下标序为证明树从下向上

func (ProofChain) Clone 

func (c ProofChain) Clone() ProofChain

func (ProofChain) Exist 

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

判断keyprefix(已经被nibble化的key，可以通过prefixToKey转回Key的二进制数组)所指向的value是否存在， 非nil：存在，并返回该value的Hash，nil：不存在 如果因为数据不全或不对，造成无法判断时，error则会返回非nil值，此时的*common.Hash返回值无效

func (ProofChain) ExistenceHash 

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

当前证明链是证明存在性时，由此方法获取生成此证明链的Trie的根Hash

func (ProofChain) IsExist 

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

判断key所指的value是否存在于生成ProofChain的Trie上

func (ProofChain) Key 

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

func (ProofChain) Proof 

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

计算从toBeProof开始经过整个证明树后得到的Hash值

type ProofType 

type ProofType uint8

0-15: 要证明某孩子节点 16: 要证明Value 254: 要证明不存在性 255: 只用merkle trie的数据进行证明，此时不知道被证明的 

const (
	// 0x00 ~ 0x0F 为要证明的节点的孩子节点的下标
	ProofValue      ProofType = 0x10 // 要证明当前节点的Value，valueHash应该为nil
	ProofHdsSummary ProofType = 0x11 // 证明打包的Hds中每一个Summary，HdsRoot=Merkle{[]Hash{Hash(ChainID(4bytes)+Height(8bytes)), Header.Hash}}
	ProofExistence  ProofType = 0xFE // 要证明某个key的value是否存在，此时所有需要一个节点的所有hash都包含进来
	ProofMerkleOnly ProofType = 0xFF // 只有孩子节点，Header和Value都不进入Hash。用来支持其他单纯的merkle tree。

	ProofHeaderDeltas    ProofType = 0x20 // 当前节点证明是header balance delta (本链生成的delta)
	ProofHeaderHistory   ProofType = 0x21 // 当前节点证明是header history hash
	ProofHeaderStateRoot ProofType = 0x23 // 当前节点证明是header state root
	ProofHeaderVCCRoot   ProofType = 0x24 // 当前节点证明是header VCC root
	ProofHeaderCCCRoot   ProofType = 0x25 // 当前节点证明是header Cashed root
	ProofHeaderHdsRoot   ProofType = 0x26 // 当前节点证明是header Headers root
)

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() 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 // 已被确认的正式数据
	Live   *Trie // 尚未被确认的临时数据
	// contains filtered or unexported fields
}

func (*RevertableTrie) CheckPoint 

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

将当前的live进行持久化并返回: chkpt: 当前检查点序号 root: 创建检查点时的live根Hash err: 当不为nil时，chkpt/root的值都不可用

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) RevertTo 

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

将live回滚到指定的检查点，返回可能出现的错误 只有checkpoint的值与根Hash的值与记录中匹配才可以成功，否则返回失败原因

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
}

以ITrie为Value的Trie

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(二进制前缀码字符串) -> 下级的Hash
	Children [childrenLength]*TreeNode // 当前节点为非叶子节点时：下标对应的是下级节点。与Leafs互斥
	Leafs    [childrenLength][]byte    // 当前节点为叶子节点时：二叉树叶子节点的Hash值, 下标即为Hash值对应的值。与Children互斥
	// contains filtered or unexported fields
}

为了可以进行序列化和反序列化，不能出现无法确定的类型（interface，或接口），所以无法做成无限层级的树 每一个TreeNode都是一个由最多16个叶子节点组成的4层完全二叉树 Branchs中，以""为key存当前节点的根Hash，"0"存所有二进制以0为前缀的子树的根Hash， 同理 "1" "00" "01" "10" "11" "000" "001" "010" "011" "100" "101" "110" "111"分别为以自身为前缀的子树的根Hash Leafs中保存所有叶子结点的Hash值

func NewNodeByProof 

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

当value为合法Hash值时，则生成新的叶子节点。否则，当child不为nil时，生成新的非叶子节点。

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)

计算指定前缀所指的子树的根Hash 如果子树下没有任何节点，则返回nil 如果在计算任何一步时缺少一个节点，用NilHash补足 leftIsNil, rightIsNil分别返回计算当前节点hash时的左右孩子是否为nil值，err不为nil时，这两个值没有意义

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)

按指定位置生成merkle证明 rootHash: 当前节点根Hash toBeProof: 被证明位置的Hash proof: merkle证明

func (*TreeNode) MergeProof 

func (n *TreeNode) MergeProof(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

仅在生成不完全节点时使用，如恢复证明时

func (*TreeNode) PutValue 

func (n *TreeNode) PutValue(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) Put 

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

func (*Trie) PutValue 

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

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.