From 8850e130896c88a4efe45badde5e7f0a5ae62173 Mon Sep 17 00:00:00 2001 From: Eric Biggers Date: Sun, 11 Nov 2012 23:41:23 -0600 Subject: [PATCH] Non-recursive for_dentry_in_tree() --- src/dentry.c | 235 +++++++++++++++++++++++++++++++++++++++++++-------- src/dentry.h | 11 +-- 2 files changed, 202 insertions(+), 44 deletions(-) diff --git a/src/dentry.c b/src/dentry.c index 359ebf16..61af7012 100644 --- 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) @@ -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 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; - 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 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); + +#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 841c9ca9..733cb2ee 100644 --- a/src/dentry.h +++ b/src/dentry.h @@ -161,13 +161,7 @@ struct dentry { /* Byte 48 */ - union { - struct list_head tmp_list; - struct { - void *tmp_ptr_1; - void *tmp_ptr_2; - }; - }; + struct list_head tmp_list; /* Byte 64 */ @@ -208,6 +202,8 @@ struct dentry { * WIMStructs */ u32 refcnt; + u32 full_path_utf8_len; + /* 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; - u32 full_path_utf8_len; }; #define rbnode_dentry(node) container_of(node, struct dentry, rb_node) -- 2.43.0