tree

package module
v1.3.3 Latest Latest
Warning

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

 Go to latest Published: Sep 23, 2025 License: ISC Imports: 11 Imported by: 0

README

tree

CI Go Reference Go Report Card

-- import "vimagination.zapto.org/tree"

Package tree implements a tree serialiser and reader. Usable as a tree-based, WORM, key-value store.

Highlights

  • Serialise trees using built-in data types Branch and Leaf, or any implementation of the two method Node interface.
  • Can read trees from files, with OpenFile, from a bytes-slice with OpenMemAt, or from any io.ReaderAt, with OpenAt.
  • Can store data on any node, be it a branch or a leaf node.

Usage

package main

import (
	"bytes"
	"fmt"

	"vimagination.zapto.org/tree"
)

func main() {
	var (
		buf, readBuf bytes.Buffer
		root         tree.Branch
		branch       tree.Branch
	)

	root.Add("child1", tree.Leaf([]byte("Hello")))
	root.Add("child2", tree.Leaf([]byte("World")))
	root.Add("branch1", &branch)

	branch.Add("childA", tree.Leaf([]byte("Foo")))
	branch.Add("childB", tree.Leaf([]byte("Bar")))

	tree.Serialise(&buf, root)

	t := tree.OpenAt(bytes.NewReader(buf.Bytes()), int64(buf.Len()))

	child1, _ := t.Child("child1")

	child1.WriteTo(&readBuf)

	fmt.Printf("child 1 data: %q\n", readBuf.Bytes())

	readBuf.Reset()

	branch1, _ := t.Child("branch1")
	childB, _ := branch1.Child("childB")

	childB.WriteTo(&readBuf)

	fmt.Printf("child B data: %q\n", readBuf.Bytes())

	// Output:
	// child 1 data: "Hello"
	// child B data: "Bar"
}

Binary Format

Node Data
Names Section
├─ Name0: Name of Child0 node (bytes)
├─ Name1: Name of Child1 node (bytes)
└─ …
Pointers Section
├─ Pointer0: int64 offset to end of Child0 node (varint)
├─ Pointer1: int64 offset to end of Child1 node (varint)
└─ …
NameSizes Section
├─ Size of Name0 << 3 & Size of Ptr0 (varint)
├─ Size of Name1 << 3 & Size of Ptr1 (varint)
└─ …
Data Section
└─ Bytes of the data stored on this node
Sizes Section
├─ Size of NameSizes section (varint); only if > 0
└─ Size of Data section (varint); only if > 0
Size Flags (uint8)
├─ Bits 0-5: Size of the Sizes section in bytes
├─ Bit 6: 1 when there size of data > 0; 0 otherwise
└─ Bit 7: 1 when there are children; 0 otherwise

NB: Pointers to leaf nodes with no data will be 0.

Documentation

Full API docs can be found at:

https://pkg.go.dev/vimagination.zapto.org/tree

Documentation

Overview

Package tree implements a tree serialiser and reader.

Example 
package main

import (
	"bytes"
	"fmt"

	"vimagination.zapto.org/tree"
)

func main() {
	var (
		buf, readBuf bytes.Buffer
		root         tree.Branch
		branch       tree.Branch
	)

	root.Add("child1", tree.Leaf([]byte("Hello")))
	root.Add("child2", tree.Leaf([]byte("World")))
	root.Add("branch1", &branch)

	branch.Add("childA", tree.Leaf([]byte("Foo")))
	branch.Add("childB", tree.Leaf([]byte("Bar")))

	tree.Serialise(&buf, root)

	t := tree.OpenAt(bytes.NewReader(buf.Bytes()), int64(buf.Len()))

	child1, _ := t.Child("child1")

	child1.WriteTo(&readBuf)

	fmt.Printf("child 1 data: %q\n", readBuf.Bytes())

	readBuf.Reset()

	branch1, _ := t.Child("branch1")
	childB, _ := branch1.Child("childB")

	childB.WriteTo(&readBuf)

	fmt.Printf("child B data: %q\n", readBuf.Bytes())

}

Output:

child 1 data: "Hello"
child B data: "Bar"

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

func Serialise 

func Serialise(w io.Writer, root Node) error

Serialise writes a tree structure to the given writer.

The byte-format for each node is as follows: 

Names     []string (stored in lexical order)
Pointers  []int64  (pointer to the end (&Size + 1) of each child node record, stored as variable-length integers; length of pointer stored in NameSizes)
NameSizes []uint64 (lengths of each name and pointer, stored as variable-length integers; bottom three bits are the length of the pointer - 1, remaining bits are name length)
Data      []byte
Sizes     []uint64 (size of NamesSizes and Data sections, stored as variable-length integers; zeros are omitted)
Size      uint8  (lower 5 bits: size of the Sizes field, bit 6: size Data > 0, bit 7: size NameSizes > 0)

NB: All slices are stored without separators.

