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