Module Name: src
Committed By: riastradh
Date: Sun Mar 2 20:00:32 UTC 2025
Modified Files:
src/tests/lib/libc/stdlib: h_sort.c t_sort.sh
Log Message:
t_sort: Test mergesort for stability too.
These test cases are trivial, but they're enough to trigger unstable
heapsort and qsort.
Fix some error branches while here.
PR lib/58931: qsort_r() missing
To generate a diff of this commit:
cvs rdiff -u -r1.1 -r1.2 src/tests/lib/libc/stdlib/h_sort.c \
src/tests/lib/libc/stdlib/t_sort.sh
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: src/tests/lib/libc/stdlib/h_sort.c
diff -u src/tests/lib/libc/stdlib/h_sort.c:1.1 src/tests/lib/libc/stdlib/h_sort.c:1.2
--- src/tests/lib/libc/stdlib/h_sort.c:1.1 Sun Mar 2 16:35:41 2025
+++ src/tests/lib/libc/stdlib/h_sort.c Sun Mar 2 20:00:32 2025
@@ -1,4 +1,4 @@
-/* $NetBSD: h_sort.c,v 1.1 2025/03/02 16:35:41 riastradh Exp $ */
+/* $NetBSD: h_sort.c,v 1.2 2025/03/02 20:00:32 riastradh Exp $ */
/*-
* Copyright (c) 2025 The NetBSD Foundation, Inc.
@@ -27,9 +27,11 @@
*/
#include <sys/cdefs.h>
-__RCSID("$NetBSD: h_sort.c,v 1.1 2025/03/02 16:35:41 riastradh Exp $");
+__RCSID("$NetBSD: h_sort.c,v 1.2 2025/03/02 20:00:32 riastradh Exp $");
+#include <assert.h>
#include <err.h>
+#include <getopt.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
@@ -53,25 +55,41 @@ mergesort_r_wrapper(void *a, size_t n, s
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 char *buf = cookie;
+ const struct context *C = cookie;
const size_t *a = va;
const size_t *b = vb;
- return strcmp(buf + *a, buf + *b);
+ 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 *lines = NULL;
+ size_t *linepos = NULL;
size_t nlines;
+ size_t *permutation = NULL;
size_t off;
ssize_t nread;
char *p;
@@ -82,16 +100,29 @@ main(int argc, char **argv)
* Parse arguments.
*/
setprogname(argv[0]);
- if (argc < 2)
- errx(1, "Usage: %s <sortfn>", getprogname());
- if (strcmp(argv[1], "heapsort_r") == 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[1], "mergesort_r") == 0)
+ else if (strcmp(argv[0], "mergesort_r") == 0)
sortfn = &mergesort_r_wrapper;
- else if (strcmp(argv[1], "qsort_r") == 0)
+ else if (strcmp(argv[0], "qsort_r") == 0)
sortfn = &qsort_r;
else
- errx(1, "unknown sort: %s", argv[1]);
+ errx(1, "unknown sort: %s", argv[0]);
/*
* Allocate an initial 4K buffer.
@@ -99,7 +130,7 @@ main(int argc, char **argv)
nbuf = 0x1000;
error = reallocarr(&buf, nbuf, 1);
if (error)
- err(1, "reallocarr");
+ errc(1, error, "reallocarr");
/*
* Read the input into a contiguous buffer. Reject input with
@@ -125,7 +156,7 @@ main(int argc, char **argv)
nbuf *= 2;
error = reallocarr(&buf, nbuf, 1);
if (error)
- err(1, "reallocarr");
+ errc(1, error, "reallocarr");
}
}
@@ -148,30 +179,47 @@ main(int argc, char **argv)
}
/*
- * Create an array of line offsets to sort. NUL-terminate each
- * line so we can use strcmp(3).
+ * Create an array of line positions 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");
+ error = reallocarr(&linepos, nlines, sizeof(linepos[0]));
+ if (error)
+ errc(1, error, "reallocarr");
i = 0;
- for (p = buf; lines[i++] = p - buf, (p = strchr(p, '\n')) != NULL;) {
+ for (p = buf; linepos[i++] = p - buf, (p = strchr(p, '\n')) != NULL;) {
*p = '\0';
if (*++p == '\0')
break;
}
+ assert(i == nlines);
/*
- * Sort the array of line offsets via comparison function that
- * consults the buffer as a cookie.
+ * Create an array of permuted line numbers.
*/
- (*sortfn)(lines, nlines, sizeof(lines[0]), &cmp, buf);
+ error = reallocarr(&permutation, nlines, sizeof(permutation[0]));
+ if (error)
+ errc(1, error, "reallocarr");
+ for (i = 0; i < nlines; i++)
+ permutation[i] = i;
/*
- * Print the lines in sorted order.
+ * Sort the lines via comparison function that consults the
+ * buffer as a cookie.
*/
- for (i = 0; i < nlines; i++)
- printf("%s\n", buf + lines[i]);
+ (*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);
}
Index: src/tests/lib/libc/stdlib/t_sort.sh
diff -u src/tests/lib/libc/stdlib/t_sort.sh:1.1 src/tests/lib/libc/stdlib/t_sort.sh:1.2
--- src/tests/lib/libc/stdlib/t_sort.sh:1.1 Sun Mar 2 16:35:41 2025
+++ src/tests/lib/libc/stdlib/t_sort.sh Sun Mar 2 20:00:32 2025
@@ -1,4 +1,4 @@
-# $NetBSD: t_sort.sh,v 1.1 2025/03/02 16:35:41 riastradh Exp $
+# $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.
@@ -28,19 +28,61 @@ check_sort()
{
local sortfn
- set -Ceu
+ set -eu
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
+ 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'
- atf_check -s exit:0 -o file:out \
+ 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
@@ -52,10 +94,22 @@ sortfn_case()
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
}
