Documentation ¶
Index ¶
- Constants
- type BTree
- type Binary
- type BinaryNode
- type Content
- type FreeList
- type Int
- type Item
- type ItemIterator
- type MaxIntHeap
- type MerkleTree
- func (m *MerkleTree) GetMerklePath(content Content) ([][]byte, []int64, error)
- func (m *MerkleTree) MerkleRoot() []byte
- func (m *MerkleTree) RebuildTree() error
- func (m *MerkleTree) RebuildTreeWith(cs []Content) error
- func (m *MerkleTree) String() string
- func (m *MerkleTree) VerifyContent(content Content) (bool, error)
- func (m *MerkleTree) VerifyTree() (bool, error)
- type Node
Constants ¶
const (
DefaultFreeListSize = 32
)
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type BTree ¶
type BTree struct {
// contains filtered or unexported fields
}
/
func NewWithFreeList ¶
NewWithFreeList creates a new B-Tree that uses the given node free list.
func (*BTree) AscendGreaterOrEqual ¶
func (t *BTree) AscendGreaterOrEqual(pivot Item, iterator ItemIterator)
func (*BTree) Delete ¶
Delete removes an item equal to the passed in item from the tree, returning it. If no such item exists, returns nil.
func (*BTree) ReplaceOrInsert ¶
type Binary ¶
type Binary[T comparable] struct { // contains filtered or unexported fields }
func NewBinary ¶
func NewBinary[T comparable](preList []T, midList []T) *Binary[T]
func (*Binary[T]) Root ¶
func (b *Binary[T]) Root() *BinaryNode[T]
type BinaryNode ¶
type BinaryNode[T comparable] struct { Data T Left *BinaryNode[T] Right *BinaryNode[T] }
type Content ¶
Content represents the data that is stored and verified by the tree. A type that implements this interface can be used as an item in the tree.
type FreeList ¶
type FreeList struct {
// contains filtered or unexported fields
}
func NewFreeList ¶
type ItemIterator ¶
type MaxIntHeap ¶
数组实现最大堆
func NewIntHeap ¶
func NewIntHeap(cap int) *MaxIntHeap
func (*MaxIntHeap) Pop ¶
func (heap *MaxIntHeap) Pop() int
func (*MaxIntHeap) Push ¶
func (heap *MaxIntHeap) Push(value int)
type MerkleTree ¶
MerkleTree is the container for the tree. It holds a pointer to the root of the tree, a list of pointers to the leaf nodes, and the merkle root.
func NewTree ¶
func NewTree(cs []Content) (*MerkleTree, error)
NewTree creates a new Merkle Tree using the content cs.
func NewTreeWithHashStrategy ¶
func NewTreeWithHashStrategy(cs []Content, hashStrategy func() hash.Hash) (*MerkleTree, error)
NewTreeWithHashStrategy creates a new Merkle Tree using the content cs using the provided hash strategy. Note that the hash type used in the type that implements the Content interface must match the hash type provided to the tree.
func NewTreeWithHashStrategySorted ¶
func NewTreeWithHashStrategySorted(cs []Content, hashStrategy func() hash.Hash, sort bool) (*MerkleTree, error)
NewTreeWithHashStrategySorted just like NewTreeWithHashStrategy but sorts the siblings before hashing, mostly to follow the OpenZepplin Merkle implementation https://github.com/OpenZeppelin/openzeppelin-contracts-ethereum-package/blob/master/contracts/cryptography/MerkleProof.sol
func (*MerkleTree) GetMerklePath ¶
func (m *MerkleTree) GetMerklePath(content Content) ([][]byte, []int64, error)
GetMerklePath: Get Merkle path and indexes(left leaf or right leaf)
func (*MerkleTree) MerkleRoot ¶
func (m *MerkleTree) MerkleRoot() []byte
MerkleRoot returns the unverified Merkle Root (hash of the root node) of the tree.
func (*MerkleTree) RebuildTree ¶
func (m *MerkleTree) RebuildTree() error
RebuildTree is a helper function that will rebuild the tree reusing only the content that it holds in the leaves.
func (*MerkleTree) RebuildTreeWith ¶
func (m *MerkleTree) RebuildTreeWith(cs []Content) error
RebuildTreeWith replaces the content of the tree and does a complete rebuild; while the root of the tree will be replaced the MerkleTree completely survives this operation. Returns an error if the list of content cs contains no entries.
func (*MerkleTree) String ¶
func (m *MerkleTree) String() string
String returns a string representation of the tree. Only leaf nodes are included in the output.
func (*MerkleTree) VerifyContent ¶
func (m *MerkleTree) VerifyContent(content Content) (bool, error)
VerifyContent indicates whether a given content is in the tree and the hashes are valid for that content. Returns true if the expected Merkle Root is equivalent to the Merkle root calculated on the critical path for a given content. Returns true if valid and false otherwise.
func (*MerkleTree) VerifyTree ¶
func (m *MerkleTree) VerifyTree() (bool, error)
VerifyTree verify tree validates the hashes at each level of the tree and returns true if the resulting hash at the root of the tree matches the resulting root hash; returns false otherwise.
type Node ¶
type Node struct { Tree *MerkleTree Parent *Node Left *Node Right *Node Hash []byte C Content // contains filtered or unexported fields }
Node represents a node, root, or leaf in the tree. It stores pointers to its immediate relationships, a hash, the content stored if it is a leaf, and other metadata.