mst

Documentation

Index

• func FindMissingNodes(ns NodeStore, hash []byte) [][]byte
• func HashWritable(obj Writable, h crypto.Hash) []byte
• type Base
  • func (b Base) LeadingZeros(obj []byte) uint32
• type Child
  • func NewChild(key Key, value Value, high []byte) Child
  • func (c Child) High() []byte
  • func (c Child) Key() Key
  • func (c Child) Value() Value
• type HashableNode
  • func (n *HashableNode) Write(w io.Writer) error
• type Key
• type KeyReader
• type LocalNodeStore
  • func (ns *LocalNodeStore) Get(k []byte) *Node
  • func (ns *LocalNodeStore) Put(n *Node) (NodeStore, []byte)
  • func (ns *LocalNodeStore) Remove(k []byte) NodeStore
  • func (ns *LocalNodeStore) Size() uint
• type MerkleSearchTree
  • func NewLocalMST(base Base, hash crypto.Hash) *MerkleSearchTree
  • func NewMST(base Base, hash crypto.Hash, store NodeStore) *MerkleSearchTree
  • func NewMSTWithRoot(root []byte, base Base, hash crypto.Hash, store NodeStore) *MerkleSearchTree
  • func (t *MerkleSearchTree) Get(key Key) Value
  • func (t *MerkleSearchTree) Merge(with *MerkleSearchTree) (*MerkleSearchTree, error)
  • func (t *MerkleSearchTree) NodeStore() NodeStore
  • func (t *MerkleSearchTree) NumNodes() uint
  • func (t *MerkleSearchTree) PrintInOrder()
  • func (t *MerkleSearchTree) Put(key Key, val Value) *MerkleSearchTree
  • func (t *MerkleSearchTree) RootHash() []byte
  • func (t *MerkleSearchTree) WithNodeStore(store NodeStore) *MerkleSearchTree
  • func (t *MerkleSearchTree) WithRoot(root []byte) *MerkleSearchTree
• type Node
  • func NewNode(level uint32, low []byte, children []Child) *Node
  • func (n *Node) Children() []Child
  • func (n *Node) Level() uint32
  • func (n *Node) Low() []byte
• type NodeStore
  • func NewLocalNodeStore(hash crypto.Hash) NodeStore
• type UInt32
  • func (f UInt32) Less(than Key) bool
  • func (f UInt32) Merge(with Value) Value
  • func (f UInt32) Write(w io.Writer) error
• type Value
• type ValueReader
• type Writable

Functions

func FindMissingNodes

func FindMissingNodes(ns NodeStore, hash []byte) [][]byte

func HashWritable

func HashWritable(obj Writable, h crypto.Hash) []byte

Types

type Base

type Base uint

const (
	Base2 Base = 1 + iota
	Base4
	Base8
	Base16
	Base32
)

func (Base) LeadingZeros

func (b Base) LeadingZeros(obj []byte) uint32

type Child

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

func NewChild

func NewChild(key Key, value Value, high []byte) Child

func (Child) High

func (c Child) High() []byte

func (Child) Key

func (c Child) Key() Key

func (Child) Value

func (c Child) Value() Value

type HashableNode

type HashableNode Node

Only used for computing the hash for a given node

func (*HashableNode) Write

func (n *HashableNode) Write(w io.Writer) error

type Key

type Key interface {
	Writable
	Less(than Key) bool
}

type KeyReader

type KeyReader interface {
	FromBytes([]byte) (Key, error)
}

type LocalNodeStore

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

func (*LocalNodeStore) Get

func (ns *LocalNodeStore) Get(k []byte) *Node

func (*LocalNodeStore) Put

func (ns *LocalNodeStore) Put(n *Node) (NodeStore, []byte)

func (*LocalNodeStore) Remove

func (ns *LocalNodeStore) Remove(k []byte) NodeStore

func (*LocalNodeStore) Size

func (ns *LocalNodeStore) Size() uint

type MerkleSearchTree

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

func NewLocalMST

func NewLocalMST(base Base, hash crypto.Hash) *MerkleSearchTree

func NewMST

func NewMST(base Base, hash crypto.Hash, store NodeStore) *MerkleSearchTree

func NewMSTWithRoot

func NewMSTWithRoot(root []byte, base Base, hash crypto.Hash, store NodeStore) *MerkleSearchTree

func (*MerkleSearchTree) Get

func (t *MerkleSearchTree) Get(key Key) Value

func (*MerkleSearchTree) Merge

func (t *MerkleSearchTree) Merge(with *MerkleSearchTree) (*MerkleSearchTree, error)

func (*MerkleSearchTree) NodeStore

func (t *MerkleSearchTree) NodeStore() NodeStore

func (*MerkleSearchTree) NumNodes

func (t *MerkleSearchTree) NumNodes() uint

func (*MerkleSearchTree) PrintInOrder

func (t *MerkleSearchTree) PrintInOrder()

func (*MerkleSearchTree) Put

func (t *MerkleSearchTree) Put(key Key, val Value) *MerkleSearchTree

func (*MerkleSearchTree) RootHash

func (t *MerkleSearchTree) RootHash() []byte

func (*MerkleSearchTree) WithNodeStore

func (t *MerkleSearchTree) WithNodeStore(store NodeStore) *MerkleSearchTree

func (*MerkleSearchTree) WithRoot

func (t *MerkleSearchTree) WithRoot(root []byte) *MerkleSearchTree

type Node

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

Node represents a node in a Merkle Search Tree It should always be true that len(children) > 0, i.e. empty nodes should not exist.

func NewNode

func NewNode(level uint32, low []byte, children []Child) *Node

func (*Node) Children

func (n *Node) Children() []Child

func (*Node) Level

func (n *Node) Level() uint32

func (*Node) Low

func (n *Node) Low() []byte

type NodeStore

type NodeStore interface {
	Get([]byte) *Node
	Put(*Node) (NodeStore, []byte)
	Remove([]byte) NodeStore
	Size() uint
}

func NewLocalNodeStore

func NewLocalNodeStore(hash crypto.Hash) NodeStore

type UInt32

type UInt32 uint32

Used mainly for testing

func (UInt32) Less

func (f UInt32) Less(than Key) bool

func (UInt32) Merge

func (f UInt32) Merge(with Value) Value

func (UInt32) Write

func (f UInt32) Write(w io.Writer) error

type Value

type Value interface {
	Writable
	Merge(with Value) Value
}

type ValueReader

type ValueReader interface {
	FromBytes([]byte) (Value, error)
}

type Writable

type Writable interface {
	Write(io.Writer) error
}