Store dentry children in red-black trees

Store the children of each dentry in a red-black tree (keyed by the dentry name)
to make dentry lookups faster.

diff --git a/src/dentry.c b/src/dentry.c
index 927b3da9baa1a80628e72d3da5ee2ef6cb548fa2..634e4def83e74d605f6306a4754acab08b119918 100644 (file)
--- a/src/dentry.c
+++ b/src/dentry.c
@@ -253,6 +253,65 @@ int inode_to_stbuf(const struct inode *inode, struct lookup_table_entry *lte,
 }
 #endif
 
 }
 #endif
 

+int for_dentry_in_rbtree(struct rb_node *node,
+                        int (*visitor)(struct dentry *, void *),
+                        void *arg)
+{
+       int ret;
+       if (node) {
+               ret = for_dentry_in_rbtree(node->rb_left, visitor, arg);
+               if (ret != 0)
+                       return ret;
+               ret = visitor(rbnode_dentry(node), arg);
+               if (ret != 0)
+                       return ret;
+               ret = for_dentry_in_rbtree(node->rb_right, visitor, arg);
+               if (ret != 0)
+                       return ret;
+       }
+       return 0;
+}
+
+int for_dentry_tree_in_rbtree(struct rb_node *node,
+                             int (*visitor)(struct dentry*, void*),
+                             void *arg)
+{
+       int ret;
+       if (node) {
+               ret = for_dentry_tree_in_rbtree(node->rb_left, visitor, arg);
+               if (ret != 0)
+                       return ret;
+               ret = for_dentry_in_tree(rbnode_dentry(node), visitor, arg);
+               if (ret != 0)
+                       return ret;
+               ret = for_dentry_tree_in_rbtree(node->rb_right, visitor, arg);
+               if (ret != 0)
+                       return ret;
+       }
+       return 0;
+}
+
+static int for_dentry_tree_in_rbtree_depth(struct rb_node *node,
+                                          int (*visitor)(struct 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)
+                       return ret;
+       }
+       return 0;
+}
+

 /*
  * 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 directory tree.  It is called
  * on a parent before its children.


@@ -260,26 +319,12 @@ int inode_to_stbuf(const struct inode *inode, struct lookup_table_entry *lte,
 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;
-       struct dentry *child;
-
-       ret = visitor(root, arg);
-
+       int ret = visitor(root, arg);

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

-       child = root->d_inode->children;
-
-       if (!child)
-               return 0;
-
-       do {
-               ret = for_dentry_in_tree(child, visitor, arg);
-               if (ret != 0)
-                       return ret;
-               child = child->next;
-       } while (child != root->d_inode->children);
-       return 0;
+       return for_dentry_tree_in_rbtree(root->d_inode->children.rb_node,
+                                        visitor, arg);

 }
 
 /*
 }
 
 /*


@@ -289,20 +334,11 @@ 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;
-       struct dentry *child;
-       struct dentry *next;

 
 

-       child = root->d_inode->children;
-       if (child) {
-               do {
-                       next = child->next;
-                       ret = for_dentry_in_tree_depth(child, visitor, arg);
-                       if (ret != 0)
-                               return ret;
-                       child = next;
-               } while (child != root->d_inode->children);
-       }
+       int ret = for_dentry_tree_in_rbtree_depth(root->d_inode->children.rb_node,
+                                                 visitor, arg);
+       if (ret != 0)
+               return ret;

        return visitor(root, arg);
 }
 
        return visitor(root, arg);
 }
 


@@ -356,6 +392,19 @@ oom:
        return WIMLIB_ERR_NOMEM;
 }
 
        return WIMLIB_ERR_NOMEM;
 }
 

+static int increment_subdir_offset(struct dentry *dentry, void *subdir_offset_p)
+{
+       *(u64*)subdir_offset_p += dentry_correct_total_length(dentry);
+       return 0;
+}
+
+static int call_calculate_subdir_offsets(struct dentry *dentry,
+                                        void *subdir_offset_p)
+{
+       calculate_subdir_offsets(dentry, subdir_offset_p);
+       return 0;
+}
+

 /*
  * Recursively calculates the subdir offsets for a directory tree.
  *
 /*
  * Recursively calculates the subdir offsets for a directory tree.
  *


@@ -365,29 +414,21 @@ oom:
  */
 void calculate_subdir_offsets(struct dentry *dentry, u64 *subdir_offset_p)
 {
  */
 void calculate_subdir_offsets(struct dentry *dentry, u64 *subdir_offset_p)
 {

-       struct dentry *child, *children;
+       struct rb_node *node;

 
 

-       children = dentry->d_inode->children;
-       child = children;

        dentry->subdir_offset = *subdir_offset_p;
        dentry->subdir_offset = *subdir_offset_p;

-
-       if (child) {
+       node = dentry->d_inode->children.rb_node;
+       if (node) {

                /* Advance the subdir offset by the amount of space the children
                 * of this dentry take up. */
                /* Advance the subdir offset by the amount of space the children
                 * of this dentry take up. */

-               do {
-                       *subdir_offset_p += dentry_correct_total_length(child);
-                       child = child->next;
-               } while (child != children);
+               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. */
 
                /* End-of-directory dentry on disk. */
                *subdir_offset_p += 8;
 
                /* Recursively call calculate_subdir_offsets() on all the
                 * children. */

-               do {
-                       calculate_subdir_offsets(child, subdir_offset_p);
-                       child = child->next;
-               } while (child != 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
        } else {
                /* On disk, childless directories have a valid subdir_offset
                 * that points to an 8-byte end-of-directory dentry.  Regular


@@ -399,47 +440,74 @@ void calculate_subdir_offsets(struct dentry *dentry, u64 *subdir_offset_p)
        }
 }
 
        }
 }
 

+static int compare_names(const char *name_1, size_t len_1,
+                        const char *name_2, size_t len_2)
+{
+       if (len_1 < len_2)
+               return -1;
+       else if (len_1 > len_2)
+               return 1;
+       else
+               return memcmp(name_1, name_2, len_1);
+}
+
+static int dentry_compare_names(const struct dentry *d1, const struct dentry *d2)
+{
+       return compare_names(d1->file_name_utf8, d1->file_name_utf8_len,
+                            d2->file_name_utf8, d2->file_name_utf8_len);
+}
+
+
+static struct dentry *
+get_rbtree_child_with_name(const struct rb_node *node,
+                          const char *name, size_t name_len)
+{
+       do {
+               struct dentry *child = rbnode_dentry(node);
+               int result = compare_names(name, name_len,
+                                          child->file_name_utf8,
+                                          child->file_name_utf8_len);
+               if (result < 0)
+                       node = node->rb_left;
+               else if (result > 0)
+                       node = node->rb_right;
+               else
+                       return child;
+       } while (node);
+       return NULL;
+}
+

 /* Returns the child of @dentry that has the file name @name.
  * Returns NULL if no child has the name. */
 struct dentry *get_dentry_child_with_name(const struct dentry *dentry,
                                          const char *name)
 {
 /* Returns the child of @dentry that has the file name @name.
  * Returns NULL if no child has the name. */
 struct dentry *get_dentry_child_with_name(const struct dentry *dentry,
                                          const char *name)
 {

-       struct dentry *child;
-       size_t name_len;
-
-       child = dentry->d_inode->children;
-       if (child) {
-               name_len = strlen(name);
-               do {
-                       if (dentry_has_name(child, name, name_len))
-                               return child;
-                       child = child->next;
-               } while (child != dentry->d_inode->children);
-       }
-       return NULL;
+       struct rb_node *node = dentry->d_inode->children.rb_node;
+       if (node)
+               return get_rbtree_child_with_name(node, name, strlen(name));
+       else
+               return NULL;

 }
 
 /* Retrieves the dentry that has the UTF-8 @path relative to the dentry
 }
 
 /* Retrieves the dentry that has the UTF-8 @path relative to the dentry

- * @cur_dir.  Returns NULL if no dentry having the path is found. */
-static struct dentry *get_dentry_relative_path(struct dentry *cur_dir,
+ * @cur_dentry.  Returns NULL if no dentry having the path is found. */
+static struct dentry *get_dentry_relative_path(struct dentry *cur_dentry,

                                               const char *path)
 {
                                               const char *path)
 {

-       struct dentry *child, *children;
-       size_t base_len;
-       const char *new_path;
-

        if (*path == '\0')
        if (*path == '\0')

-               return cur_dir;
+               return cur_dentry;
+
+       struct rb_node *node = cur_dentry->d_inode->children.rb_node;
+       if (node) {
+               struct dentry *child;
+               size_t base_len;
+               const char *new_path;

 
 

-       children = cur_dir->d_inode->children;
-       if (children) {

                new_path = path_next_part(path, &base_len);
                new_path = path_next_part(path, &base_len);

-               child = children;
-               do {
-                       if (dentry_has_name(child, path, base_len))
-                               return get_dentry_relative_path(child, new_path);
-                       child = child->next;
-               } while (child != children);
+
+               child = get_rbtree_child_with_name(node, path, base_len);
+               if (child)
+                       return get_dentry_relative_path(child, new_path);

        }
        return NULL;
 }
        }
        return NULL;
 }


@@ -643,8 +711,6 @@ struct dentry *new_dentry(const char *name)
        if (change_dentry_name(dentry, name) != 0)
                goto err;
 
        if (change_dentry_name(dentry, name) != 0)
                goto err;
 

-       dentry->next   = dentry;
-       dentry->prev   = dentry;

        dentry->parent = dentry;
 
        return dentry;
        dentry->parent = dentry;
 
        return dentry;


@@ -812,25 +878,34 @@ int increment_dentry_refcnt(struct dentry *dentry, void *ignore)
  * @dentry: The dentry to link.
  * @parent: The dentry that will be the parent of @dentry.
  */
  * @dentry: The dentry to link.
  * @parent: The dentry that will be the parent of @dentry.
  */

-void link_dentry(struct dentry *dentry, struct dentry *parent)
+bool dentry_add_child(struct dentry * restrict parent,
+                     struct dentry * restrict child)

 {
        wimlib_assert(dentry_is_directory(parent));
 {
        wimlib_assert(dentry_is_directory(parent));

-       dentry->parent = parent;
-       if (parent->d_inode->children) {
-               /* Not an only child; link to siblings. */
-               dentry->next = parent->d_inode->children;
-               dentry->prev = parent->d_inode->children->prev;
-               dentry->next->prev = dentry;
-               dentry->prev->next = dentry;
-       } else {
-               /* Only child; link to parent. */
-               parent->d_inode->children = dentry;
-               dentry->next = dentry;
-               dentry->prev = dentry;
+
+       struct rb_root *root = &parent->d_inode->children;
+       struct rb_node **new = &(root->rb_node);
+       struct rb_node *rb_parent = NULL;
+
+       while (*new) {
+               struct dentry *this = rbnode_dentry(*new);
+               int result = dentry_compare_names(child, this);
+
+               rb_parent = *new;
+
+               if (result < 0)
+                       new = &((*new)->rb_left);
+               else if (result > 0)
+                       new = &((*new)->rb_right);
+               else
+                       return false;

        }
        }

+       child->parent = parent;
+       rb_link_node(&child->rb_node, rb_parent, new);
+       rb_insert_color(&child->rb_node, root);
+       return true;

 }
 
 }
 

-

 #ifdef WITH_FUSE
 /*
  * Unlink a dentry from the directory tree.
 #ifdef WITH_FUSE
 /*
  * Unlink a dentry from the directory tree.


@@ -839,16 +914,10 @@ void link_dentry(struct dentry *dentry, struct dentry *parent)
  */
 void unlink_dentry(struct dentry *dentry)
 {
  */
 void unlink_dentry(struct dentry *dentry)
 {

-       if (dentry_is_root(dentry))
+       struct dentry *parent = dentry->parent;
+       if (parent == dentry)

                return;
                return;

-       if (dentry_is_only_child(dentry)) {
-               dentry->parent->d_inode->children = NULL;
-       } else {
-               if (dentry_is_first_sibling(dentry))
-                       dentry->parent->d_inode->children = dentry->next;
-               dentry->next->prev = dentry->prev;
-               dentry->prev->next = dentry->next;
-       }
+       rb_erase(&dentry->rb_node, &parent->d_inode->children);

 }
 #endif
 
 }
 #endif
 


@@ -1499,7 +1568,7 @@ out:
 
        /* We've read all the data for this dentry.  Set the names and their
         * lengths, and we've done. */
 
        /* We've read all the data for this dentry.  Set the names and their
         * lengths, and we've done. */

-       dentry->d_inode              = inode;
+       dentry->d_inode            = inode;

        dentry->file_name          = file_name;
        dentry->file_name_utf8     = file_name_utf8;
        dentry->short_name         = short_name;
        dentry->file_name          = file_name;
        dentry->file_name_utf8     = file_name_utf8;
        dentry->short_name         = short_name;


@@ -1577,15 +1646,8 @@ int read_dentry_tree(const u8 metadata_resource[], u64 metadata_resource_len,
                }
                memcpy(child, &cur_child, sizeof(struct dentry));
 
                }
                memcpy(child, &cur_child, sizeof(struct dentry));
 

-               if (prev_child) {
-                       prev_child->next = child;
-                       child->prev = prev_child;
-               } else {
-                       first_child = child;
-               }
+               dentry_add_child(dentry, child);

 
 

-               child->parent = dentry;
-               prev_child = child;

                inode_add_dentry(child, child->d_inode);
 
                /* If there are children of this child, call this procedure
                inode_add_dentry(child, child->d_inode);
 
                /* If there are children of this child, call this procedure


@@ -1604,14 +1666,6 @@ int read_dentry_tree(const u8 metadata_resource[], u64 metadata_resource_len,
                 * entries. */
                cur_offset += dentry_total_length(child);
        }
                 * entries. */
                cur_offset += dentry_total_length(child);
        }

-
-       /* Link last child to first one, and set parent's children pointer to
-        * the first child.  */
-       if (prev_child) {
-               prev_child->next = first_child;
-               first_child->prev = prev_child;
-       }
-       dentry->d_inode->children = first_child;

        return ret;
 }
 
        return ret;
 }
 


@@ -1695,12 +1749,26 @@ static u8 *write_dentry(const struct dentry *dentry, u8 *p)
        return p;
 }
 
        return p;
 }
 

