node

package
v0.2102.7 Latest Latest
Warning

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

Go to latest
Published: Jul 7, 2021 License: Apache-2.0 Imports: 11 Imported by: 3

Documentation

Overview

Package node defines MKVS tree nodes.

Index

Constants

View Source
const (
	// Prefix used in hash computations of leaf nodes.
	PrefixLeafNode byte = 0x00
	// Prefix used in hash computations of internal nodes.
	PrefixInternalNode byte = 0x01
	// Prefix used to mark a nil pointer in a subtree serialization.
	PrefixNilNode byte = 0x02

	// PointerSize is the size of a node pointer in memory.
	PointerSize = uint64(unsafe.Sizeof(Pointer{}))
	// InternalNodeSize is the minimum size of an internal node in memory.
	InternalNodeSize = uint64(unsafe.Sizeof(InternalNode{}))
	// LeafNodeSize is the minimum size of a leaf node in memory.
	LeafNodeSize = uint64(unsafe.Sizeof(LeafNode{}))

	// ValueLengthSize is the size of the encoded value length.
	ValueLengthSize = int(unsafe.Sizeof(uint32(0)))
)
View Source
const DepthSize = int(unsafe.Sizeof(Depth(0)))

DepthSize is the size of Depth in bytes.

Variables

View Source
var (
	// ErrMalformedNode is the error when a malformed node is encountered
	// during deserialization.
	ErrMalformedNode = errors.New("mkvs: malformed node")
	// ErrMalformedKey is the error when a malformed key is encountered
	// during deserialization.
	ErrMalformedKey = errors.New("mkvs: malformed key")
)

Functions

func ToMapKey

func ToMapKey(k []byte) string

ToMapKey returns the key in a form to be used as a Go's map key.

Types

type Depth

type Depth uint16

Depth determines the maximum length of the key in bits.

maxKeyLengthInBits = 2^size_of(Depth)*8

func (Depth) MarshalBinary

func (dt Depth) MarshalBinary() []byte

MarshalBinary encodes a Depth into binary form.

func (Depth) ToBytes

func (dt Depth) ToBytes() int

ToBytes returns the number of bytes needed to fit given bits.

func (*Depth) UnmarshalBinary

func (dt *Depth) UnmarshalBinary(data []byte) (int, error)

UnmarshalBinary decodes a binary marshaled depth.

type InternalNode

type InternalNode struct {
	Hash hash.Hash
	// Label is the label on the incoming edge.
	Label Key
	// LabelBitLength is the length of the label in bits.
	LabelBitLength Depth
	Clean          bool
	// LeafNode is for the key ending at this depth.
	LeafNode *Pointer
	Left     *Pointer
	Right    *Pointer
}

InternalNode is an internal node with two children and possibly a leaf.

Note that Label and LabelBitLength can only be empty iff the internal node is the root of the tree.

func (*InternalNode) CompactMarshalBinary

func (n *InternalNode) CompactMarshalBinary() (data []byte, err error)

CompactMarshalBinary encodes an internal node into binary form without any hash pointers (e.g., for proofs).

func (*InternalNode) Equal

func (n *InternalNode) Equal(other Node) bool

Equal compares a node with some other node.

func (*InternalNode) Extract

func (n *InternalNode) Extract() Node

Extract makes a copy of the node containing only hash references.

For LeafNode, it makes a deep copy so that the parent internal node always ships it since we cannot address the LeafNode uniquely with NodeID (both the internal node and LeafNode have the same path and bit depth).

func (*InternalNode) ExtractUnchecked

func (n *InternalNode) ExtractUnchecked() Node

Extract makes a copy of the node containing only hash references without checking the dirty flag.

For LeafNode, it makes a deep copy so that the parent internal node always ships it since we cannot address the LeafNode uniquely with NodeID (both the internal node and LeafNode have the same path and bit depth).

func (*InternalNode) GetHash

func (n *InternalNode) GetHash() hash.Hash

GetHash returns the node's cached hash.

func (*InternalNode) IsClean

func (n *InternalNode) IsClean() bool

IsClean returns true if the node is non-dirty.

func (*InternalNode) MarshalBinary

func (n *InternalNode) MarshalBinary() (data []byte, err error)

MarshalBinary encodes an internal node into binary form.

func (*InternalNode) Size

func (n *InternalNode) Size() uint64

Size returns the size of this internal node in bytes.

func (*InternalNode) SizedUnmarshalBinary

func (n *InternalNode) SizedUnmarshalBinary(data []byte) (int, error)

SizedUnmarshalBinary decodes a binary marshaled internal node.

