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 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 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 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 74 usage(void) 75 { 76 77 fprintf(stderr, "Usage: %s [-n] <sortfn>\n", getprogname()); 78 exit(1); 79 } 80 81 int 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
Indexes created Sat Sep 20 22:09:52 GMT 2025