+static int write_dentry_cb(struct dentry *dentry, void *_p)
+{
+       u8 **p = _p;
+       *p = write_dentry(dentry, *p);
+       return 0;
+}
+
+static u8 *write_dentry_tree_recursive(const struct dentry *parent, u8 *p);
+
+static int write_dentry_tree_recursive_cb(struct dentry *dentry, void *_p)
+{
+       u8 **p = _p;
+       *p = write_dentry_tree_recursive(dentry, *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 dentry *parent, u8 *p)
 {
 /* 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 dentry *parent, u8 *p)
 {

-       const struct dentry *child, *children;
-

        /* Nothing to do if this dentry has no children. */
        if (parent->subdir_offset == 0)
                return p;
        /* Nothing to do if this dentry has no children. */
        if (parent->subdir_offset == 0)
                return p;


@@ -1711,25 +1779,14 @@ static u8 *write_dentry_tree_recursive(const struct dentry *parent, u8 *p)
         * 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! */
         * 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! */

-       children = parent->d_inode->children;
-       child = children;
-       if (child) {
-               do {
-                       p = write_dentry(child, p);
-                       child = child->next;
-               } while (child != children);
-       }
+       for_dentry_in_rbtree(parent->d_inode->children.rb_node, write_dentry_cb, &p);

 
        /* write end of directory entry */
        p = put_u64(p, 0);
 
        /* Recurse on children. */
 
        /* write end of directory entry */
        p = put_u64(p, 0);
 
        /* Recurse on children. */

-       if (child) {
-               do {
-                       p = write_dentry_tree_recursive(child, p);
-                       child = child->next;
-               } while (child != children);
-       }
+       for_dentry_in_rbtree(parent->d_inode->children.rb_node,
+                            write_dentry_tree_recursive_cb, &p);

        return p;
 }
 
        return p;
 }
 

