Nonrecursive for_dentry_child()
authorEric Biggers <ebiggers3@gmail.com>
Fri, 21 Mar 2014 20:23:32 +0000 (15:23 -0500)
committerEric Biggers <ebiggers3@gmail.com>
Fri, 21 Mar 2014 20:31:06 +0000 (15:31 -0500)
include/wimlib/dentry.h
include/wimlib/inode.h
include/wimlib/rbtree.h
src/dentry.c
src/iterate_dir.c
src/mount_image.c
src/ntfs-3g_capture.c
src/rbtree.c
src/wildcard.c

index 9140693..6e58fd2 100644 (file)
@@ -154,22 +154,39 @@ for_dentry_in_tree(struct wim_dentry *root,
                   void *args);
 
 extern int
-for_dentry_in_rbtree(struct rb_node *node,
-                    int (*visitor)(struct wim_dentry *, void *),
-                    void *arg);
-
-extern int
-for_dentry_child(const struct wim_dentry *dentry,
-                int (*visitor)(struct wim_dentry *, void *),
-                void *arg);
-
-extern int
 for_dentry_in_tree_depth(struct wim_dentry *root,
                         int (*visitor)(struct wim_dentry*, void*),
                         void *args);
 
+/* Iterate through each @child dentry of the @parent inode,
+ * in sorted order (by case sensitive name).  */
+#define for_inode_child(child, parent)                                         \
+       for (struct rb_node *_tmp = rb_first(&parent->i_children);              \
+            _tmp &&                                                            \
+               ((child = rb_entry(_tmp, struct wim_dentry, rb_node)), 1);      \
+            _tmp = rb_next(_tmp))
+
+/* Iterate through each @child dentry of the @parent dentry,
+ * in sorted order (by case sensitive name).  */
+#define for_dentry_child(child, parent) \
+       for_inode_child(child, parent->d_inode)
+
+/* Iterate through each @child dentry of the @parent inode,
+ * in postorder (safe for freeing).  */
+#define for_inode_child_postorder(child, parent)                                       \
+       for (struct rb_node *_tmp = rb_first_postorder(&parent->i_children), *_parent;  \
+            _tmp &&                                                                    \
+               ((child = rb_entry(_tmp, struct wim_dentry, rb_node)), 1) &&            \
+               ((_parent = rb_parent(_tmp)), 1);                                       \
+            _tmp = rb_next_postorder(_tmp, _parent))
+
+/* Iterate through each @child dentry of the @parent dentry,
+ * in postorder (safe for freeing).  */
+#define for_dentry_child_postorder(child, parent) \
+       for_inode_child_postorder(child, parent->d_inode)
+
 extern void
-calculate_subdir_offsets(struct wim_dentry *dentry, u64 *subdir_offset_p);
+calculate_subdir_offsets(struct wim_dentry *root, u64 *subdir_offset_p);
 
 extern int
 dentry_set_name(struct wim_dentry *dentry, const tchar *new_name);
@@ -258,8 +275,7 @@ read_dentry_tree(const u8 *buf, size_t buf_len,
                 u64 root_offset, struct wim_dentry **root_ret);
 
 extern u8 *
-write_dentry_tree(const struct wim_dentry * restrict tree,
-                 u8 * restrict p);
+write_dentry_tree(struct wim_dentry *root, u8 *p);
 
 static inline bool
 dentry_is_root(const struct wim_dentry *dentry)
index 5d04427..c869f84 100644 (file)
@@ -387,7 +387,7 @@ inode_is_symlink(const struct wim_inode *inode)
 static inline bool
 inode_has_children(const struct wim_inode *inode)
 {
-       return inode->i_children.rb_node != NULL;
+       return !rb_empty_root(&inode->i_children);
 }
 
 extern int
index bdb209d..3ae97a5 100644 (file)
@@ -1,39 +1,31 @@
 /*
-  Red Black Trees
-  (C) 1999  Andrea Arcangeli <andrea@suse.de>
-
-  This program is free software; you can redistribute it and/or modify
-  it under the terms of the GNU General Public License as published by
-  the Free Software Foundation; either version 2 of the License, or
-  (at your option) any later version.
-
-  This program is distributed in the hope that it will be useful,
-  but WITHOUT ANY WARRANTY; without even the implied warranty of
-  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
-  GNU General Public License for more details.
-
-  You should have received a copy of the GNU General Public License
-  along with this program; if not, write to the Free Software
-  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
-
-  linux/include/linux/rbtree.h
-
-  To use rbtrees you'll have to implement your own insert and search cores.
-  This will avoid us to use callbacks and to drop drammatically performances.
-  I know it's not the cleaner way,  but in C (not in C++) to get
-  performances and genericity...
-
-  See Documentation/rbtree.txt for documentation and samples.
-*/
-
-#ifndef        _LINUX_RBTREE_H
-#define        _LINUX_RBTREE_H
+ *  Red Black Trees
+ *  Copyright (C) 1999  Andrea Arcangeli <andrea@suse.de>
+ *
+ *  This program is free software; you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation; either version 2 of the License, or
+ *  (at your option) any later version.
+ *
+ *  This program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with this program; if not, write to the Free Software
+ *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+
+#ifndef        _RBTREE_H
+#define        _RBTREE_H
 
 #include <stdint.h>
 #include <stddef.h>
