1 /* $NetBSD: shuffle.c,v 1.11 2001/09/01 02:17:29 simonb 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.11 2001/09/01 02:17:29 simonb 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 * page 139. 114 */ 115 116 for (j = t - 1; j > 0; j--) { 117 k = random() % (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 [-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 = strtol(str, &estr, 0); 187 188 if ((number == LONG_MIN || number == LONG_MAX) && errno == ERANGE) 189 err(1, "bad -%c argument `%s'", ch, str); 190 if (*estr) 191 errx(1, "non numeric -%c argument `%s'", ch, str); 192 if (number < 0) 193 errx(1, "negative -%c argument `%s'", ch, str); 194 return (size_t) number; 195 } 196 197 int 198 main(int argc, char *argv[]) 199 { 200 int i, nflag = 0, pflag = 0, ch; 201 char *fname = NULL; 202 size_t *shuffle = NULL; 203 struct timeval tv; 204 char **lines = NULL; 205 size_t nlines = 0, pick = 0; 206 207 while ((ch = getopt(argc, argv, "f:n:p:")) != -1) { 208 switch(ch) { 209 case 'f': 210 fname = optarg; 211 break; 212 case 'n': 213 nlines = get_number(optarg, ch); 214 nflag = 1; 215 break; 216 case 'p': 217 pick = get_number(optarg, ch); 218 pflag = 1; 219 break; 220 case '?': 221 default: 222 usage(); 223 } 224 } 225 argc -= optind; 226 argv += optind; 227 228 if ((fname && nflag) || (nflag && (argc > 0))) 229 usage(); 230 231 if (fname != NULL) 232 get_lines(fname, &lines, &nlines); 233 else if (nflag == 0) { 234 lines = argv; 235 nlines = argc; 236 } 237 238 gettimeofday(&tv, NULL); 239 srandom(getpid() ^ ~getuid() ^ tv.tv_sec ^ tv.tv_usec); 240 if (nlines > 0) 241 shuffle = get_shuffle(nlines); 242 243 if (pflag) { 244 if (pick > nlines) 245 errx(1, "-p specified more components than exist."); 246 nlines = pick; 247 } 248 249 for (i = 0; i < nlines; i++) { 250 if (nflag) 251 printf("%ld\n", (long)shuffle[i]); 252 else 253 printf("%s\n", lines[shuffle[i]]); 254 } 255 256 return 0; 257 } 258