diff --git a/src/dentry.h b/src/dentry.h
index 86a1912da48b90f10433f41aa74ecbcae02c80f7..1e8724cbc973e9665b24321a1297f96aeaa10f69 100644 (file)
--- a/src/dentry.h
+++ b/src/dentry.h
@@ -5,6 +5,7 @@
 #include "config.h"
 #include "list.h"
 #include "sha1.h"
 #include "config.h"
 #include "list.h"
 #include "sha1.h"

+#include "rbtree.h"

 #include <string.h>
 
 struct stat;
 #include <string.h>
 
 struct stat;


@@ -133,9 +134,7 @@ struct dentry {
        /* The parent of this directory entry. */
        struct dentry *parent;
 
        /* The parent of this directory entry. */
        struct dentry *parent;
 

-       /* Linked list of sibling directory entries. */
-       struct dentry *next;
-       struct dentry *prev;
+       struct rb_node rb_node;

 
        /*
         * Size of directory entry on disk, in bytes.  Typical size is around
 
        /*
         * Size of directory entry on disk, in bytes.  Typical size is around


@@ -201,6 +200,8 @@ struct dentry {
        };
 };
 
        };
 };
 

+#define rbnode_dentry(node) container_of(node, struct dentry, rb_node)
+

 /*
  * WIM inode.
  *
 /*
  * WIM inode.
  *


@@ -267,9 +268,10 @@ struct inode {
        struct hlist_node hlist;
        char *extracted_file;
 
        struct hlist_node hlist;
        char *extracted_file;
 

-       /* If non-NULL, the children of this inode (implies the inode is a
-        * directory) */
-       struct dentry *children;
+       /* Root of a red-black tree storing the children of this inode (if
+        * non-empty, implies the inode is a directory, although that is also
+        * noted in the @attributes field.) */
+       struct rb_root children;

 
 #ifdef WITH_FUSE
        /* wimfs file descriptors table for the inode */
 
 #ifdef WITH_FUSE
        /* wimfs file descriptors table for the inode */


@@ -313,6 +315,10 @@ extern int for_dentry_in_tree(struct dentry *root,
                              int (*visitor)(struct dentry*, void*),
                              void *args);
 
                              int (*visitor)(struct dentry*, void*),
                              void *args);
 

