From 00ae9e9cf11e1f7a108b63db0fc538180a81880a Mon Sep 17 00:00:00 2001 From: Eric Biggers Date: Fri, 21 Mar 2014 15:23:32 -0500 Subject: [PATCH] Nonrecursive for_dentry_child() --- include/wimlib/dentry.h | 42 ++++--- include/wimlib/inode.h | 2 +- include/wimlib/rbtree.h | 108 +++++++++++------ src/dentry.c | 251 +++++++++++----------------------------- src/iterate_dir.c | 38 ++---- src/mount_image.c | 60 ++++------ src/ntfs-3g_capture.c | 13 ++- src/rbtree.c | 211 ++++++++++++++++++--------------- src/wildcard.c | 14 ++- 9 files changed, 342 insertions(+), 397 deletions(-) diff --git a/include/wimlib/dentry.h b/include/wimlib/dentry.h index 91406931..6e58fd21 100644 --- a/include/wimlib/dentry.h +++ b/include/wimlib/dentry.h @@ -153,23 +153,40 @@ for_dentry_in_tree(struct wim_dentry *root, int (*visitor)(struct wim_dentry*, void*), 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) diff --git a/include/wimlib/inode.h b/include/wimlib/inode.h index 5d04427f..c869f841 100644 --- a/include/wimlib/inode.h +++ b/include/wimlib/inode.h @@ -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 diff --git a/include/wimlib/rbtree.h b/include/wimlib/rbtree.h index bdb209dc..3ae97a55 100644 --- a/include/wimlib/rbtree.h +++ b/include/wimlib/rbtree.h @@ -1,39 +1,31 @@ /* - Red Black Trees - (C) 1999 Andrea Arcangeli - - 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 + * + * 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 #include +#include 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 */ diff --git a/src/dentry.c b/src/dentry.c index 3783434c..59e97572 100644 --- a/src/dentry.c +++ b/src/dentry.c @@ -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; } diff --git a/src/iterate_dir.c b/src/iterate_dir.c index cc5c63b8..977a6e60 100644 --- a/src/iterate_dir.c +++ b/src/iterate_dir.c @@ -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); diff --git a/src/mount_image.c b/src/mount_image.c index 9dcfe9ee..a7dc82a1 100644 --- a/src/mount_image.c +++ b/src/mount_image.c @@ -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; } diff --git a/src/ntfs-3g_capture.c b/src/ntfs-3g_capture.c index 11cbc9dd..a0b37099 100644 --- a/src/ntfs-3g_capture.c +++ b/src/ntfs-3g_capture.c @@ -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) diff --git a/src/rbtree.c b/src/rbtree.c index 10d1dc7c..5adbada4 100644 --- a/src/rbtree.c +++ b/src/rbtree.c @@ -1,24 +1,22 @@ /* - Red Black Trees - (C) 1999 Andrea Arcangeli - (C) 2002 David Woodhouse - (C) 2012 Michel Lespinasse - - 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 + * Copyright (C) 2002 David Woodhouse + * Copyright (C) 2012 Michel Lespinasse + * + * 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 @@ -48,16 +46,10 @@ * 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; } diff --git a/src/wildcard.c b/src/wildcard.c index 90efbd33..7898690a 100644 --- a/src/wildcard.c +++ b/src/wildcard.c @@ -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, -- 2.43.0