src/shuf.c

   1 /* Shuffle lines of text.
   2
   3    Copyright (C) 2006-2010 Free Software Foundation, Inc.
   4
   5    This program is free software: you can redistribute it and/or modify
   6    it under the terms of the GNU General Public License as published by
   7    the Free Software Foundation, either version 3 of the License, or
   8    (at your option) any later version.
   9
  10    This program is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13    GNU General Public License for more details.
  14
  15    You should have received a copy of the GNU General Public License
  16    along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17
  18    Written by Paul Eggert.  */
  19
  20 #include <config.h>
  21
  22 #include <sys/types.h>
  23 #include "system.h"
  24
  25 #include "error.h"
  26 #include "fadvise.h"
  27 #include "getopt.h"
  28 #include "quote.h"
  29 #include "quotearg.h"
  30 #include "randint.h"
  31 #include "randperm.h"
  32 #include "stdio--.h"
  33 #include "xstrtol.h"
  34
  35 /* The official name of this program (e.g., no `g' prefix).  */
  36 #define PROGRAM_NAME "shuf"
  37
  38 #define AUTHORS proper_name ("Paul Eggert")
  39
  40 void
  41 usage (int status)
  42 {
  43   if (status != EXIT_SUCCESS)
  44     fprintf (stderr, _("Try `%s --help' for more information.\n"),
  45              program_name);
  46   else
  47     {
  48       printf (_("\
  49 Usage: %s [OPTION]... [FILE]\n\
  50   or:  %s -e [OPTION]... [ARG]...\n\
  51   or:  %s -i LO-HI [OPTION]...\n\
  52 "),
  53               program_name, program_name, program_name);
  54       fputs (_("\
  55 Write a random permutation of the input lines to standard output.\n\
  56 \n\
  57 "), stdout);
  58       fputs (_("\
  59 Mandatory arguments to long options are mandatory for short options too.\n\
  60 "), stdout);
  61       fputs (_("\
  62   -e, --echo                treat each ARG as an input line\n\
  63   -i, --input-range=LO-HI   treat each number LO through HI as an input line\n\
  64   -n, --head-count=COUNT    output at most COUNT lines\n\
  65   -o, --output=FILE         write result to FILE instead of standard output\n\
  66       --random-source=FILE  get random bytes from FILE\n\
  67   -z, --zero-terminated     end lines with 0 byte, not newline\n\
  68 "), stdout);
  69       fputs (HELP_OPTION_DESCRIPTION, stdout);
  70       fputs (VERSION_OPTION_DESCRIPTION, stdout);
  71       fputs (_("\
  72 \n\
  73 With no FILE, or when FILE is -, read standard input.\n\
  74 "), stdout);
  75       emit_ancillary_info ();
  76     }
  77
  78   exit (status);
  79 }
  80
  81 /* For long options that have no equivalent short option, use a
  82    non-character as a pseudo short option, starting with CHAR_MAX + 1.  */
  83 enum
  84 {
  85   RANDOM_SOURCE_OPTION = CHAR_MAX + 1
  86 };
  87
  88 static struct option const long_opts[] =
  89 {
  90   {"echo", no_argument, NULL, 'e'},
  91   {"input-range", required_argument, NULL, 'i'},
  92   {"head-count", required_argument, NULL, 'n'},
  93   {"output", required_argument, NULL, 'o'},
  94   {"random-source", required_argument, NULL, RANDOM_SOURCE_OPTION},
  95   {"zero-terminated", no_argument, NULL, 'z'},
  96   {GETOPT_HELP_OPTION_DECL},
  97   {GETOPT_VERSION_OPTION_DECL},
  98   {0, 0, 0, 0},
  99 };
 100
 101 static bool
 102 input_numbers_option_used (size_t lo_input, size_t hi_input)
 103 {
 104   return ! (lo_input == SIZE_MAX && hi_input == 0);
 105 }
 106
 107 static void
 108 input_from_argv (char **operand, int n_operands, char eolbyte)
 109 {
 110   char *p;
 111   size_t size = n_operands;
 112   int i;
 113
 114   for (i = 0; i < n_operands; i++)
 115     size += strlen (operand[i]);
 116   p = xmalloc (size);
 117
 118   for (i = 0; i < n_operands; i++)
 119     {
 120       char *p1 = stpcpy (p, operand[i]);
 121       operand[i] = p;
 122       p = p1;
 123       *p++ = eolbyte;
 124     }
 125
 126   operand[n_operands] = p;
 127 }
 128
 129 /* Return the start of the next line after LINE.  The current line
 130    ends in EOLBYTE, and is guaranteed to end before LINE + N.  */
 131
 132 static char *
 133 next_line (char *line, char eolbyte, size_t n)
 134 {
 135   char *p = memchr (line, eolbyte, n);
 136   return p + 1;
 137 }
 138
 139 /* Read data from file IN.  Input lines are delimited by EOLBYTE;
 140    silently append a trailing EOLBYTE if the file ends in some other
 141    byte.  Store a pointer to the resulting array of lines into *PLINE.
 142    Return the number of lines read.  Report an error and exit on
 143    failure.  */
 144
 145 static size_t
 146 read_input (FILE *in, char eolbyte, char ***pline)
 147 {
 148   char *p;
 149   char *buf = NULL;
 150   char *lim;
 151   size_t alloc = 0;
 152   size_t used = 0;
 153   size_t next_alloc = (1 << 13) + 1;
 154   size_t bytes_to_read;
 155   size_t nread;
 156   char **line;
 157   size_t i;
 158   size_t n_lines;
 159   int fread_errno;
 160   struct stat instat;
 161
 162   if (fstat (fileno (in), &instat) == 0 && S_ISREG (instat.st_mode))
 163     {
 164       off_t file_size = instat.st_size;
 165       off_t current_offset = ftello (in);
 166       if (0 <= current_offset)
 167         {
 168           off_t remaining_size =
 169             (current_offset < file_size ? file_size - current_offset : 0);
 170           if (SIZE_MAX - 2 < remaining_size)
 171             xalloc_die ();
 172           next_alloc = remaining_size + 2;
 173         }
 174     }
 175
 176   do
 177     {
 178       if (alloc <= used + 1)
 179         {
 180           if (alloc == SIZE_MAX)
 181             xalloc_die ();
 182           alloc = next_alloc;
 183           next_alloc = alloc * 2;
 184           if (next_alloc < alloc)
 185             next_alloc = SIZE_MAX;
 186           buf = xrealloc (buf, alloc);
 187         }
 188
 189       bytes_to_read = alloc - used - 1;
 190       nread = fread (buf + used, sizeof (char), bytes_to_read, in);
 191       used += nread;
 192     }
 193   while (nread == bytes_to_read);
 194
 195   fread_errno = errno;
 196
 197   if (used && buf[used - 1] != eolbyte)
 198     buf[used++] = eolbyte;
 199
 200   lim = buf + used;
 201
 202   n_lines = 0;
 203   for (p = buf; p < lim; p = next_line (p, eolbyte, lim - p))
 204     n_lines++;
 205
 206   *pline = line = xnmalloc (n_lines + 1, sizeof *line);
 207
 208   line[0] = p = buf;
 209   for (i = 1; i <= n_lines; i++)
 210     line[i] = p = next_line (p, eolbyte, lim - p);
 211
 212   errno = fread_errno;
 213   return n_lines;
 214 }
 215
 216 static int
 217 write_permuted_output (size_t n_lines, char * const *line, size_t lo_input,
 218                        size_t const *permutation, char eolbyte)
 219 {
 220   size_t i;
 221
 222   if (line)
 223     for (i = 0; i < n_lines; i++)
 224       {
 225         char * const *p = line + permutation[i];
 226         size_t len = p[1] - p[0];
 227         if (fwrite (p[0], sizeof *p[0], len, stdout) != len)
 228           return -1;
 229       }
 230   else
 231     for (i = 0; i < n_lines; i++)
 232       {
 233         unsigned long int n = lo_input + permutation[i];
 234         if (printf ("%lu%c", n, eolbyte) < 0)
 235           return -1;
 236       }
 237
 238   return 0;
 239 }
 240
 241 int
 242 main (int argc, char **argv)
 243 {
 244   bool echo = false;
 245   size_t lo_input = SIZE_MAX;
 246   size_t hi_input = 0;
 247   size_t head_lines = SIZE_MAX;
 248   char const *outfile = NULL;
 249   char *random_source = NULL;
 250   char eolbyte = '\n';
 251   char **input_lines = NULL;
 252
 253   int optc;
 254   int n_operands;
 255   char **operand;
 256   size_t n_lines;
 257   char **line;
 258   struct randint_source *randint_source;
 259   size_t *permutation;
 260
 261   initialize_main (&argc, &argv);
 262   set_program_name (argv[0]);
 263   setlocale (LC_ALL, "");
 264   bindtextdomain (PACKAGE, LOCALEDIR);
 265   textdomain (PACKAGE);
 266
 267   atexit (close_stdout);
 268
 269   while ((optc = getopt_long (argc, argv, "ei:n:o:z", long_opts, NULL)) != -1)
 270     switch (optc)
 271       {
 272       case 'e':
 273         echo = true;
 274         break;
 275
 276       case 'i':
 277         {
 278           unsigned long int argval = 0;
 279           char *p = strchr (optarg, '-');
 280           char const *hi_optarg = optarg;
 281           bool invalid = !p;
 282
 283           if (input_numbers_option_used (lo_input, hi_input))
 284             error (EXIT_FAILURE, 0, _("multiple -i options specified"));
 285
 286           if (p)
 287             {
 288               *p = '\0';
 289               invalid = ((xstrtoul (optarg, NULL, 10, &argval, NULL)
 290                           != LONGINT_OK)
 291                          || SIZE_MAX < argval);
 292               *p = '-';
 293               lo_input = argval;
 294               hi_optarg = p + 1;
 295             }
 296
 297           invalid |= ((xstrtoul (hi_optarg, NULL, 10, &argval, NULL)
 298                        != LONGINT_OK)
 299                       || SIZE_MAX < argval);
 300           hi_input = argval;
 301           n_lines = hi_input - lo_input + 1;
 302           invalid |= ((lo_input <= hi_input) == (n_lines == 0));
 303           if (invalid)
 304             error (EXIT_FAILURE, 0, _("invalid input range %s"),
 305                    quote (optarg));
 306         }
 307         break;
 308
 309       case 'n':
 310         {
 311           unsigned long int argval;
 312           strtol_error e = xstrtoul (optarg, NULL, 10, &argval, NULL);
 313
 314           if (e == LONGINT_OK)
 315             head_lines = MIN (head_lines, argval);
 316           else if (e != LONGINT_OVERFLOW)
 317             error (EXIT_FAILURE, 0, _("invalid line count %s"),
 318                    quote (optarg));
 319         }
 320         break;
 321
 322       case 'o':
 323         if (outfile && !STREQ (outfile, optarg))
 324           error (EXIT_FAILURE, 0, _("multiple output files specified"));
 325         outfile = optarg;
 326         break;
 327
 328       case RANDOM_SOURCE_OPTION:
 329         if (random_source && !STREQ (random_source, optarg))
 330           error (EXIT_FAILURE, 0, _("multiple random sources specified"));
 331         random_source = optarg;
 332         break;
 333
 334       case 'z':
 335         eolbyte = '\0';
 336         break;
 337
 338       case_GETOPT_HELP_CHAR;
 339       case_GETOPT_VERSION_CHAR (PROGRAM_NAME, AUTHORS);
 340       default:
 341         usage (EXIT_FAILURE);
 342       }
 343
 344   n_operands = argc - optind;
 345   operand = argv + optind;
 346
 347   if (echo)
 348     {
 349       if (input_numbers_option_used (lo_input, hi_input))
 350         error (EXIT_FAILURE, 0, _("cannot combine -e and -i options"));
 351       input_from_argv (operand, n_operands, eolbyte);
 352       n_lines = n_operands;
 353       line = operand;
 354     }
 355   else if (input_numbers_option_used (lo_input, hi_input))
 356     {
 357       if (n_operands)
 358         {
 359           error (0, 0, _("extra operand %s"), quote (operand[0]));
 360           usage (EXIT_FAILURE);
 361         }
 362       n_lines = hi_input - lo_input + 1;
 363       line = NULL;
 364     }
 365   else
 366     {
 367       switch (n_operands)
 368         {
 369         case 0:
 370           break;
 371
 372         case 1:
 373           if (! (STREQ (operand[0], "-") || freopen (operand[0], "r", stdin)))
 374             error (EXIT_FAILURE, errno, "%s", operand[0]);
 375           break;
 376
 377         default:
 378           error (0, 0, _("extra operand %s"), quote (operand[1]));
 379           usage (EXIT_FAILURE);
 380         }
 381
 382       fadvise (stdin, FADVISE_SEQUENTIAL);
 383
 384       n_lines = read_input (stdin, eolbyte, &input_lines);
 385       line = input_lines;
 386     }
 387
 388   head_lines = MIN (head_lines, n_lines);
 389
 390   randint_source = randint_all_new (random_source,
 391                                     randperm_bound (head_lines, n_lines));
 392   if (! randint_source)
 393     error (EXIT_FAILURE, errno, "%s", quotearg_colon (random_source));
 394
 395   /* Close stdin now, rather than earlier, so that randint_all_new
 396      doesn't have to worry about opening something other than
 397      stdin.  */
 398   if (! (echo || input_numbers_option_used (lo_input, hi_input))
 399       && (ferror (stdin) || fclose (stdin) != 0))
 400     error (EXIT_FAILURE, errno, _("read error"));
 401
 402   permutation = randperm_new (randint_source, head_lines, n_lines);
 403
 404   if (outfile && ! freopen (outfile, "w", stdout))
 405     error (EXIT_FAILURE, errno, "%s", quotearg_colon (outfile));
 406   if (write_permuted_output (head_lines, line, lo_input, permutation, eolbyte)
 407       != 0)
 408     error (EXIT_FAILURE, errno, _("write error"));
 409
 410 #ifdef lint
 411   free (permutation);
 412   randint_all_free (randint_source);
 413   if (input_lines)
 414     {
 415       free (input_lines[0]);
 416       free (input_lines);
 417     }
 418 #endif
 419
 420   return EXIT_SUCCESS;
 421 }