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