Transition wimlib to AVL tree code

diff --git a/include/wimlib/dentry.h b/include/wimlib/dentry.h
index 6e58fd21ea07f6314bd04c7c2408477d153794f1..d0d1d0f5eced657a8787717c559532612063b73a 100644 (file)
--- a/include/wimlib/dentry.h
+++ b/include/wimlib/dentry.h
@@ -1,11 +1,11 @@
 #ifndef _WIMLIB_DENTRY_H
 #define _WIMLIB_DENTRY_H
 
 #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/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;
 #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;
 
         * 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
 
        /* 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. */
 
        /* 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;
 };
 
        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)
 {
 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);
 
                         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).  */
  * 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 &&                                                            \
             _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) \
 
 /* 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,
 
 /* 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) \
 #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);
 
 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 *
 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,
 
 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 c869f8417561500ad2227458110375be65636de2..e2bc46fe7f6163531847af9c1ae8bc91c500142c 100644 (file)
--- 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/assert.h"
 #include "wimlib/list.h"
 #include "wimlib/lookup_table.h"

-#include "wimlib/rbtree.h"

 #include "wimlib/sha1.h"
 #include "wimlib/unix_data.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 wim_security_data;
 struct wim_lookup_table;
 struct wimfs_fd;

+struct avl_tree_node;

 
 /*
  * WIM inode.
 
 /*
  * WIM inode.


@@ -47,13 +47,17 @@ struct wim_inode {
         * this inode. */
        u32 i_attributes;
 
         * 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.  */
 
        /* 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
 
 /* 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)
 {
 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
 }
 
 extern int

diff --git a/include/wimlib/security.h b/include/wimlib/security.h
index 71ffb695b379d0cc98dd7a9605ea2c48dab08d13..8043d7d2c8e87534ed1e546928359b214dd2f53b 100644 (file)
--- a/include/wimlib/security.h
+++ b/include/wimlib/security.h
@@ -1,15 +1,17 @@
 #ifndef _WIMLIB_SECURITY_H
 #define _WIMLIB_SECURITY_H
 
 #ifndef _WIMLIB_SECURITY_H
 #define _WIMLIB_SECURITY_H
 

-#include "wimlib/rbtree.h"

 #include "wimlib/types.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 wim_sd_set {
        struct wim_security_data *sd;

-       struct rb_root rb_root;
+       struct avl_tree_node *root;

        int32_t orig_num_entries;
 };
 
        int32_t orig_num_entries;
 };
 

diff --git a/src/dentry.c b/src/dentry.c
index 59e97572bc0c49e538dc43e2306bf24ed16b9f5e..d425b2801a29e3c89dbe1322672a7e49a7923322 100644 (file)
--- 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);
 }
 
        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)
 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);
 }
 
                                   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)
 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);
 }
 
                                   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().  */
 /* 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
 ;
 
 #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. */
 /* 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)
 {
                                   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);
        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
 }
 
 /* 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);
 }
 
        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 *
 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
  * @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 *
  */
 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);
 
        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;
 }
 
        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)
 {
 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;
                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
                        /* 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;
 
                        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);
                }
        }
                        wimlib_assert(existing == NULL);
                }
        }

-       list_del(&dentry->case_insensitive_conflict_list);
+       list_del(&dentry->d_ci_conflict_list);

 }
 
 static int
 }
 
 static int

diff --git a/src/extract.c b/src/extract.c
index 9cbac117f54438d25372c90cb43dd4df4c327bb5..8331001fa4b54fd54d8edb16bf2d212aabea0041 100644 (file)
--- 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.
  *
  *
  * 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;
        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 &
                {
                        if (dentry_in_list(other)) {
                                if (ctx->extract_flags &

diff --git a/src/ntfs-3g_capture.c b/src/ntfs-3g_capture.c
index a0b370998e939bd4ca640284b1e6ae2c077f6698..1faba226c5d05104dd4fee1b14d9deb17d62ee34 100644 (file)
--- 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.
  *
  *
  * This file is part of wimlib, a library for working with WIM files.
  *


@@ -301,27 +301,35 @@ out_put_actx:
        return ret;
 }
 
        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 dos_name_map {

-       struct rb_root rb_root;
+       struct avl_tree_node *root;

 };
 
 struct dos_name_node {
 };
 
 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;
 };
 
        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;
 /* 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));
 
        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
        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;
 
        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;
 }
        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)
 {
 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
 }
 
 static int


@@ -412,18 +406,18 @@ set_dentry_dos_name(struct wim_dentry *dentry, const struct dos_name_map *map)
 }
 
 static void
 }
 
 static void

-free_dos_name_tree(struct rb_node *node) {
+free_dos_name_tree(struct avl_tree_node *node) {

        if (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)
 {
        }
 }
 
 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 {
 }
 
 struct readdir_ctx {


@@ -611,7 +605,7 @@ build_dentry_tree_ntfs_recursive(struct wim_dentry **root_ret,
 
                /* Recurse to directory children */
                s64 pos = 0;
 
                /* 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,
                struct readdir_ctx ctx = {
                        .parent          = root,
                        .path            = path,

diff --git a/src/security.c b/src/security.c
index cac61917653157e8b67761816416c1f9c9b4a5d2..a930ca2ad16cd6e541929ed9bef67e97805f5932 100644 (file)
--- 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.
  *
  *
  * This file is part of wimlib, a library for working with WIM files.
  *


@@ -28,6 +28,7 @@
 #endif
 
 #include "wimlib/assert.h"
 #endif
 
 #include "wimlib/assert.h"

+#include "wimlib/avl_tree.h"

 #include "wimlib/endianness.h"
 #include "wimlib/error.h"
 #include "wimlib/security.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 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
 static void

-free_sd_tree(struct rb_node *node)
+free_sd_tree(struct avl_tree_node *node)

 {
        if (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(*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)
 {
 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
 }
 
 /* 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])
 {
 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;
        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. */
 
        /* 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 5a5ae69066f590f119fed933296a410c545be2bc..7d2d531c506b079d6c4738430ea5a6e4006c2e8b 100644 (file)
--- 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)
 {
 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);
 
        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;
        }
 
                return WIMLIB_ERR_INVALID_OVERLAY;
        }
 

-       rb_root = &branch->d_inode->i_children;

        LIST_HEAD(moved_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 */
                struct wim_dentry *existing;
 
                /* Move @child to the directory @target */