hamt

Documentation

Index

• func AffinityKey(parentID, fileID string) string
• type DiffEntry
• type TransactionalStore
  • func NewTransactionalStore(persistent store.ObjectStore) *TransactionalStore
  • func (ts *TransactionalStore) Delete(_ context.Context, key string) error
  • func (ts *TransactionalStore) Exists(ctx context.Context, key string) (bool, error)
  • func (ts *TransactionalStore) Flush(ctx context.Context) error
  • func (ts *TransactionalStore) FlushReachable(rootRef string) error
  • func (ts *TransactionalStore) Get(ctx context.Context, key string) ([]byte, error)
  • func (ts *TransactionalStore) List(ctx context.Context, prefix string) ([]string, error)
  • func (ts *TransactionalStore) Put(_ context.Context, key string, data []byte) error
  • func (ts *TransactionalStore) Size(ctx context.Context, key string) (int64, error)
  • func (ts *TransactionalStore) TotalSize(ctx context.Context) (int64, error)
• type Tree
  • func NewTree(s store.ObjectStore) *Tree
  • func (t *Tree) Delete(root, parentID, fileID string) (string, error)
  • func (t *Tree) Diff(root1, root2 string, fn func(DiffEntry) error) error
  • func (t *Tree) Insert(root, parentID, fileID, value string) (string, error)
  • func (t *Tree) Lookup(root, parentID, fileID string) (string, error)
  • func (t *Tree) LookupByFileID(root, fileID string) (string, error)
  • func (t *Tree) NodeRefs(root string, fn func(ref string) error) error
  • func (t *Tree) Walk(root string, fn func(key, value string) error) error

Functions

func AffinityKey

func AffinityKey(parentID, fileID string) string

AffinityKey produces a locality-preserving HAMT routing key. parentID is the raw source-level parent identifier (e.g. a GDrive folder ID). fileID is the raw source-level file identifier. Files sharing the same parent will share the top routing levels in the trie, reducing metadata rewrites during incremental backups of a single directory.

Types

type DiffEntry

type DiffEntry struct {
	Key      string
	OldValue string
	NewValue string
}

DiffEntry represents a single change between two trees. OldValue is empty for additions; NewValue is empty for deletions.

type TransactionalStore

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

TransactionalStore buffers HAMT node writes in memory and flushes only the reachable subset to the persistent store.

func NewTransactionalStore

func NewTransactionalStore(persistent store.ObjectStore) *TransactionalStore

func (*TransactionalStore) Delete

func (ts *TransactionalStore) Delete(_ context.Context, key string) error

func (*TransactionalStore) Exists

func (ts *TransactionalStore) Exists(ctx context.Context, key string) (bool, error)

func (*TransactionalStore) Flush

func (ts *TransactionalStore) Flush(ctx context.Context) error

func (*TransactionalStore) FlushReachable

func (ts *TransactionalStore) FlushReachable(rootRef string) error

FlushReachable writes only the HAMT nodes reachable from rootRef to the persistent store, ignoring intermediate nodes that were superseded during the transaction.

func (*TransactionalStore) Get

func (ts *TransactionalStore) Get(ctx context.Context, key string) ([]byte, error)

func (*TransactionalStore) List

func (ts *TransactionalStore) List(ctx context.Context, prefix string) ([]string, error)

func (*TransactionalStore) Put

func (ts *TransactionalStore) Put(_ context.Context, key string, data []byte) error

func (*TransactionalStore) Size

func (ts *TransactionalStore) Size(ctx context.Context, key string) (int64, error)

func (*TransactionalStore) TotalSize

func (ts *TransactionalStore) TotalSize(ctx context.Context) (int64, error)

type Tree

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

Tree is a persistent Hash Array Mapped Trie backed by a content-addressed store. Keys and values are opaque strings; values are typically object refs ("filemeta/<hash>").

func NewTree

func NewTree(s store.ObjectStore) *Tree

NewTree creates a Tree backed by the given object store.

func (*Tree) Delete

func (t *Tree) Delete(root, parentID, fileID string) (string, error)

Delete removes the entry for (parentID, fileID), returning a new root ref. If the key is not found the original root is returned unchanged. Deleting from an empty tree is a no-op. parentID is the raw source-level parent identifier ("" for root-level entries).

func (*Tree) Diff

func (t *Tree) Diff(root1, root2 string, fn func(DiffEntry) error) error

Diff structurally compares two trees and calls fn for every entry that was added, removed, or modified between root1 and root2.

func (*Tree) Insert

func (t *Tree) Insert(root, parentID, fileID, value string) (string, error)

Insert adds or updates the entry for (parentID, fileID), returning a new root ref. parentID is the raw source-level parent identifier ("" for root-level entries). fileID is the raw source-level file identifier; it is stored as the leaf key. Pass an empty root to start a new tree.

func (*Tree) Lookup

func (t *Tree) Lookup(root, parentID, fileID string) (string, error)

Lookup returns the value associated with (parentID, fileID), or ("", nil) if not found. parentID is the raw source-level parent identifier ("" for root-level entries).

func (*Tree) LookupByFileID

func (t *Tree) LookupByFileID(root, fileID string) (string, error)

LookupByFileID finds a value by walking the entire tree and matching on the raw fileID. This is O(N) and slower than Lookup, but does not require the parentID context. Use only when the parentID is not available (e.g. path resolution for legacy entries).

func (*Tree) NodeRefs

func (t *Tree) NodeRefs(root string, fn func(ref string) error) error

NodeRefs visits every HAMT node ref reachable from root (including root itself). This is useful for garbage-collection marking.

func (*Tree) Walk

func (t *Tree) Walk(root string, fn func(key, value string) error) error

Walk visits every (key, value) pair stored in the tree rooted at root.