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

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