func (*InternalNode) UnmarshalBinary

func (n *InternalNode) UnmarshalBinary(data []byte) error

UnmarshalBinary decodes a binary marshaled internal node.

func (*InternalNode) UpdateHash

func (n *InternalNode) UpdateHash()

UpdateHash updates the node's cached hash by recomputing it.

Does not mark the node as clean.

type Key

type Key []byte

Key holds variable-length key.

func (Key) AppendBit

func (k Key) AppendBit(keyLen Depth, val bool) Key

AppendBit appends the given bit to the key.

This function is immutable and returns a new instance of Key.

func (Key) BitLength

func (k Key) BitLength() Depth

BitLength returns the length of the key in bits.

func (Key) CommonPrefixLen

func (k Key) CommonPrefixLen(keyBitLen Depth, k2 Key, k2bitLen Depth) (bitLength Depth)

CommonPrefix computes length of common prefix of k and k2.

Additionally, keyBitLen and k2bitLen are key lengths in bits of k and k2 respectively.

func (Key) Compare

func (k Key) Compare(other Key) int

Compare compares the key with some other key and returns 0 if both keys are equal, -1 if the the key is smaller and 1 if the key is larger.

func (Key) Equal

func (k Key) Equal(other Key) bool

Equal compares the key with some other key.

func (Key) GetBit

func (k Key) GetBit(bit Depth) bool

GetKeyBit returns the given bit of the key.

func (Key) MarshalBinary

func (k Key) MarshalBinary() (data []byte, err error)

MarshalBinary encodes a key length in bytes + key into binary form.

func (Key) Merge

func (k Key) Merge(keyLen Depth, k2 Key, k2Len Depth) Key

Merge bit-wise merges key of given length with another key of given length.

keyLen is the length of the original key in bits and k2Len is the length of another key in bits. This function is immutable and returns a new instance of Key.

func (Key) SetBit

func (k Key) SetBit(bit Depth, val bool) Key

SetKeyBit sets the bit at the given position bit to value val.

This function is immutable and returns a new instance of Key

func (*Key) SizedUnmarshalBinary

func (k *Key) SizedUnmarshalBinary(data []byte) (int, error)

SizedUnmarshalBinary decodes a binary marshaled key incl. length in bytes.

func (Key) Split

func (k Key) Split(splitPoint, keyLen Depth) (prefix, suffix Key)

Split performs bit-wise split of the key.

keyLen is the length of the key in bits and splitPoint is the index of the first suffix bit. This function is immutable and returns two new instances of Key.

func (Key) String

func (k Key) String() string

String returns a string representation of the key.

func (*Key) UnmarshalBinary

func (k *Key) UnmarshalBinary(data []byte) error

UnmarshalBinary decodes a binary marshaled key including the length in bytes.

type LeafNode

type LeafNode struct {
	Clean bool
	Hash  hash.Hash
	Key   Key
	Value []byte
}

LeafNode is a leaf node containing a key/value pair.

func (*LeafNode) CompactMarshalBinary

func (n *LeafNode) CompactMarshalBinary() (data []byte, err error)

CompactMarshalBinary encodes a leaf node into binary form.

func (*LeafNode) Equal

func (n *LeafNode) Equal(other Node) bool

Equal compares a node with some other node.

func (*LeafNode) Extract

func (n *LeafNode) Extract() Node

Extract makes a copy of the node containing only hash references.

func (*LeafNode) ExtractUnchecked

func (n *LeafNode) ExtractUnchecked() Node

Extract makes a copy of the node containing only hash references without checking the dirty flag.

func (*LeafNode) GetHash

func (n *LeafNode) GetHash() hash.Hash

GetHash returns the node's cached hash.

func (*LeafNode) IsClean

func (n *LeafNode) IsClean() bool

IsClean returns true if the node is non-dirty.

func (*LeafNode) MarshalBinary

func (n *LeafNode) MarshalBinary() ([]byte, error)

MarshalBinary encodes a leaf node into binary form.

func (*LeafNode) Size

func (n *LeafNode) Size() uint64

Size returns the size of this leaf node in bytes.

func (*LeafNode) SizedUnmarshalBinary

func (n *LeafNode) SizedUnmarshalBinary(data []byte) (int, error)

SizedUnmarshalBinary decodes a binary marshaled leaf node.

func (*LeafNode) UnmarshalBinary

func (n *LeafNode) UnmarshalBinary(data []byte) error

UnmarshalBinary decodes a binary marshaled leaf node.

func (*LeafNode) UpdateHash

func (n *LeafNode) UpdateHash()