+extern int for_dentry_in_rbtree(struct rb_node *node,
+                               int (*visitor)(struct dentry *, void *),
+                               void *arg);
+

 extern int for_dentry_in_tree_depth(struct dentry *root,
                                    int (*visitor)(struct dentry*, void*),
                                    void *args);
 extern int for_dentry_in_tree_depth(struct dentry *root,
                                    int (*visitor)(struct dentry*, void*),
                                    void *args);


@@ -346,7 +352,11 @@ extern void free_dentry_tree(struct dentry *root,
 extern int increment_dentry_refcnt(struct dentry *dentry, void *ignore);
 
 extern void unlink_dentry(struct dentry *dentry);
 extern int increment_dentry_refcnt(struct dentry *dentry, void *ignore);
 
 extern void unlink_dentry(struct dentry *dentry);

-extern void link_dentry(struct dentry *dentry, struct dentry *parent);
+extern bool dentry_add_child(struct dentry * restrict parent,
+                            struct dentry * restrict child);
+
+// XXX
+#define link_dentry(child, parent) dentry_add_child(parent, child)

 
 extern int verify_dentry(struct dentry *dentry, void *wim);
 
 
 extern int verify_dentry(struct dentry *dentry, void *wim);
 


@@ -374,16 +384,6 @@ static inline bool dentry_is_root(const struct dentry *dentry)
        return dentry->parent == dentry;
 }
 
        return dentry->parent == dentry;
 }
 

