diff options
Diffstat (limited to 'utils/merkletrie/internal/fsnoder/dir.go')
-rw-r--r-- | utils/merkletrie/internal/fsnoder/dir.go | 140 |
1 files changed, 140 insertions, 0 deletions
diff --git a/utils/merkletrie/internal/fsnoder/dir.go b/utils/merkletrie/internal/fsnoder/dir.go new file mode 100644 index 0000000..1811de9 --- /dev/null +++ b/utils/merkletrie/internal/fsnoder/dir.go @@ -0,0 +1,140 @@ +package fsnoder + +import ( + "bytes" + "fmt" + "hash/fnv" + "sort" + "strings" + + "gopkg.in/src-d/go-git.v4/utils/merkletrie/noder" +) + +// Dir values implement directory-like noders. +type dir struct { + name string // relative + children []noder.Noder // sorted by name + hash []byte // memoized +} + +type byName []noder.Noder + +func (a byName) Len() int { return len(a) } +func (a byName) Swap(i, j int) { a[i], a[j] = a[j], a[i] } +func (a byName) Less(i, j int) bool { + return strings.Compare(a[i].Name(), a[j].Name()) < 0 +} + +// copies the children slice, so nobody can modify the order of its +// elements from the outside. +func newDir(name string, children []noder.Noder) (*dir, error) { + cloned := make([]noder.Noder, len(children)) + _ = copy(cloned, children) + sort.Sort(byName(cloned)) + + if hasChildrenWithNoName(cloned) { + return nil, fmt.Errorf("non-root inner nodes cannot have empty names") + } + + if hasDuplicatedNames(cloned) { + return nil, fmt.Errorf("children cannot have duplicated names") + } + + return &dir{ + name: name, + children: cloned, + }, nil +} + +func hasChildrenWithNoName(children []noder.Noder) bool { + for _, c := range children { + if c.Name() == "" { + return true + } + } + + return false +} + +func hasDuplicatedNames(children []noder.Noder) bool { + if len(children) < 2 { + return false + } + + for i := 1; i < len(children); i++ { + if children[i].Name() == children[i-1].Name() { + return true + } + } + + return false +} + +func (d *dir) Hash() []byte { + if d.hash == nil { + d.calculateHash() + } + + return d.hash +} + +// hash is calculated as the hash of "dir " plus the concatenation, for +// each child, of its name, a space and its hash. Children are sorted +// alphabetically before calculating the hash, so the result is unique. +func (d *dir) calculateHash() { + h := fnv.New64a() + h.Write([]byte("dir ")) + for _, c := range d.children { + h.Write([]byte(c.Name())) + h.Write([]byte(" ")) + h.Write(c.Hash()) + } + d.hash = h.Sum([]byte{}) +} + +func (d *dir) Name() string { + return d.name +} + +func (d *dir) IsDir() bool { + return true +} + +// returns a copy so nobody can alter the order of its elements from the +// outside. +func (d *dir) Children() ([]noder.Noder, error) { + clon := make([]noder.Noder, len(d.children)) + _ = copy(clon, d.children) + return clon, nil +} + +func (d *dir) NumChildren() (int, error) { + return len(d.children), nil +} + +const ( + dirStartMark = '(' + dirEndMark = ')' + dirElementSep = ' ' +) + +// The string generated by this method is unique for each tree, as the +// children of each node are sorted alphabetically by name when +// generating the string. +func (d *dir) String() string { + var buf bytes.Buffer + + buf.WriteString(d.name) + buf.WriteRune(dirStartMark) + + for i, c := range d.children { + if i != 0 { + buf.WriteRune(dirElementSep) + } + buf.WriteString(c.String()) + } + + buf.WriteRune(dirEndMark) + + return buf.String() +} |