+#include <stdbool.h>
 
 struct rb_node {
-       uintptr_t  __rb_parent_color;
+       uintptr_t __rb_parent_color;
        struct rb_node *rb_right;
        struct rb_node *rb_left;
 };
@@ -42,20 +34,60 @@ struct rb_root {
        struct rb_node *rb_node;
 };
 
-
-#define rb_parent(r)   ((struct rb_node *)((r)->__rb_parent_color & ~3))
 #define        rb_entry(ptr, type, member) container_of(ptr, type, member)
 
-extern void rb_insert_color(struct rb_node *, struct rb_root *);
-extern void rb_erase(struct rb_node *, struct rb_root *);
+#define RB_ROOT        (struct rb_root) { NULL, }
+
+static inline bool
+rb_empty_root(const struct rb_root *root)
+{
+       return root->rb_node == NULL;
+}
+
+static inline struct rb_node *
+rb_parent(const struct rb_node *node)
+{
+       return (struct rb_node *)(node->__rb_parent_color & ~1);
+}
 
-static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
-                               struct rb_node ** rb_link)
+/* 'empty' nodes are nodes that are known not to be inserted in an rbtree */
+static inline bool
+rb_empty_node(const struct rb_node *node)
+{
+       return node->__rb_parent_color == (uintptr_t)node;
+}
+
+static inline void
+rb_clear_node(struct rb_node *node)
+{
+       node->__rb_parent_color = (uintptr_t)node;
+}
+
+extern void
+rb_insert_color(struct rb_node *node, struct rb_root *root);
+
+extern void
+rb_erase(struct rb_node *node, struct rb_root *root);
+
+extern struct rb_node *
+rb_first(const struct rb_root *root);
+
+extern struct rb_node *
+rb_first_postorder(const struct rb_root *root);
+
+extern struct rb_node *
+rb_next(const struct rb_node *node);
+
+extern struct rb_node *
+rb_next_postorder(const struct rb_node *node, const struct rb_node *parent);
+
+static inline void
+rb_link_node(struct rb_node *node, struct rb_node *parent,
+            struct rb_node **rb_link)
 {
        node->__rb_parent_color = (uintptr_t)parent;
        node->rb_left = node->rb_right = NULL;
-
        *rb_link = node;
 }
 
