tries

package
v0.0.1 Latest Latest
Warning

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

 Go to latest Published: Nov 25, 2025 License: GPL-3.0 Imports: 19 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

View Source 
var (
	ErrCannotCollapse = errors.Errorf("cannot collapse parent into child")
	ErrCannotSplit    = errors.Errorf("cannot split, < 2 entries")
)

Functions

func IsErrNotFound 

func IsErrNotFound(err error) bool

Types

type Entry 

type Entry struct {
	Key   []byte
	Value []byte
}

Entry represents a key-value pair in the trie

func (*Entry) Marshal 

func (e *Entry) Marshal() ([]byte, error)

func (*Entry) Unmarshal 

func (e *Entry) Unmarshal(data []byte) error

type ErrNotFound 

type ErrNotFound = state.ErrNotFound[[]byte]

ErrNotFound is returned when a key cannot be found.

type Index 

type Index struct {
	// Ref is the reference to the node.
	Ref Ref
	// Prefix is the common prefix of all the entries in the referenced node.
	Prefix []byte
	// Count is the cumulative number of entries transitively reachable from this node.
	Count uint64
	// IsParent is true if the node at Ref is a parent node.
	IsParent bool
}

Index represents metadata about a trie node reference

func (*Index) FromEntry 

func (idx *Index) FromEntry(ent Entry) error

func (*Index) Marshal 

func (idx *Index) Marshal(out []byte) []byte

Marshal serializes an Index using Cap'n Proto

func (*Index) ToEntry 

func (idx *Index) ToEntry() *Entry

func (*Index) Unmarshal 

func (idx *Index) Unmarshal(data []byte) error

UnmarshalIndex deserializes an Index using Cap'n Proto

type Iterator 

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

func (*Iterator) Next 

func (it *Iterator) Next(ctx context.Context, dst *Entry) error

type Machine 

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

Machine holds caches and configuration for operating on tries.

func NewMachine 

func NewMachine(salt *blobcache.CID, hf blobcache.HashFunc) *Machine

func (*Machine) BatchEdit 

func (o *Machine) BatchEdit(ctx context.Context, s schema.RW, root Root, opsSeq iter.Seq[Op]) (*Root, error)

BatchEdit applies a batch of operations to a root, returning a new root. All ops produced by opsSeq will be collected and sorted.

func (*Machine) Delete 

func (o *Machine) Delete(ctx context.Context, s schema.RWD, root Root, key []byte) (*Root, error)

Delete removes

func (*Machine) Get 

func (o *Machine) Get(ctx context.Context, s schema.RO, root Root, key []byte, dst *[]byte) error

Get retrieves a value at key if it exists, otherwise ErrNotFound is returned

func (*Machine) MinEntry 

func (o *Machine) MinEntry(ctx context.Context, s schema.RO, root Root, gteq []byte) (*Entry, error)

MinEntry returns the first entry >= gteq

func (*Machine) NewEmpty 

func (o *Machine) NewEmpty(ctx context.Context, s schema.WO) (*Root, error)

func (*Machine) NewIterator 

func (o *Machine) NewIterator(s schema.RO, root Root, span Span) *Iterator

func (*Machine) NewTx 

func (m *Machine) NewTx(prevRoot Root) *Tx

func (*Machine) NewTxOnEmpty 

func (m *Machine) NewTxOnEmpty(ctx context.Context, s schema.WO) (*Tx, error)

func (*Machine) Populate 

func (o *Machine) Populate(ctx context.Context, s schema.RO, root Root, set cadata.Set, fn func(*Entry) error) error

func (*Machine) PostSlice 

func (o *Machine) PostSlice(ctx context.Context, s schema.WO, ents []*Entry) (*Root, error)

PostSlice returns a new instance containing ents

func (*Machine) Put 

func (o *Machine) Put(ctx context.Context, s schema.RW, root Root, key, value []byte) (*Root, error)

Put returns a copy of root where key maps to value, and all other mappings are unchanged.

func (*Machine) Sync 

func (o *Machine) Sync(ctx context.Context, dst schema.WO, src schema.RO, root Root, fn func(*Entry) error) error

Sync ensures that data structure exists in dst, using src to retrieve missing pieces. Sync is only correct if dangling references can be guarenteed to not exist in dst.

func (*Machine) Validate 

func (o *Machine) Validate(ctx context.Context, s schema.RO, x Index) error

func (*Machine) Walk 

func (o *Machine) Walk(ctx context.Context, s schema.RO, root Root, w Walker) error

Walk walks a Trie calling methods on Walker throughout the traversal. w.ShouldWalk is called before walking a node, if false is returned the node is skipped w.EntryFn is called for every entry in a node w.NodeFn is called for the node after all the entries reachable from it have been walked.

type Node 

type Node struct {
	Entries []*Entry
}

Node represents a trie node containing multiple entries

func (*Node) Marshal 

func (n *Node) Marshal() ([]byte, error)

Marshal serializes a Node using Cap'n Proto

func (*Node) Unmarshal 

func (n *Node) Unmarshal(data []byte) error

UnmarshalNode deserializes a Node using Cap'n Proto

type Op 

type Op struct {
	Key   []byte
	Value []byte
}

Op is a single operation on the trie.

func OpDelete 

func OpDelete(key []byte) Op

func OpPut 

func OpPut(key []byte, value []byte) Op

func (Op) Entry 

func (op Op) Entry() *Entry

Entry returns the entry that the op would create. Nil is returned if the op is a delete.

func (Op) IsDelete 

func (op Op) IsDelete() bool

type Ref 

type Ref struct {
	CID    cadata.ID    `json:"cid"`
	DEK    bccrypto.DEK `json:"dek"`
	Length uint32       `json:"len"`
}

type Root 

type Root Index

func ParseRoot 

func ParseRoot(x []byte) (*Root, error)

func (*Root) Marshal 

func (x *Root) Marshal(out []byte) []byte

type Span 

type Span = state.ByteSpan

type Tx 

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

Tx is a transaction on a trie data structure. Tx buffers operations, and presents a logical view of the trie. Tx is not thread-safe.

func (*Tx) Delete 

func (tx *Tx) Delete(ctx context.Context, key []byte) error

func (*Tx) Flush 

func (tx *Tx) Flush(ctx context.Context, s schema.RW) (*Root, error)

Flush applies the edits to the previous root, and returns the new root. The transaction can continue, after this.

func (*Tx) Get 

func (tx *Tx) Get(ctx context.Context, s schema.RO, key []byte, dst *[]byte) error

Get retrieves a key from the store, and writes the value to dst.

func (*Tx) Put 

func (tx *Tx) Put(ctx context.Context, s schema.RW, key []byte, value []byte) error

Put creates or replace the entry for key, such that it points to value.

func (*Tx) Queued 

func (tx *Tx) Queued() int

type Walker 

type Walker struct {
	// ShouldWalk is called immediately before traversing a node.
	// ShouldWalk must be set; always return true to naively walk everything.
	ShouldWalk func(root Root) bool
	// EntryFn, if set, is called for every entry.
	EntryFn func(*Entry) error
	// NodeFn, must be set and is called after visiting every node.
	NodeFn func(root Root) error
}

Source Files

View all Source files

Directories

Path Synopsis

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.