tree

package
v1.0.17 Latest Latest
Warning

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

 Go to latest Published: Jul 29, 2026 License: MIT Imports: 7 Imported by: 0

Documentation

Overview

Package tree implements an observed-remove rooted tree CRDT.

Index

Constants

This section is empty.

Variables

View Source 
var (
	ErrInvalidReplicaID = errors.New("tree: invalid replica ID")
	ErrNilTree          = errors.New("tree: nil OR-Tree")
	ErrUnknownParent    = errors.New("tree: unknown live parent")
	ErrUnknownNode      = errors.New("tree: unknown live node")
	ErrInvalidDelta     = errors.New("tree: invalid delta")
	ErrIncompleteState  = errors.New("tree: incomplete OR-Tree state")
	ErrNodeConflict     = errors.New("tree: conflicting node identity")
	ErrResourceLimit    = errors.New("tree: OR-Tree resource limit exceeded")
	ErrUnsafeCompaction = errors.New("tree: unsafe OR-Tree tombstone compaction")
)

Functions

This section is empty.

Types

type Delta 

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

func UnmarshalDelta 

func UnmarshalDelta(data []byte) (Delta, error)

func UnmarshalDeltaWithLimits 

func UnmarshalDeltaWithLimits(data []byte, limits frame.DecoderLimits) (Delta, error)

func (Delta) MarshalBinary 

func (d Delta) MarshalBinary() ([]byte, error)

func (Delta) MarshalJSON added in v1.0.5 

func (d Delta) MarshalJSON() ([]byte, error)

MarshalJSON returns a diagnostic summary for structured logs. It omits node values, identities, tombstone identities, and clock state.

func (Delta) Merge 

func (d Delta) Merge(other Delta) (Delta, error)

type Node 

type Node struct {
	ID     NodeID
	Parent NodeID
	Value  []byte
}

Node is an immutable visible tree node. Value is always caller-owned.

type NodeID 

type NodeID = crdt.Tag

NodeID is an immutable node-instance identity. The zero ID is the synthetic root.

type ORTree 

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

ORTree supports add and observed-remove. Moving a node is deliberately not an in-place operation: remove it and add a new instance under the new parent.

func New 

func New(replicaID string) (*ORTree, error)

func NewFromClock 

func NewFromClock(state clock.State) (*ORTree, error)

func NewFromClockWithOptions added in v1.0.10 

func NewFromClockWithOptions(state clock.State, options Options) (*ORTree, error)

NewFromClockWithOptions restores an OR-Tree clock with explicit retained-state limits. Persist the clock atomically with a complete state before reusing its replica ID.

func NewFromSnapshot 

func NewFromSnapshot(saved snapshot.Snapshot) (*ORTree, error)

func NewFromSnapshotWithOptions added in v1.0.10 

func NewFromSnapshotWithOptions(saved snapshot.Snapshot, options Options) (*ORTree, error)

NewFromSnapshotWithOptions restores an OR-Tree snapshot while retaining the application's local resource limits. A snapshot is not allowed to widen the receiver's memory budget.

func NewWithOptions added in v1.0.10 

func NewWithOptions(replicaID string, options Options) (*ORTree, error)

NewWithOptions constructs an OR-Tree with explicit retained-state limits.

func (*ORTree) Add 

func (t *ORTree) Add(parent NodeID, value []byte) (NodeID, Delta, error)

func (*ORTree) ApplyDelta 

func (t *ORTree) ApplyDelta(delta Delta) error

func (*ORTree) ClockState 

func (t *ORTree) ClockState() clock.State

func (*ORTree) CompactTombstones added in v1.0.10 

func (t *ORTree) CompactTombstones(tags []NodeID) (int, error)

CompactTombstones removes exactly the requested tombstoned leaf nodes. Call it only after the current membership epoch has durably recorded exact acknowledgements, a post-compaction checkpoint, and retirement of old deltas. Any known child makes a deleted node a structural anchor, so the operation is all-or-nothing for that request.

func (*ORTree) MarshalBinary 

func (t *ORTree) MarshalBinary() ([]byte, error)

MarshalBinary returns a deterministic, bounded framed OR-Tree state.

func (*ORTree) MarshalBinaryWithClockState 

func (t *ORTree) MarshalBinaryWithClockState() ([]byte, clock.State, error)

func (*ORTree) MarshalJSON added in v1.0.5 

func (t *ORTree) MarshalJSON() ([]byte, error)

MarshalJSON returns a diagnostic summary for structured logs. It omits node values, identities, tombstone identities, and clock state.

func (*ORTree) Merge 

func (t *ORTree) Merge(other *ORTree) error

func (*ORTree) Nodes 

func (t *ORTree) Nodes() []Node

Nodes returns visible, root-reachable nodes in canonical preorder.

func (*ORTree) Remove 

func (t *ORTree) Remove(id NodeID) (Delta, error)

func (*ORTree) SnapshotCurrentState 

func (t *ORTree) SnapshotCurrentState() (snapshot.Snapshot, error)

func (*ORTree) State 

func (t *ORTree) State() crdt.StateSnapshot

func (*ORTree) TombstoneTags added in v1.0.10 

func (t *ORTree) TombstoneTags() []NodeID

TombstoneTags returns every retained deletion tag in canonical order. It is an exact-acknowledgement input, not proof that a tombstone is safe to compact.

func (*ORTree) UnmarshalBinary 

func (t *ORTree) UnmarshalBinary(data []byte) error

UnmarshalBinary validates the full state before atomically replacing t. Complete states additionally require every non-root parent to be present.

func (*ORTree) UnmarshalBinaryWithLimits 

func (t *ORTree) UnmarshalBinaryWithLimits(data []byte, limits frame.DecoderLimits) error

type Options added in v1.0.10 

type Options struct {
	MaxNodes      int
	MaxTombstones int
	MaxValueBytes int
}

Options bounds retained OR-Tree state. Applications handling untrusted peers should set limits for the replication group rather than rely on process-wide memory availability.

func DefaultOptions added in v1.0.10 

func DefaultOptions() Options

DefaultOptions returns conservative retention limits that align with one default frame's element and value limits.

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.