From 4f2e79ad50660aaaf439867a95165ce1426a8a56 Mon Sep 17 00:00:00 2001 From: Eric Biggers Date: Sat, 22 Mar 2014 19:06:54 -0500 Subject: [PATCH] Transition wimlib to AVL tree code --- include/wimlib/dentry.h | 72 +++++---- include/wimlib/inode.h | 24 +-- include/wimlib/security.h | 12 +- src/dentry.c | 327 +++++++++++++++++++++----------------- src/extract.c | 6 +- src/ntfs-3g_capture.c | 92 +++++------ src/security.c | 73 ++++----- src/update_image.c | 7 +- 8 files changed, 326 insertions(+), 287 deletions(-) diff --git a/include/wimlib/dentry.h b/include/wimlib/dentry.h index 6e58fd21..d0d1d0f5 100644 --- a/include/wimlib/dentry.h +++ b/include/wimlib/dentry.h @@ -1,11 +1,11 @@ #ifndef _WIMLIB_DENTRY_H #define _WIMLIB_DENTRY_H +#include "wimlib/avl_tree.h" #include "wimlib/case.h" #include "wimlib/compiler.h" #include "wimlib/inode.h" #include "wimlib/list.h" -#include "wimlib/rbtree.h" #include "wimlib/types.h" struct wim_inode; @@ -52,17 +52,17 @@ struct wim_dentry { * to all dentries in a hard link group. */ struct wim_inode *d_inode; - /* Node for the parent's red-black tree of child dentries, sorted by - * case sensitive long name. */ - struct rb_node rb_node; + /* Node for the parent's balanced binary search tree of child dentries + * sorted by case sensitive long name (root i_children). */ + struct avl_tree_node d_index_node; - /* Node for the parent's red-black tree of child dentries, sorted by - * case insensitive long name. */ - struct rb_node rb_node_case_insensitive; + /* Node for the parent's balanced binary search tree of child dentries, + * sorted by case insensitive long name (root i_children_ci). */ + struct avl_tree_node d_index_node_ci; /* List of dentries in a directory that have different case sensitive - * long names but share the same case insensitive long name */ - struct list_head case_insensitive_conflict_list; + * long names but share the same case insensitive long name. */ + struct list_head d_ci_conflict_list; /* Length of UTF-16LE encoded short filename, in bytes, not including * the terminating zero wide-character. */ @@ -137,8 +137,6 @@ struct wim_dentry { size_t extraction_name_nchars; }; -#define rbnode_dentry(node) container_of(node, struct wim_dentry, rb_node) - static inline bool dentry_is_first_in_inode(const struct wim_dentry *dentry) { @@ -158,32 +156,47 @@ 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, +/* Iterate through each @child dentry of the @dir directory inode, * in sorted order (by case sensitive name). */ -#define for_inode_child(child, parent) \ - for (struct rb_node *_tmp = rb_first(&parent->i_children); \ +#define for_inode_child(child, dir) \ + for (struct avl_tree_node *_tmp = \ + avl_tree_first_in_order((dir)->i_children); \ _tmp && \ - ((child = rb_entry(_tmp, struct wim_dentry, rb_node)), 1); \ - _tmp = rb_next(_tmp)) + (((child) = avl_tree_entry(_tmp, struct wim_dentry, \ + d_index_node)), 1); \ + _tmp = avl_tree_next_in_order(_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)) + for_inode_child((child), (parent)->d_inode) + +/* Iterate through each @child dentry of the @dir directory inode, + * in postorder (safe for freeing the child dentries). */ +#define for_inode_child_postorder(child, dir) \ + for (struct avl_tree_node *_parent, *_tmp = \ + avl_tree_first_in_postorder( \ + (dir)->i_children); \ + _tmp && \ + (((child) = avl_tree_entry(_tmp, struct wim_dentry, \ + d_index_node)), 1) && \ + ((_parent = avl_get_parent(_tmp)), 1); \ + _tmp = avl_tree_next_in_postorder(_tmp, _parent)) /* Iterate through each @child dentry of the @parent dentry, - * in postorder (safe for freeing). */ + * in postorder (safe for freeing the child dentries). */ #define for_dentry_child_postorder(child, parent) \ - for_inode_child_postorder(child, parent->d_inode) + for_inode_child_postorder((child), (parent)->d_inode) + +/* Get any child dentry of the @dir directory inode. Requires + * inode_has_children(@dir) == true. */ +#define inode_any_child(dir) \ + avl_tree_entry((dir)->i_children, struct wim_dentry, d_index_node) + +/* Get any child dentry of the @parent dentry. Requires + * dentry_has_children(@parent) == true. */ +#define dentry_any_child(parent) \ + inode_any_child((parent)->d_inode) extern void calculate_subdir_offsets(struct wim_dentry *root, u64 *subdir_offset_p); @@ -262,8 +275,7 @@ extern void unlink_dentry(struct wim_dentry *dentry); extern struct wim_dentry * -dentry_add_child(struct wim_dentry * restrict parent, - struct wim_dentry * restrict child); +dentry_add_child(struct wim_dentry *parent, struct wim_dentry *child); extern int rename_wim_path(WIMStruct *wim, const tchar *from, const tchar *to, diff --git a/include/wimlib/inode.h b/include/wimlib/inode.h index c869f841..e2bc46fe 100644 --- a/include/wimlib/inode.h +++ b/include/wimlib/inode.h @@ -4,7 +4,6 @@ #include "wimlib/assert.h" #include "wimlib/list.h" #include "wimlib/lookup_table.h" -#include "wimlib/rbtree.h" #include "wimlib/sha1.h" #include "wimlib/unix_data.h" @@ -15,6 +14,7 @@ struct wim_dentry; struct wim_security_data; struct wim_lookup_table; struct wimfs_fd; +struct avl_tree_node; /* * WIM inode. @@ -47,13 +47,17 @@ struct wim_inode { * this inode. */ u32 i_attributes; - /* Root of a red-black tree storing the child dentries of this inode, if - * any. Keyed by wim_dentry->file_name, case sensitively. */ - struct rb_root i_children; + /* Root of a balanced binary search tree storing the child directory + * entries of this inode, if any. Keyed by wim_dentry->file_name, case + * sensitively. If this inode is not a directory or if it has no + * children then this will be an empty tree (NULL). */ + struct avl_tree_node *i_children; - /* Root of a red-black tree storing the children of this inode, if any. - * Keyed by wim_dentry->file_name, case insensitively. */ - struct rb_root i_children_case_insensitive; + /* Root of a balanced binary search tree storing the child directory + * entries of this inode, if any. Keyed by wim_dentry->file_name, case + * insensitively. If this inode is not a directory or if it has no + * children then this will be an empty tree (NULL). */ + struct avl_tree_node *i_children_ci; /* List of dentries that are aliases for this inode. There will be * i_nlink dentries in this list. */ @@ -382,12 +386,12 @@ inode_is_symlink(const struct wim_inode *inode) /* Does the inode have children? * Currently (based on read_dentry_tree()), this can only return true for inodes - * for which inode_is_directory() returns true. However, if a directory is - * empty, this returns false. */ + * for which inode_is_directory() returns true. (This also returns false on + * empty directories.) */ static inline bool inode_has_children(const struct wim_inode *inode) { - return !rb_empty_root(&inode->i_children); + return inode->i_children != NULL; } extern int diff --git a/include/wimlib/security.h b/include/wimlib/security.h index 71ffb695..8043d7d2 100644 --- a/include/wimlib/security.h +++ b/include/wimlib/security.h @@ -1,15 +1,17 @@ #ifndef _WIMLIB_SECURITY_H #define _WIMLIB_SECURITY_H -#include "wimlib/rbtree.h" #include "wimlib/types.h" -/* Red-black tree that maps SHA1 message digests of security descriptors to - * security IDs, which are themselves indices into the table of security - * descriptors in the 'struct wim_security_data'. */ +struct wim_security_data; +struct avl_tree_node; + +/* Map from SHA1 message digests of security descriptors to security IDs, which + * are themselves indices into the table of security descriptors in the 'struct + * wim_security_data'. */ struct wim_sd_set { struct wim_security_data *sd; - struct rb_root rb_root; + struct avl_tree_node *root; int32_t orig_num_entries; }; diff --git a/src/dentry.c b/src/dentry.c index 59e97572..d425b280 100644 --- a/src/dentry.c +++ b/src/dentry.c @@ -487,6 +487,7 @@ calculate_subdir_offsets(struct wim_dentry *root, u64 *subdir_offset_p) for_dentry_in_tree(root, dentry_calculate_subdir_offset, subdir_offset_p); } +/* Compare the UTF-16LE long filenames of two dentries case insensitively. */ static int dentry_compare_names_case_insensitive(const struct wim_dentry *d1, const struct wim_dentry *d2) @@ -498,6 +499,7 @@ dentry_compare_names_case_insensitive(const struct wim_dentry *d1, true); } +/* Compare the UTF-16LE long filenames of two dentries case sensitively. */ static int dentry_compare_names_case_sensitive(const struct wim_dentry *d1, const struct wim_dentry *d2) @@ -509,6 +511,28 @@ dentry_compare_names_case_sensitive(const struct wim_dentry *d1, false); } +static int +_avl_dentry_compare_names_ci(const struct avl_tree_node *n1, + const struct avl_tree_node *n2) +{ + const struct wim_dentry *d1, *d2; + + d1 = avl_tree_entry(n1, struct wim_dentry, d_index_node_ci); + d2 = avl_tree_entry(n2, struct wim_dentry, d_index_node_ci); + return dentry_compare_names_case_insensitive(d1, d2); +} + +static int +_avl_dentry_compare_names(const struct avl_tree_node *n1, + const struct avl_tree_node *n2) +{ + const struct wim_dentry *d1, *d2; + + d1 = avl_tree_entry(n1, struct wim_dentry, d_index_node); + d2 = avl_tree_entry(n2, struct wim_dentry, d_index_node); + return dentry_compare_names_case_sensitive(d1, d2); +} + /* Default case sensitivity behavior for searches with * WIMLIB_CASE_PLATFORM_DEFAULT specified. This can be modified by * wimlib_global_init(). */ @@ -520,6 +544,36 @@ bool default_ignore_case = #endif ; +/* Case-sensitive dentry lookup. Only @file_name and @file_name_nbytes of + * @dummy must be valid. */ +static struct wim_dentry * +dir_lookup(const struct wim_inode *dir, const struct wim_dentry *dummy) +{ + struct avl_tree_node *node; + + node = avl_tree_lookup_node(dir->i_children, + &dummy->d_index_node, + _avl_dentry_compare_names); + if (!node) + return NULL; + return avl_tree_entry(node, struct wim_dentry, d_index_node); +} + +/* Case-insensitive dentry lookup. Only @file_name and @file_name_nbytes of + * @dummy must be valid. */ +static struct wim_dentry * +dir_lookup_ci(const struct wim_inode *dir, const struct wim_dentry *dummy) +{ + struct avl_tree_node *node; + + node = avl_tree_lookup_node(dir->i_children_ci, + &dummy->d_index_node_ci, + _avl_dentry_compare_names_ci); + if (!node) + return NULL; + return avl_tree_entry(node, struct wim_dentry, d_index_node_ci); +} + /* Given a UTF-16LE filename and a directory, look up the dentry for the file. * Return it if found, otherwise NULL. This is case-sensitive on UNIX and * case-insensitive on Windows. */ @@ -529,68 +583,52 @@ get_dentry_child_with_utf16le_name(const struct wim_dentry *dentry, size_t name_nbytes, CASE_SENSITIVITY_TYPE case_ctype) { - struct rb_node *node; - + const struct wim_inode *dir = dentry->d_inode; bool ignore_case = will_ignore_case(case_ctype); + struct wim_dentry dummy; + struct wim_dentry *child; - if (ignore_case) - node = dentry->d_inode->i_children_case_insensitive.rb_node; - else - node = dentry->d_inode->i_children.rb_node; + dummy.file_name = (utf16lechar*)name; + dummy.file_name_nbytes = name_nbytes; - struct wim_dentry *child; - while (node) { - if (ignore_case) - child = rb_entry(node, struct wim_dentry, rb_node_case_insensitive); - else - child = rb_entry(node, struct wim_dentry, rb_node); - - int result = cmp_utf16le_strings(name, - name_nbytes / 2, - child->file_name, - child->file_name_nbytes / 2, - ignore_case); - if (result < 0) { - node = node->rb_left; - } else if (result > 0) { - node = node->rb_right; - } else if (!ignore_case || - list_empty(&child->case_insensitive_conflict_list)) { - return child; - } else { - /* Multiple dentries have the same case-insensitive - * name, and a case-insensitive lookup is being - * performed. Choose the dentry with the same - * case-sensitive name, if one exists; otherwise print a - * warning and choose one arbitrarily. */ - struct wim_dentry *alt = child; - size_t num_alts = 0; - - do { - num_alts++; - if (0 == cmp_utf16le_strings(name, - name_nbytes / 2, - alt->file_name, - alt->file_name_nbytes / 2, - false)) - return alt; - alt = list_entry(alt->case_insensitive_conflict_list.next, - struct wim_dentry, - case_insensitive_conflict_list); - } while (alt != child); - - WARNING("Result of case-insensitive lookup is ambiguous\n" - " (returning \"%"TS"\" of %zu " - "possible files, including \"%"TS"\")", - dentry_full_path(child), - num_alts, - dentry_full_path(list_entry(child->case_insensitive_conflict_list.next, - struct wim_dentry, - case_insensitive_conflict_list))); - return child; - } - } - return NULL; + if (!ignore_case) + /* Case-sensitive lookup. */ + return dir_lookup(dir, &dummy); + + /* Case-insensitive lookup. */ + + child = dir_lookup_ci(dir, &dummy); + if (!child) + return NULL; + + if (likely(list_empty(&child->d_ci_conflict_list))) + /* Only one dentry has this case-insensitive name; return it */ + return child; + + /* Multiple dentries have the same case-insensitive name. Choose the + * dentry with the same case-sensitive name, if one exists; otherwise + * print a warning and choose one of the possible dentries arbitrarily. + */ + struct wim_dentry *alt = child; + size_t num_alts = 0; + + do { + num_alts++; + if (!dentry_compare_names_case_sensitive(&dummy, alt)) + return alt; + alt = list_entry(alt->d_ci_conflict_list.next, + struct wim_dentry, d_ci_conflict_list); + } while (alt != child); + + WARNING("Result of case-insensitive lookup is ambiguous\n" + " (returning \"%"TS"\" of %zu " + "possible files, including \"%"TS"\")", + dentry_full_path(child), + num_alts, + dentry_full_path(list_entry(child->d_ci_conflict_list.next, + struct wim_dentry, + d_ci_conflict_list))); + return child; } /* Returns the child of @dentry that has the file name @name. Returns NULL if @@ -1003,40 +1041,58 @@ free_dentry_tree(struct wim_dentry *root, struct wim_lookup_table *lookup_table) for_dentry_in_tree_depth(root, do_free_dentry, lookup_table); } -/* Insert a dentry into the case insensitive index for a directory. - * - * This is a red-black tree, but when multiple dentries share the same - * case-insensitive name, only one is inserted into the tree itself; the rest - * are connected in a list. - */ +/* Insert the @child dentry into the case sensitive index of the @dir directory. + * Return NULL if successfully inserted, otherwise a pointer to the + * already-inserted duplicate. */ static struct wim_dentry * -dentry_add_child_case_insensitive(struct wim_dentry *parent, - struct wim_dentry *child) +dir_index_child(struct wim_inode *dir, struct wim_dentry *child) { - struct rb_root *root; - struct rb_node **new; - struct rb_node *rb_parent; - - root = &parent->d_inode->i_children_case_insensitive; - new = &root->rb_node; - rb_parent = NULL; - while (*new) { - struct wim_dentry *this = container_of(*new, struct wim_dentry, - rb_node_case_insensitive); - int result = dentry_compare_names_case_insensitive(child, this); - - rb_parent = *new; - - if (result < 0) - new = &((*new)->rb_left); - else if (result > 0) - new = &((*new)->rb_right); - else - return this; - } - rb_link_node(&child->rb_node_case_insensitive, rb_parent, new); - rb_insert_color(&child->rb_node_case_insensitive, root); - return NULL; + struct avl_tree_node *duplicate; + + duplicate = avl_tree_insert(&dir->i_children, + &child->d_index_node, + _avl_dentry_compare_names); + if (!duplicate) + return NULL; + return avl_tree_entry(duplicate, struct wim_dentry, d_index_node); +} + +/* Insert the @child dentry into the case insensitive index of the @dir + * directory. Return NULL if successfully inserted, otherwise a pointer to the + * already-inserted duplicate. */ +static struct wim_dentry * +dir_index_child_ci(struct wim_inode *dir, struct wim_dentry *child) +{ + struct avl_tree_node *duplicate; + + duplicate = avl_tree_insert(&dir->i_children_ci, + &child->d_index_node_ci, + _avl_dentry_compare_names_ci); + if (!duplicate) + return NULL; + return avl_tree_entry(duplicate, struct wim_dentry, d_index_node_ci); +} + +/* Removes the specified dentry from its directory's case-sensitive index. */ +static void +dir_unindex_child(struct wim_inode *dir, struct wim_dentry *child) +{ + avl_tree_remove(&dir->i_children, &child->d_index_node); +} + +/* Removes the specified dentry from its directory's case-insensitive index. */ +static void +dir_unindex_child_ci(struct wim_inode *dir, struct wim_dentry *child) +{ + avl_tree_remove(&dir->i_children_ci, &child->d_index_node_ci); +} + +/* Returns true iff the specified dentry is in its parent directory's + * case-insensitive index. */ +static bool +dentry_in_ci_index(const struct wim_dentry *dentry) +{ + return !avl_tree_node_is_unlinked(&dentry->d_index_node_ci); } /* @@ -1046,84 +1102,67 @@ dentry_add_child_case_insensitive(struct wim_dentry *parent, * @child: The dentry to link. * * Returns NULL if successful. If @parent already contains a dentry with the - * same case-sensitive name as @child, the pointer to this duplicate dentry is - * returned. + * same case-sensitive name as @child, returns a pointer to this duplicate + * dentry. */ struct wim_dentry * -dentry_add_child(struct wim_dentry * restrict parent, - struct wim_dentry * restrict child) +dentry_add_child(struct wim_dentry *parent, struct wim_dentry *child) { - struct rb_root *root; - struct rb_node **new; - struct rb_node *rb_parent; + struct wim_dentry *duplicate; + struct wim_inode *dir; - wimlib_assert(dentry_is_directory(parent)); wimlib_assert(parent != child); - /* Case sensitive child dentry index */ - root = &parent->d_inode->i_children; - new = &root->rb_node; - rb_parent = NULL; - while (*new) { - struct wim_dentry *this = rbnode_dentry(*new); - int result = dentry_compare_names_case_sensitive(child, this); - - rb_parent = *new; - - if (result < 0) - new = &((*new)->rb_left); - else if (result > 0) - new = &((*new)->rb_right); - else - return this; - } - child->parent = parent; - rb_link_node(&child->rb_node, rb_parent, new); - rb_insert_color(&child->rb_node, root); + dir = parent->d_inode; - /* Case insensitive child dentry index */ - { - struct wim_dentry *existing; - existing = dentry_add_child_case_insensitive(parent, child); - if (existing) { - list_add(&child->case_insensitive_conflict_list, - &existing->case_insensitive_conflict_list); - rb_clear_node(&child->rb_node_case_insensitive); - } else { - INIT_LIST_HEAD(&child->case_insensitive_conflict_list); - } + wimlib_assert(inode_is_directory(dir)); + + duplicate = dir_index_child(dir, child); + if (duplicate) + return duplicate; + + duplicate = dir_index_child_ci(dir, child); + if (duplicate) { + list_add(&child->d_ci_conflict_list, &duplicate->d_ci_conflict_list); + avl_tree_node_set_unlinked(&child->d_index_node_ci); + } else { + INIT_LIST_HEAD(&child->d_ci_conflict_list); } + child->parent = parent; return NULL; } -/* Unlink a WIM dentry from the directory entry tree. */ +/* Unlink a WIM dentry from the directory entry tree. */ void unlink_dentry(struct wim_dentry *dentry) { - struct wim_dentry *parent = dentry->parent; + struct wim_inode *dir; - if (parent == dentry) + if (dentry_is_root(dentry)) return; - rb_erase(&dentry->rb_node, &parent->d_inode->i_children); - 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); - if (!list_empty(&dentry->case_insensitive_conflict_list)) { + dir = dentry->parent->d_inode; + + dir_unindex_child(dir, dentry); + + if (dentry_in_ci_index(dentry)) { + + dir_unindex_child_ci(dir, dentry); + + if (!list_empty(&dentry->d_ci_conflict_list)) { /* Make a different case-insensitively-the-same dentry - * be the "representative" in the red-black tree. */ + * be the "representative" in the search index. */ struct list_head *next; struct wim_dentry *other; struct wim_dentry *existing; - next = dentry->case_insensitive_conflict_list.next; - other = list_entry(next, struct wim_dentry, case_insensitive_conflict_list); - existing = dentry_add_child_case_insensitive(parent, other); + next = dentry->d_ci_conflict_list.next; + other = list_entry(next, struct wim_dentry, d_ci_conflict_list); + existing = dir_index_child_ci(dir, other); wimlib_assert(existing == NULL); } } - list_del(&dentry->case_insensitive_conflict_list); + list_del(&dentry->d_ci_conflict_list); } static int diff --git a/src/extract.c b/src/extract.c index 9cbac117..8331001f 100644 --- a/src/extract.c +++ b/src/extract.c @@ -6,7 +6,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. * @@ -1789,8 +1789,8 @@ dentry_calculate_extraction_name(struct wim_dentry *dentry, if (!ctx->ops->supports_case_sensitive_filenames) { struct wim_dentry *other; - list_for_each_entry(other, &dentry->case_insensitive_conflict_list, - case_insensitive_conflict_list) + list_for_each_entry(other, &dentry->d_ci_conflict_list, + d_ci_conflict_list) { if (dentry_in_list(other)) { if (ctx->extract_flags & diff --git a/src/ntfs-3g_capture.c b/src/ntfs-3g_capture.c index a0b37099..1faba226 100644 --- a/src/ntfs-3g_capture.c +++ b/src/ntfs-3g_capture.c @@ -6,7 +6,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,27 +301,35 @@ out_put_actx: return ret; } -/* Red-black tree that maps NTFS inode numbers to DOS names */ +/* Binary tree that maps NTFS inode numbers to DOS names */ struct dos_name_map { - struct rb_root rb_root; + struct avl_tree_node *root; }; struct dos_name_node { - struct rb_node rb_node; + struct avl_tree_node index_node; char dos_name[24]; int name_nbytes; le64 ntfs_ino; }; +#define DOS_NAME_NODE(avl_node) \ + avl_tree_entry(avl_node, struct dos_name_node, index_node) + +static int +_avl_cmp_by_ntfs_ino(const struct avl_tree_node *n1, + const struct avl_tree_node *n2) +{ + return cmp_u64(DOS_NAME_NODE(n1)->ntfs_ino, + DOS_NAME_NODE(n2)->ntfs_ino); +} + /* Inserts a new DOS name into the map */ static int insert_dos_name(struct dos_name_map *map, const ntfschar *dos_name, size_t name_nbytes, le64 ntfs_ino) { struct dos_name_node *new_node; - struct rb_node **p; - struct rb_root *root; - struct rb_node *rb_parent; DEBUG("DOS name_len = %zu", name_nbytes); new_node = MALLOC(sizeof(struct dos_name_node)); @@ -333,35 +341,23 @@ insert_dos_name(struct dos_name_map *map, const ntfschar *dos_name, wimlib_assert(name_nbytes <= sizeof(new_node->dos_name)); /* Initialize the DOS name, DOS name length, and NTFS inode number of - * the red-black tree node */ + * the search tree node */ memcpy(new_node->dos_name, dos_name, name_nbytes); new_node->name_nbytes = name_nbytes; new_node->ntfs_ino = ntfs_ino; - /* Insert the red-black tree node */ - root = &map->rb_root; - p = &root->rb_node; - rb_parent = NULL; - while (*p) { - struct dos_name_node *this; - - this = container_of(*p, struct dos_name_node, rb_node); - rb_parent = *p; - if (new_node->ntfs_ino < this->ntfs_ino) - p = &((*p)->rb_left); - else if (new_node->ntfs_ino > this->ntfs_ino) - p = &((*p)->rb_right); - else { - /* This should be impossible since a NTFS inode cannot - * have multiple DOS names, and we only should get each - * DOS name entry once from the ntfs_readdir() calls. */ - ERROR("NTFS inode %"PRIu64" has multiple DOS names", - le64_to_cpu(ntfs_ino)); - return -1; - } + /* Insert the search tree node */ + if (avl_tree_insert(&map->root, &new_node->index_node, + _avl_cmp_by_ntfs_ino)) + { + /* This should be impossible since a NTFS inode cannot + * have multiple DOS names, and we only should get each + * DOS name entry once from the ntfs_readdir() calls. */ + ERROR("NTFS inode %"PRIu64" has multiple DOS names", + le64_to_cpu(ntfs_ino)); + FREE(new_node); + return -1; } - rb_link_node(&new_node->rb_node, rb_parent, p); - rb_insert_color(&new_node->rb_node, root); DEBUG("Inserted DOS name for inode %"PRIu64, le64_to_cpu(ntfs_ino)); return 0; } @@ -371,18 +367,16 @@ insert_dos_name(struct dos_name_map *map, const ntfschar *dos_name, static struct dos_name_node * lookup_dos_name(const struct dos_name_map *map, u64 ntfs_ino) { - struct rb_node *node = map->rb_root.rb_node; - while (node) { - struct dos_name_node *this; - this = container_of(node, struct dos_name_node, rb_node); - if (ntfs_ino < this->ntfs_ino) - node = node->rb_left; - else if (ntfs_ino > this->ntfs_ino) - node = node->rb_right; - else - return this; - } - return NULL; + struct dos_name_node dummy; + struct avl_tree_node *res; + + dummy.ntfs_ino = cpu_to_le64(ntfs_ino); + + res = avl_tree_lookup_node(map->root, &dummy.index_node, + _avl_cmp_by_ntfs_ino); + if (!res) + return NULL; + return DOS_NAME_NODE(res); } static int @@ -412,18 +406,18 @@ set_dentry_dos_name(struct wim_dentry *dentry, const struct dos_name_map *map) } static void -free_dos_name_tree(struct rb_node *node) { +free_dos_name_tree(struct avl_tree_node *node) { if (node) { - free_dos_name_tree(node->rb_left); - free_dos_name_tree(node->rb_right); - FREE(container_of(node, struct dos_name_node, rb_node)); + free_dos_name_tree(node->left); + free_dos_name_tree(node->right); + FREE(DOS_NAME_NODE(node)); } } static void destroy_dos_name_map(struct dos_name_map *map) { - free_dos_name_tree(map->rb_root.rb_node); + free_dos_name_tree(map->root); } struct readdir_ctx { @@ -611,7 +605,7 @@ build_dentry_tree_ntfs_recursive(struct wim_dentry **root_ret, /* Recurse to directory children */ s64 pos = 0; - struct dos_name_map dos_name_map = { .rb_root = {.rb_node = NULL} }; + struct dos_name_map dos_name_map = { .root = NULL }; struct readdir_ctx ctx = { .parent = root, .path = path, diff --git a/src/security.c b/src/security.c index cac61917..a930ca2a 100644 --- a/src/security.c +++ b/src/security.c @@ -5,7 +5,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. * @@ -28,6 +28,7 @@ #endif #include "wimlib/assert.h" +#include "wimlib/avl_tree.h" #include "wimlib/endianness.h" #include "wimlib/error.h" #include "wimlib/security.h" @@ -232,16 +233,19 @@ free_wim_security_data(struct wim_security_data *sd) struct sd_node { int security_id; u8 hash[SHA1_HASH_SIZE]; - struct rb_node rb_node; + struct avl_tree_node index_node; }; +#define SD_NODE(avl_node) \ + avl_tree_entry(avl_node, struct sd_node, index_node) + static void -free_sd_tree(struct rb_node *node) +free_sd_tree(struct avl_tree_node *node) { if (node) { - free_sd_tree(node->rb_left); - free_sd_tree(node->rb_right); - FREE(container_of(node, struct sd_node, rb_node)); + free_sd_tree(node->left); + free_sd_tree(node->right); + FREE(SD_NODE(node)); } } @@ -257,32 +261,23 @@ destroy_sd_set(struct wim_sd_set *sd_set, bool rollback) FREE(*descriptors++); sd->num_entries = sd_set->orig_num_entries; } - free_sd_tree(sd_set->rb_root.rb_node); + free_sd_tree(sd_set->root); } -/* Inserts a a new node into the security descriptor index tree. */ +static int +_avl_cmp_nodes_by_hash(const struct avl_tree_node *n1, + const struct avl_tree_node *n2) +{ + return hashes_cmp(SD_NODE(n1)->hash, SD_NODE(n2)->hash); +} + +/* Inserts a a new node into the security descriptor index tree. Returns true + * if successful (not a duplicate). */ static bool insert_sd_node(struct wim_sd_set *set, struct sd_node *new) { - struct rb_root *root = &set->rb_root; - struct rb_node **p = &(root->rb_node); - struct rb_node *rb_parent = NULL; - - while (*p) { - struct sd_node *this = container_of(*p, struct sd_node, rb_node); - int cmp = hashes_cmp(new->hash, this->hash); - - rb_parent = *p; - if (cmp < 0) - p = &((*p)->rb_left); - else if (cmp > 0) - p = &((*p)->rb_right); - else - return false; /* Duplicate security descriptor */ - } - rb_link_node(&new->rb_node, rb_parent, p); - rb_insert_color(&new->rb_node, root); - return true; + return NULL == avl_tree_insert(&set->root, &new->index_node, + _avl_cmp_nodes_by_hash); } /* Returns the index of the security descriptor having a SHA1 message digest of @@ -290,19 +285,15 @@ insert_sd_node(struct wim_sd_set *set, struct sd_node *new) static int lookup_sd(struct wim_sd_set *set, const u8 hash[SHA1_HASH_SIZE]) { - struct rb_node *node = set->rb_root.rb_node; - - while (node) { - struct sd_node *sd_node = container_of(node, struct sd_node, rb_node); - int cmp = hashes_cmp(hash, sd_node->hash); - if (cmp < 0) - node = node->rb_left; - else if (cmp > 0) - node = node->rb_right; - else - return sd_node->security_id; - } - return -1; + struct avl_tree_node *res; + struct sd_node dummy; + + copy_hash(dummy.hash, hash); + res = avl_tree_lookup_node(set->root, &dummy.index_node, + _avl_cmp_nodes_by_hash); + if (!res) + return -1; + return SD_NODE(res)->security_id; } /* @@ -383,7 +374,7 @@ init_sd_set(struct wim_sd_set *sd_set, struct wim_security_data *sd) int ret; sd_set->sd = sd; - sd_set->rb_root.rb_node = NULL; + sd_set->root = NULL; /* Remember the original number of security descriptors so that newly * added ones can be rolled back if needed. */ diff --git a/src/update_image.c b/src/update_image.c index 5a5ae690..7d2d531c 100644 --- a/src/update_image.c +++ b/src/update_image.c @@ -42,8 +42,6 @@ static int do_overlay(struct wim_dentry *target, struct wim_dentry *branch) { - struct rb_root *rb_root; - DEBUG("Doing overlay \"%"WS"\" => \"%"WS"\"", branch->file_name, target->file_name); @@ -53,10 +51,9 @@ do_overlay(struct wim_dentry *target, struct wim_dentry *branch) return WIMLIB_ERR_INVALID_OVERLAY; } - rb_root = &branch->d_inode->i_children; LIST_HEAD(moved_children); - while (rb_root->rb_node) { /* While @branch has children... */ - struct wim_dentry *child = rbnode_dentry(rb_root->rb_node); + while (dentry_has_children(branch)) { + struct wim_dentry *child = dentry_any_child(branch); struct wim_dentry *existing; /* Move @child to the directory @target */ -- 2.43.0