Module Name: src
Committed By: riastradh
Date: Sun Mar 2 16:35:41 UTC 2025
Modified Files:
src/common/lib/libc/stdlib: heapsort.c
src/distrib/sets/lists/comp: mi
src/distrib/sets/lists/debug: mi
src/distrib/sets/lists/tests: mi
src/include: stdlib.h
src/lib/libc/include: namespace.h
src/lib/libc/stdlib: Makefile.inc merge.c qsort.3 qsort.c
src/sys/lib/libkern: libkern.h
src/tests/lib/libc/stdlib: Makefile
src/tools/compat: compat_defs.h
Added Files:
src/tests/lib/libc/stdlib: h_sort.c t_sort.sh
Log Message:
libc: New _r variants of heapsort, mergesort, qsort.
Also kheapsort_r for kernel/standalone use.
These variants allow the caller to pass a cookie through to the
comparison function, e.g. if you want to sort an array of indices
into a buffer.
qsort_r is new in POSIX.1-2024; the others are obvious analogues of
our nonstandard extensions for heapsort and mergesort.
PR lib/58931: qsort_r() missing
To generate a diff of this commit:
cvs rdiff -u -r1.3 -r1.4 src/common/lib/libc/stdlib/heapsort.c
cvs rdiff -u -r1.2485 -r1.2486 src/distrib/sets/lists/comp/mi
cvs rdiff -u -r1.466 -r1.467 src/distrib/sets/lists/debug/mi
cvs rdiff -u -r1.1359 -r1.1360 src/distrib/sets/lists/tests/mi
cvs rdiff -u -r1.129 -r1.130 src/include/stdlib.h
cvs rdiff -u -r1.205 -r1.206 src/lib/libc/include/namespace.h
cvs rdiff -u -r1.103 -r1.104 src/lib/libc/stdlib/Makefile.inc
cvs rdiff -u -r1.16 -r1.17 src/lib/libc/stdlib/merge.c
cvs rdiff -u -r1.14 -r1.15 src/lib/libc/stdlib/qsort.3
cvs rdiff -u -r1.23 -r1.24 src/lib/libc/stdlib/qsort.c
cvs rdiff -u -r1.147 -r1.148 src/sys/lib/libkern/libkern.h
cvs rdiff -u -r1.34 -r1.35 src/tests/lib/libc/stdlib/Makefile
cvs rdiff -u -r0 -r1.1 src/tests/lib/libc/stdlib/h_sort.c \
src/tests/lib/libc/stdlib/t_sort.sh
cvs rdiff -u -r1.123 -r1.124 src/tools/compat/compat_defs.h
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: src/common/lib/libc/stdlib/heapsort.c
diff -u src/common/lib/libc/stdlib/heapsort.c:1.3 src/common/lib/libc/stdlib/heapsort.c:1.4
--- src/common/lib/libc/stdlib/heapsort.c:1.3 Mon Nov 17 10:21:30 2008
+++ src/common/lib/libc/stdlib/heapsort.c Sun Mar 2 16:35:40 2025
@@ -1,4 +1,4 @@
-/* $NetBSD: heapsort.c,v 1.3 2008/11/17 10:21:30 jnemeth Exp $ */
+/* $NetBSD: heapsort.c,v 1.4 2025/03/02 16:35:40 riastradh Exp $ */
/*-
* Copyright (c) 1991, 1993
@@ -39,6 +39,7 @@
* XXX rename the versions found in the host's headers by mistake!
*/
#undef heapsort
+#undef heapsort_r
#endif
#include <sys/cdefs.h>
@@ -46,7 +47,7 @@
#if 0
static char sccsid[] = "from: @(#)heapsort.c 8.1 (Berkeley) 6/4/93";
#else
-__RCSID("$NetBSD: heapsort.c,v 1.3 2008/11/17 10:21:30 jnemeth Exp $");
+__RCSID("$NetBSD: heapsort.c,v 1.4 2025/03/02 16:35:40 riastradh Exp $");
#endif
#endif /* LIBC_SCCS and not lint */
@@ -65,10 +66,12 @@ __RCSID("$NetBSD: heapsort.c,v 1.3 2008/
#if HAVE_NBTOOL_CONFIG_H
/* XXX Now, re-apply the renaming that we undid above. */
#define heapsort __nbcompat_heapsort
+#define heapsort_r __nbcompat_heapsort_r
#endif
#ifdef __weak_alias
__weak_alias(heapsort,_heapsort)
+__weak_alias(heapsort_r,_heapsort_r)
#endif
#endif /* _KERNEL || _STANDALONE */
@@ -109,12 +112,13 @@ __weak_alias(heapsort,_heapsort)
for (par_i = initval; (child_i = par_i * 2) <= nmemb; \
par_i = child_i) { \
child = base + child_i * size; \
- if (child_i < nmemb && compar(child, child + size) < 0) { \
+ if (child_i < nmemb && \
+ compar(child, child + size, cookie) < 0) { \
child += size; \
++child_i; \
} \
par = base + par_i * size; \
- if (compar(child, par) <= 0) \
+ if (compar(child, par, cookie) <= 0) \
break; \
SWAP(par, child, count, size, tmp); \
} \
@@ -140,7 +144,8 @@ __weak_alias(heapsort,_heapsort)
#define SELECT(par_i, child_i, nmemb, par, child, size, k, count, tmp1, tmp2) { \
for (par_i = 1; (child_i = par_i * 2) <= nmemb; par_i = child_i) { \
child = base + child_i * size; \
- if (child_i < nmemb && compar(child, child + size) < 0) { \
+ if (child_i < nmemb && \
+ compar(child, child + size, cookie) < 0) { \
child += size; \
++child_i; \
} \
@@ -152,7 +157,7 @@ __weak_alias(heapsort,_heapsort)
par_i = child_i / 2; \
child = base + child_i * size; \
par = base + par_i * size; \
- if (child_i == 1 || compar(k, par) < 0) { \
+ if (child_i == 1 || compar(k, par, cookie) < 0) { \
COPY(child, k, count, size, tmp1, tmp2); \
break; \
} \
@@ -169,12 +174,13 @@ __weak_alias(heapsort,_heapsort)
*/
#if defined(_KERNEL) || defined(_STANDALONE)
int
-kheapsort(void *vbase, size_t nmemb, size_t size,
- int (*compar)(const void *, const void *), void *k)
+kheapsort_r(void *vbase, size_t nmemb, size_t size,
+ int (*compar)(const void *, const void *, void *), void *cookie,
+ void *k)
#else
int
-heapsort(void *vbase, size_t nmemb, size_t size,
- int (*compar)(const void *, const void *))
+heapsort_r(void *vbase, size_t nmemb, size_t size,
+ int (*compar)(const void *, const void *, void *), void *cookie)
#endif
{
size_t cnt, i, j, l;
@@ -227,3 +233,29 @@ heapsort(void *vbase, size_t nmemb, size
#endif
return (0);
}
+
+static int
+cmpnocookie(const void *a, const void *b, void *cookie)
+{
+ int (*cmp)(const void *, const void *) = cookie;
+
+ return cmp(a, b);
+}
+
+int
+#if defined(_KERNEL) || defined(_STANDALONE)
+kheapsort(void *a, size_t n, size_t es,
+ int (*cmp)(const void *, const void *),
+ void *k)
+#else
+heapsort(void *a, size_t n, size_t es,
+ int (*cmp)(const void *, const void *))
+#endif
+{
+
+#if defined(_KERNEL) || defined(_STANDALONE)
+ return kheapsort_r(a, n, es, cmpnocookie, cmp, k);
+#else
+ return heapsort_r(a, n, es, cmpnocookie, cmp);
+#endif
+}
Index: src/distrib/sets/lists/comp/mi
diff -u src/distrib/sets/lists/comp/mi:1.2485 src/distrib/sets/lists/comp/mi:1.2486
--- src/distrib/sets/lists/comp/mi:1.2485 Sun Jan 26 16:35:42 2025
+++ src/distrib/sets/lists/comp/mi Sun Mar 2 16:35:40 2025
@@ -1,4 +1,4 @@
-# $NetBSD: mi,v 1.2485 2025/01/26 16:35:42 christos Exp $
+# $NetBSD: mi,v 1.2486 2025/03/02 16:35:40 riastradh Exp $
#
# Note: don't delete entries from here - mark them as "obsolete" instead.
./etc/mtree/set.comp comp-sys-root
@@ -8183,6 +8183,7 @@
./usr/share/man/cat3/hdestroy1_r.0 comp-c-catman .cat
./usr/share/man/cat3/hdestroy_r.0 comp-c-catman .cat
./usr/share/man/cat3/heapsort.0 comp-c-catman .cat
+./usr/share/man/cat3/heapsort_r.0 comp-c-catman .cat
./usr/share/man/cat3/herror.0 comp-c-catman .cat
./usr/share/man/cat3/hesiod.0 comp-c-catman hesiod,.cat
./usr/share/man/cat3/hesiod_end.0 comp-c-catman hesiod,.cat
@@ -9292,6 +9293,7 @@
./usr/share/man/cat3/menu_win.0 comp-c-catman .cat
./usr/share/man/cat3/menus.0 comp-c-catman .cat
./usr/share/man/cat3/mergesort.0 comp-c-catman .cat
+./usr/share/man/cat3/mergesort_r.0 comp-c-catman .cat
./usr/share/man/cat3/meta.0 comp-c-catman .cat
./usr/share/man/cat3/mi_vector_hash.0 comp-c-catman .cat
./usr/share/man/cat3/minor.0 comp-c-catman .cat
@@ -10149,6 +10151,7 @@
./usr/share/man/cat3/qdiv.0 comp-c-catman .cat
./usr/share/man/cat3/qiflush.0 comp-c-catman .cat
./usr/share/man/cat3/qsort.0 comp-c-catman .cat
+./usr/share/man/cat3/qsort_r.0 comp-c-catman .cat
./usr/share/man/cat3/queue.0 comp-c-catman .cat
./usr/share/man/cat3/quick_exit.0 comp-c-catman .cat
./usr/share/man/cat3/quota_close.0 comp-c-catman .cat
@@ -16723,6 +16726,7 @@
./usr/share/man/html3/hdestroy1_r.html comp-c-htmlman html
./usr/share/man/html3/hdestroy_r.html comp-c-htmlman html
./usr/share/man/html3/heapsort.html comp-c-htmlman html
+./usr/share/man/html3/heapsort_r.html comp-c-htmlman html
./usr/share/man/html3/herror.html comp-c-htmlman html
./usr/share/man/html3/hesiod.html comp-c-htmlman hesiod,html
./usr/share/man/html3/hesiod_end.html comp-c-htmlman hesiod,html
@@ -17800,6 +17804,7 @@
./usr/share/man/html3/menu_win.html comp-c-htmlman html
./usr/share/man/html3/menus.html comp-c-htmlman html
./usr/share/man/html3/mergesort.html comp-c-htmlman html
+./usr/share/man/html3/mergesort_r.html comp-c-htmlman html
./usr/share/man/html3/meta.html comp-c-htmlman html
./usr/share/man/html3/mi_vector_hash.html comp-c-htmlman html
./usr/share/man/html3/minor.html comp-c-htmlman html
@@ -18674,6 +18679,7 @@
./usr/share/man/html3/qdiv.html comp-c-htmlman html
./usr/share/man/html3/qiflush.html comp-c-htmlman html
./usr/share/man/html3/qsort.html comp-c-htmlman html
+./usr/share/man/html3/qsort_r.html comp-c-htmlman html
./usr/share/man/html3/queue.html comp-c-htmlman html
./usr/share/man/html3/quick_exit.html comp-c-htmlman html
./usr/share/man/html3/quota_close.html comp-c-htmlman html
@@ -25207,6 +25213,7 @@
./usr/share/man/man3/hdestroy1_r.3 comp-c-man .man
./usr/share/man/man3/hdestroy_r.3 comp-c-man .man
./usr/share/man/man3/heapsort.3 comp-c-man .man
+./usr/share/man/man3/heapsort_r.3 comp-c-man .man
./usr/share/man/man3/herror.3 comp-c-man .man
./usr/share/man/man3/hesiod.3 comp-c-man hesiod,.man
./usr/share/man/man3/hesiod_end.3 comp-c-man hesiod,.man
@@ -26317,6 +26324,7 @@
./usr/share/man/man3/menu_win.3 comp-c-man .man
./usr/share/man/man3/menus.3 comp-c-man .man
./usr/share/man/man3/mergesort.3 comp-c-man .man
+./usr/share/man/man3/mergesort_r.3 comp-c-man .man
./usr/share/man/man3/meta.3 comp-c-man .man
./usr/share/man/man3/mi_vector_hash.3 comp-c-man .man
./usr/share/man/man3/minor.3 comp-c-man .man
@@ -27197,6 +27205,7 @@
./usr/share/man/man3/qdiv.3 comp-c-man .man
./usr/share/man/man3/qiflush.3 comp-c-man .man
./usr/share/man/man3/qsort.3 comp-c-man .man
+./usr/share/man/man3/qsort_r.3 comp-c-man .man
./usr/share/man/man3/queue.3 comp-c-man .man
./usr/share/man/man3/quick_exit.3 comp-c-man .man
./usr/share/man/man3/quota_close.3 comp-c-man .man
Index: src/distrib/sets/lists/debug/mi
diff -u src/distrib/sets/lists/debug/mi:1.466 src/distrib/sets/lists/debug/mi:1.467
--- src/distrib/sets/lists/debug/mi:1.466 Thu Feb 27 00:55:31 2025
+++ src/distrib/sets/lists/debug/mi Sun Mar 2 16:35:40 2025
@@ -1,4 +1,4 @@
-# $NetBSD: mi,v 1.466 2025/02/27 00:55:31 riastradh Exp $
+# $NetBSD: mi,v 1.467 2025/03/02 16:35:40 riastradh Exp $
#
./etc/mtree/set.debug comp-sys-root
./usr/lib comp-sys-usr compatdir
@@ -2162,6 +2162,7 @@
./usr/libdata/debug/usr/tests/lib/libc/stdlib/h_atexit.debug tests-lib-debug debug,atf,compattestfile
./usr/libdata/debug/usr/tests/lib/libc/stdlib/h_getopt.debug tests-lib-debug debug,atf,compattestfile
./usr/libdata/debug/usr/tests/lib/libc/stdlib/h_getopt_long.debug tests-lib-debug debug,atf,compattestfile
+./usr/libdata/debug/usr/tests/lib/libc/stdlib/h_sort.debug tests-lib-debug debug,atf,compattestfile
./usr/libdata/debug/usr/tests/lib/libc/stdlib/t_a64l.debug tests-lib-debug debug,atf,compattestfile
./usr/libdata/debug/usr/tests/lib/libc/stdlib/t_abs.debug tests-lib-debug debug,atf,compattestfile
./usr/libdata/debug/usr/tests/lib/libc/stdlib/t_atoi.debug tests-lib-debug debug,atf,compattestfile
Index: src/distrib/sets/lists/tests/mi
diff -u src/distrib/sets/lists/tests/mi:1.1359 src/distrib/sets/lists/tests/mi:1.1360
--- src/distrib/sets/lists/tests/mi:1.1359 Thu Feb 27 00:55:31 2025
+++ src/distrib/sets/lists/tests/mi Sun Mar 2 16:35:40 2025
@@ -1,4 +1,4 @@
-# $NetBSD: mi,v 1.1359 2025/02/27 00:55:31 riastradh Exp $
+# $NetBSD: mi,v 1.1360 2025/03/02 16:35:40 riastradh Exp $
#
# Note: don't delete entries from here - mark them as "obsolete" instead.
#
@@ -3267,6 +3267,7 @@
./usr/tests/lib/libc/stdlib/h_atexit tests-lib-tests compattestfile,atf
./usr/tests/lib/libc/stdlib/h_getopt tests-lib-tests compattestfile,atf
./usr/tests/lib/libc/stdlib/h_getopt_long tests-lib-tests compattestfile,atf
+./usr/tests/lib/libc/stdlib/h_sort tests-lib-tests compattestfile,atf
./usr/tests/lib/libc/stdlib/t_a64l tests-lib-tests compattestfile,atf
./usr/tests/lib/libc/stdlib/t_abs tests-lib-tests compattestfile,atf
./usr/tests/lib/libc/stdlib/t_atexit tests-lib-tests compattestfile,atf
@@ -3284,6 +3285,7 @@
./usr/tests/lib/libc/stdlib/t_mktemp tests-lib-tests compattestfile,atf
./usr/tests/lib/libc/stdlib/t_posix_memalign tests-lib-tests compattestfile,atf
./usr/tests/lib/libc/stdlib/t_random tests-lib-tests compattestfile,atf
+./usr/tests/lib/libc/stdlib/t_sort tests-lib-tests compattestfile,atf
./usr/tests/lib/libc/stdlib/t_strtod tests-lib-tests compattestfile,atf
./usr/tests/lib/libc/stdlib/t_strtoi tests-lib-tests compattestfile,atf
./usr/tests/lib/libc/stdlib/t_strtol tests-lib-tests compattestfile,atf
Index: src/include/stdlib.h
diff -u src/include/stdlib.h:1.129 src/include/stdlib.h:1.130
--- src/include/stdlib.h:1.129 Mon Feb 17 17:04:15 2025
+++ src/include/stdlib.h Sun Mar 2 16:35:40 2025
@@ -1,4 +1,4 @@
-/* $NetBSD: stdlib.h,v 1.129 2025/02/17 17:04:15 nia Exp $ */
+/* $NetBSD: stdlib.h,v 1.130 2025/03/02 16:35:40 riastradh Exp $ */
/*-
* Copyright (c) 1990, 1993
@@ -317,8 +317,12 @@ int getenv_r(const char *, char *, size
void cfree(void *);
int heapsort(void *, size_t, size_t, int (*)(const void *, const void *));
+int heapsort_r(void *, size_t, size_t,
+ int (*)(const void *, const void *, void *), void *);
int mergesort(void *, size_t, size_t,
int (*)(const void *, const void *));
+int mergesort_r(void *, size_t, size_t,
+ int (*)(const void *, const void *, void *), void *);
int ptsname_r(int, char *, size_t);
int radixsort(const unsigned char **, int, const unsigned char *,
unsigned);
@@ -400,6 +404,8 @@ void *reallocarray(void *, size_t, size_
#if (_POSIX_C_SOURCE - 0) >= 202405L || defined(_NETBSD_SOURCE)
int mkostemp(char *, int);
+void qsort_r(void *, size_t, size_t,
+ int (*)(const void *, const void *, void *), void *);
#endif /* _POSIX_C_SOURCE >= 202405L || _NETBSD_SOURCE */
__END_DECLS
Index: src/lib/libc/include/namespace.h
diff -u src/lib/libc/include/namespace.h:1.205 src/lib/libc/include/namespace.h:1.206
--- src/lib/libc/include/namespace.h:1.205 Sat Aug 17 21:24:53 2024
+++ src/lib/libc/include/namespace.h Sun Mar 2 16:35:41 2025
@@ -1,4 +1,4 @@
-/* $NetBSD: namespace.h,v 1.205 2024/08/17 21:24:53 riastradh Exp $ */
+/* $NetBSD: namespace.h,v 1.206 2025/03/02 16:35:41 riastradh Exp $ */
/*-
* Copyright (c) 1997-2004 The NetBSD Foundation, Inc.
@@ -437,6 +437,7 @@
#define gmtime_r _gmtime_r
#define group_from_gid _group_from_gid
#define heapsort _heapsort
+#define heapsort_r _heapsort_r
#define herror _herror
#define hes_error _hes_error
#define hes_free _hes_free
@@ -521,6 +522,7 @@
#define mbrtoc8_l _mbrtoc8_l
#define membar_producer _membar_producer
#define mergesort _mergesort
+#define mergesort_r _mergesort_r
#define mi_vector_hash _mi_vector_hash
#define mkstemp _mkstemp
#define mktime_z _mktime_z
Index: src/lib/libc/stdlib/Makefile.inc
diff -u src/lib/libc/stdlib/Makefile.inc:1.103 src/lib/libc/stdlib/Makefile.inc:1.104
--- src/lib/libc/stdlib/Makefile.inc:1.103 Mon Sep 23 15:49:42 2024
+++ src/lib/libc/stdlib/Makefile.inc Sun Mar 2 16:35:41 2025
@@ -1,4 +1,4 @@
-# $NetBSD: Makefile.inc,v 1.103 2024/09/23 15:49:42 christos Exp $
+# $NetBSD: Makefile.inc,v 1.104 2025/03/02 16:35:41 riastradh Exp $
# from: @(#)Makefile.inc 8.3 (Berkeley) 2/4/95
# stdlib sources
@@ -88,6 +88,9 @@ MLINKS+=lsearch.3 lfind.3
MLINKS+=malloc.3 calloc.3 malloc.3 realloc.3 malloc.3 free.3
MLINKS+=posix_memalign.3 aligned_alloc.3
MLINKS+=qsort.3 heapsort.3 qsort.3 mergesort.3
+MLINKS+=qsort.3 heapsort_r.3
+MLINKS+=qsort.3 mergesort_r.3
+MLINKS+=qsort.3 qsort_r.3
MLINKS+=ptsname.3 ptsname_r.3
MLINKS+=rand.3 rand_r.3
MLINKS+=rand.3 srand.3
Index: src/lib/libc/stdlib/merge.c
diff -u src/lib/libc/stdlib/merge.c:1.16 src/lib/libc/stdlib/merge.c:1.17
--- src/lib/libc/stdlib/merge.c:1.16 Wed May 23 21:21:27 2018
+++ src/lib/libc/stdlib/merge.c Sun Mar 2 16:35:41 2025
@@ -1,4 +1,4 @@
-/* $NetBSD: merge.c,v 1.16 2018/05/23 21:21:27 joerg Exp $ */
+/* $NetBSD: merge.c,v 1.17 2025/03/02 16:35:41 riastradh Exp $ */
/*-
* Copyright (c) 1992, 1993
@@ -37,7 +37,7 @@
#if 0
static char sccsid[] = "from: @(#)merge.c 8.2 (Berkeley) 2/14/94";
#else
-__RCSID("$NetBSD: merge.c,v 1.16 2018/05/23 21:21:27 joerg Exp $");
+__RCSID("$NetBSD: merge.c,v 1.17 2025/03/02 16:35:41 riastradh Exp $");
#endif
#endif /* LIBC_SCCS and not lint */
@@ -65,12 +65,13 @@ __RCSID("$NetBSD: merge.c,v 1.16 2018/05
#ifdef __weak_alias
__weak_alias(mergesort,_mergesort)
+__weak_alias(mergesort_r,_mergesort_r)
#endif
static void setup(u_char *, u_char *, size_t, size_t,
- int (*)(const void *, const void *));
+ int (*)(const void *, const void *, void *), void *);
static void insertionsort(u_char *, size_t, size_t,
- int (*)(const void *, const void *));
+ int (*)(const void *, const void *, void *), void *);
#define ISIZE sizeof(int)
#define PSIZE sizeof(u_char *)
@@ -93,7 +94,7 @@ static void insertionsort(u_char *, size
do \
*dst++ = *src++; \
while (i -= 1)
-
+
/*
* Find the next possible pointer head. (Trickery for forcing an array
* to do double duty as a linked list when objects do not align with word
@@ -107,8 +108,8 @@ static void insertionsort(u_char *, size
* Arguments are as for qsort.
*/
int
-mergesort(void *base, size_t nmemb, size_t size,
- int (*cmp)(const void *, const void *))
+mergesort_r(void *base, size_t nmemb, size_t size,
+ int (*cmp)(const void *, const void *, void *), void *cookie)
{
size_t i;
int sense;
@@ -139,7 +140,7 @@ mergesort(void *base, size_t nmemb, size
return (-1);
list1 = base;
- setup(list1, list2, nmemb, size, cmp);
+ setup(list1, list2, nmemb, size, cmp, cookie);
last = list2 + nmemb * size;
i = big = 0;
while (*EVAL(list2) != last) {
@@ -153,7 +154,7 @@ mergesort(void *base, size_t nmemb, size
p2 = *EVAL(p2);
l2 = list1 + (p2 - list2);
while (f1 < l1 && f2 < l2) {
- if ((*cmp)(f1, f2) <= 0) {
+ if ((*cmp)(f1, f2, cookie) <= 0) {
q = f2;
b = f1, t = l1;
sense = -1;
@@ -166,7 +167,8 @@ mergesort(void *base, size_t nmemb, size
#if 0
LINEAR:
#endif
- while ((b += size) < t && cmp(q, b) >sense)
+ while ((b += size) < t &&
+ cmp(q, b, cookie) >sense)
if (++i == 6) {
big = 1;
goto EXPONENTIAL;
@@ -175,15 +177,17 @@ LINEAR:
EXPONENTIAL: for (i = size; ; i <<= 1)
if ((p = (b + i)) >= t) {
if ((p = t - size) > b &&
- (*cmp)(q, p) <= sense)
+ ((*cmp)(q, p, cookie) <=
+ sense))
t = p;
else
b = p;
break;
- } else if ((*cmp)(q, p) <= sense) {
+ } else if ((*cmp)(q, p, cookie) <=
+ sense) {
t = p;
if (i == size)
- big = 0;
+ big = 0;
goto FASTCASE;
} else
b = p;
@@ -192,19 +196,21 @@ SLOWCASE:
#endif
while (t > b+size) {
i = (((t - b) / size) >> 1) * size;
- if ((*cmp)(q, p = b + i) <= sense)
+ if ((*cmp)(q, p = b + i, cookie) <=
+ sense)
t = p;
else
b = p;
}
goto COPY;
-FASTCASE: while (i > size)
- if ((*cmp)(q,
- p = b +
- (i = (unsigned int) i >> 1)) <= sense)
+FASTCASE: while (i > size) {
+ i = (unsigned int)i >> 1;
+ p = b + i;
+ if ((*cmp)(q, p, cookie) <= sense)
t = p;
else
b = p;
+ }
COPY: b = t;
}
i = size;
@@ -277,11 +283,9 @@ COPY: b = t;
* when THRESHOLD/2 pairs compare with same sense. (Only used when NATURAL
* is defined. Otherwise simple pairwise merging is used.)
*/
-
-/* XXX: shouldn't this function be static? - lukem 990810 */
-void
+static void
setup(u_char *list1, u_char *list2, size_t n, size_t size,
- int (*cmp)(const void *, const void *))
+ int (*cmp)(const void *, const void *, void *), void *cookie)
{
int length, tmp, sense;
u_char *f1, *f2, *s, *l2, *last, *p2;
@@ -293,7 +297,7 @@ setup(u_char *list1, u_char *list2, size
size2 = size*2;
if (n <= 5) {
- insertionsort(list1, n, size, cmp);
+ insertionsort(list1, n, size, cmp, cookie);
*EVAL(list2) = list2 + n*size;
return;
}
@@ -302,19 +306,19 @@ setup(u_char *list1, u_char *list2, size
* for simplicity.
*/
i = 4 + (n & 1);
- insertionsort(list1 + (n - i) * size, i, size, cmp);
+ insertionsort(list1 + (n - i) * size, i, size, cmp, cookie);
last = list1 + size * (n - i);
*EVAL(list2 + (last - list1)) = list2 + n * size;
#ifdef NATURAL
p2 = list2;
f1 = list1;
- sense = (cmp(f1, f1 + size) > 0);
+ sense = (cmp(f1, f1 + size, cookie) > 0);
for (; f1 < last; sense = !sense) {
length = 2;
/* Find pairs with same sense. */
for (f2 = f1 + size2; f2 < last; f2 += size2) {
- if ((cmp(f2, f2+ size) > 0) != sense)
+ if ((cmp(f2, f2 + size, cookie) > 0) != sense)
break;
length += 2;
}
@@ -327,7 +331,7 @@ setup(u_char *list1, u_char *list2, size
} else { /* Natural merge */
l2 = f2;
for (f2 = f1 + size2; f2 < l2; f2 += size2) {
- if ((cmp(f2-size, f2) > 0) != sense) {
+ if ((cmp(f2-size, f2, cookie) > 0) != sense) {
p2 = *EVAL(p2) = f2 - list1 + list2;
if (sense > 0)
reverse(f1, f2 - size);
@@ -337,7 +341,7 @@ setup(u_char *list1, u_char *list2, size
if (sense > 0)
reverse(f1, f2 - size);
f1 = f2;
- if (f2 < last || cmp(f2 - size, f2) > 0)
+ if (f2 < last || cmp(f2 - size, f2, cookie) > 0)
p2 = *EVAL(p2) = f2 - list1 + list2;
else
p2 = *EVAL(p2) = list2 + n*size;
@@ -346,7 +350,7 @@ setup(u_char *list1, u_char *list2, size
#else /* pairwise merge only. */
for (f1 = list1, p2 = list2; f1 < last; f1 += size2) {
p2 = *EVAL(p2) = p2 + size2;
- if (cmp (f1, f1 + size) > 0)
+ if (cmp(f1, f1 + size, cookie) > 0)
swap(f1, f1 + size);
}
#endif /* NATURAL */
@@ -358,7 +362,7 @@ setup(u_char *list1, u_char *list2, size
*/
static void
insertionsort(u_char *a, size_t n, size_t size,
- int (*cmp)(const void *, const void *))
+ int (*cmp)(const void *, const void *, void *), void *cookie)
{
u_char *ai, *s, *t, *u, tmp;
size_t i;
@@ -369,8 +373,24 @@ insertionsort(u_char *a, size_t n, size_
for (ai = a+size; --n >= 1; ai += size)
for (t = ai; t > a; t -= size) {
u = t - size;
- if (cmp(u, t) <= 0)
+ if (cmp(u, t, cookie) <= 0)
break;
swap(u, t);
}
}
+
+static int
+cmpnocookie(const void *a, const void *b, void *cookie)
+{
+ int (*cmp)(const void *, const void *) = cookie;
+
+ return cmp(a, b);
+}
+
+int
+mergesort(void *a, size_t n, size_t es,
+ int (*cmp)(const void *, const void *))
+{
+
+ return mergesort_r(a, n, es, cmpnocookie, cmp);
+}
Index: src/lib/libc/stdlib/qsort.3
diff -u src/lib/libc/stdlib/qsort.3:1.14 src/lib/libc/stdlib/qsort.3:1.15
--- src/lib/libc/stdlib/qsort.3:1.14 Fri Sep 19 16:02:58 2014
+++ src/lib/libc/stdlib/qsort.3 Sun Mar 2 16:35:41 2025
@@ -1,4 +1,4 @@
-.\" $NetBSD: qsort.3,v 1.14 2014/09/19 16:02:58 wiz Exp $
+.\" $NetBSD: qsort.3,v 1.15 2025/03/02 16:35:41 riastradh Exp $
.\"
.\" Copyright (c) 1990, 1991, 1993
.\" The Regents of the University of California. All rights reserved.
@@ -47,10 +47,16 @@
.In stdlib.h
.Ft void
.Fn qsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)"
+.Ft void
+.Fn qsort_r "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *, void *)" "void *cookie"
.Ft int
.Fn heapsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)"
.Ft int
+.Fn heapsort_r "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *, void *)" "void *cookie"
+.Ft int
.Fn mergesort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)"
+.Ft int
+.Fn mergesort_r "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *, void *)" "void *cookie"
.Sh DESCRIPTION
The
.Fn qsort
@@ -106,6 +112,14 @@ The function
is stable.
.Pp
The
+.Fn qsort_r ,
+.Fn heapsort_r ,
+and
+.Fn mergesort_r
+functions pass an additional cookie argument through to the comparison
+function.
+.Pp
+The
.Fn qsort
function is an implementation of C.A.R. Hoare's ``quicksort'' algorithm,
a variant of partition-exchange sorting; in particular, see D.E. Knuth's
@@ -233,6 +247,10 @@ were unable to allocate memory.
.Sh STANDARDS
The
.Fn qsort
-function
-conforms to
+function conforms to
.St -ansiC .
+.Pp
+The
+.Fn qsort_r
+function conforms to
+.St -p1003.1-2024 .
Index: src/lib/libc/stdlib/qsort.c
diff -u src/lib/libc/stdlib/qsort.c:1.23 src/lib/libc/stdlib/qsort.c:1.24
--- src/lib/libc/stdlib/qsort.c:1.23 Fri May 19 19:48:19 2017
+++ src/lib/libc/stdlib/qsort.c Sun Mar 2 16:35:41 2025
@@ -1,4 +1,4 @@
-/* $NetBSD: qsort.c,v 1.23 2017/05/19 19:48:19 christos Exp $ */
+/* $NetBSD: qsort.c,v 1.24 2025/03/02 16:35:41 riastradh Exp $ */
/*-
* Copyright (c) 1992, 1993
* The Regents of the University of California. All rights reserved.
@@ -33,7 +33,7 @@
#if 0
static char sccsid[] = "@(#)qsort.c 8.1 (Berkeley) 6/4/93";
#else
-__RCSID("$NetBSD: qsort.c,v 1.23 2017/05/19 19:48:19 christos Exp $");
+__RCSID("$NetBSD: qsort.c,v 1.24 2025/03/02 16:35:41 riastradh Exp $");
#endif
#endif /* LIBC_SCCS and not lint */
@@ -44,7 +44,8 @@ __RCSID("$NetBSD: qsort.c,v 1.23 2017/05
#include <stdlib.h>
static inline char *med3(char *, char *, char *,
- int (*)(const void *, const void *));
+ int (*)(const void *, const void *, void *),
+ void *);
static inline void swapfunc(char *, char *, size_t, int);
#define min(a, b) (a) < (b) ? a : b
@@ -70,7 +71,7 @@ static inline void
swapfunc(char *a, char *b, size_t n, int swaptype)
{
- if (swaptype <= 1)
+ if (swaptype <= 1)
swapcode(long, a, b, n)
else
swapcode(char, a, b, n)
@@ -88,17 +89,17 @@ swapfunc(char *a, char *b, size_t n, int
static inline char *
med3(char *a, char *b, char *c,
- int (*cmp)(const void *, const void *))
+ int (*cmp)(const void *, const void *, void *), void *cookie)
{
- return cmp(a, b) < 0 ?
- (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a ))
- :(cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c ));
+ return cmp(a, b, cookie) < 0 ?
+ (cmp(b, c, cookie) < 0 ? b : (cmp(a, c, cookie) < 0 ? c : a ))
+ :(cmp(b, c, cookie) > 0 ? b : (cmp(a, c, cookie) < 0 ? a : c ));
}
void
-qsort(void *a, size_t n, size_t es,
- int (*cmp)(const void *, const void *))
+qsort_r(void *a, size_t n, size_t es,
+ int (*cmp)(const void *, const void *, void *), void *cookie)
{
char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
size_t d, r, s;
@@ -110,7 +111,8 @@ qsort(void *a, size_t n, size_t es,
loop: SWAPINIT(a, es);
if (n < 7) {
for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
- for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0;
+ for (pl = pm;
+ pl > (char *) a && cmp(pl - es, pl, cookie) > 0;
pl -= es)
swap(pl, pl - es);
return;
@@ -121,25 +123,25 @@ loop: SWAPINIT(a, es);
pn = (char *) a + (n - 1) * es;
if (n > 40) {
d = (n / 8) * es;
- pl = med3(pl, pl + d, pl + 2 * d, cmp);
- pm = med3(pm - d, pm, pm + d, cmp);
- pn = med3(pn - 2 * d, pn - d, pn, cmp);
+ pl = med3(pl, pl + d, pl + 2 * d, cmp, cookie);
+ pm = med3(pm - d, pm, pm + d, cmp, cookie);
+ pn = med3(pn - 2 * d, pn - d, pn, cmp, cookie);
}
- pm = med3(pl, pm, pn, cmp);
+ pm = med3(pl, pm, pn, cmp, cookie);
}
swap(a, pm);
pa = pb = (char *) a + es;
pc = pd = (char *) a + (n - 1) * es;
for (;;) {
- while (pb <= pc && (cmp_result = cmp(pb, a)) <= 0) {
+ while (pb <= pc && (cmp_result = cmp(pb, a, cookie)) <= 0) {
if (cmp_result == 0) {
swap(pa, pb);
pa += es;
}
pb += es;
}
- while (pb <= pc && (cmp_result = cmp(pc, a)) >= 0) {
+ while (pb <= pc && (cmp_result = cmp(pc, a, cookie)) >= 0) {
if (cmp_result == 0) {
swap(pc, pd);
pd -= es;
@@ -168,7 +170,7 @@ loop: SWAPINIT(a, es);
/* Recurse for 1st side, iterate for 2nd side. */
if (s > es) {
if (r > es)
- qsort(a, r / es, es, cmp);
+ qsort_r(a, r / es, es, cmp, cookie);
a = pn - s;
n = s / es;
goto loop;
@@ -177,9 +179,25 @@ loop: SWAPINIT(a, es);
/* Recurse for 2nd side, iterate for 1st side. */
if (r > es) {
if (s > es)
- qsort(pn - s, s / es, es, cmp);
+ qsort_r(pn - s, s / es, es, cmp, cookie);
n = r / es;
goto loop;
}
}
}
+
+static int
+cmpnocookie(const void *a, const void *b, void *cookie)
+{
+ int (*cmp)(const void *, const void *) = cookie;
+
+ return cmp(a, b);
+}
+
+void
+qsort(void *a, size_t n, size_t es,
+ int (*cmp)(const void *, const void *))
+{
+
+ qsort_r(a, n, es, cmpnocookie, cmp);
+}
Index: src/sys/lib/libkern/libkern.h
diff -u src/sys/lib/libkern/libkern.h:1.147 src/sys/lib/libkern/libkern.h:1.148
--- src/sys/lib/libkern/libkern.h:1.147 Fri Nov 1 21:11:37 2024
+++ src/sys/lib/libkern/libkern.h Sun Mar 2 16:35:41 2025
@@ -1,4 +1,4 @@
-/* $NetBSD: libkern.h,v 1.147 2024/11/01 21:11:37 riastradh Exp $ */
+/* $NetBSD: libkern.h,v 1.148 2025/03/02 16:35:41 riastradh Exp $ */
/*-
* Copyright (c) 1992, 1993
@@ -476,7 +476,10 @@ void hexdump(void (*)(const char *, ...
int snprintb(char *, size_t, const char *, uint64_t);
int snprintb_m(char *, size_t, const char *, uint64_t, size_t);
int kheapsort(void *, size_t, size_t, int (*)(const void *, const void *),
- void *);
+ void *);
+int kheapsort_r(void *, size_t, size_t,
+ int (*)(const void *, const void *, void *), void *,
+ void *);
uint32_t crc32(uint32_t, const uint8_t *, size_t);
#if __GNUC_PREREQ__(4, 5) \
&& (defined(__alpha_cix__) || defined(__mips_popcount))
Index: src/tests/lib/libc/stdlib/Makefile
diff -u src/tests/lib/libc/stdlib/Makefile:1.34 src/tests/lib/libc/stdlib/Makefile:1.35
--- src/tests/lib/libc/stdlib/Makefile:1.34 Tue Jul 4 15:06:36 2023
+++ src/tests/lib/libc/stdlib/Makefile Sun Mar 2 16:35:41 2025
@@ -1,4 +1,4 @@
-# $NetBSD: Makefile,v 1.34 2023/07/04 15:06:36 riastradh Exp $
+# $NetBSD: Makefile,v 1.35 2025/03/02 16:35:41 riastradh Exp $
.include <bsd.own.mk>
@@ -23,6 +23,7 @@ TESTS_C+= t_system
TESTS_SH+= t_atexit
TESTS_SH+= t_getopt
+TESTS_SH+= t_sort
MKMAN=no
@@ -30,6 +31,7 @@ BINDIR= ${TESTSDIR}
PROGS+= h_atexit
PROGS+= h_getopt h_getopt_long
+PROGS+= h_sort
CFLAGS.t_posix_memalign.c+= -fno-builtin-posix_memalign
CFLAGS.t_posix_memalign.c+= -fno-builtin-aligned_alloc
Index: src/tools/compat/compat_defs.h
diff -u src/tools/compat/compat_defs.h:1.123 src/tools/compat/compat_defs.h:1.124
--- src/tools/compat/compat_defs.h:1.123 Thu Oct 31 17:05:05 2024
+++ src/tools/compat/compat_defs.h Sun Mar 2 16:35:41 2025
@@ -1,4 +1,4 @@
-/* $NetBSD: compat_defs.h,v 1.123 2024/10/31 17:05:05 kre Exp $ */
+/* $NetBSD: compat_defs.h,v 1.124 2025/03/02 16:35:41 riastradh Exp $ */
#ifndef __NETBSD_COMPAT_DEFS_H__
#define __NETBSD_COMPAT_DEFS_H__
@@ -462,8 +462,12 @@ int __nbcompat_gettemp(char *, int *, in
ssize_t pread(int, void *, size_t, off_t);
#endif
-int __nbcompat_heapsort (void *, size_t, size_t, int (*)(const void *, const void *));
+int __nbcompat_heapsort(void *, size_t, size_t,
+ int (*)(const void *, const void *));
+int __nbcompat_heapsort_r(void *, size_t, size_t,
+ int (*)(const void *, const void *, void *), void *);
#define heapsort __nbcompat_heapsort
+#define heapsort_r __nbcompat_heapsort_r
#if !HAVE_DECL_HEAPSORT
int heapsort (void *, size_t, size_t, int (*)(const void *, const void *));
Added files:
Index: src/tests/lib/libc/stdlib/h_sort.c
diff -u /dev/null src/tests/lib/libc/stdlib/h_sort.c:1.1
--- /dev/null Sun Mar 2 16:35:42 2025
+++ src/tests/lib/libc/stdlib/h_sort.c Sun Mar 2 16:35:41 2025
@@ -0,0 +1,177 @@
+/* $NetBSD: h_sort.c,v 1.1 2025/03/02 16:35:41 riastradh Exp $ */
+
+/*-
+ * Copyright (c) 2025 The NetBSD Foundation, Inc.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+ * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <sys/cdefs.h>
+__RCSID("$NetBSD: h_sort.c,v 1.1 2025/03/02 16:35:41 riastradh Exp $");
+
+#include <err.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+
+static void
+heapsort_r_wrapper(void *a, size_t n, size_t sz,
+ int (*cmp)(const void *, const void *, void *), void *cookie)
+{
+
+ if (heapsort_r(a, n, sz, cmp, cookie) == -1)
+ err(1, "heapsort_r");
+}
+
+static void
+mergesort_r_wrapper(void *a, size_t n, size_t sz,
+ int (*cmp)(const void *, const void *, void *), void *cookie)
+{
+
+ if (mergesort_r(a, n, sz, cmp, cookie) == -1)
+ err(1, "mergesort_r");
+}
+
+static int
+cmp(const void *va, const void *vb, void *cookie)
+{
+ const char *buf = cookie;
+ const size_t *a = va;
+ const size_t *b = vb;
+
+ return strcmp(buf + *a, buf + *b);
+}
+
+int
+main(int argc, char **argv)
+{
+ void (*sortfn)(void *, size_t, size_t,
+ int (*)(const void *, const void *, void *), void *);
+ char *buf = NULL;
+ size_t nbuf;
+ size_t *lines = NULL;
+ size_t nlines;
+ size_t off;
+ ssize_t nread;
+ char *p;
+ size_t i;
+ int error;
+
+ /*
+ * Parse arguments.
+ */
+ setprogname(argv[0]);
+ if (argc < 2)
+ errx(1, "Usage: %s <sortfn>", getprogname());
+ if (strcmp(argv[1], "heapsort_r") == 0)
+ sortfn = &heapsort_r_wrapper;
+ else if (strcmp(argv[1], "mergesort_r") == 0)
+ sortfn = &mergesort_r_wrapper;
+ else if (strcmp(argv[1], "qsort_r") == 0)
+ sortfn = &qsort_r;
+ else
+ errx(1, "unknown sort: %s", argv[1]);
+
+ /*
+ * Allocate an initial 4K buffer.
+ */
+ nbuf = 0x1000;
+ error = reallocarr(&buf, nbuf, 1);
+ if (error)
+ err(1, "reallocarr");
+
+ /*
+ * Read the input into a contiguous buffer. Reject input with
+ * embedded NULs so we can use strcmp(3) to compare lines.
+ */
+ off = 0;
+ while ((nread = read(STDIN_FILENO, buf + off, nbuf - off)) != 0) {
+ if (nread == -1)
+ err(1, "read");
+ if ((size_t)nread > nbuf - off)
+ errx(1, "overlong read: %zu", (size_t)nread);
+ if (memchr(buf + off, '\0', (size_t)nread) != NULL)
+ errx(1, "NUL byte in input");
+ off += (size_t)nread;
+
+ /*
+ * If we filled the buffer, reallocate it with double
+ * the size. Bail if that would overflow.
+ */
+ if (nbuf - off == 0) {
+ if (nbuf > SIZE_MAX/2)
+ errx(1, "input overflow");
+ nbuf *= 2;
+ error = reallocarr(&buf, nbuf, 1);
+ if (error)
+ err(1, "reallocarr");
+ }
+ }
+
+ /*
+ * If the input was empty, nothing to do.
+ */
+ if (off == 0)
+ return 0;
+
+ /*
+ * NUL-terminate the input and count the lines. The last line
+ * may have no trailing \n.
+ */
+ buf[off] = '\0';
+ nlines = 1;
+ for (p = buf; (p = strchr(p, '\n')) != NULL;) {
+ if (*++p == '\0')
+ break;
+ nlines++;
+ }
+
+ /*
+ * Create an array of line offsets to sort. NUL-terminate each
+ * line so we can use strcmp(3).
+ */
+ error = reallocarr(&lines, nlines, sizeof(lines[0]));
+ if (lines == NULL)
+ err(1, "reallocarr");
+ i = 0;
+ for (p = buf; lines[i++] = p - buf, (p = strchr(p, '\n')) != NULL;) {
+ *p = '\0';
+ if (*++p == '\0')
+ break;
+ }
+
+ /*
+ * Sort the array of line offsets via comparison function that
+ * consults the buffer as a cookie.
+ */
+ (*sortfn)(lines, nlines, sizeof(lines[0]), &cmp, buf);
+
+ /*
+ * Print the lines in sorted order.
+ */
+ for (i = 0; i < nlines; i++)
+ printf("%s\n", buf + lines[i]);
+ fflush(stdout);
+ return ferror(stdout);
+}
Index: src/tests/lib/libc/stdlib/t_sort.sh
diff -u /dev/null src/tests/lib/libc/stdlib/t_sort.sh:1.1
--- /dev/null Sun Mar 2 16:35:42 2025
+++ src/tests/lib/libc/stdlib/t_sort.sh Sun Mar 2 16:35:41 2025
@@ -0,0 +1,61 @@
+# $NetBSD: t_sort.sh,v 1.1 2025/03/02 16:35:41 riastradh Exp $
+#
+# Copyright (c) 2025 The NetBSD Foundation, Inc.
+# All rights reserved.
+#
+# Redistribution and use in source and binary forms, with or without
+# modification, are permitted provided that the following conditions
+# are met:
+# 1. Redistributions of source code must retain the above copyright
+# notice, this list of conditions and the following disclaimer.
+# 2. Redistributions in binary form must reproduce the above copyright
+# notice, this list of conditions and the following disclaimer in the
+# documentation and/or other materials provided with the distribution.
+#
+# THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
+# ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+# TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+# PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
+# BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+# CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+# SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+# INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+# CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+# ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+# POSSIBILITY OF SUCH DAMAGE.
+
+check_sort()
+{
+ local sortfn
+
+ set -Ceu
+
+ sortfn="$1"
+
+ printf 'foo\nbar\nbaz\nquux' >in1
+ printf 'bar\nbaz\nfoo\nquux\n' >out
+ atf_check -s exit:0 -o file:out \
+ "$(atf_get_srcdir)"/h_sort "$sortfn" <in1
+ atf_check -s exit:0 -o empty sh -c 'exec shuffle -f - <in1 >in2'
+ atf_check -s exit:0 -o file:out \
+ "$(atf_get_srcdir)"/h_sort "$sortfn" <in2
+}
+
+sortfn_case()
+{
+ local sortfn
+
+ sortfn="$1"
+
+ eval "${sortfn}_head() { atf_set descr \"Test ${sortfn}\"; }"
+ eval "${sortfn}_body() { check_sort $sortfn; }"
+ atf_add_test_case "$sortfn"
+}
+
+atf_init_test_cases()
+{
+
+ sortfn_case heapsort_r
+ sortfn_case mergesort_r
+ sortfn_case qsort_r
+}
