| 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 |