public inbox for glibc-cvs@sourceware.org
help / color / mirror / Atom feed
* [glibc/azanella/qsort-fixes] stdlib: Add more qsort{_r} coverage
@ 2021-09-06 18:22 Adhemerval Zanella
0 siblings, 0 replies; 2+ messages in thread
From: Adhemerval Zanella @ 2021-09-06 18:22 UTC (permalink / raw)
To: glibc-cvs
https://sourceware.org/git/gitweb.cgi?p=glibc.git;h=de255ac5b5d1d0d63405d2fa47e7d364c6bcad61
commit de255ac5b5d1d0d63405d2fa47e7d364c6bcad61
Author: Adhemerval Zanella <adhemerval.zanella@linaro.org>
Date: Mon Jan 15 09:20:30 2018 -0200
stdlib: Add more qsort{_r} coverage
This patch adds a qsort and qsort_r (which glibc current lacks
coverage). The test is done with random input (created using support
random), 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.
Diff:
---
stdlib/Makefile | 2 +-
stdlib/tst-qsort-common.c | 285 ++++++++++++++++++++++++++++++++++++++++++++++
stdlib/tst-qsort3.c | 138 ++++++++++++++++++++++
3 files changed, 424 insertions(+), 1 deletion(-)
diff --git a/stdlib/Makefile b/stdlib/Makefile
index 7c15549caf..ef8a9007d8 100644
--- a/stdlib/Makefile
+++ b/stdlib/Makefile
@@ -88,7 +88,7 @@ tests := tst-strtol tst-strtod testmb testrand testsort testdiv \
tst-swapcontext1 tst-setcontext4 tst-setcontext5 \
tst-setcontext6 tst-setcontext7 tst-setcontext8 \
tst-setcontext9 tst-bz20544 tst-canon-bz26341 \
- tst-realpath
+ tst-realpath tst-qsort3
tests-internal := tst-strtod1i tst-strtod3 tst-strtod4 tst-strtod5i \
tst-tls-atexit tst-tls-atexit-nodelete
diff --git a/stdlib/tst-qsort-common.c b/stdlib/tst-qsort-common.c
new file mode 100644
index 0000000000..9ab8f91618
--- /dev/null
+++ b/stdlib/tst-qsort-common.c
@@ -0,0 +1,285 @@
+/* Common definition for qsort testing/benchmark.
+ Copyright (C) 2021 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 <stdint.h>
+#include <string.h>
+#include <stdlib.h>
+#include <support/support.h>
+#include <sys/random.h>
+#include <time.h>
+
+/* Type of inputs arrays:
+ - SORTED: array already sorted in placed.
+ - MOSTLYSORTED: sorted array with 'MOSTLY_SORTED_RATIO * size' elements
+ in random positions set to random values.
+ - RANDOM: all elements in array set to random values.
+ - REPEATED: random array with 'RepeatedRation' elements in random
+ positions set to an unique value.
+ - BITONIC: strictly increasing to up middle then strictly
+ decreasing. */
+typedef enum
+{
+ SORTED,
+ MOSTLYSORTED,
+ RANDOM,
+ REPEATED,
+ BITONIC
+} arraytype_t;
+
+struct array_t
+{
+ arraytype_t type;
+ const char *name;
+ };
+static const struct array_t arraytypes[] =
+{
+ { SORTED, "SORTED" },
+ { MOSTLYSORTED, "MOSTLYSORTED" },
+ { RANDOM, "RANDOM" },
+ { REPEATED, "REPEATED" },
+ { BITONIC, "BITONIC" },
+};
+
+/* Ratio of total of elements which will randomized. */
+#define MOSTLY_SORTED_RATIO (0.2)
+
+/* Ratio of total of elements which will be repeated. */
+#define REPEATED_RATIO (0.2)
+
+/* Return the index of BASE as interpreted as an array of elements
+ of size SIZE. */
+static inline void *
+arr (void *base, size_t idx, size_t size)
+{
+ return (void*)((uintptr_t)base + (idx * size));
+}
+
+/* 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. */
+typedef enum
+{
+ UINT8_CMP_T,
+ UINT16_CMP_T,
+ UINT32_CMP_T,
+ UINT64_CMP_T
+} type_cmp_t;
+
+static type_cmp_t
+__attribute__((used))
+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
+__attribute__((used))
+uint_t_cmp (const void *a, const void *b, void *arg)
+{
+ type_cmp_t type = *(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 void
+seq (void *elem, size_t type_size, uint64_t value)
+{
+ if (type_size == sizeof (uint8_t))
+ {
+ uint8_t x = value;
+ memcpy (elem, &x, type_size);
+ }
+ else if (type_size == sizeof (uint16_t))
+ {
+ uint16_t x = value;
+ memcpy (elem, &x, type_size);
+ }
+ else if (type_size == sizeof (uint32_t))
+ {
+ uint32_t x = value;
+ memcpy (elem, &x, type_size);
+ }
+ else if (type_size == sizeof (uint64_t))
+ memcpy (elem, &value, type_size);
+ else
+ memset (elem, value, type_size);
+}
+
+static void
+random_init (void)
+{
+ unsigned short seed16v[3];
+ if (getrandom (seed16v, sizeof seed16v, 0) == -1)
+ srand (time (NULL));
+ else
+ seed48 (seed16v);
+}
+
+static uint32_t
+random_uniform_distribution (uint32_t min, uint32_t max)
+{
+ uint32_t ret;
+ uint32_t range = max - min;
+ /* It assumes the input random number RANDOM range is as larger or equal
+ than the RANGE, so the result will either returned or downscaled. */
+ if (range != UINT32_MAX)
+ {
+ uint32_t urange = range + 1; /* range can be 0. */
+ uint32_t scaling = UINT32_MAX / urange;
+ uint32_t past = urange * scaling;
+ do
+ ret = lrand48 ();
+ while (ret >= past);
+ ret /= scaling;
+ }
+ else
+ ret = lrand48 ();
+ return ret + min;
+}
+
+void
+random_buf (void *buf, size_t nbytes)
+{
+ size_t nw = nbytes / sizeof (uint32_t);
+ for (size_t i = 0; i < nw; i++)
+ {
+ uint32_t r = lrand48 ();
+ memcpy (buf, &r, sizeof (uint32_t));
+ buf = (void*)((uintptr_t)buf + sizeof (uint32_t));
+ }
+
+ size_t nb = nbytes % sizeof (uint32_t);
+ if (nb != 0)
+ {
+ uint32_t r = lrand48 ();
+ memcpy (buf, &r, nb);
+ }
+}
+
+static void *
+create_array (size_t nmemb, size_t type_size, arraytype_t type)
+{
+ size_t size = nmemb * type_size;
+ void *array = xmalloc (size);
+
+ switch (type)
+ {
+ case SORTED:
+ for (uint64_t i = 0; i < nmemb; i++)
+ seq (arr (array, i, type_size), type_size, i);
+ break;
+
+ case MOSTLYSORTED:
+ {
+ for (uint64_t i = 0; i < nmemb; i++)
+ seq (arr (array, i, type_size), type_size, i);
+
+ /* Change UNSORTED elements (based on MostlySortedRatio ratio)
+ in the sorted array. */
+ size_t unsorted = (size_t)(nmemb * MOSTLY_SORTED_RATIO);
+ for (size_t i = 0; i < unsorted; i++)
+ {
+ size_t pos = random_uniform_distribution (0, nmemb - 1);
+ random_buf (arr (array, pos, type_size), type_size);
+ }
+ }
+ break;
+
+ case RANDOM:
+ random_buf (array, size);
+ break;
+
+ case REPEATED:
+ {
+ random_buf (array, size);
+
+ void *randelem = xmalloc (type_size);
+ random_buf (randelem, type_size);
+
+ /* Repeat REPEATED elements (based on RepeatRatio ratio) in the random
+ array. */
+ size_t repeated = (size_t)(nmemb * REPEATED_RATIO);
+ for (size_t i = 0; i < repeated; i++)
+ {
+ size_t pos = random_uniform_distribution (0, nmemb - 1);
+ memcpy (arr (array, pos, type_size), randelem, type_size);
+ }
+
+ free (randelem);
+ }
+ break;
+
+ case BITONIC:
+ {
+ uint64_t i;
+ for (i = 0; i < nmemb / 2; i++)
+ seq (arr (array, i, type_size), type_size, i);
+ for ( ; i < nmemb; i++)
+ seq (arr (array, i, type_size), type_size, (nmemb - 1) - i);
+ }
+ break;
+ }
+
+ return array;
+}
+
+typedef int (*cmpfunc_t)(const void *, const void *);
diff --git a/stdlib/tst-qsort3.c b/stdlib/tst-qsort3.c
new file mode 100644
index 0000000000..d946f37c9d
--- /dev/null
+++ b/stdlib/tst-qsort3.c
@@ -0,0 +1,138 @@
+/* qsorte if (type_size == sizeof (uint32_t))
+ _r) generic tests.
+ Copyright (C) 2021 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 <array_length.h>
+#include <errno.h>
+#include <getopt.h>
+#include <stdio.h>
+#include <stdbool.h>
+#include <support/check.h>
+#include <support/support.h>
+#include <support/test-driver.h>
+
+#include <stdlib/tst-qsort-common.c>
+
+/* Check if ARRAY of total NMEMB element of size SIZE is sorted
+ based on CMPFUNC. */
+static void
+check_array (void *array, size_t nmemb, size_t type_size,
+ cmpfunc_t cmpfunc)
+{
+ for (size_t i = 1; i < nmemb; i++)
+ {
+ int ret = cmpfunc (arr (array, i, type_size),
+ arr (array, i-1, type_size));
+ TEST_VERIFY_EXIT (ret >= 0);
+ }
+}
+
+static void
+check_qsort (size_t nelem, size_t type_size, arraytype_t type,
+ cmpfunc_t cmpfunc)
+{
+ void *array = create_array (nelem, type_size, type);
+
+ qsort (array, nelem, type_size, cmpfunc);
+
+ check_array (array, nelem, type_size, cmpfunc);
+
+ free (array);
+}
+
+static void
+check_qsort_r (size_t nelem, size_t type_size, arraytype_t type,
+ cmpfunc_t cmpfunc)
+{
+ void *array = create_array (nelem, type_size, type);
+
+ type_cmp_t typecmp = uint_t_cmp_type (type_size);
+ qsort_r (array, nelem, type_size, uint_t_cmp, &typecmp);
+
+ check_array (array, nelem, type_size, cmpfunc);
+
+ free (array);
+}
+
+static int
+do_test (void)
+{
+ random_init ();
+
+ struct test_t
+ {
+ size_t type_size;
+ cmpfunc_t cmpfunc;
+ };
+ static const struct test_t 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 },
+ };
+
+ struct array_t
+ {
+ arraytype_t type;
+ const char *name;
+ };
+ static const struct array_t arraytypes[] =
+ {
+ { SORTED, "SORTED" },
+ { MOSTLYSORTED, "MOSTLYSORTED" },
+ { RANDOM, "RANDOM" },
+ { REPEATED, "REPEATED" },
+ { BITONIC, "BITONIC" },
+ };
+
+ static const size_t nelems[] =
+ { 0, 1, 16, 32, 64, 128, 256, 4096, 16384, 262144 };
+
+ for (const struct test_t *test = tests; test < array_end (tests); ++test)
+ {
+ if (test_verbose > 0)
+ printf ("info: testing qsort with type_size=%zu\n", test->type_size);
+ for (const struct array_t *arraytype = arraytypes;
+ arraytype < array_end (arraytypes);
+ ++arraytype)
+ {
+ if (test_verbose > 0)
+ printf (" distribution=%s\n", arraytype->name);
+ for (const size_t *nelem = nelems;
+ nelem < array_end (nelems);
+ ++nelem)
+ {
+ if (test_verbose > 0)
+ printf (" i nelem=%zu, total size=%zu\n", *nelem,
+ *nelem * test->type_size);
+
+ check_qsort (*nelem, test->type_size, arraytype->type,
+ test->cmpfunc);
+ check_qsort_r (*nelem, test->type_size, arraytype->type,
+ test->cmpfunc);
+ }
+ }
+ }
+
+ return 0;
+}
+
+#include <support/test-driver.c>
^ permalink raw reply [flat|nested] 2+ messages in thread
* [glibc/azanella/qsort-fixes] stdlib: Add more qsort{_r} coverage
@ 2021-09-06 18:44 Adhemerval Zanella
0 siblings, 0 replies; 2+ messages in thread
From: Adhemerval Zanella @ 2021-09-06 18:44 UTC (permalink / raw)
To: glibc-cvs
https://sourceware.org/git/gitweb.cgi?p=glibc.git;h=de255ac5b5d1d0d63405d2fa47e7d364c6bcad61
commit de255ac5b5d1d0d63405d2fa47e7d364c6bcad61
Author: Adhemerval Zanella <adhemerval.zanella@linaro.org>
Date: Mon Jan 15 09:20:30 2018 -0200
stdlib: Add more qsort{_r} coverage
This patch adds a qsort and qsort_r (which glibc current lacks
coverage). The test is done with random input (created using support
random), 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.
Diff:
---
stdlib/Makefile | 2 +-
stdlib/tst-qsort-common.c | 285 ++++++++++++++++++++++++++++++++++++++++++++++
stdlib/tst-qsort3.c | 138 ++++++++++++++++++++++
3 files changed, 424 insertions(+), 1 deletion(-)
diff --git a/stdlib/Makefile b/stdlib/Makefile
index 7c15549caf..ef8a9007d8 100644
--- a/stdlib/Makefile
+++ b/stdlib/Makefile
@@ -88,7 +88,7 @@ tests := tst-strtol tst-strtod testmb testrand testsort testdiv \
tst-swapcontext1 tst-setcontext4 tst-setcontext5 \
tst-setcontext6 tst-setcontext7 tst-setcontext8 \
tst-setcontext9 tst-bz20544 tst-canon-bz26341 \
- tst-realpath
+ tst-realpath tst-qsort3
tests-internal := tst-strtod1i tst-strtod3 tst-strtod4 tst-strtod5i \
tst-tls-atexit tst-tls-atexit-nodelete
diff --git a/stdlib/tst-qsort-common.c b/stdlib/tst-qsort-common.c
new file mode 100644
index 0000000000..9ab8f91618
--- /dev/null
+++ b/stdlib/tst-qsort-common.c
@@ -0,0 +1,285 @@
+/* Common definition for qsort testing/benchmark.
+ Copyright (C) 2021 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 <stdint.h>
+#include <string.h>
+#include <stdlib.h>
+#include <support/support.h>
+#include <sys/random.h>
+#include <time.h>
+
+/* Type of inputs arrays:
+ - SORTED: array already sorted in placed.
+ - MOSTLYSORTED: sorted array with 'MOSTLY_SORTED_RATIO * size' elements
+ in random positions set to random values.
+ - RANDOM: all elements in array set to random values.
+ - REPEATED: random array with 'RepeatedRation' elements in random
+ positions set to an unique value.
+ - BITONIC: strictly increasing to up middle then strictly
+ decreasing. */
+typedef enum
+{
+ SORTED,
+ MOSTLYSORTED,
+ RANDOM,
+ REPEATED,
+ BITONIC
+} arraytype_t;
+
+struct array_t
+{
+ arraytype_t type;
+ const char *name;
+ };
+static const struct array_t arraytypes[] =
+{
+ { SORTED, "SORTED" },
+ { MOSTLYSORTED, "MOSTLYSORTED" },
+ { RANDOM, "RANDOM" },
+ { REPEATED, "REPEATED" },
+ { BITONIC, "BITONIC" },
+};
+
+/* Ratio of total of elements which will randomized. */
+#define MOSTLY_SORTED_RATIO (0.2)
+
+/* Ratio of total of elements which will be repeated. */
+#define REPEATED_RATIO (0.2)
+
+/* Return the index of BASE as interpreted as an array of elements
+ of size SIZE. */
+static inline void *
+arr (void *base, size_t idx, size_t size)
+{
+ return (void*)((uintptr_t)base + (idx * size));
+}
+
+/* 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. */
+typedef enum
+{
+ UINT8_CMP_T,
+ UINT16_CMP_T,
+ UINT32_CMP_T,
+ UINT64_CMP_T
+} type_cmp_t;
+
+static type_cmp_t
+__attribute__((used))
+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
+__attribute__((used))
+uint_t_cmp (const void *a, const void *b, void *arg)
+{
+ type_cmp_t type = *(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 void
+seq (void *elem, size_t type_size, uint64_t value)
+{
+ if (type_size == sizeof (uint8_t))
+ {
+ uint8_t x = value;
+ memcpy (elem, &x, type_size);
+ }
+ else if (type_size == sizeof (uint16_t))
+ {
+ uint16_t x = value;
+ memcpy (elem, &x, type_size);
+ }
+ else if (type_size == sizeof (uint32_t))
+ {
+ uint32_t x = value;
+ memcpy (elem, &x, type_size);
+ }
+ else if (type_size == sizeof (uint64_t))
+ memcpy (elem, &value, type_size);
+ else
+ memset (elem, value, type_size);
+}
+
+static void
+random_init (void)
+{
+ unsigned short seed16v[3];
+ if (getrandom (seed16v, sizeof seed16v, 0) == -1)
+ srand (time (NULL));
+ else
+ seed48 (seed16v);
+}
+
+static uint32_t
+random_uniform_distribution (uint32_t min, uint32_t max)
+{
+ uint32_t ret;
+ uint32_t range = max - min;
+ /* It assumes the input random number RANDOM range is as larger or equal
+ than the RANGE, so the result will either returned or downscaled. */
+ if (range != UINT32_MAX)
+ {
+ uint32_t urange = range + 1; /* range can be 0. */
+ uint32_t scaling = UINT32_MAX / urange;
+ uint32_t past = urange * scaling;
+ do
+ ret = lrand48 ();
+ while (ret >= past);
+ ret /= scaling;
+ }
+ else
+ ret = lrand48 ();
+ return ret + min;
+}
+
+void
+random_buf (void *buf, size_t nbytes)
+{
+ size_t nw = nbytes / sizeof (uint32_t);
+ for (size_t i = 0; i < nw; i++)
+ {
+ uint32_t r = lrand48 ();
+ memcpy (buf, &r, sizeof (uint32_t));
+ buf = (void*)((uintptr_t)buf + sizeof (uint32_t));
+ }
+
+ size_t nb = nbytes % sizeof (uint32_t);
+ if (nb != 0)
+ {
+ uint32_t r = lrand48 ();
+ memcpy (buf, &r, nb);
+ }
+}
+
+static void *
+create_array (size_t nmemb, size_t type_size, arraytype_t type)
+{
+ size_t size = nmemb * type_size;
+ void *array = xmalloc (size);
+
+ switch (type)
+ {
+ case SORTED:
+ for (uint64_t i = 0; i < nmemb; i++)
+ seq (arr (array, i, type_size), type_size, i);
+ break;
+
+ case MOSTLYSORTED:
+ {
+ for (uint64_t i = 0; i < nmemb; i++)
+ seq (arr (array, i, type_size), type_size, i);
+
+ /* Change UNSORTED elements (based on MostlySortedRatio ratio)
+ in the sorted array. */
+ size_t unsorted = (size_t)(nmemb * MOSTLY_SORTED_RATIO);
+ for (size_t i = 0; i < unsorted; i++)
+ {
+ size_t pos = random_uniform_distribution (0, nmemb - 1);
+ random_buf (arr (array, pos, type_size), type_size);
+ }
+ }
+ break;
+
+ case RANDOM:
+ random_buf (array, size);
+ break;
+
+ case REPEATED:
+ {
+ random_buf (array, size);
+
+ void *randelem = xmalloc (type_size);
+ random_buf (randelem, type_size);
+
+ /* Repeat REPEATED elements (based on RepeatRatio ratio) in the random
+ array. */
+ size_t repeated = (size_t)(nmemb * REPEATED_RATIO);
+ for (size_t i = 0; i < repeated; i++)
+ {
+ size_t pos = random_uniform_distribution (0, nmemb - 1);
+ memcpy (arr (array, pos, type_size), randelem, type_size);
+ }
+
+ free (randelem);
+ }
+ break;
+
+ case BITONIC:
+ {
+ uint64_t i;
+ for (i = 0; i < nmemb / 2; i++)
+ seq (arr (array, i, type_size), type_size, i);
+ for ( ; i < nmemb; i++)
+ seq (arr (array, i, type_size), type_size, (nmemb - 1) - i);
+ }
+ break;
+ }
+
+ return array;
+}
+
+typedef int (*cmpfunc_t)(const void *, const void *);
diff --git a/stdlib/tst-qsort3.c b/stdlib/tst-qsort3.c
new file mode 100644
index 0000000000..d946f37c9d
--- /dev/null
+++ b/stdlib/tst-qsort3.c
@@ -0,0 +1,138 @@
+/* qsorte if (type_size == sizeof (uint32_t))
+ _r) generic tests.
+ Copyright (C) 2021 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 <array_length.h>
+#include <errno.h>
+#include <getopt.h>
+#include <stdio.h>
+#include <stdbool.h>
+#include <support/check.h>
+#include <support/support.h>
+#include <support/test-driver.h>
+
+#include <stdlib/tst-qsort-common.c>
+
+/* Check if ARRAY of total NMEMB element of size SIZE is sorted
+ based on CMPFUNC. */
+static void
+check_array (void *array, size_t nmemb, size_t type_size,
+ cmpfunc_t cmpfunc)
+{
+ for (size_t i = 1; i < nmemb; i++)
+ {
+ int ret = cmpfunc (arr (array, i, type_size),
+ arr (array, i-1, type_size));
+ TEST_VERIFY_EXIT (ret >= 0);
+ }
+}
+
+static void
+check_qsort (size_t nelem, size_t type_size, arraytype_t type,
+ cmpfunc_t cmpfunc)
+{
+ void *array = create_array (nelem, type_size, type);
+
+ qsort (array, nelem, type_size, cmpfunc);
+
+ check_array (array, nelem, type_size, cmpfunc);
+
+ free (array);
+}
+
+static void
+check_qsort_r (size_t nelem, size_t type_size, arraytype_t type,
+ cmpfunc_t cmpfunc)
+{
+ void *array = create_array (nelem, type_size, type);
+
+ type_cmp_t typecmp = uint_t_cmp_type (type_size);
+ qsort_r (array, nelem, type_size, uint_t_cmp, &typecmp);
+
+ check_array (array, nelem, type_size, cmpfunc);
+
+ free (array);
+}
+
+static int
+do_test (void)
+{
+ random_init ();
+
+ struct test_t
+ {
+ size_t type_size;
+ cmpfunc_t cmpfunc;
+ };
+ static const struct test_t 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 },
+ };
+
+ struct array_t
+ {
+ arraytype_t type;
+ const char *name;
+ };
+ static const struct array_t arraytypes[] =
+ {
+ { SORTED, "SORTED" },
+ { MOSTLYSORTED, "MOSTLYSORTED" },
+ { RANDOM, "RANDOM" },
+ { REPEATED, "REPEATED" },
+ { BITONIC, "BITONIC" },
+ };
+
+ static const size_t nelems[] =
+ { 0, 1, 16, 32, 64, 128, 256, 4096, 16384, 262144 };
+
+ for (const struct test_t *test = tests; test < array_end (tests); ++test)
+ {
+ if (test_verbose > 0)
+ printf ("info: testing qsort with type_size=%zu\n", test->type_size);
+ for (const struct array_t *arraytype = arraytypes;
+ arraytype < array_end (arraytypes);
+ ++arraytype)
+ {
+ if (test_verbose > 0)
+ printf (" distribution=%s\n", arraytype->name);
+ for (const size_t *nelem = nelems;
+ nelem < array_end (nelems);
+ ++nelem)
+ {
+ if (test_verbose > 0)
+ printf (" i nelem=%zu, total size=%zu\n", *nelem,
+ *nelem * test->type_size);
+
+ check_qsort (*nelem, test->type_size, arraytype->type,
+ test->cmpfunc);
+ check_qsort_r (*nelem, test->type_size, arraytype->type,
+ test->cmpfunc);
+ }
+ }
+ }
+
+ return 0;
+}
+
+#include <support/test-driver.c>
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2021-09-06 18:44 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-09-06 18:22 [glibc/azanella/qsort-fixes] stdlib: Add more qsort{_r} coverage Adhemerval Zanella
2021-09-06 18:44 Adhemerval Zanella
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).