Save memory by using a singly-linked list for extraction aliases

diff --git a/include/wimlib/apply.h b/include/wimlib/apply.h
index f9a4a2f1bec077b0f44616536fe0b2503071405c..ad21418ef5f92f6516914dff6c2ebeef5271c894 100644 (file)
--- a/include/wimlib/apply.h
+++ b/include/wimlib/apply.h
@@ -134,14 +134,13 @@ report_apply_error(struct apply_ctx *ctx, int error_code, const tchar *path)
        return report_error(ctx->progfunc, ctx->progctx, error_code, path);
 }
 
        return report_error(ctx->progfunc, ctx->progctx, error_code, path);
 }
 

-/* Returns any of the aliases of an inode that are being extracted.  */
-#define inode_first_extraction_dentry(inode)           \
-       list_first_entry(&(inode)->i_extraction_aliases,        \
-                        struct wim_dentry, d_extraction_alias_node)
+#define inode_first_extraction_dentry(inode)                           \
+       ((inode)->i_first_extraction_alias)

 
 #define inode_for_each_extraction_alias(dentry, inode)                 \
 
 #define inode_for_each_extraction_alias(dentry, inode)                 \

-       list_for_each_entry(dentry, &(inode)->i_extraction_aliases,     \
-                           d_extraction_alias_node)
+       for (dentry = inode_first_extraction_dentry(inode);             \
+            dentry != NULL;                                            \
+            dentry = dentry->d_next_extraction_alias)

 
 extern int
 extract_blob_list(struct apply_ctx *ctx, const struct read_blob_callbacks *cbs);
 
 extern int
 extract_blob_list(struct apply_ctx *ctx, const struct read_blob_callbacks *cbs);


@@ -203,10 +202,9 @@ struct apply_operations {
         * TODO: really, the extraction backends should be responsible for
         * generating 'd_extraction_name'.
         *
         * TODO: really, the extraction backends should be responsible for
         * generating 'd_extraction_name'.
         *

-        * Each dentry will refer to a valid inode in 'd_inode'.
-        * 'd_inode->i_extraction_aliases' will contain a list of just the
-        * dentries of that inode being extracted.  This will be a (possibly
-        * nonproper) subset of the 'd_inode->i_dentry' list.
+        * Each dentry will refer to a valid inode in 'd_inode'.  Each inode
+        * will contain a list of dentries of that inode being extracted; this
+        * list may be shorter than the inode's full dentry list.

         *
         * The blobs required to be extracted will already be prepared in
         * 'apply_ctx'.  The extraction backend should call extract_blob_list()
         *
         * The blobs required to be extracted will already be prepared in
         * 'apply_ctx'.  The extraction backend should call extract_blob_list()

diff --git a/include/wimlib/dentry.h b/include/wimlib/dentry.h
index 74cb7ad6be1d03f2e4ad30c4cfdad74bc6b20757..c6d1f12d28df0c373c80e61f40330d861204c5ea 100644 (file)
--- a/include/wimlib/dentry.h
+++ b/include/wimlib/dentry.h
@@ -116,10 +116,10 @@ struct wim_dentry {
         * extracted as part of the current extraction operation.  */
        struct list_head d_extraction_list_node;
 
         * extracted as part of the current extraction operation.  */
        struct list_head d_extraction_list_node;
 

-       /* (Extraction only) Linked list node that connects all dentries being
-        * extracted as aliases of the same inode as part of the current
-        * extraction operation.  */
-       struct list_head d_extraction_alias_node;
+       /* (Extraction only) Pointer to the next alias for this dentry's inode
+        * that needs to be extracted as part of the current extraction
+        * operation, or NULL if this is the last alias.  */
+       struct wim_dentry *d_next_extraction_alias;

 };
 
 static inline bool
 };
 
 static inline bool

diff --git a/include/wimlib/inode.h b/include/wimlib/inode.h
index f9b97cf858d0054f00ec5f7d4f395c297ce28a8b..21fb9f535f232a3f4045521afe69faaba2723700 100644 (file)
--- a/include/wimlib/inode.h
+++ b/include/wimlib/inode.h
@@ -186,13 +186,13 @@ struct wim_inode {
 
                /* Fields used only during extraction  */
                struct {
 
                /* Fields used only during extraction  */
                struct {

-                       /* List of aliases of this dentry that are being
-                        * extracted in the current extraction operation.  This
-                        * will be a (possibly nonproper) subset of the dentries
-                        * in the i_dentry list.  This list will be constructed
+                       /* A singly linked list of aliases of this dentry that
+                        * are being extracted in the current extraction
+                        * operation.  This list may be shorter than the inode's
+                        * full alias list.  This list will be constructed

                         * regardless of whether the extraction backend supports
                         * hard links or not.  */
                         * regardless of whether the extraction backend supports
                         * hard links or not.  */

-                       struct list_head i_extraction_aliases;
+                       struct wim_dentry *i_first_extraction_alias;

 
                #ifdef WITH_NTFS_3G
                        /* In NTFS-3g extraction mode, this is set to the Master
 
                #ifdef WITH_NTFS_3G
                        /* In NTFS-3g extraction mode, this is set to the Master

diff --git a/src/extract.c b/src/extract.c
index c794620d590c170c222d79fe233f8dd7e118140c..ea9c25228d8c8a4877a59223b6daa78e2777d749 100644 (file)
--- a/src/extract.c
+++ b/src/extract.c
@@ -1080,18 +1080,14 @@ static void
 dentry_list_build_inode_alias_lists(struct list_head *dentry_list)
 {
        struct wim_dentry *dentry;
 dentry_list_build_inode_alias_lists(struct list_head *dentry_list)
 {
        struct wim_dentry *dentry;

-       struct wim_inode *inode;
+
+       list_for_each_entry(dentry, dentry_list, d_extraction_list_node)
+               dentry->d_inode->i_first_extraction_alias = NULL;

 
        list_for_each_entry(dentry, dentry_list, d_extraction_list_node) {
 
        list_for_each_entry(dentry, dentry_list, d_extraction_list_node) {

-               inode = dentry->d_inode;
-               if (!inode->i_visited)
-                       INIT_LIST_HEAD(&inode->i_extraction_aliases);
-               list_add_tail(&dentry->d_extraction_alias_node,
-                             &inode->i_extraction_aliases);
-               inode->i_visited = 1;
+               dentry->d_next_extraction_alias = dentry->d_inode->i_first_extraction_alias;
+               dentry->d_inode->i_first_extraction_alias = dentry;

        }
        }

-       list_for_each_entry(dentry, dentry_list, d_extraction_list_node)
-               dentry->d_inode->i_visited = 0;

 }
 
 static void
 }
 
 static void