summaryrefslogtreecommitdiff
path: root/stdlib
diff options
context:
space:
mode:
authorUlrich Drepper <drepper@redhat.com>2002-01-29 07:54:51 +0000
committerUlrich Drepper <drepper@redhat.com>2002-01-29 07:54:51 +0000
commitfa8d436c87f156d18208df3819fecee9fc1dbd9e (patch)
treee22f5754d69c0144f0945a26727c3984008f9d37 /stdlib
parentdb2ebcef2428cb568315895f8fe3ef19d41735bc (diff)
downloadglibc-fa8d436c87f156d18208df3819fecee9fc1dbd9e.tar.gz
Update.
2002-01-18 Wolfram Gloger <wg@malloc.de> * 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 <drepper@redhat.com> * stdlib/msort.c: Remove last patch. The optimization violates the same rule which qsort.c had problems with. 2002-01-27 Paul Eggert <eggert@twinsun.com> * 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].
Diffstat (limited to 'stdlib')
-rw-r--r--stdlib/msort.c408
-rw-r--r--stdlib/qsort.c15
2 files changed, 58 insertions, 365 deletions
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 <alloca.h>
-#include <limits.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <memcopy.h>
#include <errno.h>
-
-/* 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
{
diff --git a/stdlib/qsort.c b/stdlib/qsort.c
index 512277ad5f..1ac268bec9 100644
--- a/stdlib/qsort.c
+++ b/stdlib/qsort.c
@@ -92,9 +92,6 @@ _quicksort (void *const pbase, size_t total_elems, size_t size,
{
register char *base_ptr = (char *) pbase;
- /* Allocating SIZE bytes for a pivot buffer facilitates a better
- algorithm below since we can do comparisons directly on the pivot. */
- char *pivot_buffer = (char *) __alloca (size);
const size_t max_thresh = MAX_THRESH * size;
if (total_elems == 0)
@@ -113,8 +110,6 @@ _quicksort (void *const pbase, size_t total_elems, size_t size,
char *left_ptr;
char *right_ptr;
- char *pivot = pivot_buffer;
-
/* Select median value from among LO, MID, and HI. Rearrange
LO and HI so the three values are sorted. This lowers the
probability of picking a pathological pivot value and
@@ -132,8 +127,6 @@ _quicksort (void *const pbase, size_t total_elems, size_t size,
if ((*cmp) ((void *) mid, (void *) lo) < 0)
SWAP (mid, lo, size);
jump_over:;
- memcpy (pivot, mid, size);
- pivot = pivot_buffer;
left_ptr = lo + size;
right_ptr = hi - size;
@@ -143,15 +136,19 @@ _quicksort (void *const pbase, size_t total_elems, size_t size,
that this algorithm runs much faster than others. */
do
{
- while ((*cmp) ((void *) left_ptr, (void *) pivot) < 0)
+ while ((*cmp) ((void *) left_ptr, (void *) mid) < 0)
left_ptr += size;
- while ((*cmp) ((void *) pivot, (void *) right_ptr) < 0)
+ while ((*cmp) ((void *) mid, (void *) right_ptr) < 0)
right_ptr -= size;
if (left_ptr < right_ptr)
{
SWAP (left_ptr, right_ptr, size);
+ if (mid == left_ptr)
+ mid = right_ptr;
+ else if (mid == right_ptr)
+ mid = left_ptr;
left_ptr += size;
right_ptr -= size;
}