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