1/* sort - sort lines of text (with all kinds of options).
2   Copyright (C) 1988-2017 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 3 of the License, or
7   (at your option) 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, see <http://www.gnu.org/licenses/>.
16
17   Written December 1988 by Mike Haertel.
18   The author may be reached (Email) at the address mike@gnu.ai.mit.edu,
19   or (US mail) as Mike Haertel c/o Free Software Foundation.
20
21   Ørn E. Hansen added NLS support in 1997.  */
22
23#include <config.h>
24
25#include <getopt.h>
26#include <pthread.h>
27#include <sys/resource.h>
28#include <sys/types.h>
29#include <sys/wait.h>
30#include <signal.h>
31#include <assert.h>
32#include "system.h"
33#include "argmatch.h"
34#include "die.h"
35#include "error.h"
36#include "fadvise.h"
37#include "filevercmp.h"
38#include "flexmember.h"
39#include "hard-locale.h"
40#include "hash.h"
41#include "heap.h"
42#include "ignore-value.h"
43#include "md5.h"
44#include "mbswidth.h"
45#include "nproc.h"
46#include "physmem.h"
47#include "posixver.h"
48#include "quote.h"
49#include "randread.h"
50#include "readtokens0.h"
51#include "stdio--.h"
52#include "stdlib--.h"
53#include "strnumcmp.h"
54#include "xmemcoll.h"
55#include "xnanosleep.h"
56#include "xstrtol.h"
57
58#ifndef RLIMIT_DATA
59struct rlimit { size_t rlim_cur; };
60# define getrlimit(Resource, Rlp) (-1)
61#endif
62
63/* The official name of this program (e.g., no 'g' prefix).  */
64#define PROGRAM_NAME "sort"
65
66#define AUTHORS \
67  proper_name ("Mike Haertel"), \
68  proper_name ("Paul Eggert")
69
70#if HAVE_LANGINFO_CODESET
71# include <langinfo.h>
72#endif
73
74/* Use SA_NOCLDSTOP as a proxy for whether the sigaction machinery is
75   present.  */
76#ifndef SA_NOCLDSTOP
77# define SA_NOCLDSTOP 0
78/* No sigprocmask.  Always 'return' zero. */
79# define sigprocmask(How, Set, Oset) (0)
80# define sigset_t int
81# if ! HAVE_SIGINTERRUPT
82#  define siginterrupt(sig, flag) /* empty */
83# endif
84#endif
85
86#if !defined OPEN_MAX && defined NR_OPEN
87# define OPEN_MAX NR_OPEN
88#endif
89#if !defined OPEN_MAX
90# define OPEN_MAX 20
91#endif
92
93#define UCHAR_LIM (UCHAR_MAX + 1)
94
95#if HAVE_C99_STRTOLD
96# define long_double long double
97#else
98# define long_double double
99# undef strtold
100# define strtold strtod
101#endif
102
103#ifndef DEFAULT_TMPDIR
104# define DEFAULT_TMPDIR "/tmp"
105#endif
106
107/* Maximum number of lines to merge every time a NODE is taken from
108   the merge queue.  Node is at LEVEL in the binary merge tree,
109   and is responsible for merging TOTAL lines. */
110#define MAX_MERGE(total, level) (((total) >> (2 * ((level) + 1))) + 1)
111
112/* Heuristic value for the number of lines for which it is worth creating
113   a subthread, during an internal merge sort.  I.e., it is a small number
114   of "average" lines for which sorting via two threads is faster than
115   sorting via one on an "average" system.  On a dual-core 2.0 GHz i686
116   system with 3GB of RAM and 2MB of L2 cache, a file containing 128K
117   lines of gensort -a output is sorted slightly faster with --parallel=2
118   than with --parallel=1.  By contrast, using --parallel=1 is about 10%
119   faster than using --parallel=2 with a 64K-line input.  */
120enum { SUBTHREAD_LINES_HEURISTIC = 128 * 1024 };
121verify (4 <= SUBTHREAD_LINES_HEURISTIC);
122
123/* The number of threads after which there are
124   diminishing performance gains.  */
125enum { DEFAULT_MAX_THREADS = 8 };
126
127/* Exit statuses.  */
128enum
129  {
130    /* POSIX says to exit with status 1 if invoked with -c and the
131       input is not properly sorted.  */
132    SORT_OUT_OF_ORDER = 1,
133
134    /* POSIX says any other irregular exit must exit with a status
135       code greater than 1.  */
136    SORT_FAILURE = 2
137  };
138
139enum
140  {
141    /* The number of times we should try to fork a compression process
142       (we retry if the fork call fails).  We don't _need_ to compress
143       temp files, this is just to reduce disk access, so this number
144       can be small.  Each retry doubles in duration.  */
145    MAX_FORK_TRIES_COMPRESS = 4,
146
147    /* The number of times we should try to fork a decompression process.
148       If we can't fork a decompression process, we can't sort, so this
149       number should be big.  Each retry doubles in duration.  */
150    MAX_FORK_TRIES_DECOMPRESS = 9
151  };
152
153enum
154  {
155    /* Level of the end-of-merge node, one level above the root. */
156    MERGE_END = 0,
157
158    /* Level of the root node in merge tree. */
159    MERGE_ROOT = 1
160  };
161
162/* The representation of the decimal point in the current locale.  */
163static int decimal_point;
164
165/* Thousands separator; if -1, then there isn't one.  */
166static int thousands_sep;
167
168/* Nonzero if the corresponding locales are hard.  */
169static bool hard_LC_COLLATE;
170#if HAVE_NL_LANGINFO
171static bool hard_LC_TIME;
172#endif
173
174#define NONZERO(x) ((x) != 0)
175
176/* The kind of blanks for '-b' to skip in various options. */
177enum blanktype { bl_start, bl_end, bl_both };
178
179/* The character marking end of line. Default to \n. */
180static char eolchar = '\n';
181
182/* Lines are held in core as counted strings. */
183struct line
184{
185  char *text;			/* Text of the line. */
186  size_t length;		/* Length including final newline. */
187  char *keybeg;			/* Start of first key. */
188  char *keylim;			/* Limit of first key. */
189};
190
191/* Input buffers. */
192struct buffer
193{
194  char *buf;			/* Dynamically allocated buffer,
195                                   partitioned into 3 regions:
196                                   - input data;
197                                   - unused area;
198                                   - an array of lines, in reverse order.  */
199  size_t used;			/* Number of bytes used for input data.  */
200  size_t nlines;		/* Number of lines in the line array.  */
201  size_t alloc;			/* Number of bytes allocated. */
202  size_t left;			/* Number of bytes left from previous reads. */
203  size_t line_bytes;		/* Number of bytes to reserve for each line. */
204  bool eof;			/* An EOF has been read.  */
205};
206
207/* Sort key.  */
208struct keyfield
209{
210  size_t sword;			/* Zero-origin 'word' to start at. */
211  size_t schar;			/* Additional characters to skip. */
212  size_t eword;			/* Zero-origin last 'word' of key. */
213  size_t echar;			/* Additional characters in field. */
214  bool const *ignore;		/* Boolean array of characters to ignore. */
215  char const *translate;	/* Translation applied to characters. */
216  bool skipsblanks;		/* Skip leading blanks when finding start.  */
217  bool skipeblanks;		/* Skip leading blanks when finding end.  */
218  bool numeric;			/* Flag for numeric comparison.  Handle
219                                   strings of digits with optional decimal
220                                   point, but no exponential notation. */
221  bool random;			/* Sort by random hash of key.  */
222  bool general_numeric;		/* Flag for general, numeric comparison.
223                                   Handle numbers in exponential notation. */
224  bool human_numeric;		/* Flag for sorting by human readable
225                                   units with either SI or IEC prefixes. */
226  bool month;			/* Flag for comparison by month name. */
227  bool reverse;			/* Reverse the sense of comparison. */
228  bool version;			/* sort by version number */
229  bool traditional_used;	/* Traditional key option format is used. */
230  struct keyfield *next;	/* Next keyfield to try. */
231};
232
233struct month
234{
235  char const *name;
236  int val;
237};
238
239/* Binary merge tree node. */
240struct merge_node
241{
242  struct line *lo;              /* Lines to merge from LO child node. */
243  struct line *hi;              /* Lines to merge from HI child node. */
244  struct line *end_lo;          /* End of available lines from LO. */
245  struct line *end_hi;          /* End of available lines from HI. */
246  struct line **dest;           /* Pointer to destination of merge. */
247  size_t nlo;                   /* Total Lines remaining from LO. */
248  size_t nhi;                   /* Total lines remaining from HI. */
249  struct merge_node *parent;    /* Parent node. */
250  struct merge_node *lo_child;  /* LO child node. */
251  struct merge_node *hi_child;  /* HI child node. */
252  unsigned int level;           /* Level in merge tree. */
253  bool queued;                  /* Node is already in heap. */
254  pthread_mutex_t lock;         /* Lock for node operations. */
255};
256
257/* Priority queue of merge nodes. */
258struct merge_node_queue
259{
260  struct heap *priority_queue;  /* Priority queue of merge tree nodes. */
261  pthread_mutex_t mutex;        /* Lock for queue operations. */
262  pthread_cond_t cond;          /* Conditional wait for empty queue to populate
263                                   when popping. */
264};
265
266/* Used to implement --unique (-u).  */
267static struct line saved_line;
268
269/* FIXME: None of these tables work with multibyte character sets.
270   Also, there are many other bugs when handling multibyte characters.
271   One way to fix this is to rewrite 'sort' to use wide characters
272   internally, but doing this with good performance is a bit
273   tricky.  */
274
275/* Table of blanks.  */
276static bool blanks[UCHAR_LIM];
277
278/* Table of non-printing characters. */
279static bool nonprinting[UCHAR_LIM];
280
281/* Table of non-dictionary characters (not letters, digits, or blanks). */
282static bool nondictionary[UCHAR_LIM];
283
284/* Translation table folding lower case to upper.  */
285static char fold_toupper[UCHAR_LIM];
286
287#define MONTHS_PER_YEAR 12
288
289/* Table mapping month names to integers.
290   Alphabetic order allows binary search. */
291static struct month monthtab[] =
292{
293  {"APR", 4},
294  {"AUG", 8},
295  {"DEC", 12},
296  {"FEB", 2},
297  {"JAN", 1},
298  {"JUL", 7},
299  {"JUN", 6},
300  {"MAR", 3},
301  {"MAY", 5},
302  {"NOV", 11},
303  {"OCT", 10},
304  {"SEP", 9}
305};
306
307/* During the merge phase, the number of files to merge at once. */
308#define NMERGE_DEFAULT 16
309
310/* Minimum size for a merge or check buffer.  */
311#define MIN_MERGE_BUFFER_SIZE (2 + sizeof (struct line))
312
313/* Minimum sort size; the code might not work with smaller sizes.  */
314#define MIN_SORT_SIZE (nmerge * MIN_MERGE_BUFFER_SIZE)
315
316/* The number of bytes needed for a merge or check buffer, which can
317   function relatively efficiently even if it holds only one line.  If
318   a longer line is seen, this value is increased.  */
319static size_t merge_buffer_size = MAX (MIN_MERGE_BUFFER_SIZE, 256 * 1024);
320
321/* The approximate maximum number of bytes of main memory to use, as
322   specified by the user.  Zero if the user has not specified a size.  */
323static size_t sort_size;
324
325/* The initial allocation factor for non-regular files.
326   This is used, e.g., when reading from a pipe.
327   Don't make it too big, since it is multiplied by ~130 to
328   obtain the size of the actual buffer sort will allocate.
329   Also, there may be 8 threads all doing this at the same time.  */
330#define INPUT_FILE_SIZE_GUESS (128 * 1024)
331
332/* Array of directory names in which any temporary files are to be created. */
333static char const **temp_dirs;
334
335/* Number of temporary directory names used.  */
336static size_t temp_dir_count;
337
338/* Number of allocated slots in temp_dirs.  */
339static size_t temp_dir_alloc;
340
341/* Flag to reverse the order of all comparisons. */
342static bool reverse;
343
344/* Flag for stable sort.  This turns off the last ditch bytewise
345   comparison of lines, and instead leaves lines in the same order
346   they were read if all keys compare equal.  */
347static bool stable;
348
349/* If TAB has this value, blanks separate fields.  */
350enum { TAB_DEFAULT = CHAR_MAX + 1 };
351
352/* Tab character separating fields.  If TAB_DEFAULT, then fields are
353   separated by the empty string between a non-blank character and a blank
354   character. */
355static int tab = TAB_DEFAULT;
356
357/* Flag to remove consecutive duplicate lines from the output.
358   Only the last of a sequence of equal lines will be output. */
359static bool unique;
360
361/* Nonzero if any of the input files are the standard input. */
362static bool have_read_stdin;
363
364/* List of key field comparisons to be tried.  */
365static struct keyfield *keylist;
366
367/* Program used to (de)compress temp files.  Must accept -d.  */
368static char const *compress_program;
369
370/* Annotate the output with extra info to aid the user.  */
371static bool debug;
372
373/* Maximum number of files to merge in one go.  If more than this
374   number are present, temp files will be used. */
375static unsigned int nmerge = NMERGE_DEFAULT;
376
377/* Output an error to stderr using async-signal-safe routines, and _exit().
378   This can be used safely from signal handlers,
379   and between fork() and exec() of multithreaded processes.  */
380
381static void async_safe_die (int, const char *) ATTRIBUTE_NORETURN;
382static void
383async_safe_die (int errnum, const char *errstr)
384{
385  ignore_value (write (STDERR_FILENO, errstr, strlen (errstr)));
386
387  /* Even if defined HAVE_STRERROR_R, we can't use it,
388     as it may return a translated string etc. and even if not
389     may malloc() which is unsafe.  We might improve this
390     by testing for sys_errlist and using that if available.
391     For now just report the error number.  */
392  if (errnum)
393    {
394      char errbuf[INT_BUFSIZE_BOUND (errnum)];
395      char *p = inttostr (errnum, errbuf);
396      ignore_value (write (STDERR_FILENO, ": errno ", 8));
397      ignore_value (write (STDERR_FILENO, p, strlen (p)));
398    }
399
400  ignore_value (write (STDERR_FILENO, "\n", 1));
401
402  _exit (SORT_FAILURE);
403}
404
405/* Report MESSAGE for FILE, then clean up and exit.
406   If FILE is null, it represents standard output.  */
407
408static void sort_die (char const *, char const *) ATTRIBUTE_NORETURN;
409static void
410sort_die (char const *message, char const *file)
411{
412  die (SORT_FAILURE, errno, "%s: %s", message,
413       quotef (file ? file : _("standard output")));
414}
415
416void
417usage (int status)
418{
419  if (status != EXIT_SUCCESS)
420    emit_try_help ();
421  else
422    {
423      printf (_("\
424Usage: %s [OPTION]... [FILE]...\n\
425  or:  %s [OPTION]... --files0-from=F\n\
426"),
427              program_name, program_name);
428      fputs (_("\
429Write sorted concatenation of all FILE(s) to standard output.\n\
430"), stdout);
431
432      emit_stdin_note ();
433      emit_mandatory_arg_note ();
434
435      fputs (_("\
436Ordering options:\n\
437\n\
438"), stdout);
439      fputs (_("\
440  -b, --ignore-leading-blanks  ignore leading blanks\n\
441  -d, --dictionary-order      consider only blanks and alphanumeric characters\
442\n\
443  -f, --ignore-case           fold lower case to upper case characters\n\
444"), stdout);
445      fputs (_("\
446  -g, --general-numeric-sort  compare according to general numerical value\n\
447  -i, --ignore-nonprinting    consider only printable characters\n\
448  -M, --month-sort            compare (unknown) < 'JAN' < ... < 'DEC'\n\
449"), stdout);
450      fputs (_("\
451  -h, --human-numeric-sort    compare human readable numbers (e.g., 2K 1G)\n\
452"), stdout);
453      fputs (_("\
454  -n, --numeric-sort          compare according to string numerical value\n\
455  -R, --random-sort           shuffle, but group identical keys.  See shuf(1)\n\
456      --random-source=FILE    get random bytes from FILE\n\
457  -r, --reverse               reverse the result of comparisons\n\
458"), stdout);
459      fputs (_("\
460      --sort=WORD             sort according to WORD:\n\
461                                general-numeric -g, human-numeric -h, month -M,\
462\n\
463                                numeric -n, random -R, version -V\n\
464  -V, --version-sort          natural sort of (version) numbers within text\n\
465\n\
466"), stdout);
467      fputs (_("\
468Other options:\n\
469\n\
470"), stdout);
471      fputs (_("\
472      --batch-size=NMERGE   merge at most NMERGE inputs at once;\n\
473                            for more use temp files\n\
474"), stdout);
475      fputs (_("\
476  -c, --check, --check=diagnose-first  check for sorted input; do not sort\n\
477  -C, --check=quiet, --check=silent  like -c, but do not report first bad line\
478\n\
479      --compress-program=PROG  compress temporaries with PROG;\n\
480                              decompress them with PROG -d\n\
481"), stdout);
482      fputs (_("\
483      --debug               annotate the part of the line used to sort,\n\
484                              and warn about questionable usage to stderr\n\
485      --files0-from=F       read input from the files specified by\n\
486                            NUL-terminated names in file F;\n\
487                            If F is - then read names from standard input\n\
488"), stdout);
489      fputs (_("\
490  -k, --key=KEYDEF          sort via a key; KEYDEF gives location and type\n\
491  -m, --merge               merge already sorted files; do not sort\n\
492"), stdout);
493      fputs (_("\
494  -o, --output=FILE         write result to FILE instead of standard output\n\
495  -s, --stable              stabilize sort by disabling last-resort comparison\
496\n\
497  -S, --buffer-size=SIZE    use SIZE for main memory buffer\n\
498"), stdout);
499      printf (_("\
500  -t, --field-separator=SEP  use SEP instead of non-blank to blank transition\n\
501  -T, --temporary-directory=DIR  use DIR for temporaries, not $TMPDIR or %s;\n\
502                              multiple options specify multiple directories\n\
503      --parallel=N          change the number of sorts run concurrently to N\n\
504  -u, --unique              with -c, check for strict ordering;\n\
505                              without -c, output only the first of an equal run\
506\n\
507"), DEFAULT_TMPDIR);
508      fputs (_("\
509  -z, --zero-terminated     line delimiter is NUL, not newline\n\
510"), stdout);
511      fputs (HELP_OPTION_DESCRIPTION, stdout);
512      fputs (VERSION_OPTION_DESCRIPTION, stdout);
513      fputs (_("\
514\n\
515KEYDEF is F[.C][OPTS][,F[.C][OPTS]] for start and stop position, where F is a\n\
516field number and C a character position in the field; both are origin 1, and\n\
517the stop position defaults to the line's end.  If neither -t nor -b is in\n\
518effect, characters in a field are counted from the beginning of the preceding\n\
519whitespace.  OPTS is one or more single-letter ordering options [bdfgiMhnRrV],\
520\n\
521which override global ordering options for that key.  If no key is given, use\n\
522the entire line as the key.  Use --debug to diagnose incorrect key usage.\n\
523\n\
524SIZE may be followed by the following multiplicative suffixes:\n\
525"), stdout);
526      fputs (_("\
527% 1% of memory, b 1, K 1024 (default), and so on for M, G, T, P, E, Z, Y.\n\
528\n\
529*** WARNING ***\n\
530The locale specified by the environment affects sort order.\n\
531Set LC_ALL=C to get the traditional sort order that uses\n\
532native byte values.\n\
533"), stdout );
534      emit_ancillary_info (PROGRAM_NAME);
535    }
536
537  exit (status);
538}
539
540/* For long options that have no equivalent short option, use a
541   non-character as a pseudo short option, starting with CHAR_MAX + 1.  */
542enum
543{
544  CHECK_OPTION = CHAR_MAX + 1,
545  COMPRESS_PROGRAM_OPTION,
546  DEBUG_PROGRAM_OPTION,
547  FILES0_FROM_OPTION,
548  NMERGE_OPTION,
549  RANDOM_SOURCE_OPTION,
550  SORT_OPTION,
551  PARALLEL_OPTION
552};
553
554static char const short_options[] = "-bcCdfghik:mMno:rRsS:t:T:uVy:z";
555
556static struct option const long_options[] =
557{
558  {"ignore-leading-blanks", no_argument, NULL, 'b'},
559  {"check", optional_argument, NULL, CHECK_OPTION},
560  {"compress-program", required_argument, NULL, COMPRESS_PROGRAM_OPTION},
561  {"debug", no_argument, NULL, DEBUG_PROGRAM_OPTION},
562  {"dictionary-order", no_argument, NULL, 'd'},
563  {"ignore-case", no_argument, NULL, 'f'},
564  {"files0-from", required_argument, NULL, FILES0_FROM_OPTION},
565  {"general-numeric-sort", no_argument, NULL, 'g'},
566  {"ignore-nonprinting", no_argument, NULL, 'i'},
567  {"key", required_argument, NULL, 'k'},
568  {"merge", no_argument, NULL, 'm'},
569  {"month-sort", no_argument, NULL, 'M'},
570  {"numeric-sort", no_argument, NULL, 'n'},
571  {"human-numeric-sort", no_argument, NULL, 'h'},
572  {"version-sort", no_argument, NULL, 'V'},
573  {"random-sort", no_argument, NULL, 'R'},
574  {"random-source", required_argument, NULL, RANDOM_SOURCE_OPTION},
575  {"sort", required_argument, NULL, SORT_OPTION},
576  {"output", required_argument, NULL, 'o'},
577  {"reverse", no_argument, NULL, 'r'},
578  {"stable", no_argument, NULL, 's'},
579  {"batch-size", required_argument, NULL, NMERGE_OPTION},
580  {"buffer-size", required_argument, NULL, 'S'},
581  {"field-separator", required_argument, NULL, 't'},
582  {"temporary-directory", required_argument, NULL, 'T'},
583  {"unique", no_argument, NULL, 'u'},
584  {"zero-terminated", no_argument, NULL, 'z'},
585  {"parallel", required_argument, NULL, PARALLEL_OPTION},
586  {GETOPT_HELP_OPTION_DECL},
587  {GETOPT_VERSION_OPTION_DECL},
588  {NULL, 0, NULL, 0},
589};
590
591#define CHECK_TABLE \
592  _ct_("quiet",          'C') \
593  _ct_("silent",         'C') \
594  _ct_("diagnose-first", 'c')
595
596static char const *const check_args[] =
597{
598#define _ct_(_s, _c) _s,
599  CHECK_TABLE NULL
600#undef  _ct_
601};
602static char const check_types[] =
603{
604#define _ct_(_s, _c) _c,
605  CHECK_TABLE
606#undef  _ct_
607};
608
609#define SORT_TABLE \
610  _st_("general-numeric", 'g') \
611  _st_("human-numeric",   'h') \
612  _st_("month",           'M') \
613  _st_("numeric",         'n') \
614  _st_("random",          'R') \
615  _st_("version",         'V')
616
617static char const *const sort_args[] =
618{
619#define _st_(_s, _c) _s,
620  SORT_TABLE NULL
621#undef  _st_
622};
623static char const sort_types[] =
624{
625#define _st_(_s, _c) _c,
626  SORT_TABLE
627#undef  _st_
628};
629
630/* The set of signals that are caught.  */
631static sigset_t caught_signals;
632
633/* Critical section status.  */
634struct cs_status
635{
636  bool valid;
637  sigset_t sigs;
638};
639
640/* Enter a critical section.  */
641static struct cs_status
642cs_enter (void)
643{
644  struct cs_status status;
645  status.valid = (sigprocmask (SIG_BLOCK, &caught_signals, &status.sigs) == 0);
646  return status;
647}
648
649/* Leave a critical section.  */
650static void
651cs_leave (struct cs_status status)
652{
653  if (status.valid)
654    {
655      /* Ignore failure when restoring the signal mask. */
656      sigprocmask (SIG_SETMASK, &status.sigs, NULL);
657    }
658}
659
660/* Possible states for a temp file.  If compressed, the file's status
661   is unreaped or reaped, depending on whether 'sort' has waited for
662   the subprocess to finish.  */
663enum { UNCOMPRESSED, UNREAPED, REAPED };
664
665/* The list of temporary files. */
666struct tempnode
667{
668  struct tempnode *volatile next;
669  pid_t pid;     /* The subprocess PID; undefined if state == UNCOMPRESSED.  */
670  char state;
671  char name[FLEXIBLE_ARRAY_MEMBER];
672};
673static struct tempnode *volatile temphead;
674static struct tempnode *volatile *temptail = &temphead;
675
676/* A file to be sorted.  */
677struct sortfile
678{
679  /* The file's name.  */
680  char const *name;
681
682  /* Non-null if this is a temporary file, in which case NAME == TEMP->name.  */
683  struct tempnode *temp;
684};
685
686/* Map PIDs of unreaped subprocesses to their struct tempnode objects.  */
687static Hash_table *proctab;
688
689enum { INIT_PROCTAB_SIZE = 47 };
690
691static size_t
692proctab_hasher (void const *entry, size_t tabsize)
693{
694  struct tempnode const *node = entry;
695  return node->pid % tabsize;
696}
697
698static bool
699proctab_comparator (void const *e1, void const *e2)
700{
701  struct tempnode const *n1 = e1;
702  struct tempnode const *n2 = e2;
703  return n1->pid == n2->pid;
704}
705
706/* The number of unreaped child processes.  */
707static pid_t nprocs;
708
709static bool delete_proc (pid_t);
710
711/* If PID is positive, wait for the child process with that PID to
712   exit, and assume that PID has already been removed from the process
713   table.  If PID is 0 or -1, clean up some child that has exited (by
714   waiting for it, and removing it from the proc table) and return the
715   child's process ID.  However, if PID is 0 and no children have
716   exited, return 0 without waiting.  */
717
718static pid_t
719reap (pid_t pid)
720{
721  int status;
722  pid_t cpid = waitpid ((pid ? pid : -1), &status, (pid ? 0 : WNOHANG));
723
724  if (cpid < 0)
725    die (SORT_FAILURE, errno, _("waiting for %s [-d]"),
726         quoteaf (compress_program));
727  else if (0 < cpid && (0 < pid || delete_proc (cpid)))
728    {
729      if (! WIFEXITED (status) || WEXITSTATUS (status))
730        die (SORT_FAILURE, 0, _("%s [-d] terminated abnormally"),
731             quoteaf (compress_program));
732      --nprocs;
733    }
734
735  return cpid;
736}
737
738/* TEMP represents a new process; add it to the process table.  Create
739   the process table the first time it's called.  */
740
741static void
742register_proc (struct tempnode *temp)
743{
744  if (! proctab)
745    {
746      proctab = hash_initialize (INIT_PROCTAB_SIZE, NULL,
747                                 proctab_hasher,
748                                 proctab_comparator,
749                                 NULL);
750      if (! proctab)
751        xalloc_die ();
752    }
753
754  temp->state = UNREAPED;
755
756  if (! hash_insert (proctab, temp))
757    xalloc_die ();
758}
759
760/* If PID is in the process table, remove it and return true.
761   Otherwise, return false.  */
762
763static bool
764delete_proc (pid_t pid)
765{
766  struct tempnode test;
767
768  test.pid = pid;
769  struct tempnode *node = hash_delete (proctab, &test);
770  if (! node)
771    return false;
772  node->state = REAPED;
773  return true;
774}
775
776/* Remove PID from the process table, and wait for it to exit if it
777   hasn't already.  */
778
779static void
780wait_proc (pid_t pid)
781{
782  if (delete_proc (pid))
783    reap (pid);
784}
785
786/* Reap any exited children.  Do not block; reap only those that have
787   already exited.  */
788
789static void
790reap_exited (void)
791{
792  while (0 < nprocs && reap (0))
793    continue;
794}
795
796/* Reap at least one exited child, waiting if necessary.  */
797
798static void
799reap_some (void)
800{
801  reap (-1);
802  reap_exited ();
803}
804
805/* Reap all children, waiting if necessary.  */
806
807static void
808reap_all (void)
809{
810  while (0 < nprocs)
811    reap (-1);
812}
813
814/* Clean up any remaining temporary files.  */
815
816static void
817cleanup (void)
818{
819  struct tempnode const *node;
820
821  for (node = temphead; node; node = node->next)
822    unlink (node->name);
823  temphead = NULL;
824}
825
826/* Cleanup actions to take when exiting.  */
827
828static void
829exit_cleanup (void)
830{
831  if (temphead)
832    {
833      /* Clean up any remaining temporary files in a critical section so
834         that a signal handler does not try to clean them too.  */
835      struct cs_status cs = cs_enter ();
836      cleanup ();
837      cs_leave (cs);
838    }
839
840  close_stdout ();
841}
842
843/* Create a new temporary file, returning its newly allocated tempnode.
844   Store into *PFD the file descriptor open for writing.
845   If the creation fails, return NULL and store -1 into *PFD if the
846   failure is due to file descriptor exhaustion and
847   SURVIVE_FD_EXHAUSTION; otherwise, die.  */
848
849static struct tempnode *
850create_temp_file (int *pfd, bool survive_fd_exhaustion)
851{
852  static char const slashbase[] = "/sortXXXXXX";
853  static size_t temp_dir_index;
854  int fd;
855  int saved_errno;
856  char const *temp_dir = temp_dirs[temp_dir_index];
857  size_t len = strlen (temp_dir);
858  struct tempnode *node =
859    xmalloc (FLEXSIZEOF (struct tempnode, name, len + sizeof slashbase));
860  char *file = node->name;
861  struct cs_status cs;
862
863  memcpy (file, temp_dir, len);
864  memcpy (file + len, slashbase, sizeof slashbase);
865  node->next = NULL;
866  if (++temp_dir_index == temp_dir_count)
867    temp_dir_index = 0;
868
869  /* Create the temporary file in a critical section, to avoid races.  */
870  cs = cs_enter ();
871  fd = mkstemp (file);
872  if (0 <= fd)
873    {
874      *temptail = node;
875      temptail = &node->next;
876    }
877  saved_errno = errno;
878  cs_leave (cs);
879  errno = saved_errno;
880
881  if (fd < 0)
882    {
883      if (! (survive_fd_exhaustion && errno == EMFILE))
884        die (SORT_FAILURE, errno, _("cannot create temporary file in %s"),
885             quoteaf (temp_dir));
886      free (node);
887      node = NULL;
888    }
889
890  *pfd = fd;
891  return node;
892}
893
894/* Return a stream for FILE, opened with mode HOW.  A null FILE means
895   standard output; HOW should be "w".  When opening for input, "-"
896   means standard input.  To avoid confusion, do not return file
897   descriptors STDIN_FILENO, STDOUT_FILENO, or STDERR_FILENO when
898   opening an ordinary FILE.  Return NULL if unsuccessful.
899
900   fadvise() is used to specify an access pattern for input files.
901   There are a few hints we could possibly provide,
902   and after careful testing it was decided that
903   specifying FADVISE_SEQUENTIAL was not detrimental
904   to any cases.  On Linux 2.6.31, this option doubles
905   the size of read ahead performed and thus was seen to
906   benefit these cases:
907     Merging
908     Sorting with a smaller internal buffer
909     Reading from faster flash devices
910
911   In _addition_ one could also specify other hints...
912
913   FADVISE_WILLNEED was tested, but Linux 2.6.31
914   at least uses that to _synchronously_ prepopulate the cache
915   with the specified range.  While sort does need to
916   read all of its input before outputting, a synchronous
917   read of the whole file up front precludes any processing
918   that sort could do in parallel with the system doing
919   read ahead of the data. This was seen to have negative effects
920   in a couple of cases:
921     Merging
922     Sorting with a smaller internal buffer
923   Note this option was seen to shorten the runtime for sort
924   on a multicore system with lots of RAM and other processes
925   competing for CPU.  It could be argued that more explicit
926   scheduling hints with 'nice' et. al. are more appropriate
927   for this situation.
928
929   FADVISE_NOREUSE is a possibility as it could lower
930   the priority of input data in the cache as sort will
931   only need to process it once.  However its functionality
932   has changed over Linux kernel versions and as of 2.6.31
933   it does nothing and thus we can't depend on what it might
934   do in future.
935
936   FADVISE_DONTNEED is not appropriate for user specified
937   input files, but for temp files we do want to drop the
938   cache immediately after processing.  This is done implicitly
939   however when the files are unlinked.  */
940
941static FILE *
942stream_open (char const *file, char const *how)
943{
944  FILE *fp;
945
946  if (*how == 'r')
947    {
948      if (STREQ (file, "-"))
949        {
950          have_read_stdin = true;
951          fp = stdin;
952        }
953      else
954        fp = fopen (file, how);
955      fadvise (fp, FADVISE_SEQUENTIAL);
956    }
957  else if (*how == 'w')
958    {
959      if (file && ftruncate (STDOUT_FILENO, 0) != 0)
960        die (SORT_FAILURE, errno, _("%s: error truncating"),
961             quotef (file));
962      fp = stdout;
963    }
964  else
965    assert (!"unexpected mode passed to stream_open");
966
967  return fp;
968}
969
970/* Same as stream_open, except always return a non-null value; die on
971   failure.  */
972
973static FILE *
974xfopen (char const *file, char const *how)
975{
976  FILE *fp = stream_open (file, how);
977  if (!fp)
978    sort_die (_("open failed"), file);
979  return fp;
980}
981
982/* Close FP, whose name is FILE, and report any errors.  */
983
984static void
985xfclose (FILE *fp, char const *file)
986{
987  switch (fileno (fp))
988    {
989    case STDIN_FILENO:
990      /* Allow reading stdin from tty more than once.  */
991      if (feof (fp))
992        clearerr (fp);
993      break;
994
995    case STDOUT_FILENO:
996      /* Don't close stdout just yet.  close_stdout does that.  */
997      if (fflush (fp) != 0)
998        sort_die (_("fflush failed"), file);
999      break;
1000
1001    default:
1002      if (fclose (fp) != 0)
1003        sort_die (_("close failed"), file);
1004      break;
1005    }
1006}
1007
1008static void
1009move_fd_or_die (int oldfd, int newfd)
1010{
1011  if (oldfd != newfd)
1012    {
1013      /* This should never fail for our usage.  */
1014      dup2 (oldfd, newfd);
1015      close (oldfd);
1016    }
1017}
1018
1019/* Fork a child process for piping to and do common cleanup.  The
1020   TRIES parameter tells us how many times to try to fork before
1021   giving up.  Return the PID of the child, or -1 (setting errno)
1022   on failure. */
1023
1024static pid_t
1025pipe_fork (int pipefds[2], size_t tries)
1026{
1027#if HAVE_WORKING_FORK
1028  struct tempnode *saved_temphead;
1029  int saved_errno;
1030  double wait_retry = 0.25;
1031  pid_t pid IF_LINT ( = -1);
1032  struct cs_status cs;
1033
1034  if (pipe (pipefds) < 0)
1035    return -1;
1036
1037  /* At least NMERGE + 1 subprocesses are needed.  More could be created, but
1038     uncontrolled subprocess generation can hurt performance significantly.
1039     Allow at most NMERGE + 2 subprocesses, on the theory that there
1040     may be some useful parallelism by letting compression for the
1041     previous merge finish (1 subprocess) in parallel with the current
1042     merge (NMERGE + 1 subprocesses).  */
1043
1044  if (nmerge + 1 < nprocs)
1045    reap_some ();
1046
1047  while (tries--)
1048    {
1049      /* This is so the child process won't delete our temp files
1050         if it receives a signal before exec-ing.  */
1051      cs = cs_enter ();
1052      saved_temphead = temphead;
1053      temphead = NULL;
1054
1055      pid = fork ();
1056      saved_errno = errno;
1057      if (pid)
1058        temphead = saved_temphead;
1059
1060      cs_leave (cs);
1061      errno = saved_errno;
1062
1063      if (0 <= pid || errno != EAGAIN)
1064        break;
1065      else
1066        {
1067          xnanosleep (wait_retry);
1068          wait_retry *= 2;
1069          reap_exited ();
1070        }
1071    }
1072
1073  if (pid < 0)
1074    {
1075      saved_errno = errno;
1076      close (pipefds[0]);
1077      close (pipefds[1]);
1078      errno = saved_errno;
1079    }
1080  else if (pid == 0)
1081    {
1082      close (STDIN_FILENO);
1083      close (STDOUT_FILENO);
1084    }
1085  else
1086    ++nprocs;
1087
1088  return pid;
1089
1090#else  /* ! HAVE_WORKING_FORK */
1091  return -1;
1092#endif
1093}
1094
1095/* Create a temporary file and, if asked for, start a compressor
1096   to that file.  Set *PFP to the file handle and return
1097   the address of the new temp node.  If the creation
1098   fails, return NULL if the failure is due to file descriptor
1099   exhaustion and SURVIVE_FD_EXHAUSTION; otherwise, die.  */
1100
1101static struct tempnode *
1102maybe_create_temp (FILE **pfp, bool survive_fd_exhaustion)
1103{
1104  int tempfd;
1105  struct tempnode *node = create_temp_file (&tempfd, survive_fd_exhaustion);
1106  if (! node)
1107    return NULL;
1108
1109  node->state = UNCOMPRESSED;
1110
1111  if (compress_program)
1112    {
1113      int pipefds[2];
1114
1115      node->pid = pipe_fork (pipefds, MAX_FORK_TRIES_COMPRESS);
1116      if (0 < node->pid)
1117        {
1118          close (tempfd);
1119          close (pipefds[0]);
1120          tempfd = pipefds[1];
1121
1122          register_proc (node);
1123        }
1124      else if (node->pid == 0)
1125        {
1126          /* Being the child of a multithreaded program before exec(),
1127             we're restricted to calling async-signal-safe routines here.  */
1128          close (pipefds[1]);
1129          move_fd_or_die (tempfd, STDOUT_FILENO);
1130          move_fd_or_die (pipefds[0], STDIN_FILENO);
1131
1132          execlp (compress_program, compress_program, (char *) NULL);
1133
1134          async_safe_die (errno, "couldn't execute compress program");
1135        }
1136    }
1137
1138  *pfp = fdopen (tempfd, "w");
1139  if (! *pfp)
1140    sort_die (_("couldn't create temporary file"), node->name);
1141
1142  return node;
1143}
1144
1145/* Create a temporary file and, if asked for, start a compressor
1146   to that file.  Set *PFP to the file handle and return the address
1147   of the new temp node.  Die on failure.  */
1148
1149static struct tempnode *
1150create_temp (FILE **pfp)
1151{
1152  return maybe_create_temp (pfp, false);
1153}
1154
1155/* Open a compressed temp file and start a decompression process through
1156   which to filter the input.  Return NULL (setting errno to
1157   EMFILE) if we ran out of file descriptors, and die on any other
1158   kind of failure.  */
1159
1160static FILE *
1161open_temp (struct tempnode *temp)
1162{
1163  int tempfd, pipefds[2];
1164  FILE *fp = NULL;
1165
1166  if (temp->state == UNREAPED)
1167    wait_proc (temp->pid);
1168
1169  tempfd = open (temp->name, O_RDONLY);
1170  if (tempfd < 0)
1171    return NULL;
1172
1173  pid_t child = pipe_fork (pipefds, MAX_FORK_TRIES_DECOMPRESS);
1174
1175  switch (child)
1176    {
1177    case -1:
1178      if (errno != EMFILE)
1179        die (SORT_FAILURE, errno, _("couldn't create process for %s -d"),
1180             quoteaf (compress_program));
1181      close (tempfd);
1182      errno = EMFILE;
1183      break;
1184
1185    case 0:
1186      /* Being the child of a multithreaded program before exec(),
1187         we're restricted to calling async-signal-safe routines here.  */
1188      close (pipefds[0]);
1189      move_fd_or_die (tempfd, STDIN_FILENO);
1190      move_fd_or_die (pipefds[1], STDOUT_FILENO);
1191
1192      execlp (compress_program, compress_program, "-d", (char *) NULL);
1193
1194      async_safe_die (errno, "couldn't execute compress program (with -d)");
1195
1196    default:
1197      temp->pid = child;
1198      register_proc (temp);
1199      close (tempfd);
1200      close (pipefds[1]);
1201
1202      fp = fdopen (pipefds[0], "r");
1203      if (! fp)
1204        {
1205          int saved_errno = errno;
1206          close (pipefds[0]);
1207          errno = saved_errno;
1208        }
1209      break;
1210    }
1211
1212  return fp;
1213}
1214
1215/* Append DIR to the array of temporary directory names.  */
1216static void
1217add_temp_dir (char const *dir)
1218{
1219  if (temp_dir_count == temp_dir_alloc)
1220    temp_dirs = X2NREALLOC (temp_dirs, &temp_dir_alloc);
1221
1222  temp_dirs[temp_dir_count++] = dir;
1223}
1224
1225/* Remove NAME from the list of temporary files.  */
1226
1227static void
1228zaptemp (char const *name)
1229{
1230  struct tempnode *volatile *pnode;
1231  struct tempnode *node;
1232  struct tempnode *next;
1233  int unlink_status;
1234  int unlink_errno = 0;
1235  struct cs_status cs;
1236
1237  for (pnode = &temphead; (node = *pnode)->name != name; pnode = &node->next)
1238    continue;
1239
1240  if (node->state == UNREAPED)
1241    wait_proc (node->pid);
1242
1243  /* Unlink the temporary file in a critical section to avoid races.  */
1244  next = node->next;
1245  cs = cs_enter ();
1246  unlink_status = unlink (name);
1247  unlink_errno = errno;
1248  *pnode = next;
1249  cs_leave (cs);
1250
1251  if (unlink_status != 0)
1252    error (0, unlink_errno, _("warning: cannot remove: %s"), quotef (name));
1253  if (! next)
1254    temptail = pnode;
1255  free (node);
1256}
1257
1258#if HAVE_NL_LANGINFO
1259
1260static int
1261struct_month_cmp (void const *m1, void const *m2)
1262{
1263  struct month const *month1 = m1;
1264  struct month const *month2 = m2;
1265  return strcmp (month1->name, month2->name);
1266}
1267
1268#endif
1269
1270/* Initialize the character class tables. */
1271
1272static void
1273inittables (void)
1274{
1275  size_t i;
1276
1277  for (i = 0; i < UCHAR_LIM; ++i)
1278    {
1279      blanks[i] = field_sep (i);
1280      nonprinting[i] = ! isprint (i);
1281      nondictionary[i] = ! isalnum (i) && ! field_sep (i);
1282      fold_toupper[i] = toupper (i);
1283    }
1284
1285#if HAVE_NL_LANGINFO
1286  /* If we're not in the "C" locale, read different names for months.  */
1287  if (hard_LC_TIME)
1288    {
1289      for (i = 0; i < MONTHS_PER_YEAR; i++)
1290        {
1291          char const *s;
1292          size_t s_len;
1293          size_t j, k;
1294          char *name;
1295
1296          s = nl_langinfo (ABMON_1 + i);
1297          s_len = strlen (s);
1298          monthtab[i].name = name = xmalloc (s_len + 1);
1299          monthtab[i].val = i + 1;
1300
1301          for (j = k = 0; j < s_len; j++)
1302            if (! isblank (to_uchar (s[j])))
1303              name[k++] = fold_toupper[to_uchar (s[j])];
1304          name[k] = '\0';
1305        }
1306      qsort (monthtab, MONTHS_PER_YEAR, sizeof *monthtab, struct_month_cmp);
1307    }
1308#endif
1309}
1310
1311/* Specify how many inputs may be merged at once.
1312   This may be set on the command-line with the
1313   --batch-size option. */
1314static void
1315specify_nmerge (int oi, char c, char const *s)
1316{
1317  uintmax_t n;
1318  struct rlimit rlimit;
1319  enum strtol_error e = xstrtoumax (s, NULL, 10, &n, NULL);
1320
1321  /* Try to find out how many file descriptors we'll be able
1322     to open.  We need at least nmerge + 3 (STDIN_FILENO,
1323     STDOUT_FILENO and STDERR_FILENO). */
1324  unsigned int max_nmerge = ((getrlimit (RLIMIT_NOFILE, &rlimit) == 0
1325                              ? rlimit.rlim_cur
1326                              : OPEN_MAX)
1327                             - 3);
1328
1329  if (e == LONGINT_OK)
1330    {
1331      nmerge = n;
1332      if (nmerge != n)
1333        e = LONGINT_OVERFLOW;
1334      else
1335        {
1336          if (nmerge < 2)
1337            {
1338              error (0, 0, _("invalid --%s argument %s"),
1339                     long_options[oi].name, quote (s));
1340              die (SORT_FAILURE, 0,
1341                   _("minimum --%s argument is %s"),
1342                   long_options[oi].name, quote ("2"));
1343            }
1344          else if (max_nmerge < nmerge)
1345            {
1346              e = LONGINT_OVERFLOW;
1347            }
1348          else
1349            return;
1350        }
1351    }
1352
1353  if (e == LONGINT_OVERFLOW)
1354    {
1355      char max_nmerge_buf[INT_BUFSIZE_BOUND (max_nmerge)];
1356      error (0, 0, _("--%s argument %s too large"),
1357             long_options[oi].name, quote (s));
1358      die (SORT_FAILURE, 0,
1359           _("maximum --%s argument with current rlimit is %s"),
1360           long_options[oi].name,
1361           uinttostr (max_nmerge, max_nmerge_buf));
1362    }
1363  else
1364    xstrtol_fatal (e, oi, c, long_options, s);
1365}
1366
1367/* Specify the amount of main memory to use when sorting.  */
1368static void
1369specify_sort_size (int oi, char c, char const *s)
1370{
1371  uintmax_t n;
1372  char *suffix;
1373  enum strtol_error e = xstrtoumax (s, &suffix, 10, &n, "EgGkKmMPtTYZ");
1374
1375  /* The default unit is KiB.  */
1376  if (e == LONGINT_OK && ISDIGIT (suffix[-1]))
1377    {
1378      if (n <= UINTMAX_MAX / 1024)
1379        n *= 1024;
1380      else
1381        e = LONGINT_OVERFLOW;
1382    }
1383
1384  /* A 'b' suffix means bytes; a '%' suffix means percent of memory.  */
1385  if (e == LONGINT_INVALID_SUFFIX_CHAR && ISDIGIT (suffix[-1]) && ! suffix[1])
1386    switch (suffix[0])
1387      {
1388      case 'b':
1389        e = LONGINT_OK;
1390        break;
1391
1392      case '%':
1393        {
1394          double mem = physmem_total () * n / 100;
1395
1396          /* Use "<", not "<=", to avoid problems with rounding.  */
1397          if (mem < UINTMAX_MAX)
1398            {
1399              n = mem;
1400              e = LONGINT_OK;
1401            }
1402          else
1403            e = LONGINT_OVERFLOW;
1404        }
1405        break;
1406      }
1407
1408  if (e == LONGINT_OK)
1409    {
1410      /* If multiple sort sizes are specified, take the maximum, so
1411         that option order does not matter.  */
1412      if (n < sort_size)
1413        return;
1414
1415      sort_size = n;
1416      if (sort_size == n)
1417        {
1418          sort_size = MAX (sort_size, MIN_SORT_SIZE);
1419          return;
1420        }
1421
1422      e = LONGINT_OVERFLOW;
1423    }
1424
1425  xstrtol_fatal (e, oi, c, long_options, s);
1426}
1427
1428/* Specify the number of threads to spawn during internal sort.  */
1429static size_t
1430specify_nthreads (int oi, char c, char const *s)
1431{
1432  unsigned long int nthreads;
1433  enum strtol_error e = xstrtoul (s, NULL, 10, &nthreads, "");
1434  if (e == LONGINT_OVERFLOW)
1435    return SIZE_MAX;
1436  if (e != LONGINT_OK)
1437    xstrtol_fatal (e, oi, c, long_options, s);
1438  if (SIZE_MAX < nthreads)
1439    nthreads = SIZE_MAX;
1440  if (nthreads == 0)
1441    die (SORT_FAILURE, 0, _("number in parallel must be nonzero"));
1442  return nthreads;
1443}
1444
1445/* Return the default sort size.  */
1446static size_t
1447default_sort_size (void)
1448{
1449  /* Let SIZE be MEM, but no more than the maximum object size,
1450     total memory, or system resource limits.  Don't bother to check
1451     for values like RLIM_INFINITY since in practice they are not much
1452     less than SIZE_MAX.  */
1453  size_t size = SIZE_MAX;
1454  struct rlimit rlimit;
1455  if (getrlimit (RLIMIT_DATA, &rlimit) == 0 && rlimit.rlim_cur < size)
1456    size = rlimit.rlim_cur;
1457#ifdef RLIMIT_AS
1458  if (getrlimit (RLIMIT_AS, &rlimit) == 0 && rlimit.rlim_cur < size)
1459    size = rlimit.rlim_cur;
1460#endif
1461
1462  /* Leave a large safety margin for the above limits, as failure can
1463     occur when they are exceeded.  */
1464  size /= 2;
1465
1466#ifdef RLIMIT_RSS
1467  /* Leave a 1/16 margin for RSS to leave room for code, stack, etc.
1468     Exceeding RSS is not fatal, but can be quite slow.  */
1469  if (getrlimit (RLIMIT_RSS, &rlimit) == 0 && rlimit.rlim_cur / 16 * 15 < size)
1470    size = rlimit.rlim_cur / 16 * 15;
1471#endif
1472
1473  /* Let MEM be available memory or 1/8 of total memory, whichever
1474     is greater.  */
1475  double avail = physmem_available ();
1476  double total = physmem_total ();
1477  double mem = MAX (avail, total / 8);
1478
1479  /* Leave a 1/4 margin for physical memory.  */
1480  if (total * 0.75 < size)
1481    size = total * 0.75;
1482
1483  /* Return the minimum of MEM and SIZE, but no less than
1484     MIN_SORT_SIZE.  Avoid the MIN macro here, as it is not quite
1485     right when only one argument is floating point.  */
1486  if (mem < size)
1487    size = mem;
1488  return MAX (size, MIN_SORT_SIZE);
1489}
1490
1491/* Return the sort buffer size to use with the input files identified
1492   by FPS and FILES, which are alternate names of the same files.
1493   NFILES gives the number of input files; NFPS may be less.  Assume
1494   that each input line requires LINE_BYTES extra bytes' worth of line
1495   information.  Do not exceed the size bound specified by the user
1496   (or a default size bound, if the user does not specify one).  */
1497
1498static size_t
1499sort_buffer_size (FILE *const *fps, size_t nfps,
1500                  char *const *files, size_t nfiles,
1501                  size_t line_bytes)
1502{
1503  /* A bound on the input size.  If zero, the bound hasn't been
1504     determined yet.  */
1505  static size_t size_bound;
1506
1507  /* In the worst case, each input byte is a newline.  */
1508  size_t worst_case_per_input_byte = line_bytes + 1;
1509
1510  /* Keep enough room for one extra input line and an extra byte.
1511     This extra room might be needed when preparing to read EOF.  */
1512  size_t size = worst_case_per_input_byte + 1;
1513
1514  for (size_t i = 0; i < nfiles; i++)
1515    {
1516      struct stat st;
1517      off_t file_size;
1518      size_t worst_case;
1519
1520      if ((i < nfps ? fstat (fileno (fps[i]), &st)
1521           : STREQ (files[i], "-") ? fstat (STDIN_FILENO, &st)
1522           : stat (files[i], &st))
1523          != 0)
1524        sort_die (_("stat failed"), files[i]);
1525
1526      if (S_ISREG (st.st_mode))
1527        file_size = st.st_size;
1528      else
1529        {
1530          /* The file has unknown size.  If the user specified a sort
1531             buffer size, use that; otherwise, guess the size.  */
1532          if (sort_size)
1533            return sort_size;
1534          file_size = INPUT_FILE_SIZE_GUESS;
1535        }
1536
1537      if (! size_bound)
1538        {
1539          size_bound = sort_size;
1540          if (! size_bound)
1541            size_bound = default_sort_size ();
1542        }
1543
1544      /* Add the amount of memory needed to represent the worst case
1545         where the input consists entirely of newlines followed by a
1546         single non-newline.  Check for overflow.  */
1547      worst_case = file_size * worst_case_per_input_byte + 1;
1548      if (file_size != worst_case / worst_case_per_input_byte
1549          || size_bound - size <= worst_case)
1550        return size_bound;
1551      size += worst_case;
1552    }
1553
1554  return size;
1555}
1556
1557/* Initialize BUF.  Reserve LINE_BYTES bytes for each line; LINE_BYTES
1558   must be at least sizeof (struct line).  Allocate ALLOC bytes
1559   initially.  */
1560
1561static void
1562initbuf (struct buffer *buf, size_t line_bytes, size_t alloc)
1563{
1564  /* Ensure that the line array is properly aligned.  If the desired
1565     size cannot be allocated, repeatedly halve it until allocation
1566     succeeds.  The smaller allocation may hurt overall performance,
1567     but that's better than failing.  */
1568  while (true)
1569    {
1570      alloc += sizeof (struct line) - alloc % sizeof (struct line);
1571      buf->buf = malloc (alloc);
1572      if (buf->buf)
1573        break;
1574      alloc /= 2;
1575      if (alloc <= line_bytes + 1)
1576        xalloc_die ();
1577    }
1578
1579  buf->line_bytes = line_bytes;
1580  buf->alloc = alloc;
1581  buf->used = buf->left = buf->nlines = 0;
1582  buf->eof = false;
1583}
1584
1585/* Return one past the limit of the line array.  */
1586
1587static inline struct line *
1588buffer_linelim (struct buffer const *buf)
1589{
1590  void *linelim = buf->buf + buf->alloc;
1591  return linelim;
1592}
1593
1594/* Return a pointer to the first character of the field specified
1595   by KEY in LINE. */
1596
1597static char *
1598begfield (struct line const *line, struct keyfield const *key)
1599{
1600  char *ptr = line->text, *lim = ptr + line->length - 1;
1601  size_t sword = key->sword;
1602  size_t schar = key->schar;
1603
1604  /* The leading field separator itself is included in a field when -t
1605     is absent.  */
1606
1607  if (tab != TAB_DEFAULT)
1608    while (ptr < lim && sword--)
1609      {
1610        while (ptr < lim && *ptr != tab)
1611          ++ptr;
1612        if (ptr < lim)
1613          ++ptr;
1614      }
1615  else
1616    while (ptr < lim && sword--)
1617      {
1618        while (ptr < lim && blanks[to_uchar (*ptr)])
1619          ++ptr;
1620        while (ptr < lim && !blanks[to_uchar (*ptr)])
1621          ++ptr;
1622      }
1623
1624  /* If we're ignoring leading blanks when computing the Start
1625     of the field, skip past them here.  */
1626  if (key->skipsblanks)
1627    while (ptr < lim && blanks[to_uchar (*ptr)])
1628      ++ptr;
1629
1630  /* Advance PTR by SCHAR (if possible), but no further than LIM.  */
1631  ptr = MIN (lim, ptr + schar);
1632
1633  return ptr;
1634}
1635
1636/* Return the limit of (a pointer to the first character after) the field
1637   in LINE specified by KEY. */
1638
1639static char *
1640limfield (struct line const *line, struct keyfield const *key)
1641{
1642  char *ptr = line->text, *lim = ptr + line->length - 1;
1643  size_t eword = key->eword, echar = key->echar;
1644
1645  if (echar == 0)
1646    eword++; /* Skip all of end field.  */
1647
1648  /* Move PTR past EWORD fields or to one past the last byte on LINE,
1649     whichever comes first.  If there are more than EWORD fields, leave
1650     PTR pointing at the beginning of the field having zero-based index,
1651     EWORD.  If a delimiter character was specified (via -t), then that
1652     'beginning' is the first character following the delimiting TAB.
1653     Otherwise, leave PTR pointing at the first 'blank' character after
1654     the preceding field.  */
1655  if (tab != TAB_DEFAULT)
1656    while (ptr < lim && eword--)
1657      {
1658        while (ptr < lim && *ptr != tab)
1659          ++ptr;
1660        if (ptr < lim && (eword || echar))
1661          ++ptr;
1662      }
1663  else
1664    while (ptr < lim && eword--)
1665      {
1666        while (ptr < lim && blanks[to_uchar (*ptr)])
1667          ++ptr;
1668        while (ptr < lim && !blanks[to_uchar (*ptr)])
1669          ++ptr;
1670      }
1671
1672#ifdef POSIX_UNSPECIFIED
1673  /* The following block of code makes GNU sort incompatible with
1674     standard Unix sort, so it's ifdef'd out for now.
1675     The POSIX spec isn't clear on how to interpret this.
1676     FIXME: request clarification.
1677
1678     From: kwzh@gnu.ai.mit.edu (Karl Heuer)
1679     Date: Thu, 30 May 96 12:20:41 -0400
1680     [Translated to POSIX 1003.1-2001 terminology by Paul Eggert.]
1681
1682     [...]I believe I've found another bug in 'sort'.
1683
1684     $ cat /tmp/sort.in
1685     a b c 2 d
1686     pq rs 1 t
1687     $ textutils-1.15/src/sort -k1.7,1.7 </tmp/sort.in
1688     a b c 2 d
1689     pq rs 1 t
1690     $ /bin/sort -k1.7,1.7 </tmp/sort.in
1691     pq rs 1 t
1692     a b c 2 d
1693
1694     Unix sort produced the answer I expected: sort on the single character
1695     in column 7.  GNU sort produced different results, because it disagrees
1696     on the interpretation of the key-end spec "M.N".  Unix sort reads this
1697     as "skip M-1 fields, then N-1 characters"; but GNU sort wants it to mean
1698     "skip M-1 fields, then either N-1 characters or the rest of the current
1699     field, whichever comes first".  This extra clause applies only to
1700     key-ends, not key-starts.
1701     */
1702
1703  /* Make LIM point to the end of (one byte past) the current field.  */
1704  if (tab != TAB_DEFAULT)
1705    {
1706      char *newlim;
1707      newlim = memchr (ptr, tab, lim - ptr);
1708      if (newlim)
1709        lim = newlim;
1710    }
1711  else
1712    {
1713      char *newlim;
1714      newlim = ptr;
1715      while (newlim < lim && blanks[to_uchar (*newlim)])
1716        ++newlim;
1717      while (newlim < lim && !blanks[to_uchar (*newlim)])
1718        ++newlim;
1719      lim = newlim;
1720    }
1721#endif
1722
1723  if (echar != 0) /* We need to skip over a portion of the end field.  */
1724    {
1725      /* If we're ignoring leading blanks when computing the End
1726         of the field, skip past them here.  */
1727      if (key->skipeblanks)
1728        while (ptr < lim && blanks[to_uchar (*ptr)])
1729          ++ptr;
1730
1731      /* Advance PTR by ECHAR (if possible), but no further than LIM.  */
1732      ptr = MIN (lim, ptr + echar);
1733    }
1734
1735  return ptr;
1736}
1737
1738/* Fill BUF reading from FP, moving buf->left bytes from the end
1739   of buf->buf to the beginning first.  If EOF is reached and the
1740   file wasn't terminated by a newline, supply one.  Set up BUF's line
1741   table too.  FILE is the name of the file corresponding to FP.
1742   Return true if some input was read.  */
1743
1744static bool
1745fillbuf (struct buffer *buf, FILE *fp, char const *file)
1746{
1747  struct keyfield const *key = keylist;
1748  char eol = eolchar;
1749  size_t line_bytes = buf->line_bytes;
1750  size_t mergesize = merge_buffer_size - MIN_MERGE_BUFFER_SIZE;
1751
1752  if (buf->eof)
1753    return false;
1754
1755  if (buf->used != buf->left)
1756    {
1757      memmove (buf->buf, buf->buf + buf->used - buf->left, buf->left);
1758      buf->used = buf->left;
1759      buf->nlines = 0;
1760    }
1761
1762  while (true)
1763    {
1764      char *ptr = buf->buf + buf->used;
1765      struct line *linelim = buffer_linelim (buf);
1766      struct line *line = linelim - buf->nlines;
1767      size_t avail = (char *) linelim - buf->nlines * line_bytes - ptr;
1768      char *line_start = buf->nlines ? line->text + line->length : buf->buf;
1769
1770      while (line_bytes + 1 < avail)
1771        {
1772          /* Read as many bytes as possible, but do not read so many
1773             bytes that there might not be enough room for the
1774             corresponding line array.  The worst case is when the
1775             rest of the input file consists entirely of newlines,
1776             except that the last byte is not a newline.  */
1777          size_t readsize = (avail - 1) / (line_bytes + 1);
1778          size_t bytes_read = fread (ptr, 1, readsize, fp);
1779          char *ptrlim = ptr + bytes_read;
1780          char *p;
1781          avail -= bytes_read;
1782
1783          if (bytes_read != readsize)
1784            {
1785              if (ferror (fp))
1786                sort_die (_("read failed"), file);
1787              if (feof (fp))
1788                {
1789                  buf->eof = true;
1790                  if (buf->buf == ptrlim)
1791                    return false;
1792                  if (line_start != ptrlim && ptrlim[-1] != eol)
1793                    *ptrlim++ = eol;
1794                }
1795            }
1796
1797          /* Find and record each line in the just-read input.  */
1798          while ((p = memchr (ptr, eol, ptrlim - ptr)))
1799            {
1800              /* Delimit the line with NUL. This eliminates the need to
1801                 temporarily replace the last byte with NUL when calling
1802                 xmemcoll(), which increases performance.  */
1803              *p = '\0';
1804              ptr = p + 1;
1805              line--;
1806              line->text = line_start;
1807              line->length = ptr - line_start;
1808              mergesize = MAX (mergesize, line->length);
1809              avail -= line_bytes;
1810
1811              if (key)
1812                {
1813                  /* Precompute the position of the first key for
1814                     efficiency.  */
1815                  line->keylim = (key->eword == SIZE_MAX
1816                                  ? p
1817                                  : limfield (line, key));
1818
1819                  if (key->sword != SIZE_MAX)
1820                    line->keybeg = begfield (line, key);
1821                  else
1822                    {
1823                      if (key->skipsblanks)
1824                        while (blanks[to_uchar (*line_start)])
1825                          line_start++;
1826                      line->keybeg = line_start;
1827                    }
1828                }
1829
1830              line_start = ptr;
1831            }
1832
1833          ptr = ptrlim;
1834          if (buf->eof)
1835            break;
1836        }
1837
1838      buf->used = ptr - buf->buf;
1839      buf->nlines = buffer_linelim (buf) - line;
1840      if (buf->nlines != 0)
1841        {
1842          buf->left = ptr - line_start;
1843          merge_buffer_size = mergesize + MIN_MERGE_BUFFER_SIZE;
1844          return true;
1845        }
1846
1847      {
1848        /* The current input line is too long to fit in the buffer.
1849           Increase the buffer size and try again, keeping it properly
1850           aligned.  */
1851        size_t line_alloc = buf->alloc / sizeof (struct line);
1852        buf->buf = x2nrealloc (buf->buf, &line_alloc, sizeof (struct line));
1853        buf->alloc = line_alloc * sizeof (struct line);
1854      }
1855    }
1856}
1857
1858/* Table that maps characters to order-of-magnitude values.  */
1859static char const unit_order[UCHAR_LIM] =
1860  {
1861#if ! ('K' == 75 && 'M' == 77 && 'G' == 71 && 'T' == 84 && 'P' == 80 \
1862     && 'E' == 69 && 'Z' == 90 && 'Y' == 89 && 'k' == 107)
1863    /* This initializer syntax works on all C99 hosts.  For now, use
1864       it only on non-ASCII hosts, to ease the pain of porting to
1865       pre-C99 ASCII hosts.  */
1866    ['K']=1, ['M']=2, ['G']=3, ['T']=4, ['P']=5, ['E']=6, ['Z']=7, ['Y']=8,
1867    ['k']=1,
1868#else
1869    /* Generate the following table with this command:
1870       perl -e 'my %a=(k=>1, K=>1, M=>2, G=>3, T=>4, P=>5, E=>6, Z=>7, Y=>8);
1871       foreach my $i (0..255) {my $c=chr($i); $a{$c} ||= 0;print "$a{$c}, "}'\
1872       |fmt  */
1873    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1874    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1875    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 0, 3,
1876    0, 0, 0, 1, 0, 2, 0, 0, 5, 0, 0, 0, 4, 0, 0, 0, 0, 8, 7, 0, 0, 0, 0, 0,
1877    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1878    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1879    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1880    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1881    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1882    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1883    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
1884#endif
1885  };
1886
1887/* Traverse number given as *number consisting of digits, thousands_sep, and
1888   decimal_point chars only.  Returns the highest digit found in the number,
1889   or '\0' if no digit has been found.  Upon return *number points at the
1890   character that immediately follows after the given number.  */
1891static unsigned char
1892traverse_raw_number (char const **number)
1893{
1894  char const *p = *number;
1895  unsigned char ch;
1896  unsigned char max_digit = '\0';
1897  bool ends_with_thousands_sep = false;
1898
1899  /* Scan to end of number.
1900     Decimals or separators not followed by digits stop the scan.
1901     Numbers ending in decimals or separators are thus considered
1902     to be lacking in units.
1903     FIXME: add support for multibyte thousands_sep and decimal_point.  */
1904
1905  while (ISDIGIT (ch = *p++))
1906    {
1907      if (max_digit < ch)
1908        max_digit = ch;
1909
1910      /* Allow to skip only one occurrence of thousands_sep to avoid finding
1911         the unit in the next column in case thousands_sep matches as blank
1912         and is used as column delimiter.  */
1913      ends_with_thousands_sep = (*p == thousands_sep);
1914      if (ends_with_thousands_sep)
1915        ++p;
1916    }
1917
1918  if (ends_with_thousands_sep)
1919    {
1920      /* thousands_sep not followed by digit is not allowed.  */
1921      *number = p - 2;
1922      return max_digit;
1923    }
1924
1925  if (ch == decimal_point)
1926    while (ISDIGIT (ch = *p++))
1927      if (max_digit < ch)
1928        max_digit = ch;
1929
1930  *number = p - 1;
1931  return max_digit;
1932}
1933
1934/* Return an integer that represents the order of magnitude of the
1935   unit following the number.  The number may contain thousands
1936   separators and a decimal point, but it may not contain leading blanks.
1937   Negative numbers get negative orders; zero numbers have a zero order.  */
1938
1939static int _GL_ATTRIBUTE_PURE
1940find_unit_order (char const *number)
1941{
1942  bool minus_sign = (*number == '-');
1943  char const *p = number + minus_sign;
1944  unsigned char max_digit = traverse_raw_number (&p);
1945  if ('0' < max_digit)
1946    {
1947      unsigned char ch = *p;
1948      int order = unit_order[ch];
1949      return (minus_sign ? -order : order);
1950    }
1951  else
1952    return 0;
1953}
1954
1955/* Compare numbers A and B ending in units with SI or IEC prefixes
1956       <none/unknown> < K/k < M < G < T < P < E < Z < Y  */
1957
1958static int
1959human_numcompare (char const *a, char const *b)
1960{
1961  while (blanks[to_uchar (*a)])
1962    a++;
1963  while (blanks[to_uchar (*b)])
1964    b++;
1965
1966  int diff = find_unit_order (a) - find_unit_order (b);
1967  return (diff ? diff : strnumcmp (a, b, decimal_point, thousands_sep));
1968}
1969
1970/* Compare strings A and B as numbers without explicitly converting them to
1971   machine numbers.  Comparatively slow for short strings, but asymptotically
1972   hideously fast. */
1973
1974static int
1975numcompare (char const *a, char const *b)
1976{
1977  while (blanks[to_uchar (*a)])
1978    a++;
1979  while (blanks[to_uchar (*b)])
1980    b++;
1981
1982  return strnumcmp (a, b, decimal_point, thousands_sep);
1983}
1984
1985/* Work around a problem whereby the long double value returned by glibc's
1986   strtold ("NaN", ...) contains uninitialized bits: clear all bytes of
1987   A and B before calling strtold.  FIXME: remove this function once
1988   gnulib guarantees that strtold's result is always well defined.  */
1989static int
1990nan_compare (char const *sa, char const *sb)
1991{
1992  long_double a;
1993  memset (&a, 0, sizeof a);
1994  a = strtold (sa, NULL);
1995
1996  long_double b;
1997  memset (&b, 0, sizeof b);
1998  b = strtold (sb, NULL);
1999
2000  return memcmp (&a, &b, sizeof a);
2001}
2002
2003static int
2004general_numcompare (char const *sa, char const *sb)
2005{
2006  /* FIXME: maybe add option to try expensive FP conversion
2007     only if A and B can't be compared more cheaply/accurately.  */
2008
2009  char *ea;
2010  char *eb;
2011  long_double a = strtold (sa, &ea);
2012  long_double b = strtold (sb, &eb);
2013
2014  /* Put conversion errors at the start of the collating sequence.  */
2015  if (sa == ea)
2016    return sb == eb ? 0 : -1;
2017  if (sb == eb)
2018    return 1;
2019
2020  /* Sort numbers in the usual way, where -0 == +0.  Put NaNs after
2021     conversion errors but before numbers; sort them by internal
2022     bit-pattern, for lack of a more portable alternative.  */
2023  return (a < b ? -1
2024          : a > b ? 1
2025          : a == b ? 0
2026          : b == b ? -1
2027          : a == a ? 1
2028          : nan_compare (sa, sb));
2029}
2030
2031/* Return an integer in 1..12 of the month name MONTH.
2032   Return 0 if the name in S is not recognized.  */
2033
2034static int
2035getmonth (char const *month, char **ea)
2036{
2037  size_t lo = 0;
2038  size_t hi = MONTHS_PER_YEAR;
2039
2040  while (blanks[to_uchar (*month)])
2041    month++;
2042
2043  do
2044    {
2045      size_t ix = (lo + hi) / 2;
2046      char const *m = month;
2047      char const *n = monthtab[ix].name;
2048
2049      for (;; m++, n++)
2050        {
2051          if (!*n)
2052            {
2053              if (ea)
2054                *ea = (char *) m;
2055              return monthtab[ix].val;
2056            }
2057          if (to_uchar (fold_toupper[to_uchar (*m)]) < to_uchar (*n))
2058            {
2059              hi = ix;
2060              break;
2061            }
2062          else if (to_uchar (fold_toupper[to_uchar (*m)]) > to_uchar (*n))
2063            {
2064              lo = ix + 1;
2065              break;
2066            }
2067        }
2068    }
2069  while (lo < hi);
2070
2071  return 0;
2072}
2073
2074/* A randomly chosen MD5 state, used for random comparison.  */
2075static struct md5_ctx random_md5_state;
2076
2077/* Initialize the randomly chosen MD5 state.  */
2078
2079static void
2080random_md5_state_init (char const *random_source)
2081{
2082  unsigned char buf[MD5_DIGEST_SIZE];
2083  struct randread_source *r = randread_new (random_source, sizeof buf);
2084  if (! r)
2085    sort_die (_("open failed"), random_source);
2086  randread (r, buf, sizeof buf);
2087  if (randread_free (r) != 0)
2088    sort_die (_("close failed"), random_source);
2089  md5_init_ctx (&random_md5_state);
2090  md5_process_bytes (buf, sizeof buf, &random_md5_state);
2091}
2092
2093/* This is like strxfrm, except it reports any error and exits.  */
2094
2095static size_t
2096xstrxfrm (char *restrict dest, char const *restrict src, size_t destsize)
2097{
2098  errno = 0;
2099  size_t translated_size = strxfrm (dest, src, destsize);
2100
2101  if (errno)
2102    {
2103      error (0, errno, _("string transformation failed"));
2104      error (0, 0, _("set LC_ALL='C' to work around the problem"));
2105      die (SORT_FAILURE, 0,
2106           _("the untransformed string was %s"),
2107           quotearg_n_style (0, locale_quoting_style, src));
2108    }
2109
2110  return translated_size;
2111}
2112
2113/* Compare the keys TEXTA (of length LENA) and TEXTB (of length LENB)
2114   using one or more random hash functions.  TEXTA[LENA] and
2115   TEXTB[LENB] must be zero.  */
2116
2117static int
2118compare_random (char *restrict texta, size_t lena,
2119                char *restrict textb, size_t lenb)
2120{
2121  /* XFRM_DIFF records the equivalent of memcmp on the transformed
2122     data.  This is used to break ties if there is a checksum
2123     collision, and this is good enough given the astronomically low
2124     probability of a collision.  */
2125  int xfrm_diff = 0;
2126
2127  char stackbuf[4000];
2128  char *buf = stackbuf;
2129  size_t bufsize = sizeof stackbuf;
2130  void *allocated = NULL;
2131  uint32_t dig[2][MD5_DIGEST_SIZE / sizeof (uint32_t)];
2132  struct md5_ctx s[2];
2133  s[0] = s[1] = random_md5_state;
2134
2135  if (hard_LC_COLLATE)
2136    {
2137      char const *lima = texta + lena;
2138      char const *limb = textb + lenb;
2139
2140      while (true)
2141        {
2142          /* Transform the text into the basis of comparison, so that byte
2143             strings that would otherwise considered to be equal are
2144             considered equal here even if their bytes differ.
2145
2146             Each time through this loop, transform one
2147             null-terminated string's worth from TEXTA or from TEXTB
2148             or both.  That way, there's no need to store the
2149             transformation of the whole line, if it contains many
2150             null-terminated strings.  */
2151
2152          /* Store the transformed data into a big-enough buffer.  */
2153
2154          /* A 3X size guess avoids the overhead of calling strxfrm
2155             twice on typical implementations.  Don't worry about
2156             size_t overflow, as the guess need not be correct.  */
2157          size_t guess_bufsize = 3 * (lena + lenb) + 2;
2158          if (bufsize < guess_bufsize)
2159            {
2160              bufsize = MAX (guess_bufsize, bufsize * 3 / 2);
2161              free (allocated);
2162              buf = allocated = malloc (bufsize);
2163              if (! buf)
2164                {
2165                  buf = stackbuf;
2166                  bufsize = sizeof stackbuf;
2167                }
2168            }
2169
2170          size_t sizea =
2171            (texta < lima ? xstrxfrm (buf, texta, bufsize) + 1 : 0);
2172          bool a_fits = sizea <= bufsize;
2173          size_t sizeb =
2174            (textb < limb
2175             ? (xstrxfrm ((a_fits ? buf + sizea : NULL), textb,
2176                          (a_fits ? bufsize - sizea : 0))
2177                + 1)
2178             : 0);
2179
2180          if (! (a_fits && sizea + sizeb <= bufsize))
2181            {
2182              bufsize = sizea + sizeb;
2183              if (bufsize < SIZE_MAX / 3)
2184                bufsize = bufsize * 3 / 2;
2185              free (allocated);
2186              buf = allocated = xmalloc (bufsize);
2187              if (texta < lima)
2188                strxfrm (buf, texta, sizea);
2189              if (textb < limb)
2190                strxfrm (buf + sizea, textb, sizeb);
2191            }
2192
2193          /* Advance past NULs to the next part of each input string,
2194             exiting the loop if both strings are exhausted.  When
2195             exiting the loop, prepare to finish off the tiebreaker
2196             comparison properly.  */
2197          if (texta < lima)
2198            texta += strlen (texta) + 1;
2199          if (textb < limb)
2200            textb += strlen (textb) + 1;
2201          if (! (texta < lima || textb < limb))
2202            {
2203              lena = sizea; texta = buf;
2204              lenb = sizeb; textb = buf + sizea;
2205              break;
2206            }
2207
2208          /* Accumulate the transformed data in the corresponding
2209             checksums.  */
2210          md5_process_bytes (buf, sizea, &s[0]);
2211          md5_process_bytes (buf + sizea, sizeb, &s[1]);
2212
2213          /* Update the tiebreaker comparison of the transformed data.  */
2214          if (! xfrm_diff)
2215            {
2216              xfrm_diff = memcmp (buf, buf + sizea, MIN (sizea, sizeb));
2217              if (! xfrm_diff)
2218                xfrm_diff = (sizea > sizeb) - (sizea < sizeb);
2219            }
2220        }
2221    }
2222
2223  /* Compute and compare the checksums.  */
2224  md5_process_bytes (texta, lena, &s[0]); md5_finish_ctx (&s[0], dig[0]);
2225  md5_process_bytes (textb, lenb, &s[1]); md5_finish_ctx (&s[1], dig[1]);
2226  int diff = memcmp (dig[0], dig[1], sizeof dig[0]);
2227
2228  /* Fall back on the tiebreaker if the checksums collide.  */
2229  if (! diff)
2230    {
2231      if (! xfrm_diff)
2232        {
2233          xfrm_diff = memcmp (texta, textb, MIN (lena, lenb));
2234          if (! xfrm_diff)
2235            xfrm_diff = (lena > lenb) - (lena < lenb);
2236        }
2237
2238      diff = xfrm_diff;
2239    }
2240
2241  free (allocated);
2242
2243  return diff;
2244}
2245
2246/* Return the printable width of the block of memory starting at
2247   TEXT and ending just before LIM, counting each tab as one byte.
2248   FIXME: Should we generally be counting non printable chars?  */
2249
2250static size_t
2251debug_width (char const *text, char const *lim)
2252{
2253  size_t width = mbsnwidth (text, lim - text, 0);
2254  while (text < lim)
2255    width += (*text++ == '\t');
2256  return width;
2257}
2258
2259/* For debug mode, "underline" a key at the
2260   specified offset and screen width.  */
2261
2262static void
2263mark_key (size_t offset, size_t width)
2264{
2265  while (offset--)
2266    putchar (' ');
2267
2268  if (!width)
2269    printf (_("^ no match for key\n"));
2270  else
2271    {
2272      do
2273        putchar ('_');
2274      while (--width);
2275
2276      putchar ('\n');
2277    }
2278}
2279
2280/* Return true if KEY is a numeric key.  */
2281
2282static inline bool
2283key_numeric (struct keyfield const *key)
2284{
2285  return key->numeric || key->general_numeric || key->human_numeric;
2286}
2287
2288/* For LINE, output a debugging line that underlines KEY in LINE.
2289   If KEY is null, underline the whole line.  */
2290
2291static void
2292debug_key (struct line const *line, struct keyfield const *key)
2293{
2294  char *text = line->text;
2295  char *beg = text;
2296  char *lim = text + line->length - 1;
2297
2298  if (key)
2299    {
2300      if (key->sword != SIZE_MAX)
2301        beg = begfield (line, key);
2302      if (key->eword != SIZE_MAX)
2303        lim = limfield (line, key);
2304
2305      if ((key->skipsblanks && key->sword == SIZE_MAX)
2306          || key->month || key_numeric (key))
2307        {
2308          char saved = *lim;
2309          *lim = '\0';
2310
2311          while (blanks[to_uchar (*beg)])
2312            beg++;
2313
2314          char *tighter_lim = beg;
2315
2316          if (lim < beg)
2317            tighter_lim = lim;
2318          else if (key->month)
2319            getmonth (beg, &tighter_lim);
2320          else if (key->general_numeric)
2321            ignore_value (strtold (beg, &tighter_lim));
2322          else if (key->numeric || key->human_numeric)
2323            {
2324              char const *p = beg + (beg < lim && *beg == '-');
2325              unsigned char max_digit = traverse_raw_number (&p);
2326              if ('0' <= max_digit)
2327                {
2328                  unsigned char ch = *p;
2329                  tighter_lim = (char *) p
2330                    + (key->human_numeric && unit_order[ch]);
2331                }
2332            }
2333          else
2334            tighter_lim = lim;
2335
2336          *lim = saved;
2337          lim = tighter_lim;
2338        }
2339    }
2340
2341  size_t offset = debug_width (text, beg);
2342  size_t width = debug_width (beg, lim);
2343  mark_key (offset, width);
2344}
2345
2346/* Debug LINE by underlining its keys.  */
2347
2348static void
2349debug_line (struct line const *line)
2350{
2351  struct keyfield const *key = keylist;
2352
2353  do
2354    debug_key (line, key);
2355  while (key && ((key = key->next) || ! (unique || stable)));
2356}
2357
2358/* Return whether sorting options specified for key.  */
2359
2360static bool
2361default_key_compare (struct keyfield const *key)
2362{
2363  return ! (key->ignore
2364            || key->translate
2365            || key->skipsblanks
2366            || key->skipeblanks
2367            || key_numeric (key)
2368            || key->month
2369            || key->version
2370            || key->random
2371            /* || key->reverse */
2372           );
2373}
2374
2375/* Convert a key to the short options used to specify it.  */
2376
2377static void
2378key_to_opts (struct keyfield const *key, char *opts)
2379{
2380  if (key->skipsblanks || key->skipeblanks)
2381    *opts++ = 'b';/* either disables global -b  */
2382  if (key->ignore == nondictionary)
2383    *opts++ = 'd';
2384  if (key->translate)
2385    *opts++ = 'f';
2386  if (key->general_numeric)
2387    *opts++ = 'g';
2388  if (key->human_numeric)
2389    *opts++ = 'h';
2390  if (key->ignore == nonprinting)
2391    *opts++ = 'i';
2392  if (key->month)
2393    *opts++ = 'M';
2394  if (key->numeric)
2395    *opts++ = 'n';
2396  if (key->random)
2397    *opts++ = 'R';
2398  if (key->reverse)
2399    *opts++ = 'r';
2400  if (key->version)
2401    *opts++ = 'V';
2402  *opts = '\0';
2403}
2404
2405/* Output data independent key warnings to stderr.  */
2406
2407static void
2408key_warnings (struct keyfield const *gkey, bool gkey_only)
2409{
2410  struct keyfield const *key;
2411  struct keyfield ugkey = *gkey;
2412  unsigned long keynum = 1;
2413
2414  for (key = keylist; key; key = key->next, keynum++)
2415    {
2416      if (key->traditional_used)
2417        {
2418          size_t sword = key->sword;
2419          size_t eword = key->eword;
2420          char tmp[INT_BUFSIZE_BOUND (uintmax_t)];
2421          /* obsolescent syntax +A.x -B.y is equivalent to:
2422               -k A+1.x+1,B.y   (when y = 0)
2423               -k A+1.x+1,B+1.y (when y > 0)  */
2424          char obuf[INT_BUFSIZE_BOUND (sword) * 2 + 4]; /* +# -#  */
2425          char nbuf[INT_BUFSIZE_BOUND (sword) * 2 + 5]; /* -k #,#  */
2426          char *po = obuf;
2427          char *pn = nbuf;
2428
2429          if (sword == SIZE_MAX)
2430            sword++;
2431
2432          po = stpcpy (stpcpy (po, "+"), umaxtostr (sword, tmp));
2433          pn = stpcpy (stpcpy (pn, "-k "), umaxtostr (sword + 1, tmp));
2434          if (key->eword != SIZE_MAX)
2435            {
2436              stpcpy (stpcpy (po, " -"), umaxtostr (eword + 1, tmp));
2437              stpcpy (stpcpy (pn, ","),
2438                      umaxtostr (eword + 1
2439                                 + (key->echar == SIZE_MAX), tmp));
2440            }
2441          error (0, 0, _("obsolescent key %s used; consider %s instead"),
2442                 quote_n (0, obuf), quote_n (1, nbuf));
2443        }
2444
2445      /* Warn about field specs that will never match.  */
2446      bool zero_width = key->sword != SIZE_MAX && key->eword < key->sword;
2447      if (zero_width)
2448        error (0, 0, _("key %lu has zero width and will be ignored"), keynum);
2449
2450      /* Warn about significant leading blanks.  */
2451      bool implicit_skip = key_numeric (key) || key->month;
2452      bool line_offset = key->eword == 0 && key->echar != 0; /* -k1.x,1.y  */
2453      if (!zero_width && !gkey_only && tab == TAB_DEFAULT && !line_offset
2454          && ((!key->skipsblanks && !implicit_skip)
2455              || (!key->skipsblanks && key->schar)
2456              || (!key->skipeblanks && key->echar)))
2457        error (0, 0, _("leading blanks are significant in key %lu; "
2458                       "consider also specifying 'b'"), keynum);
2459
2460      /* Warn about numeric comparisons spanning fields,
2461         as field delimiters could be interpreted as part
2462         of the number (maybe only in other locales).  */
2463      if (!gkey_only && key_numeric (key))
2464        {
2465          size_t sword = key->sword + 1;
2466          size_t eword = key->eword + 1;
2467          if (!sword)
2468            sword++;
2469          if (!eword || sword < eword)
2470            error (0, 0, _("key %lu is numeric and spans multiple fields"),
2471                   keynum);
2472        }
2473
2474      /* Flag global options not copied or specified in any key.  */
2475      if (ugkey.ignore && (ugkey.ignore == key->ignore))
2476        ugkey.ignore = NULL;
2477      if (ugkey.translate && (ugkey.translate == key->translate))
2478        ugkey.translate = NULL;
2479      ugkey.skipsblanks &= !key->skipsblanks;
2480      ugkey.skipeblanks &= !key->skipeblanks;
2481      ugkey.month &= !key->month;
2482      ugkey.numeric &= !key->numeric;
2483      ugkey.general_numeric &= !key->general_numeric;
2484      ugkey.human_numeric &= !key->human_numeric;
2485      ugkey.random &= !key->random;
2486      ugkey.version &= !key->version;
2487      ugkey.reverse &= !key->reverse;
2488    }
2489
2490  /* Warn about ignored global options flagged above.
2491     Note if gkey is the only one in the list, all flags are cleared.  */
2492  if (!default_key_compare (&ugkey)
2493      || (ugkey.reverse && (stable || unique) && keylist))
2494    {
2495      bool ugkey_reverse = ugkey.reverse;
2496      if (!(stable || unique))
2497        ugkey.reverse = false;
2498      /* The following is too big, but guaranteed to be "big enough".  */
2499      char opts[sizeof short_options];
2500      key_to_opts (&ugkey, opts);
2501      error (0, 0,
2502             ngettext ("option '-%s' is ignored",
2503                       "options '-%s' are ignored",
2504                       select_plural (strlen (opts))), opts);
2505      ugkey.reverse = ugkey_reverse;
2506    }
2507  if (ugkey.reverse && !(stable || unique) && keylist)
2508    error (0, 0, _("option '-r' only applies to last-resort comparison"));
2509}
2510
2511/* Compare two lines A and B trying every key in sequence until there
2512   are no more keys or a difference is found. */
2513
2514static int
2515keycompare (struct line const *a, struct line const *b)
2516{
2517  struct keyfield *key = keylist;
2518
2519  /* For the first iteration only, the key positions have been
2520     precomputed for us. */
2521  char *texta = a->keybeg;
2522  char *textb = b->keybeg;
2523  char *lima = a->keylim;
2524  char *limb = b->keylim;
2525
2526  int diff;
2527
2528  while (true)
2529    {
2530      char const *translate = key->translate;
2531      bool const *ignore = key->ignore;
2532
2533      /* Treat field ends before field starts as empty fields.  */
2534      lima = MAX (texta, lima);
2535      limb = MAX (textb, limb);
2536
2537      /* Find the lengths. */
2538      size_t lena = lima - texta;
2539      size_t lenb = limb - textb;
2540
2541      if (hard_LC_COLLATE || key_numeric (key)
2542          || key->month || key->random || key->version)
2543        {
2544          char *ta;
2545          char *tb;
2546          size_t tlena;
2547          size_t tlenb;
2548
2549          char enda IF_LINT (= 0);
2550          char endb IF_LINT (= 0);
2551          void *allocated IF_LINT (= NULL);
2552          char stackbuf[4000];
2553
2554          if (ignore || translate)
2555            {
2556              /* Compute with copies of the keys, which are the result of
2557                 translating or ignoring characters, and which need their
2558                 own storage.  */
2559
2560              size_t i;
2561
2562              /* Allocate space for copies.  */
2563              size_t size = lena + 1 + lenb + 1;
2564              if (size <= sizeof stackbuf)
2565                ta = stackbuf, allocated = NULL;
2566              else
2567                ta = allocated = xmalloc (size);
2568              tb = ta + lena + 1;
2569
2570              /* Put into each copy a version of the key in which the
2571                 requested characters are ignored or translated.  */
2572              for (tlena = i = 0; i < lena; i++)
2573                if (! (ignore && ignore[to_uchar (texta[i])]))
2574                  ta[tlena++] = (translate
2575                                 ? translate[to_uchar (texta[i])]
2576                                 : texta[i]);
2577              ta[tlena] = '\0';
2578
2579              for (tlenb = i = 0; i < lenb; i++)
2580                if (! (ignore && ignore[to_uchar (textb[i])]))
2581                  tb[tlenb++] = (translate
2582                                 ? translate[to_uchar (textb[i])]
2583                                 : textb[i]);
2584              tb[tlenb] = '\0';
2585            }
2586          else
2587            {
2588              /* Use the keys in-place, temporarily null-terminated.  */
2589              ta = texta; tlena = lena; enda = ta[tlena]; ta[tlena] = '\0';
2590              tb = textb; tlenb = lenb; endb = tb[tlenb]; tb[tlenb] = '\0';
2591            }
2592
2593          if (key->numeric)
2594            diff = numcompare (ta, tb);
2595          else if (key->general_numeric)
2596            diff = general_numcompare (ta, tb);
2597          else if (key->human_numeric)
2598            diff = human_numcompare (ta, tb);
2599          else if (key->month)
2600            diff = getmonth (ta, NULL) - getmonth (tb, NULL);
2601          else if (key->random)
2602            diff = compare_random (ta, tlena, tb, tlenb);
2603          else if (key->version)
2604            diff = filevercmp (ta, tb);
2605          else
2606            {
2607              /* Locale-dependent string sorting.  This is slower than
2608                 C-locale sorting, which is implemented below.  */
2609              if (tlena == 0)
2610                diff = - NONZERO (tlenb);
2611              else if (tlenb == 0)
2612                diff = 1;
2613              else
2614                diff = xmemcoll0 (ta, tlena + 1, tb, tlenb + 1);
2615            }
2616
2617          if (ignore || translate)
2618            free (allocated);
2619          else
2620            {
2621              ta[tlena] = enda;
2622              tb[tlenb] = endb;
2623            }
2624        }
2625      else if (ignore)
2626        {
2627#define CMP_WITH_IGNORE(A, B)						\
2628  do									\
2629    {									\
2630          while (true)							\
2631            {								\
2632              while (texta < lima && ignore[to_uchar (*texta)])		\
2633                ++texta;						\
2634              while (textb < limb && ignore[to_uchar (*textb)])		\
2635                ++textb;						\
2636              if (! (texta < lima && textb < limb))			\
2637                break;							\
2638              diff = to_uchar (A) - to_uchar (B);			\
2639              if (diff)							\
2640                goto not_equal;						\
2641              ++texta;							\
2642              ++textb;							\
2643            }								\
2644                                                                        \
2645          diff = (texta < lima) - (textb < limb);			\
2646    }									\
2647  while (0)
2648
2649          if (translate)
2650            CMP_WITH_IGNORE (translate[to_uchar (*texta)],
2651                             translate[to_uchar (*textb)]);
2652          else
2653            CMP_WITH_IGNORE (*texta, *textb);
2654        }
2655      else if (lena == 0)
2656        diff = - NONZERO (lenb);
2657      else if (lenb == 0)
2658        goto greater;
2659      else
2660        {
2661          if (translate)
2662            {
2663              while (texta < lima && textb < limb)
2664                {
2665                  diff = (to_uchar (translate[to_uchar (*texta++)])
2666                          - to_uchar (translate[to_uchar (*textb++)]));
2667                  if (diff)
2668                    goto not_equal;
2669                }
2670            }
2671          else
2672            {
2673              diff = memcmp (texta, textb, MIN (lena, lenb));
2674              if (diff)
2675                goto not_equal;
2676            }
2677          diff = lena < lenb ? -1 : lena != lenb;
2678        }
2679
2680      if (diff)
2681        goto not_equal;
2682
2683      key = key->next;
2684      if (! key)
2685        break;
2686
2687      /* Find the beginning and limit of the next field.  */
2688      if (key->eword != SIZE_MAX)
2689        lima = limfield (a, key), limb = limfield (b, key);
2690      else
2691        lima = a->text + a->length - 1, limb = b->text + b->length - 1;
2692
2693      if (key->sword != SIZE_MAX)
2694        texta = begfield (a, key), textb = begfield (b, key);
2695      else
2696        {
2697          texta = a->text, textb = b->text;
2698          if (key->skipsblanks)
2699            {
2700              while (texta < lima && blanks[to_uchar (*texta)])
2701                ++texta;
2702              while (textb < limb && blanks[to_uchar (*textb)])
2703                ++textb;
2704            }
2705        }
2706    }
2707
2708  return 0;
2709
2710 greater:
2711  diff = 1;
2712 not_equal:
2713  return key->reverse ? -diff : diff;
2714}
2715
2716/* Compare two lines A and B, returning negative, zero, or positive
2717   depending on whether A compares less than, equal to, or greater than B. */
2718
2719static int
2720compare (struct line const *a, struct line const *b)
2721{
2722  int diff;
2723  size_t alen, blen;
2724
2725  /* First try to compare on the specified keys (if any).
2726     The only two cases with no key at all are unadorned sort,
2727     and unadorned sort -r. */
2728  if (keylist)
2729    {
2730      diff = keycompare (a, b);
2731      if (diff || unique || stable)
2732        return diff;
2733    }
2734
2735  /* If the keys all compare equal (or no keys were specified)
2736     fall through to the default comparison.  */
2737  alen = a->length - 1, blen = b->length - 1;
2738
2739  if (alen == 0)
2740    diff = - NONZERO (blen);
2741  else if (blen == 0)
2742    diff = 1;
2743  else if (hard_LC_COLLATE)
2744    {
2745      /* Note xmemcoll0 is a performance enhancement as
2746         it will not unconditionally write '\0' after the
2747         passed in buffers, which was seen to give around
2748         a 3% increase in performance for short lines.  */
2749      diff = xmemcoll0 (a->text, alen + 1, b->text, blen + 1);
2750    }
2751  else if (! (diff = memcmp (a->text, b->text, MIN (alen, blen))))
2752    diff = alen < blen ? -1 : alen != blen;
2753
2754  return reverse ? -diff : diff;
2755}
2756
2757/* Write LINE to output stream FP; the output file's name is
2758   OUTPUT_FILE if OUTPUT_FILE is non-null, and is the standard output
2759   otherwise.  If debugging is enabled and FP is standard output,
2760   append some debugging information.  */
2761
2762static void
2763write_line (struct line const *line, FILE *fp, char const *output_file)
2764{
2765  char *buf = line->text;
2766  size_t n_bytes = line->length;
2767  char *ebuf = buf + n_bytes;
2768
2769  if (!output_file && debug)
2770    {
2771      /* Convert TAB to '>' and EOL to \n, and then output debugging info.  */
2772      char const *c = buf;
2773
2774      while (c < ebuf)
2775        {
2776          char wc = *c++;
2777          if (wc == '\t')
2778            wc = '>';
2779          else if (c == ebuf)
2780            wc = '\n';
2781          if (fputc (wc, fp) == EOF)
2782            sort_die (_("write failed"), output_file);
2783        }
2784
2785      debug_line (line);
2786    }
2787  else
2788    {
2789      ebuf[-1] = eolchar;
2790      if (fwrite (buf, 1, n_bytes, fp) != n_bytes)
2791        sort_die (_("write failed"), output_file);
2792      ebuf[-1] = '\0';
2793    }
2794}
2795
2796/* Check that the lines read from FILE_NAME come in order.  Return
2797   true if they are in order.  If CHECKONLY == 'c', also print a
2798   diagnostic (FILE_NAME, line number, contents of line) to stderr if
2799   they are not in order.  */
2800
2801static bool
2802check (char const *file_name, char checkonly)
2803{
2804  FILE *fp = xfopen (file_name, "r");
2805  struct buffer buf;		/* Input buffer. */
2806  struct line temp;		/* Copy of previous line. */
2807  size_t alloc = 0;
2808  uintmax_t line_number = 0;
2809  struct keyfield const *key = keylist;
2810  bool nonunique = ! unique;
2811  bool ordered = true;
2812
2813  initbuf (&buf, sizeof (struct line),
2814           MAX (merge_buffer_size, sort_size));
2815  temp.text = NULL;
2816
2817  while (fillbuf (&buf, fp, file_name))
2818    {
2819      struct line const *line = buffer_linelim (&buf);
2820      struct line const *linebase = line - buf.nlines;
2821
2822      /* Make sure the line saved from the old buffer contents is
2823         less than or equal to the first line of the new buffer. */
2824      if (alloc && nonunique <= compare (&temp, line - 1))
2825        {
2826        found_disorder:
2827          {
2828            if (checkonly == 'c')
2829              {
2830                struct line const *disorder_line = line - 1;
2831                uintmax_t disorder_line_number =
2832                  buffer_linelim (&buf) - disorder_line + line_number;
2833                char hr_buf[INT_BUFSIZE_BOUND (disorder_line_number)];
2834                fprintf (stderr, _("%s: %s:%s: disorder: "),
2835                         program_name, file_name,
2836                         umaxtostr (disorder_line_number, hr_buf));
2837                write_line (disorder_line, stderr, _("standard error"));
2838              }
2839
2840            ordered = false;
2841            break;
2842          }
2843        }
2844
2845      /* Compare each line in the buffer with its successor.  */
2846      while (linebase < --line)
2847        if (nonunique <= compare (line, line - 1))
2848          goto found_disorder;
2849
2850      line_number += buf.nlines;
2851
2852      /* Save the last line of the buffer.  */
2853      if (alloc < line->length)
2854        {
2855          do
2856            {
2857              alloc *= 2;
2858              if (! alloc)
2859                {
2860                  alloc = line->length;
2861                  break;
2862                }
2863            }
2864          while (alloc < line->length);
2865
2866          free (temp.text);
2867          temp.text = xmalloc (alloc);
2868        }
2869      memcpy (temp.text, line->text, line->length);
2870      temp.length = line->length;
2871      if (key)
2872        {
2873          temp.keybeg = temp.text + (line->keybeg - line->text);
2874          temp.keylim = temp.text + (line->keylim - line->text);
2875        }
2876    }
2877
2878  xfclose (fp, file_name);
2879  free (buf.buf);
2880  free (temp.text);
2881  return ordered;
2882}
2883
2884/* Open FILES (there are NFILES of them) and store the resulting array
2885   of stream pointers into (*PFPS).  Allocate the array.  Return the
2886   number of successfully opened files, setting errno if this value is
2887   less than NFILES.  */
2888
2889static size_t
2890open_input_files (struct sortfile *files, size_t nfiles, FILE ***pfps)
2891{
2892  FILE **fps = *pfps = xnmalloc (nfiles, sizeof *fps);
2893  int i;
2894
2895  /* Open as many input files as we can.  */
2896  for (i = 0; i < nfiles; i++)
2897    {
2898      fps[i] = (files[i].temp && files[i].temp->state != UNCOMPRESSED
2899                ? open_temp (files[i].temp)
2900                : stream_open (files[i].name, "r"));
2901      if (!fps[i])
2902        break;
2903    }
2904
2905  return i;
2906}
2907
2908/* Merge lines from FILES onto OFP.  NTEMPS is the number of temporary
2909   files (all of which are at the start of the FILES array), and
2910   NFILES is the number of files; 0 <= NTEMPS <= NFILES <= NMERGE.
2911   FPS is the vector of open stream corresponding to the files.
2912   Close input and output streams before returning.
2913   OUTPUT_FILE gives the name of the output file.  If it is NULL,
2914   the output file is standard output.  */
2915
2916static void
2917mergefps (struct sortfile *files, size_t ntemps, size_t nfiles,
2918          FILE *ofp, char const *output_file, FILE **fps)
2919{
2920  struct buffer *buffer = xnmalloc (nfiles, sizeof *buffer);
2921                                /* Input buffers for each file. */
2922  struct line saved;		/* Saved line storage for unique check. */
2923  struct line const *savedline = NULL;
2924                                /* &saved if there is a saved line. */
2925  size_t savealloc = 0;		/* Size allocated for the saved line. */
2926  struct line const **cur = xnmalloc (nfiles, sizeof *cur);
2927                                /* Current line in each line table. */
2928  struct line const **base = xnmalloc (nfiles, sizeof *base);
2929                                /* Base of each line table.  */
2930  size_t *ord = xnmalloc (nfiles, sizeof *ord);
2931                                /* Table representing a permutation of fps,
2932                                   such that cur[ord[0]] is the smallest line
2933                                   and will be next output. */
2934  size_t i;
2935  size_t j;
2936  size_t t;
2937  struct keyfield const *key = keylist;
2938  saved.text = NULL;
2939
2940  /* Read initial lines from each input file. */
2941  for (i = 0; i < nfiles; )
2942    {
2943      initbuf (&buffer[i], sizeof (struct line),
2944               MAX (merge_buffer_size, sort_size / nfiles));
2945      if (fillbuf (&buffer[i], fps[i], files[i].name))
2946        {
2947          struct line const *linelim = buffer_linelim (&buffer[i]);
2948          cur[i] = linelim - 1;
2949          base[i] = linelim - buffer[i].nlines;
2950          i++;
2951        }
2952      else
2953        {
2954          /* fps[i] is empty; eliminate it from future consideration.  */
2955          xfclose (fps[i], files[i].name);
2956          if (i < ntemps)
2957            {
2958              ntemps--;
2959              zaptemp (files[i].name);
2960            }
2961          free (buffer[i].buf);
2962          --nfiles;
2963          for (j = i; j < nfiles; ++j)
2964            {
2965              files[j] = files[j + 1];
2966              fps[j] = fps[j + 1];
2967            }
2968        }
2969    }
2970
2971  /* Set up the ord table according to comparisons among input lines.
2972     Since this only reorders two items if one is strictly greater than
2973     the other, it is stable. */
2974  for (i = 0; i < nfiles; ++i)
2975    ord[i] = i;
2976  for (i = 1; i < nfiles; ++i)
2977    if (0 < compare (cur[ord[i - 1]], cur[ord[i]]))
2978      t = ord[i - 1], ord[i - 1] = ord[i], ord[i] = t, i = 0;
2979
2980  /* Repeatedly output the smallest line until no input remains. */
2981  while (nfiles)
2982    {
2983      struct line const *smallest = cur[ord[0]];
2984
2985      /* If uniquified output is turned on, output only the first of
2986         an identical series of lines. */
2987      if (unique)
2988        {
2989          if (savedline && compare (savedline, smallest))
2990            {
2991              savedline = NULL;
2992              write_line (&saved, ofp, output_file);
2993            }
2994          if (!savedline)
2995            {
2996              savedline = &saved;
2997              if (savealloc < smallest->length)
2998                {
2999                  do
3000                    if (! savealloc)
3001                      {
3002                        savealloc = smallest->length;
3003                        break;
3004                      }
3005                  while ((savealloc *= 2) < smallest->length);
3006
3007                  free (saved.text);
3008                  saved.text = xmalloc (savealloc);
3009                }
3010              saved.length = smallest->length;
3011              memcpy (saved.text, smallest->text, saved.length);
3012              if (key)
3013                {
3014                  saved.keybeg =
3015                    saved.text + (smallest->keybeg - smallest->text);
3016                  saved.keylim =
3017                    saved.text + (smallest->keylim - smallest->text);
3018                }
3019            }
3020        }
3021      else
3022        write_line (smallest, ofp, output_file);
3023
3024      /* Check if we need to read more lines into core. */
3025      if (base[ord[0]] < smallest)
3026        cur[ord[0]] = smallest - 1;
3027      else
3028        {
3029          if (fillbuf (&buffer[ord[0]], fps[ord[0]], files[ord[0]].name))
3030            {
3031              struct line const *linelim = buffer_linelim (&buffer[ord[0]]);
3032              cur[ord[0]] = linelim - 1;
3033              base[ord[0]] = linelim - buffer[ord[0]].nlines;
3034            }
3035          else
3036            {
3037              /* We reached EOF on fps[ord[0]].  */
3038              for (i = 1; i < nfiles; ++i)
3039                if (ord[i] > ord[0])
3040                  --ord[i];
3041              --nfiles;
3042              xfclose (fps[ord[0]], files[ord[0]].name);
3043              if (ord[0] < ntemps)
3044                {
3045                  ntemps--;
3046                  zaptemp (files[ord[0]].name);
3047                }
3048              free (buffer[ord[0]].buf);
3049              for (i = ord[0]; i < nfiles; ++i)
3050                {
3051                  fps[i] = fps[i + 1];
3052                  files[i] = files[i + 1];
3053                  buffer[i] = buffer[i + 1];
3054                  cur[i] = cur[i + 1];
3055                  base[i] = base[i + 1];
3056                }
3057              for (i = 0; i < nfiles; ++i)
3058                ord[i] = ord[i + 1];
3059              continue;
3060            }
3061        }
3062
3063      /* The new line just read in may be larger than other lines
3064         already in main memory; push it back in the queue until we
3065         encounter a line larger than it.  Optimize for the common
3066         case where the new line is smallest.  */
3067      {
3068        size_t lo = 1;
3069        size_t hi = nfiles;
3070        size_t probe = lo;
3071        size_t ord0 = ord[0];
3072        size_t count_of_smaller_lines;
3073
3074        while (lo < hi)
3075          {
3076            int cmp = compare (cur[ord0], cur[ord[probe]]);
3077            if (cmp < 0 || (cmp == 0 && ord0 < ord[probe]))
3078              hi = probe;
3079            else
3080              lo = probe + 1;
3081            probe = (lo + hi) / 2;
3082          }
3083
3084        count_of_smaller_lines = lo - 1;
3085        for (j = 0; j < count_of_smaller_lines; j++)
3086          ord[j] = ord[j + 1];
3087        ord[count_of_smaller_lines] = ord0;
3088      }
3089    }
3090
3091  if (unique && savedline)
3092    {
3093      write_line (&saved, ofp, output_file);
3094      free (saved.text);
3095    }
3096
3097  xfclose (ofp, output_file);
3098  free (fps);
3099  free (buffer);
3100  free (ord);
3101  free (base);
3102  free (cur);
3103}
3104
3105/* Merge lines from FILES onto OFP.  NTEMPS is the number of temporary
3106   files (all of which are at the start of the FILES array), and
3107   NFILES is the number of files; 0 <= NTEMPS <= NFILES <= NMERGE.
3108   Close input and output files before returning.
3109   OUTPUT_FILE gives the name of the output file.
3110
3111   Return the number of files successfully merged.  This number can be
3112   less than NFILES if we ran low on file descriptors, but in this
3113   case it is never less than 2.  */
3114
3115static size_t
3116mergefiles (struct sortfile *files, size_t ntemps, size_t nfiles,
3117            FILE *ofp, char const *output_file)
3118{
3119  FILE **fps;
3120  size_t nopened = open_input_files (files, nfiles, &fps);
3121  if (nopened < nfiles && nopened < 2)
3122    sort_die (_("open failed"), files[nopened].name);
3123  mergefps (files, ntemps, nopened, ofp, output_file, fps);
3124  return nopened;
3125}
3126
3127/* Merge into T (of size NLINES) the two sorted arrays of lines
3128   LO (with NLINES / 2 members), and
3129   T - (NLINES / 2) (with NLINES - NLINES / 2 members).
3130   T and LO point just past their respective arrays, and the arrays
3131   are in reverse order.  NLINES must be at least 2.  */
3132
3133static void
3134mergelines (struct line *restrict t, size_t nlines,
3135            struct line const *restrict lo)
3136{
3137  size_t nlo = nlines / 2;
3138  size_t nhi = nlines - nlo;
3139  struct line *hi = t - nlo;
3140
3141  while (true)
3142    if (compare (lo - 1, hi - 1) <= 0)
3143      {
3144        *--t = *--lo;
3145        if (! --nlo)
3146          {
3147            /* HI must equal T now, and there is no need to copy from
3148               HI to T. */
3149            return;
3150          }
3151      }
3152    else
3153      {
3154        *--t = *--hi;
3155        if (! --nhi)
3156          {
3157            do
3158              *--t = *--lo;
3159            while (--nlo);
3160
3161            return;
3162          }
3163      }
3164}
3165
3166/* Sort the array LINES with NLINES members, using TEMP for temporary space.
3167   Do this all within one thread.  NLINES must be at least 2.
3168   If TO_TEMP, put the sorted output into TEMP, and TEMP is as large as LINES.
3169   Otherwise the sort is in-place and TEMP is half-sized.
3170   The input and output arrays are in reverse order, and LINES and
3171   TEMP point just past the end of their respective arrays.
3172
3173   Use a recursive divide-and-conquer algorithm, in the style
3174   suggested by Knuth volume 3 (2nd edition), exercise 5.2.4-23.  Use
3175   the optimization suggested by exercise 5.2.4-10; this requires room
3176   for only 1.5*N lines, rather than the usual 2*N lines.  Knuth
3177   writes that this memory optimization was originally published by
3178   D. A. Bell, Comp J. 1 (1958), 75.  */
3179
3180static void
3181sequential_sort (struct line *restrict lines, size_t nlines,
3182                 struct line *restrict temp, bool to_temp)
3183{
3184  if (nlines == 2)
3185    {
3186      /* Declare 'swap' as int, not bool, to work around a bug
3187         <http://lists.gnu.org/archive/html/bug-coreutils/2005-10/msg00086.html>
3188         in the IBM xlc 6.0.0.0 compiler in 64-bit mode.  */
3189      int swap = (0 < compare (&lines[-1], &lines[-2]));
3190      if (to_temp)
3191        {
3192          temp[-1] = lines[-1 - swap];
3193          temp[-2] = lines[-2 + swap];
3194        }
3195      else if (swap)
3196        {
3197          temp[-1] = lines[-1];
3198          lines[-1] = lines[-2];
3199          lines[-2] = temp[-1];
3200        }
3201    }
3202  else
3203    {
3204      size_t nlo = nlines / 2;
3205      size_t nhi = nlines - nlo;
3206      struct line *lo = lines;
3207      struct line *hi = lines - nlo;
3208
3209      sequential_sort (hi, nhi, temp - (to_temp ? nlo : 0), to_temp);
3210      if (1 < nlo)
3211        sequential_sort (lo, nlo, temp, !to_temp);
3212      else if (!to_temp)
3213        temp[-1] = lo[-1];
3214
3215      struct line *dest;
3216      struct line const *sorted_lo;
3217      if (to_temp)
3218        {
3219          dest = temp;
3220          sorted_lo = lines;
3221        }
3222      else
3223        {
3224          dest = lines;
3225          sorted_lo = temp;
3226        }
3227      mergelines (dest, nlines, sorted_lo);
3228    }
3229}
3230
3231static struct merge_node *init_node (struct merge_node *restrict,
3232                                     struct merge_node *restrict,
3233                                     struct line *, size_t, size_t, bool);
3234
3235
3236/* Create and return a merge tree for NTHREADS threads, sorting NLINES
3237   lines, with destination DEST.  */
3238static struct merge_node *
3239merge_tree_init (size_t nthreads, size_t nlines, struct line *dest)
3240{
3241  struct merge_node *merge_tree = xmalloc (2 * sizeof *merge_tree * nthreads);
3242
3243  struct merge_node *root = merge_tree;
3244  root->lo = root->hi = root->end_lo = root->end_hi = NULL;
3245  root->dest = NULL;
3246  root->nlo = root->nhi = nlines;
3247  root->parent = NULL;
3248  root->level = MERGE_END;
3249  root->queued = false;
3250  pthread_mutex_init (&root->lock, NULL);
3251
3252  init_node (root, root + 1, dest, nthreads, nlines, false);
3253  return merge_tree;
3254}
3255
3256/* Destroy the merge tree. */
3257static void
3258merge_tree_destroy (size_t nthreads, struct merge_node *merge_tree)
3259{
3260  size_t n_nodes = nthreads * 2;
3261  struct merge_node *node = merge_tree;
3262
3263  while (n_nodes--)
3264    {
3265      pthread_mutex_destroy (&node->lock);
3266      node++;
3267    }
3268
3269  free (merge_tree);
3270}
3271
3272/* Initialize a merge tree node and its descendants.  The node's
3273   parent is PARENT.  The node and its descendants are taken from the
3274   array of nodes NODE_POOL.  Their destination starts at DEST; they
3275   will consume NTHREADS threads.  The total number of sort lines is
3276   TOTAL_LINES.  IS_LO_CHILD is true if the node is the low child of
3277   its parent.  */
3278
3279static struct merge_node *
3280init_node (struct merge_node *restrict parent,
3281           struct merge_node *restrict node_pool,
3282           struct line *dest, size_t nthreads,
3283           size_t total_lines, bool is_lo_child)
3284{
3285  size_t nlines = (is_lo_child ? parent->nlo : parent->nhi);
3286  size_t nlo = nlines / 2;
3287  size_t nhi = nlines - nlo;
3288  struct line *lo = dest - total_lines;
3289  struct line *hi = lo - nlo;
3290  struct line **parent_end = (is_lo_child ? &parent->end_lo : &parent->end_hi);
3291
3292  struct merge_node *node = node_pool++;
3293  node->lo = node->end_lo = lo;
3294  node->hi = node->end_hi = hi;
3295  node->dest = parent_end;
3296  node->nlo = nlo;
3297  node->nhi = nhi;
3298  node->parent = parent;
3299  node->level = parent->level + 1;
3300  node->queued = false;
3301  pthread_mutex_init (&node->lock, NULL);
3302
3303  if (nthreads > 1)
3304    {
3305      size_t lo_threads = nthreads / 2;
3306      size_t hi_threads = nthreads - lo_threads;
3307      node->lo_child = node_pool;
3308      node_pool = init_node (node, node_pool, lo, lo_threads,
3309                             total_lines, true);
3310      node->hi_child = node_pool;
3311      node_pool = init_node (node, node_pool, hi, hi_threads,
3312                             total_lines, false);
3313    }
3314  else
3315    {
3316      node->lo_child = NULL;
3317      node->hi_child = NULL;
3318    }
3319  return node_pool;
3320}
3321
3322
3323/* Compare two merge nodes A and B for priority.  */
3324
3325static int
3326compare_nodes (void const *a, void const *b)
3327{
3328  struct merge_node const *nodea = a;
3329  struct merge_node const *nodeb = b;
3330  if (nodea->level == nodeb->level)
3331      return (nodea->nlo + nodea->nhi) < (nodeb->nlo + nodeb->nhi);
3332  return nodea->level < nodeb->level;
3333}
3334
3335/* Lock a merge tree NODE.  */
3336
3337static inline void
3338lock_node (struct merge_node *node)
3339{
3340  pthread_mutex_lock (&node->lock);
3341}
3342
3343/* Unlock a merge tree NODE. */
3344
3345static inline void
3346unlock_node (struct merge_node *node)
3347{
3348  pthread_mutex_unlock (&node->lock);
3349}
3350
3351/* Destroy merge QUEUE. */
3352
3353static void
3354queue_destroy (struct merge_node_queue *queue)
3355{
3356  heap_free (queue->priority_queue);
3357  pthread_cond_destroy (&queue->cond);
3358  pthread_mutex_destroy (&queue->mutex);
3359}
3360
3361/* Initialize merge QUEUE, allocating space suitable for a maximum of
3362   NTHREADS threads.  */
3363
3364static void
3365queue_init (struct merge_node_queue *queue, size_t nthreads)
3366{
3367  /* Though it's highly unlikely all nodes are in the heap at the same
3368     time, the heap should accommodate all of them.  Counting a NULL
3369     dummy head for the heap, reserve 2 * NTHREADS nodes.  */
3370  queue->priority_queue = heap_alloc (compare_nodes, 2 * nthreads);
3371  pthread_mutex_init (&queue->mutex, NULL);
3372  pthread_cond_init (&queue->cond, NULL);
3373}
3374
3375/* Insert NODE into QUEUE.  The caller either holds a lock on NODE, or
3376   does not need to lock NODE.  */
3377
3378static void
3379queue_insert (struct merge_node_queue *queue, struct merge_node *node)
3380{
3381  pthread_mutex_lock (&queue->mutex);
3382  heap_insert (queue->priority_queue, node);
3383  node->queued = true;
3384  pthread_cond_signal (&queue->cond);
3385  pthread_mutex_unlock (&queue->mutex);
3386}
3387
3388/* Pop the top node off the priority QUEUE, lock the node, return it.  */
3389
3390static struct merge_node *
3391queue_pop (struct merge_node_queue *queue)
3392{
3393  struct merge_node *node;
3394  pthread_mutex_lock (&queue->mutex);
3395  while (! (node = heap_remove_top (queue->priority_queue)))
3396    pthread_cond_wait (&queue->cond, &queue->mutex);
3397  pthread_mutex_unlock (&queue->mutex);
3398  lock_node (node);
3399  node->queued = false;
3400  return node;
3401}
3402
3403/* Output LINE to TFP, unless -u is specified and the line compares
3404   equal to the previous line.  TEMP_OUTPUT is the name of TFP, or
3405   is null if TFP is standard output.
3406
3407   This function does not save the line for comparison later, so it is
3408   appropriate only for internal sort.  */
3409
3410static void
3411write_unique (struct line const *line, FILE *tfp, char const *temp_output)
3412{
3413  if (unique)
3414    {
3415      if (saved_line.text && ! compare (line, &saved_line))
3416        return;
3417      saved_line = *line;
3418    }
3419
3420  write_line (line, tfp, temp_output);
3421}
3422
3423/* Merge the lines currently available to a NODE in the binary
3424   merge tree.  Merge a number of lines appropriate for this merge
3425   level, assuming TOTAL_LINES is the total number of lines.
3426
3427   If merging at the top level, send output to TFP.  TEMP_OUTPUT is
3428   the name of TFP, or is null if TFP is standard output.  */
3429
3430static void
3431mergelines_node (struct merge_node *restrict node, size_t total_lines,
3432                 FILE *tfp, char const *temp_output)
3433{
3434  struct line *lo_orig = node->lo;
3435  struct line *hi_orig = node->hi;
3436  size_t to_merge = MAX_MERGE (total_lines, node->level);
3437  size_t merged_lo;
3438  size_t merged_hi;
3439
3440  if (node->level > MERGE_ROOT)
3441    {
3442      /* Merge to destination buffer. */
3443      struct line *dest = *node->dest;
3444      while (node->lo != node->end_lo && node->hi != node->end_hi && to_merge--)
3445        if (compare (node->lo - 1, node->hi - 1) <= 0)
3446          *--dest = *--node->lo;
3447        else
3448          *--dest = *--node->hi;
3449
3450      merged_lo = lo_orig - node->lo;
3451      merged_hi = hi_orig - node->hi;
3452
3453      if (node->nhi == merged_hi)
3454        while (node->lo != node->end_lo && to_merge--)
3455          *--dest = *--node->lo;
3456      else if (node->nlo == merged_lo)
3457        while (node->hi != node->end_hi && to_merge--)
3458          *--dest = *--node->hi;
3459      *node->dest = dest;
3460    }
3461  else
3462    {
3463      /* Merge directly to output. */
3464      while (node->lo != node->end_lo && node->hi != node->end_hi && to_merge--)
3465        {
3466          if (compare (node->lo - 1, node->hi - 1) <= 0)
3467            write_unique (--node->lo, tfp, temp_output);
3468          else
3469            write_unique (--node->hi, tfp, temp_output);
3470        }
3471
3472      merged_lo = lo_orig - node->lo;
3473      merged_hi = hi_orig - node->hi;
3474
3475      if (node->nhi == merged_hi)
3476        {
3477          while (node->lo != node->end_lo && to_merge--)
3478            write_unique (--node->lo, tfp, temp_output);
3479        }
3480      else if (node->nlo == merged_lo)
3481        {
3482          while (node->hi != node->end_hi && to_merge--)
3483            write_unique (--node->hi, tfp, temp_output);
3484        }
3485    }
3486
3487  /* Update NODE. */
3488  merged_lo = lo_orig - node->lo;
3489  merged_hi = hi_orig - node->hi;
3490  node->nlo -= merged_lo;
3491  node->nhi -= merged_hi;
3492}
3493
3494/* Into QUEUE, insert NODE if it is not already queued, and if one of
3495   NODE's children has available lines and the other either has
3496   available lines or has exhausted its lines.  */
3497
3498static void
3499queue_check_insert (struct merge_node_queue *queue, struct merge_node *node)
3500{
3501  if (! node->queued)
3502    {
3503      bool lo_avail = (node->lo - node->end_lo) != 0;
3504      bool hi_avail = (node->hi - node->end_hi) != 0;
3505      if (lo_avail ? hi_avail || ! node->nhi : hi_avail && ! node->nlo)
3506        queue_insert (queue, node);
3507    }
3508}
3509
3510/* Into QUEUE, insert NODE's parent if the parent can now be worked on.  */
3511
3512static void
3513queue_check_insert_parent (struct merge_node_queue *queue,
3514                           struct merge_node *node)
3515{
3516  if (node->level > MERGE_ROOT)
3517    {
3518      lock_node (node->parent);
3519      queue_check_insert (queue, node->parent);
3520      unlock_node (node->parent);
3521    }
3522  else if (node->nlo + node->nhi == 0)
3523    {
3524      /* If the MERGE_ROOT NODE has finished merging, insert the
3525         MERGE_END node.  */
3526      queue_insert (queue, node->parent);
3527    }
3528}
3529
3530/* Repeatedly pop QUEUE for a node with lines to merge, and merge at least
3531   some of those lines, until the MERGE_END node is popped.
3532   TOTAL_LINES is the total number of lines.  If merging at the top
3533   level, send output to TFP.  TEMP_OUTPUT is the name of TFP, or is
3534   null if TFP is standard output.  */
3535
3536static void
3537merge_loop (struct merge_node_queue *queue,
3538            size_t total_lines, FILE *tfp, char const *temp_output)
3539{
3540  while (1)
3541    {
3542      struct merge_node *node = queue_pop (queue);
3543
3544      if (node->level == MERGE_END)
3545        {
3546          unlock_node (node);
3547          /* Reinsert so other threads can pop it. */
3548          queue_insert (queue, node);
3549          break;
3550        }
3551      mergelines_node (node, total_lines, tfp, temp_output);
3552      queue_check_insert (queue, node);
3553      queue_check_insert_parent (queue, node);
3554
3555      unlock_node (node);
3556    }
3557}
3558
3559
3560static void sortlines (struct line *restrict, size_t, size_t,
3561                       struct merge_node *, struct merge_node_queue *,
3562                       FILE *, char const *);
3563
3564/* Thread arguments for sortlines_thread. */
3565
3566struct thread_args
3567{
3568  /* Source, i.e., the array of lines to sort.  This points just past
3569     the end of the array.  */
3570  struct line *lines;
3571
3572  /* Number of threads to use.  If 0 or 1, sort single-threaded.  */
3573  size_t nthreads;
3574
3575  /* Number of lines in LINES and DEST.  */
3576  size_t const total_lines;
3577
3578  /* Merge node. Lines from this node and this node's sibling will merged
3579     to this node's parent. */
3580  struct merge_node *const node;
3581
3582  /* The priority queue controlling available work for the entire
3583     internal sort.  */
3584  struct merge_node_queue *const queue;
3585
3586  /* If at the top level, the file to output to, and the file's name.
3587     If the file is standard output, the file's name is null.  */
3588  FILE *tfp;
3589  char const *output_temp;
3590};
3591
3592/* Like sortlines, except with a signature acceptable to pthread_create.  */
3593
3594static void *
3595sortlines_thread (void *data)
3596{
3597  struct thread_args const *args = data;
3598  sortlines (args->lines, args->nthreads, args->total_lines,
3599             args->node, args->queue, args->tfp,
3600             args->output_temp);
3601  return NULL;
3602}
3603
3604/* Sort lines, possibly in parallel.  The arguments are as in struct
3605   thread_args above.
3606
3607   The algorithm has three phases: node creation, sequential sort,
3608   and binary merge.
3609
3610   During node creation, sortlines recursively visits each node in the
3611   binary merge tree and creates a NODE structure corresponding to all the
3612   future line merging NODE is responsible for. For each call to
3613   sortlines, half the available threads are assigned to each recursive
3614   call, until a leaf node having only 1 available thread is reached.
3615
3616   Each leaf node then performs two sequential sorts, one on each half of
3617   the lines it is responsible for. It records in its NODE structure that
3618   there are two sorted sublists available to merge from, and inserts its
3619   NODE into the priority queue.
3620
3621   The binary merge phase then begins. Each thread drops into a loop
3622   where the thread retrieves a NODE from the priority queue, merges lines
3623   available to that NODE, and potentially insert NODE or its parent back
3624   into the queue if there are sufficient available lines for them to
3625   merge. This continues until all lines at all nodes of the merge tree
3626   have been merged. */
3627
3628static void
3629sortlines (struct line *restrict lines, size_t nthreads,
3630           size_t total_lines, struct merge_node *node,
3631           struct merge_node_queue *queue, FILE *tfp, char const *temp_output)
3632{
3633  size_t nlines = node->nlo + node->nhi;
3634
3635  /* Calculate thread arguments. */
3636  size_t lo_threads = nthreads / 2;
3637  size_t hi_threads = nthreads - lo_threads;
3638  pthread_t thread;
3639  struct thread_args args = {lines, lo_threads, total_lines,
3640                             node->lo_child, queue, tfp, temp_output};
3641
3642  if (nthreads > 1 && SUBTHREAD_LINES_HEURISTIC <= nlines
3643      && pthread_create (&thread, NULL, sortlines_thread, &args) == 0)
3644    {
3645      sortlines (lines - node->nlo, hi_threads, total_lines,
3646                 node->hi_child, queue, tfp, temp_output);
3647      pthread_join (thread, NULL);
3648    }
3649  else
3650    {
3651      /* Nthreads = 1, this is a leaf NODE, or pthread_create failed.
3652         Sort with 1 thread. */
3653      size_t nlo = node->nlo;
3654      size_t nhi = node->nhi;
3655      struct line *temp = lines - total_lines;
3656      if (1 < nhi)
3657        sequential_sort (lines - nlo, nhi, temp - nlo / 2, false);
3658      if (1 < nlo)
3659        sequential_sort (lines, nlo, temp, false);
3660
3661      /* Update merge NODE. No need to lock yet. */
3662      node->lo = lines;
3663      node->hi = lines - nlo;
3664      node->end_lo = lines - nlo;
3665      node->end_hi = lines - nlo - nhi;
3666
3667      queue_insert (queue, node);
3668      merge_loop (queue, total_lines, tfp, temp_output);
3669    }
3670}
3671
3672/* Scan through FILES[NTEMPS .. NFILES-1] looking for files that are
3673   the same as OUTFILE.  If found, replace each with the same
3674   temporary copy that can be merged into OUTFILE without destroying
3675   OUTFILE before it is completely read.  This temporary copy does not
3676   count as a merge temp, so don't worry about incrementing NTEMPS in
3677   the caller; final cleanup will remove it, not zaptemp.
3678
3679   This test ensures that an otherwise-erroneous use like
3680   "sort -m -o FILE ... FILE ..." copies FILE before writing to it.
3681   It's not clear that POSIX requires this nicety.
3682   Detect common error cases, but don't try to catch obscure cases like
3683   "cat ... FILE ... | sort -m -o FILE"
3684   where traditional "sort" doesn't copy the input and where
3685   people should know that they're getting into trouble anyway.
3686   Catching these obscure cases would slow down performance in
3687   common cases.  */
3688
3689static void
3690avoid_trashing_input (struct sortfile *files, size_t ntemps,
3691                      size_t nfiles, char const *outfile)
3692{
3693  bool got_outstat = false;
3694  struct stat outstat;
3695  struct tempnode *tempcopy = NULL;
3696
3697  for (size_t i = ntemps; i < nfiles; i++)
3698    {
3699      bool is_stdin = STREQ (files[i].name, "-");
3700      bool same;
3701      struct stat instat;
3702
3703      if (outfile && STREQ (outfile, files[i].name) && !is_stdin)
3704        same = true;
3705      else
3706        {
3707          if (! got_outstat)
3708            {
3709              if (fstat (STDOUT_FILENO, &outstat) != 0)
3710                break;
3711              got_outstat = true;
3712            }
3713
3714          same = (((is_stdin
3715                    ? fstat (STDIN_FILENO, &instat)
3716                    : stat (files[i].name, &instat))
3717                   == 0)
3718                  && SAME_INODE (instat, outstat));
3719        }
3720
3721      if (same)
3722        {
3723          if (! tempcopy)
3724            {
3725              FILE *tftp;
3726              tempcopy = create_temp (&tftp);
3727              mergefiles (&files[i], 0, 1, tftp, tempcopy->name);
3728            }
3729
3730          files[i].name = tempcopy->name;
3731          files[i].temp = tempcopy;
3732        }
3733    }
3734}
3735
3736/* Scan the input files to ensure all are accessible.
3737   Otherwise exit with a diagnostic.
3738
3739   Note this will catch common issues with permissions etc.
3740   but will fail to notice issues where you can open() but not read(),
3741   like when a directory is specified on some systems.
3742   Catching these obscure cases could slow down performance in
3743   common cases.  */
3744
3745static void
3746check_inputs (char *const *files, size_t nfiles)
3747{
3748  for (size_t i = 0; i < nfiles; i++)
3749    {
3750      if (STREQ (files[i], "-"))
3751        continue;
3752
3753      if (euidaccess (files[i], R_OK) != 0)
3754        sort_die (_("cannot read"), files[i]);
3755    }
3756}
3757
3758/* Ensure a specified output file can be created or written to,
3759   and point stdout to it.  Do not truncate the file.
3760   Exit with a diagnostic on failure.  */
3761
3762static void
3763check_output (char const *outfile)
3764{
3765  if (outfile)
3766    {
3767      int outfd = open (outfile, O_WRONLY | O_CREAT | O_BINARY, MODE_RW_UGO);
3768      if (outfd < 0)
3769        sort_die (_("open failed"), outfile);
3770      move_fd_or_die (outfd, STDOUT_FILENO);
3771    }
3772}
3773
3774/* Merge the input FILES.  NTEMPS is the number of files at the
3775   start of FILES that are temporary; it is zero at the top level.
3776   NFILES is the total number of files.  Put the output in
3777   OUTPUT_FILE; a null OUTPUT_FILE stands for standard output.  */
3778
3779static void
3780merge (struct sortfile *files, size_t ntemps, size_t nfiles,
3781       char const *output_file)
3782{
3783  while (nmerge < nfiles)
3784    {
3785      /* Number of input files processed so far.  */
3786      size_t in;
3787
3788      /* Number of output files generated so far.  */
3789      size_t out;
3790
3791      /* nfiles % NMERGE; this counts input files that are left over
3792         after all full-sized merges have been done.  */
3793      size_t remainder;
3794
3795      /* Number of easily-available slots at the next loop iteration.  */
3796      size_t cheap_slots;
3797
3798      /* Do as many NMERGE-size merges as possible. In the case that
3799         nmerge is bogus, increment by the maximum number of file
3800         descriptors allowed.  */
3801      for (out = in = 0; nmerge <= nfiles - in; out++)
3802        {
3803          FILE *tfp;
3804          struct tempnode *temp = create_temp (&tfp);
3805          size_t num_merged = mergefiles (&files[in], MIN (ntemps, nmerge),
3806                                          nmerge, tfp, temp->name);
3807          ntemps -= MIN (ntemps, num_merged);
3808          files[out].name = temp->name;
3809          files[out].temp = temp;
3810          in += num_merged;
3811        }
3812
3813      remainder = nfiles - in;
3814      cheap_slots = nmerge - out % nmerge;
3815
3816      if (cheap_slots < remainder)
3817        {
3818          /* So many files remain that they can't all be put into the last
3819             NMERGE-sized output window.  Do one more merge.  Merge as few
3820             files as possible, to avoid needless I/O.  */
3821          size_t nshortmerge = remainder - cheap_slots + 1;
3822          FILE *tfp;
3823          struct tempnode *temp = create_temp (&tfp);
3824          size_t num_merged = mergefiles (&files[in], MIN (ntemps, nshortmerge),
3825                                          nshortmerge, tfp, temp->name);
3826          ntemps -= MIN (ntemps, num_merged);
3827          files[out].name = temp->name;
3828          files[out++].temp = temp;
3829          in += num_merged;
3830        }
3831
3832      /* Put the remaining input files into the last NMERGE-sized output
3833         window, so they will be merged in the next pass.  */
3834      memmove (&files[out], &files[in], (nfiles - in) * sizeof *files);
3835      ntemps += out;
3836      nfiles -= in - out;
3837    }
3838
3839  avoid_trashing_input (files, ntemps, nfiles, output_file);
3840
3841  /* We aren't guaranteed that this final mergefiles will work, therefore we
3842     try to merge into the output, and then merge as much as we can into a
3843     temp file if we can't. Repeat.  */
3844
3845  while (true)
3846    {
3847      /* Merge directly into the output file if possible.  */
3848      FILE **fps;
3849      size_t nopened = open_input_files (files, nfiles, &fps);
3850
3851      if (nopened == nfiles)
3852        {
3853          FILE *ofp = stream_open (output_file, "w");
3854          if (ofp)
3855            {
3856              mergefps (files, ntemps, nfiles, ofp, output_file, fps);
3857              break;
3858            }
3859          if (errno != EMFILE || nopened <= 2)
3860            sort_die (_("open failed"), output_file);
3861        }
3862      else if (nopened <= 2)
3863        sort_die (_("open failed"), files[nopened].name);
3864
3865      /* We ran out of file descriptors.  Close one of the input
3866         files, to gain a file descriptor.  Then create a temporary
3867         file with our spare file descriptor.  Retry if that failed
3868         (e.g., some other process could open a file between the time
3869         we closed and tried to create).  */
3870      FILE *tfp;
3871      struct tempnode *temp;
3872      do
3873        {
3874          nopened--;
3875          xfclose (fps[nopened], files[nopened].name);
3876          temp = maybe_create_temp (&tfp, ! (nopened <= 2));
3877        }
3878      while (!temp);
3879
3880      /* Merge into the newly allocated temporary.  */
3881      mergefps (&files[0], MIN (ntemps, nopened), nopened, tfp, temp->name,
3882                fps);
3883      ntemps -= MIN (ntemps, nopened);
3884      files[0].name = temp->name;
3885      files[0].temp = temp;
3886
3887      memmove (&files[1], &files[nopened], (nfiles - nopened) * sizeof *files);
3888      ntemps++;
3889      nfiles -= nopened - 1;
3890    }
3891}
3892
3893/* Sort NFILES FILES onto OUTPUT_FILE.  Use at most NTHREADS threads.  */
3894
3895static void
3896sort (char *const *files, size_t nfiles, char const *output_file,
3897      size_t nthreads)
3898{
3899  struct buffer buf;
3900  IF_LINT (buf.buf = NULL);
3901  size_t ntemps = 0;
3902  bool output_file_created = false;
3903
3904  buf.alloc = 0;
3905
3906  while (nfiles)
3907    {
3908      char const *temp_output;
3909      char const *file = *files;
3910      FILE *fp = xfopen (file, "r");
3911      FILE *tfp;
3912
3913      size_t bytes_per_line;
3914      if (nthreads > 1)
3915        {
3916          /* Get log P. */
3917          size_t tmp = 1;
3918          size_t mult = 1;
3919          while (tmp < nthreads)
3920            {
3921              tmp *= 2;
3922              mult++;
3923            }
3924          bytes_per_line = (mult * sizeof (struct line));
3925        }
3926      else
3927        bytes_per_line = sizeof (struct line) * 3 / 2;
3928
3929      if (! buf.alloc)
3930        initbuf (&buf, bytes_per_line,
3931                 sort_buffer_size (&fp, 1, files, nfiles, bytes_per_line));
3932      buf.eof = false;
3933      files++;
3934      nfiles--;
3935
3936      while (fillbuf (&buf, fp, file))
3937        {
3938          struct line *line;
3939
3940          if (buf.eof && nfiles
3941              && (bytes_per_line + 1
3942                  < (buf.alloc - buf.used - bytes_per_line * buf.nlines)))
3943            {
3944              /* End of file, but there is more input and buffer room.
3945                 Concatenate the next input file; this is faster in
3946                 the usual case.  */
3947              buf.left = buf.used;
3948              break;
3949            }
3950
3951          saved_line.text = NULL;
3952          line = buffer_linelim (&buf);
3953          if (buf.eof && !nfiles && !ntemps && !buf.left)
3954            {
3955              xfclose (fp, file);
3956              tfp = xfopen (output_file, "w");
3957              temp_output = output_file;
3958              output_file_created = true;
3959            }
3960          else
3961            {
3962              ++ntemps;
3963              temp_output = create_temp (&tfp)->name;
3964            }
3965          if (1 < buf.nlines)
3966            {
3967              struct merge_node_queue queue;
3968              queue_init (&queue, nthreads);
3969              struct merge_node *merge_tree =
3970                merge_tree_init (nthreads, buf.nlines, line);
3971
3972              sortlines (line, nthreads, buf.nlines, merge_tree + 1,
3973                         &queue, tfp, temp_output);
3974
3975#ifdef lint
3976              merge_tree_destroy (nthreads, merge_tree);
3977              queue_destroy (&queue);
3978#endif
3979            }
3980          else
3981            write_unique (line - 1, tfp, temp_output);
3982
3983          xfclose (tfp, temp_output);
3984
3985          if (output_file_created)
3986            goto finish;
3987        }
3988      xfclose (fp, file);
3989    }
3990
3991 finish:
3992  free (buf.buf);
3993
3994  if (! output_file_created)
3995    {
3996      struct tempnode *node = temphead;
3997      struct sortfile *tempfiles = xnmalloc (ntemps, sizeof *tempfiles);
3998      for (size_t i = 0; node; i++)
3999        {
4000          tempfiles[i].name = node->name;
4001          tempfiles[i].temp = node;
4002          node = node->next;
4003        }
4004      merge (tempfiles, ntemps, ntemps, output_file);
4005      free (tempfiles);
4006    }
4007
4008  reap_all ();
4009}
4010
4011/* Insert a malloc'd copy of key KEY_ARG at the end of the key list.  */
4012
4013static void
4014insertkey (struct keyfield *key_arg)
4015{
4016  struct keyfield **p;
4017  struct keyfield *key = xmemdup (key_arg, sizeof *key);
4018
4019  for (p = &keylist; *p; p = &(*p)->next)
4020    continue;
4021  *p = key;
4022  key->next = NULL;
4023}
4024
4025/* Report a bad field specification SPEC, with extra info MSGID.  */
4026
4027static void badfieldspec (char const *, char const *)
4028     ATTRIBUTE_NORETURN;
4029static void
4030badfieldspec (char const *spec, char const *msgid)
4031{
4032  die (SORT_FAILURE, 0, _("%s: invalid field specification %s"),
4033       _(msgid), quote (spec));
4034}
4035
4036/* Report incompatible options.  */
4037
4038static void incompatible_options (char const *) ATTRIBUTE_NORETURN;
4039static void
4040incompatible_options (char const *opts)
4041{
4042  die (SORT_FAILURE, 0, _("options '-%s' are incompatible"), (opts));
4043}
4044
4045/* Check compatibility of ordering options.  */
4046
4047static void
4048check_ordering_compatibility (void)
4049{
4050  struct keyfield *key;
4051
4052  for (key = keylist; key; key = key->next)
4053    if (1 < (key->numeric + key->general_numeric + key->human_numeric
4054             + key->month + (key->version | key->random | !!key->ignore)))
4055      {
4056        /* The following is too big, but guaranteed to be "big enough".  */
4057        char opts[sizeof short_options];
4058        /* Clear flags we're not interested in.  */
4059        key->skipsblanks = key->skipeblanks = key->reverse = false;
4060        key_to_opts (key, opts);
4061        incompatible_options (opts);
4062      }
4063}
4064
4065/* Parse the leading integer in STRING and store the resulting value
4066   (which must fit into size_t) into *VAL.  Return the address of the
4067   suffix after the integer.  If the value is too large, silently
4068   substitute SIZE_MAX.  If MSGID is NULL, return NULL after
4069   failure; otherwise, report MSGID and exit on failure.  */
4070
4071static char const *
4072parse_field_count (char const *string, size_t *val, char const *msgid)
4073{
4074  char *suffix;
4075  uintmax_t n;
4076
4077  switch (xstrtoumax (string, &suffix, 10, &n, ""))
4078    {
4079    case LONGINT_OK:
4080    case LONGINT_INVALID_SUFFIX_CHAR:
4081      *val = n;
4082      if (*val == n)
4083        break;
4084      FALLTHROUGH;
4085    case LONGINT_OVERFLOW:
4086    case LONGINT_OVERFLOW | LONGINT_INVALID_SUFFIX_CHAR:
4087      *val = SIZE_MAX;
4088      break;
4089
4090    case LONGINT_INVALID:
4091      if (msgid)
4092        die (SORT_FAILURE, 0, _("%s: invalid count at start of %s"),
4093             _(msgid), quote (string));
4094      return NULL;
4095    }
4096
4097  return suffix;
4098}
4099
4100/* Handle interrupts and hangups. */
4101
4102static void
4103sighandler (int sig)
4104{
4105  if (! SA_NOCLDSTOP)
4106    signal (sig, SIG_IGN);
4107
4108  cleanup ();
4109
4110  signal (sig, SIG_DFL);
4111  raise (sig);
4112}
4113
4114/* Set the ordering options for KEY specified in S.
4115   Return the address of the first character in S that
4116   is not a valid ordering option.
4117   BLANKTYPE is the kind of blanks that 'b' should skip. */
4118
4119static char *
4120set_ordering (char const *s, struct keyfield *key, enum blanktype blanktype)
4121{
4122  while (*s)
4123    {
4124      switch (*s)
4125        {
4126        case 'b':
4127          if (blanktype == bl_start || blanktype == bl_both)
4128            key->skipsblanks = true;
4129          if (blanktype == bl_end || blanktype == bl_both)
4130            key->skipeblanks = true;
4131          break;
4132        case 'd':
4133          key->ignore = nondictionary;
4134          break;
4135        case 'f':
4136          key->translate = fold_toupper;
4137          break;
4138        case 'g':
4139          key->general_numeric = true;
4140          break;
4141        case 'h':
4142          key->human_numeric = true;
4143          break;
4144        case 'i':
4145          /* Option order should not matter, so don't let -i override
4146             -d.  -d implies -i, but -i does not imply -d.  */
4147          if (! key->ignore)
4148            key->ignore = nonprinting;
4149          break;
4150        case 'M':
4151          key->month = true;
4152          break;
4153        case 'n':
4154          key->numeric = true;
4155          break;
4156        case 'R':
4157          key->random = true;
4158          break;
4159        case 'r':
4160          key->reverse = true;
4161          break;
4162        case 'V':
4163          key->version = true;
4164          break;
4165        default:
4166          return (char *) s;
4167        }
4168      ++s;
4169    }
4170  return (char *) s;
4171}
4172
4173/* Initialize KEY.  */
4174
4175static struct keyfield *
4176key_init (struct keyfield *key)
4177{
4178  memset (key, 0, sizeof *key);
4179  key->eword = SIZE_MAX;
4180  return key;
4181}
4182
4183int
4184main (int argc, char **argv)
4185{
4186  struct keyfield *key;
4187  struct keyfield key_buf;
4188  struct keyfield gkey;
4189  bool gkey_only = false;
4190  char const *s;
4191  int c = 0;
4192  char checkonly = 0;
4193  bool mergeonly = false;
4194  char *random_source = NULL;
4195  bool need_random = false;
4196  size_t nthreads = 0;
4197  size_t nfiles = 0;
4198  bool posixly_correct = (getenv ("POSIXLY_CORRECT") != NULL);
4199  int posix_ver = posix2_version ();
4200  bool traditional_usage = ! (200112 <= posix_ver && posix_ver < 200809);
4201  char **files;
4202  char *files_from = NULL;
4203  struct Tokens tok;
4204  char const *outfile = NULL;
4205  bool locale_ok;
4206
4207  initialize_main (&argc, &argv);
4208  set_program_name (argv[0]);
4209  locale_ok = !! setlocale (LC_ALL, "");
4210  bindtextdomain (PACKAGE, LOCALEDIR);
4211  textdomain (PACKAGE);
4212
4213  initialize_exit_failure (SORT_FAILURE);
4214
4215  hard_LC_COLLATE = hard_locale (LC_COLLATE);
4216#if HAVE_NL_LANGINFO
4217  hard_LC_TIME = hard_locale (LC_TIME);
4218#endif
4219
4220  /* Get locale's representation of the decimal point.  */
4221  {
4222    struct lconv const *locale = localeconv ();
4223
4224    /* If the locale doesn't define a decimal point, or if the decimal
4225       point is multibyte, use the C locale's decimal point.  FIXME:
4226       add support for multibyte decimal points.  */
4227    decimal_point = to_uchar (locale->decimal_point[0]);
4228    if (! decimal_point || locale->decimal_point[1])
4229      decimal_point = '.';
4230
4231    /* FIXME: add support for multibyte thousands separators.  */
4232    thousands_sep = to_uchar (*locale->thousands_sep);
4233    if (! thousands_sep || locale->thousands_sep[1])
4234      thousands_sep = -1;
4235  }
4236
4237  have_read_stdin = false;
4238  inittables ();
4239
4240  {
4241    size_t i;
4242    static int const sig[] =
4243      {
4244        /* The usual suspects.  */
4245        SIGALRM, SIGHUP, SIGINT, SIGPIPE, SIGQUIT, SIGTERM,
4246#ifdef SIGPOLL
4247        SIGPOLL,
4248#endif
4249#ifdef SIGPROF
4250        SIGPROF,
4251#endif
4252#ifdef SIGVTALRM
4253        SIGVTALRM,
4254#endif
4255#ifdef SIGXCPU
4256        SIGXCPU,
4257#endif
4258#ifdef SIGXFSZ
4259        SIGXFSZ,
4260#endif
4261      };
4262    enum { nsigs = ARRAY_CARDINALITY (sig) };
4263
4264#if SA_NOCLDSTOP
4265    struct sigaction act;
4266
4267    sigemptyset (&caught_signals);
4268    for (i = 0; i < nsigs; i++)
4269      {
4270        sigaction (sig[i], NULL, &act);
4271        if (act.sa_handler != SIG_IGN)
4272          sigaddset (&caught_signals, sig[i]);
4273      }
4274
4275    act.sa_handler = sighandler;
4276    act.sa_mask = caught_signals;
4277    act.sa_flags = 0;
4278
4279    for (i = 0; i < nsigs; i++)
4280      if (sigismember (&caught_signals, sig[i]))
4281        sigaction (sig[i], &act, NULL);
4282#else
4283    for (i = 0; i < nsigs; i++)
4284      if (signal (sig[i], SIG_IGN) != SIG_IGN)
4285        {
4286          signal (sig[i], sighandler);
4287          siginterrupt (sig[i], 1);
4288        }
4289#endif
4290  }
4291  signal (SIGCHLD, SIG_DFL); /* Don't inherit CHLD handling from parent.  */
4292
4293  /* The signal mask is known, so it is safe to invoke exit_cleanup.  */
4294  atexit (exit_cleanup);
4295
4296  key_init (&gkey);
4297  gkey.sword = SIZE_MAX;
4298
4299  files = xnmalloc (argc, sizeof *files);
4300
4301  while (true)
4302    {
4303      /* Parse an operand as a file after "--" was seen; or if
4304         pedantic and a file was seen, unless the POSIX version
4305         is not 1003.1-2001 and -c was not seen and the operand is
4306         "-o FILE" or "-oFILE".  */
4307      int oi = -1;
4308
4309      if (c == -1
4310          || (posixly_correct && nfiles != 0
4311              && ! (traditional_usage
4312                    && ! checkonly
4313                    && optind != argc
4314                    && argv[optind][0] == '-' && argv[optind][1] == 'o'
4315                    && (argv[optind][2] || optind + 1 != argc)))
4316          || ((c = getopt_long (argc, argv, short_options,
4317                                long_options, &oi))
4318              == -1))
4319        {
4320          if (argc <= optind)
4321            break;
4322          files[nfiles++] = argv[optind++];
4323        }
4324      else switch (c)
4325        {
4326        case 1:
4327          key = NULL;
4328          if (optarg[0] == '+')
4329            {
4330              bool minus_pos_usage = (optind != argc && argv[optind][0] == '-'
4331                                      && ISDIGIT (argv[optind][1]));
4332              traditional_usage |= minus_pos_usage && !posixly_correct;
4333              if (traditional_usage)
4334                {
4335                  /* Treat +POS1 [-POS2] as a key if possible; but silently
4336                     treat an operand as a file if it is not a valid +POS1.  */
4337                  key = key_init (&key_buf);
4338                  s = parse_field_count (optarg + 1, &key->sword, NULL);
4339                  if (s && *s == '.')
4340                    s = parse_field_count (s + 1, &key->schar, NULL);
4341                  if (! (key->sword || key->schar))
4342                    key->sword = SIZE_MAX;
4343                  if (! s || *set_ordering (s, key, bl_start))
4344                    key = NULL;
4345                  else
4346                    {
4347                      if (minus_pos_usage)
4348                        {
4349                          char const *optarg1 = argv[optind++];
4350                          s = parse_field_count (optarg1 + 1, &key->eword,
4351                                             N_("invalid number after '-'"));
4352                          /* When called with a non-NULL message ID,
4353                             parse_field_count cannot return NULL.  Tell static
4354                             analysis tools that dereferencing S is safe.  */
4355                          assert (s);
4356                          if (*s == '.')
4357                            s = parse_field_count (s + 1, &key->echar,
4358                                               N_("invalid number after '.'"));
4359                          if (!key->echar && key->eword)
4360                            {
4361                              /* obsolescent syntax +A.x -B.y is equivalent to:
4362                                   -k A+1.x+1,B.y   (when y = 0)
4363                                   -k A+1.x+1,B+1.y (when y > 0)
4364                                 So eword is decremented as in the -k case
4365                                 only when the end field (B) is specified and
4366                                 echar (y) is 0.  */
4367                              key->eword--;
4368                            }
4369                          if (*set_ordering (s, key, bl_end))
4370                            badfieldspec (optarg1,
4371                                      N_("stray character in field spec"));
4372                        }
4373                      key->traditional_used = true;
4374                      insertkey (key);
4375                    }
4376                }
4377            }
4378          if (! key)
4379            files[nfiles++] = optarg;
4380          break;
4381
4382        case SORT_OPTION:
4383          c = XARGMATCH ("--sort", optarg, sort_args, sort_types);
4384          FALLTHROUGH;
4385        case 'b':
4386        case 'd':
4387        case 'f':
4388        case 'g':
4389        case 'h':
4390        case 'i':
4391        case 'M':
4392        case 'n':
4393        case 'r':
4394        case 'R':
4395        case 'V':
4396          {
4397            char str[2];
4398            str[0] = c;
4399            str[1] = '\0';
4400            set_ordering (str, &gkey, bl_both);
4401          }
4402          break;
4403
4404        case CHECK_OPTION:
4405          c = (optarg
4406               ? XARGMATCH ("--check", optarg, check_args, check_types)
4407               : 'c');
4408          FALLTHROUGH;
4409        case 'c':
4410        case 'C':
4411          if (checkonly && checkonly != c)
4412            incompatible_options ("cC");
4413          checkonly = c;
4414          break;
4415
4416        case COMPRESS_PROGRAM_OPTION:
4417          if (compress_program && !STREQ (compress_program, optarg))
4418            die (SORT_FAILURE, 0, _("multiple compress programs specified"));
4419          compress_program = optarg;
4420          break;
4421
4422        case DEBUG_PROGRAM_OPTION:
4423          debug = true;
4424          break;
4425
4426        case FILES0_FROM_OPTION:
4427          files_from = optarg;
4428          break;
4429
4430        case 'k':
4431          key = key_init (&key_buf);
4432
4433          /* Get POS1. */
4434          s = parse_field_count (optarg, &key->sword,
4435                                 N_("invalid number at field start"));
4436          if (! key->sword--)
4437            {
4438              /* Provoke with 'sort -k0' */
4439              badfieldspec (optarg, N_("field number is zero"));
4440            }
4441          if (*s == '.')
4442            {
4443              s = parse_field_count (s + 1, &key->schar,
4444                                     N_("invalid number after '.'"));
4445              if (! key->schar--)
4446                {
4447                  /* Provoke with 'sort -k1.0' */
4448                  badfieldspec (optarg, N_("character offset is zero"));
4449                }
4450            }
4451          if (! (key->sword || key->schar))
4452            key->sword = SIZE_MAX;
4453          s = set_ordering (s, key, bl_start);
4454          if (*s != ',')
4455            {
4456              key->eword = SIZE_MAX;
4457              key->echar = 0;
4458            }
4459          else
4460            {
4461              /* Get POS2. */
4462              s = parse_field_count (s + 1, &key->eword,
4463                                     N_("invalid number after ','"));
4464              if (! key->eword--)
4465                {
4466                  /* Provoke with 'sort -k1,0' */
4467                  badfieldspec (optarg, N_("field number is zero"));
4468                }
4469              if (*s == '.')
4470                {
4471                  s = parse_field_count (s + 1, &key->echar,
4472                                         N_("invalid number after '.'"));
4473                }
4474              s = set_ordering (s, key, bl_end);
4475            }
4476          if (*s)
4477            badfieldspec (optarg, N_("stray character in field spec"));
4478          insertkey (key);
4479          break;
4480
4481        case 'm':
4482          mergeonly = true;
4483          break;
4484
4485        case NMERGE_OPTION:
4486          specify_nmerge (oi, c, optarg);
4487          break;
4488
4489        case 'o':
4490          if (outfile && !STREQ (outfile, optarg))
4491            die (SORT_FAILURE, 0, _("multiple output files specified"));
4492          outfile = optarg;
4493          break;
4494
4495        case RANDOM_SOURCE_OPTION:
4496          if (random_source && !STREQ (random_source, optarg))
4497            die (SORT_FAILURE, 0, _("multiple random sources specified"));
4498          random_source = optarg;
4499          break;
4500
4501        case 's':
4502          stable = true;
4503          break;
4504
4505        case 'S':
4506          specify_sort_size (oi, c, optarg);
4507          break;
4508
4509        case 't':
4510          {
4511            char newtab = optarg[0];
4512            if (! newtab)
4513              die (SORT_FAILURE, 0, _("empty tab"));
4514            if (optarg[1])
4515              {
4516                if (STREQ (optarg, "\\0"))
4517                  newtab = '\0';
4518                else
4519                  {
4520                    /* Provoke with 'sort -txx'.  Complain about
4521                       "multi-character tab" instead of "multibyte tab", so
4522                       that the diagnostic's wording does not need to be
4523                       changed once multibyte characters are supported.  */
4524                    die (SORT_FAILURE, 0, _("multi-character tab %s"),
4525                         quote (optarg));
4526                  }
4527              }
4528            if (tab != TAB_DEFAULT && tab != newtab)
4529              die (SORT_FAILURE, 0, _("incompatible tabs"));
4530            tab = newtab;
4531          }
4532          break;
4533
4534        case 'T':
4535          add_temp_dir (optarg);
4536          break;
4537
4538        case PARALLEL_OPTION:
4539          nthreads = specify_nthreads (oi, c, optarg);
4540          break;
4541
4542        case 'u':
4543          unique = true;
4544          break;
4545
4546        case 'y':
4547          /* Accept and ignore e.g. -y0 for compatibility with Solaris 2.x
4548             through Solaris 7.  It is also accepted by many non-Solaris
4549             "sort" implementations, e.g., AIX 5.2, HP-UX 11i v2, IRIX 6.5.
4550             -y is marked as obsolete starting with Solaris 8 (1999), but is
4551             still accepted as of Solaris 10 prerelease (2004).
4552
4553             Solaris 2.5.1 "sort -y 100" reads the input file "100", but
4554             emulate Solaris 8 and 9 "sort -y 100" which ignores the "100",
4555             and which in general ignores the argument after "-y" if it
4556             consists entirely of digits (it can even be empty).  */
4557          if (optarg == argv[optind - 1])
4558            {
4559              char const *p;
4560              for (p = optarg; ISDIGIT (*p); p++)
4561                continue;
4562              optind -= (*p != '\0');
4563            }
4564          break;
4565
4566        case 'z':
4567          eolchar = 0;
4568          break;
4569
4570        case_GETOPT_HELP_CHAR;
4571
4572        case_GETOPT_VERSION_CHAR (PROGRAM_NAME, AUTHORS);
4573
4574        default:
4575          usage (SORT_FAILURE);
4576        }
4577    }
4578
4579  if (files_from)
4580    {
4581      FILE *stream;
4582
4583      /* When using --files0-from=F, you may not specify any files
4584         on the command-line.  */
4585      if (nfiles)
4586        {
4587          error (0, 0, _("extra operand %s"), quoteaf (files[0]));
4588          fprintf (stderr, "%s\n",
4589                   _("file operands cannot be combined with --files0-from"));
4590          usage (SORT_FAILURE);
4591        }
4592
4593      if (STREQ (files_from, "-"))
4594        stream = stdin;
4595      else
4596        {
4597          stream = fopen (files_from, "r");
4598          if (stream == NULL)
4599            die (SORT_FAILURE, errno, _("cannot open %s for reading"),
4600                 quoteaf (files_from));
4601        }
4602
4603      readtokens0_init (&tok);
4604
4605      if (! readtokens0 (stream, &tok) || fclose (stream) != 0)
4606        die (SORT_FAILURE, 0, _("cannot read file names from %s"),
4607             quoteaf (files_from));
4608
4609      if (tok.n_tok)
4610        {
4611          free (files);
4612          files = tok.tok;
4613          nfiles = tok.n_tok;
4614          for (size_t i = 0; i < nfiles; i++)
4615            {
4616              if (STREQ (files[i], "-"))
4617                die (SORT_FAILURE, 0, _("when reading file names from stdin, "
4618                                        "no file name of %s allowed"),
4619                     quoteaf (files[i]));
4620              else if (files[i][0] == '\0')
4621                {
4622                  /* Using the standard 'filename:line-number:' prefix here is
4623                     not totally appropriate, since NUL is the separator,
4624                     not NL, but it might be better than nothing.  */
4625                  unsigned long int file_number = i + 1;
4626                  die (SORT_FAILURE, 0,
4627                       _("%s:%lu: invalid zero-length file name"),
4628                       quotef (files_from), file_number);
4629                }
4630            }
4631        }
4632      else
4633        die (SORT_FAILURE, 0, _("no input from %s"),
4634             quoteaf (files_from));
4635    }
4636
4637  /* Inheritance of global options to individual keys. */
4638  for (key = keylist; key; key = key->next)
4639    {
4640      if (default_key_compare (key) && !key->reverse)
4641        {
4642          key->ignore = gkey.ignore;
4643          key->translate = gkey.translate;
4644          key->skipsblanks = gkey.skipsblanks;
4645          key->skipeblanks = gkey.skipeblanks;
4646          key->month = gkey.month;
4647          key->numeric = gkey.numeric;
4648          key->general_numeric = gkey.general_numeric;
4649          key->human_numeric = gkey.human_numeric;
4650          key->version = gkey.version;
4651          key->random = gkey.random;
4652          key->reverse = gkey.reverse;
4653        }
4654
4655      need_random |= key->random;
4656    }
4657
4658  if (!keylist && !default_key_compare (&gkey))
4659    {
4660      gkey_only = true;
4661      insertkey (&gkey);
4662      need_random |= gkey.random;
4663    }
4664
4665  check_ordering_compatibility ();
4666
4667  if (debug)
4668    {
4669      if (checkonly || outfile)
4670        {
4671          static char opts[] = "X --debug";
4672          opts[0] = (checkonly ? checkonly : 'o');
4673          incompatible_options (opts);
4674        }
4675
4676      /* Always output the locale in debug mode, since this
4677         is such a common source of confusion.  */
4678      if (hard_LC_COLLATE)
4679        error (0, 0, _("using %s sorting rules"),
4680               quote (setlocale (LC_COLLATE, NULL)));
4681      else
4682        {
4683          /* OpenBSD can only set some categories with LC_ALL above,
4684             so set LC_COLLATE explicitly to flag errors.  */
4685          if (locale_ok)
4686            locale_ok = !! setlocale (LC_COLLATE, "");
4687          error (0, 0, "%s%s", locale_ok ? "" : _("failed to set locale; "),
4688                 _("using simple byte comparison"));
4689        }
4690      key_warnings (&gkey, gkey_only);
4691    }
4692
4693  reverse = gkey.reverse;
4694
4695  if (need_random)
4696    random_md5_state_init (random_source);
4697
4698  if (temp_dir_count == 0)
4699    {
4700      char const *tmp_dir = getenv ("TMPDIR");
4701      add_temp_dir (tmp_dir ? tmp_dir : DEFAULT_TMPDIR);
4702    }
4703
4704  if (nfiles == 0)
4705    {
4706      nfiles = 1;
4707      free (files);
4708      files = xmalloc (sizeof *files);
4709      *files = (char *) "-";
4710    }
4711
4712  /* Need to re-check that we meet the minimum requirement for memory
4713     usage with the final value for NMERGE. */
4714  if (0 < sort_size)
4715    sort_size = MAX (sort_size, MIN_SORT_SIZE);
4716
4717  if (checkonly)
4718    {
4719      if (nfiles > 1)
4720        die (SORT_FAILURE, 0, _("extra operand %s not allowed with -%c"),
4721             quoteaf (files[1]), checkonly);
4722
4723      if (outfile)
4724        {
4725          static char opts[] = {0, 'o', 0};
4726          opts[0] = checkonly;
4727          incompatible_options (opts);
4728        }
4729
4730      /* POSIX requires that sort return 1 IFF invoked with -c or -C and the
4731         input is not properly sorted.  */
4732      return check (files[0], checkonly) ? EXIT_SUCCESS : SORT_OUT_OF_ORDER;
4733    }
4734
4735  /* Check all inputs are accessible, or exit immediately.  */
4736  check_inputs (files, nfiles);
4737
4738  /* Check output is writable, or exit immediately.  */
4739  check_output (outfile);
4740
4741  if (mergeonly)
4742    {
4743      struct sortfile *sortfiles = xcalloc (nfiles, sizeof *sortfiles);
4744
4745      for (size_t i = 0; i < nfiles; ++i)
4746        sortfiles[i].name = files[i];
4747
4748      merge (sortfiles, 0, nfiles, outfile);
4749      IF_LINT (free (sortfiles));
4750    }
4751  else
4752    {
4753      if (!nthreads)
4754        {
4755          unsigned long int np = num_processors (NPROC_CURRENT_OVERRIDABLE);
4756          nthreads = MIN (np, DEFAULT_MAX_THREADS);
4757        }
4758
4759      /* Avoid integer overflow later.  */
4760      size_t nthreads_max = SIZE_MAX / (2 * sizeof (struct merge_node));
4761      nthreads = MIN (nthreads, nthreads_max);
4762
4763      sort (files, nfiles, outfile, nthreads);
4764    }
4765
4766#ifdef lint
4767  if (files_from)
4768    readtokens0_free (&tok);
4769  else
4770    free (files);
4771#endif
4772
4773  if (have_read_stdin && fclose (stdin) == EOF)
4774    sort_die (_("close failed"), "-");
4775
4776  return EXIT_SUCCESS;
4777}
4778