diff options
| -rw-r--r-- | weed/util/bounded_tree/bounded_tree.go | 66 | ||||
| -rw-r--r-- | weed/util/bounded_tree/bounded_tree_test.go | 5 |
2 files changed, 55 insertions, 16 deletions
diff --git a/weed/util/bounded_tree/bounded_tree.go b/weed/util/bounded_tree/bounded_tree.go index fa172a764..5aa31ef74 100644 --- a/weed/util/bounded_tree/bounded_tree.go +++ b/weed/util/bounded_tree/bounded_tree.go @@ -1,8 +1,6 @@ package bounded_tree import ( - "fmt" - "github.com/chrislusf/seaweedfs/weed/glog" "github.com/chrislusf/seaweedfs/weed/util" ) @@ -32,14 +30,14 @@ type VisitNodeFunc func(path util.FullPath) (childDirectories []string, err erro // A leaf node, which has no children, represents a directory not visited. // A non-leaf node or a non-existing node represents a directory already visited, or does not need to visit. func (t *BoundedTree) EnsureVisited(p util.FullPath, visitFn VisitNodeFunc) { - println() - println("EnsureVisited", p) + // println() + // println("EnsureVisited", p) if t.root == nil { return } components := p.Split() - fmt.Printf("components %v %d\n", components, len(components)) + // fmt.Printf("components %v %d\n", components, len(components)) if canDelete := t.ensureVisited(t.root, util.FullPath("/"), components, 0, visitFn); canDelete { t.root = nil } @@ -47,17 +45,17 @@ func (t *BoundedTree) EnsureVisited(p util.FullPath, visitFn VisitNodeFunc) { func (t *BoundedTree) ensureVisited(n *Node, currentPath util.FullPath, components []string, i int, visitFn VisitNodeFunc) (canDeleteNode bool) { - println("ensureVisited", currentPath, i) + // println("ensureVisited", currentPath, i) if n == nil { - fmt.Printf("%s null\n", currentPath) + // fmt.Printf("%s null\n", currentPath) return } if n.isVisited() { - fmt.Printf("%s visited %v\n", currentPath, n.Name) + // fmt.Printf("%s visited %v\n", currentPath, n.Name) } else { - fmt.Printf("ensure %v\n", currentPath) + // fmt.Printf("ensure %v\n", currentPath) children, err := visitFn(currentPath) if err != nil { @@ -66,13 +64,13 @@ func (t *BoundedTree) ensureVisited(n *Node, currentPath util.FullPath, componen } if len(children) == 0 { - fmt.Printf(" canDelete %v without children\n", currentPath) + // fmt.Printf(" canDelete %v without children\n", currentPath) return true } n.Children = make(map[string]*Node) for _, child := range children { - fmt.Printf(" add child %v %v\n", currentPath, child) + // fmt.Printf(" add child %v %v\n", currentPath, child) n.Children[child] = &Node{ Name: child, } @@ -83,23 +81,23 @@ func (t *BoundedTree) ensureVisited(n *Node, currentPath util.FullPath, componen return } - fmt.Printf(" check child %v %v\n", currentPath, components[i]) + // fmt.Printf(" check child %v %v\n", currentPath, components[i]) toVisitNode, found := n.Children[components[i]] if !found { - fmt.Printf(" did not find child %v %v\n", currentPath, components[i]) + // fmt.Printf(" did not find child %v %v\n", currentPath, components[i]) return } - fmt.Printf(" ensureVisited %v %v\n", currentPath, toVisitNode.Name) + // fmt.Printf(" ensureVisited %v %v\n", currentPath, toVisitNode.Name) if canDelete := t.ensureVisited(toVisitNode, currentPath.Child(components[i]), components, i+1, visitFn); canDelete { - fmt.Printf(" delete %v %v\n", currentPath, components[i]) + // fmt.Printf(" delete %v %v\n", currentPath, components[i]) delete(n.Children, components[i]) if len(n.Children) == 0 { - fmt.Printf(" canDelete %v\n", currentPath) + // fmt.Printf(" canDelete %v\n", currentPath) return true } } @@ -127,3 +125,39 @@ func (n *Node) getChild(childName string) *Node { } return nil } + +func (t *BoundedTree) HasVisited(p util.FullPath) bool { + + if t.root == nil { + return true + } + + components := p.Split() + // fmt.Printf("components %v %d\n", components, len(components)) + return t.hasVisited(t.root, util.FullPath("/"), components, 0) +} + +func (t *BoundedTree) hasVisited(n *Node, currentPath util.FullPath, components []string, i int) bool { + + if n == nil { + return true + } + + if !n.isVisited() { + return false + } + + // fmt.Printf(" hasVisited child %v %v\n", currentPath, components[i]) + + toVisitNode, found := n.Children[components[i]] + if !found { + return true + } + + if i+1 >= len(components) { + return false + } + + return t.hasVisited(toVisitNode, currentPath.Child(components[i]), components, i+1) + +} diff --git a/weed/util/bounded_tree/bounded_tree_test.go b/weed/util/bounded_tree/bounded_tree_test.go index b8dce664c..18bc2f6d5 100644 --- a/weed/util/bounded_tree/bounded_tree_test.go +++ b/weed/util/bounded_tree/bounded_tree_test.go @@ -110,4 +110,9 @@ func TestEmptyBoundedTree(t *testing.T) { printMap(tree.root.Children) + println(tree.HasVisited(util.FullPath("/a/b"))) + println(tree.HasVisited(util.FullPath("/a"))) + println(tree.HasVisited(util.FullPath("/g"))) + println(tree.HasVisited(util.FullPath("/g/x"))) + } |