[4/7] stdlib: Add more qsort{_r} coverage

Message ID 1516298002-4618-5-git-send-email-adhemerval.zanella@linaro.org
State New
Headers show
Series
  • Refactor qsort implementation
Related show

Commit Message

Adhemerval Zanella Jan. 18, 2018, 5:53 p.m.
This patch adds a qsort and qsort_t (which glibc current lacks
coverage).  The test check with random input (created using support
random) with different internal types (uint8_t, uint16_t, uint32_t,
and uint64_t) and with different set of element numbers (from 0
to 262144).

Checked on x86_64-linux-gnu.

	* stdlib/tst-qsort3.c: New file.
	* stdlib/Makefile (tests): Add tst-qsort3.
---
 stdlib/Makefile     |   2 +-
 stdlib/tst-qsort3.c | 231 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 232 insertions(+), 1 deletion(-)
 create mode 100644 stdlib/tst-qsort3.c

-- 
2.7.4

Patch

diff --git a/stdlib/Makefile b/stdlib/Makefile
index 7c363a6..6ef20a7 100644
--- a/stdlib/Makefile
+++ b/stdlib/Makefile
@@ -84,7 +84,7 @@  tests		:= tst-strtol tst-strtod testmb testrand testsort testdiv   \
 		   tst-cxa_atexit tst-on_exit test-atexit-race 		    \
 		   test-at_quick_exit-race test-cxa_atexit-race             \
 		   test-on_exit-race test-dlclose-exit-race 		    \
-		   tst-makecontext-align
+		   tst-makecontext-align tst-qsort3
 
 tests-internal	:= tst-strtod1i tst-strtod3 tst-strtod4 tst-strtod5i \
 		   tst-tls-atexit tst-tls-atexit-nodelete
