Linux Archive

Linux Archive (http://www.linux-archive.org/)
-   ArchLinux Pacman Development (http://www.linux-archive.org/archlinux-pacman-development/)
-   -   lib/be_package: use qsort instead of our own msort (http://www.linux-archive.org/archlinux-pacman-development/683021-lib-be_package-use-qsort-instead-our-own-msort.html)

Dan McGee 07-12-2012 05:51 PM

lib/be_package: use qsort instead of our own msort
 
On Thu, Jul 12, 2012 at 12:18 PM, Dave Reisner <dreisner@archlinux.org> wrote:
> 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>
> ---
> I didn't actually measure the impact here. One thing to consider here is
> that qsort isn't reentrant, and qsort_r isn't standard.

1. Add qsort_r() to configure.ac's list of functions to check for, use
that if available, else use plain qsort() ?
2. I can take a look at the impact performance wise, but I do like the
loc-- going on here.
3. I'd feel better if this patch came before the other one, and if we
also added a qsort() in loading the local filelists, to ensure our
bsearch() doesn't fall over due to reading unsorted lists off the
filesystem.

> lib/libalpm/be_package.c | 47 +++--------------------------------------------
> 1 file changed, 3 insertions(+), 44 deletions(-)
>
> diff --git a/lib/libalpm/be_package.c b/lib/libalpm/be_package.c
> index dd027f5..1a6324c 100644
> --- a/lib/libalpm/be_package.c
> +++ b/lib/libalpm/be_package.c
> @@ -248,50 +248,9 @@ 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)
> +static alpm_file_t *files_sort(alpm_file_t *files, 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);
> + qsort(files, n, sizeof(alpm_file_t), _alpm_files_cmp);
> return files;
> }
>
> @@ -536,7 +495,7 @@ 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
", pkgfile);
> - newpkg->files.files = files_msort(newpkg->files.files,
> + newpkg->files.files = files_sort(newpkg->files.files,
> newpkg->files.count);
> }
> newpkg->infolevel |= INFRQ_FILES;
> --
> 1.7.11.1


All times are GMT. The time now is 12:03 AM.

VBulletin, Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.
Content Relevant URLs by vBSEO ©2007, Crawlability, Inc.