Documentation
¶
Index ¶
- type DiffEntry
- type NodeStore
- type Tree
- func (t *Tree) Diff(ctx context.Context, root1, root2 string, fn func(DiffEntry) error) error
- func (t *Tree) Edit(root string) *Txn
- func (t *Tree) Lookup(ctx context.Context, root, routingKey, key string) (string, error)
- func (t *Tree) LookupByKey(ctx context.Context, root, key string) (string, error)
- func (t *Tree) NodeRefs(ctx context.Context, root string, fn func(ref string) error) error
- func (t *Tree) Walk(ctx context.Context, root string, fn func(key, value string) error) error
- type Txn
- func (tx *Txn) Commit(ctx context.Context) (string, error)
- func (tx *Txn) Delete(ctx context.Context, routingKey, key string) error
- func (tx *Txn) DiffFrom(ctx context.Context, oldRoot string, fn func(DiffEntry) error) error
- func (tx *Txn) Insert(ctx context.Context, routingKey, key, value string) error
- func (tx *Txn) Lookup(ctx context.Context, routingKey, key string) (string, error)
- func (tx *Txn) LookupByKey(ctx context.Context, key string) (string, error)
- func (tx *Txn) Root(ctx context.Context) (string, error)
- func (tx *Txn) Walk(ctx context.Context, fn func(key, value string) error) error
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type DiffEntry ¶
DiffEntry represents a single change between two trees. OldValue is empty for additions; NewValue is empty for deletions.
type NodeStore ¶ added in v1.16.0
type NodeStore struct {
// contains filtered or unexported fields
}
NodeStore is the only part of this package that knows HAMT nodes are bytes. It maps a node ref ("node/<sha256>") to a decoded node and back, owning the key prefix, the canonical encoding, and a read cache.
Nodes are content-addressed, so a ref's decoded form never changes and the cache needs no invalidation. For the same reason Load hands out a shared pointer: a loaded node is clean, and clean nodes are immutable (see child).
func NewNodeStore ¶ added in v1.16.0
func NewNodeStore(s store.ObjectStore) *NodeStore
NewNodeStore returns a NodeStore reading and writing through s.
type Tree ¶
type Tree struct {
// contains filtered or unexported fields
}
Tree reads persistent Hash Array Mapped Tries.
A HAMT here is a map from (routing key, key) to an opaque string value. The routing key is a hex string chosen by the caller; its first 32 bits decide the path through the trie, so callers wanting locality between related keys give them a shared prefix. The key identifies the entry within its leaf. The value is opaque — callers store object refs there, but the tree never interprets them.
Tree itself holds no tree state: every read names the root it applies to, so one Tree serves any number of snapshots and shares a single node cache between them. Mutation happens in a Txn, obtained from Edit.
func NewTree ¶
func NewTree(s store.ObjectStore) *Tree
NewTree creates a Tree backed by the given object store.
func NewTreeWithNodes ¶ added in v1.16.0
NewTreeWithNodes creates a Tree over an existing NodeStore, so several trees can share one read cache.
func (*Tree) Diff ¶
Diff structurally compares two persisted trees and calls fn for every entry added, removed, or modified between root1 and root2.
func (*Tree) Edit ¶ added in v1.16.0
Edit opens a transaction over the tree rooted at root. Pass an empty root to build a new tree.
func (*Tree) Lookup ¶
Lookup returns the value associated with key in the tree rooted at root, or ("", nil) if not found. routingKey must be the key the entry was inserted under.
func (*Tree) LookupByKey ¶ added in v1.16.0
LookupByKey finds a value by walking the entire tree and matching on the raw key. This is O(N) and slower than Lookup, but does not require the entry's routing key. Use only when the routing key cannot be reconstructed.
type Txn ¶ added in v1.16.0
type Txn struct {
// contains filtered or unexported fields
}
Txn is a mutable working copy of a tree.
Insert and Delete rewrite nodes in memory and write nothing; the resulting tree is a mixture of clean children, still shared with the tree it was opened from, and dirty ones that exist only here. Commit is the only write path: it serializes the dirty spine bottom-up and returns the new root ref. Nodes that were superseded during the transaction were never serialized in the first place, so there is nothing to garbage-collect afterwards.
A Txn is not safe for concurrent use.
func (*Txn) Commit ¶ added in v1.16.0
Commit writes every node that is actually part of the final tree and returns the new root ref. Superseded intermediate nodes were never serialized, so "dirty" and "reachable" are the same set and no reachability pass is needed.
After Commit the transaction is clean and can be committed again cheaply; a second Commit writes nothing and returns the same ref.
func (*Txn) Delete ¶ added in v1.16.0
Delete removes the entry for key. Deleting a key that is not present, or deleting from an empty tree, is a no-op.
func (*Txn) DiffFrom ¶ added in v1.16.0
DiffFrom compares a persisted tree against the working tree, reporting what this transaction would change. It writes nothing, so callers can report a would-be result without committing.
func (*Txn) Insert ¶ added in v1.16.0
Insert adds or updates the entry for key. routingKey decides the entry's path through the trie; key is stored as the leaf key.
func (*Txn) Lookup ¶ added in v1.16.0
Lookup returns the value for key in the working tree, including changes made in this transaction that have not been committed.
func (*Txn) LookupByKey ¶ added in v1.16.0
LookupByKey is Tree.LookupByKey over the working tree.
Source Files