-#endif /* _LINUX_RBTREE_H */
+#endif /* _RBTREE_H */
index 3783434..59e9757 100644 (file)
@@ -9,7 +9,7 @@
  */
 
 /*
- * Copyright (C) 2012, 2013 Eric Biggers
+ * Copyright (C) 2012, 2013, 2014 Eric Biggers
  *
  * This file is part of wimlib, a library for working with WIM files.
  *
@@ -301,93 +301,39 @@ dentry_in_total_length(const struct wim_dentry *dentry)
        return (length + 7) & ~7;
 }
 
-int
-for_dentry_in_rbtree(struct rb_node *root,
-                    int (*visitor)(struct wim_dentry *, void *),
-                    void *arg)
-{
-       int ret;
-       struct rb_node *node = root;
-       LIST_HEAD(stack);
-       while (1) {
-               if (node) {
-                       list_add(&rbnode_dentry(node)->tmp_list, &stack);
-                       node = node->rb_left;
-               } else {
-                       struct list_head *next;
-                       struct wim_dentry *dentry;
-
-                       next = stack.next;
-                       if (next == &stack)
-                               return 0;
-                       dentry = container_of(next, struct wim_dentry, tmp_list);
-                       list_del(next);
-                       ret = visitor(dentry, 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 wim_dentry*, void*),
-                               void *arg)
+do_for_dentry_in_tree(struct wim_dentry *dentry,
+                     int (*visitor)(struct wim_dentry *, void *), void *arg)
 {
        int ret;
-       if (node) {
-               ret = for_dentry_tree_in_rbtree_depth(node->rb_left,
-                                                     visitor, arg);
-               if (ret != 0)
-                       return ret;
-               ret = for_dentry_tree_in_rbtree_depth(node->rb_right,
-                                                     visitor, arg);
-               if (ret != 0)
-                       return ret;
-               ret = for_dentry_in_tree_depth(rbnode_dentry(node), visitor, arg);
-               if (ret != 0)
+       struct wim_dentry *child;
+
+       ret = (*visitor)(dentry, arg);
+       if (unlikely(ret))
+               return ret;
+
+       for_dentry_child(child, dentry) {
+               ret = for_dentry_in_tree(child, visitor, arg);
+               if (unlikely(ret))
                        return ret;
        }
        return 0;
 }
 
+
 static int
-for_dentry_tree_in_rbtree(struct rb_node *node,
-                         int (*visitor)(struct wim_dentry*, void*),
-                         void *arg)
+do_for_dentry_in_tree_depth(struct wim_dentry *dentry,
+                           int (*visitor)(struct wim_dentry *, void *), void *arg)
 {
        int ret;
-       if (node) {
-               ret = for_dentry_tree_in_rbtree(node->rb_left, visitor, arg);
-               if (ret)
-                       return ret;
-               ret = for_dentry_in_tree(rbnode_dentry(node), visitor, arg);
-               if (ret)
-                       return ret;
-               ret = for_dentry_tree_in_rbtree(node->rb_right, visitor, arg);
-               if (ret)
+       struct wim_dentry *child;
+
+       for_dentry_child_postorder(child, dentry) {
+               ret = for_dentry_in_tree_depth(child, visitor, arg);
+               if (unlikely(ret))
                        return ret;
        }
-       return 0;
-}
-
-/*
- * Iterate over all children of @dentry, calling the function @visitor, passing
- * it a child dentry and the extra argument @arg.
- *
- * Note: this function iterates over ALL child dentries, even those with the
- * same case-insensitive name.
- *
- * Note: this function clobbers the tmp_list field of the child dentries.  */
-int
-for_dentry_child(const struct wim_dentry *dentry,
-                int (*visitor)(struct wim_dentry *, void *),
-                void *arg)
-{
-       return for_dentry_in_rbtree(dentry->d_inode->i_children.rb_node,
-                                   visitor,
-                                   arg);
+       return unlikely((*visitor)(dentry, arg));
 }
 
 /* Calls a function on all directory entries in a WIM dentry tree.  Logically,
@@ -396,35 +342,22 @@ for_dentry_child(const struct wim_dentry *dentry,
  * */
 int
 for_dentry_in_tree(struct wim_dentry *root,
-                  int (*visitor)(struct wim_dentry*, void*), void *arg)
+                  int (*visitor)(struct wim_dentry *, void *), void *arg)
 {
-       int ret;
-
-       if (root == NULL)
+       if (unlikely(!root))
                return 0;
-       ret = (*visitor)(root, arg);
-       if (ret)
-               return ret;
-       return for_dentry_tree_in_rbtree(root->d_inode->i_children.rb_node,
-                                        visitor,
-                                        arg);
+       return do_for_dentry_in_tree(root, visitor, arg);
 }
 
 /* Like for_dentry_in_tree(), but the visitor function is always called on a
  * dentry's children before on itself. */
 int
 for_dentry_in_tree_depth(struct wim_dentry *root,
-                        int (*visitor)(struct wim_dentry*, void*), void *arg)
+                        int (*visitor)(struct wim_dentry *, void *), void *arg)
 {
-       int ret;
-
-       if (root == NULL)
+       if (unlikely(!root))
                return 0;
-       ret = for_dentry_tree_in_rbtree_depth(root->d_inode->i_children.rb_node,
-                                             visitor, arg);
-       if (ret)
-               return ret;
-       return (*visitor)(root, arg);
+       return do_for_dentry_in_tree_depth(root, visitor, arg);
 }
 
 /* Calculate the full path of @dentry.  The full path of its parent must have
@@ -522,53 +455,36 @@ dentry_full_path(struct wim_dentry *dentry)
 }
 
 static int
-increment_subdir_offset(struct wim_dentry *dentry, void *subdir_offset_p)
+dentry_calculate_subdir_offset(struct wim_dentry *dentry, void *_subdir_offset_p)
 {
-       *(u64*)subdir_offset_p += dentry_out_total_length(dentry);
-       return 0;
-}
 
-static int
-call_calculate_subdir_offsets(struct wim_dentry *dentry, void *subdir_offset_p)
-{
-       calculate_subdir_offsets(dentry, subdir_offset_p);
+       if (dentry_is_directory(dentry)) {
+               u64 *subdir_offset_p = _subdir_offset_p;
+               struct wim_dentry *child;
+
+               /* Set offset of directory's child dentries  */
+               dentry->subdir_offset = *subdir_offset_p;
+
+               /* Account for child dentries  */
+               for_dentry_child(child, dentry)
+                       *subdir_offset_p += dentry_out_total_length(child);
+
+               /* Account for end-of-directory entry  */
+               *subdir_offset_p += 8;
+       } else {
+               /* Not a directory; set subdir_offset to 0  */
+               dentry->subdir_offset = 0;
+       }
        return 0;
 }
 
 /*
- * Recursively calculates the subdir offsets for a directory tree.
- *
- * @dentry:  The root of the directory tree.
- * @subdir_offset_p:  The current subdirectory offset; i.e., the subdirectory
- *                   offset for @dentry.
+ * Calculates the subdir offsets for a directory tree.
  */
 void
-calculate_subdir_offsets(struct wim_dentry *dentry, u64 *subdir_offset_p)
+calculate_subdir_offsets(struct wim_dentry *root, u64 *subdir_offset_p)
 {
-       struct rb_node *node;
-
-       dentry->subdir_offset = *subdir_offset_p;
-       node = dentry->d_inode->i_children.rb_node;
-       if (node) {
-               /* Advance the subdir offset by the amount of space the children
-                * of this dentry take up. */
-               for_dentry_in_rbtree(node, increment_subdir_offset, subdir_offset_p);
-
-               /* End-of-directory dentry on disk. */
-               *subdir_offset_p += 8;
-
-               /* Recursively call calculate_subdir_offsets() on all the
-                * children. */
-               for_dentry_in_rbtree(node, call_calculate_subdir_offsets, subdir_offset_p);
-       } else {
-               /* On disk, childless directories have a valid subdir_offset
-                * that points to an 8-byte end-of-directory dentry.  Regular
-                * files or reparse points have a subdir_offset of 0. */
-               if (dentry_is_directory(dentry))
-                       *subdir_offset_p += 8;
-               else
-                       dentry->subdir_offset = 0;
-       }
+       for_dentry_in_tree(root, dentry_calculate_subdir_offset, subdir_offset_p);
 }
 
 static int
