Convert package filelists to an array instead of linked list

This accomplishes quite a few things with one rather invasive change.

1. Iteration is much more performant, due to a reduction in pointer
   chasing and linear item access.
2. Data structures are smaller- we no longer have the overhead of the
   linked list as the file struts are now laid out consecutively in
   memory.
3. Memory allocation has been massively reworked. Before, we would
   allocate three different pieces of memory per file item- the list
   struct, the file struct, and the copied filename. What this resulted
   in was massive fragmentation of memory when loading filelists since
   the memory allocator had to leave holes all over the place. The new
   situation here now removes the need for any list item allocation;
   allocates the file structs in contiguous memory (and reallocs as
   necessary), leaving only the strings as individually allocated. Tests
   using valgrind (massif) show some pretty significant memory
   reductions on the worst case `pacman -Ql > /dev/null` (366387 files
   on my machine):

   Before:
     Peak heap:   54,416,024 B
	 Useful heap: 36,840,692 B
	 Extra heap:  17,575,332 B

   After:
     Peak heap:   38,004,352 B
	 Useful heap: 28,101,347 B
	 Extra heap:   9,903,005 B

Several small helper methods have been introduced, including a list to
array conversion helper as well as a filelist merge sort that works
directly on arrays.

Signed-off-by: Dan McGee <dan@archlinux.org>

1 files changed, 26 insertions, 20 deletions

diff --git a/lib/libalpm/package.c b/lib/libalpm/package.c
index ae9b9a9d..fd3d0c65 100644
--- a/lib/libalpm/package.c
+++ b/lib/libalpm/package.c
@@ -106,7 +106,7 @@ static alpm_list_t *_pkg_get_conflicts(alpm_pkg_t *pkg)  { return pkg->conflicts
 static alpm_list_t *_pkg_get_provides(alpm_pkg_t *pkg)   { return pkg->provides; }
 static alpm_list_t *_pkg_get_replaces(alpm_pkg_t *pkg)   { return pkg->replaces; }
 static alpm_list_t *_pkg_get_deltas(alpm_pkg_t *pkg)     { return pkg->deltas; }
-static alpm_list_t *_pkg_get_files(alpm_pkg_t *pkg)      { return pkg->files; }
+static alpm_filelist_t *_pkg_get_files(alpm_pkg_t *pkg)  { return &(pkg->files); }
 static alpm_list_t *_pkg_get_backup(alpm_pkg_t *pkg)     { return pkg->backup; }
 
 static void *_pkg_changelog_open(alpm_pkg_t UNUSED *pkg)
@@ -313,7 +313,7 @@ alpm_list_t SYMEXPORT *alpm_pkg_get_deltas(alpm_pkg_t *pkg)
 	return pkg->ops->get_deltas(pkg);
 }
 
-alpm_list_t SYMEXPORT *alpm_pkg_get_files(alpm_pkg_t *pkg)
+alpm_filelist_t SYMEXPORT *alpm_pkg_get_files(alpm_pkg_t *pkg)
 {
 	ASSERT(pkg != NULL, return NULL);
 	pkg->handle->pm_errno = 0;
@@ -427,22 +427,14 @@ alpm_list_t SYMEXPORT *alpm_pkg_compute_requiredby(alpm_pkg_t *pkg)
 
 /** @} */
 
-void _alpm_files_free(alpm_file_t *file)
+alpm_file_t *_alpm_file_copy(alpm_file_t *dest,
+		const alpm_file_t *src)
 {
-	free(file->name);
-	free(file);
-}
-
-alpm_file_t *_alpm_files_dup(const alpm_file_t *file)
-{
-	alpm_file_t *newfile;
-	CALLOC(newfile, 1, sizeof(alpm_file_t), return NULL);
-
-	STRDUP(newfile->name, file->name, return NULL);
-	newfile->size = file->size;
-	newfile->mode = file->mode;
+	STRDUP(dest->name, src->name, return NULL);
+	dest->size = src->size;
+	dest->mode = src->mode;
 
-	return newfile;
+	return dest;
 }
 
 /* Helper function for comparing files list entries
@@ -493,8 +485,17 @@ alpm_pkg_t *_alpm_pkg_dup(alpm_pkg_t *pkg)
 	newpkg->licenses   = alpm_list_strdup(pkg->licenses);
 	newpkg->replaces   = alpm_list_strdup(pkg->replaces);
 	newpkg->groups     = alpm_list_strdup(pkg->groups);
-	for(i = pkg->files; i; i = alpm_list_next(i)) {
-		newpkg->files = alpm_list_add(newpkg->files, _alpm_files_dup(i->data));
+	if(pkg->files.count) {
+		size_t filenum;
+		size_t len = sizeof(alpm_file_t) * pkg->files.count;
+		MALLOC(newpkg->files.files, len, goto cleanup);
+		for(filenum = 0; filenum < pkg->files.count; filenum++) {
+			if(!_alpm_file_copy(newpkg->files.files + filenum,
+						pkg->files.files + filenum)) {
+				goto cleanup;
+			}
+		}
+		newpkg->files.count = pkg->files.count;
 	}
 	for(i = pkg->backup; i; i = alpm_list_next(i)) {
 		newpkg->backup = alpm_list_add(newpkg->backup, _alpm_backup_dup(i->data));
@@ -545,8 +546,13 @@ void _alpm_pkg_free(alpm_pkg_t *pkg)
 	FREELIST(pkg->licenses);
 	FREELIST(pkg->replaces);
 	FREELIST(pkg->groups);
-	alpm_list_free_inner(pkg->files, (alpm_list_fn_free)_alpm_files_free);
-	alpm_list_free(pkg->files);
+	if(pkg->files.count) {
+		size_t i;
+		for(i = 0; i < pkg->files.count; i++) {
+			free(pkg->files.files[i].name);
+		}
+		free(pkg->files.files);
+	}
 	alpm_list_free_inner(pkg->backup, (alpm_list_fn_free)_alpm_backup_free);
 	alpm_list_free(pkg->backup);
 	alpm_list_free_inner(pkg->depends, (alpm_list_fn_free)_alpm_dep_free);