forked from restic/restic
-
Notifications
You must be signed in to change notification settings - Fork 0
/
tree.go
105 lines (84 loc) · 2.19 KB
/
tree.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
package restic
import (
"errors"
"fmt"
"sort"
"github.com/restic/restic/backend"
"github.com/restic/restic/debug"
"github.com/restic/restic/pack"
)
type Tree struct {
Nodes []*Node `json:"nodes"`
}
var (
ErrNodeNotFound = errors.New("named node not found")
ErrNodeAlreadyInTree = errors.New("node already present")
)
func NewTree() *Tree {
return &Tree{
Nodes: []*Node{},
}
}
func (t Tree) String() string {
return fmt.Sprintf("Tree<%d nodes>", len(t.Nodes))
}
type TreeLoader interface {
LoadJSONPack(pack.BlobType, backend.ID, interface{}) error
}
func LoadTree(repo TreeLoader, id backend.ID) (*Tree, error) {
tree := &Tree{}
err := repo.LoadJSONPack(pack.Tree, id, tree)
if err != nil {
return nil, err
}
return tree, nil
}
// Equals returns true if t and other have exactly the same nodes.
func (t Tree) Equals(other *Tree) bool {
if len(t.Nodes) != len(other.Nodes) {
debug.Log("Tree.Equals", "tree.Equals(): trees have different number of nodes")
return false
}
for i := 0; i < len(t.Nodes); i++ {
if !t.Nodes[i].Equals(*other.Nodes[i]) {
debug.Log("Tree.Equals", "tree.Equals(): node %d is different:", i)
debug.Log("Tree.Equals", " %#v", t.Nodes[i])
debug.Log("Tree.Equals", " %#v", other.Nodes[i])
return false
}
}
return true
}
func (t *Tree) Insert(node *Node) error {
pos, _, err := t.binarySearch(node.Name)
if err == nil {
return ErrNodeAlreadyInTree
}
// https://code.google.com/p/go-wiki/wiki/SliceTricks
t.Nodes = append(t.Nodes, &Node{})
copy(t.Nodes[pos+1:], t.Nodes[pos:])
t.Nodes[pos] = node
return nil
}
func (t Tree) binarySearch(name string) (int, *Node, error) {
pos := sort.Search(len(t.Nodes), func(i int) bool {
return t.Nodes[i].Name >= name
})
if pos < len(t.Nodes) && t.Nodes[pos].Name == name {
return pos, t.Nodes[pos], nil
}
return pos, nil, ErrNodeNotFound
}
func (t Tree) Find(name string) (*Node, error) {
_, node, err := t.binarySearch(name)
return node, err
}
// Subtrees returns a slice of all subtree IDs of the tree.
func (t Tree) Subtrees() (trees backend.IDs) {
for _, node := range t.Nodes {
if node.Type == "dir" && node.Subtree != nil {
trees = append(trees, *node.Subtree)
}
}
return trees
}