struct dentry optimization and stack-based rbtree traversal
authorEric Biggers <ebiggers3@gmail.com>
Sun, 11 Nov 2012 22:47:57 +0000 (16:47 -0600)
committerEric Biggers <ebiggers3@gmail.com>
Sun, 11 Nov 2012 22:47:57 +0000 (16:47 -0600)
src/dentry.c
src/dentry.h

index 634e4de..9306212 100644 (file)
@@ -253,42 +253,60 @@ int inode_to_stbuf(const struct inode *inode, struct lookup_table_entry *lte,
 }
 #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;
-       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;
-       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,
index 1e8724c..a68f075 100644 (file)
@@ -128,14 +128,55 @@ static inline bool ads_entries_have_same_name(const struct ads_entry *entry_1,
  * hardlink.c).
  */
 struct dentry {
+       /* Byte 0 */
+
        /* 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;
 
+       /* 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.
@@ -156,48 +197,26 @@ struct dentry {
         */
        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;
 
-       /* 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;
 
-       /* Pointer to the filename (malloc()ed buffer). */
+       /* Pointer to the UTF-16 filename (malloc()ed buffer). */
        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;
-
-       /* 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)