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