If the given Writer implements the io.Seeker interface it will be used to determine the current writer position, and offset all pointer accordingly.

The OffsetWriter type can be used to wrap an io.Writer to provide a custom offset, or to have Serialise ignore the underlying Writers position.

Types

type Branch added in v1.2.0 

type Branch []nameNode

Branch is a collection of named Nodes.

func (*Branch) Add added in v1.2.0 

func (b *Branch) Add(name string, node Node) error

Add adds a named Node to the branch.

No locking takes place, so all children should be added before using the Branch Node.

func (Branch) Child added in v1.2.0 

func (b Branch) Child(name string) (Node, error)

Child attempts to retrieve a child Node corresponding to the given name.

If no child matches the given name, the returned error will be of type ChildNotFoundError.

func (Branch) Children added in v1.2.0 

func (b Branch) Children() iter.Seq2[string, Node]

Children returns an iterator that loops through all of the child Nodes.

func (Branch) Data added in v1.2.0 

func (Branch) Data() []byte

Data returns the Nodes data.

func (Branch) DataLen added in v1.2.0 

func (Branch) DataLen() int64

DataLen will always return 0 for a Branch Node.

func (Branch) NumChildren added in v1.2.0 

func (b Branch) NumChildren() int

NumChildren returns the number of child Nodes that are attached to this Node.

func (Branch) WriteTo added in v1.2.0 

func (Branch) WriteTo(_ io.Writer) (int64, error)

WriteTo always returns 0, nil for a Branch Node.

type ChildNotFoundError 

type ChildNotFoundError string

ChildNotFoundError contains the name of the child that could not be found.

func (ChildNotFoundError) Error 

func (c ChildNotFoundError) Error() string

Error implements the error interface.

type ChildrenError 

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

ChildrenError is a Node and error type that is returned from the Children iterator.

It has no children and any attempt to retrieve the data will result in the underlying error to be returned.

func NewChildrenError added in v1.1.0 

func NewChildrenError(err error) ChildrenError

NewChildrenError wraps an error to give it the methods of a Node.

func (ChildrenError) Children 

func (ChildrenError) Children() iter.Seq2[string, Node]

Children always returns an empty iterator.

func (ChildrenError) Unwrap added in v1.0.1 

func (c ChildrenError) Unwrap() error

Unwrap returns the wrapped error.

func (ChildrenError) WriteTo 

func (c ChildrenError) WriteTo(_ io.Writer) (int64, error)

WriteTo always returns the underlying error.

type DuplicateChildError 

type DuplicateChildError []string

DuplicateChildError is an error that records the duplicated child name.

func (DuplicateChildError) Error 

func (d DuplicateChildError) Error() string

Error implements the error interface.

type Leaf added in v1.2.0 

type Leaf []byte

Leaf represents a childless Node that contains only data.

The Leaf itself is a byte-slice.

func (Leaf) Child added in v1.2.0 

func (Leaf) Child(name string) (Node, error)

Child will always return nil with a ChildNotFoundError error for a Leaf Node.

func (Leaf) Children added in v1.2.0 

func (Leaf) Children() iter.Seq2[string, Node]

Children will return an empty iterator for Leaf Nodes.

func (Leaf) Data added in v1.2.0 

func (l Leaf) Data() []byte

Data returns the Nodes data.

func (Leaf) DataLen added in v1.2.0 

func (l Leaf) DataLen() int64

DataLen returns the length of the data stored on this Node.

func (Leaf) NumChildren added in v1.2.0 

func (Leaf) NumChildren() int

NumChildren will always return 0 for a Leaf Node.

func (Leaf) WriteTo added in v1.2.0 

func (l Leaf) WriteTo(w io.Writer) (int64, error)

WriteTo will pass the Nodes data to the given io.Writer as a single byte-slice.

type MemTree 

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

MemTree represents a tree backed by an in-memory byte slice.

func OpenMem 

func OpenMem(data []byte) (*MemTree, error)

OpenMem opens a Tree from the given byte slice.

func OpenMemAt 

func OpenMemAt(data []byte, pos int64) (*MemTree, error)

OpenMemAt opens a Tree from the given byte slice, using the given Node pointer instead of using the length of the data.

func (*MemTree) Child 

func (m *MemTree) Child(name string) (*MemTree, error)

Child attempts to retrieve a child Node corresponding to the given name.

If no child matches the given name, the returned error will be of type ChildNotFoundError.

func (*MemTree) ChildNames added in v1.3.0 

func (m *MemTree) ChildNames() iter.Seq[string]

ChildNames returns an iterator that loops through the names of the child Nodes.

func (*MemTree) Children 

func (m *MemTree) Children() iter.Seq2[string, Node]

Children returns an iterator that loops through all of the child Nodes.

Read errors will be expressed with a final Node of underlying type ChildrenError.

func (*MemTree) Data 

func (m *MemTree) Data() []byte

Data returns the Nodes data.

