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/qsort.c | 15 ++++++--------- 1 file changed, 6 insertions(+), 9 deletions(-) (limited to 'stdlib/qsort.c') 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; } -- cgit v1.2.3