Documentation
¶
Overview ¶
Package merkletrie provides support for n-ary trees that are at the same time Merkle trees and Radix trees (tries).
Git trees are Radix n-ary trees in virtue of the names of their tree entries. At the same time, git trees are Merkle trees thanks to their hashes.
This package defines Merkle tries as nodes that should have:
- a hash: the Merkle part of the Merkle trie
- a key: the Radix part of the Merkle trie
The Merkle hash condition is not enforced by this package though. This means that the hash of a node doesn't have to take into account the hashes of their children, which is good for testing purposes.
Nodes in the Merkle trie are abstracted by the Noder interface. The intended use is that git trees implements this interface, either directly or using a simple wrapper.
This package provides an iterator for merkletries that can skip whole directory-like noders and an efficient merkletrie comparison algorithm.
When comparing git trees, the simple approach of alphabetically sorting their elements and comparing the resulting lists is too slow as it depends linearly on the number of files in the trees: When a directory has lots of files but none of them has been modified, this approach is very expensive. We can do better by prunning whole directories that have not change, just by looking at their hashes. This package provides the tools to do exactly that.
Index ¶
Constants ¶
This section is empty.
Variables ¶
Functions ¶
This section is empty.
Types ¶
type Action ¶
type Action int
Action values represent the kind of things a Change can represent: insertion, deletions or modifications of files.
const ( Insert Action Delete Modify )
The set of possible actions in a change.
type Change ¶
type Change struct {
// The noder before the change or nil if it was inserted.
From noder.Path
// The noder after the change or nil if it was deleted.
To noder.Path
}
A Change value represent how a noder has change between to merkletries.
func NewDelete ¶
NewDelete returns a new Change representing the deletion of n.
func NewInsert ¶
NewInsert returns a new Change representing the insertion of n.
func NewModify ¶
NewModify returns a new Change representing that a has been modified and it is now b.
func (*Change) Action ¶
Action is convenience method that returns what Action c represents.
func (Change) String ¶
String returns a single change in human readable form, using the format: '<' + action + space + path + '>'. The contents of the file before or after the change are not included in this format.
Example: inserting a file at the path a/b/c.txt will return "<Insert a/b/c.txt>".
type Changes ¶
type Changes []Change
Changes is a list of changes between to merkletries.
func DiffTree ¶
DiffTree calculates the list of changes between two merkletries. It uses the provided hashEqual callback to compare noders.
func DiffTreeContext ¶
func DiffTreeContext(ctx context.Context, fromTree, toTree noder.Noder, hashEqual noder.Equal) (Changes, error)
DiffTree calculates the list of changes between two merkletries. It uses the provided hashEqual callback to compare noders. Error will be returned if context expires Provided context must be non nil
func (*Changes) AddRecursiveDelete ¶
AddRecursiveDelete adds the required changes to delete all the file-like noders found in root, recursively.
type Iter ¶
type Iter struct {
// contains filtered or unexported fields
}
Iter is an iterator for merkletries (only the trie part of the merkletrie is relevant here, it does not use the Hasher interface).
The iteration is performed in depth-first pre-order. Entries at each depth are traversed in (case-sensitive) alphabetical order.
This is the kind of traversal you will expect when listing ordinary files and directories recursively, for example:
Trie Traversal order
---- ---------------
.
/ | \ c
/ | \ d/
d c z ===> d/a
/ \ d/b
b a z
This iterator is somewhat especial as you can chose to skip whole "directories" when iterating:
- The Step method will iterate normally.
- the Next method will not descend deeper into the tree.
For example, if the iterator is at `d/`, the Step method will return `d/a` while the Next would have returned `z` instead (skipping `d/` and its descendants). The name of the these two methods are based on the well known "next" and "step" operations, quite common in debuggers, like gdb.
The paths returned by the iterator will be relative, if the iterator was created from a single node, or absolute, if the iterator was created from the path to the node (the path will be prefixed to all returned paths).
func NewIter ¶
NewIter returns a new relative iterator using the provider noder as its unnamed root. When iterating, all returned paths will be relative to node.
func NewIterFromPath ¶
NewIterFromPath returns a new absolute iterator from the noder at the end of the path p. When iterating, all returned paths will be absolute, using the root of the path p as their root.
func (*Iter) Next ¶
Next returns the path of the next node without descending deeper into the trie and nil. If there are no more entries in the trie it returns nil and io.EOF. In case of error, it will return nil and the error.
Source Files
Directories
¶
| Path | Synopsis |
|---|---|
|
internal
|
|
|
fsnoder
Package fsnoder allows to create merkletrie noders that resemble file systems, from human readable string descriptions.
|
Package fsnoder allows to create merkletrie noders that resemble file systems, from human readable string descriptions. |
|
Package noder provide an interface for defining nodes in a merkletrie, their hashes and their paths (a noders and its ancestors).
|
Package noder provide an interface for defining nodes in a merkletrie, their hashes and their paths (a noders and its ancestors). |