bounded_tree.go 4.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187
  1. package bounded_tree
  2. import (
  3. "sync"
  4. "github.com/chrislusf/seaweedfs/weed/glog"
  5. "github.com/chrislusf/seaweedfs/weed/util"
  6. )
  7. type Node struct {
  8. Parent *Node
  9. Name string
  10. Children map[string]*Node
  11. }
  12. type BoundedTree struct {
  13. root *Node
  14. sync.RWMutex
  15. baseDir util.FullPath
  16. }
  17. func NewBoundedTree(baseDir util.FullPath) *BoundedTree {
  18. return &BoundedTree{
  19. root: &Node{
  20. Name: "/",
  21. },
  22. baseDir: baseDir,
  23. }
  24. }
  25. type VisitNodeFunc func(path util.FullPath) (childDirectories []string, err error)
  26. // If the path is not visited, call the visitFn for each level of directory
  27. // No action if the directory has been visited before or does not exist.
  28. // A leaf node, which has no children, represents a directory not visited.
  29. // A non-leaf node or a non-existing node represents a directory already visited, or does not need to visit.
  30. func (t *BoundedTree) EnsureVisited(p util.FullPath, visitFn VisitNodeFunc) (visitErr error) {
  31. t.Lock()
  32. defer t.Unlock()
  33. if t.root == nil {
  34. return
  35. }
  36. if t.baseDir != "/" {
  37. p = p[len(t.baseDir):]
  38. }
  39. components := p.Split()
  40. // fmt.Printf("components %v %d\n", components, len(components))
  41. canDelete, err := t.ensureVisited(t.root, t.baseDir, components, 0, visitFn)
  42. if err != nil {
  43. return err
  44. }
  45. if canDelete {
  46. t.root = nil
  47. }
  48. return nil
  49. }
  50. func (t *BoundedTree) ensureVisited(n *Node, currentPath util.FullPath, components []string, i int, visitFn VisitNodeFunc) (canDeleteNode bool, visitErr error) {
  51. // println("ensureVisited", currentPath, i)
  52. if n == nil {
  53. // fmt.Printf("%s null\n", currentPath)
  54. return
  55. }
  56. if n.isVisited() {
  57. // fmt.Printf("%s visited %v\n", currentPath, n.Name)
  58. } else {
  59. // fmt.Printf("ensure %v\n", currentPath)
  60. filerPath := currentPath
  61. if t.baseDir != "/" {
  62. filerPath = t.baseDir + filerPath
  63. }
  64. children, err := visitFn(filerPath)
  65. if err != nil {
  66. glog.V(0).Infof("failed to visit %s: %v", currentPath, err)
  67. return false, err
  68. }
  69. if len(children) == 0 {
  70. // fmt.Printf(" canDelete %v without children\n", currentPath)
  71. return true, nil
  72. }
  73. n.Children = make(map[string]*Node)
  74. for _, child := range children {
  75. // fmt.Printf(" add child %v %v\n", currentPath, child)
  76. n.Children[child] = &Node{
  77. Name: child,
  78. }
  79. }
  80. }
  81. if i >= len(components) {
  82. return
  83. }
  84. // fmt.Printf(" check child %v %v\n", currentPath, components[i])
  85. toVisitNode, found := n.Children[components[i]]
  86. if !found {
  87. // fmt.Printf(" did not find child %v %v\n", currentPath, components[i])
  88. return
  89. }
  90. // fmt.Printf(" ensureVisited %v %v\n", currentPath, toVisitNode.Name)
  91. canDelete, childVisitErr := t.ensureVisited(toVisitNode, currentPath.Child(components[i]), components, i+1, visitFn)
  92. if childVisitErr != nil {
  93. return false, childVisitErr
  94. }
  95. if canDelete {
  96. // fmt.Printf(" delete %v %v\n", currentPath, components[i])
  97. delete(n.Children, components[i])
  98. if len(n.Children) == 0 {
  99. // fmt.Printf(" canDelete %v\n", currentPath)
  100. return true, nil
  101. }
  102. }
  103. return false, nil
  104. }
  105. func (n *Node) isVisited() bool {
  106. if n == nil {
  107. return true
  108. }
  109. if len(n.Children) > 0 {
  110. return true
  111. }
  112. return false
  113. }
  114. func (n *Node) getChild(childName string) *Node {
  115. if n == nil {
  116. return nil
  117. }
  118. if len(n.Children) > 0 {
  119. return n.Children[childName]
  120. }
  121. return nil
  122. }
  123. func (t *BoundedTree) HasVisited(p util.FullPath) bool {
  124. t.RLock()
  125. defer t.RUnlock()
  126. if t.root == nil {
  127. return true
  128. }
  129. components := p.Split()
  130. // fmt.Printf("components %v %d\n", components, len(components))
  131. return t.hasVisited(t.root, util.FullPath("/"), components, 0)
  132. }
  133. func (t *BoundedTree) hasVisited(n *Node, currentPath util.FullPath, components []string, i int) bool {
  134. if n == nil {
  135. return true
  136. }
  137. if !n.isVisited() {
  138. return false
  139. }
  140. // fmt.Printf(" hasVisited child %v %+v %d\n", currentPath, components, i)
  141. if i >= len(components) {
  142. return true
  143. }
  144. toVisitNode, found := n.Children[components[i]]
  145. if !found {
  146. return true
  147. }
  148. return t.hasVisited(toVisitNode, currentPath.Child(components[i]), components, i+1)
  149. }