Non-recursive for_dentry_in_tree()

diff --git a/src/dentry.c b/src/dentry.c
index 359ebf1602c005e4eef8dee6f6c9238aa514e63b..61af70120eea2613b9919e49d3506cf3e7fc4f08 100644 (file)
--- a/src/dentry.c
+++ b/src/dentry.c
@@ -281,34 +281,6 @@ int for_dentry_in_rbtree(struct rb_node *root,
        }
 }
 
        }
 }
 

-int for_dentry_tree_in_rbtree(struct rb_node *root,
-                             int (*visitor)(struct dentry*, void*),
-                             void *arg)
-{
-       int ret;
-       struct rb_node *node = root;
-       LIST_HEAD(stack);
-       while (true) {
-               if (node) {
-                       list_add(&rbnode_dentry(node)->tmp_list, &stack);
-                       node = node->rb_left;
-               } else {
-                       struct list_head *next;
-                       struct dentry *dentry;
-
-                       next = stack.next;
-                       if (next == &stack)
-                               return 0;
-                       dentry = container_of(next, struct dentry, tmp_list);
-                       list_del(next);
-                       ret = for_dentry_in_tree(dentry, visitor, arg);
-                       if (ret != 0)
-                               return ret;
-                       node = dentry->rb_node.rb_right;
-               }
-       }
-}
-

 static int for_dentry_tree_in_rbtree_depth(struct rb_node *node,
                                           int (*visitor)(struct dentry*, void*),
                                           void *arg)
 static int for_dentry_tree_in_rbtree_depth(struct rb_node *node,
                                           int (*visitor)(struct dentry*, void*),
                                           void *arg)