-static inline bool dentry_is_first_sibling(const struct dentry *dentry)
-{
-       return dentry_is_root(dentry) || dentry->parent->d_inode->children == dentry;
-}
-
-static inline bool dentry_is_only_child(const struct dentry *dentry)
-{
-       return dentry->next == dentry;
-}
-

 static inline bool inode_is_directory(const struct inode *inode)
 {
        return (inode->attributes & FILE_ATTRIBUTE_DIRECTORY)
 static inline bool inode_is_directory(const struct inode *inode)
 {
        return (inode->attributes & FILE_ATTRIBUTE_DIRECTORY)


@@ -419,9 +419,15 @@ static inline bool dentry_is_regular_file(const struct dentry *dentry)
        return inode_is_regular_file(dentry->d_inode);
 }
 
        return inode_is_regular_file(dentry->d_inode);
 }
 

+static inline bool inode_has_children(const struct inode *inode)
+{
+       return inode->children.rb_node != NULL;
+}
+

 static inline bool dentry_is_empty_directory(const struct dentry *dentry)
 {
 static inline bool dentry_is_empty_directory(const struct dentry *dentry)
 {

-       return dentry_is_directory(dentry) && dentry->d_inode->children == NULL;
+       const struct inode *inode = dentry->d_inode;
+       return inode_is_directory(inode) && !inode_has_children(inode);

 }
 
 #endif
 }
 
 #endif

