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].

1 files changed, 6 insertions, 9 deletions

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;
 		}