From 4f54dd3f9aa8f5c30d0ae013da0e8ab7a67816e5 Mon Sep 17 00:00:00 2001 From: Eric Biggers Date: Sun, 11 Nov 2012 16:47:57 -0600 Subject: [PATCH] struct dentry optimization and stack-based rbtree traversal --- src/dentry.c | 66 ++++++++++++++++++++++++++---------------- src/dentry.h | 81 ++++++++++++++++++++++++++++++++-------------------- 2 files changed, 92 insertions(+), 55 deletions(-) diff --git a/src/dentry.c b/src/dentry.c index 634e4def..9306212d 100644 --- 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 -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, diff --git a/src/dentry.h b/src/dentry.h index 1e8724cb..a68f0753 100644 --- 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 { + /* 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) -- 2.43.0