From: Eric Biggers <ebiggers3@gmail.com>
Date: Sun, 31 May 2015 05:36:25 +0000 (-0500)
Subject: Save memory by using a singly-linked list for extraction aliases
X-Git-Tag: v1.8.2~93
X-Git-Url: https://wimlib.net/git/?p=wimlib;a=commitdiff_plain;h=846d3ae386f6c12953816108c04de244533e3a4a

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

diff --git a/include/wimlib/apply.h b/include/wimlib/apply.h
index f9a4a2f1..ad21418e 100644
--- 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);
 }
 
-/* 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()
diff --git a/include/wimlib/dentry.h b/include/wimlib/dentry.h
index 74cb7ad6..c6d1f12d 100644
--- 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;
 
-	/* (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
diff --git a/include/wimlib/inode.h b/include/wimlib/inode.h
index f9b97cf8..21fb9f53 100644
--- a/include/wimlib/inode.h
+++ b/include/wimlib/inode.h
@@ -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
diff --git a/src/extract.c b/src/extract.c
index c794620d..ea9c2522 100644
--- 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;
-	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