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