Debian Codegraph @

utils/merkletrie/doc.go

raw
1 /*
2 Package merkletrie provides support for n-ary trees that are at the same
3 time Merkle trees and Radix trees (tries).
4
5 Git trees are Radix n-ary trees in virtue of the names of their
6 tree entries. At the same time, git trees are Merkle trees thanks to
7 their hashes.
8
9 This package defines Merkle tries as nodes that should have:
10
11 - a hash: the Merkle part of the Merkle trie
12
13 - a key: the Radix part of the Merkle trie
14
15 The Merkle hash condition is not enforced by this package though. This
16 means that the hash of a node doesn't have to take into account the hashes of
17 their children, which is good for testing purposes.
18
19 Nodes in the Merkle trie are abstracted by the Noder interface. The
20 intended use is that git trees implements this interface, either
21 directly or using a simple wrapper.
22
23 This package provides an iterator for merkletries that can skip whole
24 directory-like noders and an efficient merkletrie comparison algorithm.
25
26 When comparing git trees, the simple approach of alphabetically sorting
27 their elements and comparing the resulting lists is too slow as it
28 depends linearly on the number of files in the trees: When a directory
29 has lots of files but none of them has been modified, this approach is
30 very expensive. We can do better by prunning whole directories that
31 have not change, just by looking at their hashes. This package provides
32 the tools to do exactly that.
33 */
34 package merkletrie