struct dentry optimization and stack-based rbtree traversal

diff --git a/src/dentry.c b/src/dentry.c
index 634e4def83e74d605f6306a4754acab08b119918..9306212d82cf4ffef0bec7ca8dbce2ab310efe6c 100644 (file)
--- a/src/dentry.c
+++ b/src/dentry.c
@@ -253,42 +253,60 @@ 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 for_dentry_in_rbtree(struct rb_node *root,

                         int (*visitor)(struct dentry *, void *),
                         void *arg)
 {
        int ret;
                         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;
+       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 = visitor(dentry, arg);
+                       if (ret != 0)
+                               return ret;
+                       node = dentry->rb_node.rb_right;
+               }

        }
        }

-       return 0;

 }
 
 }
 

-int for_dentry_tree_in_rbtree(struct rb_node *node,
+int for_dentry_tree_in_rbtree(struct rb_node *root,

                              int (*visitor)(struct dentry*, void*),
                              void *arg)
 {
        int ret;
                              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;
+       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;
+               }

        }
        }

-       return 0;

 }
 
 static int for_dentry_tree_in_rbtree_depth(struct rb_node *node,
 }
 
 static int for_dentry_tree_in_rbtree_depth(struct rb_node *node,

diff --git a/src/dentry.h b/src/dentry.h
index 1e8724cbc973e9665b24321a1297f96aeaa10f69..a68f07530930f321999f015b7c572a5c6a3cad1f 100644 (file)
--- a/src/dentry.h
+++ b/src/dentry.h
@@ -128,14 +128,55 @@ static inline bool ads_entries_have_same_name(const struct ads_entry *entry_1,
  * hardlink.c).
  */
 struct dentry {
  * hardlink.c).
  */
 struct dentry {

+       /* Byte 0 */
+

        /* The inode for this dentry */
        struct inode *d_inode;
 
        /* The inode for this dentry */
        struct inode *d_inode;
 

-       /* The parent of this directory entry. */
-       struct dentry *parent;
+       /* Byte 8 */

 
 

+       /* Red-black tree of sibling dentries */

        struct rb_node rb_node;
 
        struct rb_node rb_node;
 

+       /* Byte 32 */
+
+       /* Length of short filename, in bytes, not including the terminating
+        * zero wide-character. */
+       u16 short_name_len;
+
+       /* Length of file name, in bytes, not including the terminating zero
+        * wide-character. */
+       u16 file_name_len;
+
+       /* Length of the filename converted into UTF-8, in bytes, not including
+        * the terminating zero byte. */
+       u16 file_name_utf8_len;
+
+       u8 is_extracted : 1;
+
+       /* Byte 40 */
+
+       /* Pointer to the filename converted to UTF-8 (malloc()ed buffer). */
+       char *file_name_utf8;
+
+       /* Byte 48 */
+
+       union {
+               struct list_head tmp_list;
+               struct {
+                       void *tmp_ptr_1;
+                       void *tmp_ptr_2;
+               };
+       };
+
+       /* Byte 64 */
+
+       /* List of dentries in the inode (hard link set)  */
+       struct list_head inode_dentry_list;
+
+       /* The parent of this directory entry. */
+       struct dentry *parent;
+

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


@@ -156,48 +197,26 @@ struct dentry {
         */
        u64 length;
 
         */
        u64 length;
 

+

        /* The offset, from the start of the uncompressed WIM metadata resource
         * for this image, of this dentry's child dentries.  0 if the directory
         * entry has no children, which is the case for regular files or reparse
         * points. */
        u64 subdir_offset;
 
        /* The offset, from the start of the uncompressed WIM metadata resource
         * for this image, of this dentry's child dentries.  0 if the directory
         * entry has no children, which is the case for regular files or reparse
         * points. */
        u64 subdir_offset;
 

-       /* Length of short filename, in bytes, not including the terminating
-        * zero wide-character. */
-       u16 short_name_len;
-
-       /* Length of file name, in bytes, not including the terminating zero
-        * wide-character. */
-       u16 file_name_len;
-
-       /* Length of the filename converted into UTF-8, in bytes, not including
-        * the terminating zero byte. */
-       u16 file_name_utf8_len;
+       /* Number of references to the dentry tree itself, as in multiple
+        * WIMStructs */
+       u32 refcnt;

 
 

-       /* Pointer to the short filename (malloc()ed buffer) */
+       /* Pointer to the UTF-16 short filename (malloc()ed buffer) */

        char *short_name;
 
        char *short_name;
 

-       /* Pointer to the filename (malloc()ed buffer). */
+       /* Pointer to the UTF-16 filename (malloc()ed buffer). */

        char *file_name;
 
        char *file_name;
 

-       /* Pointer to the filename converted to UTF-8 (malloc()ed buffer). */
-       char *file_name_utf8;
-
-       /* Full path to this dentry (malloc()ed buffer). */
+       /* Full path (UTF-8) to this dentry (malloc()ed buffer). */

        char *full_path_utf8;
        u32   full_path_utf8_len;
        char *full_path_utf8;
        u32   full_path_utf8_len;

-
-       /* Number of references to the dentry tree itself, as in multiple
-        * WIMStructs */
-       u32 refcnt;
-
-       /* List of dentries in the inode (hard link set)  */
-       struct list_head inode_dentry_list;
-
-       union {
-               struct list_head tmp_list;
-               bool is_extracted;
-       };

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