From 8fe383860e4406d0becf34d2410155e8c93dd494 Mon Sep 17 00:00:00 2001
From: Dave Reisner <dreisner@archlinux.org>
Date: Wed, 11 Jul 2012 09:59:49 -0400
Subject: lib/be_package: use qsort instead of our own msort
On the assumption that these arrays are already mostly sorted, use the
standard quicksort method to sort the files arrays. The files_msort
function name is tweaked to give it a more general name to reflect this
change.
Signed-off-by: Dave Reisner <dreisner@archlinux.org>
Signed-off-by: Dan McGee <dan@archlinux.org>
---
lib/libalpm/be_package.c | 52 +++---------------------------------------------
1 file changed, 3 insertions(+), 49 deletions(-)
(limited to 'lib')
diff --git a/lib/libalpm/be_package.c b/lib/libalpm/be_package.c
index dd027f5e..07c75a16 100644
--- a/lib/libalpm/be_package.c
+++ b/lib/libalpm/be_package.c
@@ -248,53 +248,6 @@ static int parse_descfile(alpm_handle_t *handle, struct archive *a, alpm_pkg_t *
return 0;
}
-static void files_merge(alpm_file_t a[], alpm_file_t b[], alpm_file_t c[],
- size_t m, size_t n)
-{
- size_t i = 0, j = 0, k = 0;
- while(i < m && j < n) {
- if(strcmp(a[i].name, b[j].name) < 0) {
- c[k++] = a[i++];
- } else {
- c[k++] = b[j++];
- }
- }
- while(i < m) {
- c[k++] = a[i++];
- }
- while(j < n) {
- c[k++] = b[j++];
- }
-}
-
-static alpm_file_t *files_msort(alpm_file_t *files, size_t n)
-{
- alpm_file_t *work;
- size_t blocksize = 1;
-
- CALLOC(work, n, sizeof(alpm_file_t), return NULL);
-
- for(blocksize = 1; blocksize < n; blocksize *= 2) {
- size_t i, max_extent = 0;
- for(i = 0; i < n - blocksize; i += 2 * blocksize) {
- /* this limits our actual merge to the length of the array, since we will
- * not likely be a perfect power of two. */
- size_t right_blocksize = blocksize;
- if(i + blocksize * 2 > n) {
- right_blocksize = n - i - blocksize;
- }
- files_merge(files + i, files + i + blocksize, work + i,
- blocksize, right_blocksize);
- max_extent = i + blocksize + right_blocksize;
- }
- /* ensure we only copy what we actually touched on this merge pass,
- * no more, no less */
- memcpy(files, work, max_extent * sizeof(alpm_file_t));
- }
- free(work);
- return files;
-}
-
/**
* Validate a package.
* @param handle the context handle
@@ -536,8 +489,9 @@ alpm_pkg_t *_alpm_pkg_load_internal(alpm_handle_t *handle,
/* "checking for conflicts" requires a sorted list, ensure that here */
_alpm_log(handle, ALPM_LOG_DEBUG,
"sorting package filelist for %s\n", pkgfile);
- newpkg->files.files = files_msort(newpkg->files.files,
- newpkg->files.count);
+
+ qsort(newpkg->files.files, newpkg->files.count,
+ sizeof(alpm_file_t), _alpm_files_cmp);
}
newpkg->infolevel |= INFRQ_FILES;
}
--
cgit v1.2.3-2-g168b