The highest tagged major version isv5.
merkletrie
package
This package is not in the latest version of its module.
Details
Valid go.mod file
The Go module system was introduced in Go 1.11 and is the official dependency management solution for Go.
Redistributable licenseRedistributable licenses place minimal restrictions on how software can be used, modified, and redistributed.
- Tagged version
Modules with tagged versions give importers more predictable builds.
- Stable version
When a project reaches major version v1 it is considered stable.
- Learn more about best practices
Repository
Links
Open Source Insights
Documentation¶
Overview¶
Package merkletrie provides support for n-ary trees that are at the sametime Merkle trees and Radix trees (tries).
Git trees are Radix n-ary trees in virtue of the names of theirtree entries. At the same time, git trees are Merkle trees thanks totheir 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. Thismeans that the hash of a node doesn't have to take into account the hashes oftheir children, which is good for testing purposes.
Nodes in the Merkle trie are abstracted by the Noder interface. Theintended use is that git trees implements this interface, eitherdirectly or using a simple wrapper.
This package provides an iterator for merkletries that can skip wholedirectory-like noders and an efficient merkletrie comparison algorithm.
When comparing git trees, the simple approach of alphabetically sortingtheir elements and comparing the resulting lists is too slow as itdepends linearly on the number of files in the trees: When a directoryhas lots of files but none of them has been modified, this approach isvery expensive. We can do better by prunning whole directories thathave not change, just by looking at their hashes. This package providesthe tools to do exactly that.
Index¶
Constants¶
This section is empty.
Variables¶
var (ErrCanceled =errors.New("operation canceled"))Functions¶
This section is empty.
Types¶
typeAction¶
type Actionint
Action values represent the kind of things a Change can represent:insertion, deletions or modifications of files.
const (Insert ActionDeleteModify)
The set of possible actions in a change.
typeChange¶
type Change struct {// The noder before the change or nil if it was inserted.Fromnoder.Path// The noder after the change or nil if it was deleted.Tonoder.Path}A Change value represent how a noder has change between to merkletries.
typeChanges¶
type Changes []Change
Changes is a list of changes between to merkletries.
funcDiffTree¶
DiffTree calculates the list of changes between two merkletries. Ituses the provided hashEqual callback to compare noders.
funcDiffTreeContext¶
func DiffTreeContext(ctxcontext.Context, fromTree, toTreenoder.Noder,hashEqualnoder.Equal) (Changes,error)
DiffTree calculates the list of changes between two merkletries. Ituses the provided hashEqual callback to compare noders.Error will be returned if context expiresProvided context must be non nil
func (*Changes)AddRecursiveDelete¶
AddRecursiveDelete adds the required changes to delete all thefile-like noders found in root, recursively.
typeIter¶
type Iter struct {// contains filtered or unexported fields}Iter is an iterator for merkletries (only the trie part of themerkletrie is relevant here, it does not use the Hasher interface).
The iteration is performed in depth-first pre-order. Entries at eachdepth are traversed in (case-sensitive) alphabetical order.
This is the kind of traversal you will expect when listing ordinaryfiles and directories recursively, for example:
Trie Traversal order ---- --------------- . / | \ c / | \ d/ d c z ===> d/a / \ d/bb 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 onthe well known "next" and "step" operations, quite common indebuggers, like gdb.
The paths returned by the iterator will be relative, if the iteratorwas created from a single node, or absolute, if the iterator wascreated from the path to the node (the path will be prefixed to allreturned paths).
funcNewIter¶
NewIter returns a new relative iterator using the provider noder asits unnamed root. When iterating, all returned paths will berelative to node.
funcNewIterFromPath¶
NewIterFromPath returns a new absolute iterator from the noder at theend of the path p. When iterating, all returned paths will beabsolute, using the root of the path p as their root.
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). |