UpdateHash updates the node's cached hash by recomputing it.

Does not mark the node as clean.

type Node

type Node interface {
	encoding.BinaryMarshaler
	encoding.BinaryUnmarshaler

	// IsClean returns true if the node is non-dirty.
	IsClean() bool

	// CompactMarshalBinary encodes a node into binary form without any hash
	// pointers (e.g., for proofs).
	CompactMarshalBinary() ([]byte, error)

	// GetHash returns the node's cached hash.
	GetHash() hash.Hash

	// UpdateHash updates the node's cached hash by recomputing it.
	//
	// Does not mark the node as clean.
	UpdateHash()

	// Extract makes a copy of the node containing only hash references.
	Extract() Node

	// ExtractUnchecked makes a copy of the node containing only hash
	// references without checking the dirty flag.
	ExtractUnchecked() Node

	// Equal compares a node with another node.
	Equal(other Node) bool

	// Size returns the size of this pointer in bytes.
	Size() uint64
}

Node is either an InternalNode or a LeafNode.

func UnmarshalBinary

func UnmarshalBinary(bytes []byte) (Node, error)

UnmarshalBinary unmarshals a node of arbitrary type.

type Pointer

type Pointer struct {
	Clean bool
	Hash  hash.Hash
	Node  Node
	LRU   *list.Element

	// DBInternal contains NodeDB-specific internal metadata to aid
	// pointer resolution.
	DBInternal interface{}
}

Pointer is a pointer to another node.

func (*Pointer) Equal

func (p *Pointer) Equal(other *Pointer) bool

Equal compares two pointers for equality.

func (*Pointer) Extract

func (p *Pointer) Extract() *Pointer

Extract makes a copy of the pointer containing only hash references.

func (*Pointer) ExtractUnchecked

func (p *Pointer) ExtractUnchecked() *Pointer

Extract makes a copy of the pointer containing only hash references without checking the dirty flag.

func (*Pointer) ExtractWithNode

func (p *Pointer) ExtractWithNode() *Pointer

ExtractWithNode makes a copy of the pointer containing hash references and an extracted copy of the node pointed to.

func (*Pointer) ExtractWithNodeUnchecked

func (p *Pointer) ExtractWithNodeUnchecked() *Pointer

ExtractWithNodeUnchecked makes a copy of the pointer containing hash references and an extracted copy of the node pointed to without checking the dirty flag.

func (*Pointer) GetHash

func (p *Pointer) GetHash() hash.Hash

GetHash returns the pointers's cached hash.

func (*Pointer) IsClean

func (p *Pointer) IsClean() bool

IsClean returns true if the pointer is clean.

func (*Pointer) Size

func (p *Pointer) Size() uint64

Size returns the size of this pointer in bytes.

type Root

type Root struct {
	// Namespace is the namespace under which the root is stored.
	Namespace common.Namespace `json:"ns"`
	// Version is the monotonically increasing version number in which the root is stored.
	Version uint64 `json:"version"`
	// Type is the type of storage this root is used for.
	Type RootType `json:"root_type"`
	// Hash is the merkle root hash.
	Hash hash.Hash `json:"hash"`
}

Root is a storage root.

func (*Root) Empty

func (r *Root) Empty()

Empty sets the storage root to an empty root.

func (*Root) EncodedHash

func (r *Root) EncodedHash() hash.Hash

EncodedHash returns the encoded cryptographic hash of the storage root.

func (*Root) Equal

func (r *Root) Equal(other *Root) bool

Equal compares against another root for equality.

func (*Root) Follows

func (r *Root) Follows(other *Root) bool

Follows checks if another root follows the given root. A root follows another iff the namespace matches and the version is either equal or exactly one higher.

It is the responsibility of the caller to check if the merkle roots follow each other.

func (*Root) IsEmpty

func (r *Root) IsEmpty() bool

IsEmpty checks whether the storage root is empty.

func (Root) String

func (r Root) String() string

String returns the string representation of a storage root.

type RootType added in v0.2100.0

type RootType uint8

RootType is a storage root type.

const (
	// RootTypeInvalid is an invalid/uninitialized root type.
	RootTypeInvalid RootType = 0
	// RootTypeState is the type for state storage roots.
	RootTypeState RootType = 1
	// RootTypeIO is the type for IO storage roots.
	RootTypeIO RootType = 2

	// RootTypeMax is the number of different root types and should be kept at the last one.
	RootTypeMax RootType = 2
)

func (RootType) String added in v0.2100.0

func (r RootType) String() string

String returns the string representation of the storage root type.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL