about summary refs log tree commit diff
path: root/stdlib/msort.c
diff options
context:
space:
mode:
Diffstat (limited to 'stdlib/msort.c')
-rw-r--r--stdlib/msort.c408
1 files changed, 52 insertions, 356 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
 	{
generated by cgit-pink 1.4.1 (git 2.36.1) at 2024-12-05 01:05:29 +0000