From fa8d436c87f156d18208df3819fecee9fc1dbd9e Mon Sep 17 00:00:00 2001 From: Ulrich Drepper Date: Tue, 29 Jan 2002 07:54:51 +0000 Subject: Update. 2002-01-18 Wolfram Gloger * malloc/malloc.c: Rewrite, adapted from Doug Lea's malloc-2.7.0.c. * malloc/malloc.h: Likewise. * malloc/arena.c: New file. * malloc/hooks.c: New file. * malloc/tst-mallocstate.c: New file. * malloc/Makefile: Add new testcase tst-mallocstate. Add arena.c and hooks.c to distribute. Fix commented CPPFLAGS. 2002-01-28 Ulrich Drepper * stdlib/msort.c: Remove last patch. The optimization violates the same rule which qsort.c had problems with. 2002-01-27 Paul Eggert * stdlib/qsort.c (_quicksort): Do not apply the comparison function to a pivot element that lies outside the array to be sorted, as ISO C99 requires that the comparison function be called only with addresses of array elements [PR libc/2880]. --- stdlib/msort.c | 408 ++++++++------------------------------------------------- 1 file changed, 52 insertions(+), 356 deletions(-) (limited to 'stdlib/msort.c') diff --git a/stdlib/msort.c b/stdlib/msort.c index 7d21c10fc9..3668370cd5 100644 --- a/stdlib/msort.c +++ b/stdlib/msort.c @@ -1,9 +1,7 @@ /* An alternative to qsort, with an identical interface. This file is part of the GNU C Library. - Copyright (C) 1992, 1995-1997, 1999, 2000, 2001, 2002 - Free Software Foundation, Inc. - Original Implementation by Mike Haertel, September 1988. - Towers of Hanoi Mergesort by Roger Sayle, January 2002. + Copyright (C) 1992, 1995-1997, 1999, 2000, 2001 Free Software Foundation, Inc. + Written by Mike Haertel, September 1988. The GNU C Library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public @@ -21,372 +19,70 @@ 02111-1307 USA. */ #include -#include #include #include #include #include #include - -/* Check whether pointer P is aligned for access by type T. */ -#define TYPE_ALIGNED(P,T) (((char *) (P) - (char *) 0) % __alignof__ (T) == 0) - - -static int hanoi_sort (char *b, size_t n, size_t s, - __compar_fn_t cmp, char *t); -static int hanoi_sort_int (int *b, size_t n, - __compar_fn_t cmp, int *t); -#if INT_MAX != LONG_MAX -static int hanoi_sort_long (long int *b, size_t n, - __compar_fn_t cmp, long int *t); -#endif static void msort_with_tmp (void *b, size_t n, size_t s, - __compar_fn_t cmp, void *t); - - -/* This routine implements "Towers of Hanoi Mergesort". The algorithm - sorts the n elements of size s pointed to by array b using comparison - function cmp. The argument t points to a suitable temporary buffer. - If the return value is zero, the sorted array is returned in b, and - for non-zero return values the sorted array is returned in t. */ -static int -hanoi_sort (char *b, size_t n, size_t s, __compar_fn_t cmp, char *t) -{ - size_t n1, n2; - char *b1,*b2; - char *t1,*t2; - char *s1,*s2; - size_t size; - int result; - char *ptr; - - if (n <= 1) - return 0; - - if (n == 2) - { - b2 = b + s; - if ((*cmp) (b, b2) <= 0) - return 0; - memcpy (__mempcpy (t, b2, s), b, s); - return 1; - } - - n1 = n/2; - n2 = n - n1; - /* n1 < n2! */ - - size = n1 * s; - b1 = b; - b2 = b + size; - - t1 = t; - t2 = t + size; - - /* Recursively call hanoi_sort to sort the two halves of the array. - Depending upon the return values, determine the values s1 and s2 - the locations of the two sorted subarrays, ptr, the location to - contain the sorted array and result, the return value for this - function. Note that "ptr = result? t : b". */ - if (hanoi_sort (b1, n1, s, cmp, t1)) - { - if (hanoi_sort (b2, n2, s, cmp, t2)) - { - result = 0; - ptr = b; - s1 = t1; - s2 = t2; - } - else - { - result = 0; - ptr = b; - s1 = t1; - s2 = b2; - } - } - else - { - if (hanoi_sort (b2, n2, s, cmp, t2)) - { - result = 1; - ptr = t; - s1 = b1; - s2 = t2; - } - else - { - result = 1; - ptr = t; - s1 = b1; - s2 = b2; - } - } + __compar_fn_t cmp, char *t); - /* Merge the two sorted arrays s1 and s2 of n1 and n2 elements - respectively, placing the result in ptr. On entry, n1 > 0 - && n2 > 0, and with each iteration either n1 or n2 is decreased - until either reaches zero, and the loop terminates via return. */ - for (;;) - { - if ((*cmp) (s1, s2) <= 0) - { - ptr = (char *) __mempcpy (ptr, s1, s); - s1 += s; - --n1; - if (n1 == 0) - { - if (ptr != s2) - memcpy (ptr, s2, n2 * s); - return result; - } - } - else - { - ptr = (char *) __mempcpy (ptr, s2, s); - s2 += s; - --n2; - if (n2 == 0) - { - memcpy (ptr, s1, n1 * s); - return result; - } - } - } -} - - -/* This routine is a variant of hanoi_sort that is optimized for the - case where items to be sorted are the size of ints, and both b and - t are suitably aligned. The parameter s in not needed as it is - known to be sizeof(int). */ -static int -hanoi_sort_int (int *b, size_t n, __compar_fn_t cmp, int *t) -{ - size_t n1, n2; - int *b1,*b2; - int *t1,*t2; - int *s1,*s2; - int result; - int *ptr; - - if (n <= 1) - return 0; - - if (n == 2) - { - if ((*cmp) (b, b + 1) <= 0) - return 0; - t[0] = b[1]; - t[1] = b[0]; - return 1; - } - - n1 = n/2; - n2 = n - n1; - /* n1 < n2! */ - - b1 = b; - b2 = b + n1; - - t1 = t; - t2 = t + n1; - - /* Recursively call hanoi_sort_int to sort the two halves. */ - if (hanoi_sort_int (b1, n1, cmp, t1)) - { - if (hanoi_sort_int (b2, n2, cmp, t2)) - { - result = 0; - ptr = b; - s1 = t1; - s2 = t2; - } - else - { - result = 0; - ptr = b; - s1 = t1; - s2 = b2; - } - } - else - { - if (hanoi_sort_int (b2, n2, cmp, t2)) - { - result = 1; - ptr = t; - s1 = b1; - s2 = t2; - } - else - { - result = 1; - ptr = t; - s1 = b1; - s2 = b2; - } - } - - /* Merge n1 elements from s1 and n2 elements from s2 into ptr. */ - for (;;) - { - if ((*cmp) (s1, s2) <= 0) - { - *ptr++ = *s1++; - --n1; - if (n1 == 0) - { - if (ptr != s2) - memcpy (ptr, s2, n2 * sizeof (int)); - return result; - } - } - else - { - *ptr++ = *s2++; - --n2; - if (n2 == 0) - { - memcpy (ptr, s1, n1 * sizeof (int)); - return result; - } - } - } -} - - -#if INT_MAX != LONG_MAX -/* This routine is a variant of hanoi_sort that is optimized for the - case where items to be sorted are the size of longs, and both b and - t are suitably aligned. The parameter s in not needed as it is - known to be sizeof(long). In case sizeof(int)== sizeof(long) we - do not need this code since it would be the same as hanoi_sort_int. */ -static int -hanoi_sort_long (long int *b, size_t n, __compar_fn_t cmp, long int *t) +static void +msort_with_tmp (void *b, size_t n, size_t s, __compar_fn_t cmp, + char *t) { + char *tmp; + char *b1, *b2; size_t n1, n2; - long int *b1,*b2; - long int *t1,*t2; - long int *s1,*s2; - int result; - long int *ptr; if (n <= 1) - return 0; - - if (n == 2) - { - if ((*cmp) (b, b + 1) <= 0) - return 0; - t[0] = b[1]; - t[1] = b[0]; - return 1; - } + return; - n1 = n/2; + n1 = n / 2; n2 = n - n1; - /* n1 < n2! */ - b1 = b; - b2 = b + n1; - - t1 = t; - t2 = t + n1; - - /* Recursively call hanoi_sort_long to sort the two halves. */ - if (hanoi_sort_long (b1, n1, cmp, t1)) - { - if (hanoi_sort_long (b2, n2, cmp, t2)) - { - result = 0; - ptr = b; - s1 = t1; - s2 = t2; - } - else - { - result = 0; - ptr = b; - s1 = t1; - s2 = b2; - } - } + b2 = (char *) b + (n1 * s); + + msort_with_tmp (b1, n1, s, cmp, t); + msort_with_tmp (b2, n2, s, cmp, t); + + tmp = t; + + if (s == OPSIZ && (b1 - (char *) 0) % OPSIZ == 0) + /* We are operating on aligned words. Use direct word stores. */ + while (n1 > 0 && n2 > 0) + { + if ((*cmp) (b1, b2) <= 0) + { + --n1; + *((op_t *) tmp)++ = *((op_t *) b1)++; + } + else + { + --n2; + *((op_t *) tmp)++ = *((op_t *) b2)++; + } + } else - { - if (hanoi_sort_long (b2, n2, cmp, t2)) - { - result = 1; - ptr = t; - s1 = b1; - s2 = t2; - } - else - { - result = 1; - ptr = t; - s1 = b1; - s2 = b2; - } - } - - /* Merge n1 elements from s1 and n2 elements from s2 into ptr. */ - for (;;) - { - if ((*cmp) (s1, s2) <= 0) - { - *ptr++ = *s1++; - --n1; - if (n1 == 0) - { - if (ptr != s2) - memcpy (ptr, s2, n2 * sizeof (long)); - return result; - } - } - else - { - *ptr++ = *s2++; - --n2; - if (n2 == 0) - { - memcpy (ptr, s1, n1 * sizeof (long)); - return result; - } - } - } -} -#endif - - -/* This routine preserves the original interface to msort_with_tmp and - determines which variant of hanoi_sort to call, based upon item size - and alignment. */ - -static void -msort_with_tmp (void *b, size_t n, size_t s, __compar_fn_t cmp, void *t) -{ - const size_t size = n * s; - - if (s == sizeof (int) && TYPE_ALIGNED (b, int)) - { - if (hanoi_sort_int (b, n, cmp, t)) - memcpy (b, t, size); - } -#if INT_MAX != LONG_MAX - else if (s == sizeof (long int) && TYPE_ALIGNED (b, long int)) - { - if (hanoi_sort_long (b, n, cmp, t)) - memcpy (b, t, size); - } -#endif - else - { - /* Call the generic implementation. */ - if (hanoi_sort (b, n, s, cmp, t)) - memcpy (b, t, size); - } + while (n1 > 0 && n2 > 0) + { + if ((*cmp) (b1, b2) <= 0) + { + tmp = (char *) __mempcpy (tmp, b1, s); + b1 += s; + --n1; + } + else + { + tmp = (char *) __mempcpy (tmp, b2, s); + b2 += s; + --n2; + } + } + if (n1 > 0) + memcpy (tmp, b1, n1 * s); + memcpy (b, t, (n - n2) * s); } void @@ -397,7 +93,7 @@ qsort (void *b, size_t n, size_t s, __compar_fn_t cmp) if (size < 1024) { void *buf = __alloca (size); - + /* The temporary array is small, so put it on the stack. */ msort_with_tmp (b, n, s, cmp, buf); } @@ -434,7 +130,7 @@ qsort (void *b, size_t n, size_t s, __compar_fn_t cmp) measured in bytes. */ /* If the memory requirements are too high don't allocate memory. */ - if ((long int) (size / pagesize) > phys_pages) + if (size / pagesize > phys_pages) _quicksort (b, n, s, cmp); else { -- cgit 1.4.1