Replace red-black tree code with AVL tree code

[wimlib] / include / wimlib / dentry.h

diff --git a/include/wimlib/dentry.h b/include/wimlib/dentry.h
index b1fba029233396cf69eb1a4640c4482a08430c89..6e58fd21ea07f6314bd04c7c2408477d153794f1 100644 (file)
--- a/include/wimlib/dentry.h
+++ b/include/wimlib/dentry.h
@@ -76,17 +76,6 @@ struct wim_dentry {
         * including the terminating null character. */
        u32 full_path_nbytes;
 
-       /* For extraction operations, this flag will be set on dentries in the
-        * tree being extracted.  Otherwise this will always be 0.  */
-       u8 in_extraction_tree : 1;
-
-       /* For extraction operations, this flag will be set when a dentry in the
-        * tree being extracted is not being extracted for some reason (file
-        * type not supported by target filesystem, contains invalid characters,
-        * or not in one of the multiple sub-trees being extracted).  Otherwise
-        * this will always be 0.  */
-       u8 extraction_skipped : 1;
-
        /* During extraction extractions, this flag will be set after the
         * "skeleton" of the dentry has been extracted.  */
        u8 skeleton_extracted : 1;
@@ -97,21 +86,19 @@ struct wim_dentry {
         * always be 0.  */
        u8 is_win32_name : 1;
 
-       /* When verifying the dentry tree after reading it into memory, this
-        * flag will be set on all dentries in a hard link group that have a
-        * nonempty DOS name except one.  This is because it is supposed to be
-        * illegal (on NTFS, at least) for a single inode to have multiple DOS
-        * names.  */
-       u8 dos_name_invalid : 1;
-
+       /* Temporary flag; always reset to 0 when done using.  */
        u8 tmp_flag : 1;
 
-       u8 was_hardlinked : 1;
+       /* Set to 1 if this name was extracted as a link, so no streams need to
+        * be extracted to it.  */
+       u8 was_linked : 1;
 
-       /* Temporary list field used to make lists of dentries in a few places.
-        * */
+       /* Temporary list field  */
        struct list_head tmp_list;
 
+       /* Links list of dentries being extracted  */
+       struct list_head extraction_list;
+
        /* Linked list node that places this dentry in the list of aliases for
         * its inode (d_inode) */
        struct list_head d_alias;
@@ -125,12 +112,6 @@ struct wim_dentry {
        u64 length;
        u64 subdir_offset;
 
-       /* These correspond to the two unused fields in the on-disk WIM dentry;
-        * we read them into memory so we can write them unchanged.  These
-        * fields are set to 0 on new dentries.  */
-       u64 d_unused_1;
-       u64 d_unused_2;
-
        /* Pointer to the UTF-16LE short filename (malloc()ed buffer), or NULL
         * if this dentry has no short name.  */
        utf16lechar *short_name;
@@ -172,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);
@@ -226,12 +224,6 @@ wim_pathname_to_stream(WIMStruct *wim,
                       u16 *stream_idx_ret);
 #endif
 
-extern int
-print_dentry(struct wim_dentry *dentry, void *lookup_table);
-
-extern int
-print_dentry_full_path(struct wim_dentry *entry, void *ignore);
-
 extern int
 calculate_dentry_full_path(struct wim_dentry *dentry);
 
@@ -283,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)