diff --git a/src/mount.c b/src/mount.c
index f83d73c13227f4f2829f8b8ea810abaa65571212..ed428fca58907d1b943fb51b7590cbd934c92ace 100644 (file)
--- a/src/mount.c
+++ b/src/mount.c
@@ -1308,6 +1308,18 @@ static int wimfs_read(const char *path, char *buf, size_t size,
        }
 }
 
        }
 }
 

+struct fill_params {
+       void *buf;
+       fuse_fill_dir_t filler;
+};
+
+static int dentry_fuse_fill(struct dentry *dentry, void *arg)
+{
+       struct fill_params *fill_params = arg;
+       return fill_params->filler(fill_params->buf, dentry->file_name_utf8,
+                                  NULL, 0);
+}
+

 /* Fills in the entries of the directory specified by @path using the
  * FUSE-provided function @filler.  */
 static int wimfs_readdir(const char *path, void *buf, fuse_fill_dir_t filler,
 /* Fills in the entries of the directory specified by @path using the
  * FUSE-provided function @filler.  */
 static int wimfs_readdir(const char *path, void *buf, fuse_fill_dir_t filler,


@@ -1315,27 +1327,22 @@ static int wimfs_readdir(const char *path, void *buf, fuse_fill_dir_t filler,
 {
        struct wimlib_fd *fd = (struct wimlib_fd*)(uintptr_t)fi->fh;
        struct inode *inode;
 {
        struct wimlib_fd *fd = (struct wimlib_fd*)(uintptr_t)fi->fh;
        struct inode *inode;

-       struct dentry *child;

 
        if (!fd)
                return -EBADF;
 
        inode = fd->f_inode;
 
 
        if (!fd)
                return -EBADF;
 
        inode = fd->f_inode;
 

+       struct fill_params fill_params = {
+               .buf = buf,
+               .filler = filler,
+       };
+

        filler(buf, ".", NULL, 0);
        filler(buf, "..", NULL, 0);
 
        filler(buf, ".", NULL, 0);
        filler(buf, "..", NULL, 0);
 

-       child = inode->children;
-
-       if (!child)
-               return 0;
-
-       do {
-               if (filler(buf, child->file_name_utf8, NULL, 0))
-                       return 0;
-               child = child->next;
-       } while (child != inode->children);
-       return 0;
+       return for_dentry_in_rbtree(inode->children.rb_node,
+                                   dentry_fuse_fill, &fill_params);

 }
 
 
 }
 
 


@@ -1439,7 +1446,7 @@ static int wimfs_rename(const char *from, const char *to)
                         * directory */
                        if (!dentry_is_directory(dst))
                                return -ENOTDIR;
                         * directory */
                        if (!dentry_is_directory(dst))
                                return -ENOTDIR;

-                       if (dst->d_inode->children != NULL)
+                       if (inode_has_children(dst->d_inode))

                                return -ENOTEMPTY;
                }
                parent_of_dst = dst->parent;
                                return -ENOTEMPTY;
                }
                parent_of_dst = dst->parent;

diff --git a/src/rbtree.c b/src/rbtree.c
index 465d7148400f6cbcd1fba68feeedc069e814dae3..978844084dca8b22197b58f6c6d667a893a7318e 100644 (file)
--- a/src/rbtree.c
+++ b/src/rbtree.c
@@ -433,7 +433,7 @@ struct rb_node *rb_next(const struct rb_node *node)
         * as we can.
         */
        if (node->rb_right) {
         * as we can.
         */
        if (node->rb_right) {

-               node = node->rb_right; 
+               node = node->rb_right;

                while (node->rb_left)
                        node=node->rb_left;
                return (struct rb_node *)node;
                while (node->rb_left)
                        node=node->rb_left;
                return (struct rb_node *)node;


@@ -464,7 +464,7 @@ struct rb_node *rb_prev(const struct rb_node *node)
         * as we can.
         */
        if (node->rb_left) {
         * as we can.
         */
        if (node->rb_left) {

-               node = node->rb_left; 
+               node = node->rb_left;

                while (node->rb_right)
                        node=node->rb_right;
                return (struct rb_node *)node;
                while (node->rb_right)
                        node=node->rb_right;
                return (struct rb_node *)node;

diff --git a/src/rbtree.h b/src/rbtree.h
index 6aa184957752dce6fbe809ab9652c030e2d657a3..3fa0f16c3a9937454bbbb1f4c782621c3d29f74e 100644 (file)
--- a/src/rbtree.h
+++ b/src/rbtree.h
@@ -1,7 +1,7 @@
 /*
   Red Black Trees
   (C) 1999  Andrea Arcangeli <andrea@suse.de>
 /*
   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
   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


@@ -68,7 +68,7 @@ extern struct rb_node *rb_first(const struct rb_root *);
 extern struct rb_node *rb_last(const struct rb_root *);
 
 /* Fast replacement of a single node without remove/rebalance/add/rebalance */
 extern struct rb_node *rb_last(const struct rb_root *);
 
 /* Fast replacement of a single node without remove/rebalance/add/rebalance */

-extern void rb_replace_node(struct rb_node *victim, struct rb_node *new, 
+extern void rb_replace_node(struct rb_node *victim, struct rb_node *new,

                            struct rb_root *root);
 
 static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
                            struct rb_root *root);
 
 static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,

diff --git a/src/resource.c b/src/resource.c
index c6da07a29ed6b709dbf493acc03ed3ec0a499435..f21fd5148355ab2c0920980a4e45306a66f9139e 100644 (file)
--- a/src/resource.c
+++ b/src/resource.c
@@ -1219,10 +1219,9 @@ int read_metadata_resource(WIMStruct *w, struct image_metadata *imd)
 
        ret = read_dentry(buf, metadata_len, dentry_offset, dentry);
 
 
        ret = read_dentry(buf, metadata_len, dentry_offset, dentry);
 

-       /* This is the root dentry, so set its pointers correctly. */
+       /* This is the root dentry, so set its parent to itself. */

        dentry->parent = dentry;
        dentry->parent = dentry;

-       dentry->next   = dentry;
-       dentry->prev   = dentry;
+

        if (ret != 0)
                goto out_free_dentry_tree;
        inode_add_dentry(dentry, dentry->d_inode);
        if (ret != 0)
                goto out_free_dentry_tree;
        inode_add_dentry(dentry, dentry->d_inode);