hashtree

Documentation

Overview

Package hashtree contains a merkle tree for the filesystem, which can be updated efficiently using delta calculations based on a files ModTime.

Index

• Variables
• func FindFile(s []File, name string) int
• func Read(fname string) (r [32]byte, err error)
• func ReadDir(rootDir string, parent *Node) error
• type File
  • func PutTop(dst, src []File) []File
• type Node
  • func NewNode() *Node
  • func (n *Node) Add(child *Node)
  • func (n *Node) Find(name string) *Node
  • func (n *Node) Flatten(prefix string) []File
  • func (n *Node) IndexOf(name string) int
  • func (n *Node) Remove(name string)
  • func (n *Node) RemoveAt(i int)

Variables

var Debug = false

Debug is a global flag, which is only used by the command line program to track errors down.

Functions

func FindFile

func FindFile(s []File, name string) int

FindFile returns the first entry index or -1 if not found. Expects that s is sorted ascending by name.

func Read

func Read(fname string) (r [32]byte, err error)

Read just calculates the sha256 value for a single file.

func ReadDir

func ReadDir(rootDir string, parent *Node) error

ReadDir walks in sorted order from root to any leaf. It ignores anything starting with a dot. If a directory matches that name, it is ignored entirely. To improve performance, it will only ever read leaf-files if they are unknown or if the ModTime is different. Extra in-memory nodes are removed, if they are not present in the filesystem anymore. Note that this performance improvement will fail on systems where the ModTime is not updated or the timer resolution is not small enough.

Types

type File

type File struct {
	Prefix   string // Prefix is a constant
	Filename string // Filename is a relative but full file name
	Node     *Node
}

File should represent a real physical file with the given meta data. It still virtual, as the file may not exist.

func PutTop

func PutTop(dst, src []File) []File

PutTop inserts or updates all entries from src on dst. The result is returned.

type Node

type Node struct {
	Hash     [32]byte
	Name     string
	Mode     os.FileMode
	ModTime  time.Time
	Children []*Node
}

A Node is an element in a merkle tree. This one represents a part of the real filesystem. Using a hash tree, we can efficiently decide and find changes in very large and complex trees.

func NewNode

func NewNode() *Node

func (*Node) Add

func (n *Node) Add(child *Node)

Add inserts the given child and keeps a sorted order.

func (*Node) Find

func (n *Node) Find(name string) *Node

Find returns the first Node with the given name or nil.

func (*Node) Flatten

func (n *Node) Flatten(prefix string) []File

Flatten returns hashtree files with absolute file names according to the given root. The array is sorted ascending.

func (*Node) IndexOf

func (n *Node) IndexOf(name string) int

IndexOf returns the found index or nil in log(n), because children are sorted ascending by name.

func (*Node) Remove

func (n *Node) Remove(name string)

Remove deletes the first child with that name

func (*Node) RemoveAt

func (n *Node) RemoveAt(i int)

RemoveAt deletes the node at the given index