@@ -331,18 +303,125 @@ static int for_dentry_tree_in_rbtree_depth(struct rb_node *node,
 }
 
 /*
 }
 
 /*

- * Calls a function on all directory entries in a directory tree.  It is called
- * on a parent before its children.
+ * Calls a function on all directory entries in a WIM dentry tree.  Logically,
+ * this is a pre-order traversal (the function is called on a parent dentry
+ * before its children), but sibling dentries will be visited in order as well.
+ *
+ * In reality, the data structures are more complicated than the above might
+ * suggest because there is a separate red-black tree for each dentry that
+ * contains its direct children.

  */
 int for_dentry_in_tree(struct dentry *root,
                       int (*visitor)(struct dentry*, void*), void *arg)
 {
  */
 int for_dentry_in_tree(struct dentry *root,
                       int (*visitor)(struct dentry*, void*), void *arg)
 {

-       int ret = visitor(root, arg);
+       int ret;
+       struct list_head main_stack;
+       struct list_head sibling_stack;
+       struct list_head *sibling_stack_bottom;
+       struct dentry *main_dentry;
+       struct rb_node *node;
+       struct list_head *next_sibling;
+       struct dentry *dentry;
+
+       ret = visitor(root, arg);

        if (ret != 0)
                return ret;
 
        if (ret != 0)
                return ret;
 

-       return for_dentry_tree_in_rbtree(root->d_inode->children.rb_node,
-                                        visitor, arg);
+       main_dentry = root;
+       sibling_stack_bottom = &sibling_stack;
+       INIT_LIST_HEAD(&main_stack);
+       INIT_LIST_HEAD(&sibling_stack);
+
+       list_add(&main_dentry->tmp_list, &main_stack);
+
+       while (1) {
+               // Prepare for non-recursive in-order traversal of the red-black
+               // tree of this dentry's children
+               node = main_dentry->d_inode->children.rb_node;
+
+               while (node) {
+                       // Push this node to the sibling stack and examine the
+                       // left neighbor, if any
+                       list_add(&rbnode_dentry(node)->tmp_list, &sibling_stack);
+               push_left_siblings:
+                       node = node->rb_left;
+               }
+
+
+               pop_sibling:
+
+               next_sibling = sibling_stack.next;
+               if (next_sibling == sibling_stack_bottom) {
+                       // Done with all siblings.  Pop the main dentry to move
+                       // back up one level.
+                       main_dentry = container_of(main_stack.next,
+                                                  struct dentry,
+                                                  tmp_list);
+                       list_del(&main_dentry->tmp_list);
+
+                       if (main_dentry == root) {
+                               ret = 0;
+                               goto out;
+                       }
+
+                       // Restore sibling stack bottom from the previous level
+                       sibling_stack_bottom = (void*)main_dentry->parent;
+
+                       // Restore the just-popped main dentry's parent
+                       main_dentry->parent = container_of(main_stack.next,
+                                                          struct dentry,
+                                                          tmp_list);
+
+                       // The next sibling to traverse in the previous level,
+                       // in the in-order traversal of the red-black tree, is
+                       // the one to the right.
+                       node = main_dentry->rb_node.rb_right;
+                       if (node)  {
+                               list_add(&rbnode_dentry(node)->tmp_list,
+                                        &sibling_stack);
+                               goto push_left_siblings;
+                       } else {
+                               goto pop_sibling;
+                       }
+               } else {
+                       // The sibling stack is not empty, so there are more to
+                       // go!
+
+                       // Pop a sibling from the stack.
+                       list_del(next_sibling);
+                       dentry = container_of(next_sibling, struct dentry, tmp_list);
+
+                       // Visit the sibling.
+                       ret = visitor(dentry, arg);
+                       if (ret != 0) {
+                               // Failed.  Restore parent pointers for the
+                               // dentries in the main stack
+                               list_del(&root->tmp_list);
+                               list_for_each_entry(dentry, &main_stack, tmp_list) {
+                                       dentry->parent = container_of(dentry->tmp_list.next,
+                                                                     struct dentry,
+                                                                     tmp_list);
+                               }
+                               goto out;
+                       }
+
+                       // We'd like to recursively visit the dentry tree rooted
+                       // at this sibling.  To do this, add it to the main
+                       // stack, save the bottom of this level's sibling stack
+                       // in the dentry->parent field, re-set the bottom of the
+                       // sibling stack to be its current height, and set
+                       // main_dentry to the sibling so it becomes the parent
+                       // dentry in the next iteration through the outer loop.
+                       list_add(&dentry->tmp_list, &main_stack);
+                       dentry->parent = (void*)sibling_stack_bottom;
+                       sibling_stack_bottom = sibling_stack.next;
+
+                       main_dentry = dentry;
+               }
+       }
+out:
+       root->parent = root;
+       return ret;

 }
 
 /*
 }
 
 /*


@@ -352,12 +431,96 @@ int for_dentry_in_tree(struct dentry *root,
 int for_dentry_in_tree_depth(struct dentry *root,
                             int (*visitor)(struct dentry*, void*), void *arg)
 {
 int for_dentry_in_tree_depth(struct dentry *root,
                             int (*visitor)(struct dentry*, void*), void *arg)
 {

-
-       int ret = for_dentry_tree_in_rbtree_depth(root->d_inode->children.rb_node,
-                                                 visitor, arg);
+#if 1
+       int ret;
+       ret = for_dentry_tree_in_rbtree_depth(root->d_inode->children.rb_node,
+                                             visitor, arg);

        if (ret != 0)
                return ret;
        return visitor(root, arg);
        if (ret != 0)
                return ret;
        return visitor(root, arg);

+
+#else
+       int ret;
+       struct list_head main_stack;
+       struct list_head sibling_stack;
+       struct list_head *sibling_stack_bottom;
+       struct dentry *main_dentry;
+       struct rb_node *node;
+       struct list_head *next_sibling;
+       struct dentry *dentry;
+
+       main_dentry = root;
+       sibling_stack_bottom = &sibling_stack;
+       INIT_LIST_HEAD(&main_stack);
+       INIT_LIST_HEAD(&sibling_stack);
+
+       list_add(&main_dentry->tmp_list, &main_stack);
+
+       while (1) {
+               node = main_dentry->d_inode->children.rb_node;
+
+               while (1) {
+                       if (node->rb_left) {
+                               list_add(&rbnode_dentry(node)->tmp_list, &sibling_stack);
+                               node = node->rb_left;
+                               continue;
+                       }
+                       if (node->rb_right) {
+                               list_add(&rbnode_dentry(node)->tmp_list, &sibling_stack);
+                               node = node->rb_right;
+                               continue;
+                       }
+                       list_add(&rbnode_dentry(node)->tmp_list, &sibling_stack);
+               }
+
+       pop_sibling:
+               next_sibling = sibling_stack.next;
+               if (next_sibling == sibling_stack_bottom) {
+                       main_dentry = container_of(main_stack.next,
+                                                  struct dentry,
+                                                  tmp_list);
+                       list_del(&main_dentry->tmp_list);
+
+
+                       sibling_stack_bottom = (void*)main_dentry->parent;
+
+                       if (main_dentry == root) {
+                               main_dentry->parent = main_dentry;
+                               ret = visitor(dentry, arg);
+                               return ret;
+                       } else {
+                               main_dentry->parent = container_of(main_stack.next,
+                                                                  struct dentry,
+                                                                  tmp_list);
+                       }
+
+                       ret = visitor(main_dentry, arg);
+
+                       if (ret != 0) {
+                               list_del(&root->tmp_list);
+                               list_for_each_entry(dentry, &main_stack, tmp_list) {
+                                       dentry->parent = container_of(dentry->tmp_list.next,
+                                                                     struct dentry,
+                                                                     tmp_list);
+                               }
+                               root->parent = root;
+                               return ret;
+                       }
+                       goto pop_sibling;
+               } else {
+
+                       list_del(next_sibling);
+                       dentry = container_of(next_sibling, struct dentry, tmp_list);
+
+
+                       list_add(&dentry->tmp_list, &main_stack);
+                       dentry->parent = (void*)sibling_stack_bottom;
+                       sibling_stack_bottom = sibling_stack.next;
+
+                       main_dentry = dentry;
+               }
+       }
+#endif

 }
 
 /*
 }
 
 /*

diff --git a/src/dentry.h b/src/dentry.h
index 841c9ca935bda23c420bff4b841cb099b7e4a222..733cb2eea36ed5a074df72df2f8c135531b6eeed 100644 (file)
--- a/src/dentry.h
+++ b/src/dentry.h
@@ -161,13 +161,7 @@ struct dentry {
 
        /* Byte 48 */
 
 
        /* Byte 48 */
 

-       union {
-               struct list_head tmp_list;
-               struct {
-                       void *tmp_ptr_1;
-                       void *tmp_ptr_2;
-               };
-       };
+       struct list_head tmp_list;

 
        /* Byte 64 */
 
 
        /* Byte 64 */
 


@@ -208,6 +202,8 @@ struct dentry {
         * WIMStructs */
        u32 refcnt;
 
         * WIMStructs */
        u32 refcnt;
 

+       u32   full_path_utf8_len;
+

        /* Pointer to the UTF-16 short filename (malloc()ed buffer) */
        char *short_name;
 
        /* Pointer to the UTF-16 short filename (malloc()ed buffer) */
        char *short_name;
 


@@ -216,7 +212,6 @@ struct dentry {
 
        /* Full path (UTF-8) to this dentry (malloc()ed buffer). */
        char *full_path_utf8;
 
        /* Full path (UTF-8) to this dentry (malloc()ed buffer). */
        char *full_path_utf8;

-       u32   full_path_utf8_len;

 };
 
 #define rbnode_dentry(node) container_of(node, struct dentry, rb_node)
 };
 
 #define rbnode_dentry(node) container_of(node, struct dentry, rb_node)