diff --git a/stdlib/tst-qsort3.c b/stdlib/tst-qsort3.c
new file mode 100644
index 0000000..e6ddb60
--- /dev/null
+++ b/stdlib/tst-qsort3.c
@@ -0,0 +1,231 @@ 
+/* qsort(_r) generic tests.
+   Copyright (C) 2017 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
+
+   The GNU C Library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2.1 of the License, or (at your option) any later version.
+
+   The GNU C Library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with the GNU C Library; if not, see
+   <http://www.gnu.org/licenses/>.  */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdint.h>
+#include <getopt.h>
+#include <errno.h>
+
+#include <support/check.h>
+#include <support/support.h>
+#include <support/test-driver.h>
+#include <support/support_random.h>
+
+/* Functions used to check qsort.  */
+static int
+uint8_t_cmp (const void *a, const void *b)
+{
+  uint8_t ia = *(uint8_t*)a;
+  uint8_t ib = *(uint8_t*)b;
+  return (ia > ib) - (ia < ib);
+}
+
+static int
+uint16_t_cmp (const void *a, const void *b)
+{
+  uint16_t ia = *(uint16_t*)a;
+  uint16_t ib = *(uint16_t*)b;
+  return (ia > ib) - (ia < ib);
+}
+
+static int
+uint32_t_cmp (const void *a, const void *b)
+{
+  uint32_t ia = *(uint32_t*)a;
+  uint32_t ib = *(uint32_t*)b;
+  return (ia > ib) - (ia < ib);
+}
+
+static int
+uint64_t_cmp (const void *a, const void *b)
+{
+  uint64_t ia = *(uint64_t*)a;
+  uint64_t ib = *(uint64_t*)b;
+  return (ia > ib) - (ia < ib);
+}
+
+/* Function used to check qsort_r.  */
+
+enum type_cmp_t
+{
+  UINT8_CMP_T  = 0,
+  UINT16_CMP_T = 1,
+  UINT32_CMP_T = 2,
+  UINT64_CMP_T = 3,
+};
+
+static enum type_cmp_t
+uint_t_cmp_type (size_t sz)
+{
+  switch (sz)
+    {
+      case sizeof (uint8_t):  return UINT8_CMP_T;
+      case sizeof (uint16_t): return UINT16_CMP_T;
+      case sizeof (uint64_t): return UINT64_CMP_T;
+      case sizeof (uint32_t):
+      default:                return UINT32_CMP_T;
+    }
+}
+
+static int
+uint_t_cmp (const void *a, const void *b, void *arg)
+{
+  enum type_cmp_t type = *(enum type_cmp_t*) arg;
+  switch (type)
+    {
+    case UINT8_CMP_T:  return uint8_t_cmp (a, b);
+    case UINT16_CMP_T: return uint16_t_cmp (a, b);
+    case UINT64_CMP_T: return uint64_t_cmp (a, b);
+    case UINT32_CMP_T:
+    default:           return uint32_t_cmp (a, b);
+    }
+}
+
+static struct mt19937_32 mt;
+
+static void *
+create_array (size_t nmemb, size_t type_size)
+{
+  size_t size = nmemb * type_size;
+  uint8_t *array = xmalloc (size);
+
+  for (size_t i = 0; i < size; i++)
+    array[i] = uniform_uint32_distribution (mt32_rand (&mt), 0, UINT8_MAX);
+
+  return array;
+}
+
+typedef int (*cmpfunc_t)(const void *, const void *);
+
+static void
+check_array (void *array, size_t nmemb, size_t type_size,
+	     cmpfunc_t cmpfunc)
+{
+  for (size_t i = 1; i < nmemb; i++)
+    {
+      void *array_i   = (void*)((uintptr_t)array + i * type_size);
+      void *array_i_1 = (void*)((uintptr_t)array + (i-1) * type_size);
+      int ret;
+      TEST_VERIFY ((ret = cmpfunc (array_i, array_i_1)) >= 0);
+      if (ret < 0)
+	break;
+    }
+}
+
+static uint32_t seed;
+
+#define OPT_SEED 10000
+#define CMDLINE_OPTIONS \
+  { "seed", required_argument, NULL, OPT_SEED },
+
+static void __attribute__ ((used))
+cmdline_process_function (int c)
+{
+  switch (c)
+    {
+      case OPT_SEED:
+	{
+	  unsigned long int value = strtoul (optarg, NULL, 0);
+	  if (errno == ERANGE || value > UINT32_MAX)
+	    {
+	      printf ("error: seed should be a value in range of "
+		      "[0, UINT32_MAX]\n");
+	      exit (EXIT_FAILURE);
+	    }
+	  seed = value;
+	}
+      break;
+    }
+}
+
+#define CMDLINE_PROCESS cmdline_process_function
+
+
+static int
+do_test (void)
+{
+  mt32_seed (&mt, seed);
+  printf ("info: seed=0x%08x\n", seed);
+
+  const size_t elem[] = { 0, 1, 64, 128, 4096, 16384, 262144 };
+  const size_t nelem = sizeof (elem) / sizeof (elem[0]);
+
+  struct test_t
+    {
+      size_t type_size;
+      cmpfunc_t cmpfunc;
+    }
+  tests[] =
+    {
+      { sizeof (uint8_t),  uint8_t_cmp },
+      { sizeof (uint16_t), uint16_t_cmp },
+      { sizeof (uint32_t), uint32_t_cmp },
+      { sizeof (uint64_t), uint64_t_cmp },
+      /* Test swap with large elements.  */
+      { 32,                uint32_t_cmp },
+    };
+  size_t ntests = sizeof (tests) / sizeof (tests[0]);
+
+  for (size_t i = 0; i < ntests; i++)
+    {
+      size_t ts = tests[i].type_size;
+      if (test_verbose > 0)
+        printf ("info: testing qsort with type_size=%zu\n", ts);
+      for (size_t n = 0; n < nelem; n++)
+	{
+	  size_t nmemb = elem[n];
+	  if (test_verbose > 0)
+            printf ("  nmemb=%zu, total size=%zu\n", nmemb, nmemb * ts);
+
+	  void *array = create_array (nmemb, ts);
+
+	  qsort (array, nmemb, ts, tests[i].cmpfunc);
+
+	  check_array (array, nmemb, ts, tests[i].cmpfunc);
+
+	  free (array);
+	}
+    }
+
+  for (size_t i = 0; i < ntests; i++)
+    {
+      size_t ts = tests[i].type_size;
+      if (test_verbose > 0)
+        printf ("info: testing qsort_r type_size=%zu\n", ts);
+      for (size_t n = 0; n < nelem; n++)
+	{
+	  size_t nmemb = elem[n];
+	  if (test_verbose > 0)
+            printf ("  nmemb=%zu, total size=%zu\n", nmemb, nmemb * ts);
+
+	  void *array = create_array (nmemb, ts);
+
+	  enum type_cmp_t type = uint_t_cmp_type (ts);
+	  qsort_r (array, nmemb, ts, uint_t_cmp, &type);
+
+	  check_array (array, nmemb, ts, tests[i].cmpfunc);
+
+	  free (array);
+	}
+    }
+
+  return 0;
+}
+
+#include <support/test-driver.c>