1 /* $NetBSD: h_sort.c,v 1.3 2025/03/02 23:11:19 riastradh Exp $ */
2
3 /*-
4 * Copyright (c) 2025 The NetBSD Foundation, Inc.
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
17 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
18 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
19 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
20 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 */
28
29 #include <sys/cdefs.h>
30 __RCSID("$NetBSD: h_sort.c,v 1.3 2025/03/02 23:11:19 riastradh Exp $");
31
32 #include <assert.h>
33 #include <err.h>
34 #include <getopt.h>
35 #include <stdio.h>
36 #include <stdlib.h>
37 #include <string.h>
38 #include <unistd.h>
39
40 static void
heapsort_r_wrapper(void * a,size_t n,size_t sz,int (* cmp)(const void *,const void *,void *),void * cookie)41 heapsort_r_wrapper(void *a, size_t n, size_t sz,
42 int (*cmp)(const void *, const void *, void *), void *cookie)
43 {
44
45 if (heapsort_r(a, n, sz, cmp, cookie) == -1)
46 err(1, "heapsort_r");
47 }
48
49 static void
mergesort_r_wrapper(void * a,size_t n,size_t sz,int (* cmp)(const void *,const void *,void *),void * cookie)50 mergesort_r_wrapper(void *a, size_t n, size_t sz,
51 int (*cmp)(const void *, const void *, void *), void *cookie)
52 {
53
54 if (mergesort_r(a, n, sz, cmp, cookie) == -1)
55 err(1, "mergesort_r");
56 }
57
58 struct context {
59 const char *buf;
60 const size_t *linepos;
61 };
62
63 static int
cmp(const void * va,const void * vb,void * cookie)64 cmp(const void *va, const void *vb, void *cookie)
65 {
66 const struct context *C = cookie;
67 const size_t *a = va;
68 const size_t *b = vb;
69
70 return strcmp(C->buf + C->linepos[*a], C->buf + C->linepos[*b]);
71 }
72
73 static void __dead
usage(void)74 usage(void)
75 {
76
77 fprintf(stderr, "Usage: %s [-n] <sortfn>\n", getprogname());
78 exit(1);
79 }
80
81 int
main(int argc,char ** argv)82 main(int argc, char **argv)
83 {
84 int ch;
85 int nflag = 0;
86 void (*sortfn)(void *, size_t, size_t,
87 int (*)(const void *, const void *, void *), void *);
88 char *buf = NULL;
89 size_t nbuf;
90 size_t *linepos = NULL;
91 size_t nlines;
92 size_t *permutation = NULL;
93 size_t off;
94 ssize_t nread;
95 char *p;
96 size_t i;
97 int error;
98
99 /*
100 * Parse arguments.
101 */
102 setprogname(argv[0]);
103 while ((ch = getopt(argc, argv, "hn")) != -1) {
104 switch (ch) {
105 case 'n':
106 nflag = 1;
107 break;
108 case '?':
109 case 'h':
110 default:
111 usage();
112 }
113 }
114 argc -= optind;
115 argv += optind;
116 if (argc != 1)
117 usage();
118 if (strcmp(argv[0], "heapsort_r") == 0)
119 sortfn = &heapsort_r_wrapper;
120 else if (strcmp(argv[0], "mergesort_r") == 0)
121 sortfn = &mergesort_r_wrapper;
122 else if (strcmp(argv[0], "qsort_r") == 0)
123 sortfn = &qsort_r;
124 else
125 errx(1, "unknown sort: %s", argv[0]);
126
127 /*
128 * Allocate an initial 4K buffer.
129 */
130 nbuf = 0x1000;
131 error = reallocarr(&buf, nbuf, 1);
132 if (error)
133 errc(1, error, "reallocarr");
134
135 /*
136 * Read the input into a contiguous buffer. Reject input with
137 * embedded NULs so we can use strcmp(3) to compare lines.
138 */
139 off = 0;
140 while ((nread = read(STDIN_FILENO, buf + off, nbuf - off - 1)) != 0) {
141 if (nread == -1)
142 err(1, "read");
143 if ((size_t)nread > nbuf - off - 1)
144 errx(1, "overlong read: %zu", (size_t)nread);
145 if (memchr(buf + off, '\0', (size_t)nread) != NULL)
146 errx(1, "NUL byte in input");
147 off += (size_t)nread;
148
149 /*
150 * If we filled the buffer, reallocate it with double
151 * the size. Bail if that would overflow.
152 */
153 if (nbuf - off == 1) {
154 if (nbuf > SIZE_MAX/2)
155 errx(1, "input overflow");
156 nbuf *= 2;
157 error = reallocarr(&buf, nbuf, 1);
158 if (error)
159 errc(1, error, "reallocarr");
160 }
161 }
162
163 /*
164 * If the input was empty, nothing to do.
165 */
166 if (off == 0)
167 return 0;
168
169 /*
170 * NUL-terminate the input and count the lines. The last line
171 * may have no trailing \n.
172 */
173 buf[off] = '\0';
174 nlines = 1;
175 for (p = buf; (p = strchr(p, '\n')) != NULL;) {
176 if (*++p == '\0')
177 break;
178 nlines++;
179 }
180
181 /*
182 * Create an array of line positions to sort. NUL-terminate
183 * each line so we can use strcmp(3).
184 */
185 error = reallocarr(&linepos, nlines, sizeof(linepos[0]));
186 if (error)
187 errc(1, error, "reallocarr");
188 i = 0;
189 for (p = buf; linepos[i++] = p - buf, (p = strchr(p, '\n')) != NULL;) {
190 *p = '\0';
191 if (*++p == '\0')
192 break;
193 }
194 assert(i == nlines);
195
196 /*
197 * Create an array of permuted line numbers.
198 */
199 error = reallocarr(&permutation, nlines, sizeof(permutation[0]));
200 if (error)
201 errc(1, error, "reallocarr");
202 for (i = 0; i < nlines; i++)
203 permutation[i] = i;
204
205 /*
206 * Sort the lines via comparison function that consults the
207 * buffer as a cookie.
208 */
209 (*sortfn)(permutation, nlines, sizeof(permutation[0]), &cmp,
210 &(struct context) { .buf = buf, .linepos = linepos });
211
212 /*
213 * Print the lines in sorted order with the original line
214 * numbers.
215 */
216 for (i = 0; i < nlines; i++) {
217 const size_t j = permutation[i];
218 if (nflag)
219 printf("%zu %s\n", j, buf + linepos[j]);
220 else
221 printf("%s\n", buf + linepos[j]);
222 }
223 fflush(stdout);
224 return ferror(stdout);
225 }
226