vendor/NetBSD/tests/2026.02.14_2vendor/NetBSD/tests

2 files changed, 340 insertions, 0 deletions

diff --git a/lib/libc/stdlib/h_sort.c b/lib/libc/stdlib/h_sort.c
new file mode 100644
index 000000000000..1e5f4b3b0798
--- /dev/null
+++ b/lib/libc/stdlib/h_sort.c
@@ -0,0 +1,225 @@
+/*	$NetBSD: h_sort.c,v 1.3 2025/03/02 23:11:19 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.3 2025/03/02 23:11:19 riastradh Exp $");
+
+#include <assert.h>
+#include <err.h>
+#include <getopt.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");
+}
+
+struct context {
+	const char	*buf;
+	const size_t	*linepos;
+};
+
+static int
+cmp(const void *va, const void *vb, void *cookie)
+{
+	const struct context *C = cookie;
+	const size_t *a = va;
+	const size_t *b = vb;
+
+	return strcmp(C->buf + C->linepos[*a], C->buf + C->linepos[*b]);
+}
+
+static void __dead
+usage(void)
+{
+
+	fprintf(stderr, "Usage: %s [-n] <sortfn>\n", getprogname());
+	exit(1);
+}
+
+int
+main(int argc, char **argv)
+{
+	int ch;
+	int nflag = 0;
+	void (*sortfn)(void *, size_t, size_t,
+	    int (*)(const void *, const void *, void *), void *);
+	char *buf = NULL;
+	size_t nbuf;
+	size_t *linepos = NULL;
+	size_t nlines;
+	size_t *permutation = NULL;
+	size_t off;
+	ssize_t nread;
+	char *p;
+	size_t i;
+	int error;
+
+	/*
+	 * Parse arguments.
+	 */
+	setprogname(argv[0]);
+	while ((ch = getopt(argc, argv, "hn")) != -1) {
+		switch (ch) {
+		case 'n':
+			nflag = 1;
+			break;
+		case '?':
+		case 'h':
+		default:
+			usage();
+		}
+	}
+	argc -= optind;
+	argv += optind;
+	if (argc != 1)
+		usage();
+	if (strcmp(argv[0], "heapsort_r") == 0)
+		sortfn = &heapsort_r_wrapper;
+	else if (strcmp(argv[0], "mergesort_r") == 0)
+		sortfn = &mergesort_r_wrapper;
+	else if (strcmp(argv[0], "qsort_r") == 0)
+		sortfn = &qsort_r;
+	else
+		errx(1, "unknown sort: %s", argv[0]);
+
+	/*
+	 * Allocate an initial 4K buffer.
+	 */
+	nbuf = 0x1000;
+	error = reallocarr(&buf, nbuf, 1);
+	if (error)
+		errc(1, error, "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 - 1)) != 0) {
+		if (nread == -1)
+			err(1, "read");
+		if ((size_t)nread > nbuf - off - 1)
+			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 == 1) {
+			if (nbuf > SIZE_MAX/2)
+				errx(1, "input overflow");
+			nbuf *= 2;
+			error = reallocarr(&buf, nbuf, 1);
+			if (error)
+				errc(1, error, "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 positions to sort.  NUL-terminate
+	 * each line so we can use strcmp(3).
+	 */
+	error = reallocarr(&linepos, nlines, sizeof(linepos[0]));
+	if (error)
+		errc(1, error, "reallocarr");
+	i = 0;
+	for (p = buf; linepos[i++] = p - buf, (p = strchr(p, '\n')) != NULL;) {
+		*p = '\0';
+		if (*++p == '\0')
+			break;
+	}
+	assert(i == nlines);
+
+	/*
+	 * Create an array of permuted line numbers.
+	 */
+	error = reallocarr(&permutation, nlines, sizeof(permutation[0]));
+	if (error)
+		errc(1, error, "reallocarr");
+	for (i = 0; i < nlines; i++)
+		permutation[i] = i;
+
+	/*
+	 * Sort the lines via comparison function that consults the
+	 * buffer as a cookie.
+	 */
+	(*sortfn)(permutation, nlines, sizeof(permutation[0]), &cmp,
+	    &(struct context) { .buf = buf, .linepos = linepos });
+
+	/*
+	 * Print the lines in sorted order with the original line
+	 * numbers.
+	 */
+	for (i = 0; i < nlines; i++) {
+		const size_t j = permutation[i];
+		if (nflag)
+			printf("%zu %s\n", j, buf + linepos[j]);
+		else
+			printf("%s\n", buf + linepos[j]);
+	}
+	fflush(stdout);
+	return ferror(stdout);
+}
diff --git a/lib/libc/stdlib/t_sort.sh b/lib/libc/stdlib/t_sort.sh
new file mode 100644
index 000000000000..8987ac1ec623
--- /dev/null
+++ b/lib/libc/stdlib/t_sort.sh
@@ -0,0 +1,115 @@
+#	$NetBSD: t_sort.sh,v 1.2 2025/03/02 20:00:32 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 -eu
+
+	sortfn="$1"
+
+	printf 'foo\nbar\nbaz\nquux' >in1
+	printf '1 bar\n2 baz\n0 foo\n3 quux\n' >out1
+	atf_check -s exit:0 -o file:out1 \
+		"$(atf_get_srcdir)"/h_sort -n "$sortfn" <in1
+
+	atf_check -s exit:0 -o empty sh -c 'exec shuffle -f - <in1 >in2'
+	printf 'bar\nbaz\nfoo\nquux\n' >out2
+	atf_check -s exit:0 -o file:out2 \
+		"$(atf_get_srcdir)"/h_sort "$sortfn" <in2
+}
+
+check_stablesort()
+{
+	local sortfn
+
+	set -eu
+
+	sortfn="$1"
+
+	printf 'foo\nfoo\nfoo\nfoo\nfoo' >in1
+	printf '0 foo\n1 foo\n2 foo\n3 foo\n4 foo\n' >out1
+	atf_check -s exit:0 -o file:out1 \
+		"$(atf_get_srcdir)"/h_sort -n "$sortfn" <in1
+
+	printf 'foo\nfoo\nfoo\nfoo\nfoo\nbar\nbar\nbar\nbar\nbar' >in2
+	printf '5 bar\n6 bar\n7 bar\n8 bar\n9 bar\n' >out2
+	printf '0 foo\n1 foo\n2 foo\n3 foo\n4 foo\n' >>out2
+	atf_check -s exit:0 -o file:out2 \
+		"$(atf_get_srcdir)"/h_sort -n "$sortfn" <in2
+
+	printf 'foo\nfoo\nbar\nbaz\nquux' >in3
+	printf '2 bar\n3 baz\n0 foo\n1 foo\n4 quux\n' >out3
+	atf_check -s exit:0 -o file:out3 \
+		"$(atf_get_srcdir)"/h_sort -n "$sortfn" <in3
+
+	printf 'foo\nbar\nbar\nbaz\nquux' >in4
+	printf '1 bar\n2 bar\n3 baz\n0 foo\n4 quux\n' >out4
+	atf_check -s exit:0 -o file:out4 \
+		"$(atf_get_srcdir)"/h_sort -n "$sortfn" <in4
+
+	printf 'foo\nbar\nbaz\nbaz\nquux' >in5
+	printf '1 bar\n2 baz\n3 baz\n0 foo\n4 quux\n' >out5
+	atf_check -s exit:0 -o file:out5 \
+		"$(atf_get_srcdir)"/h_sort -n "$sortfn" <in5
+
+	printf 'foo\nbar\nbaz\nquux\nquux' >in6
+	printf '1 bar\n2 baz\n0 foo\n3 quux\n4 quux\n' >out6
+	atf_check -s exit:0 -o file:out6 \
+		"$(atf_get_srcdir)"/h_sort -n "$sortfn" <in6
+}
+
+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"
+}
+
+stablesortfn_case()
+{
+	local sortfn
+
+	sortfn="$1"
+
+	eval "${sortfn}_stable_head() { atf_set descr \"Test ${sortfn}\"; }"
+	eval "${sortfn}_stable_body() { check_stablesort $sortfn; }"
+	atf_add_test_case "${sortfn}_stable"
+}
+
+atf_init_test_cases()
+{
+
+	sortfn_case heapsort_r
+	sortfn_case mergesort_r
+	sortfn_case qsort_r
+	stablesortfn_case mergesort_r
+}