node

package
v0.2201.9 Latest Latest
Warning

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

 Go to latest Published: Jul 26, 2022 License: Apache-2.0 Imports: 11 Imported by: 4

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.

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.