Save memory by using a singly-linked list for extraction aliases
authorEric Biggers <ebiggers3@gmail.com>
Sun, 31 May 2015 05:36:25 +0000 (00:36 -0500)
committerEric Biggers <ebiggers3@gmail.com>
Fri, 5 Jun 2015 03:45:34 +0000 (22:45 -0500)
include/wimlib/apply.h
include/wimlib/dentry.h
include/wimlib/inode.h
src/extract.c

index f9a4a2f..ad21418 100644 (file)
@@ -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);
 }
 
-/* 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)                 \
-       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);
@@ -203,10 +202,9 @@ struct apply_operations {
         * 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()
index 74cb7ad..c6d1f12 100644 (file)
@@ -116,10 +116,10 @@ struct wim_dentry {
         * 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
index f9b97cf..21fb9f5 100644 (file)
@@ -186,13 +186,13 @@ struct wim_inode {
 
                /* 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.  */
-                       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
index c794620..ea9c252 100644 (file)
@@ -1080,18 +1080,14 @@ static void
 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) {
-               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