@@ -1172,7 +1088,7 @@ dentry_add_child(struct wim_dentry * restrict parent,
                if (existing) {
                        list_add(&child->case_insensitive_conflict_list,
                                 &existing->case_insensitive_conflict_list);
-                       child->rb_node_case_insensitive.__rb_parent_color = 0;
+                       rb_clear_node(&child->rb_node_case_insensitive);
                } else {
                        INIT_LIST_HEAD(&child->case_insensitive_conflict_list);
                }
@@ -1190,7 +1106,7 @@ unlink_dentry(struct wim_dentry *dentry)
                return;
        rb_erase(&dentry->rb_node, &parent->d_inode->i_children);
 
-       if (dentry->rb_node_case_insensitive.__rb_parent_color) {
+       if (!rb_empty_node(&dentry->rb_node_case_insensitive)) {
                /* This dentry was in the case-insensitive red-black tree. */
                rb_erase(&dentry->rb_node_case_insensitive,
                         &parent->d_inode->i_children_case_insensitive);
@@ -1788,50 +1704,25 @@ write_dentry(const struct wim_dentry * restrict dentry, u8 * restrict p)
 }
 
 static int
-write_dentry_cb(struct wim_dentry *dentry, void *_p)
+write_dir_dentries(struct wim_dentry *dir, void *_pp)
 {
-       u8 **p = _p;
-       *p = write_dentry(dentry, *p);
-       return 0;
-}
+       if (dentry_is_directory(dir)) {
+               u8 **pp = _pp;
+               u8 *p = *pp;
+               struct wim_dentry *child;
 
-static u8 *
-write_dentry_tree_recursive(const struct wim_dentry *parent, u8 *p);
+               /* write child dentries */
+               for_dentry_child(child, dir)
+                       p = write_dentry(child, p);
 
-static int
-write_dentry_tree_recursive_cb(struct wim_dentry *dentry, void *_p)
-{
-       u8 **p = _p;
-       *p = write_dentry_tree_recursive(dentry, *p);
+               /* write end of directory entry */
+               *(u64*)p = 0;
+               p += 8;
+               *pp = p;
+       }
        return 0;
 }
 
-/* Recursive function that writes a dentry tree rooted at @parent, not including
- * @parent itself, which has already been written. */
-static u8 *
-write_dentry_tree_recursive(const struct wim_dentry *parent, u8 *p)
-{
-       /* Nothing to do if this dentry has no children. */
-       if (parent->subdir_offset == 0)
-               return p;
-
-       /* Write child dentries and end-of-directory entry.
-        *
-        * Note: we need to write all of this dentry's children before
-        * recursively writing the directory trees rooted at each of the child
-        * dentries, since the on-disk dentries for a dentry's children are
-        * always located at consecutive positions in the metadata resource! */
-       for_dentry_child(parent, write_dentry_cb, &p);
-
-       /* write end of directory entry */
-       *(le64*)p = cpu_to_le64(0);
-       p += 8;
-
-       /* Recurse on children. */
-       for_dentry_child(parent, write_dentry_tree_recursive_cb, &p);
-       return p;
-}
-
 /* Writes a directory tree to the metadata resource.
  *
  * @root:      Root of the dentry tree.
@@ -1840,20 +1731,18 @@ write_dentry_tree_recursive(const struct wim_dentry *parent, u8 *p)
  * Returns pointer to the byte after the last byte we wrote.
  */
 u8 *
-write_dentry_tree(const struct wim_dentry * restrict root, u8 * restrict p)
+write_dentry_tree(struct wim_dentry *root, u8 *p)
 {
        DEBUG("Writing dentry tree.");
        wimlib_assert(dentry_is_root(root));
 
-       /* If we're the root dentry, we have no parent that already
-        * wrote us, so we need to write ourselves. */
+       /* write root dentry and end-of-directory entry following it */
        p = write_dentry(root, p);
-
-       /* Write end of directory entry after the root dentry just to be safe;
-        * however the root dentry obviously cannot have any siblings. */
-       *(le64*)p = cpu_to_le64(0);
+       *(u64*)p = 0;
        p += 8;
 
-       /* Recursively write the rest of the dentry tree. */
-       return write_dentry_tree_recursive(root, p);
+       /* write the rest of the dentry tree */
+       for_dentry_in_tree(root, write_dir_dentries, &p);
+
+       return p;
 }
index cc5c63b..977a6e6 100644 (file)
@@ -149,27 +149,6 @@ free_wimlib_dentry(struct wimlib_dir_entry *wdentry)
        FREE(wdentry);
 }
 
-struct iterate_dir_tree_ctx {
-       WIMStruct *wim;
-       int flags;
-       wimlib_iterate_dir_tree_callback_t cb;
-       void *user_ctx;
-};
-
-static int
-do_iterate_dir_tree(WIMStruct *wim,
-                   struct wim_dentry *dentry, int flags,
-                   wimlib_iterate_dir_tree_callback_t cb,
-                   void *user_ctx);
-
-static int
-call_do_iterate_dir_tree(struct wim_dentry *dentry, void *_ctx)
-{
-       struct iterate_dir_tree_ctx *ctx = _ctx;
-       return do_iterate_dir_tree(ctx->wim, dentry, ctx->flags,
-                                  ctx->cb, ctx->user_ctx);
-}
-
 static int
 do_iterate_dir_tree(WIMStruct *wim,
                    struct wim_dentry *dentry, int flags,
@@ -199,13 +178,16 @@ do_iterate_dir_tree(WIMStruct *wim,
        if (flags & (WIMLIB_ITERATE_DIR_TREE_FLAG_RECURSIVE |
                     WIMLIB_ITERATE_DIR_TREE_FLAG_CHILDREN))
        {
-               struct iterate_dir_tree_ctx ctx = {
-                       .wim      = wim,
-                       .flags    = flags &= ~WIMLIB_ITERATE_DIR_TREE_FLAG_CHILDREN,
-                       .cb       = cb,
-                       .user_ctx = user_ctx,
-               };
-               ret = for_dentry_child(dentry, call_do_iterate_dir_tree, &ctx);
+               struct wim_dentry *child;
+
+               ret = 0;
+               for_dentry_child(child, dentry) {
+                       ret = do_iterate_dir_tree(wim, child,
+                                                 flags & ~WIMLIB_ITERATE_DIR_TREE_FLAG_CHILDREN,
+                                                 cb, user_ctx);
+                       if (ret)
+                               break;
+               }
        }
 out_free_wimlib_dentry:
        free_wimlib_dentry(wdentry);
index 9dcfe9e..a7dc82a 100644 (file)
@@ -8,7 +8,7 @@
  */
 
 /*
- * Copyright (C) 2012, 2013 Eric Biggers
+ * Copyright (C) 2012, 2013, 2014 Eric Biggers
  *
  * This file is part of wimlib, a library for working with WIM files.
  *
@@ -2045,32 +2045,6 @@ wimfs_read(const char *path, char *buf, size_t size,
        return ret;
 }
 
-struct fill_params {
-       void *buf;
-       fuse_fill_dir_t filler;
-};
-
-static int
-dentry_fuse_fill(struct wim_dentry *dentry, void *arg)
-{
-       struct fill_params *fill_params = arg;
-
-       char *file_name_mbs;
-       size_t file_name_mbs_nbytes;
-       int ret;
-
-       ret = utf16le_to_tstr(dentry->file_name,
-                             dentry->file_name_nbytes,
-                             &file_name_mbs,
-                             &file_name_mbs_nbytes);
-       if (ret)
-               return -errno;
-
-       ret = fill_params->filler(fill_params->buf, file_name_mbs, NULL, 0);
-       FREE(file_name_mbs);
-       return ret;
-}
-
 /* Fills in the entries of the directory specified by @path using the
  * FUSE-provided function @filler.  */
 static int
@@ -2079,22 +2053,38 @@ wimfs_readdir(const char *path, void *buf, fuse_fill_dir_t filler,
 {
        struct wimfs_fd *fd = (struct wimfs_fd*)(uintptr_t)fi->fh;
        struct wim_inode *inode;
+       struct wim_dentry *child;
+       int ret;
 
        if (!fd)
                return -EBADF;
 
        inode = fd->f_inode;
 
-       struct fill_params fill_params = {
-               .buf = buf,
-               .filler = filler,
-       };
+       ret = filler(buf, ".", NULL, 0);
+       if (ret)
+               return ret;
+       ret = filler(buf, "..", NULL, 0);
+       if (ret)
+               return ret;
 
-       filler(buf, ".", NULL, 0);
-       filler(buf, "..", NULL, 0);
+       for_inode_child(child, inode) {
+               char *file_name_mbs;
+               size_t file_name_mbs_nbytes;
 
-       return for_dentry_in_rbtree(inode->i_children.rb_node,
-                                   dentry_fuse_fill, &fill_params);
+               ret = utf16le_to_tstr(child->file_name,
+                                     child->file_name_nbytes,
+                                     &file_name_mbs,
+                                     &file_name_mbs_nbytes);
+               if (ret)
+                       return -errno;
+
+               ret = filler(buf, file_name_mbs, NULL, 0);
+               FREE(file_name_mbs);
+               if (ret)
+                       return ret;
+       }
+       return 0;
 }
 
 
index 11cbc9d..a0b3709 100644 (file)
@@ -386,9 +386,8 @@ lookup_dos_name(const struct dos_name_map *map, u64 ntfs_ino)
 }
 
 static int
-set_dentry_dos_name(struct wim_dentry *dentry, void *arg)
+set_dentry_dos_name(struct wim_dentry *dentry, const struct dos_name_map *map)
 {
-       const struct dos_name_map *map = arg;
        const struct dos_name_node *node;
 
        if (dentry->is_win32_name) {
@@ -626,8 +625,14 @@ build_dentry_tree_ntfs_recursive(struct wim_dentry **root_ret,
                        ERROR_WITH_ERRNO("Error reading directory \"%s\"", path);
                        ret = WIMLIB_ERR_NTFS_3G;
                } else {
-                       ret = for_dentry_child(root, set_dentry_dos_name,
-                                              &dos_name_map);
+                       struct wim_dentry *child;
+
+                       ret = 0;
+                       for_dentry_child(child, root) {
+                               ret = set_dentry_dos_name(child, &dos_name_map);
+                               if (ret)
+                                       break;
+                       }
                }
                destroy_dos_name_map(&dos_name_map);
                if (ret)
index 10d1dc7..5adbada 100644 (file)
@@ -1,24 +1,22 @@
 /*
-  Red Black Trees
-  (C) 1999  Andrea Arcangeli <andrea@suse.de>
-  (C) 2002  David Woodhouse <dwmw2@infradead.org>
-  (C) 2012  Michel Lespinasse <walken@google.com>
-
-  This program is free software; you can redistribute it and/or modify
-  it under the terms of the GNU General Public License as published by
-  the Free Software Foundation; either version 2 of the License, or
-  (at your option) any later version.
-
-  This program is distributed in the hope that it will be useful,
-  but WITHOUT ANY WARRANTY; without even the implied warranty of
-  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
-  GNU General Public License for more details.
-
-  You should have received a copy of the GNU General Public License
-  along with this program; if not, write to the Free Software
-  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
-
-  linux/lib/rbtree.c
+ *  Red Black Trees
+ *  Copyright (C) 1999  Andrea Arcangeli <andrea@suse.de>
+ *  Copyright (C) 2002  David Woodhouse <dwmw2@infradead.org>
+ *  Copyright (C) 2012  Michel Lespinasse <walken@google.com>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */
 
 #ifdef HAVE_CONFIG_H
  *  parentheses and have some accompanying text comment.
  */
 
-struct rb_augment_callbacks {
-       void (*propagate)(struct rb_node *node, struct rb_node *stop);
-       void (*copy)(struct rb_node *old, struct rb_node *new);
-       void (*rotate)(struct rb_node *old, struct rb_node *new);
-};
-
 #define        RB_RED          0
 #define        RB_BLACK        1
 
-#define __rb_parent(pc)    ((struct rb_node *)(pc & ~3))
+#define __rb_parent(pc)    ((struct rb_node *)(pc & ~1))
 
 #define __rb_color(pc)     ((pc) & 1)
 #define __rb_is_black(pc)  __rb_color(pc)
@@ -66,30 +58,33 @@ struct rb_augment_callbacks {
 #define rb_is_red(rb)      __rb_is_red((rb)->__rb_parent_color)
 #define rb_is_black(rb)    __rb_is_black((rb)->__rb_parent_color)
 
-static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
+static inline void
+rb_set_parent(struct rb_node *rb, struct rb_node *p)
 {
        rb->__rb_parent_color = rb_color(rb) | (uintptr_t)p;
 }
 
-static inline void rb_set_parent_color(struct rb_node *rb,
-                                      struct rb_node *p, int color)
+static inline void
+rb_set_parent_color(struct rb_node *rb, struct rb_node *p, int color)
 {
        rb->__rb_parent_color = (uintptr_t)p | color;
 }
 
-static inline void rb_set_black(struct rb_node *rb)
+static inline void
+rb_set_black(struct rb_node *rb)
 {
        rb->__rb_parent_color |= RB_BLACK;
 }
 
-static inline struct rb_node *rb_red_parent(struct rb_node *red)
+static inline struct rb_node *
+rb_red_parent(struct rb_node *red)
 {
        return (struct rb_node *)red->__rb_parent_color;
 }
 
 static inline void
-__rb_change_child(struct rb_node *old, struct rb_node *new,
-                 struct rb_node *parent, struct rb_root *root)
+rb_change_child(struct rb_node *old, struct rb_node *new,
+               struct rb_node *parent, struct rb_root *root)
 {
        if (parent) {
                if (parent->rb_left == old)
@@ -106,22 +101,21 @@ __rb_change_child(struct rb_node *old, struct rb_node *new,
  * - old gets assigned new as a parent and 'color' as a color.
  */
 static inline void
-__rb_rotate_set_parents(struct rb_node *old, struct rb_node *new,
+rb_rotate_set_parents(struct rb_node *old, struct rb_node *new,
                        struct rb_root *root, int color)
 {
        struct rb_node *parent = rb_parent(old);
        new->__rb_parent_color = old->__rb_parent_color;
        rb_set_parent_color(old, new, color);
-       __rb_change_child(old, new, parent, root);
+       rb_change_child(old, new, parent, root);
 }
 
-static inline void
-__rb_erase_color(struct rb_node *parent, struct rb_root *root,
-       void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
+static void
+rb_erase_color(struct rb_node *parent, struct rb_root *root)
 {
        struct rb_node *node = NULL, *sibling, *tmp1, *tmp2;
 
-       while (true) {
+       for (;;) {
                /*
                 * Loop invariants:
                 * - node is black (or NULL on first iteration)
@@ -144,9 +138,7 @@ __rb_erase_color(struct rb_node *parent, struct rb_root *root,
                                parent->rb_right = tmp1 = sibling->rb_left;
                                sibling->rb_left = parent;
                                rb_set_parent_color(tmp1, parent, RB_BLACK);
-                               __rb_rotate_set_parents(parent, sibling, root,
-                                                       RB_RED);
-                               augment_rotate(parent, sibling);
+                               rb_rotate_set_parents(parent, sibling, root, RB_RED);
                                sibling = tmp1;
                        }
                        tmp1 = sibling->rb_right;
@@ -198,7 +190,6 @@ __rb_erase_color(struct rb_node *parent, struct rb_root *root,
                                if (tmp1)
                                        rb_set_parent_color(tmp1, sibling,
                                                            RB_BLACK);
-                               augment_rotate(sibling, tmp2);
                                tmp1 = sibling;
                                sibling = tmp2;
                        }
@@ -219,9 +210,7 @@ __rb_erase_color(struct rb_node *parent, struct rb_root *root,
                        rb_set_parent_color(tmp1, sibling, RB_BLACK);
                        if (tmp2)
                                rb_set_parent(tmp2, parent);
-                       __rb_rotate_set_parents(parent, sibling, root,
-                                               RB_BLACK);
-                       augment_rotate(parent, sibling);
+                       rb_rotate_set_parents(parent, sibling, root, RB_BLACK);
                        break;
                } else {
                        sibling = parent->rb_left;
@@ -230,9 +219,8 @@ __rb_erase_color(struct rb_node *parent, struct rb_root *root,
                                parent->rb_left = tmp1 = sibling->rb_right;
                                sibling->rb_right = parent;
                                rb_set_parent_color(tmp1, parent, RB_BLACK);
-                               __rb_rotate_set_parents(parent, sibling, root,
-                                                       RB_RED);
-                               augment_rotate(parent, sibling);
+                               rb_rotate_set_parents(parent, sibling, root,
+                                                     RB_RED);
                                sibling = tmp1;
                        }
                        tmp1 = sibling->rb_left;
@@ -259,7 +247,6 @@ __rb_erase_color(struct rb_node *parent, struct rb_root *root,
                                if (tmp1)
                                        rb_set_parent_color(tmp1, sibling,
                                                            RB_BLACK);
-                               augment_rotate(sibling, tmp2);
                                tmp1 = sibling;
                                sibling = tmp2;
                        }
@@ -269,17 +256,14 @@ __rb_erase_color(struct rb_node *parent, struct rb_root *root,
                        rb_set_parent_color(tmp1, sibling, RB_BLACK);
                        if (tmp2)
                                rb_set_parent(tmp2, parent);
-                       __rb_rotate_set_parents(parent, sibling, root,
-                                               RB_BLACK);
-                       augment_rotate(parent, sibling);
+                       rb_rotate_set_parents(parent, sibling, root, RB_BLACK);
                        break;
                }
        }
 }
 
-static inline void
-rb_erase_augmented(struct rb_node *node, struct rb_root *root,
-                  const struct rb_augment_callbacks *augment)
+void
+rb_erase(struct rb_node *node, struct rb_root *root)
 {
        struct rb_node *child = node->rb_right, *tmp = node->rb_left;
        struct rb_node *parent, *rebalance;
@@ -295,7 +279,7 @@ rb_erase_augmented(struct rb_node *node, struct rb_root *root,
                 */
                pc = node->__rb_parent_color;
                parent = __rb_parent(pc);
-               __rb_change_child(node, child, parent, root);
+               rb_change_child(node, child, parent, root);
                if (child) {
                        child->__rb_parent_color = pc;
                        rebalance = NULL;
@@ -306,7 +290,7 @@ rb_erase_augmented(struct rb_node *node, struct rb_root *root,
                /* Still case 1, but this time the child is node->rb_left */
                tmp->__rb_parent_color = pc = node->__rb_parent_color;
                parent = __rb_parent(pc);
-               __rb_change_child(node, tmp, parent, root);
+               rb_change_child(node, tmp, parent, root);
                rebalance = NULL;
                tmp = parent;
        } else {
@@ -324,7 +308,6 @@ rb_erase_augmented(struct rb_node *node, struct rb_root *root,
                         */
                        parent = successor;
                        child2 = successor->rb_right;
-                       augment->copy(node, successor);
                } else {
                        /*
                         * Case 3: node's successor is leftmost under
@@ -348,8 +331,6 @@ rb_erase_augmented(struct rb_node *node, struct rb_root *root,
                        parent->rb_left = child2 = successor->rb_right;
                        successor->rb_right = child;
                        rb_set_parent(child, successor);
-                       augment->copy(node, successor);
-                       augment->propagate(parent, successor);
                }
 
                successor->rb_left = tmp = node->rb_left;
@@ -357,7 +338,7 @@ rb_erase_augmented(struct rb_node *node, struct rb_root *root,
 
                pc = node->__rb_parent_color;
                tmp = __rb_parent(pc);
-               __rb_change_child(node, successor, tmp, root);
+               rb_change_child(node, successor, tmp, root);
                if (child2) {
                        successor->__rb_parent_color = pc;
                        rb_set_parent_color(child2, parent, RB_BLACK);
@@ -370,15 +351,12 @@ rb_erase_augmented(struct rb_node *node, struct rb_root *root,
                tmp = successor;
        }
 
-       augment->propagate(tmp, NULL);
        if (rebalance)
-               __rb_erase_color(rebalance, root, augment->rotate);
+               rb_erase_color(rebalance, root);
 }
 
-
-static inline void
-__rb_insert(struct rb_node *node, struct rb_root *root,
-           void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
+void
+rb_insert_color(struct rb_node *node, struct rb_root *root)
 {
        struct rb_node *parent = rb_red_parent(node), *gparent, *tmp;
 
@@ -442,7 +420,6 @@ __rb_insert(struct rb_node *node, struct rb_root *root,
                                        rb_set_parent_color(tmp, parent,
                                                            RB_BLACK);
                                rb_set_parent_color(parent, node, RB_RED);
-                               augment_rotate(parent, node);
                                parent = node;
                                tmp = node->rb_right;
                        }
@@ -460,8 +437,7 @@ __rb_insert(struct rb_node *node, struct rb_root *root,
                        parent->rb_right = gparent;
                        if (tmp)
                                rb_set_parent_color(tmp, gparent, RB_BLACK);
-                       __rb_rotate_set_parents(gparent, parent, root, RB_RED);
-                       augment_rotate(gparent, parent);
+                       rb_rotate_set_parents(gparent, parent, root, RB_RED);
                        break;
                } else {
                        tmp = gparent->rb_left;
@@ -484,7 +460,6 @@ __rb_insert(struct rb_node *node, struct rb_root *root,
                                        rb_set_parent_color(tmp, parent,
                                                            RB_BLACK);
                                rb_set_parent_color(parent, node, RB_RED);
-                               augment_rotate(parent, node);
                                parent = node;
                                tmp = node->rb_left;
                        }
@@ -494,35 +469,89 @@ __rb_insert(struct rb_node *node, struct rb_root *root,
                        parent->rb_left = gparent;
                        if (tmp)
                                rb_set_parent_color(tmp, gparent, RB_BLACK);
-                       __rb_rotate_set_parents(gparent, parent, root, RB_RED);
-                       augment_rotate(gparent, parent);
+                       rb_rotate_set_parents(gparent, parent, root, RB_RED);
                        break;
                }
        }
 }
 
+static struct rb_node *
+rb_left_deepest_node(const struct rb_node *node)
+{
+       for (;;) {
+               if (node->rb_left)
+                       node = node->rb_left;
+               else if (node->rb_right)
+                       node = node->rb_right;
+               else
+                       return (struct rb_node *)node;
+       }
+}
 
-/*
- * Non-augmented rbtree manipulation functions.
- *
- * We use dummy augmented callbacks here, and have the compiler optimize them
- * out of the rb_insert_color() and rb_erase() function definitions.
- */
+struct rb_node *
+rb_next_postorder(const struct rb_node *node, const struct rb_node *parent)
+{
+       /* If we're sitting on node, we've already seen our children */
+       if (parent && node == parent->rb_left && parent->rb_right) {
+               /* If we are the parent's left node, go to the parent's right
+                * node then all the way down to the left */
+               return rb_left_deepest_node(parent->rb_right);
+       } else
+               /* Otherwise we are the parent's right node, and the parent
+                * should be next */
+               return (struct rb_node *)parent;
+}
 
-static inline void dummy_propagate(struct rb_node *node, struct rb_node *stop) {}
-static inline void dummy_copy(struct rb_node *old, struct rb_node *new) {}
-static inline void dummy_rotate(struct rb_node *old, struct rb_node *new) {}
+struct rb_node *
+rb_first_postorder(const struct rb_root *root)
+{
+       if (!root->rb_node)
+               return NULL;
 
-static const struct rb_augment_callbacks dummy_callbacks = {
-       dummy_propagate, dummy_copy, dummy_rotate
-};
+       return rb_left_deepest_node(root->rb_node);
+}
 
-void rb_insert_color(struct rb_node *node, struct rb_root *root)
+struct rb_node *
+rb_next(const struct rb_node *node)
 {
-       __rb_insert(node, root, dummy_rotate);
+       struct rb_node *parent;
+
+       /*
+        * If we have a right-hand child, go down and then left as far
+        * as we can.
+        */
+       if (node->rb_right) {
+               node = node->rb_right;
+               while (node->rb_left)
+                       node = node->rb_left;
+               return (struct rb_node *)node;
+       }
+
+       /*
+        * No right-hand children. Everything down and left is smaller than us,
+        * so any 'next' node must be in the general direction of our parent.
+        * Go up the tree; any time the ancestor is a right-hand child of its
+        * parent, keep going up. First time it's a left-hand child of its
+        * parent, said parent is our 'next' node.
+        */
+       while ((parent = rb_parent(node)) && node == parent->rb_right)
+               node = parent;
+
+       return parent;
 }
 
-void rb_erase(struct rb_node *node, struct rb_root *root)
+/*
+ * This function returns the first node (in sort order) of the tree.
+ */
+struct rb_node *
+rb_first(const struct rb_root *root)
 {
-       rb_erase_augmented(node, root, &dummy_callbacks);
+       struct rb_node  *n;
+
+       n = root->rb_node;
+       if (!n)
+               return NULL;
+       while (n->rb_left)
+               n = n->rb_left;
+       return n;
 }
index 90efbd3..7898690 100644 (file)
@@ -138,9 +138,8 @@ wildcard_status(const tchar *wildcard)
 }
 
 static int
-match_dentry(struct wim_dentry *cur_dentry, void *_ctx)
+match_dentry(struct wim_dentry *cur_dentry, struct match_dentry_ctx *ctx)
 {
-       struct match_dentry_ctx *ctx = _ctx;
        tchar *name;
        size_t name_len;
        int ret;
@@ -205,6 +204,7 @@ expand_wildcard_recursive(struct wim_dentry *cur_dentry,
        size_t offset_save;
        size_t len_save;
        int ret;
+       struct wim_dentry *child;
 
        w = ctx->wildcard_path;
 
@@ -228,7 +228,12 @@ expand_wildcard_recursive(struct wim_dentry *cur_dentry,
        ctx->cur_component_offset = begin;
        ctx->cur_component_len = len;
 
-       ret = for_dentry_child(cur_dentry, match_dentry, ctx);
+       ret = 0;
+       for_dentry_child(child, cur_dentry) {
+               ret = match_dentry(child, ctx);
+               if (ret)
+                       break;
+       }
 
        ctx->cur_component_len = len_save;
        ctx->cur_component_offset = offset_save;
@@ -268,9 +273,6 @@ expand_wildcard_recursive(struct wim_dentry *cur_dentry,
  *
  * @return 0 on success; a positive error code on error; or the first nonzero
  * value returned by @consume_dentry.
- *
- * Note: this function uses the @tmp_list field of dentries it attempts to
- * match.
  */
 int
 expand_wildcard(WIMStruct *wim,