src/sort.c

   1 /* sort - sort lines of text (with all kinds of options).
   2    Copyright (C) 1988, 1991-2005 Free Software Foundation, Inc.
   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 Foundation,
  16    Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 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    Ørn E. Hansen added NLS support in 1997.  */
  23
  24 #include <config.h>
  25
  26 #include <getopt.h>
  27 #include <sys/types.h>
  28 #include <signal.h>
  29 #include <stdio.h>
  30 #include "system.h"
  31 #include "error.h"
  32 #include "hard-locale.h"
  33 #include "inttostr.h"
  34 #include "physmem.h"
  35 #include "posixver.h"
  36 #include "quote.h"
  37 #include "stdlib--.h"
  38 #include "stdio--.h"
  39 #include "strnumcmp.h"
  40 #include "xmemcoll.h"
  41 #include "xstrtol.h"
  42
  43 #if HAVE_SYS_RESOURCE_H
  44 # include <sys/resource.h>
  45 #endif
  46 #ifndef RLIMIT_DATA
  47 struct rlimit { size_t rlim_cur; };
  48 # define getrlimit(Resource, Rlp) (-1)
  49 #endif
  50
  51 /* The official name of this program (e.g., no `g' prefix).  */
  52 #define PROGRAM_NAME "sort"
  53
  54 #define AUTHORS "Mike Haertel", "Paul Eggert"
  55
  56 #if HAVE_LANGINFO_CODESET
  57 # include <langinfo.h>
  58 #endif
  59
  60 /* Use SA_NOCLDSTOP as a proxy for whether the sigaction machinery is
  61    present.  */
  62 #ifndef SA_NOCLDSTOP
  63 # define SA_NOCLDSTOP 0
  64 # define sigprocmask(How, Set, Oset) /* empty */
  65 # define sigset_t int
  66 # if ! HAVE_SIGINTERRUPT
  67 #  define siginterrupt(sig, flag) /* empty */
  68 # endif
  69 #endif
  70
  71 #ifndef STDC_HEADERS
  72 double strtod ();
  73 #endif
  74
  75 #define UCHAR_LIM (UCHAR_MAX + 1)
  76
  77 #ifndef DEFAULT_TMPDIR
  78 # define DEFAULT_TMPDIR "/tmp"
  79 #endif
  80
  81 /* Exit statuses.  */
  82 enum
  83   {
  84     /* POSIX says to exit with status 1 if invoked with -c and the
  85        input is not properly sorted.  */
  86     SORT_OUT_OF_ORDER = 1,
  87
  88     /* POSIX says any other irregular exit must exit with a status
  89        code greater than 1.  */
  90     SORT_FAILURE = 2
  91   };
  92
  93 /* The representation of the decimal point in the current locale.  */
  94 static int decimal_point;
  95
  96 /* Thousands separator; if -1, then there isn't one.  */
  97 static int thousands_sep;
  98
  99 /* Nonzero if the corresponding locales are hard.  */
 100 static bool hard_LC_COLLATE;
 101 #if HAVE_NL_LANGINFO
 102 static bool hard_LC_TIME;
 103 #endif
 104
 105 #define NONZERO(x) ((x) != 0)
 106
 107 /* The kind of blanks for '-b' to skip in various options. */
 108 enum blanktype { bl_start, bl_end, bl_both };
 109
 110 /* The character marking end of line. Default to \n. */
 111 static char eolchar = '\n';
 112
 113 /* Lines are held in core as counted strings. */
 114 struct line
 115 {
 116   char *text;                   /* Text of the line. */
 117   size_t length;                /* Length including final newline. */
 118   char *keybeg;                 /* Start of first key. */
 119   char *keylim;                 /* Limit of first key. */
 120 };
 121
 122 /* Input buffers. */
 123 struct buffer
 124 {
 125   char *buf;                    /* Dynamically allocated buffer,
 126                                    partitioned into 3 regions:
 127                                    - input data;
 128                                    - unused area;
 129                                    - an array of lines, in reverse order.  */
 130   size_t used;                  /* Number of bytes used for input data.  */
 131   size_t nlines;                /* Number of lines in the line array.  */
 132   size_t alloc;                 /* Number of bytes allocated. */
 133   size_t left;                  /* Number of bytes left from previous reads. */
 134   size_t line_bytes;            /* Number of bytes to reserve for each line. */
 135   bool eof;                     /* An EOF has been read.  */
 136 };
 137
 138 struct keyfield
 139 {
 140   size_t sword;                 /* Zero-origin 'word' to start at. */
 141   size_t schar;                 /* Additional characters to skip. */
 142   size_t eword;                 /* Zero-origin first word after field. */
 143   size_t echar;                 /* Additional characters in field. */
 144   bool const *ignore;           /* Boolean array of characters to ignore. */
 145   char const *translate;        /* Translation applied to characters. */
 146   bool skipsblanks;             /* Skip leading blanks when finding start.  */
 147   bool skipeblanks;             /* Skip leading blanks when finding end.  */
 148   bool numeric;                 /* Flag for numeric comparison.  Handle
 149                                    strings of digits with optional decimal
 150                                    point, but no exponential notation. */
 151   bool general_numeric;         /* Flag for general, numeric comparison.
 152                                    Handle numbers in exponential notation. */
 153   bool month;                   /* Flag for comparison by month name. */
 154   bool reverse;                 /* Reverse the sense of comparison. */
 155   struct keyfield *next;        /* Next keyfield to try. */
 156 };
 157
 158 struct month
 159 {
 160   char const *name;
 161   int val;
 162 };
 163
 164 /* The name this program was run with. */
 165 char *program_name;
 166
 167 /* FIXME: None of these tables work with multibyte character sets.
 168    Also, there are many other bugs when handling multibyte characters.
 169    One way to fix this is to rewrite `sort' to use wide characters
 170    internally, but doing this with good performance is a bit
 171    tricky.  */
 172
 173 /* Table of blanks.  */
 174 static bool blanks[UCHAR_LIM];
 175
 176 /* Table of non-printing characters. */
 177 static bool nonprinting[UCHAR_LIM];
 178
 179 /* Table of non-dictionary characters (not letters, digits, or blanks). */
 180 static bool nondictionary[UCHAR_LIM];
 181
 182 /* Translation table folding lower case to upper.  */
 183 static char fold_toupper[UCHAR_LIM];
 184
 185 #define MONTHS_PER_YEAR 12
 186
 187 /* Table mapping month names to integers.
 188    Alphabetic order allows binary search. */
 189 static struct month monthtab[] =
 190 {
 191   {"APR", 4},
 192   {"AUG", 8},
 193   {"DEC", 12},
 194   {"FEB", 2},
 195   {"JAN", 1},
 196   {"JUL", 7},
 197   {"JUN", 6},
 198   {"MAR", 3},
 199   {"MAY", 5},
 200   {"NOV", 11},
 201   {"OCT", 10},
 202   {"SEP", 9}
 203 };
 204
 205 /* During the merge phase, the number of files to merge at once. */
 206 #define NMERGE 16
 207
 208 /* Minimum size for a merge or check buffer.  */
 209 #define MIN_MERGE_BUFFER_SIZE (2 + sizeof (struct line))
 210
 211 /* Minimum sort size; the code might not work with smaller sizes.  */
 212 #define MIN_SORT_SIZE (NMERGE * MIN_MERGE_BUFFER_SIZE)
 213
 214 /* The number of bytes needed for a merge or check buffer, which can
 215    function relatively efficiently even if it holds only one line.  If
 216    a longer line is seen, this value is increased.  */
 217 static size_t merge_buffer_size = MAX (MIN_MERGE_BUFFER_SIZE, 256 * 1024);
 218
 219 /* The approximate maximum number of bytes of main memory to use, as
 220    specified by the user.  Zero if the user has not specified a size.  */
 221 static size_t sort_size;
 222
 223 /* The guessed size for non-regular files.  */
 224 #define INPUT_FILE_SIZE_GUESS (1024 * 1024)
 225
 226 /* Array of directory names in which any temporary files are to be created. */
 227 static char const **temp_dirs;
 228
 229 /* Number of temporary directory names used.  */
 230 static size_t temp_dir_count;
 231
 232 /* Number of allocated slots in temp_dirs.  */
 233 static size_t temp_dir_alloc;
 234
 235 /* Flag to reverse the order of all comparisons. */
 236 static bool reverse;
 237
 238 /* Flag for stable sort.  This turns off the last ditch bytewise
 239    comparison of lines, and instead leaves lines in the same order
 240    they were read if all keys compare equal.  */
 241 static bool stable;
 242
 243 /* If TAB has this value, blanks separate fields.  */
 244 enum { TAB_DEFAULT = CHAR_MAX + 1 };
 245
 246 /* Tab character separating fields.  If TAB_DEFAULT, then fields are
 247    separated by the empty string between a non-blank character and a blank
 248    character. */
 249 static int tab = TAB_DEFAULT;
 250
 251 /* Flag to remove consecutive duplicate lines from the output.
 252    Only the last of a sequence of equal lines will be output. */
 253 static bool unique;
 254
 255 /* Nonzero if any of the input files are the standard input. */
 256 static bool have_read_stdin;
 257
 258 /* List of key field comparisons to be tried.  */
 259 static struct keyfield *keylist;
 260
 261 static void sortlines_temp (struct line *, size_t, struct line *);
 262
 263 /* Report MESSAGE for FILE, then clean up and exit.
 264    If FILE is null, it represents standard output.  */
 265
 266 static void die (char const *, char const *) ATTRIBUTE_NORETURN;
 267 static void
 268 die (char const *message, char const *file)
 269 {
 270   error (0, errno, "%s: %s", message, file ? file : _("standard output"));
 271   exit (SORT_FAILURE);
 272 }
 273
 274 void
 275 usage (int status)
 276 {
 277   if (status != EXIT_SUCCESS)
 278     fprintf (stderr, _("Try `%s --help' for more information.\n"),
 279              program_name);
 280   else
 281     {
 282       printf (_("\
 283 Usage: %s [OPTION]... [FILE]...\n\
 284 "),
 285               program_name);
 286       fputs (_("\
 287 Write sorted concatenation of all FILE(s) to standard output.\n\
 288 \n\
 289 "), stdout);
 290       fputs (_("\
 291 Mandatory arguments to long options are mandatory for short options too.\n\
 292 "), stdout);
 293       fputs (_("\
 294 Ordering options:\n\
 295 \n\
 296 "), stdout);
 297       fputs (_("\
 298   -b, --ignore-leading-blanks ignore leading blanks\n\
 299   -d, --dictionary-order      consider only blanks and alphanumeric characters\n\
 300   -f, --ignore-case           fold lower case to upper case characters\n\
 301 "), stdout);
 302       fputs (_("\
 303   -g, --general-numeric-sort  compare according to general numerical value\n\
 304   -i, --ignore-nonprinting    consider only printable characters\n\
 305   -M, --month-sort            compare (unknown) < `JAN' < ... < `DEC'\n\
 306   -n, --numeric-sort          compare according to string numerical value\n\
 307   -r, --reverse               reverse the result of comparisons\n\
 308 \n\
 309 "), stdout);
 310       fputs (_("\
 311 Other options:\n\
 312 \n\
 313   -c, --check               check whether input is sorted; do not sort\n\
 314   -k, --key=POS1[,POS2]     start a key at POS1, end it at POS 2 (origin 1)\n\
 315   -m, --merge               merge already sorted files; do not sort\n\
 316   -o, --output=FILE         write result to FILE instead of standard output\n\
 317   -s, --stable              stabilize sort by disabling last-resort comparison\n\
 318   -S, --buffer-size=SIZE    use SIZE for main memory buffer\n\
 319 "), stdout);
 320       printf (_("\
 321   -t, --field-separator=SEP use SEP instead of non-blank to blank transition\n\
 322   -T, --temporary-directory=DIR  use DIR for temporaries, not $TMPDIR or %s;\n\
 323                               multiple options specify multiple directories\n\
 324   -u, --unique              with -c, check for strict ordering;\n\
 325                               without -c, output only the first of an equal run\n\
 326 "), DEFAULT_TMPDIR);
 327       fputs (_("\
 328   -z, --zero-terminated     end lines with 0 byte, not newline\n\
 329 "), stdout);
 330       fputs (HELP_OPTION_DESCRIPTION, stdout);
 331       fputs (VERSION_OPTION_DESCRIPTION, stdout);
 332       fputs (_("\
 333 \n\
 334 POS is F[.C][OPTS], where F is the field number and C the character position\n\
 335 in the field.  OPTS is one or more single-letter ordering options, which\n\
 336 override global ordering options for that key.  If no key is given, use the\n\
 337 entire line as the key.\n\
 338 \n\
 339 SIZE may be followed by the following multiplicative suffixes:\n\
 340 "), stdout);
 341       fputs (_("\
 342 % 1% of memory, b 1, K 1024 (default), and so on for M, G, T, P, E, Z, Y.\n\
 343 \n\
 344 With no FILE, or when FILE is -, read standard input.\n\
 345 \n\
 346 *** WARNING ***\n\
 347 The locale specified by the environment affects sort order.\n\
 348 Set LC_ALL=C to get the traditional sort order that uses\n\
 349 native byte values.\n\
 350 "), stdout );
 351       printf (_("\nReport bugs to <%s>.\n"), PACKAGE_BUGREPORT);
 352     }
 353
 354   exit (status);
 355 }
 356
 357 static char const short_options[] = "-bcdfgik:mMno:rsS:t:T:uy:z";
 358
 359 static struct option const long_options[] =
 360 {
 361   {"ignore-leading-blanks", no_argument, NULL, 'b'},
 362   {"check", no_argument, NULL, 'c'},
 363   {"dictionary-order", no_argument, NULL, 'd'},
 364   {"ignore-case", no_argument, NULL, 'f'},
 365   {"general-numeric-sort", no_argument, NULL, 'g'},
 366   {"ignore-nonprinting", no_argument, NULL, 'i'},
 367   {"key", required_argument, NULL, 'k'},
 368   {"merge", no_argument, NULL, 'm'},
 369   {"month-sort", no_argument, NULL, 'M'},
 370   {"numeric-sort", no_argument, NULL, 'n'},
 371   {"output", required_argument, NULL, 'o'},
 372   {"reverse", no_argument, NULL, 'r'},
 373   {"stable", no_argument, NULL, 's'},
 374   {"buffer-size", required_argument, NULL, 'S'},
 375   {"field-separator", required_argument, NULL, 't'},
 376   {"temporary-directory", required_argument, NULL, 'T'},
 377   {"unique", no_argument, NULL, 'u'},
 378   {"zero-terminated", no_argument, NULL, 'z'},
 379   {GETOPT_HELP_OPTION_DECL},
 380   {GETOPT_VERSION_OPTION_DECL},
 381   {NULL, 0, NULL, 0},
 382 };
 383
 384 /* The set of signals that are caught.  */
 385 static sigset_t caught_signals;
 386
 387 /* The list of temporary files. */
 388 struct tempnode
 389 {
 390   struct tempnode *volatile next;
 391   char name[1];  /* Actual size is 1 + file name length.  */
 392 };
 393 static struct tempnode *volatile temphead;
 394 static struct tempnode *volatile *temptail = &temphead;
 395
 396 /* Clean up any remaining temporary files.  */
 397
 398 static void
 399 cleanup (void)
 400 {
 401   struct tempnode const *node;
 402
 403   for (node = temphead; node; node = node->next)
 404     unlink (node->name);
 405 }
 406
 407 /* Create a new temporary file, returning its newly allocated name.
 408    Store into *PFP a stream open for writing.  */
 409
 410 static char *
 411 create_temp_file (FILE **pfp)
 412 {
 413   static char const slashbase[] = "/sortXXXXXX";
 414   static size_t temp_dir_index;
 415   sigset_t oldset;
 416   int fd;
 417   int saved_errno;
 418   char const *temp_dir = temp_dirs[temp_dir_index];
 419   size_t len = strlen (temp_dir);
 420   struct tempnode *node =
 421     xmalloc (offsetof (struct tempnode, name) + len + sizeof slashbase);
 422   char *file = node->name;
 423
 424   memcpy (file, temp_dir, len);
 425   memcpy (file + len, slashbase, sizeof slashbase);
 426   node->next = NULL;
 427   if (++temp_dir_index == temp_dir_count)
 428     temp_dir_index = 0;
 429
 430   /* Create the temporary file in a critical section, to avoid races.  */
 431   sigprocmask (SIG_BLOCK, &caught_signals, &oldset);
 432   fd = mkstemp (file);
 433   if (0 <= fd)
 434     {
 435       *temptail = node;
 436       temptail = &node->next;
 437     }
 438   saved_errno = errno;
 439   sigprocmask (SIG_SETMASK, &oldset, NULL);
 440   errno = saved_errno;
 441
 442   if (fd < 0 || (*pfp = fdopen (fd, "w")) == NULL)
 443     die (_("cannot create temporary file"), file);
 444
 445   return file;
 446 }
 447
 448 /* Return a stream for FILE, opened with mode HOW.  A null FILE means
 449    standard output; HOW should be "w".  When opening for input, "-"
 450    means standard input.  To avoid confusion, do not return file
 451    descriptors STDIN_FILENO, STDOUT_FILENO, or STDERR_FILENO when
 452    opening an ordinary FILE.  */
 453
 454 static FILE *
 455 xfopen (const char *file, const char *how)
 456 {
 457   FILE *fp;
 458
 459   if (!file)
 460     fp = stdout;
 461   else if (STREQ (file, "-") && *how == 'r')
 462     {
 463       have_read_stdin = true;
 464       fp = stdin;
 465     }
 466   else
 467     {
 468       fp = fopen (file, how);
 469       if (! fp)
 470         die (_("open failed"), file);
 471     }
 472
 473   return fp;
 474 }
 475
 476 /* Close FP, whose name is FILE, and report any errors.  */
 477
 478 static void
 479 xfclose (FILE *fp, char const *file)
 480 {
 481   switch (fileno (fp))
 482     {
 483     case STDIN_FILENO:
 484       /* Allow reading stdin from tty more than once.  */
 485       if (feof (fp))
 486         clearerr (fp);
 487       break;
 488
 489     case STDOUT_FILENO:
 490       /* Don't close stdout just yet.  close_stdout does that.  */
 491       if (fflush (fp) != 0)
 492         die (_("fflush failed"), file);
 493       break;
 494
 495     default:
 496       if (fclose (fp) != 0)
 497         die (_("close failed"), file);
 498       break;
 499     }
 500 }
 501
 502 static void
 503 write_bytes (const char *buf, size_t n_bytes, FILE *fp, const char *output_file)
 504 {
 505   if (fwrite (buf, 1, n_bytes, fp) != n_bytes)
 506     die (_("write failed"), output_file);
 507 }
 508
 509 /* Append DIR to the array of temporary directory names.  */
 510 static void
 511 add_temp_dir (char const *dir)
 512 {
 513   if (temp_dir_count == temp_dir_alloc)
 514     temp_dirs = x2nrealloc (temp_dirs, &temp_dir_alloc, sizeof *temp_dirs);
 515
 516   temp_dirs[temp_dir_count++] = dir;
 517 }
 518
 519 /* Remove NAME from the list of temporary files.  */
 520
 521 static void
 522 zaptemp (const char *name)
 523 {
 524   struct tempnode *volatile *pnode;
 525   struct tempnode *node;
 526   struct tempnode *next;
 527   sigset_t oldset;
 528   int unlink_status;
 529   int unlink_errno = 0;
 530
 531   for (pnode = &temphead; (node = *pnode)->name != name; pnode = &node->next)
 532     continue;
 533
 534   /* Unlink the temporary file in a critical section to avoid races.  */
 535   next = node->next;
 536   sigprocmask (SIG_BLOCK, &caught_signals, &oldset);
 537   unlink_status = unlink (name);
 538   unlink_errno = errno;
 539   *pnode = next;
 540   sigprocmask (SIG_SETMASK, &oldset, NULL);
 541
 542   if (unlink_status != 0)
 543     error (0, unlink_errno, _("warning: cannot remove: %s"), name);
 544   if (! next)
 545     temptail = pnode;
 546   free (node);
 547 }
 548
 549 #if HAVE_NL_LANGINFO
 550
 551 static int
 552 struct_month_cmp (const void *m1, const void *m2)
 553 {
 554   struct month const *month1 = m1;
 555   struct month const *month2 = m2;
 556   return strcmp (month1->name, month2->name);
 557 }
 558
 559 #endif
 560
 561 /* Initialize the character class tables. */
 562
 563 static void
 564 inittables (void)
 565 {
 566   size_t i;
 567
 568   for (i = 0; i < UCHAR_LIM; ++i)
 569     {
 570       blanks[i] = !!ISBLANK (i);
 571       nonprinting[i] = !ISPRINT (i);
 572       nondictionary[i] = !ISALNUM (i) && !ISBLANK (i);
 573       fold_toupper[i] = (ISLOWER (i) ? toupper (i) : i);
 574     }
 575
 576 #if HAVE_NL_LANGINFO
 577   /* If we're not in the "C" locale, read different names for months.  */
 578   if (hard_LC_TIME)
 579     {
 580       for (i = 0; i < MONTHS_PER_YEAR; i++)
 581         {
 582           char const *s;
 583           size_t s_len;
 584           size_t j;
 585           char *name;
 586
 587           s = (char *) nl_langinfo (ABMON_1 + i);
 588           s_len = strlen (s);
 589           monthtab[i].name = name = xmalloc (s_len + 1);
 590           monthtab[i].val = i + 1;
 591
 592           for (j = 0; j < s_len; j++)
 593             name[j] = fold_toupper[to_uchar (s[j])];
 594           name[j] = '\0';
 595         }
 596       qsort ((void *) monthtab, MONTHS_PER_YEAR,
 597              sizeof *monthtab, struct_month_cmp);
 598     }
 599 #endif
 600 }
 601
 602 /* Specify the amount of main memory to use when sorting.  */
 603 static void
 604 specify_sort_size (char const *s)
 605 {
 606   uintmax_t n;
 607   char *suffix;
 608   enum strtol_error e = xstrtoumax (s, &suffix, 10, &n, "EgGkKmMPtTYZ");
 609
 610   /* The default unit is KiB.  */
 611   if (e == LONGINT_OK && ISDIGIT (suffix[-1]))
 612     {
 613       if (n <= UINTMAX_MAX / 1024)
 614         n *= 1024;
 615       else
 616         e = LONGINT_OVERFLOW;
 617     }
 618
 619   /* A 'b' suffix means bytes; a '%' suffix means percent of memory.  */
 620   if (e == LONGINT_INVALID_SUFFIX_CHAR && ISDIGIT (suffix[-1]) && ! suffix[1])
 621     switch (suffix[0])
 622       {
 623       case 'b':
 624         e = LONGINT_OK;
 625         break;
 626
 627       case '%':
 628         {
 629           double mem = physmem_total () * n / 100;
 630
 631           /* Use "<", not "<=", to avoid problems with rounding.  */
 632           if (mem < UINTMAX_MAX)
 633             {
 634               n = mem;
 635               e = LONGINT_OK;
 636             }
 637           else
 638             e = LONGINT_OVERFLOW;
 639         }
 640         break;
 641       }
 642
 643   if (e == LONGINT_OK)
 644     {
 645       /* If multiple sort sizes are specified, take the maximum, so
 646          that option order does not matter.  */
 647       if (n < sort_size)
 648         return;
 649
 650       sort_size = n;
 651       if (sort_size == n)
 652         {
 653           sort_size = MAX (sort_size, MIN_SORT_SIZE);
 654           return;
 655         }
 656
 657       e = LONGINT_OVERFLOW;
 658     }
 659
 660   STRTOL_FATAL_ERROR (s, _("sort size"), e);
 661 }
 662
 663 /* Return the default sort size.  */
 664 static size_t
 665 default_sort_size (void)
 666 {
 667   /* Let MEM be available memory or 1/8 of total memory, whichever
 668      is greater.  */
 669   double avail = physmem_available ();
 670   double total = physmem_total ();
 671   double mem = MAX (avail, total / 8);
 672   struct rlimit rlimit;
 673
 674   /* Let SIZE be MEM, but no more than the maximum object size or
 675      system resource limits.  Avoid the MIN macro here, as it is not
 676      quite right when only one argument is floating point.  Don't
 677      bother to check for values like RLIM_INFINITY since in practice
 678      they are not much less than SIZE_MAX.  */
 679   size_t size = SIZE_MAX;
 680   if (mem < size)
 681     size = mem;
 682   if (getrlimit (RLIMIT_DATA, &rlimit) == 0 && rlimit.rlim_cur < size)
 683     size = rlimit.rlim_cur;
 684 #ifdef RLIMIT_AS
 685   if (getrlimit (RLIMIT_AS, &rlimit) == 0 && rlimit.rlim_cur < size)
 686     size = rlimit.rlim_cur;
 687 #endif
 688
 689   /* Leave a large safety margin for the above limits, as failure can
 690      occur when they are exceeded.  */
 691   size /= 2;
 692
 693 #ifdef RLIMIT_RSS
 694   /* Leave a 1/16 margin for RSS to leave room for code, stack, etc.
 695      Exceeding RSS is not fatal, but can be quite slow.  */
 696   if (getrlimit (RLIMIT_RSS, &rlimit) == 0 && rlimit.rlim_cur / 16 * 15 < size)
 697     size = rlimit.rlim_cur / 16 * 15;
 698 #endif
 699
 700   /* Use no less than the minimum.  */
 701   return MAX (size, MIN_SORT_SIZE);
 702 }
 703
 704 /* Return the sort buffer size to use with the input files identified
 705    by FPS and FILES, which are alternate names of the same files.
 706    NFILES gives the number of input files; NFPS may be less.  Assume
 707    that each input line requires LINE_BYTES extra bytes' worth of line
 708    information.  Do not exceed a bound on the size: if the bound is
 709    not specified by the user, use a default.  */
 710
 711 static size_t
 712 sort_buffer_size (FILE *const *fps, size_t nfps,
 713                   char *const *files, size_t nfiles,
 714                   size_t line_bytes)
 715 {
 716   /* A bound on the input size.  If zero, the bound hasn't been
 717      determined yet.  */
 718   static size_t size_bound;
 719
 720   /* In the worst case, each input byte is a newline.  */
 721   size_t worst_case_per_input_byte = line_bytes + 1;
 722
 723   /* Keep enough room for one extra input line and an extra byte.
 724      This extra room might be needed when preparing to read EOF.  */
 725   size_t size = worst_case_per_input_byte + 1;
 726
 727   size_t i;
 728
 729   for (i = 0; i < nfiles; i++)
 730     {
 731       struct stat st;
 732       off_t file_size;
 733       size_t worst_case;
 734
 735       if ((i < nfps ? fstat (fileno (fps[i]), &st)
 736            : STREQ (files[i], "-") ? fstat (STDIN_FILENO, &st)
 737            : stat (files[i], &st))
 738           != 0)
 739         die (_("stat failed"), files[i]);
 740
 741       if (S_ISREG (st.st_mode))
 742         file_size = st.st_size;
 743       else
 744         {
 745           /* The file has unknown size.  If the user specified a sort
 746              buffer size, use that; otherwise, guess the size.  */
 747           if (sort_size)
 748             return sort_size;
 749           file_size = INPUT_FILE_SIZE_GUESS;
 750         }
 751
 752       if (! size_bound)
 753         {
 754           size_bound = sort_size;
 755           if (! size_bound)
 756             size_bound = default_sort_size ();
 757         }
 758
 759       /* Add the amount of memory needed to represent the worst case
 760          where the input consists entirely of newlines followed by a
 761          single non-newline.  Check for overflow.  */
 762       worst_case = file_size * worst_case_per_input_byte + 1;
 763       if (file_size != worst_case / worst_case_per_input_byte
 764           || size_bound - size <= worst_case)
 765         return size_bound;
 766       size += worst_case;
 767     }
 768
 769   return size;
 770 }
 771
 772 /* Initialize BUF.  Reserve LINE_BYTES bytes for each line; LINE_BYTES
 773    must be at least sizeof (struct line).  Allocate ALLOC bytes
 774    initially.  */
 775
 776 static void
 777 initbuf (struct buffer *buf, size_t line_bytes, size_t alloc)
 778 {
 779   /* Ensure that the line array is properly aligned.  If the desired
 780      size cannot be allocated, repeatedly halve it until allocation
 781      succeeds.  The smaller allocation may hurt overall performance,
 782      but that's better than failing.  */
 783   for (;;)
 784     {
 785       alloc += sizeof (struct line) - alloc % sizeof (struct line);
 786       buf->buf = malloc (alloc);
 787       if (buf->buf)
 788         break;
 789       alloc /= 2;
 790       if (alloc <= line_bytes + 1)
 791         xalloc_die ();
 792     }
 793
 794   buf->line_bytes = line_bytes;
 795   buf->alloc = alloc;
 796   buf->used = buf->left = buf->nlines = 0;
 797   buf->eof = false;
 798 }
 799
 800 /* Return one past the limit of the line array.  */
 801
 802 static inline struct line *
 803 buffer_linelim (struct buffer const *buf)
 804 {
 805   return (struct line *) (buf->buf + buf->alloc);
 806 }
 807
 808 /* Return a pointer to the first character of the field specified
 809    by KEY in LINE. */
 810
 811 static char *
 812 begfield (const struct line *line, const struct keyfield *key)
 813 {
 814   char *ptr = line->text, *lim = ptr + line->length - 1;
 815   size_t sword = key->sword;
 816   size_t schar = key->schar;
 817   size_t remaining_bytes;
 818
 819   /* The leading field separator itself is included in a field when -t
 820      is absent.  */
 821
 822   if (tab != TAB_DEFAULT)
 823     while (ptr < lim && sword--)
 824       {
 825         while (ptr < lim && *ptr != tab)
 826           ++ptr;
 827         if (ptr < lim)
 828           ++ptr;
 829       }
 830   else
 831     while (ptr < lim && sword--)
 832       {
 833         while (ptr < lim && blanks[to_uchar (*ptr)])
 834           ++ptr;
 835         while (ptr < lim && !blanks[to_uchar (*ptr)])
 836           ++ptr;
 837       }
 838
 839   if (key->skipsblanks)
 840     while (ptr < lim && blanks[to_uchar (*ptr)])
 841       ++ptr;
 842
 843   /* Advance PTR by SCHAR (if possible), but no further than LIM.  */
 844   remaining_bytes = lim - ptr;
 845   if (schar < remaining_bytes)
 846     ptr += schar;
 847   else
 848     ptr = lim;
 849
 850   return ptr;
 851 }
 852
 853 /* Return the limit of (a pointer to the first character after) the field
 854    in LINE specified by KEY. */
 855
 856 static char *
 857 limfield (const struct line *line, const struct keyfield *key)
 858 {
 859   char *ptr = line->text, *lim = ptr + line->length - 1;
 860   size_t eword = key->eword, echar = key->echar;
 861   size_t remaining_bytes;
 862
 863   /* Move PTR past EWORD fields or to one past the last byte on LINE,
 864      whichever comes first.  If there are more than EWORD fields, leave
 865      PTR pointing at the beginning of the field having zero-based index,
 866      EWORD.  If a delimiter character was specified (via -t), then that
 867      `beginning' is the first character following the delimiting TAB.
 868      Otherwise, leave PTR pointing at the first `blank' character after
 869      the preceding field.  */
 870   if (tab != TAB_DEFAULT)
 871     while (ptr < lim && eword--)
 872       {
 873         while (ptr < lim && *ptr != tab)
 874           ++ptr;
 875         if (ptr < lim && (eword | echar))
 876           ++ptr;
 877       }
 878   else
 879     while (ptr < lim && eword--)
 880       {
 881         while (ptr < lim && blanks[to_uchar (*ptr)])
 882           ++ptr;
 883         while (ptr < lim && !blanks[to_uchar (*ptr)])
 884           ++ptr;
 885       }
 886
 887 #ifdef POSIX_UNSPECIFIED
 888   /* The following block of code makes GNU sort incompatible with
 889      standard Unix sort, so it's ifdef'd out for now.
 890      The POSIX spec isn't clear on how to interpret this.
 891      FIXME: request clarification.
 892
 893      From: kwzh@gnu.ai.mit.edu (Karl Heuer)
 894      Date: Thu, 30 May 96 12:20:41 -0400
 895      [Translated to POSIX 1003.1-2001 terminology by Paul Eggert.]
 896
 897      [...]I believe I've found another bug in `sort'.
 898
 899      $ cat /tmp/sort.in
 900      a b c 2 d
 901      pq rs 1 t
 902      $ textutils-1.15/src/sort -k1.7,1.7 </tmp/sort.in
 903      a b c 2 d
 904      pq rs 1 t
 905      $ /bin/sort -k1.7,1.7 </tmp/sort.in
 906      pq rs 1 t
 907      a b c 2 d
 908
 909      Unix sort produced the answer I expected: sort on the single character
 910      in column 7.  GNU sort produced different results, because it disagrees
 911      on the interpretation of the key-end spec "M.N".  Unix sort reads this
 912      as "skip M-1 fields, then N-1 characters"; but GNU sort wants it to mean
 913      "skip M-1 fields, then either N-1 characters or the rest of the current
 914      field, whichever comes first".  This extra clause applies only to
 915      key-ends, not key-starts.
 916      */
 917
 918   /* Make LIM point to the end of (one byte past) the current field.  */
 919   if (tab != TAB_DEFAULT)
 920     {
 921       char *newlim;
 922       newlim = memchr (ptr, tab, lim - ptr);
 923       if (newlim)
 924         lim = newlim;
 925     }
 926   else
 927     {
 928       char *newlim;
 929       newlim = ptr;
 930       while (newlim < lim && blanks[to_uchar (*newlim)])
 931         ++newlim;
 932       while (newlim < lim && !blanks[to_uchar (*newlim)])
 933         ++newlim;
 934       lim = newlim;
 935     }
 936 #endif
 937
 938   /* If we're ignoring leading blanks when computing the End
 939      of the field, don't start counting bytes until after skipping
 940      past any leading blanks. */
 941   if (key->skipeblanks)
 942     while (ptr < lim && blanks[to_uchar (*ptr)])
 943       ++ptr;
 944
 945   /* Advance PTR by ECHAR (if possible), but no further than LIM.  */
 946   remaining_bytes = lim - ptr;
 947   if (echar < remaining_bytes)
 948     ptr += echar;
 949   else
 950     ptr = lim;
 951
 952   return ptr;
 953 }
 954
 955 /* Fill BUF reading from FP, moving buf->left bytes from the end
 956    of buf->buf to the beginning first.  If EOF is reached and the
 957    file wasn't terminated by a newline, supply one.  Set up BUF's line
 958    table too.  FILE is the name of the file corresponding to FP.
 959    Return true if some input was read.  */
 960
 961 static bool
 962 fillbuf (struct buffer *buf, FILE *fp, char const *file)
 963 {
 964   struct keyfield const *key = keylist;
 965   char eol = eolchar;
 966   size_t line_bytes = buf->line_bytes;
 967   size_t mergesize = merge_buffer_size - MIN_MERGE_BUFFER_SIZE;
 968
 969   if (buf->eof)
 970     return false;
 971
 972   if (buf->used != buf->left)
 973     {
 974       memmove (buf->buf, buf->buf + buf->used - buf->left, buf->left);
 975       buf->used = buf->left;
 976       buf->nlines = 0;
 977     }
 978
 979   for (;;)
 980     {
 981       char *ptr = buf->buf + buf->used;
 982       struct line *linelim = buffer_linelim (buf);
 983       struct line *line = linelim - buf->nlines;
 984       size_t avail = (char *) linelim - buf->nlines * line_bytes - ptr;
 985       char *line_start = buf->nlines ? line->text + line->length : buf->buf;
 986
 987       while (line_bytes + 1 < avail)
 988         {
 989           /* Read as many bytes as possible, but do not read so many
 990              bytes that there might not be enough room for the
 991              corresponding line array.  The worst case is when the
 992              rest of the input file consists entirely of newlines,
 993              except that the last byte is not a newline.  */
 994           size_t readsize = (avail - 1) / (line_bytes + 1);
 995           size_t bytes_read = fread (ptr, 1, readsize, fp);
 996           char *ptrlim = ptr + bytes_read;
 997           char *p;
 998           avail -= bytes_read;
 999
1000           if (bytes_read != readsize)
1001             {
1002               if (ferror (fp))
1003                 die (_("read failed"), file);
1004               if (feof (fp))
1005                 {
1006                   buf->eof = true;
1007                   if (buf->buf == ptrlim)
1008                     return false;
1009                   if (ptrlim[-1] != eol)
1010                     *ptrlim++ = eol;
1011                 }
1012             }
1013
1014           /* Find and record each line in the just-read input.  */
1015           while ((p = memchr (ptr, eol, ptrlim - ptr)))
1016             {
1017               ptr = p + 1;
1018               line--;
1019               line->text = line_start;
1020               line->length = ptr - line_start;
1021               mergesize = MAX (mergesize, line->length);
1022               avail -= line_bytes;
1023
1024               if (key)
1025                 {
1026                   /* Precompute the position of the first key for
1027                      efficiency.  */
1028                   line->keylim = (key->eword == SIZE_MAX
1029                                   ? p
1030                                   : limfield (line, key));
1031
1032                   if (key->sword != SIZE_MAX)
1033                     line->keybeg = begfield (line, key);
1034                   else
1035                     {
1036                       if (key->skipsblanks)
1037                         while (blanks[to_uchar (*line_start)])
1038                           line_start++;
1039                       line->keybeg = line_start;
1040                     }
1041                 }
1042
1043               line_start = ptr;
1044             }
1045
1046           ptr = ptrlim;
1047           if (buf->eof)
1048             break;
1049         }
1050
1051       buf->used = ptr - buf->buf;
1052       buf->nlines = buffer_linelim (buf) - line;
1053       if (buf->nlines != 0)
1054         {
1055           buf->left = ptr - line_start;
1056           merge_buffer_size = mergesize + MIN_MERGE_BUFFER_SIZE;
1057           return true;
1058         }
1059
1060       /* The current input line is too long to fit in the buffer.
1061          Double the buffer size and try again.  */
1062       buf->buf = X2REALLOC (buf->buf, &buf->alloc);
1063     }
1064 }
1065
1066 /* Compare strings A and B as numbers without explicitly converting them to
1067    machine numbers.  Comparatively slow for short strings, but asymptotically
1068    hideously fast. */
1069
1070 static int
1071 numcompare (const char *a, const char *b)
1072 {
1073   while (blanks[to_uchar (*a)])
1074     a++;
1075   while (blanks[to_uchar (*b)])
1076     b++;
1077
1078   return strnumcmp (a, b, decimal_point, thousands_sep);
1079 }
1080
1081 static int
1082 general_numcompare (const char *sa, const char *sb)
1083 {
1084   /* FIXME: add option to warn about failed conversions.  */
1085   /* FIXME: maybe add option to try expensive FP conversion
1086      only if A and B can't be compared more cheaply/accurately.  */
1087
1088   char *ea;
1089   char *eb;
1090   double a = strtod (sa, &ea);
1091   double b = strtod (sb, &eb);
1092
1093   /* Put conversion errors at the start of the collating sequence.  */
1094   if (sa == ea)
1095     return sb == eb ? 0 : -1;
1096   if (sb == eb)
1097     return 1;
1098
1099   /* Sort numbers in the usual way, where -0 == +0.  Put NaNs after
1100      conversion errors but before numbers; sort them by internal
1101      bit-pattern, for lack of a more portable alternative.  */
1102   return (a < b ? -1
1103           : a > b ? 1
1104           : a == b ? 0
1105           : b == b ? -1
1106           : a == a ? 1
1107           : memcmp ((char *) &a, (char *) &b, sizeof a));
1108 }
1109
1110 /* Return an integer in 1..12 of the month name MONTH with length LEN.
1111    Return 0 if the name in S is not recognized.  */
1112
1113 static int
1114 getmonth (char const *month, size_t len)
1115 {
1116   size_t lo = 0;
1117   size_t hi = MONTHS_PER_YEAR;
1118   char const *monthlim = month + len;
1119
1120   for (;;)
1121     {
1122       if (month == monthlim)
1123         return 0;
1124       if (!blanks[to_uchar (*month)])
1125         break;
1126       ++month;
1127     }
1128
1129   do
1130     {
1131       size_t ix = (lo + hi) / 2;
1132       char const *m = month;
1133       char const *n = monthtab[ix].name;
1134
1135       for (;; m++, n++)
1136         {
1137           if (!*n)
1138             return monthtab[ix].val;
1139           if (m == monthlim || fold_toupper[to_uchar (*m)] < to_uchar (*n))
1140             {
1141               hi = ix;
1142               break;
1143             }
1144           else if (fold_toupper[to_uchar (*m)] > to_uchar (*n))
1145             {
1146               lo = ix + 1;
1147               break;
1148             }
1149         }
1150     }
1151   while (lo < hi);
1152
1153   return 0;
1154 }
1155
1156 /* Compare two lines A and B trying every key in sequence until there
1157    are no more keys or a difference is found. */
1158
1159 static int
1160 keycompare (const struct line *a, const struct line *b)
1161 {
1162   struct keyfield const *key = keylist;
1163
1164   /* For the first iteration only, the key positions have been
1165      precomputed for us. */
1166   char *texta = a->keybeg;
1167   char *textb = b->keybeg;
1168   char *lima = a->keylim;
1169   char *limb = b->keylim;
1170
1171   int diff;
1172
1173   for (;;)
1174     {
1175       char const *translate = key->translate;
1176       bool const *ignore = key->ignore;
1177
1178       /* Find the lengths. */
1179       size_t lena = lima <= texta ? 0 : lima - texta;
1180       size_t lenb = limb <= textb ? 0 : limb - textb;
1181
1182       /* Actually compare the fields. */
1183       if (key->numeric | key->general_numeric)
1184         {
1185           char savea = *lima, saveb = *limb;
1186
1187           *lima = *limb = '\0';
1188           diff = ((key->numeric ? numcompare : general_numcompare)
1189                   (texta, textb));
1190           *lima = savea, *limb = saveb;
1191         }
1192       else if (key->month)
1193         diff = getmonth (texta, lena) - getmonth (textb, lenb);
1194       /* Sorting like this may become slow, so in a simple locale the user
1195          can select a faster sort that is similar to ascii sort.  */
1196       else if (hard_LC_COLLATE)
1197         {
1198           if (ignore || translate)
1199             {
1200               char buf[4000];
1201               size_t size = lena + 1 + lenb + 1;
1202               char *copy_a = (size <= sizeof buf ? buf : xmalloc (size));
1203               char *copy_b = copy_a + lena + 1;
1204               size_t new_len_a, new_len_b, i;
1205
1206               /* Ignore and/or translate chars before comparing.  */
1207               for (new_len_a = new_len_b = i = 0; i < MAX (lena, lenb); i++)
1208                 {
1209                   if (i < lena)
1210                     {
1211                       copy_a[new_len_a] = (translate
1212                                            ? translate[to_uchar (texta[i])]
1213                                            : texta[i]);
1214                       if (!ignore || !ignore[to_uchar (texta[i])])
1215                         ++new_len_a;
1216                     }
1217                   if (i < lenb)
1218                     {
1219                       copy_b[new_len_b] = (translate
1220                                            ? translate[to_uchar (textb[i])]
1221                                            : textb [i]);
1222                       if (!ignore || !ignore[to_uchar (textb[i])])
1223                         ++new_len_b;
1224                     }
1225                 }
1226
1227               diff = xmemcoll (copy_a, new_len_a, copy_b, new_len_b);
1228
1229               if (sizeof buf < size)
1230                 free (copy_a);
1231             }
1232           else if (lena == 0)
1233             diff = - NONZERO (lenb);
1234           else if (lenb == 0)
1235             goto greater;
1236           else
1237             diff = xmemcoll (texta, lena, textb, lenb);
1238         }
1239       else if (ignore)
1240         {
1241 #define CMP_WITH_IGNORE(A, B)                                           \
1242   do                                                                    \
1243     {                                                                   \
1244           for (;;)                                                      \
1245             {                                                           \
1246               while (texta < lima && ignore[to_uchar (*texta)])         \
1247                 ++texta;                                                \
1248               while (textb < limb && ignore[to_uchar (*textb)])         \
1249                 ++textb;                                                \
1250               if (! (texta < lima && textb < limb))                     \
1251                 break;                                                  \
1252               diff = to_uchar (A) - to_uchar (B);                       \
1253               if (diff)                                                 \
1254                 goto not_equal;                                         \
1255               ++texta;                                                  \
1256               ++textb;                                                  \
1257             }                                                           \
1258                                                                         \
1259           diff = (texta < lima) - (textb < limb);                       \
1260     }                                                                   \
1261   while (0)
1262
1263           if (translate)
1264             CMP_WITH_IGNORE (translate[to_uchar (*texta)],
1265                              translate[to_uchar (*textb)]);
1266           else
1267             CMP_WITH_IGNORE (*texta, *textb);
1268         }
1269       else if (lena == 0)
1270         diff = - NONZERO (lenb);
1271       else if (lenb == 0)
1272         goto greater;
1273       else
1274         {
1275           if (translate)
1276             {
1277               while (texta < lima && textb < limb)
1278                 {
1279                   diff = (to_uchar (translate[to_uchar (*texta++)])
1280                           - to_uchar (translate[to_uchar (*textb++)]));
1281                   if (diff)
1282                     goto not_equal;
1283                 }
1284             }
1285           else
1286             {
1287               diff = memcmp (texta, textb, MIN (lena, lenb));
1288               if (diff)
1289                 goto not_equal;
1290             }
1291           diff = lena < lenb ? -1 : lena != lenb;
1292         }
1293
1294       if (diff)
1295         goto not_equal;
1296
1297       key = key->next;
1298       if (! key)
1299         break;
1300
1301       /* Find the beginning and limit of the next field.  */
1302       if (key->eword != SIZE_MAX)
1303         lima = limfield (a, key), limb = limfield (b, key);
1304       else
1305         lima = a->text + a->length - 1, limb = b->text + b->length - 1;
1306
1307       if (key->sword != SIZE_MAX)
1308         texta = begfield (a, key), textb = begfield (b, key);
1309       else
1310         {
1311           texta = a->text, textb = b->text;
1312           if (key->skipsblanks)
1313             {
1314               while (texta < lima && blanks[to_uchar (*texta)])
1315                 ++texta;
1316               while (textb < limb && blanks[to_uchar (*textb)])
1317                 ++textb;
1318             }
1319         }
1320     }
1321
1322   return 0;
1323
1324  greater:
1325   diff = 1;
1326  not_equal:
1327   return key->reverse ? -diff : diff;
1328 }
1329
1330 /* Compare two lines A and B, returning negative, zero, or positive
1331    depending on whether A compares less than, equal to, or greater than B. */
1332
1333 static int
1334 compare (const struct line *a, const struct line *b)
1335 {
1336   int diff;
1337   size_t alen, blen;
1338
1339   /* First try to compare on the specified keys (if any).
1340      The only two cases with no key at all are unadorned sort,
1341      and unadorned sort -r. */
1342   if (keylist)
1343     {
1344       diff = keycompare (a, b);
1345       if (diff | unique | stable)
1346         return diff;
1347     }
1348
1349   /* If the keys all compare equal (or no keys were specified)
1350      fall through to the default comparison.  */
1351   alen = a->length - 1, blen = b->length - 1;
1352
1353   if (alen == 0)
1354     diff = - NONZERO (blen);
1355   else if (blen == 0)
1356     diff = 1;
1357   else if (hard_LC_COLLATE)
1358     diff = xmemcoll (a->text, alen, b->text, blen);
1359   else if (! (diff = memcmp (a->text, b->text, MIN (alen, blen))))
1360     diff = alen < blen ? -1 : alen != blen;
1361
1362   return reverse ? -diff : diff;
1363 }
1364
1365 /* Check that the lines read from FILE_NAME come in order.  Print a
1366    diagnostic (FILE_NAME, line number, contents of line) to stderr and return
1367    false if they are not in order.  Otherwise, print no diagnostic
1368    and return true.  */
1369
1370 static bool
1371 check (char const *file_name)
1372 {
1373   FILE *fp = xfopen (file_name, "r");
1374   struct buffer buf;            /* Input buffer. */
1375   struct line temp;             /* Copy of previous line. */
1376   size_t alloc = 0;
1377   uintmax_t line_number = 0;
1378   struct keyfield const *key = keylist;
1379   bool nonunique = ! unique;
1380   bool ordered = true;
1381
1382   initbuf (&buf, sizeof (struct line),
1383            MAX (merge_buffer_size, sort_size));
1384   temp.text = NULL;
1385
1386   while (fillbuf (&buf, fp, file_name))
1387     {
1388       struct line const *line = buffer_linelim (&buf);
1389       struct line const *linebase = line - buf.nlines;
1390
1391       /* Make sure the line saved from the old buffer contents is
1392          less than or equal to the first line of the new buffer. */
1393       if (alloc && nonunique <= compare (&temp, line - 1))
1394         {
1395         found_disorder:
1396           {
1397             struct line const *disorder_line = line - 1;
1398             uintmax_t disorder_line_number =
1399               buffer_linelim (&buf) - disorder_line + line_number;
1400             char hr_buf[INT_BUFSIZE_BOUND (uintmax_t)];
1401             fprintf (stderr, _("%s: %s:%s: disorder: "),
1402                      program_name, file_name,
1403                      umaxtostr (disorder_line_number, hr_buf));
1404             write_bytes (disorder_line->text, disorder_line->length, stderr,
1405                          _("standard error"));
1406             ordered = false;
1407             break;
1408           }
1409         }
1410
1411       /* Compare each line in the buffer with its successor.  */
1412       while (linebase < --line)
1413         if (nonunique <= compare (line, line - 1))
1414           goto found_disorder;
1415
1416       line_number += buf.nlines;
1417
1418       /* Save the last line of the buffer.  */
1419       if (alloc < line->length)
1420         {
1421           do
1422             {
1423               alloc *= 2;
1424               if (! alloc)
1425                 {
1426                   alloc = line->length;
1427                   break;
1428                 }
1429             }
1430           while (alloc < line->length);
1431
1432           temp.text = xrealloc (temp.text, alloc);
1433         }
1434       memcpy (temp.text, line->text, line->length);
1435       temp.length = line->length;
1436       if (key)
1437         {
1438           temp.keybeg = temp.text + (line->keybeg - line->text);
1439           temp.keylim = temp.text + (line->keylim - line->text);
1440         }
1441     }
1442
1443   xfclose (fp, file_name);
1444   free (buf.buf);
1445   free (temp.text);
1446   return ordered;
1447 }
1448
1449 /* Merge lines from FILES onto OFP.  NTEMPS is the number of temporary
1450    files (all of which are at the start of the FILES array), and
1451    NFILES is the number of files; 0 <= NTEMPS <= NFILES <= NMERGE.
1452    Close input and output files before returning.
1453    OUTPUT_FILE gives the name of the output file.  If it is NULL,
1454    the output file is standard output.  If OFP is NULL, the output
1455    file has not been opened yet (or written to, if standard output).  */
1456
1457 static void
1458 mergefps (char **files, size_t ntemps, size_t nfiles,
1459           FILE *ofp, char const *output_file)
1460 {
1461   FILE *fps[NMERGE];            /* Input streams for each file.  */
1462   struct buffer buffer[NMERGE]; /* Input buffers for each file. */
1463   struct line saved;            /* Saved line storage for unique check. */
1464   struct line const *savedline = NULL;
1465                                 /* &saved if there is a saved line. */
1466   size_t savealloc = 0;         /* Size allocated for the saved line. */
1467   struct line const *cur[NMERGE]; /* Current line in each line table. */
1468   struct line const *base[NMERGE]; /* Base of each line table.  */
1469   size_t ord[NMERGE];           /* Table representing a permutation of fps,
1470                                    such that cur[ord[0]] is the smallest line
1471                                    and will be next output. */
1472   size_t i;
1473   size_t j;
1474   size_t t;
1475   struct keyfield const *key = keylist;
1476   saved.text = NULL;
1477
1478   /* Read initial lines from each input file. */
1479   for (i = 0; i < nfiles; )
1480     {
1481       fps[i] = xfopen (files[i], "r");
1482       initbuf (&buffer[i], sizeof (struct line),
1483                MAX (merge_buffer_size, sort_size / nfiles));
1484       if (fillbuf (&buffer[i], fps[i], files[i]))
1485         {
1486           struct line const *linelim = buffer_linelim (&buffer[i]);
1487           cur[i] = linelim - 1;
1488           base[i] = linelim - buffer[i].nlines;
1489           i++;
1490         }
1491       else
1492         {
1493           /* fps[i] is empty; eliminate it from future consideration.  */
1494           xfclose (fps[i], files[i]);
1495           if (i < ntemps)
1496             {
1497               ntemps--;
1498               zaptemp (files[i]);
1499             }
1500           free (buffer[i].buf);
1501           --nfiles;
1502           for (j = i; j < nfiles; ++j)
1503             files[j] = files[j + 1];
1504         }
1505     }
1506
1507   if (! ofp)
1508     ofp = xfopen (output_file, "w");
1509
1510   /* Set up the ord table according to comparisons among input lines.
1511      Since this only reorders two items if one is strictly greater than
1512      the other, it is stable. */
1513   for (i = 0; i < nfiles; ++i)
1514     ord[i] = i;
1515   for (i = 1; i < nfiles; ++i)
1516     if (0 < compare (cur[ord[i - 1]], cur[ord[i]]))
1517       t = ord[i - 1], ord[i - 1] = ord[i], ord[i] = t, i = 0;
1518
1519   /* Repeatedly output the smallest line until no input remains. */
1520   while (nfiles)
1521     {
1522       struct line const *smallest = cur[ord[0]];
1523
1524       /* If uniquified output is turned on, output only the first of
1525          an identical series of lines. */
1526       if (unique)
1527         {
1528           if (savedline && compare (savedline, smallest))
1529             {
1530               savedline = NULL;
1531               write_bytes (saved.text, saved.length, ofp, output_file);
1532             }
1533           if (!savedline)
1534             {
1535               savedline = &saved;
1536               if (savealloc < smallest->length)
1537                 {
1538                   do
1539                     if (! savealloc)
1540                       {
1541                         savealloc = smallest->length;
1542                         break;
1543                       }
1544                   while ((savealloc *= 2) < smallest->length);
1545
1546                   saved.text = xrealloc (saved.text, savealloc);
1547                 }
1548               saved.length = smallest->length;
1549               memcpy (saved.text, smallest->text, saved.length);
1550               if (key)
1551                 {
1552                   saved.keybeg =
1553                     saved.text + (smallest->keybeg - smallest->text);
1554                   saved.keylim =
1555                     saved.text + (smallest->keylim - smallest->text);
1556                 }
1557             }
1558         }
1559       else
1560         write_bytes (smallest->text, smallest->length, ofp, output_file);
1561
1562       /* Check if we need to read more lines into core. */
1563       if (base[ord[0]] < smallest)
1564         cur[ord[0]] = smallest - 1;
1565       else
1566         {
1567           if (fillbuf (&buffer[ord[0]], fps[ord[0]], files[ord[0]]))
1568             {
1569               struct line const *linelim = buffer_linelim (&buffer[ord[0]]);
1570               cur[ord[0]] = linelim - 1;
1571               base[ord[0]] = linelim - buffer[ord[0]].nlines;
1572             }
1573           else
1574             {
1575               /* We reached EOF on fps[ord[0]].  */
1576               for (i = 1; i < nfiles; ++i)
1577                 if (ord[i] > ord[0])
1578                   --ord[i];
1579               --nfiles;
1580               xfclose (fps[ord[0]], files[ord[0]]);
1581               if (ord[0] < ntemps)
1582                 {
1583                   ntemps--;
1584                   zaptemp (files[ord[0]]);
1585                 }
1586               free (buffer[ord[0]].buf);
1587               for (i = ord[0]; i < nfiles; ++i)
1588                 {
1589                   fps[i] = fps[i + 1];
1590                   files[i] = files[i + 1];
1591                   buffer[i] = buffer[i + 1];
1592                   cur[i] = cur[i + 1];
1593                   base[i] = base[i + 1];
1594                 }
1595               for (i = 0; i < nfiles; ++i)
1596                 ord[i] = ord[i + 1];
1597               continue;
1598             }
1599         }
1600
1601       /* The new line just read in may be larger than other lines
1602          already in main memory; push it back in the queue until we
1603          encounter a line larger than it.  Optimize for the common
1604          case where the new line is smallest.  */
1605       {
1606         size_t lo = 1;
1607         size_t hi = nfiles;
1608         size_t probe = lo;
1609         size_t ord0 = ord[0];
1610         size_t count_of_smaller_lines;
1611
1612         while (lo < hi)
1613           {
1614             int cmp = compare (cur[ord0], cur[ord[probe]]);
1615             if (cmp < 0 || (cmp == 0 && ord0 < ord[probe]))
1616               hi = probe;
1617             else
1618               lo = probe + 1;
1619             probe = (lo + hi) / 2;
1620           }
1621
1622         count_of_smaller_lines = lo - 1;
1623         for (j = 0; j < count_of_smaller_lines; j++)
1624           ord[j] = ord[j + 1];
1625         ord[count_of_smaller_lines] = ord0;
1626       }
1627     }
1628
1629   if (unique && savedline)
1630     {
1631       write_bytes (saved.text, saved.length, ofp, output_file);
1632       free (saved.text);
1633     }
1634
1635   xfclose (ofp, output_file);
1636 }
1637
1638 /* Merge into T the two sorted arrays of lines LO (with NLO members)
1639    and HI (with NHI members).  T, LO, and HI point just past their
1640    respective arrays, and the arrays are in reverse order.  NLO and
1641    NHI must be positive, and HI - NHI must equal T - (NLO + NHI).  */
1642
1643 static inline void
1644 mergelines (struct line *t,
1645             struct line const *lo, size_t nlo,
1646             struct line const *hi, size_t nhi)
1647 {
1648   for (;;)
1649     if (compare (lo - 1, hi - 1) <= 0)
1650       {
1651         *--t = *--lo;
1652         if (! --nlo)
1653           {
1654             /* HI - NHI equalled T - (NLO + NHI) when this function
1655                began.  Therefore HI must equal T now, and there is no
1656                need to copy from HI to T.  */
1657             return;
1658           }
1659       }
1660     else
1661       {
1662         *--t = *--hi;
1663         if (! --nhi)
1664           {
1665             do
1666               *--t = *--lo;
1667             while (--nlo);
1668
1669             return;
1670           }
1671       }
1672 }
1673
1674 /* Sort the array LINES with NLINES members, using TEMP for temporary space.
1675    NLINES must be at least 2.
1676    The input and output arrays are in reverse order, and LINES and
1677    TEMP point just past the end of their respective arrays.
1678
1679    Use a recursive divide-and-conquer algorithm, in the style
1680    suggested by Knuth volume 3 (2nd edition), exercise 5.2.4-23.  Use
1681    the optimization suggested by exercise 5.2.4-10; this requires room
1682    for only 1.5*N lines, rather than the usual 2*N lines.  Knuth
1683    writes that this memory optimization was originally published by
1684    D. A. Bell, Comp J. 1 (1958), 75.  */
1685
1686 static void
1687 sortlines (struct line *lines, size_t nlines, struct line *temp)
1688 {
1689   if (nlines == 2)
1690     {
1691       if (0 < compare (&lines[-1], &lines[-2]))
1692         {
1693           struct line tmp = lines[-1];
1694           lines[-1] = lines[-2];
1695           lines[-2] = tmp;
1696         }
1697     }
1698   else
1699     {
1700       size_t nlo = nlines / 2;
1701       size_t nhi = nlines - nlo;
1702       struct line *lo = lines;
1703       struct line *hi = lines - nlo;
1704       struct line *sorted_lo = temp;
1705
1706       sortlines (hi, nhi, temp);
1707       if (1 < nlo)
1708         sortlines_temp (lo, nlo, sorted_lo);
1709       else
1710         sorted_lo[-1] = lo[-1];
1711
1712       mergelines (lines, sorted_lo, nlo, hi, nhi);
1713     }
1714 }
1715
1716 /* Like sortlines (LINES, NLINES, TEMP), except output into TEMP
1717    rather than sorting in place.  */
1718
1719 static void
1720 sortlines_temp (struct line *lines, size_t nlines, struct line *temp)
1721 {
1722   if (nlines == 2)
1723     {
1724       bool swap = (0 < compare (&lines[-1], &lines[-2]));
1725       temp[-1] = lines[-1 - swap];
1726       temp[-2] = lines[-2 + swap];
1727     }
1728   else
1729     {
1730       size_t nlo = nlines / 2;
1731       size_t nhi = nlines - nlo;
1732       struct line *lo = lines;
1733       struct line *hi = lines - nlo;
1734       struct line *sorted_hi = temp - nlo;
1735
1736       sortlines_temp (hi, nhi, sorted_hi);
1737       if (1 < nlo)
1738         sortlines (lo, nlo, temp);
1739
1740       mergelines (temp, lo, nlo, sorted_hi, nhi);
1741     }
1742 }
1743
1744 /* Scan through FILES[NTEMPS .. NFILES-1] looking for a file that is
1745    the same as OUTFILE.  If found, merge the found instances (and perhaps
1746    some other files) into a temporary file so that it can in turn be
1747    merged into OUTFILE without destroying OUTFILE before it is completely
1748    read.  Return the new value of NFILES, which differs from the old if
1749    some merging occurred.
1750
1751    This test ensures that an otherwise-erroneous use like
1752    "sort -m -o FILE ... FILE ..." copies FILE before writing to it.
1753    It's not clear that POSIX requires this nicety.
1754    Detect common error cases, but don't try to catch obscure cases like
1755    "cat ... FILE ... | sort -m -o FILE"
1756    where traditional "sort" doesn't copy the input and where
1757    people should know that they're getting into trouble anyway.
1758    Catching these obscure cases would slow down performance in
1759    common cases.  */
1760
1761 static size_t
1762 avoid_trashing_input (char **files, size_t ntemps, size_t nfiles,
1763                       char const *outfile)
1764 {
1765   size_t i;
1766   bool got_outstat = false;
1767   struct stat outstat;
1768
1769   for (i = ntemps; i < nfiles; i++)
1770     {
1771       bool is_stdin = STREQ (files[i], "-");
1772       bool same;
1773       struct stat instat;
1774
1775       if (outfile && STREQ (outfile, files[i]) && !is_stdin)
1776         same = true;
1777       else
1778         {
1779           if (! got_outstat)
1780             {
1781               if ((outfile
1782                    ? stat (outfile, &outstat)
1783                    : fstat (STDOUT_FILENO, &outstat))
1784                   != 0)
1785                 break;
1786               got_outstat = true;
1787             }
1788
1789           same = (((is_stdin
1790                     ? fstat (STDIN_FILENO, &instat)
1791                     : stat (files[i], &instat))
1792                    == 0)
1793                   && SAME_INODE (instat, outstat));
1794         }
1795
1796       if (same)
1797         {
1798           FILE *tftp;
1799           char *temp = create_temp_file (&tftp);
1800           mergefps (&files[i], 0, nfiles - i, tftp, temp);
1801           files[i] = temp;
1802           return i + 1;
1803         }
1804     }
1805
1806   return nfiles;
1807 }
1808
1809 /* Merge the input FILES.  NTEMPS is the number of files at the
1810    start of FILES that are temporary; it is zero at the top level.
1811    NFILES is the total number of files.  Put the output in
1812    OUTPUT_FILE; a null OUTPUT_FILE stands for standard output.  */
1813
1814 static void
1815 merge (char **files, size_t ntemps, size_t nfiles, char const *output_file)
1816 {
1817   while (NMERGE < nfiles)
1818     {
1819       /* Number of input files processed so far.  */
1820       size_t in;
1821
1822       /* Number of output files generated so far.  */
1823       size_t out;
1824
1825       /* nfiles % NMERGE; this counts input files that are left over
1826          after all full-sized merges have been done.  */
1827       size_t remainder;
1828
1829       /* Number of easily-available slots at the next loop iteration.  */
1830       size_t cheap_slots;
1831
1832       /* Do as many NMERGE-size merges as possible.  */
1833       for (out = in = 0; out < nfiles / NMERGE; out++, in += NMERGE)
1834         {
1835           FILE *tfp;
1836           char *temp = create_temp_file (&tfp);
1837           size_t nt = MIN (ntemps, NMERGE);
1838           ntemps -= nt;
1839           mergefps (&files[in], nt, NMERGE, tfp, temp);
1840           files[out] = temp;
1841         }
1842
1843       remainder = nfiles - in;
1844       cheap_slots = NMERGE - out % NMERGE;
1845
1846       if (cheap_slots < remainder)
1847         {
1848           /* So many files remain that they can't all be put into the last
1849              NMERGE-sized output window.  Do one more merge.  Merge as few
1850              files as possible, to avoid needless I/O.  */
1851           size_t nshortmerge = remainder - cheap_slots + 1;
1852           FILE *tfp;
1853           char *temp = create_temp_file (&tfp);
1854           size_t nt = MIN (ntemps, nshortmerge);
1855           ntemps -= nt;
1856           mergefps (&files[in], nt, nshortmerge, tfp, temp);
1857           files[out++] = temp;
1858           in += nshortmerge;
1859         }
1860
1861       /* Put the remaining input files into the last NMERGE-sized output
1862          window, so they will be merged in the next pass.  */
1863       memmove(&files[out], &files[in], (nfiles - in) * sizeof *files);
1864       ntemps += out;
1865       nfiles -= in - out;
1866     }
1867
1868   nfiles = avoid_trashing_input (files, ntemps, nfiles, output_file);
1869   mergefps (files, ntemps, nfiles, NULL, output_file);
1870 }
1871
1872 /* Sort NFILES FILES onto OUTPUT_FILE. */
1873
1874 static void
1875 sort (char * const *files, size_t nfiles, char const *output_file)
1876 {
1877   struct buffer buf;
1878   size_t ntemps = 0;
1879   bool output_file_created = false;
1880
1881   buf.alloc = 0;
1882
1883   while (nfiles)
1884     {
1885       char const *temp_output;
1886       char const *file = *files;
1887       FILE *fp = xfopen (file, "r");
1888       FILE *tfp;
1889       size_t bytes_per_line = (2 * sizeof (struct line)
1890                                - sizeof (struct line) / 2);
1891
1892       if (! buf.alloc)
1893         initbuf (&buf, bytes_per_line,
1894                  sort_buffer_size (&fp, 1, files, nfiles, bytes_per_line));
1895       buf.eof = false;
1896       files++;
1897       nfiles--;
1898
1899       while (fillbuf (&buf, fp, file))
1900         {
1901           struct line *line;
1902           struct line *linebase;
1903
1904           if (buf.eof && nfiles
1905               && (bytes_per_line + 1
1906                   < (buf.alloc - buf.used - bytes_per_line * buf.nlines)))
1907             {
1908               /* End of file, but there is more input and buffer room.
1909                  Concatenate the next input file; this is faster in
1910                  the usual case.  */
1911               buf.left = buf.used;
1912               break;
1913             }
1914
1915           line = buffer_linelim (&buf);
1916           linebase = line - buf.nlines;
1917           if (1 < buf.nlines)
1918             sortlines (line, buf.nlines, linebase);
1919           if (buf.eof && !nfiles && !ntemps && !buf.left)
1920             {
1921               xfclose (fp, file);
1922               tfp = xfopen (output_file, "w");
1923               temp_output = output_file;
1924               output_file_created = true;
1925             }
1926           else
1927             {
1928               ++ntemps;
1929               temp_output = create_temp_file (&tfp);
1930             }
1931
1932           do
1933             {
1934               line--;
1935               write_bytes (line->text, line->length, tfp, temp_output);
1936               if (unique)
1937                 while (linebase < line && compare (line, line - 1) == 0)
1938                   line--;
1939             }
1940           while (linebase < line);
1941
1942           xfclose (tfp, temp_output);
1943
1944           if (output_file_created)
1945             goto finish;
1946         }
1947       xfclose (fp, file);
1948     }
1949
1950  finish:
1951   free (buf.buf);
1952
1953   if (! output_file_created)
1954     {
1955       size_t i;
1956       struct tempnode *node = temphead;
1957       char **tempfiles = xnmalloc (ntemps, sizeof *tempfiles);
1958       for (i = 0; node; i++)
1959         {
1960           tempfiles[i] = node->name;
1961           node = node->next;
1962         }
1963       merge (tempfiles, ntemps, ntemps, output_file);
1964       free (tempfiles);
1965     }
1966 }
1967
1968 /* Insert key KEY at the end of the key list.  */
1969
1970 static void
1971 insertkey (struct keyfield *key)
1972 {
1973   struct keyfield **p;
1974
1975   for (p = &keylist; *p; p = &(*p)->next)
1976     continue;
1977   *p = key;
1978   key->next = NULL;
1979 }
1980
1981 /* Report a bad field specification SPEC, with extra info MSGID.  */
1982
1983 static void badfieldspec (char const *, char const *)
1984      ATTRIBUTE_NORETURN;
1985 static void
1986 badfieldspec (char const *spec, char const *msgid)
1987 {
1988   error (SORT_FAILURE, 0, _("%s: invalid field specification %s"),
1989          _(msgid), quote (spec));
1990   abort ();
1991 }
1992
1993 /* Parse the leading integer in STRING and store the resulting value
1994    (which must fit into size_t) into *VAL.  Return the address of the
1995    suffix after the integer.  If MSGID is NULL, return NULL after
1996    failure; otherwise, report MSGID and exit on failure.  */
1997
1998 static char const *
1999 parse_field_count (char const *string, size_t *val, char const *msgid)
2000 {
2001   char *suffix;
2002   uintmax_t n;
2003
2004   switch (xstrtoumax (string, &suffix, 10, &n, ""))
2005     {
2006     case LONGINT_OK:
2007     case LONGINT_INVALID_SUFFIX_CHAR:
2008       *val = n;
2009       if (*val == n)
2010         break;
2011       /* Fall through.  */
2012     case LONGINT_OVERFLOW:
2013     case LONGINT_OVERFLOW | LONGINT_INVALID_SUFFIX_CHAR:
2014       if (msgid)
2015         error (SORT_FAILURE, 0, _("%s: count `%.*s' too large"),
2016                _(msgid), (int) (suffix - string), string);
2017       return NULL;
2018
2019     case LONGINT_INVALID:
2020       if (msgid)
2021         error (SORT_FAILURE, 0, _("%s: invalid count at start of %s"),
2022                _(msgid), quote (string));
2023       return NULL;
2024     }
2025
2026   return suffix;
2027 }
2028
2029 /* Handle interrupts and hangups. */
2030
2031 static void
2032 sighandler (int sig)
2033 {
2034   if (! SA_NOCLDSTOP)
2035     signal (sig, SIG_IGN);
2036
2037   cleanup ();
2038
2039   signal (sig, SIG_DFL);
2040   raise (sig);
2041 }
2042
2043 /* Set the ordering options for KEY specified in S.
2044    Return the address of the first character in S that
2045    is not a valid ordering option.
2046    BLANKTYPE is the kind of blanks that 'b' should skip. */
2047
2048 static char *
2049 set_ordering (const char *s, struct keyfield *key, enum blanktype blanktype)
2050 {
2051   while (*s)
2052     {
2053       switch (*s)
2054         {
2055         case 'b':
2056           if (blanktype == bl_start || blanktype == bl_both)
2057             key->skipsblanks = true;
2058           if (blanktype == bl_end || blanktype == bl_both)
2059             key->skipeblanks = true;
2060           break;
2061         case 'd':
2062           key->ignore = nondictionary;
2063           break;
2064         case 'f':
2065           key->translate = fold_toupper;
2066           break;
2067         case 'g':
2068           key->general_numeric = true;
2069           break;
2070         case 'i':
2071           /* Option order should not matter, so don't let -i override
2072              -d.  -d implies -i, but -i does not imply -d.  */
2073           if (! key->ignore)
2074             key->ignore = nonprinting;
2075           break;
2076         case 'M':
2077           key->month = true;
2078           break;
2079         case 'n':
2080           key->numeric = true;
2081           break;
2082         case 'r':
2083           key->reverse = true;
2084           break;
2085         default:
2086           return (char *) s;
2087         }
2088       ++s;
2089     }
2090   return (char *) s;
2091 }
2092
2093 static struct keyfield *
2094 new_key (void)
2095 {
2096   struct keyfield *key = xzalloc (sizeof *key);
2097   key->eword = SIZE_MAX;
2098   return key;
2099 }
2100
2101 int
2102 main (int argc, char **argv)
2103 {
2104   struct keyfield *key;
2105   struct keyfield gkey;
2106   char const *s;
2107   int c = 0;
2108   bool checkonly = false;
2109   bool mergeonly = false;
2110   size_t nfiles = 0;
2111   bool posixly_correct = (getenv ("POSIXLY_CORRECT") != NULL);
2112   bool obsolete_usage = (posix2_version () < 200112);
2113   char *minus = "-", **files;
2114   char const *outfile = NULL;
2115
2116   initialize_main (&argc, &argv);
2117   program_name = argv[0];
2118   setlocale (LC_ALL, "");
2119   bindtextdomain (PACKAGE, LOCALEDIR);
2120   textdomain (PACKAGE);
2121
2122   atexit (cleanup);
2123
2124   initialize_exit_failure (SORT_FAILURE);
2125   atexit (close_stdout);
2126
2127   hard_LC_COLLATE = hard_locale (LC_COLLATE);
2128 #if HAVE_NL_LANGINFO
2129   hard_LC_TIME = hard_locale (LC_TIME);
2130 #endif
2131
2132   /* Get locale's representation of the decimal point.  */
2133   {
2134     struct lconv const *locale = localeconv ();
2135
2136     /* If the locale doesn't define a decimal point, or if the decimal
2137        point is multibyte, use the C locale's decimal point.  FIXME:
2138        add support for multibyte decimal points.  */
2139     decimal_point = to_uchar (locale->decimal_point[0]);
2140     if (! decimal_point || locale->decimal_point[1])
2141       decimal_point = '.';
2142
2143     /* FIXME: add support for multibyte thousands separators.  */
2144     thousands_sep = to_uchar (*locale->thousands_sep);
2145     if (! thousands_sep || locale->thousands_sep[1])
2146       thousands_sep = -1;
2147   }
2148
2149   have_read_stdin = false;
2150   inittables ();
2151
2152   {
2153     size_t i;
2154     static int const sig[] = { SIGHUP, SIGINT, SIGPIPE, SIGTERM };
2155     enum { nsigs = sizeof sig / sizeof sig[0] };
2156
2157 #if SA_NOCLDSTOP
2158     struct sigaction act;
2159
2160     sigemptyset (&caught_signals);
2161     for (i = 0; i < nsigs; i++)
2162       {
2163         sigaction (sig[i], NULL, &act);
2164         if (act.sa_handler != SIG_IGN)
2165           sigaddset (&caught_signals, sig[i]);
2166       }
2167
2168     act.sa_handler = sighandler;
2169     act.sa_mask = caught_signals;
2170     act.sa_flags = 0;
2171
2172     for (i = 0; i < nsigs; i++)
2173       if (sigismember (&caught_signals, sig[i]))
2174         sigaction (sig[i], &act, NULL);
2175 #else
2176     for (i = 0; i < nsigs; i++)
2177       if (signal (sig[i], SIG_IGN) != SIG_IGN)
2178         {
2179           signal (sig[i], sighandler);
2180           siginterrupt (sig[i], 1);
2181         }
2182 #endif
2183   }
2184
2185   gkey.sword = gkey.eword = SIZE_MAX;
2186   gkey.ignore = NULL;
2187   gkey.translate = NULL;
2188   gkey.numeric = gkey.general_numeric = gkey.month = gkey.reverse = false;
2189   gkey.skipsblanks = gkey.skipeblanks = false;
2190
2191   files = xnmalloc (argc, sizeof *files);
2192
2193   for (;;)
2194     {
2195       /* Parse an operand as a file after "--" was seen; or if
2196          pedantic and a file was seen, unless the POSIX version
2197          predates 1003.1-2001 and -c was not seen and the operand is
2198          "-o FILE" or "-oFILE".  */
2199
2200       if (c == -1
2201           || (posixly_correct && nfiles != 0
2202               && ! (obsolete_usage
2203                     && ! checkonly
2204                     && optind != argc
2205                     && argv[optind][0] == '-' && argv[optind][1] == 'o'
2206                     && (argv[optind][2] || optind + 1 != argc)))
2207           || ((c = getopt_long (argc, argv, short_options,
2208                                 long_options, NULL))
2209               == -1))
2210         {
2211           if (argc <= optind)
2212             break;
2213           files[nfiles++] = argv[optind++];
2214         }
2215       else switch (c)
2216         {
2217         case 1:
2218           key = NULL;
2219           if (obsolete_usage && optarg[0] == '+')
2220             {
2221               /* Treat +POS1 [-POS2] as a key if possible; but silently
2222                  treat an operand as a file if it is not a valid +POS1.  */
2223               key = new_key ();
2224               s = parse_field_count (optarg + 1, &key->sword, NULL);
2225               if (s && *s == '.')
2226                 s = parse_field_count (s + 1, &key->schar, NULL);
2227               if (! (key->sword | key->schar))
2228                 key->sword = SIZE_MAX;
2229               if (! s || *set_ordering (s, key, bl_start))
2230                 {
2231                   free (key);
2232                   key = NULL;
2233                 }
2234               else
2235                 {
2236                   if (optind != argc && argv[optind][0] == '-'
2237                       && ISDIGIT (argv[optind][1]))
2238                     {
2239                       char const *optarg1 = argv[optind++];
2240                       s = parse_field_count (optarg1 + 1, &key->eword,
2241                                              N_("invalid number after `-'"));
2242                       if (*s == '.')
2243                         s = parse_field_count (s + 1, &key->echar,
2244                                                N_("invalid number after `.'"));
2245                       if (*set_ordering (s, key, bl_end))
2246                         badfieldspec (optarg1,
2247                                       N_("stray character in field spec"));
2248                     }
2249                   insertkey (key);
2250                 }
2251             }
2252           if (! key)
2253             files[nfiles++] = optarg;
2254           break;
2255
2256         case 'b':
2257         case 'd':
2258         case 'f':
2259         case 'g':
2260         case 'i':
2261         case 'M':
2262         case 'n':
2263         case 'r':
2264           {
2265             char str[2];
2266             str[0] = c;
2267             str[1] = '\0';
2268             set_ordering (str, &gkey, bl_both);
2269           }
2270           break;
2271
2272         case 'c':
2273           checkonly = true;
2274           break;
2275
2276         case 'k':
2277           key = new_key ();
2278
2279           /* Get POS1. */
2280           s = parse_field_count (optarg, &key->sword,
2281                                  N_("invalid number at field start"));
2282           if (! key->sword--)
2283             {
2284               /* Provoke with `sort -k0' */
2285               badfieldspec (optarg, N_("field number is zero"));
2286             }
2287           if (*s == '.')
2288             {
2289               s = parse_field_count (s + 1, &key->schar,
2290                                      N_("invalid number after `.'"));
2291               if (! key->schar--)
2292                 {
2293                   /* Provoke with `sort -k1.0' */
2294                   badfieldspec (optarg, N_("character offset is zero"));
2295                 }
2296             }
2297           if (! (key->sword | key->schar))
2298             key->sword = SIZE_MAX;
2299           s = set_ordering (s, key, bl_start);
2300           if (*s != ',')
2301             {
2302               key->eword = SIZE_MAX;
2303               key->echar = 0;
2304             }
2305           else
2306             {
2307               /* Get POS2. */
2308               s = parse_field_count (s + 1, &key->eword,
2309                                      N_("invalid number after `,'"));
2310               if (! key->eword--)
2311                 {
2312                   /* Provoke with `sort -k1,0' */
2313                   badfieldspec (optarg, N_("field number is zero"));
2314                 }
2315               if (*s == '.')
2316                 s = parse_field_count (s + 1, &key->echar,
2317                                        N_("invalid number after `.'"));
2318               else
2319                 {
2320                   /* `-k 2,3' is equivalent to `+1 -3'.  */
2321                   key->eword++;
2322                 }
2323               s = set_ordering (s, key, bl_end);
2324             }
2325           if (*s)
2326             badfieldspec (optarg, N_("stray character in field spec"));
2327           insertkey (key);
2328           break;
2329
2330         case 'm':
2331           mergeonly = true;
2332           break;
2333
2334         case 'o':
2335           if (outfile && !STREQ (outfile, optarg))
2336             error (SORT_FAILURE, 0, _("multiple output files specified"));
2337           outfile = optarg;
2338           break;
2339
2340         case 's':
2341           stable = true;
2342           break;
2343
2344         case 'S':
2345           specify_sort_size (optarg);
2346           break;
2347
2348         case 't':
2349           {
2350             char newtab = optarg[0];
2351             if (! newtab)
2352               error (SORT_FAILURE, 0, _("empty tab"));
2353             if (optarg[1])
2354               {
2355                 if (STREQ (optarg, "\\0"))
2356                   newtab = '\0';
2357                 else
2358                   {
2359                     /* Provoke with `sort -txx'.  Complain about
2360                        "multi-character tab" instead of "multibyte tab", so
2361                        that the diagnostic's wording does not need to be
2362                        changed once multibyte characters are supported.  */
2363                     error (SORT_FAILURE, 0, _("multi-character tab %s"),
2364                            quote (optarg));
2365                   }
2366               }
2367             if (tab != TAB_DEFAULT && tab != newtab)
2368               error (SORT_FAILURE, 0, _("incompatible tabs"));
2369             tab = newtab;
2370           }
2371           break;
2372
2373         case 'T':
2374           add_temp_dir (optarg);
2375           break;
2376
2377         case 'u':
2378           unique = true;
2379           break;
2380
2381         case 'y':
2382           /* Accept and ignore e.g. -y0 for compatibility with Solaris 2.x
2383              through Solaris 7.  It is also accepted by many non-Solaris
2384              "sort" implementations, e.g., AIX 5.2, HP-UX 11i v2, IRIX 6.5.
2385              -y is marked as obsolete starting with Solaris 8 (1999), but is
2386              still accepted as of Solaris 10 prerelease (2004).
2387
2388              Solaris 2.5.1 "sort -y 100" reads the input file "100", but
2389              emulate Solaris 8 and 9 "sort -y 100" which ignores the "100",
2390              and which in general ignores the argument after "-y" if it
2391              consists entirely of digits (it can even be empty).  */
2392           if (optarg == argv[optind - 1])
2393             {
2394               char const *p;
2395               for (p = optarg; ISDIGIT (*p); p++)
2396                 continue;
2397               optind -= (*p != '\0');
2398             }
2399           break;
2400
2401         case 'z':
2402           eolchar = 0;
2403           break;
2404
2405         case_GETOPT_HELP_CHAR;
2406
2407         case_GETOPT_VERSION_CHAR (PROGRAM_NAME, AUTHORS);
2408
2409         default:
2410           usage (SORT_FAILURE);
2411         }
2412     }
2413
2414   /* Inheritance of global options to individual keys. */
2415   for (key = keylist; key; key = key->next)
2416     if (! (key->ignore || key->translate
2417            || (key->skipsblanks | key->reverse
2418                | key->skipeblanks | key->month | key->numeric
2419                | key->general_numeric)))
2420       {
2421         key->ignore = gkey.ignore;
2422         key->translate = gkey.translate;
2423         key->skipsblanks = gkey.skipsblanks;
2424         key->skipeblanks = gkey.skipeblanks;
2425         key->month = gkey.month;
2426         key->numeric = gkey.numeric;
2427         key->general_numeric = gkey.general_numeric;
2428         key->reverse = gkey.reverse;
2429       }
2430
2431   if (!keylist && (gkey.ignore || gkey.translate
2432                    || (gkey.skipsblanks | gkey.skipeblanks | gkey.month
2433                        | gkey.numeric | gkey.general_numeric)))
2434     insertkey (&gkey);
2435   reverse = gkey.reverse;
2436
2437   if (temp_dir_count == 0)
2438     {
2439       char const *tmp_dir = getenv ("TMPDIR");
2440       add_temp_dir (tmp_dir ? tmp_dir : DEFAULT_TMPDIR);
2441     }
2442
2443   if (nfiles == 0)
2444     {
2445       nfiles = 1;
2446       files = &minus;
2447     }
2448
2449   if (checkonly)
2450     {
2451       if (nfiles > 1)
2452         {
2453           error (0, 0, _("extra operand %s not allowed with -c"),
2454                  quote (files[1]));
2455           usage (SORT_FAILURE);
2456         }
2457
2458       /* POSIX requires that sort return 1 IFF invoked with -c and the
2459          input is not properly sorted.  */
2460       exit (check (files[0]) ? EXIT_SUCCESS : SORT_OUT_OF_ORDER);
2461     }
2462
2463   if (mergeonly)
2464     merge (files, 0, nfiles, outfile);
2465   else
2466     sort (files, nfiles, outfile);
2467
2468   if (have_read_stdin && fclose (stdin) == EOF)
2469     die (_("close failed"), "-");
2470
2471   exit (EXIT_SUCCESS);
2472 }