tries

package
v0.0.2 Latest Latest
Warning

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

 Go to latest Published: Dec 15, 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

This section is empty.

Types

type Entry 

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

Entry represents a key-value pair in the trie. See-also: IndexEntry for entries that refer to other nodes. and VNodeEntry for entries that contain other nodes inline.

type Index 

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

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 (mach *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 (mach *Machine) Delete(ctx context.Context, s bcsdk.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) (bool, error)

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

func (*Machine) MinEntry 

func (mach *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.RW) (*Root, error)

func (*Machine) NewIterator 

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

func (*Machine) NewTx 

func (mach *Machine) NewTx(s bcsdk.RWD, prevRoot Root) *Tx

NewTx creates a new transaction based on an existing Trie

func (*Machine) NewTxOnEmpty 

func (mach *Machine) NewTxOnEmpty(s bcsdk.RWD) *Tx

NewTxOnEmpty creates a new Tx based on an empty Trie.

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.RW, ents []Entry) (*Root, error)

PostSlice returns a new instance containing ents

func (*Machine) Put 

func (mach *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 Root) error

func (*Machine) Walk 

func (mach *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 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

func (*Root) Unmarshal added in v0.0.2 

func (x *Root) Unmarshal(data []byte) error

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) (*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, key []byte, dst *[]byte) (bool, error)

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

func (*Tx) Put 

func (tx *Tx) Put(ctx context.Context, 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 VNodeEntry added in v0.0.2 

type VNodeEntry struct {
	Prefix []byte
	Node   triescnp.Node
}

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.