2007-10-04 Jakub Jelinek

	* stdlib/msort.c: Include stdint.h.
	(struct msort_param): New type.
	(msort_with_tmp): Use struct msort_param pointer for unchanging
	parameters.  Add optimized handling for several common sizes
	and indirect sorting mode.
	(qsort): Adjust msort_with_tmp callers.  For big S use indirect
	sorting.
	Suggested by Belazougui Djamel .

	* stdlib/Makefile (tests): Add tst-qsort2.
	* stdlib/tst-qsort2.c: New test.

1 files changed, 89 insertions, 0 deletions

diff --git a/stdlib/tst-qsort2.c b/stdlib/tst-qsort2.c
new file mode 100644
index 0000000000..75d4a1732d
--- /dev/null
+++ b/stdlib/tst-qsort2.c
@@ -0,0 +1,89 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+char *array;
+char *array_end;
+size_t member_size;
+
+int
+compare (const void *a1, const void *b1)
+{
+  const char *a = a1;
+  const char *b = b1;
+
+  if (! (array <= a && a < array_end
+	 && array <= b && b < array_end))
+    {
+      puts ("compare arguments not inside of the array");
+      exit (EXIT_FAILURE);
+    }
+  int ret = b[0] - a[0];
+  if (ret)
+    return ret;
+  if (member_size > 1)
+    return b[1] - a[1];
+  return 0;
+}
+
+int
+test (size_t nmemb, size_t size)
+{
+  array = malloc (nmemb * size);
+  if (array == NULL)
+    {
+      printf ("%zd x %zd: no memory", nmemb, size);
+      return 1;
+    }
+
+  array_end = array + nmemb * size;
+  member_size = size;
+
+  char *p;
+  size_t i;
+  size_t bias = random ();
+  for (i = 0, p = array; i < nmemb; i++, p += size)
+    {
+      p[0] = (char) (i + bias);
+      if (size > 1)
+	p[1] = (char) ((i + bias) >> 8);
+    }
+
+  qsort (array, nmemb, size, compare);
+
+  for (i = 0, p = array; i < nmemb - 1; i++, p += size)
+    {
+      if (p[0] < p[size]
+	  || (size > 1 && p[0] == p[size] && p[1] < p[size + 1]))
+	{
+	  printf ("%zd x %zd: failure at offset %zd\n", nmemb,
+		  size, i);
+	  free (array);
+	  return 1;
+	}
+    }
+
+  free (array);
+  return 0;
+}
+
+int
+main (int argc, char **argv)
+{
+  int ret = 0;
+  if (argc >= 2)
+    ret |= test (atoi (argv[1]), atoi (argv[2]));
+  else
+    {
+      ret |= test (10000, 1);
+      ret |= test (200000, 2);
+      ret |= test (2000000, 3);
+      ret |= test (2132310, 4);
+      ret |= test (1202730, 7);
+      ret |= test (1184710, 8);
+      ret |= test (272710, 12);
+      ret |= test (14170, 32);
+      ret |= test (4170, 320);
+    }
+
+  return ret;
+}