src/sort.c

   1 /* sort - sort lines of text (with all kinds of options).
   2    Copyright (C) 1988, 1991, 1992, 1993, 1994, 1995 Free Software Foundation
   3
   4    This program is free software; you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation; either version 2, or (at your option)
   7    any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program; if not, write to the Free Software
  16    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  17
  18    Written December 1988 by Mike Haertel.
  19    The author may be reached (Email) at the address mike@gnu.ai.mit.edu,
  20    or (US mail) as Mike Haertel c/o Free Software Foundation. */
  21
  22 #include <config.h>
  23
  24 /* Get isblank from GNU libc.  */
  25 #define _GNU_SOURCE
  26
  27 #include <sys/types.h>
  28 #include <signal.h>
  29 #include <stdio.h>
  30 #include "system.h"
  31 #include "long-options.h"
  32 #include "error.h"
  33 #include "xstrtod.h"
  34
  35 #ifdef HAVE_LIMITS_H
  36 #include <limits.h>
  37 #else
  38 #ifndef UCHAR_MAX
  39 #define UCHAR_MAX 255
  40 #endif
  41 #endif
  42 #ifndef STDC_HEADERS
  43 char *malloc ();
  44 char *realloc ();
  45 void free ();
  46 #endif
  47
  48 /* Undefine, to avoid warning about redefinition on some systems.  */
  49 #undef min
  50 #define min(a, b) ((a) < (b) ? (a) : (b))
  51
  52 #define UCHAR_LIM (UCHAR_MAX + 1)
  53 #define UCHAR(c) ((unsigned char) (c))
  54
  55 #ifndef DEFAULT_TMPDIR
  56 #define DEFAULT_TMPDIR "/tmp"
  57 #endif
  58
  59 /* The kind of blanks for '-b' to skip in various options. */
  60 enum blanktype { bl_start, bl_end, bl_both };
  61
  62 /* The character marking end of line. Default to \n. */
  63 int eolchar = '\n';
  64
  65 /* Lines are held in core as counted strings. */
  66 struct line
  67 {
  68   char *text;                   /* Text of the line. */
  69   int length;                   /* Length not including final newline. */
  70   char *keybeg;                 /* Start of first key. */
  71   char *keylim;                 /* Limit of first key. */
  72 };
  73
  74 /* Arrays of lines. */
  75 struct lines
  76 {
  77   struct line *lines;           /* Dynamically allocated array of lines. */
  78   int used;                     /* Number of slots used. */
  79   int alloc;                    /* Number of slots allocated. */
  80   int limit;                    /* Max number of slots to allocate.  */
  81 };
  82
  83 /* Input buffers. */
  84 struct buffer
  85 {
  86   char *buf;                    /* Dynamically allocated buffer. */
  87   int used;                     /* Number of bytes used. */
  88   int alloc;                    /* Number of bytes allocated. */
  89   int left;                     /* Number of bytes left after line parsing. */
  90 };
  91
  92 struct keyfield
  93 {
  94   int sword;                    /* Zero-origin 'word' to start at. */
  95   int schar;                    /* Additional characters to skip. */
  96   int skipsblanks;              /* Skip leading white space at start. */
  97   int eword;                    /* Zero-origin first word after field. */
  98   int echar;                    /* Additional characters in field. */
  99   int skipeblanks;              /* Skip trailing white space at finish. */
 100   int *ignore;                  /* Boolean array of characters to ignore. */
 101   char *translate;              /* Translation applied to characters. */
 102   int numeric;                  /* Flag for numeric comparison.  Handle
 103                                    strings of digits with optional decimal
 104                                    point, but no exponential notation. */
 105   int general_numeric;          /* Flag for general, numeric comparison.
 106                                    Handle numbers in exponential notation. */
 107   int month;                    /* Flag for comparison by month name. */
 108   int reverse;                  /* Reverse the sense of comparison. */
 109   struct keyfield *next;        /* Next keyfield to try. */
 110 };
 111
 112 struct month
 113 {
 114   char *name;
 115   int val;
 116 };
 117
 118 /* The name this program was run with. */
 119 char *program_name;
 120
 121 /* Table of digits. */
 122 static int digits[UCHAR_LIM];
 123
 124 /* Table of white space. */
 125 static int blanks[UCHAR_LIM];
 126
 127 /* Table of non-printing characters. */
 128 static int nonprinting[UCHAR_LIM];
 129
 130 /* Table of non-dictionary characters (not letters, digits, or blanks). */
 131 static int nondictionary[UCHAR_LIM];
 132
 133 /* Translation table folding lower case to upper. */
 134 static char fold_toupper[UCHAR_LIM];
 135
 136 /* Table mapping 3-letter month names to integers.
 137    Alphabetic order allows binary search. */
 138 static struct month const monthtab[] =
 139 {
 140   {"APR", 4},
 141   {"AUG", 8},
 142   {"DEC", 12},
 143   {"FEB", 2},
 144   {"JAN", 1},
 145   {"JUL", 7},
 146   {"JUN", 6},
 147   {"MAR", 3},
 148   {"MAY", 5},
 149   {"NOV", 11},
 150   {"OCT", 10},
 151   {"SEP", 9}
 152 };
 153
 154 /* During the merge phase, the number of files to merge at once. */
 155 #define NMERGE 16
 156
 157 /* Initial buffer size for in core sorting.  Will not grow unless a
 158    line longer than this is seen. */
 159 static int sortalloc = 512 * 1024;
 160
 161 /* Initial buffer size for in core merge buffers.  Bear in mind that
 162    up to NMERGE * mergealloc bytes may be allocated for merge buffers. */
 163 static int mergealloc =  16 * 1024;
 164
 165 /* Guess of average line length. */
 166 static int linelength = 30;
 167
 168 /* Maximum number of elements for the array(s) of struct line's, in bytes.  */
 169 #define LINEALLOC (256 * 1024)
 170
 171 /* Prefix for temporary file names. */
 172 static char *temp_file_prefix;
 173
 174 /* Flag to reverse the order of all comparisons. */
 175 static int reverse;
 176
 177 /* Flag for stable sort.  This turns off the last ditch bytewise
 178    comparison of lines, and instead leaves lines in the same order
 179    they were read if all keys compare equal.  */
 180 static int stable;
 181
 182 /* Tab character separating fields.  If NUL, then fields are separated
 183    by the empty string between a non-whitespace character and a whitespace
 184    character. */
 185 static char tab;
 186
 187 /* Flag to remove consecutive duplicate lines from the output.
 188    Only the last of a sequence of equal lines will be output. */
 189 static int unique;
 190
 191 /* Nonzero if any of the input files are the standard input. */
 192 static int have_read_stdin;
 193
 194 /* Lists of key field comparisons to be tried. */
 195 static struct keyfield keyhead;
 196
 197 static void
 198 usage (int status)
 199 {
 200   if (status != 0)
 201     fprintf (stderr, _("Try `%s --help' for more information.\n"),
 202              program_name);
 203   else
 204     {
 205       printf (_("\
 206 Usage: %s [OPTION]... [FILE]...\n\
 207 "),
 208               program_name);
 209       printf (_("\
 210 Write sorted concatenation of all FILE(s) to standard output.\n\
 211 \n\
 212   +POS1 [-POS2]    start a key at POS1, end it before POS2\n\
 213   -M               compare (unknown) < `JAN' < ... < `DEC', imply -b\n\
 214   -T DIRECT        use DIRECT for temporary files, not $TMPDIR or %s\n\
 215   -b               ignore leading blanks in sort fields or keys\n\
 216   -c               check if given files already sorted, do not sort\n\
 217   -d               consider only [a-zA-Z0-9 ] characters in keys\n\
 218   -f               fold lower case to upper case characters in keys\n\
 219   -g               compare according to general numerical value, imply -b\n\
 220   -i               consider only [\\040-\\0176] characters in keys\n\
 221   -k POS1[,POS2]   same as +POS1 [-POS2], but all positions counted from 1\n\
 222   -m               merge already sorted files, do not sort\n\
 223   -n               compare according to string numerical value, imply -b\n\
 224   -o FILE          write result on FILE instead of standard output\n\
 225   -r               reverse the result of comparisons\n\
 226   -s               stabilize sort by disabling last resort comparison\n\
 227   -t SEP           use SEParator instead of non- to whitespace transition\n\
 228   -u               with -c, check for strict ordering\n\
 229   -u               with -m, only output the first of an equal sequence\n\
 230   -z               end lines with 0 byte, not newline, for find -print0\n\
 231       --help       display this help and exit\n\
 232       --version    output version information and exit\n\
 233 \n\
 234 POS is F[.C][OPTS], where F is the field number and C the character\n\
 235 position in the field, both counted from zero.  OPTS is made up of one\n\
 236 or more of Mbdfinr, this effectively disable global -Mbdfinr settings\n\
 237 for that key.  If no key given, use the entire line as key.  With no\n\
 238 FILE, or when FILE is -, read standard input.\n\
 239 ")
 240               , DEFAULT_TMPDIR);
 241     }
 242   exit (status);
 243 }
 244
 245 /* The list of temporary files. */
 246 static struct tempnode
 247 {
 248   char *name;
 249   struct tempnode *next;
 250 } temphead;
 251
 252 /* Clean up any remaining temporary files. */
 253
 254 static void
 255 cleanup (void)
 256 {
 257   struct tempnode *node;
 258
 259   for (node = temphead.next; node; node = node->next)
 260     unlink (node->name);
 261 }
 262
 263 /* Allocate N bytes of memory dynamically, with error checking.  */
 264
 265 static char *
 266 xmalloc (unsigned int n)
 267 {
 268   char *p;
 269
 270   p = malloc (n);
 271   if (p == 0)
 272     {
 273       error (0, 0, _("virtual memory exhausted"));
 274       cleanup ();
 275       exit (2);
 276     }
 277   return p;
 278 }
 279
 280 /* Change the size of an allocated block of memory P to N bytes,
 281    with error checking.
 282    If P is NULL, run xmalloc.
 283    If N is 0, run free and return NULL.  */
 284
 285 static char *
 286 xrealloc (char *p, unsigned int n)
 287 {
 288   if (p == 0)
 289     return xmalloc (n);
 290   if (n == 0)
 291     {
 292       free (p);
 293       return 0;
 294     }
 295   p = realloc (p, n);
 296   if (p == 0)
 297     {
 298       error (0, 0, _("virtual memory exhausted"));
 299       cleanup ();
 300       exit (2);
 301     }
 302   return p;
 303 }
 304
 305 static FILE *
 306 xtmpfopen (const char *file)
 307 {
 308   FILE *fp;
 309   int fd;
 310
 311   fd = open (file, O_WRONLY | O_CREAT | O_TRUNC, 0600);
 312   if (fd < 0 || (fp = fdopen (fd, "w")) == NULL)
 313     {
 314       error (0, errno, "%s", file);
 315       cleanup ();
 316       exit (2);
 317     }
 318
 319   return fp;
 320 }
 321
 322 static FILE *
 323 xfopen (const char *file, const char *how)
 324 {
 325   FILE *fp;
 326
 327   if (strcmp (file, "-") == 0)
 328     {
 329       fp = stdin;
 330     }
 331   else
 332     {
 333       if ((fp = fopen (file, how)) == NULL)
 334         {
 335           error (0, errno, "%s", file);
 336           cleanup ();
 337           exit (2);
 338         }
 339     }
 340
 341   if (fp == stdin)
 342     have_read_stdin = 1;
 343   return fp;
 344 }
 345
 346 static void
 347 xfclose (FILE *fp)
 348 {
 349   if (fp == stdin)
 350     {
 351       /* Allow reading stdin from tty more than once. */
 352       if (feof (fp))
 353         clearerr (fp);
 354     }
 355   else if (fp == stdout)
 356     {
 357       if (fflush (fp) != 0)
 358         {
 359           error (0, errno, _("flushing file"));
 360           cleanup ();
 361           exit (2);
 362         }
 363     }
 364   else
 365     {
 366       if (fclose (fp) != 0)
 367         {
 368           error (0, errno, _("error closing file"));
 369           cleanup ();
 370           exit (2);
 371         }
 372     }
 373 }
 374
 375 static void
 376 write_bytes (const char *buf, size_t n_bytes, FILE *fp)
 377 {
 378   if (fwrite (buf, 1, n_bytes, fp) != n_bytes)
 379     {
 380       error (0, errno, _("write error"));
 381       cleanup ();
 382       exit (2);
 383     }
 384 }
 385
 386 /* Return a name for a temporary file. */
 387
 388 static char *
 389 tempname (void)
 390 {
 391   static unsigned int seq;
 392   int len = strlen (temp_file_prefix);
 393   char *name = xmalloc (len + 1 + sizeof ("sort") - 1 + 5 + 5 + 1);
 394   struct tempnode *node;
 395
 396   node = (struct tempnode *) xmalloc (sizeof (struct tempnode));
 397   sprintf (name,
 398            "%s%ssort%5.5d%5.5d",
 399            temp_file_prefix,
 400            (len && temp_file_prefix[len - 1] != '/') ? "/" : "",
 401            (unsigned int) getpid () & 0xffff, seq);
 402
 403   /* Make sure that SEQ's value fits in 5 digits.  */
 404   ++seq;
 405   if (seq >= 100000)
 406     seq = 0;
 407
 408   node->name = name;
 409   node->next = temphead.next;
 410   temphead.next = node;
 411   return name;
 412 }
 413
 414 /* Search through the list of temporary files for NAME;
 415    remove it if it is found on the list. */
 416
 417 static void
 418 zaptemp (char *name)
 419 {
 420   struct tempnode *node, *temp;
 421
 422   for (node = &temphead; node->next; node = node->next)
 423     if (!strcmp (name, node->next->name))
 424       break;
 425   if (node->next)
 426     {
 427       temp = node->next;
 428       unlink (temp->name);
 429       free (temp->name);
 430       node->next = temp->next;
 431       free ((char *) temp);
 432     }
 433 }
 434
 435 /* Initialize the character class tables. */
 436
 437 static void
 438 inittables (void)
 439 {
 440   int i;
 441
 442   for (i = 0; i < UCHAR_LIM; ++i)
 443     {
 444       if (ISBLANK (i))
 445         blanks[i] = 1;
 446       if (ISDIGIT (i))
 447         digits[i] = 1;
 448       if (!ISPRINT (i))
 449         nonprinting[i] = 1;
 450       if (!ISALNUM (i) && !ISBLANK (i))
 451         nondictionary[i] = 1;
 452       if (ISLOWER (i))
 453         fold_toupper[i] = toupper (i);
 454       else
 455         fold_toupper[i] = i;
 456     }
 457 }
 458
 459 /* Initialize BUF, allocating ALLOC bytes initially. */
 460
 461 static void
 462 initbuf (struct buffer *buf, int alloc)
 463 {
 464   buf->alloc = alloc;
 465   buf->buf = xmalloc (buf->alloc);
 466   buf->used = buf->left = 0;
 467 }
 468
 469 /* Fill BUF reading from FP, moving buf->left bytes from the end
 470    of buf->buf to the beginning first.  If EOF is reached and the
 471    file wasn't terminated by a newline, supply one.  Return a count
 472    of bytes buffered. */
 473
 474 static int
 475 fillbuf (struct buffer *buf, FILE *fp)
 476 {
 477   int cc;
 478
 479   memmove (buf->buf, buf->buf + buf->used - buf->left, buf->left);
 480   buf->used = buf->left;
 481
 482   while (!feof (fp) && (buf->used == 0 || !memchr (buf->buf, eolchar, buf->used)))
 483     {
 484       if (buf->used == buf->alloc)
 485         {
 486           buf->alloc *= 2;
 487           buf->buf = xrealloc (buf->buf, buf->alloc);
 488         }
 489       cc = fread (buf->buf + buf->used, 1, buf->alloc - buf->used, fp);
 490       if (ferror (fp))
 491         {
 492           error (0, errno, _("read error"));
 493           cleanup ();
 494           exit (2);
 495         }
 496       buf->used += cc;
 497     }
 498
 499   if (feof (fp) && buf->used && buf->buf[buf->used - 1] != eolchar)
 500     {
 501       if (buf->used == buf->alloc)
 502         {
 503           buf->alloc *= 2;
 504           buf->buf = xrealloc (buf->buf, buf->alloc);
 505         }
 506       buf->buf[buf->used++] = eolchar;
 507     }
 508
 509   return buf->used;
 510 }
 511
 512 /* Initialize LINES, allocating space for ALLOC lines initially.
 513    LIMIT is the maximum possible number of lines to allocate space
 514    for, ever.  */
 515
 516 static void
 517 initlines (struct lines *lines, int alloc, int limit)
 518 {
 519   lines->alloc = alloc;
 520   lines->lines = (struct line *) xmalloc (lines->alloc * sizeof (struct line));
 521   lines->used = 0;
 522   lines->limit = limit;
 523 }
 524
 525 /* Return a pointer to the first character of the field specified
 526    by KEY in LINE. */
 527
 528 static char *
 529 begfield (const struct line *line, const struct keyfield *key)
 530 {
 531   register char *ptr = line->text, *lim = ptr + line->length;
 532   register int sword = key->sword, schar = key->schar;
 533
 534   if (tab)
 535     while (ptr < lim && sword--)
 536       {
 537         while (ptr < lim && *ptr != tab)
 538           ++ptr;
 539         if (ptr < lim)
 540           ++ptr;
 541       }
 542   else
 543     while (ptr < lim && sword--)
 544       {
 545         while (ptr < lim && blanks[UCHAR (*ptr)])
 546           ++ptr;
 547         while (ptr < lim && !blanks[UCHAR (*ptr)])
 548           ++ptr;
 549       }
 550
 551   if (key->skipsblanks)
 552     while (ptr < lim && blanks[UCHAR (*ptr)])
 553       ++ptr;
 554
 555   if (ptr + schar <= lim)
 556     ptr += schar;
 557   else
 558     ptr = lim;
 559
 560   return ptr;
 561 }
 562
 563 /* Return the limit of (a pointer to the first character after) the field
 564    in LINE specified by KEY. */
 565
 566 static char *
 567 limfield (const struct line *line, const struct keyfield *key)
 568 {
 569   register char *ptr = line->text, *lim = ptr + line->length;
 570   register int eword = key->eword, echar = key->echar;
 571
 572   /* Note: from the POSIX spec:
 573      The leading field separator itself is included in
 574      a field when -t is not used.  FIXME: move this comment up... */
 575
 576   /* Move PTR past EWORD fields or to one past the last byte on LINE,
 577      whichever comes first.  If there are more than EWORD fields, leave
 578      PTR pointing at the beginning of the field having zero-based index,
 579      EWORD.  If a delimiter character was specified (via -t), then that
 580      `beginning' is the first character following the delimiting TAB.
 581      Otherwise, leave PTR pointing at the first `blank' character after
 582      the preceding field.  */
 583   if (tab)
 584     while (ptr < lim && eword--)
 585       {
 586         while (ptr < lim && *ptr != tab)
 587           ++ptr;
 588         if (ptr < lim && (eword || echar > 0))
 589           ++ptr;
 590       }
 591   else
 592     while (ptr < lim && eword--)
 593       {
 594         while (ptr < lim && blanks[UCHAR (*ptr)])
 595           ++ptr;
 596         while (ptr < lim && !blanks[UCHAR (*ptr)])
 597           ++ptr;
 598       }
 599
 600   /* Make LIM point to the end of (one byte past) the current field.  */
 601   if (tab)
 602     {
 603       char *newlim;
 604       newlim = memchr (ptr, tab, lim - ptr);
 605       if (newlim)
 606         lim = newlim;
 607     }
 608   else
 609     {
 610       char *newlim;
 611       newlim = ptr;
 612       while (newlim < lim && blanks[UCHAR (*newlim)])
 613         ++newlim;
 614       while (newlim < lim && !blanks[UCHAR (*newlim)])
 615         ++newlim;
 616       lim = newlim;
 617     }
 618
 619   /* If we're skipping leading blanks, don't start counting characters
 620      until after skipping past any leading blanks.  */
 621   if (key->skipsblanks)
 622     while (ptr < lim && blanks[UCHAR (*ptr)])
 623       ++ptr;
 624
 625   /* Advance PTR by ECHAR (if possible), but no further than LIM.  */
 626   if (ptr + echar <= lim)
 627     ptr += echar;
 628   else
 629     ptr = lim;
 630
 631   return ptr;
 632 }
 633
 634 /* FIXME */
 635
 636 void
 637 trim_trailing_blanks (const char *a_start, char **a_end)
 638 {
 639   while (*a_end > a_start && blanks[UCHAR (*(*a_end - 1))])
 640     --(*a_end);
 641 }
 642
 643 /* Find the lines in BUF, storing pointers and lengths in LINES.
 644    Also replace newlines in BUF with NULs. */
 645
 646 static void
 647 findlines (struct buffer *buf, struct lines *lines)
 648 {
 649   register char *beg = buf->buf, *lim = buf->buf + buf->used, *ptr;
 650   struct keyfield *key = keyhead.next;
 651
 652   lines->used = 0;
 653
 654   while (beg < lim && (ptr = memchr (beg, eolchar, lim - beg))
 655          && lines->used < lines->limit)
 656     {
 657       /* There are various places in the code that rely on a NUL
 658          being at the end of in-core lines; NULs inside the lines
 659          will not cause trouble, though. */
 660       *ptr = '\0';
 661
 662       if (lines->used == lines->alloc)
 663         {
 664           lines->alloc *= 2;
 665           lines->lines = (struct line *)
 666             xrealloc ((char *) lines->lines,
 667                       lines->alloc * sizeof (struct line));
 668         }
 669
 670       lines->lines[lines->used].text = beg;
 671       lines->lines[lines->used].length = ptr - beg;
 672
 673       /* Precompute the position of the first key for efficiency. */
 674       if (key)
 675         {
 676           if (key->eword >= 0)
 677             lines->lines[lines->used].keylim =
 678               limfield (&lines->lines[lines->used], key);
 679           else
 680             lines->lines[lines->used].keylim = ptr;
 681
 682           if (key->sword >= 0)
 683             lines->lines[lines->used].keybeg =
 684               begfield (&lines->lines[lines->used], key);
 685           else
 686             {
 687               if (key->skipsblanks)
 688                 while (blanks[UCHAR (*beg)])
 689                   ++beg;
 690               lines->lines[lines->used].keybeg = beg;
 691             }
 692           if (key->skipeblanks)
 693             {
 694               trim_trailing_blanks (lines->lines[lines->used].keybeg,
 695                                     &lines->lines[lines->used].keylim);
 696             }
 697         }
 698       else
 699         {
 700           lines->lines[lines->used].keybeg = 0;
 701           lines->lines[lines->used].keylim = 0;
 702         }
 703
 704       ++lines->used;
 705       beg = ptr + 1;
 706     }
 707
 708   buf->left = lim - beg;
 709 }
 710
 711 /* Compare strings A and B containing decimal fractions < 1.  Each string
 712    should begin with a decimal point followed immediately by the digits
 713    of the fraction.  Strings not of this form are considered to be zero. */
 714
 715 static int
 716 fraccompare (register const char *a, register const char *b)
 717 {
 718   register tmpa = UCHAR (*a), tmpb = UCHAR (*b);
 719
 720   if (tmpa == '.' && tmpb == '.')
 721     {
 722       do
 723         tmpa = UCHAR (*++a), tmpb = UCHAR (*++b);
 724       while (tmpa == tmpb && digits[tmpa]);
 725       if (digits[tmpa] && digits[tmpb])
 726         return tmpa - tmpb;
 727       if (digits[tmpa])
 728         {
 729           while (tmpa == '0')
 730             tmpa = UCHAR (*++a);
 731           if (digits[tmpa])
 732             return 1;
 733           return 0;
 734         }
 735       if (digits[tmpb])
 736         {
 737           while (tmpb == '0')
 738             tmpb = UCHAR (*++b);
 739           if (digits[tmpb])
 740             return -1;
 741           return 0;
 742         }
 743       return 0;
 744     }
 745   else if (tmpa == '.')
 746     {
 747       do
 748         tmpa = UCHAR (*++a);
 749       while (tmpa == '0');
 750       if (digits[tmpa])
 751         return 1;
 752       return 0;
 753     }
 754   else if (tmpb == '.')
 755     {
 756       do
 757         tmpb = UCHAR (*++b);
 758       while (tmpb == '0');
 759       if (digits[tmpb])
 760         return -1;
 761       return 0;
 762     }
 763   return 0;
 764 }
 765
 766 /* Compare strings A and B as numbers without explicitly converting them to
 767    machine numbers.  Comparatively slow for short strings, but asymptotically
 768    hideously fast. */
 769
 770 static int
 771 numcompare (register const char *a, register const char *b)
 772 {
 773   register int tmpa, tmpb, loga, logb, tmp;
 774
 775   tmpa = UCHAR (*a);
 776   tmpb = UCHAR (*b);
 777
 778   while (blanks[tmpa])
 779     tmpa = UCHAR (*++a);
 780   while (blanks[tmpb])
 781     tmpb = UCHAR (*++b);
 782
 783   if (tmpa == '-')
 784     {
 785       do
 786         tmpa = UCHAR (*++a);
 787       while (tmpa == '0');
 788       if (tmpb != '-')
 789         {
 790           if (tmpa == '.')
 791             do
 792               tmpa = UCHAR (*++a);
 793             while (tmpa == '0');
 794           if (digits[tmpa])
 795             return -1;
 796           while (tmpb == '0')
 797             tmpb = UCHAR (*++b);
 798           if (tmpb == '.')
 799             do
 800               tmpb = *++b;
 801             while (tmpb == '0');
 802           if (digits[tmpb])
 803             return -1;
 804           return 0;
 805         }
 806       do
 807         tmpb = UCHAR (*++b);
 808       while (tmpb == '0');
 809
 810       while (tmpa == tmpb && digits[tmpa])
 811         tmpa = UCHAR (*++a), tmpb = UCHAR (*++b);
 812
 813       if ((tmpa == '.' && !digits[tmpb]) || (tmpb == '.' && !digits[tmpa]))
 814         return -fraccompare (a, b);
 815
 816       if (digits[tmpa])
 817         for (loga = 1; digits[UCHAR (*++a)]; ++loga)
 818           ;
 819       else
 820         loga = 0;
 821
 822       if (digits[tmpb])
 823         for (logb = 1; digits[UCHAR (*++b)]; ++logb)
 824           ;
 825       else
 826         logb = 0;
 827
 828       if ((tmp = logb - loga) != 0)
 829         return tmp;
 830
 831       if (!loga)
 832         return 0;
 833
 834       return tmpb - tmpa;
 835     }
 836   else if (tmpb == '-')
 837     {
 838       do
 839         tmpb = UCHAR (*++b);
 840       while (tmpb == '0');
 841       if (tmpb == '.')
 842         do
 843           tmpb = *++b;
 844         while (tmpb == '0');
 845       if (digits[tmpb])
 846         return 1;
 847       while (tmpa == '0')
 848         tmpa = UCHAR (*++a);
 849       if (tmpa == '.')
 850         do
 851           tmpa = UCHAR (*++a);
 852         while (tmpa == '0');
 853       if (digits[tmpa])
 854         return 1;
 855       return 0;
 856     }
 857   else
 858     {
 859       while (tmpa == '0')
 860         tmpa = UCHAR (*++a);
 861       while (tmpb == '0')
 862         tmpb = UCHAR (*++b);
 863
 864       while (tmpa == tmpb && digits[tmpa])
 865         tmpa = UCHAR (*++a), tmpb = UCHAR (*++b);
 866
 867       if ((tmpa == '.' && !digits[tmpb]) || (tmpb == '.' && !digits[tmpa]))
 868         return fraccompare (a, b);
 869
 870       if (digits[tmpa])
 871         for (loga = 1; digits[UCHAR (*++a)]; ++loga)
 872           ;
 873       else
 874         loga = 0;
 875
 876       if (digits[tmpb])
 877         for (logb = 1; digits[UCHAR (*++b)]; ++logb)
 878           ;
 879       else
 880         logb = 0;
 881
 882       if ((tmp = loga - logb) != 0)
 883         return tmp;
 884
 885       if (!loga)
 886         return 0;
 887
 888       return tmpa - tmpb;
 889     }
 890 }
 891
 892 static int
 893 general_numcompare (const char *sa, const char *sb)
 894 {
 895   double a, b;
 896   /* FIXME: add option to warn about failed conversions.  */
 897   /* FIXME: maybe add option to try expensive FP conversion
 898      only if A and B can't be compared more cheaply/accurately.  */
 899   if (xstrtod (sa, NULL, &a))
 900     {
 901       a = 0;
 902     }
 903   if (xstrtod (sb, NULL, &b))
 904     {
 905       b = 0;
 906     }
 907   return a == b ? 0 : a < b ? -1 : 1;
 908 }
 909
 910 /* Return an integer <= 12 associated with month name S with length LEN,
 911    0 if the name in S is not recognized. */
 912
 913 static int
 914 getmonth (const char *s, int len)
 915 {
 916   char month[4];
 917   register int i, lo = 0, hi = 12;
 918
 919   while (len > 0 && blanks[UCHAR(*s)])
 920     ++s, --len;
 921
 922   if (len < 3)
 923     return 0;
 924
 925   for (i = 0; i < 3; ++i)
 926     month[i] = fold_toupper[UCHAR (s[i])];
 927   month[3] = '\0';
 928
 929   while (hi - lo > 1)
 930     if (strcmp (month, monthtab[(lo + hi) / 2].name) < 0)
 931       hi = (lo + hi) / 2;
 932     else
 933       lo = (lo + hi) / 2;
 934   if (!strcmp (month, monthtab[lo].name))
 935     return monthtab[lo].val;
 936   return 0;
 937 }
 938
 939 /* Compare two lines A and B trying every key in sequence until there
 940    are no more keys or a difference is found. */
 941
 942 static int
 943 keycompare (const struct line *a, const struct line *b)
 944 {
 945   register char *texta, *textb, *lima, *limb, *translate;
 946   register int *ignore;
 947   struct keyfield *key;
 948   int diff = 0, iter = 0, lena, lenb;
 949
 950   for (key = keyhead.next; key; key = key->next, ++iter)
 951     {
 952       ignore = key->ignore;
 953       translate = key->translate;
 954
 955       /* Find the beginning and limit of each field. */
 956       if (iter || a->keybeg == NULL || b->keybeg == NULL)
 957         {
 958           if (key->eword >= 0)
 959             lima = limfield (a, key), limb = limfield (b, key);
 960           else
 961             lima = a->text + a->length, limb = b->text + b->length;
 962
 963           if (key->sword >= 0)
 964             texta = begfield (a, key), textb = begfield (b, key);
 965           else
 966             {
 967               texta = a->text, textb = b->text;
 968               if (key->skipsblanks)
 969                 {
 970                   while (texta < lima && blanks[UCHAR (*texta)])
 971                     ++texta;
 972                   while (textb < limb && blanks[UCHAR (*textb)])
 973                     ++textb;
 974                 }
 975             }
 976         }
 977       else
 978         {
 979           /* For the first iteration only, the key positions have
 980              been precomputed for us. */
 981           texta = a->keybeg, lima = a->keylim;
 982           textb = b->keybeg, limb = b->keylim;
 983         }
 984
 985       /* Find the lengths. */
 986       lena = lima - texta, lenb = limb - textb;
 987       if (lena < 0)
 988         lena = 0;
 989       if (lenb < 0)
 990         lenb = 0;
 991
 992       if (key->skipeblanks)
 993         {
 994           char *a_end = texta + lena;
 995           char *b_end = textb + lenb;
 996           trim_trailing_blanks (texta, &a_end);
 997           trim_trailing_blanks (textb, &b_end);
 998           lena = a_end - texta;
 999           lenb = b_end - textb;
1000         }
1001
1002       /* Actually compare the fields. */
1003       if (key->numeric)
1004         {
1005           if (*lima || *limb)
1006             {
1007               char savea = *lima, saveb = *limb;
1008
1009               *lima = *limb = '\0';
1010               diff = numcompare (texta, textb);
1011               *lima = savea, *limb = saveb;
1012             }
1013           else
1014             diff = numcompare (texta, textb);
1015
1016           if (diff)
1017             return key->reverse ? -diff : diff;
1018           continue;
1019         }
1020       else if (key->general_numeric)
1021         {
1022           if (*lima || *limb)
1023             {
1024               char savea = *lima, saveb = *limb;
1025
1026               *lima = *limb = '\0';
1027               diff = general_numcompare (texta, textb);
1028               *lima = savea, *limb = saveb;
1029             }
1030           else
1031             diff = general_numcompare (texta, textb);
1032
1033           if (diff)
1034             return key->reverse ? -diff : diff;
1035           continue;
1036         }
1037       else if (key->month)
1038         {
1039           diff = getmonth (texta, lena) - getmonth (textb, lenb);
1040           if (diff)
1041             return key->reverse ? -diff : diff;
1042           continue;
1043         }
1044       else if (ignore && translate)
1045
1046 #define CMP_WITH_IGNORE(A, B)                                           \
1047   do                                                                    \
1048     {                                                                   \
1049           while (texta < lima && textb < limb)                          \
1050             {                                                           \
1051               while (texta < lima && ignore[UCHAR (*texta)])            \
1052                 ++texta;                                                \
1053               while (textb < limb && ignore[UCHAR (*textb)])            \
1054                 ++textb;                                                \
1055               if (texta < lima && textb < limb)                         \
1056                 {                                                       \
1057                   if ((A) != (B))                                       \
1058                     {                                                   \
1059                       diff = (A) - (B);                                 \
1060                       break;                                            \
1061                     }                                                   \
1062                   ++texta;                                              \
1063                   ++textb;                                              \
1064                 }                                                       \
1065                                                                         \
1066               if (texta == lima && textb < limb && !ignore[UCHAR (*textb)]) \
1067                 diff = -1;                                              \
1068               else if (texta < lima && textb == limb                    \
1069                        && !ignore[UCHAR (*texta)])                      \
1070                 diff = 1;                                               \
1071             }                                                           \
1072                                                                         \
1073           if (diff == 0)                                                \
1074             {                                                           \
1075               while (texta < lima && ignore[UCHAR (*texta)])            \
1076                 ++texta;                                                \
1077               while (textb < limb && ignore[UCHAR (*textb)])            \
1078                 ++textb;                                                \
1079                                                                         \
1080               if (texta == lima && textb < limb)                        \
1081                 diff = -1;                                              \
1082               else if (texta < lima && textb == limb)                   \
1083                 diff = 1;                                               \
1084             }                                                           \
1085           /* Relative lengths are meaningless if characters were ignored.  \
1086              Handling this case here avoids what might be an invalid length  \
1087              comparison below.  */                                      \
1088           if (diff == 0 && texta == lima && textb == limb)              \
1089             return 0;                                                   \
1090     }                                                                   \
1091   while (0)
1092
1093         CMP_WITH_IGNORE (translate[UCHAR (*texta)], translate[UCHAR (*textb)]);
1094       else if (ignore)
1095         CMP_WITH_IGNORE (*texta, *textb);
1096       else if (translate)
1097         while (texta < lima && textb < limb)
1098           {
1099             if (translate[UCHAR (*texta++)] != translate[UCHAR (*textb++)])
1100               {
1101                 diff = (translate[UCHAR (*--texta)]
1102                         - translate[UCHAR (*--textb)]);
1103                 break;
1104               }
1105           }
1106       else
1107         diff = memcmp (texta, textb, min (lena, lenb));
1108
1109       if (diff)
1110         return key->reverse ? -diff : diff;
1111       if ((diff = lena - lenb) != 0)
1112         return key->reverse ? -diff : diff;
1113     }
1114
1115   return 0;
1116 }
1117
1118 /* Compare two lines A and B, returning negative, zero, or positive
1119    depending on whether A compares less than, equal to, or greater than B. */
1120
1121 static int
1122 compare (register const struct line *a, register const struct line *b)
1123 {
1124   int diff, tmpa, tmpb, mini;
1125
1126   /* First try to compare on the specified keys (if any).
1127      The only two cases with no key at all are unadorned sort,
1128      and unadorned sort -r. */
1129   if (keyhead.next)
1130     {
1131       diff = keycompare (a, b);
1132       if (diff != 0)
1133         return diff;
1134       if (unique || stable)
1135         return 0;
1136     }
1137
1138   /* If the keys all compare equal (or no keys were specified)
1139      fall through to the default byte-by-byte comparison. */
1140   tmpa = a->length, tmpb = b->length;
1141   mini = min (tmpa, tmpb);
1142   if (mini == 0)
1143     diff = tmpa - tmpb;
1144   else
1145     {
1146       char *ap = a->text, *bp = b->text;
1147
1148       diff = UCHAR (*ap) - UCHAR (*bp);
1149       if (diff == 0)
1150         {
1151           diff = memcmp (ap, bp, mini);
1152           if (diff == 0)
1153             diff = tmpa - tmpb;
1154         }
1155     }
1156
1157   return reverse ? -diff : diff;
1158 }
1159
1160 /* Check that the lines read from the given FP come in order.  Return
1161    1 if they do and 0 if there is a disorder.
1162    FIXME: return number of first out-of-order line if not sorted.  */
1163
1164 static int
1165 checkfp (FILE *fp)
1166 {
1167   struct buffer buf;            /* Input buffer. */
1168   struct lines lines;           /* Lines scanned from the buffer. */
1169   struct line temp;             /* Copy of previous line. */
1170   int cc;                       /* Character count. */
1171   int alloc, sorted = 1;
1172
1173   initbuf (&buf, mergealloc);
1174   initlines (&lines, mergealloc / linelength + 1,
1175              LINEALLOC / ((NMERGE + NMERGE) * sizeof (struct line)));
1176   alloc = linelength;
1177   temp.text = xmalloc (alloc);
1178
1179   cc = fillbuf (&buf, fp);
1180   if (cc == 0)
1181     goto finish;
1182
1183   findlines (&buf, &lines);
1184
1185   while (1)
1186     {
1187       struct line *prev_line;   /* Pointer to previous line. */
1188       int cmp;                  /* Result of calling compare. */
1189       int i;
1190
1191       /* Compare each line in the buffer with its successor. */
1192       for (i = 0; i < lines.used - 1; ++i)
1193         {
1194           cmp = compare (&lines.lines[i], &lines.lines[i + 1]);
1195           if ((unique && cmp >= 0) || (cmp > 0))
1196             {
1197               sorted = 0;
1198               goto finish;
1199             }
1200         }
1201
1202       /* Save the last line of the buffer and refill the buffer. */
1203       prev_line = lines.lines + (lines.used - 1);
1204       if (prev_line->length > alloc)
1205         {
1206           while (prev_line->length + 1 > alloc)
1207             alloc *= 2;
1208           temp.text = xrealloc (temp.text, alloc);
1209         }
1210       memcpy (temp.text, prev_line->text, prev_line->length + 1);
1211       temp.length = prev_line->length;
1212       temp.keybeg = temp.text + (prev_line->keybeg - prev_line->text);
1213       temp.keylim = temp.text + (prev_line->keylim - prev_line->text);
1214
1215       cc = fillbuf (&buf, fp);
1216       if (cc == 0)
1217         break;
1218
1219       findlines (&buf, &lines);
1220       /* Make sure the line saved from the old buffer contents is
1221          less than or equal to the first line of the new buffer. */
1222       cmp = compare (&temp, &lines.lines[0]);
1223       if ((unique && cmp >= 0) || (cmp > 0))
1224         {
1225           sorted = 0;
1226           break;
1227         }
1228     }
1229
1230 finish:
1231   xfclose (fp);
1232   free (buf.buf);
1233   free ((char *) lines.lines);
1234   free (temp.text);
1235   return sorted;
1236 }
1237
1238 /* Merge lines from FPS onto OFP.  NFPS cannot be greater than NMERGE.
1239    Close FPS before returning. */
1240
1241 static void
1242 mergefps (FILE **fps, register int nfps, FILE *ofp)
1243 {
1244   struct buffer buffer[NMERGE]; /* Input buffers for each file. */
1245   struct lines lines[NMERGE];   /* Line tables for each buffer. */
1246   struct line saved;            /* Saved line for unique check. */
1247   int savedflag = 0;            /* True if there is a saved line. */
1248   int savealloc;                /* Size allocated for the saved line. */
1249   int cur[NMERGE];              /* Current line in each line table. */
1250   int ord[NMERGE];              /* Table representing a permutation of fps,
1251                                    such that lines[ord[0]].lines[cur[ord[0]]]
1252                                    is the smallest line and will be next
1253                                    output. */
1254   register int i, j, t;
1255
1256 #ifdef lint  /* Suppress `used before initialized' warning.  */
1257   savealloc = 0;
1258 #endif
1259
1260   /* Allocate space for a saved line if necessary. */
1261   if (unique)
1262     {
1263       savealloc = linelength;
1264       saved.text = xmalloc (savealloc);
1265     }
1266
1267   /* Read initial lines from each input file. */
1268   for (i = 0; i < nfps; ++i)
1269     {
1270       initbuf (&buffer[i], mergealloc);
1271       /* If a file is empty, eliminate it from future consideration. */
1272       while (i < nfps && !fillbuf (&buffer[i], fps[i]))
1273         {
1274           xfclose (fps[i]);
1275           --nfps;
1276           for (j = i; j < nfps; ++j)
1277             fps[j] = fps[j + 1];
1278         }
1279       if (i == nfps)
1280         free (buffer[i].buf);
1281       else
1282         {
1283           initlines (&lines[i], mergealloc / linelength + 1,
1284                      LINEALLOC / ((NMERGE + NMERGE) * sizeof (struct line)));
1285           findlines (&buffer[i], &lines[i]);
1286           cur[i] = 0;
1287         }
1288     }
1289
1290   /* Set up the ord table according to comparisons among input lines.
1291      Since this only reorders two items if one is strictly greater than
1292      the other, it is stable. */
1293   for (i = 0; i < nfps; ++i)
1294     ord[i] = i;
1295   for (i = 1; i < nfps; ++i)
1296     if (compare (&lines[ord[i - 1]].lines[cur[ord[i - 1]]],
1297                  &lines[ord[i]].lines[cur[ord[i]]]) > 0)
1298       t = ord[i - 1], ord[i - 1] = ord[i], ord[i] = t, i = 0;
1299
1300   /* Repeatedly output the smallest line until no input remains. */
1301   while (nfps)
1302     {
1303       /* If uniqified output is turned on, output only the first of
1304          an identical series of lines. */
1305       if (unique)
1306         {
1307           if (savedflag && compare (&saved, &lines[ord[0]].lines[cur[ord[0]]]))
1308             {
1309               write_bytes (saved.text, saved.length, ofp);
1310               putc (eolchar, ofp);
1311               savedflag = 0;
1312             }
1313           if (!savedflag)
1314             {
1315               if (savealloc < lines[ord[0]].lines[cur[ord[0]]].length + 1)
1316                 {
1317                   while (savealloc < lines[ord[0]].lines[cur[ord[0]]].length + 1)
1318                     savealloc *= 2;
1319                   saved.text = xrealloc (saved.text, savealloc);
1320                 }
1321               saved.length = lines[ord[0]].lines[cur[ord[0]]].length;
1322               memcpy (saved.text, lines[ord[0]].lines[cur[ord[0]]].text,
1323                      saved.length + 1);
1324               if (lines[ord[0]].lines[cur[ord[0]]].keybeg != NULL)
1325                 {
1326                   saved.keybeg = saved.text +
1327                     (lines[ord[0]].lines[cur[ord[0]]].keybeg
1328                      - lines[ord[0]].lines[cur[ord[0]]].text);
1329                 }
1330               if (lines[ord[0]].lines[cur[ord[0]]].keylim != NULL)
1331                 {
1332                   saved.keylim = saved.text +
1333                     (lines[ord[0]].lines[cur[ord[0]]].keylim
1334                      - lines[ord[0]].lines[cur[ord[0]]].text);
1335                 }
1336               savedflag = 1;
1337             }
1338         }
1339       else
1340         {
1341           write_bytes (lines[ord[0]].lines[cur[ord[0]]].text,
1342                        lines[ord[0]].lines[cur[ord[0]]].length, ofp);
1343           putc (eolchar, ofp);
1344         }
1345
1346       /* Check if we need to read more lines into core. */
1347       if (++cur[ord[0]] == lines[ord[0]].used)
1348         if (fillbuf (&buffer[ord[0]], fps[ord[0]]))
1349           {
1350             findlines (&buffer[ord[0]], &lines[ord[0]]);
1351             cur[ord[0]] = 0;
1352           }
1353         else
1354           {
1355             /* We reached EOF on fps[ord[0]]. */
1356             for (i = 1; i < nfps; ++i)
1357               if (ord[i] > ord[0])
1358                 --ord[i];
1359             --nfps;
1360             xfclose (fps[ord[0]]);
1361             free (buffer[ord[0]].buf);
1362             free ((char *) lines[ord[0]].lines);
1363             for (i = ord[0]; i < nfps; ++i)
1364               {
1365                 fps[i] = fps[i + 1];
1366                 buffer[i] = buffer[i + 1];
1367                 lines[i] = lines[i + 1];
1368                 cur[i] = cur[i + 1];
1369               }
1370             for (i = 0; i < nfps; ++i)
1371               ord[i] = ord[i + 1];
1372             continue;
1373           }
1374
1375       /* The new line just read in may be larger than other lines
1376          already in core; push it back in the queue until we encounter
1377          a line larger than it. */
1378       for (i = 1; i < nfps; ++i)
1379         {
1380           t = compare (&lines[ord[0]].lines[cur[ord[0]]],
1381                        &lines[ord[i]].lines[cur[ord[i]]]);
1382           if (!t)
1383             t = ord[0] - ord[i];
1384           if (t < 0)
1385             break;
1386         }
1387       t = ord[0];
1388       for (j = 1; j < i; ++j)
1389         ord[j - 1] = ord[j];
1390       ord[i - 1] = t;
1391     }
1392
1393   if (unique && savedflag)
1394     {
1395       write_bytes (saved.text, saved.length, ofp);
1396       putc (eolchar, ofp);
1397       free (saved.text);
1398     }
1399 }
1400
1401 /* Sort the array LINES with NLINES members, using TEMP for temporary space. */
1402
1403 static void
1404 sortlines (struct line *lines, int nlines, struct line *temp)
1405 {
1406   register struct line *lo, *hi, *t;
1407   register int nlo, nhi;
1408
1409   if (nlines == 2)
1410     {
1411       if (compare (&lines[0], &lines[1]) > 0)
1412         *temp = lines[0], lines[0] = lines[1], lines[1] = *temp;
1413       return;
1414     }
1415
1416   nlo = nlines / 2;
1417   lo = lines;
1418   nhi = nlines - nlo;
1419   hi = lines + nlo;
1420
1421   if (nlo > 1)
1422     sortlines (lo, nlo, temp);
1423
1424   if (nhi > 1)
1425     sortlines (hi, nhi, temp);
1426
1427   t = temp;
1428
1429   while (nlo && nhi)
1430     if (compare (lo, hi) <= 0)
1431       *t++ = *lo++, --nlo;
1432     else
1433       *t++ = *hi++, --nhi;
1434   while (nlo--)
1435     *t++ = *lo++;
1436
1437   for (lo = lines, nlo = nlines - nhi, t = temp; nlo; --nlo)
1438     *lo++ = *t++;
1439 }
1440
1441 /* Check that each of the NFILES FILES is ordered.
1442    Return a count of disordered files. */
1443
1444 static int
1445 check (char **files, int nfiles)
1446 {
1447   int i, disorders = 0;
1448   FILE *fp;
1449
1450   for (i = 0; i < nfiles; ++i)
1451     {
1452       fp = xfopen (files[i], "r");
1453       if (!checkfp (fp))
1454         {
1455           fprintf (stderr, _("%s: disorder on %s\n"), program_name, files[i]);
1456           ++disorders;
1457         }
1458     }
1459   return disorders;
1460 }
1461
1462 /* Merge NFILES FILES onto OFP. */
1463
1464 static void
1465 merge (char **files, int nfiles, FILE *ofp)
1466 {
1467   int i, j, t;
1468   char *temp;
1469   FILE *fps[NMERGE], *tfp;
1470
1471   while (nfiles > NMERGE)
1472     {
1473       t = 0;
1474       for (i = 0; i < nfiles / NMERGE; ++i)
1475         {
1476           for (j = 0; j < NMERGE; ++j)
1477             fps[j] = xfopen (files[i * NMERGE + j], "r");
1478           tfp = xtmpfopen (temp = tempname ());
1479           mergefps (fps, NMERGE, tfp);
1480           xfclose (tfp);
1481           for (j = 0; j < NMERGE; ++j)
1482             zaptemp (files[i * NMERGE + j]);
1483           files[t++] = temp;
1484         }
1485       for (j = 0; j < nfiles % NMERGE; ++j)
1486         fps[j] = xfopen (files[i * NMERGE + j], "r");
1487       tfp = xtmpfopen (temp = tempname ());
1488       mergefps (fps, nfiles % NMERGE, tfp);
1489       xfclose (tfp);
1490       for (j = 0; j < nfiles % NMERGE; ++j)
1491         zaptemp (files[i * NMERGE + j]);
1492       files[t++] = temp;
1493       nfiles = t;
1494     }
1495
1496   for (i = 0; i < nfiles; ++i)
1497     fps[i] = xfopen (files[i], "r");
1498   mergefps (fps, i, ofp);
1499   for (i = 0; i < nfiles; ++i)
1500     zaptemp (files[i]);
1501 }
1502
1503 /* Sort NFILES FILES onto OFP. */
1504
1505 static void
1506 sort (char **files, int nfiles, FILE *ofp)
1507 {
1508   struct buffer buf;
1509   struct lines lines;
1510   struct line *tmp;
1511   int i, ntmp;
1512   FILE *fp, *tfp;
1513   struct tempnode *node;
1514   int n_temp_files = 0;
1515   char **tempfiles;
1516
1517   initbuf (&buf, sortalloc);
1518   initlines (&lines, sortalloc / linelength + 1,
1519              LINEALLOC / sizeof (struct line));
1520   ntmp = lines.alloc;
1521   tmp = (struct line *) xmalloc (ntmp * sizeof (struct line));
1522
1523   while (nfiles--)
1524     {
1525       fp = xfopen (*files++, "r");
1526       while (fillbuf (&buf, fp))
1527         {
1528           findlines (&buf, &lines);
1529           if (lines.used > ntmp)
1530             {
1531               while (lines.used > ntmp)
1532                 ntmp *= 2;
1533               tmp = (struct line *)
1534                 xrealloc ((char *) tmp, ntmp * sizeof (struct line));
1535             }
1536           sortlines (lines.lines, lines.used, tmp);
1537           if (feof (fp) && !nfiles && !n_temp_files && !buf.left)
1538             tfp = ofp;
1539           else
1540             {
1541               ++n_temp_files;
1542               tfp = xtmpfopen (tempname ());
1543             }
1544           for (i = 0; i < lines.used; ++i)
1545             if (!unique || i == 0
1546                 || compare (&lines.lines[i], &lines.lines[i - 1]))
1547               {
1548                 write_bytes (lines.lines[i].text, lines.lines[i].length, tfp);
1549                 putc (eolchar, tfp);
1550               }
1551           if (tfp != ofp)
1552             xfclose (tfp);
1553         }
1554       xfclose (fp);
1555     }
1556
1557   free (buf.buf);
1558   free ((char *) lines.lines);
1559   free ((char *) tmp);
1560
1561   if (n_temp_files)
1562     {
1563       tempfiles = (char **) xmalloc (n_temp_files * sizeof (char *));
1564       i = n_temp_files;
1565       for (node = temphead.next; i > 0; node = node->next)
1566         tempfiles[--i] = node->name;
1567       merge (tempfiles, n_temp_files, ofp);
1568       free ((char *) tempfiles);
1569     }
1570 }
1571
1572 /* Insert key KEY at the end of the list (`keyhead'). */
1573
1574 static void
1575 insertkey (struct keyfield *key)
1576 {
1577   struct keyfield *k = &keyhead;
1578
1579   while (k->next)
1580     k = k->next;
1581   k->next = key;
1582   key->next = NULL;
1583 }
1584
1585 static void
1586 badfieldspec (const char *s)
1587 {
1588   error (2, 0, _("invalid field specification `%s'"), s);
1589 }
1590
1591 /* Handle interrupts and hangups. */
1592
1593 static void
1594 sighandler (int sig)
1595 {
1596 #ifdef SA_INTERRUPT
1597   struct sigaction sigact;
1598
1599   sigact.sa_handler = SIG_DFL;
1600   sigemptyset (&sigact.sa_mask);
1601   sigact.sa_flags = 0;
1602   sigaction (sig, &sigact, NULL);
1603 #else                           /* !SA_INTERRUPT */
1604   signal (sig, SIG_DFL);
1605 #endif                          /* SA_INTERRUPT */
1606   cleanup ();
1607   kill (getpid (), sig);
1608 }
1609
1610 /* Set the ordering options for KEY specified in S.
1611    Return the address of the first character in S that
1612    is not a valid ordering option.
1613    BLANKTYPE is the kind of blanks that 'b' should skip. */
1614
1615 static char *
1616 set_ordering (register const char *s, struct keyfield *key,
1617               enum blanktype blanktype)
1618 {
1619   while (*s)
1620     {
1621       switch (*s)
1622         {
1623         case 'b':
1624           if (blanktype == bl_start || blanktype == bl_both)
1625             key->skipsblanks = 1;
1626           if (blanktype == bl_end || blanktype == bl_both)
1627             key->skipeblanks = 1;
1628           break;
1629         case 'd':
1630           key->ignore = nondictionary;
1631           break;
1632         case 'f':
1633           key->translate = fold_toupper;
1634           break;
1635         case 'g':
1636           key->general_numeric = 1;
1637           break;
1638         case 'i':
1639           key->ignore = nonprinting;
1640           break;
1641         case 'M':
1642           key->month = 1;
1643           break;
1644         case 'n':
1645           key->numeric = 1;
1646           if (blanktype == bl_start || blanktype == bl_both)
1647             key->skipsblanks = 1;
1648           if (blanktype == bl_end || blanktype == bl_both)
1649             key->skipeblanks = 1;
1650           break;
1651         case 'r':
1652           key->reverse = 1;
1653           break;
1654         default:
1655           return (char *) s;
1656         }
1657       ++s;
1658     }
1659   return (char *) s;
1660 }
1661
1662 void
1663 main (int argc, char **argv)
1664 {
1665   struct keyfield *key = NULL, gkey;
1666   char *s;
1667   int i, t, t2;
1668   int checkonly = 0, mergeonly = 0, nfiles = 0;
1669   char *minus = "-", *outfile = minus, **files, *tmp;
1670   FILE *ofp;
1671 #ifdef SA_INTERRUPT
1672   struct sigaction oldact, newact;
1673 #endif                          /* SA_INTERRUPT */
1674
1675   program_name = argv[0];
1676   setlocale (LC_ALL, "");
1677   bindtextdomain (PACKAGE, LOCALEDIR);
1678   textdomain (PACKAGE);
1679
1680   parse_long_options (argc, argv, "sort", PACKAGE_VERSION, usage);
1681
1682   have_read_stdin = 0;
1683   inittables ();
1684
1685   temp_file_prefix = getenv ("TMPDIR");
1686   if (temp_file_prefix == NULL)
1687     temp_file_prefix = DEFAULT_TMPDIR;
1688
1689 #ifdef SA_INTERRUPT
1690   newact.sa_handler = sighandler;
1691   sigemptyset (&newact.sa_mask);
1692   newact.sa_flags = 0;
1693
1694   sigaction (SIGINT, NULL, &oldact);
1695   if (oldact.sa_handler != SIG_IGN)
1696     sigaction (SIGINT, &newact, NULL);
1697   sigaction (SIGHUP, NULL, &oldact);
1698   if (oldact.sa_handler != SIG_IGN)
1699     sigaction (SIGHUP, &newact, NULL);
1700   sigaction (SIGPIPE, NULL, &oldact);
1701   if (oldact.sa_handler != SIG_IGN)
1702     sigaction (SIGPIPE, &newact, NULL);
1703   sigaction (SIGTERM, NULL, &oldact);
1704   if (oldact.sa_handler != SIG_IGN)
1705     sigaction (SIGTERM, &newact, NULL);
1706 #else                           /* !SA_INTERRUPT */
1707   if (signal (SIGINT, SIG_IGN) != SIG_IGN)
1708     signal (SIGINT, sighandler);
1709   if (signal (SIGHUP, SIG_IGN) != SIG_IGN)
1710     signal (SIGHUP, sighandler);
1711   if (signal (SIGPIPE, SIG_IGN) != SIG_IGN)
1712     signal (SIGPIPE, sighandler);
1713   if (signal (SIGTERM, SIG_IGN) != SIG_IGN)
1714     signal (SIGTERM, sighandler);
1715 #endif                          /* !SA_INTERRUPT */
1716
1717   gkey.sword = gkey.eword = -1;
1718   gkey.ignore = NULL;
1719   gkey.translate = NULL;
1720   gkey.numeric =  gkey.general_numeric = gkey.month = gkey.reverse = 0;
1721   gkey.skipsblanks = gkey.skipeblanks = 0;
1722
1723   files = (char **) xmalloc (sizeof (char *) * argc);
1724
1725   for (i = 1; i < argc; ++i)
1726     {
1727       if (argv[i][0] == '+')
1728         {
1729           if (key)
1730             insertkey (key);
1731           key = (struct keyfield *) xmalloc (sizeof (struct keyfield));
1732           key->eword = -1;
1733           key->ignore = NULL;
1734           key->translate = NULL;
1735           key->skipsblanks = key->skipeblanks = 0;
1736           key->numeric = key->general_numeric = key->month = key->reverse = 0;
1737           s = argv[i] + 1;
1738           if (! (digits[UCHAR (*s)] || (*s == '.' && digits[UCHAR (s[1])])))
1739             badfieldspec (argv[i]);
1740           for (t = 0; digits[UCHAR (*s)]; ++s)
1741             t = 10 * t + *s - '0';
1742           t2 = 0;
1743           if (*s == '.')
1744             for (++s; digits[UCHAR (*s)]; ++s)
1745               t2 = 10 * t2 + *s - '0';
1746           if (t2 || t)
1747             {
1748               key->sword = t;
1749               key->schar = t2;
1750             }
1751           else
1752             key->sword = -1;
1753           s = set_ordering (s, key, bl_start);
1754           if (*s)
1755             badfieldspec (argv[i]);
1756         }
1757       else if (argv[i][0] == '-' && argv[i][1])
1758         {
1759           s = argv[i] + 1;
1760           if (digits[UCHAR (*s)] || (*s == '.' && digits[UCHAR (s[1])]))
1761             {
1762               if (!key)
1763                 usage (2);
1764               for (t = 0; digits[UCHAR (*s)]; ++s)
1765                 t = t * 10 + *s - '0';
1766               t2 = 0;
1767               if (*s == '.')
1768                 for (++s; digits[UCHAR (*s)]; ++s)
1769                   t2 = t2 * 10 + *s - '0';
1770               key->eword = t;
1771               key->echar = t2;
1772               s = set_ordering (s, key, bl_end);
1773               if (*s)
1774                 badfieldspec (argv[i]);
1775               insertkey (key);
1776               key = NULL;
1777             }
1778           else
1779             while (*s)
1780               {
1781                 s = set_ordering (s, &gkey, bl_both);
1782                 switch (*s)
1783                   {
1784                   case '\0':
1785                     break;
1786                   case 'c':
1787                     checkonly = 1;
1788                     break;
1789                   case 'k':
1790                     if (s[1])
1791                       ++s;
1792                     else
1793                       {
1794                         if (i == argc - 1)
1795                           error (2, 0, _("option `-k' requires an argument"));
1796                         else
1797                           s = argv[++i];
1798                       }
1799                     if (key)
1800                       insertkey (key);
1801                     key = (struct keyfield *)
1802                       xmalloc (sizeof (struct keyfield));
1803                     key->eword = -1;
1804                     key->ignore = NULL;
1805                     key->translate = NULL;
1806                     key->skipsblanks = key->skipeblanks = 0;
1807                     key->numeric = key->month = key->reverse = 0;
1808                     /* Get POS1. */
1809                     if (!digits[UCHAR (*s)])
1810                       badfieldspec (argv[i]);
1811                     for (t = 0; digits[UCHAR (*s)]; ++s)
1812                       t = 10 * t + *s - '0';
1813                     if (t == 0)
1814                       {
1815                         /* Provoke with `sort -k0' */
1816                         error (0, 0, _("the starting field number argument \
1817 to the `-k' option must be positive"));
1818                         badfieldspec (argv[i]);
1819                       }
1820                     --t;
1821                     t2 = 0;
1822                     if (*s == '.')
1823                       {
1824                         if (!digits[UCHAR (s[1])])
1825                           {
1826                             /* Provoke with `sort -k1.' */
1827                             error (0, 0, _("starting field spec has `.' but \
1828 lacks following character offset"));
1829                             badfieldspec (argv[i]);
1830                           }
1831                         for (++s; digits[UCHAR (*s)]; ++s)
1832                           t2 = 10 * t2 + *s - '0';
1833                         if (t2 == 0)
1834                           {
1835                             /* Provoke with `sort -k1.0' */
1836                             error (0, 0, _("starting field character offset \
1837 argument to the `-k' option\nmust be positive"));
1838                             badfieldspec (argv[i]);
1839                           }
1840                         --t2;
1841                       }
1842                     if (t2 || t)
1843                       {
1844                         key->sword = t;
1845                         key->schar = t2;
1846                       }
1847                     else
1848                       key->sword = -1;
1849                     s = set_ordering (s, key, bl_start);
1850                     if (*s == 0)
1851                       {
1852                         key->eword = -1;
1853                         key->echar = 0;
1854                       }
1855                     else if (*s != ',')
1856                       badfieldspec (argv[i]);
1857                     else if (*s == ',')
1858                       {
1859                         /* Skip over comma.  */
1860                         ++s;
1861                         if (*s == 0)
1862                           {
1863                             /* Provoke with `sort -k1,' */
1864                             error (0, 0, _("field specification has `,' but \
1865 lacks following field spec"));
1866                             badfieldspec (argv[i]);
1867                           }
1868                         /* Get POS2. */
1869                         for (t = 0; digits[UCHAR (*s)]; ++s)
1870                           t = t * 10 + *s - '0';
1871                         if (t == 0)
1872                           {
1873                             /* Provoke with `sort -k1,0' */
1874                             error (0, 0, _("ending field number argument \
1875 to the `-k' option must be positive"));
1876                             badfieldspec (argv[i]);
1877                           }
1878                         --t;
1879                         t2 = 0;
1880                         if (*s == '.')
1881                           {
1882                             if (!digits[UCHAR (s[1])])
1883                               {
1884                                 /* Provoke with `sort -k1,1.' */
1885                                 error (0, 0, _("ending field spec has `.' \
1886 but lacks following character offset"));
1887                                 badfieldspec (argv[i]);
1888                               }
1889                             for (++s; digits[UCHAR (*s)]; ++s)
1890                               t2 = t2 * 10 + *s - '0';
1891                           }
1892                         else
1893                           {
1894                             /* `-k 2,3' is equivalent to `+1 -3'.  */
1895                             ++t;
1896                           }
1897                         key->eword = t;
1898                         key->echar = t2;
1899                         s = set_ordering (s, key, bl_end);
1900                         if (*s)
1901                           badfieldspec (argv[i]);
1902                       }
1903                     insertkey (key);
1904                     key = NULL;
1905                     goto outer;
1906                   case 'm':
1907                     mergeonly = 1;
1908                     break;
1909                   case 'o':
1910                     if (s[1])
1911                       outfile = s + 1;
1912                     else
1913                       {
1914                         if (i == argc - 1)
1915                           error (2, 0, _("option `-o' requires an argument"));
1916                         else
1917                           outfile = argv[++i];
1918                       }
1919                     goto outer;
1920                   case 's':
1921                     stable = 1;
1922                     break;
1923                   case 't':
1924                     if (s[1])
1925                       tab = *++s;
1926                     else if (i < argc - 1)
1927                       {
1928                         tab = *argv[++i];
1929                         goto outer;
1930                       }
1931                     else
1932                       error (2, 0, _("option `-t' requires an argument"));
1933                     break;
1934                   case 'T':
1935                     if (s[1])
1936                       temp_file_prefix = ++s;
1937                     else
1938                       {
1939                         if (i < argc - 1)
1940                           temp_file_prefix = argv[++i];
1941                         else
1942                           error (2, 0, _("option `-T' requires an argument"));
1943                       }
1944                     goto outer;
1945                     /* break; */
1946                   case 'u':
1947                     unique = 1;
1948                     break;
1949                   case 'z':
1950                     eolchar = 0;
1951                     break;
1952                   case 'y':
1953                     /* Accept and ignore e.g. -y0 for compatibility with
1954                        Solaris 2.  */
1955                     goto outer;
1956                   default:
1957                     fprintf (stderr, _("%s: unrecognized option `-%c'\n"),
1958                              argv[0], *s);
1959                     usage (2);
1960                   }
1961                 if (*s)
1962                   ++s;
1963               }
1964         }
1965       else                      /* Not an option. */
1966         {
1967           files[nfiles++] = argv[i];
1968         }
1969     outer:;
1970     }
1971
1972   if (key)
1973     insertkey (key);
1974
1975   /* Inheritance of global options to individual keys. */
1976   for (key = keyhead.next; key; key = key->next)
1977     if (!key->ignore && !key->translate && !key->skipsblanks && !key->reverse
1978         && !key->skipeblanks && !key->month && !key->numeric
1979         && !key->general_numeric)
1980       {
1981         key->ignore = gkey.ignore;
1982         key->translate = gkey.translate;
1983         key->skipsblanks = gkey.skipsblanks;
1984         key->skipeblanks = gkey.skipeblanks;
1985         key->month = gkey.month;
1986         key->numeric = gkey.numeric;
1987         key->general_numeric = gkey.general_numeric;
1988         key->reverse = gkey.reverse;
1989       }
1990
1991   if (!keyhead.next && (gkey.ignore || gkey.translate || gkey.skipsblanks
1992                         || gkey.skipeblanks || gkey.month || gkey.numeric
1993                         || gkey.general_numeric))
1994     insertkey (&gkey);
1995   reverse = gkey.reverse;
1996
1997   if (nfiles == 0)
1998     {
1999       nfiles = 1;
2000       files = &minus;
2001     }
2002
2003   if (checkonly)
2004     exit (check (files, nfiles) != 0);
2005
2006   if (strcmp (outfile, "-"))
2007     {
2008       struct stat outstat;
2009       if (stat (outfile, &outstat) == 0)
2010         {
2011           /* The following code prevents a race condition when
2012              people use the brain dead shell programming idiom:
2013                   cat file | sort -o file
2014              This feature is provided for historical compatibility,
2015              but we strongly discourage ever relying on this in
2016              new shell programs. */
2017
2018           /* Temporarily copy each input file that might be another name
2019              for the output file.  When in doubt (e.g. a pipe), copy.  */
2020           for (i = 0; i < nfiles; ++i)
2021             {
2022               char buf[8192];
2023               FILE *fp;
2024               int cc;
2025
2026               if (S_ISREG (outstat.st_mode) && strcmp (outfile, files[i]))
2027                 {
2028                   struct stat instat;
2029                   if ((strcmp (files[i], "-")
2030                        ? stat (files[i], &instat)
2031                        : fstat (fileno (stdin), &instat)) != 0)
2032                     {
2033                       error (0, errno, "%s", files[i]);
2034                       cleanup ();
2035                       exit (2);
2036                     }
2037                   if (S_ISREG (instat.st_mode)
2038                       && (instat.st_ino != outstat.st_ino
2039                           || instat.st_dev != outstat.st_dev))
2040                     {
2041                       /* We know the files are distinct.  */
2042                       continue;
2043                     }
2044                 }
2045
2046               fp = xfopen (files[i], "r");
2047               tmp = tempname ();
2048               ofp = xtmpfopen (tmp);
2049               while ((cc = fread (buf, 1, sizeof buf, fp)) > 0)
2050                 write_bytes (buf, cc, ofp);
2051               if (ferror (fp))
2052                 {
2053                   error (0, errno, "%s", files[i]);
2054                   cleanup ();
2055                   exit (2);
2056                 }
2057               xfclose (ofp);
2058               xfclose (fp);
2059               files[i] = tmp;
2060             }
2061         }
2062       ofp = xfopen (outfile, "w");
2063     }
2064   else
2065     ofp = stdout;
2066
2067   if (mergeonly)
2068     merge (files, nfiles, ofp);
2069   else
2070     sort (files, nfiles, ofp);
2071   cleanup ();
2072
2073   /* If we wait for the implicit flush on exit, and the parent process
2074      has closed stdout (e.g., exec >&- in a shell), then the output file
2075      winds up empty.  I don't understand why.  This is under SunOS,
2076      Solaris, Ultrix, and Irix.  This premature fflush makes the output
2077      reappear. --karl@cs.umb.edu  */
2078   if (fflush (ofp) < 0)
2079     error (1, errno, _("%s: write error"), outfile);
2080
2081   if (have_read_stdin && fclose (stdin) == EOF)
2082     error (1, errno, outfile);
2083   if (ferror (stdout) || fclose (stdout) == EOF)
2084     error (1, errno, _("%s: write error"), outfile);
2085
2086   exit (0);
2087 }