[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[PATCH] qsort_r: new module, for GNU-style qsort_r
|
From: |
Paul Eggert |
|
Subject: |
[PATCH] qsort_r: new module, for GNU-style qsort_r |
|
Date: |
Fri, 29 Aug 2014 13:50:48 -0700 |
This works even on FreeBSD, which has an incompatible qsort_r API.
* MODULES.html.sh: Add it.
* doc/glibc-functions/qsort_r.texi: It's now supported.
* lib/qsort.c: New file, taken from glibc with minor changes
inside "#ifndef _LIBC" and with an unnecessary "#include <alloca.h>"
removed.
* lib/qsort_r.c: New file, compiled only on FreeBSD.
* lib/stdlib.in.h (qsort_r): Declare in the usual way.
* m4/stdlib_h.m4 (gl_STDLIB_H_DEFAULTS):
* modules/qsort_r, modules/qsort_r-tests: New files.
* modules/stdlib (Makefile): Set up its defaults.
* tests/test-qsort_r.c: New file.
---
ChangeLog | 16 +++
MODULES.html.sh | 1 +
doc/glibc-functions/qsort_r.texi | 9 +-
lib/qsort.c | 254 +++++++++++++++++++++++++++++++++++++++
lib/qsort_r.c | 51 ++++++++
lib/stdlib.in.h | 23 ++++
m4/stdlib_h.m4 | 2 +
modules/qsort_r | 31 +++++
modules/qsort_r-tests | 10 ++
modules/stdlib | 2 +
tests/test-qsort_r.c | 47 ++++++++
11 files changed, 443 insertions(+), 3 deletions(-)
create mode 100644 lib/qsort.c
create mode 100644 lib/qsort_r.c
create mode 100644 modules/qsort_r
create mode 100644 modules/qsort_r-tests
create mode 100644 tests/test-qsort_r.c
diff --git a/ChangeLog b/ChangeLog
index f440efe..a1f9602 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,19 @@
+2014-08-29 Paul Eggert <address@hidden>
+
+ qsort_r: new module, for GNU-style qsort_r
+ This works even on FreeBSD, which has an incompatible qsort_r API.
+ * MODULES.html.sh: Add it.
+ * doc/glibc-functions/qsort_r.texi: It's now supported.
+ * lib/qsort.c: New file, taken from glibc with minor changes
+ inside "#ifndef _LIBC" and with an unnecessary "#include <alloca.h>"
+ removed.
+ * lib/qsort_r.c: New file, compiled only on FreeBSD.
+ * lib/stdlib.in.h (qsort_r): Declare in the usual way.
+ * m4/stdlib_h.m4 (gl_STDLIB_H_DEFAULTS):
+ * modules/qsort_r, modules/qsort_r-tests: New files.
+ * modules/stdlib (Makefile): Set up its defaults.
+ * tests/test-qsort_r.c: New file.
+
2014-08-08 Paul Eggert <address@hidden>
vla: new module
diff --git a/MODULES.html.sh b/MODULES.html.sh
index 6c4520a..db66253 100755
--- a/MODULES.html.sh
+++ b/MODULES.html.sh
@@ -1712,6 +1712,7 @@ func_all_modules ()
func_begin_table
func_module array-mergesort
func_module mpsort
+ func_module qsort_r
func_end_table
element="Date and time <time.h>"
diff --git a/doc/glibc-functions/qsort_r.texi b/doc/glibc-functions/qsort_r.texi
index 94df972..ced8c70 100644
--- a/doc/glibc-functions/qsort_r.texi
+++ b/doc/glibc-functions/qsort_r.texi
@@ -6,11 +6,14 @@ Gnulib module: ---
Portability problems fixed by Gnulib:
@itemize
address@hidden
+This function has an incompatible API on some platforms:
+FreeBSD 10.
address@hidden
+This function is missing on some platforms:
+glibc 2.7, NetBSD 5.0, OpenBSD 3.8, Minix 3.1.8, AIX 7.1, HP-UX 11.31, IRIX
6.5, OSF/1 5.1, Solaris 11 2011-11, Cygwin, mingw, MSVC 9, Interix 3.5, BeOS.
@end itemize
Portability problems not fixed by Gnulib:
@itemize
address@hidden
-This function is missing on some platforms:
-glibc 2.7, NetBSD 5.0, OpenBSD 3.8, Minix 3.1.8, AIX 7.1, HP-UX 11.31, IRIX
6.5, OSF/1 5.1, Solaris 11 2011-11, Cygwin, mingw, MSVC 9, Interix 3.5, BeOS.
@end itemize
diff --git a/lib/qsort.c b/lib/qsort.c
new file mode 100644
index 0000000..a6c33eb
--- /dev/null
+++ b/lib/qsort.c
@@ -0,0 +1,254 @@
+/* Copyright (C) 1991-2014 Free Software Foundation, Inc.
+ This file is part of the GNU C Library.
+ Written by Douglas C. Schmidt (address@hidden).
+
+ 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/>. */
+
+/* If you consider tuning this algorithm, you should consult first:
+ Engineering a sort function; Jon Bentley and M. Douglas McIlroy;
+ Software - Practice and Experience; Vol. 23 (11), 1249-1265, 1993. */
+
+#include <limits.h>
+#include <stdlib.h>
+#include <string.h>
+
+#ifndef _LIBC
+# define _quicksort qsort_r
+# define __compar_d_fn_t compar_d_fn_t
+typedef int (*compar_d_fn_t) (const void *, const void *, void *);
+#endif
+
+/* Byte-wise swap two items of size SIZE. */
+#define SWAP(a, b, size) \
+ do \
+ { \
+ size_t __size = (size); \
+ char *__a = (a), *__b = (b); \
+ do \
+ { \
+ char __tmp = *__a; \
+ *__a++ = *__b; \
+ *__b++ = __tmp; \
+ } while (--__size > 0); \
+ } while (0)
+
+/* Discontinue quicksort algorithm when partition gets below this size.
+ This particular magic number was chosen to work best on a Sun 4/260. */
+#define MAX_THRESH 4
+
+/* Stack node declarations used to store unfulfilled partition obligations. */
+typedef struct
+ {
+ char *lo;
+ char *hi;
+ } stack_node;
+
+/* The next 4 #defines implement a very fast in-line stack abstraction. */
+/* The stack needs log (total_elements) entries (we could even subtract
+ log(MAX_THRESH)). Since total_elements has type size_t, we get as
+ upper bound for log (total_elements):
+ bits per byte (CHAR_BIT) * sizeof(size_t). */
+#define STACK_SIZE (CHAR_BIT * sizeof(size_t))
+#define PUSH(low, high) ((void) ((top->lo = (low)), (top->hi = (high)),
++top))
+#define POP(low, high) ((void) (--top, (low = top->lo), (high =
top->hi)))
+#define STACK_NOT_EMPTY (stack < top)
+
+
+/* Order size using quicksort. This implementation incorporates
+ four optimizations discussed in Sedgewick:
+
+ 1. Non-recursive, using an explicit stack of pointer that store the
+ next array partition to sort. To save time, this maximum amount
+ of space required to store an array of SIZE_MAX is allocated on the
+ stack. Assuming a 32-bit (64 bit) integer for size_t, this needs
+ only 32 * sizeof(stack_node) == 256 bytes (for 64 bit: 1024 bytes).
+ Pretty cheap, actually.
+
+ 2. Chose the pivot element using a median-of-three decision tree.
+ This reduces the probability of selecting a bad pivot value and
+ eliminates certain extraneous comparisons.
+
+ 3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving
+ insertion sort to order the MAX_THRESH items within each partition.
+ This is a big win, since insertion sort is faster for small, mostly
+ sorted array segments.
+
+ 4. The larger of the two sub-partitions is always pushed onto the
+ stack first, with the algorithm then concentrating on the
+ smaller partition. This *guarantees* no more than log (total_elems)
+ stack size is needed (actually O(1) in this case)! */
+
+void
+_quicksort (void *const pbase, size_t total_elems, size_t size,
+ __compar_d_fn_t cmp, void *arg)
+{
+ char *base_ptr = (char *) pbase;
+
+ const size_t max_thresh = MAX_THRESH * size;
+
+ if (total_elems == 0)
+ /* Avoid lossage with unsigned arithmetic below. */
+ return;
+
+ if (total_elems > MAX_THRESH)
+ {
+ char *lo = base_ptr;
+ char *hi = &lo[size * (total_elems - 1)];
+ stack_node stack[STACK_SIZE];
+ stack_node *top = stack;
+
+ PUSH (NULL, NULL);
+
+ while (STACK_NOT_EMPTY)
+ {
+ char *left_ptr;
+ char *right_ptr;
+
+ /* 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
+ skips a comparison for both the LEFT_PTR and RIGHT_PTR in
+ the while loops. */
+
+ char *mid = lo + size * ((hi - lo) / size >> 1);
+
+ if ((*cmp) ((void *) mid, (void *) lo, arg) < 0)
+ SWAP (mid, lo, size);
+ if ((*cmp) ((void *) hi, (void *) mid, arg) < 0)
+ SWAP (mid, hi, size);
+ else
+ goto jump_over;
+ if ((*cmp) ((void *) mid, (void *) lo, arg) < 0)
+ SWAP (mid, lo, size);
+ jump_over:;
+
+ left_ptr = lo + size;
+ right_ptr = hi - size;
+
+ /* Here's the famous ``collapse the walls'' section of quicksort.
+ Gotta like those tight inner loops! They are the main reason
+ that this algorithm runs much faster than others. */
+ do
+ {
+ while ((*cmp) ((void *) left_ptr, (void *) mid, arg) < 0)
+ left_ptr += size;
+
+ while ((*cmp) ((void *) mid, (void *) right_ptr, arg) < 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;
+ }
+ else if (left_ptr == right_ptr)
+ {
+ left_ptr += size;
+ right_ptr -= size;
+ break;
+ }
+ }
+ while (left_ptr <= right_ptr);
+
+ /* Set up pointers for next iteration. First determine whether
+ left and right partitions are below the threshold size. If so,
+ ignore one or both. Otherwise, push the larger partition's
+ bounds on the stack and continue sorting the smaller one. */
+
+ if ((size_t) (right_ptr - lo) <= max_thresh)
+ {
+ if ((size_t) (hi - left_ptr) <= max_thresh)
+ /* Ignore both small partitions. */
+ POP (lo, hi);
+ else
+ /* Ignore small left partition. */
+ lo = left_ptr;
+ }
+ else if ((size_t) (hi - left_ptr) <= max_thresh)
+ /* Ignore small right partition. */
+ hi = right_ptr;
+ else if ((right_ptr - lo) > (hi - left_ptr))
+ {
+ /* Push larger left partition indices. */
+ PUSH (lo, right_ptr);
+ lo = left_ptr;
+ }
+ else
+ {
+ /* Push larger right partition indices. */
+ PUSH (left_ptr, hi);
+ hi = right_ptr;
+ }
+ }
+ }
+
+ /* Once the BASE_PTR array is partially sorted by quicksort the rest
+ is completely sorted using insertion sort, since this is efficient
+ for partitions below MAX_THRESH size. BASE_PTR points to the beginning
+ of the array to sort, and END_PTR points at the very last element in
+ the array (*not* one beyond it!). */
+
+#define min(x, y) ((x) < (y) ? (x) : (y))
+
+ {
+ char *const end_ptr = &base_ptr[size * (total_elems - 1)];
+ char *tmp_ptr = base_ptr;
+ char *thresh = min(end_ptr, base_ptr + max_thresh);
+ char *run_ptr;
+
+ /* Find smallest element in first threshold and place it at the
+ array's beginning. This is the smallest array element,
+ and the operation speeds up insertion sort's inner loop. */
+
+ for (run_ptr = tmp_ptr + size; run_ptr <= thresh; run_ptr += size)
+ if ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, arg) < 0)
+ tmp_ptr = run_ptr;
+
+ if (tmp_ptr != base_ptr)
+ SWAP (tmp_ptr, base_ptr, size);
+
+ /* Insertion sort, running from left-hand-side up to right-hand-side. */
+
+ run_ptr = base_ptr + size;
+ while ((run_ptr += size) <= end_ptr)
+ {
+ tmp_ptr = run_ptr - size;
+ while ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, arg) < 0)
+ tmp_ptr -= size;
+
+ tmp_ptr += size;
+ if (tmp_ptr != run_ptr)
+ {
+ char *trav;
+
+ trav = run_ptr + size;
+ while (--trav >= run_ptr)
+ {
+ char c = *trav;
+ char *hi, *lo;
+
+ for (hi = lo = trav; (lo -= size) >= tmp_ptr; hi = lo)
+ *hi = *lo;
+ *hi = c;
+ }
+ }
+ }
+ }
+}
diff --git a/lib/qsort_r.c b/lib/qsort_r.c
new file mode 100644
index 0000000..ad68efa
--- /dev/null
+++ b/lib/qsort_r.c
@@ -0,0 +1,51 @@
+/* Reentrant sort function.
+
+ Copyright 2014 Free Software Foundation, Inc.
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2, or (at your option)
+ any later version.
+
+ This program 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 General Public License for more details.
+
+ You should have received a copy of the GNU General Public License along
+ with this program; if not, see <http://www.gnu.org/licenses/>. */
+
+/* Written by Paul Eggert. */
+
+#include <config.h>
+
+#include <stdlib.h>
+
+/* This file is compiled only when the system has a qsort_r that needs
+ to be replaced because it has the BSD signature rather than the GNU
+ signature. */
+
+struct thunk
+{
+ int (*cmp) (void const *, void const *, void *);
+ void *arg;
+};
+
+static int
+thunk_cmp (void *thunk, void const *a, void const *b)
+{
+ struct thunk *th = thunk;
+ return th->cmp (a, b, th->arg);
+}
+
+void
+qsort_r (void *base, size_t nmemb, size_t size,
+ int (*cmp) (void const *, void const *, void *),
+ void *arg)
+{
+# undef qsort_r
+ struct thunk thunk;
+ thunk.cmp = cmp;
+ thunk.arg = arg;
+ qsort_r (base, nmemb, size, &thunk, thunk_cmp);
+}
diff --git a/lib/stdlib.in.h b/lib/stdlib.in.h
index 46e10db..ee64324 100644
--- a/lib/stdlib.in.h
+++ b/lib/stdlib.in.h
@@ -520,6 +520,29 @@ _GL_CXXALIAS_SYS (putenv, int, (char *string));
_GL_CXXALIASWARN (putenv);
#endif
+#if @GNULIB_QSORT_R@
+# if @REPLACE_QSORT_R@
+# if !(defined __cplusplus && defined GNULIB_NAMESPACE)
+# undef qsort_r
+# define qsort_r rpl_qsort_r
+# endif
+_GL_FUNCDECL_RPL (qsort_r, void, (void *base, size_t nmemb, size_t size,
+ int (*compare) (void const *, void const *,
+ void *),
+ void *arg) _GL_ARG_NONNULL ((1, 4)));
+_GL_CXXALIAS_RPL (qsort_r, void, (void *base, size_t nmemb, size_t size,
+ int (*compare) (void const *, void const *,
+ void *),
+ void *arg));
+# else
+_GL_CXXALIAS_SYS (qsort_r, void, (void *base, size_t nmemb, size_t size,
+ int (*compare) (void const *, void const *,
+ void *),
+ void *arg));
+# endif
+_GL_CXXALIASWARN (qsort_r);
+#endif
+
#if @GNULIB_RANDOM_R@
# if address@hidden@
diff --git a/m4/stdlib_h.m4 b/m4/stdlib_h.m4
index 03b448b..86aff16 100644
--- a/m4/stdlib_h.m4
+++ b/m4/stdlib_h.m4
@@ -55,6 +55,7 @@ AC_DEFUN([gl_STDLIB_H_DEFAULTS],
GNULIB_PTSNAME=0; AC_SUBST([GNULIB_PTSNAME])
GNULIB_PTSNAME_R=0; AC_SUBST([GNULIB_PTSNAME_R])
GNULIB_PUTENV=0; AC_SUBST([GNULIB_PUTENV])
+ GNULIB_QSORT_R=0; AC_SUBST([GNULIB_QSORT_R])
GNULIB_RANDOM=0; AC_SUBST([GNULIB_RANDOM])
GNULIB_RANDOM_R=0; AC_SUBST([GNULIB_RANDOM_R])
GNULIB_REALLOC_POSIX=0; AC_SUBST([GNULIB_REALLOC_POSIX])
@@ -107,6 +108,7 @@ AC_DEFUN([gl_STDLIB_H_DEFAULTS],
REPLACE_PTSNAME=0; AC_SUBST([REPLACE_PTSNAME])
REPLACE_PTSNAME_R=0; AC_SUBST([REPLACE_PTSNAME_R])
REPLACE_PUTENV=0; AC_SUBST([REPLACE_PUTENV])
+ REPLACE_QSORT_R=0; AC_SUBST([REPLACE_QSORT_R])
REPLACE_RANDOM_R=0; AC_SUBST([REPLACE_RANDOM_R])
REPLACE_REALLOC=0; AC_SUBST([REPLACE_REALLOC])
REPLACE_REALPATH=0; AC_SUBST([REPLACE_REALPATH])
diff --git a/modules/qsort_r b/modules/qsort_r
new file mode 100644
index 0000000..52b57c0
--- /dev/null
+++ b/modules/qsort_r
@@ -0,0 +1,31 @@
+Description:
+Reentrant sort function with GNU signature
+
+Files:
+lib/qsort.c
+lib/qsort_r.c
+m4/qsort_r.m4
+
+Depends-on:
+extensions
+stdlib
+
+configure.ac:
+gl_FUNC_QSORT_R
+if test $HAVE_QSORT_R = 0; then
+ AC_LIBOBJ([qsort])
+elif test $REPLACE_QSORT_R = 1; then
+ AC_LIBOBJ([qsort_r])
+fi
+gl_STDLIB_MODULE_INDICATOR([qsort_r])
+
+Makefile.am:
+
+Include:
+<stdlib.h>
+
+License:
+LGPLv2+
+
+Maintainer:
+Paul Eggert
diff --git a/modules/qsort_r-tests b/modules/qsort_r-tests
new file mode 100644
index 0000000..428baf1
--- /dev/null
+++ b/modules/qsort_r-tests
@@ -0,0 +1,10 @@
+Files:
+tests/test-qsort_r.c
+
+Depends-on:
+
+configure.ac:
+
+Makefile.am:
+TESTS += test-qsort_r
+check_PROGRAMS += test-qsort_r
diff --git a/modules/stdlib b/modules/stdlib
index 40847e9..cbc5b01 100644
--- a/modules/stdlib
+++ b/modules/stdlib
@@ -49,6 +49,7 @@ stdlib.h: stdlib.in.h $(top_builddir)/config.status
$(CXXDEFS_H) \
-e 's/@''GNULIB_PTSNAME''@/$(GNULIB_PTSNAME)/g' \
-e 's/@''GNULIB_PTSNAME_R''@/$(GNULIB_PTSNAME_R)/g' \
-e 's/@''GNULIB_PUTENV''@/$(GNULIB_PUTENV)/g' \
+ -e 's/@''GNULIB_QSORT_R''@/$(GNULIB_QSORT_R)/g' \
-e 's/@''GNULIB_RANDOM''@/$(GNULIB_RANDOM)/g' \
-e 's/@''GNULIB_RANDOM_R''@/$(GNULIB_RANDOM_R)/g' \
-e 's/@''GNULIB_REALLOC_POSIX''@/$(GNULIB_REALLOC_POSIX)/g' \
@@ -100,6 +101,7 @@ stdlib.h: stdlib.in.h $(top_builddir)/config.status
$(CXXDEFS_H) \
-e 's|@''REPLACE_PTSNAME''@|$(REPLACE_PTSNAME)|g' \
-e 's|@''REPLACE_PTSNAME_R''@|$(REPLACE_PTSNAME_R)|g' \
-e 's|@''REPLACE_PUTENV''@|$(REPLACE_PUTENV)|g' \
+ -e 's|@''REPLACE_QSORT_R''@|$(REPLACE_QSORT_R)|g' \
-e 's|@''REPLACE_RANDOM_R''@|$(REPLACE_RANDOM_R)|g' \
-e 's|@''REPLACE_REALLOC''@|$(REPLACE_REALLOC)|g' \
-e 's|@''REPLACE_REALPATH''@|$(REPLACE_REALPATH)|g' \
diff --git a/tests/test-qsort_r.c b/tests/test-qsort_r.c
new file mode 100644
index 0000000..0b840ea
--- /dev/null
+++ b/tests/test-qsort_r.c
@@ -0,0 +1,47 @@
+/* Test qsort_r.
+
+ Copyright 2014 Free Software Foundation, Inc.
+
+ This program is free software: you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 3 of the License, or
+ (at your option) any later version.
+
+ This program 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 General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program. If not, see <http://www.gnu.org/licenses/>. */
+
+/* Written by Paul Eggert. */
+
+#include <config.h>
+
+#include <stdlib.h>
+#include <string.h>
+
+int
+cmp (void const *va, void const *vb, void *varg)
+{
+ char const *a = va;
+ char const *b = vb;
+ int *arg = varg;
+ return (*a < *b ? -1 : *a > *b) * *arg;
+}
+
+int
+main (void)
+{
+ char buf[] = "thequickbrownfoxjumpedoverthelazydogs";
+ int forward = 1;
+ int reverse = -1;
+ qsort_r (buf, sizeof buf - 1, 1, cmp, &forward);
+ if (strcmp (buf, "abcddeeeefghhijklmnoooopqrrsttuuvwxyz") != 0)
+ return 1;
+ qsort_r (buf, sizeof buf - 1, 1, cmp, &reverse);
+ if (strcmp (buf, "zyxwvuuttsrrqpoooonmlkjihhgfeeeeddcba") != 0)
+ return 1;
+ return 0;
+}
--
1.9.3
- [PATCH] qsort_r: new module, for GNU-style qsort_r,
Paul Eggert <=