tree.go (2600B) - Raw
1 package rootfs 2 3 import ( 4 "path/filepath" 5 "sort" 6 "strings" 7 ) 8 9 // tree is a way to store directory paths for whiteouts. 10 // It is semi-optimized for reads and non-optimized for writes; 11 // See Merge() and HasPrefix for trade-offs. 12 type tree struct { 13 name string 14 children []*tree 15 end bool 16 } 17 18 // newTree creates a new tree from a given path. 19 func newTree(paths ...string) *tree { 20 t := &tree{name: ".", children: []*tree{}} 21 for _, path := range paths { 22 t.Add(path) 23 } 24 return t 25 } 26 27 // Add adds a sequence to a tree 28 func (t *tree) Add(path string) { 29 t.add(strings.Split(filepath.Clean(path), "/")) 30 } 31 32 // HasPrefix returns if tree contains a prefix matching a given sequence. 33 // Search algorithm is naive: it does linear search when going through the 34 // nodes, whereas binary search would work here too. Since we expect number of 35 // children to be really small (usually 1 or 2), it does not really matter. If 36 // you find a real-world container with 30+ whiteout paths on a single path, it 37 // may make sense to replace the algorithm. 38 func (t *tree) HasPrefix(path string) bool { 39 return t.hasprefix(strings.Split(filepath.Clean(path), "/")) 40 } 41 42 // Merge merges adds t2 to t. It is not optimized for speed, since it's walking 43 // full branch for every other branch. 44 func (t *tree) Merge(t2 *tree) { 45 t.merge(t2, []string{}) 46 } 47 48 // String stringifies a tree 49 func (t *tree) String() string { 50 if len(t.children) == 0 { 51 return "<empty>" 52 } 53 54 res := &stringer{[]string{}} 55 res.stringify(t, []string{}) 56 sort.Strings(res.res) 57 return strings.Join(res.res, ":") 58 } 59 60 func (t *tree) add(nodes []string) { 61 if len(nodes) == 0 { 62 t.end = true 63 return 64 } 65 for i := range t.children { 66 if t.children[i].name == nodes[0] { 67 t.children[i].add(nodes[1:]) 68 return 69 } 70 } 71 72 newNode := &tree{name: nodes[0]} 73 t.children = append(t.children, newNode) 74 newNode.add(nodes[1:]) 75 } 76 77 func (t *tree) hasprefix(nodes []string) bool { 78 if len(nodes) == 0 { 79 return t.end 80 } 81 if t.end { 82 return true 83 } 84 85 for i := range t.children { 86 if t.children[i].name == nodes[0] { 87 return t.children[i].hasprefix(nodes[1:]) 88 } 89 } 90 91 return false 92 } 93 94 type stringer struct { 95 res []string 96 } 97 98 func (s *stringer) stringify(t *tree, acc []string) { 99 if t.name == "" { 100 return 101 } 102 acc = append(acc, t.name) 103 if t.end { 104 s.res = append(s.res, strings.Join(acc, "/")) 105 } 106 107 for _, child := range t.children { 108 s.stringify(child, acc) 109 } 110 } 111 112 func (t *tree) merge(t2 *tree, acc []string) { 113 if t2.end { 114 t.add(append(acc[1:], t2.name)) 115 } 116 acc = append(acc, t2.name) 117 for _, child := range t2.children { 118 t.merge(child, acc) 119 } 120 }