func (*MemTree) DataLen added in v1.1.0 

func (m *MemTree) DataLen() int64

DataLen returns the length of the data stored on this Node.

func (*MemTree) NumChildren added in v1.1.0 

func (m *MemTree) NumChildren() int

NumChildren returns the number of child Nodes that are attached to this Node.

func (*MemTree) WriteTo 

func (m *MemTree) WriteTo(w io.Writer) (int64, error)

WriteTo will pass the Nodes data to the given io.Writer as a single byte-slice.

type Node 

type Node interface {
	// Children returns an iterator that yields a (unique) name and Node for each
	// of the child nodes.
	//
	// Yielding the children in a lexically sorted order is recommended,
	// but not required.
	//
	// If an error occurs, the Node may be of type ChildrenError, which in
	// addition to being a Node also implements the error interface.
	Children() iter.Seq2[string, Node]

	// WriterTo accepts an io.Writer to which any data stored on the node will be
	// passed.
	io.WriterTo
}

Node represents a single node in a Tree.

type OffsetReaderAt added in v1.3.1 

type OffsetReaderAt struct {
	io.ReaderAt
	Offset int64
}

OffsetReaderAt is a wrapper around the io.ReaderAt interface that will shift the read position by the set Offset.

func (*OffsetReaderAt) ReadAt added in v1.3.1 

func (o *OffsetReaderAt) ReadAt(p []byte, offset int64) (int, error)

ReadAt implements the io.ReaderAt interface, but shifts the offset by adding OffsetReaderAt.Offset.

type OffsetWriter added in v1.3.1 

type OffsetWriter struct {
	io.Writer
	Offset int64
}

OffsetWriter is a wrapper around io.Writer that provides an io.Seeker interface that can be used by Serialise to offset the pointers in the tree.

func (OffsetWriter) Seek added in v1.3.1 

func (o OffsetWriter) Seek(_ int64, _ int) (int64, error)

Seek implements the io.Seeker interface, but always returns OffsetWriter.Offset, nil.

type Roots added in v1.2.0 

type Roots []multiNode

func Merge added in v1.2.0 

func Merge(nodes ...Node) (Roots, error)

Merge combines the children from multiple nodes, merging same named children similarly.

Changes made to the Nodes after merging will not be recognised.

func (Roots) Child added in v1.2.0 

func (r Roots) Child(name string) (Node, error)

Child attempts to retrieve a child Node corresponding to the given name.

If no child matches the given name, the returned error will be of type ChildNotFoundError.

func (Roots) Children added in v1.2.0 

func (r Roots) Children() iter.Seq2[string, Node]

Children returns an iterator that loops through all of the child Nodes.

Any errors will be expressed with a final Node of underlying type ChildrenError.

func (Roots) Data added in v1.2.0 

func (Roots) Data() []byte

Data will always return nil for a Roots Node.

func (Roots) DataLen added in v1.2.0 

func (Roots) DataLen() int64

DataLen will always return 0 for a Roots Node.

func (Roots) NumChildren added in v1.2.0 

func (r Roots) NumChildren() int

NumChildren returns the number of child Nodes that are attached to this Node.

func (Roots) WriteTo added in v1.2.0 

func (Roots) WriteTo(_ io.Writer) (int64, error)

WriteTo always return 0, nil for a Roots Node.

type Tree 

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

Tree represents a Node of a tree backed by an io.ReaderAt.

func OpenAt 

func OpenAt(r io.ReaderAt, pos int64) *Tree

OpenAt opens a Tree from the given io.ReaderAt.

The pos should be the length of the data underlying the io.ReaderAt, or a specific Node pointer address within the data.

func (*Tree) Child 

func (t *Tree) Child(name string) (*Tree, error)

Child attempts to retrieve a child Node corresponding to the given name.

If no child matches the given name, the returned error will be of type ChildNotFoundError.

func (*Tree) Children 

func (t *Tree) Children() iter.Seq2[string, Node]

Children returns an iterator that loops through all of the child Nodes.

Read errors will be expressed with a final Node of underlying type ChildrenError.

func (*Tree) DataLen added in v1.1.0 

func (t *Tree) DataLen() (int64, error)

DataLen returns the length of the data stored on this Node.

func (*Tree) NumChildren added in v1.1.0 

func (t *Tree) NumChildren() (int, error)

NumChildren returns the number of child Nodes that are attached to this Node.

func (*Tree) Reader 

func (t *Tree) Reader() (io.Reader, error)

func (*Tree) WriteTo 

func (t *Tree) WriteTo(w io.Writer) (int64, error)

WriteTo writes the Nodes data to the given writer.

type TreeCloser 

type TreeCloser struct {
	Tree
	io.Closer
}

TreeCloser is a tree that includes a Close method for an opened file.

func OpenFile 

func OpenFile(path string) (*TreeCloser, error)

OpenFile opens a Tree from the given filename.

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.