1 /* $NetBSD: shuffle.c,v 1.18 2004/12/01 00:03:45 perry Exp $ */ 2 3 /* 4 * Copyright (c) 1998 5 * Perry E. Metzger. 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 * 3. All advertising materials mentioning features or use of this software 16 * must display the following acknowledgment: 17 * This product includes software developed for the NetBSD Project 18 * by Perry E. Metzger. 19 * 4. The name of the author may not be used to endorse or promote products 20 * derived from this software without specific prior written permission. 21 * 22 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 23 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 24 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 25 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 26 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 27 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 28 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 29 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 30 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 31 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 32 */ 33 34 #include <sys/cdefs.h> 35 #ifndef lint 36 __RCSID("$NetBSD: shuffle.c,v 1.18 2004/12/01 00:03:45 perry Exp $"); 37 #endif /* not lint */ 38 39 #include <sys/time.h> 40 41 #include <err.h> 42 #include <errno.h> 43 #include <limits.h> 44 #include <stdio.h> 45 #include <stdlib.h> 46 #include <string.h> 47 #include <unistd.h> 48 49 static void enomem(void); 50 static void *emalloc(size_t); 51 static void *erealloc(void *, size_t); 52 53 static size_t *get_shuffle(size_t); 54 static void usage(void); 55 static void get_lines(const char *, char ***, size_t *); 56 static size_t get_number(const char *, int); 57 58 int main(int, char *[]); 59 60 /* 61 * enomem -- 62 * die when out of memory. 63 */ 64 static void 65 enomem(void) 66 { 67 errx(2, "Cannot allocate memory."); 68 } 69 70 /* 71 * emalloc -- 72 * malloc, but die on error. 73 */ 74 static void * 75 emalloc(size_t len) 76 { 77 void *p; 78 79 if ((p = malloc(len)) == NULL) 80 enomem(); 81 return p; 82 } 83 84 /* 85 * erealloc -- 86 * realloc, but die on error. 87 */ 88 void * 89 erealloc(void *ptr, size_t size) 90 { 91 if ((ptr = realloc(ptr, size)) == NULL) 92 enomem(); 93 return ptr; 94 } 95 96 /* 97 * get_shuffle -- 98 * Construct a random shuffle array of t elements 99 */ 100 static size_t * 101 get_shuffle(size_t t) 102 { 103 size_t *shuffle; 104 size_t i, j, k, temp; 105 106 shuffle = emalloc(t * sizeof(size_t)); 107 108 for (i = 0; i < t; i++) 109 shuffle[i] = i; 110 111 /* 112 * This algorithm taken from Knuth, Seminumerical Algorithms, 113 * 2nd Ed., page 139. 114 */ 115 116 for (j = t - 1; j > 0; j--) { 117 k = arc4random() % (j + 1); 118 temp = shuffle[j]; 119 shuffle[j] = shuffle[k]; 120 shuffle[k] = temp; 121 } 122 123 return shuffle; 124 } 125 126 /* 127 * usage -- 128 * Print a usage message and exit 129 */ 130 static void 131 usage(void) 132 { 133 134 (void) fprintf(stderr, 135 "usage: %s [-0] [-f <filename>] [-n <number>] [-p <number>] [<arg> ...]\n", 136 getprogname()); 137 exit(1); 138 } 139 140 141 /* 142 * get_lines -- 143 * Return an array of lines read from input 144 */ 145 static void 146 get_lines(const char *fname, char ***linesp, size_t *nlinesp) 147 { 148 FILE *fp; 149 char *line; 150 size_t size, nlines = 0, maxlines = 128; 151 char **lines = emalloc(sizeof(char *) * maxlines); 152 153 if (strcmp(fname, "-") == 0) 154 fp = stdin; 155 else 156 if ((fp = fopen(fname, "r")) == NULL) 157 err(1, "Cannot open `%s'", fname); 158 159 while ((line = fgetln(fp, &size)) != NULL) { 160 if (size > 0 && line[size - 1] == '\n') 161 size--; 162 lines[nlines] = emalloc(size + 1); 163 (void)memcpy(lines[nlines], line, size); 164 lines[nlines++][size] = '\0'; 165 if (nlines >= maxlines) { 166 maxlines *= 2; 167 lines = erealloc(lines, (sizeof(char *) * maxlines)); 168 } 169 } 170 lines[nlines] = NULL; 171 172 *linesp = lines; 173 *nlinesp = nlines; 174 if (strcmp(fname, "-") != 0) 175 (void)fclose(fp); 176 } 177 178 /* 179 * get_number -- 180 * Return a number or exit on error 181 */ 182 static size_t 183 get_number(const char *str, int ch) 184 { 185 char *estr; 186 long number; 187 188 errno = 0; 189 number = strtol(str, &estr, 0); 190 if ((number == LONG_MIN || number == LONG_MAX) && errno == ERANGE) 191 err(1, "bad -%c argument `%s'", ch, str); 192 if (*estr) 193 errx(1, "non numeric -%c argument `%s'", ch, str); 194 if (number < 0) 195 errx(1, "negative -%c argument `%s'", ch, str); 196 return (size_t) number; 197 } 198 199 int 200 main(int argc, char *argv[]) 201 { 202 int i, nflag = 0, pflag = 0, ch; 203 char *fname = NULL; 204 size_t *shuffle = NULL; 205 char **lines = NULL; 206 size_t nlines = 0, pick = 0; 207 char sep = '\n'; 208 209 while ((ch = getopt(argc, argv, "0f:n:p:")) != -1) { 210 switch(ch) { 211 case '0': 212 sep = '\0'; 213 break; 214 case 'f': 215 fname = optarg; 216 break; 217 case 'n': 218 nlines = get_number(optarg, ch); 219 nflag = 1; 220 break; 221 case 'p': 222 pick = get_number(optarg, ch); 223 pflag = 1; 224 break; 225 case '?': 226 default: 227 usage(); 228 } 229 } 230 argc -= optind; 231 argv += optind; 232 233 if ((fname && nflag) || (nflag && (argc > 0))) 234 usage(); 235 236 if (fname != NULL) 237 get_lines(fname, &lines, &nlines); 238 else if (nflag == 0) { 239 lines = argv; 240 nlines = argc; 241 } 242 243 if (nlines > 0) 244 shuffle = get_shuffle(nlines); 245 246 if (pflag) { 247 if (pick > nlines) 248 errx(1, "-p specified more components than exist."); 249 nlines = pick; 250 } 251 252 for (i = 0; i < nlines; i++) { 253 if (nflag) 254 printf("%ld", (long)shuffle[i]); 255 else 256 printf("%s", lines[shuffle[i]]); 257 putc(sep, stdout); 258 } 259 260 return 0; 261 } 262