1 files changed, 32 insertions, 0 deletions
diff --git a/utils/merkletrie/doc.go b/utils/merkletrie/doc.go
new file mode 100644
index 0000000..28ece3e
--- /dev/null
+++ b/utils/merkletrie/doc.go
@@ -0,0 +1,32 @@
+/*
+Package merkletrie provides support for n-ary trees that are at the same
+time Merkle trees and Radix trees (tries), and provides an efficient
+tree comparison algorithm for them.
+
+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.
+
+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.
+
+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.
+*/
+package merkletrie