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 "system.h"
  30 #include "error.h"
  31 #include "hard-locale.h"
  32 #include "inttostr.h"
  33 #include "physmem.h"
  34 #include "posixver.h"
  35 #include "quote.h"
  36 #include "stdlib--.h"
  37 #include "stdio--.h"
  38 #include "strnumcmp.h"
  39 #include "xmemcoll.h"
  40 #include "xstrtol.h"
  41
  42 #if HAVE_SYS_RESOURCE_H
  43 # include <sys/resource.h>
  44 #endif
  45 #ifndef RLIMIT_DATA
  46 struct rlimit { size_t rlim_cur; };
  47 # define getrlimit(Resource, Rlp) (-1)
  48 #endif
  49
  50 /* The official name of this program (e.g., no `g' prefix).  */
  51 #define PROGRAM_NAME "sort"
  52
  53 #define AUTHORS "Mike Haertel", "Paul Eggert"
  54
  55 #if HAVE_LANGINFO_CODESET
  56 # include <langinfo.h>
  57 #endif
  58
  59 /* Use SA_NOCLDSTOP as a proxy for whether the sigaction machinery is
  60    present.  */
  61 #ifndef SA_NOCLDSTOP
  62 # define SA_NOCLDSTOP 0
  63 # define sigprocmask(How, Set, Oset) /* empty */
  64 # define sigset_t int
  65 # if ! HAVE_SIGINTERRUPT
  66 #  define siginterrupt(sig, flag) /* empty */
  67 # endif
  68 #endif
  69
  70 #ifndef STDC_HEADERS
  71 double strtod ();
  72 #endif
  73
  74 #define UCHAR_LIM (UCHAR_MAX + 1)
  75
  76 #ifndef DEFAULT_TMPDIR
  77 # define DEFAULT_TMPDIR "/tmp"
  78 #endif
  79
  80 /* Exit statuses.  */
  81 enum
  82   {
  83     /* POSIX says to exit with status 1 if invoked with -c and the
  84        input is not properly sorted.  */
  85     SORT_OUT_OF_ORDER = 1,
  86
  87     /* POSIX says any other irregular exit must exit with a status
  88        code greater than 1.  */
  89     SORT_FAILURE = 2
  90   };
  91
  92 /* The representation of the decimal point in the current locale.  */
  93 static int decimal_point;
  94
  95 /* Thousands separator; if -1, then there isn't one.  */
  96 static int thousands_sep;
  97
  98 /* Nonzero if the corresponding locales are hard.  */
  99 static bool hard_LC_COLLATE;
 100 #if HAVE_NL_LANGINFO
 101 static bool hard_LC_TIME;
 102 #endif
 103
 104 #define NONZERO(x) ((x) != 0)
 105
 106 /* The kind of blanks for '-b' to skip in various options. */
 107 enum blanktype { bl_start, bl_end, bl_both };
 108
 109 /* The character marking end of line. Default to \n. */
 110 static char eolchar = '\n';
 111
 112 /* Lines are held in core as counted strings. */
 113 struct line
 114 {
 115   char *text;                   /* Text of the line. */
 116   size_t length;                /* Length including final newline. */
 117   char *keybeg;                 /* Start of first key. */
 118   char *keylim;                 /* Limit of first key. */
 119 };
 120
 121 /* Input buffers. */
 122 struct buffer
 123 {
 124   char *buf;                    /* Dynamically allocated buffer,
 125                                    partitioned into 3 regions:
 126                                    - input data;
 127                                    - unused area;
 128                                    - an array of lines, in reverse order.  */
 129   size_t used;                  /* Number of bytes used for input data.  */
 130   size_t nlines;                /* Number of lines in the line array.  */
 131   size_t alloc;                 /* Number of bytes allocated. */
 132   size_t left;                  /* Number of bytes left from previous reads. */
 133   size_t line_bytes;            /* Number of bytes to reserve for each line. */
 134   bool eof;                     /* An EOF has been read.  */
 135 };
 136
 137 struct keyfield
 138 {
 139   size_t sword;                 /* Zero-origin 'word' to start at. */
 140   size_t schar;                 /* Additional characters to skip. */
 141   size_t eword;                 /* Zero-origin first word after field. */
 142   size_t echar;                 /* Additional characters in field. */
 143   bool const *ignore;           /* Boolean array of characters to ignore. */
 144   char const *translate;        /* Translation applied to characters. */
 145   bool skipsblanks;             /* Skip leading blanks when finding start.  */
 146   bool skipeblanks;             /* Skip leading blanks when finding end.  */
 147   bool numeric;                 /* Flag for numeric comparison.  Handle
 148                                    strings of digits with optional decimal
 149                                    point, but no exponential notation. */
 150   bool general_numeric;         /* Flag for general, numeric comparison.
 151                                    Handle numbers in exponential notation. */
 152   bool month;                   /* Flag for comparison by month name. */
 153   bool reverse;                 /* Reverse the sense of comparison. */
 154   struct keyfield *next;        /* Next keyfield to try. */
 155 };
 156
 157 struct month
 158 {
 159   char const *name;
 160   int val;
 161 };
 162
 163 /* The name this program was run with. */
 164 char *program_name;
 165
 166 /* FIXME: None of these tables work with multibyte character sets.
 167    Also, there are many other bugs when handling multibyte characters.
 168    One way to fix this is to rewrite `sort' to use wide characters
 169    internally, but doing this with good performance is a bit
 170    tricky.  */
 171
 172 /* Table of blanks.  */
 173 static bool blanks[UCHAR_LIM];
 174
 175 /* Table of non-printing characters. */
 176 static bool nonprinting[UCHAR_LIM];
 177
 178 /* Table of non-dictionary characters (not letters, digits, or blanks). */
 179 static bool nondictionary[UCHAR_LIM];
 180
 181 /* Translation table folding lower case to upper.  */
 182 static char fold_toupper[UCHAR_LIM];
 183
 184 #define MONTHS_PER_YEAR 12
 185
 186 /* Table mapping month names to integers.
 187    Alphabetic order allows binary search. */
 188 static struct month monthtab[] =
 189 {
 190   {"APR", 4},
 191   {"AUG", 8},
 192   {"DEC", 12},
 193   {"FEB", 2},
 194   {"JAN", 1},
 195   {"JUL", 7},
 196   {"JUN", 6},
 197   {"MAR", 3},
 198   {"MAY", 5},
 199   {"NOV", 11},
 200   {"OCT", 10},
 201   {"SEP", 9}
 202 };
 203
 204 /* During the merge phase, the number of files to merge at once. */
 205 #define NMERGE 16
 206
 207 /* Minimum size for a merge or check buffer.  */
 208 #define MIN_MERGE_BUFFER_SIZE (2 + sizeof (struct line))
 209
 210 /* Minimum sort size; the code might not work with smaller sizes.  */
 211 #define MIN_SORT_SIZE (NMERGE * MIN_MERGE_BUFFER_SIZE)
 212
 213 /* The number of bytes needed for a merge or check buffer, which can
 214    function relatively efficiently even if it holds only one line.  If
 215    a longer line is seen, this value is increased.  */
 216 static size_t merge_buffer_size = MAX (MIN_MERGE_BUFFER_SIZE, 256 * 1024);
 217
 218 /* The approximate maximum number of bytes of main memory to use, as
 219    specified by the user.  Zero if the user has not specified a size.  */
 220 static size_t sort_size;
 221
 222 /* The guessed size for non-regular files.  */
 223 #define INPUT_FILE_SIZE_GUESS (1024 * 1024)
 224
 225 /* Array of directory names in which any temporary files are to be created. */
 226 static char const **temp_dirs;
 227
 228 /* Number of temporary directory names used.  */
 229 static size_t temp_dir_count;
 230
 231 /* Number of allocated slots in temp_dirs.  */
 232 static size_t temp_dir_alloc;
 233
 234 /* Flag to reverse the order of all comparisons. */
 235 static bool reverse;
 236
 237 /* Flag for stable sort.  This turns off the last ditch bytewise
 238    comparison of lines, and instead leaves lines in the same order
 239    they were read if all keys compare equal.  */
 240 static bool stable;
 241
 242 /* If TAB has this value, blanks separate fields.  */
 243 enum { TAB_DEFAULT = CHAR_MAX + 1 };
 244
 245 /* Tab character separating fields.  If TAB_DEFAULT, then fields are
 246    separated by the empty string between a non-blank character and a blank
 247    character. */
 248 static int tab = TAB_DEFAULT;
 249
 250 /* Flag to remove consecutive duplicate lines from the output.
 251    Only the last of a sequence of equal lines will be output. */
 252 static bool unique;
 253
 254 /* Nonzero if any of the input files are the standard input. */
 255 static bool have_read_stdin;
 256
 257 /* List of key field comparisons to be tried.  */
 258 static struct keyfield *keylist;
 259
 260 static void sortlines_temp (struct line *, size_t, struct line *);
 261
 262 /* Report MESSAGE for FILE, then clean up and exit.
 263    If FILE is null, it represents standard output.  */
 264
 265 static void die (char const *, char const *) ATTRIBUTE_NORETURN;
 266 static void
 267 die (char const *message, char const *file)
 268 {
 269   error (0, errno, "%s: %s", message, file ? file : _("standard output"));
 270   exit (SORT_FAILURE);
 271 }
 272
 273 void
 274 usage (int status)
 275 {
 276   if (status != EXIT_SUCCESS)
 277     fprintf (stderr, _("Try `%s --help' for more information.\n"),
 278              program_name);
 279   else
 280     {
 281       printf (_("\
 282 Usage: %s [OPTION]... [FILE]...\n\
 283 "),
 284               program_name);
 285       fputs (_("\
 286 Write sorted concatenation of all FILE(s) to standard output.\n\
 287 \n\
 288 "), stdout);
 289       fputs (_("\
 290 Mandatory arguments to long options are mandatory for short options too.\n\
 291 "), stdout);
 292       fputs (_("\
 293 Ordering options:\n\
 294 \n\
 295 "), stdout);
 296       fputs (_("\
 297   -b, --ignore-leading-blanks  ignore leading blanks\n\
 298   -d, --dictionary-order      consider only blanks and alphanumeric characters\n\
 299   -f, --ignore-case           fold lower case to upper case characters\n\
 300 "), stdout);
 301       fputs (_("\
 302   -g, --general-numeric-sort  compare according to general numerical value\n\
 303   -i, --ignore-nonprinting    consider only printable characters\n\
 304   -M, --month-sort            compare (unknown) < `JAN' < ... < `DEC'\n\
 305   -n, --numeric-sort          compare according to string numerical value\n\
 306   -r, --reverse               reverse the result of comparisons\n\
 307 \n\
 308 "), stdout);
 309       fputs (_("\
 310 Other options:\n\
 311 \n\
 312   -c, --check               check whether input is sorted; do not sort\n\
 313   -k, --key=POS1[,POS2]     start a key at POS1, end it at POS2 (origin 1)\n\
 314   -m, --merge               merge already sorted files; do not sort\n\
 315   -o, --output=FILE         write result to FILE instead of standard output\n\
 316   -s, --stable              stabilize sort by disabling last-resort comparison\n\
 317   -S, --buffer-size=SIZE    use SIZE for main memory buffer\n\
 318 "), stdout);
 319       printf (_("\
 320   -t, --field-separator=SEP  use SEP instead of non-blank to blank transition\n\
 321   -T, --temporary-directory=DIR  use DIR for temporaries, not $TMPDIR or %s;\n\
 322                               multiple options specify multiple directories\n\
 323   -u, --unique              with -c, check for strict ordering;\n\
 324                               without -c, output only the first of an equal run\n\
 325 "), DEFAULT_TMPDIR);
 326       fputs (_("\
 327   -z, --zero-terminated     end lines with 0 byte, not newline\n\
 328 "), stdout);
 329       fputs (HELP_OPTION_DESCRIPTION, stdout);
 330       fputs (VERSION_OPTION_DESCRIPTION, stdout);
 331       fputs (_("\
 332 \n\
 333 POS is F[.C][OPTS], where F is the field number and C the character position\n\
 334 in the field.  If neither the -t nor the -b option is in effect, the characters\n\
 335 in a field are counted from the beginning of the preceding whitespace.  OPTS is\n\
 336 one or more single-letter ordering options, which override global ordering\n\
 337 options for that key.  If no key is given, use the 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);
 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 the size bound specified by the user
 709    (or a default size bound, if the user does not specify one).  */
 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       /* Declare `swap' as int, not bool, to work around a bug
1725          <http://lists.gnu.org/archive/html/bug-coreutils/2005-10/msg00086.html>
1726          in the IBM xlc 6.0.0.0 compiler in 64-bit mode.  */
1727       int swap = (0 < compare (&lines[-1], &lines[-2]));
1728       temp[-1] = lines[-1 - swap];
1729       temp[-2] = lines[-2 + swap];
1730     }
1731   else
1732     {
1733       size_t nlo = nlines / 2;
1734       size_t nhi = nlines - nlo;
1735       struct line *lo = lines;
1736       struct line *hi = lines - nlo;
1737       struct line *sorted_hi = temp - nlo;
1738
1739       sortlines_temp (hi, nhi, sorted_hi);
1740       if (1 < nlo)
1741         sortlines (lo, nlo, temp);
1742
1743       mergelines (temp, lo, nlo, sorted_hi, nhi);
1744     }
1745 }
1746
1747 /* Scan through FILES[NTEMPS .. NFILES-1] looking for a file that is
1748    the same as OUTFILE.  If found, merge the found instances (and perhaps
1749    some other files) into a temporary file so that it can in turn be
1750    merged into OUTFILE without destroying OUTFILE before it is completely
1751    read.  Return the new value of NFILES, which differs from the old if
1752    some merging occurred.
1753
1754    This test ensures that an otherwise-erroneous use like
1755    "sort -m -o FILE ... FILE ..." copies FILE before writing to it.
1756    It's not clear that POSIX requires this nicety.
1757    Detect common error cases, but don't try to catch obscure cases like
1758    "cat ... FILE ... | sort -m -o FILE"
1759    where traditional "sort" doesn't copy the input and where
1760    people should know that they're getting into trouble anyway.
1761    Catching these obscure cases would slow down performance in
1762    common cases.  */
1763
1764 static size_t
1765 avoid_trashing_input (char **files, size_t ntemps, size_t nfiles,
1766                       char const *outfile)
1767 {
1768   size_t i;
1769   bool got_outstat = false;
1770   struct stat outstat;
1771
1772   for (i = ntemps; i < nfiles; i++)
1773     {
1774       bool is_stdin = STREQ (files[i], "-");
1775       bool same;
1776       struct stat instat;
1777
1778       if (outfile && STREQ (outfile, files[i]) && !is_stdin)
1779         same = true;
1780       else
1781         {
1782           if (! got_outstat)
1783             {
1784               if ((outfile
1785                    ? stat (outfile, &outstat)
1786                    : fstat (STDOUT_FILENO, &outstat))
1787                   != 0)
1788                 break;
1789               got_outstat = true;
1790             }
1791
1792           same = (((is_stdin
1793                     ? fstat (STDIN_FILENO, &instat)
1794                     : stat (files[i], &instat))
1795                    == 0)
1796                   && SAME_INODE (instat, outstat));
1797         }
1798
1799       if (same)
1800         {
1801           FILE *tftp;
1802           char *temp = create_temp_file (&tftp);
1803           mergefps (&files[i], 0, nfiles - i, tftp, temp);
1804           files[i] = temp;
1805           return i + 1;
1806         }
1807     }
1808
1809   return nfiles;
1810 }
1811
1812 /* Merge the input FILES.  NTEMPS is the number of files at the
1813    start of FILES that are temporary; it is zero at the top level.
1814    NFILES is the total number of files.  Put the output in
1815    OUTPUT_FILE; a null OUTPUT_FILE stands for standard output.  */
1816
1817 static void
1818 merge (char **files, size_t ntemps, size_t nfiles, char const *output_file)
1819 {
1820   while (NMERGE < nfiles)
1821     {
1822       /* Number of input files processed so far.  */
1823       size_t in;
1824
1825       /* Number of output files generated so far.  */
1826       size_t out;
1827
1828       /* nfiles % NMERGE; this counts input files that are left over
1829          after all full-sized merges have been done.  */
1830       size_t remainder;
1831
1832       /* Number of easily-available slots at the next loop iteration.  */
1833       size_t cheap_slots;
1834
1835       /* Do as many NMERGE-size merges as possible.  */
1836       for (out = in = 0; out < nfiles / NMERGE; out++, in += NMERGE)
1837         {
1838           FILE *tfp;
1839           char *temp = create_temp_file (&tfp);
1840           size_t nt = MIN (ntemps, NMERGE);
1841           ntemps -= nt;
1842           mergefps (&files[in], nt, NMERGE, tfp, temp);
1843           files[out] = temp;
1844         }
1845
1846       remainder = nfiles - in;
1847       cheap_slots = NMERGE - out % NMERGE;
1848
1849       if (cheap_slots < remainder)
1850         {
1851           /* So many files remain that they can't all be put into the last
1852              NMERGE-sized output window.  Do one more merge.  Merge as few
1853              files as possible, to avoid needless I/O.  */
1854           size_t nshortmerge = remainder - cheap_slots + 1;
1855           FILE *tfp;
1856           char *temp = create_temp_file (&tfp);
1857           size_t nt = MIN (ntemps, nshortmerge);
1858           ntemps -= nt;
1859           mergefps (&files[in], nt, nshortmerge, tfp, temp);
1860           files[out++] = temp;
1861           in += nshortmerge;
1862         }
1863
1864       /* Put the remaining input files into the last NMERGE-sized output
1865          window, so they will be merged in the next pass.  */
1866       memmove(&files[out], &files[in], (nfiles - in) * sizeof *files);
1867       ntemps += out;
1868       nfiles -= in - out;
1869     }
1870
1871   nfiles = avoid_trashing_input (files, ntemps, nfiles, output_file);
1872   mergefps (files, ntemps, nfiles, NULL, output_file);
1873 }
1874
1875 /* Sort NFILES FILES onto OUTPUT_FILE. */
1876
1877 static void
1878 sort (char * const *files, size_t nfiles, char const *output_file)
1879 {
1880   struct buffer buf;
1881   size_t ntemps = 0;
1882   bool output_file_created = false;
1883
1884   buf.alloc = 0;
1885
1886   while (nfiles)
1887     {
1888       char const *temp_output;
1889       char const *file = *files;
1890       FILE *fp = xfopen (file, "r");
1891       FILE *tfp;
1892       size_t bytes_per_line = (2 * sizeof (struct line)
1893                                - sizeof (struct line) / 2);
1894
1895       if (! buf.alloc)
1896         initbuf (&buf, bytes_per_line,
1897                  sort_buffer_size (&fp, 1, files, nfiles, bytes_per_line));
1898       buf.eof = false;
1899       files++;
1900       nfiles--;
1901
1902       while (fillbuf (&buf, fp, file))
1903         {
1904           struct line *line;
1905           struct line *linebase;
1906
1907           if (buf.eof && nfiles
1908               && (bytes_per_line + 1
1909                   < (buf.alloc - buf.used - bytes_per_line * buf.nlines)))
1910             {
1911               /* End of file, but there is more input and buffer room.
1912                  Concatenate the next input file; this is faster in
1913                  the usual case.  */
1914               buf.left = buf.used;
1915               break;
1916             }
1917
1918           line = buffer_linelim (&buf);
1919           linebase = line - buf.nlines;
1920           if (1 < buf.nlines)
1921             sortlines (line, buf.nlines, linebase);
1922           if (buf.eof && !nfiles && !ntemps && !buf.left)
1923             {
1924               xfclose (fp, file);
1925               tfp = xfopen (output_file, "w");
1926               temp_output = output_file;
1927               output_file_created = true;
1928             }
1929           else
1930             {
1931               ++ntemps;
1932               temp_output = create_temp_file (&tfp);
1933             }
1934
1935           do
1936             {
1937               line--;
1938               write_bytes (line->text, line->length, tfp, temp_output);
1939               if (unique)
1940                 while (linebase < line && compare (line, line - 1) == 0)
1941                   line--;
1942             }
1943           while (linebase < line);
1944
1945           xfclose (tfp, temp_output);
1946
1947           if (output_file_created)
1948             goto finish;
1949         }
1950       xfclose (fp, file);
1951     }
1952
1953  finish:
1954   free (buf.buf);
1955
1956   if (! output_file_created)
1957     {
1958       size_t i;
1959       struct tempnode *node = temphead;
1960       char **tempfiles = xnmalloc (ntemps, sizeof *tempfiles);
1961       for (i = 0; node; i++)
1962         {
1963           tempfiles[i] = node->name;
1964           node = node->next;
1965         }
1966       merge (tempfiles, ntemps, ntemps, output_file);
1967       free (tempfiles);
1968     }
1969 }
1970
1971 /* Insert key KEY at the end of the key list.  */
1972
1973 static void
1974 insertkey (struct keyfield *key)
1975 {
1976   struct keyfield **p;
1977
1978   for (p = &keylist; *p; p = &(*p)->next)
1979     continue;
1980   *p = key;
1981   key->next = NULL;
1982 }
1983
1984 /* Report a bad field specification SPEC, with extra info MSGID.  */
1985
1986 static void badfieldspec (char const *, char const *)
1987      ATTRIBUTE_NORETURN;
1988 static void
1989 badfieldspec (char const *spec, char const *msgid)
1990 {
1991   error (SORT_FAILURE, 0, _("%s: invalid field specification %s"),
1992          _(msgid), quote (spec));
1993   abort ();
1994 }
1995
1996 /* Parse the leading integer in STRING and store the resulting value
1997    (which must fit into size_t) into *VAL.  Return the address of the
1998    suffix after the integer.  If MSGID is NULL, return NULL after
1999    failure; otherwise, report MSGID and exit on failure.  */
2000
2001 static char const *
2002 parse_field_count (char const *string, size_t *val, char const *msgid)
2003 {
2004   char *suffix;
2005   uintmax_t n;
2006
2007   switch (xstrtoumax (string, &suffix, 10, &n, ""))
2008     {
2009     case LONGINT_OK:
2010     case LONGINT_INVALID_SUFFIX_CHAR:
2011       *val = n;
2012       if (*val == n)
2013         break;
2014       /* Fall through.  */
2015     case LONGINT_OVERFLOW:
2016     case LONGINT_OVERFLOW | LONGINT_INVALID_SUFFIX_CHAR:
2017       if (msgid)
2018         error (SORT_FAILURE, 0, _("%s: count `%.*s' too large"),
2019                _(msgid), (int) (suffix - string), string);
2020       return NULL;
2021
2022     case LONGINT_INVALID:
2023       if (msgid)
2024         error (SORT_FAILURE, 0, _("%s: invalid count at start of %s"),
2025                _(msgid), quote (string));
2026       return NULL;
2027     }
2028
2029   return suffix;
2030 }
2031
2032 /* Handle interrupts and hangups. */
2033
2034 static void
2035 sighandler (int sig)
2036 {
2037   if (! SA_NOCLDSTOP)
2038     signal (sig, SIG_IGN);
2039
2040   cleanup ();
2041
2042   signal (sig, SIG_DFL);
2043   raise (sig);
2044 }
2045
2046 /* Set the ordering options for KEY specified in S.
2047    Return the address of the first character in S that
2048    is not a valid ordering option.
2049    BLANKTYPE is the kind of blanks that 'b' should skip. */
2050
2051 static char *
2052 set_ordering (const char *s, struct keyfield *key, enum blanktype blanktype)
2053 {
2054   while (*s)
2055     {
2056       switch (*s)
2057         {
2058         case 'b':
2059           if (blanktype == bl_start || blanktype == bl_both)
2060             key->skipsblanks = true;
2061           if (blanktype == bl_end || blanktype == bl_both)
2062             key->skipeblanks = true;
2063           break;
2064         case 'd':
2065           key->ignore = nondictionary;
2066           break;
2067         case 'f':
2068           key->translate = fold_toupper;
2069           break;
2070         case 'g':
2071           key->general_numeric = true;
2072           break;
2073         case 'i':
2074           /* Option order should not matter, so don't let -i override
2075              -d.  -d implies -i, but -i does not imply -d.  */
2076           if (! key->ignore)
2077             key->ignore = nonprinting;
2078           break;
2079         case 'M':
2080           key->month = true;
2081           break;
2082         case 'n':
2083           key->numeric = true;
2084           break;
2085         case 'r':
2086           key->reverse = true;
2087           break;
2088         default:
2089           return (char *) s;
2090         }
2091       ++s;
2092     }
2093   return (char *) s;
2094 }
2095
2096 static struct keyfield *
2097 new_key (void)
2098 {
2099   struct keyfield *key = xzalloc (sizeof *key);
2100   key->eword = SIZE_MAX;
2101   return key;
2102 }
2103
2104 int
2105 main (int argc, char **argv)
2106 {
2107   struct keyfield *key;
2108   struct keyfield gkey;
2109   char const *s;
2110   int c = 0;
2111   bool checkonly = false;
2112   bool mergeonly = false;
2113   size_t nfiles = 0;
2114   bool posixly_correct = (getenv ("POSIXLY_CORRECT") != NULL);
2115   bool obsolete_usage = (posix2_version () < 200112);
2116   char *minus = "-", **files;
2117   char const *outfile = NULL;
2118
2119   initialize_main (&argc, &argv);
2120   program_name = argv[0];
2121   setlocale (LC_ALL, "");
2122   bindtextdomain (PACKAGE, LOCALEDIR);
2123   textdomain (PACKAGE);
2124
2125   atexit (cleanup);
2126
2127   initialize_exit_failure (SORT_FAILURE);
2128   atexit (close_stdout);
2129
2130   hard_LC_COLLATE = hard_locale (LC_COLLATE);
2131 #if HAVE_NL_LANGINFO
2132   hard_LC_TIME = hard_locale (LC_TIME);
2133 #endif
2134
2135   /* Get locale's representation of the decimal point.  */
2136   {
2137     struct lconv const *locale = localeconv ();
2138
2139     /* If the locale doesn't define a decimal point, or if the decimal
2140        point is multibyte, use the C locale's decimal point.  FIXME:
2141        add support for multibyte decimal points.  */
2142     decimal_point = to_uchar (locale->decimal_point[0]);
2143     if (! decimal_point || locale->decimal_point[1])
2144       decimal_point = '.';
2145
2146     /* FIXME: add support for multibyte thousands separators.  */
2147     thousands_sep = to_uchar (*locale->thousands_sep);
2148     if (! thousands_sep || locale->thousands_sep[1])
2149       thousands_sep = -1;
2150   }
2151
2152   have_read_stdin = false;
2153   inittables ();
2154
2155   {
2156     size_t i;
2157     static int const sig[] = { SIGHUP, SIGINT, SIGPIPE, SIGTERM };
2158     enum { nsigs = sizeof sig / sizeof sig[0] };
2159
2160 #if SA_NOCLDSTOP
2161     struct sigaction act;
2162
2163     sigemptyset (&caught_signals);
2164     for (i = 0; i < nsigs; i++)
2165       {
2166         sigaction (sig[i], NULL, &act);
2167         if (act.sa_handler != SIG_IGN)
2168           sigaddset (&caught_signals, sig[i]);
2169       }
2170
2171     act.sa_handler = sighandler;
2172     act.sa_mask = caught_signals;
2173     act.sa_flags = 0;
2174
2175     for (i = 0; i < nsigs; i++)
2176       if (sigismember (&caught_signals, sig[i]))
2177         sigaction (sig[i], &act, NULL);
2178 #else
2179     for (i = 0; i < nsigs; i++)
2180       if (signal (sig[i], SIG_IGN) != SIG_IGN)
2181         {
2182           signal (sig[i], sighandler);
2183           siginterrupt (sig[i], 1);
2184         }
2185 #endif
2186   }
2187
2188   gkey.sword = gkey.eword = SIZE_MAX;
2189   gkey.ignore = NULL;
2190   gkey.translate = NULL;
2191   gkey.numeric = gkey.general_numeric = gkey.month = gkey.reverse = false;
2192   gkey.skipsblanks = gkey.skipeblanks = false;
2193
2194   files = xnmalloc (argc, sizeof *files);
2195
2196   for (;;)
2197     {
2198       /* Parse an operand as a file after "--" was seen; or if
2199          pedantic and a file was seen, unless the POSIX version
2200          predates 1003.1-2001 and -c was not seen and the operand is
2201          "-o FILE" or "-oFILE".  */
2202
2203       if (c == -1
2204           || (posixly_correct && nfiles != 0
2205               && ! (obsolete_usage
2206                     && ! checkonly
2207                     && optind != argc
2208                     && argv[optind][0] == '-' && argv[optind][1] == 'o'
2209                     && (argv[optind][2] || optind + 1 != argc)))
2210           || ((c = getopt_long (argc, argv, short_options,
2211                                 long_options, NULL))
2212               == -1))
2213         {
2214           if (argc <= optind)
2215             break;
2216           files[nfiles++] = argv[optind++];
2217         }
2218       else switch (c)
2219         {
2220         case 1:
2221           key = NULL;
2222           if (obsolete_usage && optarg[0] == '+')
2223             {
2224               /* Treat +POS1 [-POS2] as a key if possible; but silently
2225                  treat an operand as a file if it is not a valid +POS1.  */
2226               key = new_key ();
2227               s = parse_field_count (optarg + 1, &key->sword, NULL);
2228               if (s && *s == '.')
2229                 s = parse_field_count (s + 1, &key->schar, NULL);
2230               if (! (key->sword | key->schar))
2231                 key->sword = SIZE_MAX;
2232               if (! s || *set_ordering (s, key, bl_start))
2233                 {
2234                   free (key);
2235                   key = NULL;
2236                 }
2237               else
2238                 {
2239                   if (optind != argc && argv[optind][0] == '-'
2240                       && ISDIGIT (argv[optind][1]))
2241                     {
2242                       char const *optarg1 = argv[optind++];
2243                       s = parse_field_count (optarg1 + 1, &key->eword,
2244                                              N_("invalid number after `-'"));
2245                       if (*s == '.')
2246                         s = parse_field_count (s + 1, &key->echar,
2247                                                N_("invalid number after `.'"));
2248                       if (*set_ordering (s, key, bl_end))
2249                         badfieldspec (optarg1,
2250                                       N_("stray character in field spec"));
2251                     }
2252                   insertkey (key);
2253                 }
2254             }
2255           if (! key)
2256             files[nfiles++] = optarg;
2257           break;
2258
2259         case 'b':
2260         case 'd':
2261         case 'f':
2262         case 'g':
2263         case 'i':
2264         case 'M':
2265         case 'n':
2266         case 'r':
2267           {
2268             char str[2];
2269             str[0] = c;
2270             str[1] = '\0';
2271             set_ordering (str, &gkey, bl_both);
2272           }
2273           break;
2274
2275         case 'c':
2276           checkonly = true;
2277           break;
2278
2279         case 'k':
2280           key = new_key ();
2281
2282           /* Get POS1. */
2283           s = parse_field_count (optarg, &key->sword,
2284                                  N_("invalid number at field start"));
2285           if (! key->sword--)
2286             {
2287               /* Provoke with `sort -k0' */
2288               badfieldspec (optarg, N_("field number is zero"));
2289             }
2290           if (*s == '.')
2291             {
2292               s = parse_field_count (s + 1, &key->schar,
2293                                      N_("invalid number after `.'"));
2294               if (! key->schar--)
2295                 {
2296                   /* Provoke with `sort -k1.0' */
2297                   badfieldspec (optarg, N_("character offset is zero"));
2298                 }
2299             }
2300           if (! (key->sword | key->schar))
2301             key->sword = SIZE_MAX;
2302           s = set_ordering (s, key, bl_start);
2303           if (*s != ',')
2304             {
2305               key->eword = SIZE_MAX;
2306               key->echar = 0;
2307             }
2308           else
2309             {
2310               /* Get POS2. */
2311               s = parse_field_count (s + 1, &key->eword,
2312                                      N_("invalid number after `,'"));
2313               if (! key->eword--)
2314                 {
2315                   /* Provoke with `sort -k1,0' */
2316                   badfieldspec (optarg, N_("field number is zero"));
2317                 }
2318               if (*s == '.')
2319                 s = parse_field_count (s + 1, &key->echar,
2320                                        N_("invalid number after `.'"));
2321               else
2322                 {
2323                   /* `-k 2,3' is equivalent to `+1 -3'.  */
2324                   key->eword++;
2325                 }
2326               s = set_ordering (s, key, bl_end);
2327             }
2328           if (*s)
2329             badfieldspec (optarg, N_("stray character in field spec"));
2330           insertkey (key);
2331           break;
2332
2333         case 'm':
2334           mergeonly = true;
2335           break;
2336
2337         case 'o':
2338           if (outfile && !STREQ (outfile, optarg))
2339             error (SORT_FAILURE, 0, _("multiple output files specified"));
2340           outfile = optarg;
2341           break;
2342
2343         case 's':
2344           stable = true;
2345           break;
2346
2347         case 'S':
2348           specify_sort_size (optarg);
2349           break;
2350
2351         case 't':
2352           {
2353             char newtab = optarg[0];
2354             if (! newtab)
2355               error (SORT_FAILURE, 0, _("empty tab"));
2356             if (optarg[1])
2357               {
2358                 if (STREQ (optarg, "\\0"))
2359                   newtab = '\0';
2360                 else
2361                   {
2362                     /* Provoke with `sort -txx'.  Complain about
2363                        "multi-character tab" instead of "multibyte tab", so
2364                        that the diagnostic's wording does not need to be
2365                        changed once multibyte characters are supported.  */
2366                     error (SORT_FAILURE, 0, _("multi-character tab %s"),
2367                            quote (optarg));
2368                   }
2369               }
2370             if (tab != TAB_DEFAULT && tab != newtab)
2371               error (SORT_FAILURE, 0, _("incompatible tabs"));
2372             tab = newtab;
2373           }
2374           break;
2375
2376         case 'T':
2377           add_temp_dir (optarg);
2378           break;
2379
2380         case 'u':
2381           unique = true;
2382           break;
2383
2384         case 'y':
2385           /* Accept and ignore e.g. -y0 for compatibility with Solaris 2.x
2386              through Solaris 7.  It is also accepted by many non-Solaris
2387              "sort" implementations, e.g., AIX 5.2, HP-UX 11i v2, IRIX 6.5.
2388              -y is marked as obsolete starting with Solaris 8 (1999), but is
2389              still accepted as of Solaris 10 prerelease (2004).
2390
2391              Solaris 2.5.1 "sort -y 100" reads the input file "100", but
2392              emulate Solaris 8 and 9 "sort -y 100" which ignores the "100",
2393              and which in general ignores the argument after "-y" if it
2394              consists entirely of digits (it can even be empty).  */
2395           if (optarg == argv[optind - 1])
2396             {
2397               char const *p;
2398               for (p = optarg; ISDIGIT (*p); p++)
2399                 continue;
2400               optind -= (*p != '\0');
2401             }
2402           break;
2403
2404         case 'z':
2405           eolchar = 0;
2406           break;
2407
2408         case_GETOPT_HELP_CHAR;
2409
2410         case_GETOPT_VERSION_CHAR (PROGRAM_NAME, AUTHORS);
2411
2412         default:
2413           usage (SORT_FAILURE);
2414         }
2415     }
2416
2417   /* Inheritance of global options to individual keys. */
2418   for (key = keylist; key; key = key->next)
2419     if (! (key->ignore || key->translate
2420            || (key->skipsblanks | key->reverse
2421                | key->skipeblanks | key->month | key->numeric
2422                | key->general_numeric)))
2423       {
2424         key->ignore = gkey.ignore;
2425         key->translate = gkey.translate;
2426         key->skipsblanks = gkey.skipsblanks;
2427         key->skipeblanks = gkey.skipeblanks;
2428         key->month = gkey.month;
2429         key->numeric = gkey.numeric;
2430         key->general_numeric = gkey.general_numeric;
2431         key->reverse = gkey.reverse;
2432       }
2433
2434   if (!keylist && (gkey.ignore || gkey.translate
2435                    || (gkey.skipsblanks | gkey.skipeblanks | gkey.month
2436                        | gkey.numeric | gkey.general_numeric)))
2437     insertkey (&gkey);
2438   reverse = gkey.reverse;
2439
2440   if (temp_dir_count == 0)
2441     {
2442       char const *tmp_dir = getenv ("TMPDIR");
2443       add_temp_dir (tmp_dir ? tmp_dir : DEFAULT_TMPDIR);
2444     }
2445
2446   if (nfiles == 0)
2447     {
2448       nfiles = 1;
2449       files = &minus;
2450     }
2451
2452   if (checkonly)
2453     {
2454       if (nfiles > 1)
2455         {
2456           error (0, 0, _("extra operand %s not allowed with -c"),
2457                  quote (files[1]));
2458           usage (SORT_FAILURE);
2459         }
2460
2461       /* POSIX requires that sort return 1 IFF invoked with -c and the
2462          input is not properly sorted.  */
2463       exit (check (files[0]) ? EXIT_SUCCESS : SORT_OUT_OF_ORDER);
2464     }
2465
2466   if (mergeonly)
2467     merge (files, 0, nfiles, outfile);
2468   else
2469     sort (files, nfiles, outfile);
2470
2471   if (have_read_stdin && fclose (stdin) == EOF)
2472     die (_("close failed"), "-");
2473
2474   exit (EXIT_SUCCESS);
2475 }