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 "error.h"
35#include "fadvise.h"
36#include "filevercmp.h"
37#include "flexmember.h"
38#include "hard-locale.h"
39#include "hash.h"
40#include "heap.h"
41#include "ignore-value.h"
42#include "md5.h"
43#include "mbswidth.h"
44#include "nproc.h"
45#include "physmem.h"
46#include "posixver.h"
47#include "quote.h"
48#include "randread.h"
49#include "readtokens0.h"
50#include "stdio--.h"
51#include "stdlib--.h"
52#include "strnumcmp.h"
53#include "xmemcoll.h"
54#include "xnanosleep.h"
55#include "xstrtol.h"
56
57#ifndef RLIMIT_DATA
58struct rlimit { size_t rlim_cur; };
59# define getrlimit(Resource, Rlp) (-1)
60#endif
61
62/* The official name of this program (e.g., no 'g' prefix).  */
63#define PROGRAM_NAME "sort"
64
65#define AUTHORS \
66  proper_name ("Mike Haertel"), \
67  proper_name ("Paul Eggert")
68
69#if HAVE_LANGINFO_CODESET
70# include <langinfo.h>
71#endif
72
73/* Use SA_NOCLDSTOP as a proxy for whether the sigaction machinery is
74   present.  */
75#ifndef SA_NOCLDSTOP
76# define SA_NOCLDSTOP 0
77/* No sigprocmask.  Always 'return' zero. */
78# define sigprocmask(How, Set, Oset) (0)
79# define sigset_t int
80# if ! HAVE_SIGINTERRUPT
81#  define siginterrupt(sig, flag) /* empty */
82# endif
83#endif
84
85#if !defined OPEN_MAX && defined NR_OPEN
86# define OPEN_MAX NR_OPEN
87#endif
88#if !defined OPEN_MAX
89# define OPEN_MAX 20
90#endif
91
92#define UCHAR_LIM (UCHAR_MAX + 1)
93
94#if HAVE_C99_STRTOLD
95# define long_double long double
96#else
97# define long_double double
98# undef strtold
99# define strtold strtod
100#endif
101
102#ifndef DEFAULT_TMPDIR
103# define DEFAULT_TMPDIR "/tmp"
104#endif
105
106/* Maximum number of lines to merge every time a NODE is taken from
107   the merge queue.  Node is at LEVEL in the binary merge tree,
108   and is responsible for merging TOTAL lines. */
109#define MAX_MERGE(total, level) (((total) >> (2 * ((level) + 1))) + 1)
110
111/* Heuristic value for the number of lines for which it is worth creating
112   a subthread, during an internal merge sort.  I.e., it is a small number
113   of "average" lines for which sorting via two threads is faster than
114   sorting via one on an "average" system.  On a dual-core 2.0 GHz i686
115   system with 3GB of RAM and 2MB of L2 cache, a file containing 128K
116   lines of gensort -a output is sorted slightly faster with --parallel=2
117   than with --parallel=1.  By contrast, using --parallel=1 is about 10%
118   faster than using --parallel=2 with a 64K-line input.  */
119enum { SUBTHREAD_LINES_HEURISTIC = 128 * 1024 };
120verify (4 <= SUBTHREAD_LINES_HEURISTIC);
121
122/* The number of threads after which there are
123   diminishing performance gains.  */
124enum { DEFAULT_MAX_THREADS = 8 };
125
126/* Exit statuses.  */
127enum
128  {
129    /* POSIX says to exit with status 1 if invoked with -c and the
130       input is not properly sorted.  */
131    SORT_OUT_OF_ORDER = 1,
132
133    /* POSIX says any other irregular exit must exit with a status
134       code greater than 1.  */
135    SORT_FAILURE = 2
136  };
137
138enum
139  {
140    /* The number of times we should try to fork a compression process
141       (we retry if the fork call fails).  We don't _need_ to compress
142       temp files, this is just to reduce disk access, so this number
143       can be small.  Each retry doubles in duration.  */
144    MAX_FORK_TRIES_COMPRESS = 4,
145
146    /* The number of times we should try to fork a decompression process.
147       If we can't fork a decompression process, we can't sort, so this
148       number should be big.  Each retry doubles in duration.  */
149    MAX_FORK_TRIES_DECOMPRESS = 9
150  };
151
152enum
153  {
154    /* Level of the end-of-merge node, one level above the root. */
155    MERGE_END = 0,
156
157    /* Level of the root node in merge tree. */
158    MERGE_ROOT = 1
159  };
160
161/* The representation of the decimal point in the current locale.  */
162static int decimal_point;
163
164/* Thousands separator; if -1, then there isn't one.  */
165static int thousands_sep;
166
167/* Nonzero if the corresponding locales are hard.  */
168static bool hard_LC_COLLATE;
169#if HAVE_NL_LANGINFO
170static bool hard_LC_TIME;
171#endif
172
173#define NONZERO(x) ((x) != 0)
174
175/* The kind of blanks for '-b' to skip in various options. */
176enum blanktype { bl_start, bl_end, bl_both };
177
178/* The character marking end of line. Default to \n. */
179static char eolchar = '\n';
180
181/* Lines are held in core as counted strings. */
182struct line
183{
184  char *text;			/* Text of the line. */
185  size_t length;		/* Length including final newline. */
186  char *keybeg;			/* Start of first key. */
187  char *keylim;			/* Limit of first key. */
188};
189
190/* Input buffers. */
191struct buffer
192{
193  char *buf;			/* Dynamically allocated buffer,
194                                   partitioned into 3 regions:
195                                   - input data;
196                                   - unused area;
197                                   - an array of lines, in reverse order.  */
198  size_t used;			/* Number of bytes used for input data.  */
199  size_t nlines;		/* Number of lines in the line array.  */
200  size_t alloc;			/* Number of bytes allocated. */
201  size_t left;			/* Number of bytes left from previous reads. */
202  size_t line_bytes;		/* Number of bytes to reserve for each line. */
203  bool eof;			/* An EOF has been read.  */
204};
205
206/* Sort key.  */
207struct keyfield
208{
209  size_t sword;			/* Zero-origin 'word' to start at. */
210  size_t schar;			/* Additional characters to skip. */
211  size_t eword;			/* Zero-origin last 'word' of key. */
212  size_t echar;			/* Additional characters in field. */
213  bool const *ignore;		/* Boolean array of characters to ignore. */
214  char const *translate;	/* Translation applied to characters. */
215  bool skipsblanks;		/* Skip leading blanks when finding start.  */
216  bool skipeblanks;		/* Skip leading blanks when finding end.  */
217  bool numeric;			/* Flag for numeric comparison.  Handle
218                                   strings of digits with optional decimal
219                                   point, but no exponential notation. */
220  bool random;			/* Sort by random hash of key.  */
221  bool general_numeric;		/* Flag for general, numeric comparison.
222                                   Handle numbers in exponential notation. */
223  bool human_numeric;		/* Flag for sorting by human readable
224                                   units with either SI or IEC prefixes. */
225  bool month;			/* Flag for comparison by month name. */
226  bool reverse;			/* Reverse the sense of comparison. */
227  bool version;			/* sort by version number */
228  bool traditional_used;	/* Traditional key option format is used. */
229  struct keyfield *next;	/* Next keyfield to try. */
230};
231
232struct month
233{
234  char const *name;
235  int val;
236};
237
238/* Binary merge tree node. */
239struct merge_node
240{
241  struct line *lo;              /* Lines to merge from LO child node. */
242  struct line *hi;              /* Lines to merge from HI child node. */
243  struct line *end_lo;          /* End of available lines from LO. */
244  struct line *end_hi;          /* End of available lines from HI. */
245  struct line **dest;           /* Pointer to destination of merge. */
246  size_t nlo;                   /* Total Lines remaining from LO. */
247  size_t nhi;                   /* Total lines remaining from HI. */
248  struct merge_node *parent;    /* Parent node. */
249  struct merge_node *lo_child;  /* LO child node. */
250  struct merge_node *hi_child;  /* HI child node. */
251  unsigned int level;           /* Level in merge tree. */
252  bool queued;                  /* Node is already in heap. */
253  pthread_mutex_t lock;         /* Lock for node operations. */
254};
255
256/* Priority queue of merge nodes. */
257struct merge_node_queue
258{
259  struct heap *priority_queue;  /* Priority queue of merge tree nodes. */
260  pthread_mutex_t mutex;        /* Lock for queue operations. */
261  pthread_cond_t cond;          /* Conditional wait for empty queue to populate
262                                   when popping. */
263};
264
265/* Used to implement --unique (-u).  */
266static struct line saved_line;
267
268/* FIXME: None of these tables work with multibyte character sets.
269   Also, there are many other bugs when handling multibyte characters.
270   One way to fix this is to rewrite 'sort' to use wide characters
271   internally, but doing this with good performance is a bit
272   tricky.  */
273
274/* Table of blanks.  */
275static bool blanks[UCHAR_LIM];
276
277/* Table of non-printing characters. */
278static bool nonprinting[UCHAR_LIM];
279
280/* Table of non-dictionary characters (not letters, digits, or blanks). */
281static bool nondictionary[UCHAR_LIM];
282
283/* Translation table folding lower case to upper.  */
284static char fold_toupper[UCHAR_LIM];
285
286#define MONTHS_PER_YEAR 12
287
288/* Table mapping month names to integers.
289   Alphabetic order allows binary search. */
290static struct month monthtab[] =
291{
292  {"APR", 4},
293  {"AUG", 8},
294  {"DEC", 12},
295  {"FEB", 2},
296  {"JAN", 1},
297  {"JUL", 7},
298  {"JUN", 6},
299  {"MAR", 3},
300  {"MAY", 5},
301  {"NOV", 11},
302  {"OCT", 10},
303  {"SEP", 9}
304};
305
306/* During the merge phase, the number of files to merge at once. */
307#define NMERGE_DEFAULT 16
308
309/* Minimum size for a merge or check buffer.  */
310#define MIN_MERGE_BUFFER_SIZE (2 + sizeof (struct line))
311
312/* Minimum sort size; the code might not work with smaller sizes.  */
313#define MIN_SORT_SIZE (nmerge * MIN_MERGE_BUFFER_SIZE)
314
315/* The number of bytes needed for a merge or check buffer, which can
316   function relatively efficiently even if it holds only one line.  If
317   a longer line is seen, this value is increased.  */
318static size_t merge_buffer_size = MAX (MIN_MERGE_BUFFER_SIZE, 256 * 1024);
319
320/* The approximate maximum number of bytes of main memory to use, as
321   specified by the user.  Zero if the user has not specified a size.  */
322static size_t sort_size;
323
324/* The initial allocation factor for non-regular files.
325   This is used, e.g., when reading from a pipe.
326   Don't make it too big, since it is multiplied by ~130 to
327   obtain the size of the actual buffer sort will allocate.
328   Also, there may be 8 threads all doing this at the same time.  */
329#define INPUT_FILE_SIZE_GUESS (128 * 1024)
330
331/* Array of directory names in which any temporary files are to be created. */
332static char const **temp_dirs;
333
334/* Number of temporary directory names used.  */
335static size_t temp_dir_count;
336
337/* Number of allocated slots in temp_dirs.  */
338static size_t temp_dir_alloc;
339
340/* Flag to reverse the order of all comparisons. */
341static bool reverse;
342
343/* Flag for stable sort.  This turns off the last ditch bytewise
344   comparison of lines, and instead leaves lines in the same order
345   they were read if all keys compare equal.  */
346static bool stable;
347
348/* If TAB has this value, blanks separate fields.  */
349enum { TAB_DEFAULT = CHAR_MAX + 1 };
350
351/* Tab character separating fields.  If TAB_DEFAULT, then fields are
352   separated by the empty string between a non-blank character and a blank
353   character. */
354static int tab = TAB_DEFAULT;
355
356/* Flag to remove consecutive duplicate lines from the output.
357   Only the last of a sequence of equal lines will be output. */
358static bool unique;
359
360/* Nonzero if any of the input files are the standard input. */
361static bool have_read_stdin;
362
363/* List of key field comparisons to be tried.  */
364static struct keyfield *keylist;
365
366/* Program used to (de)compress temp files.  Must accept -d.  */
367static char const *compress_program;
368
369/* Annotate the output with extra info to aid the user.  */
370static bool debug;
371
372/* Maximum number of files to merge in one go.  If more than this
373   number are present, temp files will be used. */
374static unsigned int nmerge = NMERGE_DEFAULT;
375
376/* Output an error to stderr using async-signal-safe routines, and _exit().
377   This can be used safely from signal handlers,
378   and between fork() and exec() of multithreaded processes.  */
379
380static void async_safe_die (int, const char *) ATTRIBUTE_NORETURN;
381static void
382async_safe_die (int errnum, const char *errstr)
383{
384  ignore_value (write (STDERR_FILENO, errstr, strlen (errstr)));
385
386  /* Even if defined HAVE_STRERROR_R, we can't use it,
387     as it may return a translated string etc. and even if not
388     may malloc() which is unsafe.  We might improve this
389     by testing for sys_errlist and using that if available.
390     For now just report the error number.  */
391  if (errnum)
392    {
393      char errbuf[INT_BUFSIZE_BOUND (errnum)];
394      char *p = inttostr (errnum, errbuf);
395      ignore_value (write (STDERR_FILENO, ": errno ", 8));
396      ignore_value (write (STDERR_FILENO, p, strlen (p)));
397    }
398
399  ignore_value (write (STDERR_FILENO, "\n", 1));
400
401  _exit (SORT_FAILURE);
402}
403
404/* Report MESSAGE for FILE, then clean up and exit.
405   If FILE is null, it represents standard output.  */
406
407static void die (char const *, char const *) ATTRIBUTE_NORETURN;
408static void
409die (char const *message, char const *file)
410{
411  error (0, errno, "%s: %s", message,
412         quotef (file ? file : _("standard output")));
413  exit (SORT_FAILURE);
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    error (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        error (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        error (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        error (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    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        die (_("fflush failed"), file);
999      break;
1000
1001    default:
1002      if (fclose (fp) != 0)
1003        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    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        error (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              error (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      error (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    error (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        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                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    die (_("open failed"), random_source);
2088  randread (r, buf, sizeof buf);
2089  if (randread_free (r) != 0)
2090    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      error (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            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        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    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        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        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            die (_("open failed"), output_file);
3865        }
3866      else if (nopened <= 2)
3867        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  error (SORT_FAILURE, 0, _("%s: invalid field specification %s"),
4038         _(msgid), quote (spec));
4039  abort ();
4040}
4041
4042/* Report incompatible options.  */
4043
4044static void incompatible_options (char const *) ATTRIBUTE_NORETURN;
4045static void
4046incompatible_options (char const *opts)
4047{
4048  error (SORT_FAILURE, 0, _("options '-%s' are incompatible"), (opts));
4049  abort ();
4050}
4051
4052/* Check compatibility of ordering options.  */
4053
4054static void
4055check_ordering_compatibility (void)
4056{
4057  struct keyfield *key;
4058
4059  for (key = keylist; key; key = key->next)
4060    if (1 < (key->numeric + key->general_numeric + key->human_numeric
4061             + key->month + (key->version | key->random | !!key->ignore)))
4062      {
4063        /* The following is too big, but guaranteed to be "big enough".  */
4064        char opts[sizeof short_options];
4065        /* Clear flags we're not interested in.  */
4066        key->skipsblanks = key->skipeblanks = key->reverse = false;
4067        key_to_opts (key, opts);
4068        incompatible_options (opts);
4069      }
4070}
4071
4072/* Parse the leading integer in STRING and store the resulting value
4073   (which must fit into size_t) into *VAL.  Return the address of the
4074   suffix after the integer.  If the value is too large, silently
4075   substitute SIZE_MAX.  If MSGID is NULL, return NULL after
4076   failure; otherwise, report MSGID and exit on failure.  */
4077
4078static char const *
4079parse_field_count (char const *string, size_t *val, char const *msgid)
4080{
4081  char *suffix;
4082  uintmax_t n;
4083
4084  switch (xstrtoumax (string, &suffix, 10, &n, ""))
4085    {
4086    case LONGINT_OK:
4087    case LONGINT_INVALID_SUFFIX_CHAR:
4088      *val = n;
4089      if (*val == n)
4090        break;
4091      /* Fall through.  */
4092    case LONGINT_OVERFLOW:
4093    case LONGINT_OVERFLOW | LONGINT_INVALID_SUFFIX_CHAR:
4094      *val = SIZE_MAX;
4095      break;
4096
4097    case LONGINT_INVALID:
4098      if (msgid)
4099        error (SORT_FAILURE, 0, _("%s: invalid count at start of %s"),
4100               _(msgid), quote (string));
4101      return NULL;
4102    }
4103
4104  return suffix;
4105}
4106
4107/* Handle interrupts and hangups. */
4108
4109static void
4110sighandler (int sig)
4111{
4112  if (! SA_NOCLDSTOP)
4113    signal (sig, SIG_IGN);
4114
4115  cleanup ();
4116
4117  signal (sig, SIG_DFL);
4118  raise (sig);
4119}
4120
4121/* Set the ordering options for KEY specified in S.
4122   Return the address of the first character in S that
4123   is not a valid ordering option.
4124   BLANKTYPE is the kind of blanks that 'b' should skip. */
4125
4126static char *
4127set_ordering (char const *s, struct keyfield *key, enum blanktype blanktype)
4128{
4129  while (*s)
4130    {
4131      switch (*s)
4132        {
4133        case 'b':
4134          if (blanktype == bl_start || blanktype == bl_both)
4135            key->skipsblanks = true;
4136          if (blanktype == bl_end || blanktype == bl_both)
4137            key->skipeblanks = true;
4138          break;
4139        case 'd':
4140          key->ignore = nondictionary;
4141          break;
4142        case 'f':
4143          key->translate = fold_toupper;
4144          break;
4145        case 'g':
4146          key->general_numeric = true;
4147          break;
4148        case 'h':
4149          key->human_numeric = true;
4150          break;
4151        case 'i':
4152          /* Option order should not matter, so don't let -i override
4153             -d.  -d implies -i, but -i does not imply -d.  */
4154          if (! key->ignore)
4155            key->ignore = nonprinting;
4156          break;
4157        case 'M':
4158          key->month = true;
4159          break;
4160        case 'n':
4161          key->numeric = true;
4162          break;
4163        case 'R':
4164          key->random = true;
4165          break;
4166        case 'r':
4167          key->reverse = true;
4168          break;
4169        case 'V':
4170          key->version = true;
4171          break;
4172        default:
4173          return (char *) s;
4174        }
4175      ++s;
4176    }
4177  return (char *) s;
4178}
4179
4180/* Initialize KEY.  */
4181
4182static struct keyfield *
4183key_init (struct keyfield *key)
4184{
4185  memset (key, 0, sizeof *key);
4186  key->eword = SIZE_MAX;
4187  return key;
4188}
4189
4190int
4191main (int argc, char **argv)
4192{
4193  struct keyfield *key;
4194  struct keyfield key_buf;
4195  struct keyfield gkey;
4196  bool gkey_only = false;
4197  char const *s;
4198  int c = 0;
4199  char checkonly = 0;
4200  bool mergeonly = false;
4201  char *random_source = NULL;
4202  bool need_random = false;
4203  size_t nthreads = 0;
4204  size_t nfiles = 0;
4205  bool posixly_correct = (getenv ("POSIXLY_CORRECT") != NULL);
4206  int posix_ver = posix2_version ();
4207  bool traditional_usage = ! (200112 <= posix_ver && posix_ver < 200809);
4208  char **files;
4209  char *files_from = NULL;
4210  struct Tokens tok;
4211  char const *outfile = NULL;
4212  bool locale_ok;
4213
4214  initialize_main (&argc, &argv);
4215  set_program_name (argv[0]);
4216  locale_ok = !! setlocale (LC_ALL, "");
4217  bindtextdomain (PACKAGE, LOCALEDIR);
4218  textdomain (PACKAGE);
4219
4220  initialize_exit_failure (SORT_FAILURE);
4221
4222  hard_LC_COLLATE = hard_locale (LC_COLLATE);
4223#if HAVE_NL_LANGINFO
4224  hard_LC_TIME = hard_locale (LC_TIME);
4225#endif
4226
4227  /* Get locale's representation of the decimal point.  */
4228  {
4229    struct lconv const *locale = localeconv ();
4230
4231    /* If the locale doesn't define a decimal point, or if the decimal
4232       point is multibyte, use the C locale's decimal point.  FIXME:
4233       add support for multibyte decimal points.  */
4234    decimal_point = to_uchar (locale->decimal_point[0]);
4235    if (! decimal_point || locale->decimal_point[1])
4236      decimal_point = '.';
4237
4238    /* FIXME: add support for multibyte thousands separators.  */
4239    thousands_sep = to_uchar (*locale->thousands_sep);
4240    if (! thousands_sep || locale->thousands_sep[1])
4241      thousands_sep = -1;
4242  }
4243
4244  have_read_stdin = false;
4245  inittables ();
4246
4247  {
4248    size_t i;
4249    static int const sig[] =
4250      {
4251        /* The usual suspects.  */
4252        SIGALRM, SIGHUP, SIGINT, SIGPIPE, SIGQUIT, SIGTERM,
4253#ifdef SIGPOLL
4254        SIGPOLL,
4255#endif
4256#ifdef SIGPROF
4257        SIGPROF,
4258#endif
4259#ifdef SIGVTALRM
4260        SIGVTALRM,
4261#endif
4262#ifdef SIGXCPU
4263        SIGXCPU,
4264#endif
4265#ifdef SIGXFSZ
4266        SIGXFSZ,
4267#endif
4268      };
4269    enum { nsigs = ARRAY_CARDINALITY (sig) };
4270
4271#if SA_NOCLDSTOP
4272    struct sigaction act;
4273
4274    sigemptyset (&caught_signals);
4275    for (i = 0; i < nsigs; i++)
4276      {
4277        sigaction (sig[i], NULL, &act);
4278        if (act.sa_handler != SIG_IGN)
4279          sigaddset (&caught_signals, sig[i]);
4280      }
4281
4282    act.sa_handler = sighandler;
4283    act.sa_mask = caught_signals;
4284    act.sa_flags = 0;
4285
4286    for (i = 0; i < nsigs; i++)
4287      if (sigismember (&caught_signals, sig[i]))
4288        sigaction (sig[i], &act, NULL);
4289#else
4290    for (i = 0; i < nsigs; i++)
4291      if (signal (sig[i], SIG_IGN) != SIG_IGN)
4292        {
4293          signal (sig[i], sighandler);
4294          siginterrupt (sig[i], 1);
4295        }
4296#endif
4297  }
4298  signal (SIGCHLD, SIG_DFL); /* Don't inherit CHLD handling from parent.  */
4299
4300  /* The signal mask is known, so it is safe to invoke exit_cleanup.  */
4301  atexit (exit_cleanup);
4302
4303  key_init (&gkey);
4304  gkey.sword = SIZE_MAX;
4305
4306  files = xnmalloc (argc, sizeof *files);
4307
4308  while (true)
4309    {
4310      /* Parse an operand as a file after "--" was seen; or if
4311         pedantic and a file was seen, unless the POSIX version
4312         is not 1003.1-2001 and -c was not seen and the operand is
4313         "-o FILE" or "-oFILE".  */
4314      int oi = -1;
4315
4316      if (c == -1
4317          || (posixly_correct && nfiles != 0
4318              && ! (traditional_usage
4319                    && ! checkonly
4320                    && optind != argc
4321                    && argv[optind][0] == '-' && argv[optind][1] == 'o'
4322                    && (argv[optind][2] || optind + 1 != argc)))
4323          || ((c = getopt_long (argc, argv, short_options,
4324                                long_options, &oi))
4325              == -1))
4326        {
4327          if (argc <= optind)
4328            break;
4329          files[nfiles++] = argv[optind++];
4330        }
4331      else switch (c)
4332        {
4333        case 1:
4334          key = NULL;
4335          if (optarg[0] == '+')
4336            {
4337              bool minus_pos_usage = (optind != argc && argv[optind][0] == '-'
4338                                      && ISDIGIT (argv[optind][1]));
4339              traditional_usage |= minus_pos_usage && !posixly_correct;
4340              if (traditional_usage)
4341                {
4342                  /* Treat +POS1 [-POS2] as a key if possible; but silently
4343                     treat an operand as a file if it is not a valid +POS1.  */
4344                  key = key_init (&key_buf);
4345                  s = parse_field_count (optarg + 1, &key->sword, NULL);
4346                  if (s && *s == '.')
4347                    s = parse_field_count (s + 1, &key->schar, NULL);
4348                  if (! (key->sword || key->schar))
4349                    key->sword = SIZE_MAX;
4350                  if (! s || *set_ordering (s, key, bl_start))
4351                    key = NULL;
4352                  else
4353                    {
4354                      if (minus_pos_usage)
4355                        {
4356                          char const *optarg1 = argv[optind++];
4357                          s = parse_field_count (optarg1 + 1, &key->eword,
4358                                             N_("invalid number after '-'"));
4359                          /* When called with a non-NULL message ID,
4360                             parse_field_count cannot return NULL.  Tell static
4361                             analysis tools that dereferencing S is safe.  */
4362                          assert (s);
4363                          if (*s == '.')
4364                            s = parse_field_count (s + 1, &key->echar,
4365                                               N_("invalid number after '.'"));
4366                          if (!key->echar && key->eword)
4367                            {
4368                              /* obsolescent syntax +A.x -B.y is equivalent to:
4369                                   -k A+1.x+1,B.y   (when y = 0)
4370                                   -k A+1.x+1,B+1.y (when y > 0)
4371                                 So eword is decremented as in the -k case
4372                                 only when the end field (B) is specified and
4373                                 echar (y) is 0.  */
4374                              key->eword--;
4375                            }
4376                          if (*set_ordering (s, key, bl_end))
4377                            badfieldspec (optarg1,
4378                                      N_("stray character in field spec"));
4379                        }
4380                      key->traditional_used = true;
4381                      insertkey (key);
4382                    }
4383                }
4384            }
4385          if (! key)
4386            files[nfiles++] = optarg;
4387          break;
4388
4389        case SORT_OPTION:
4390          c = XARGMATCH ("--sort", optarg, sort_args, sort_types);
4391          /* Fall through. */
4392        case 'b':
4393        case 'd':
4394        case 'f':
4395        case 'g':
4396        case 'h':
4397        case 'i':
4398        case 'M':
4399        case 'n':
4400        case 'r':
4401        case 'R':
4402        case 'V':
4403          {
4404            char str[2];
4405            str[0] = c;
4406            str[1] = '\0';
4407            set_ordering (str, &gkey, bl_both);
4408          }
4409          break;
4410
4411        case CHECK_OPTION:
4412          c = (optarg
4413               ? XARGMATCH ("--check", optarg, check_args, check_types)
4414               : 'c');
4415          /* Fall through.  */
4416        case 'c':
4417        case 'C':
4418          if (checkonly && checkonly != c)
4419            incompatible_options ("cC");
4420          checkonly = c;
4421          break;
4422
4423        case COMPRESS_PROGRAM_OPTION:
4424          if (compress_program && !STREQ (compress_program, optarg))
4425            error (SORT_FAILURE, 0, _("multiple compress programs specified"));
4426          compress_program = optarg;
4427          break;
4428
4429        case DEBUG_PROGRAM_OPTION:
4430          debug = true;
4431          break;
4432
4433        case FILES0_FROM_OPTION:
4434          files_from = optarg;
4435          break;
4436
4437        case 'k':
4438          key = key_init (&key_buf);
4439
4440          /* Get POS1. */
4441          s = parse_field_count (optarg, &key->sword,
4442                                 N_("invalid number at field start"));
4443          if (! key->sword--)
4444            {
4445              /* Provoke with 'sort -k0' */
4446              badfieldspec (optarg, N_("field number is zero"));
4447            }
4448          if (*s == '.')
4449            {
4450              s = parse_field_count (s + 1, &key->schar,
4451                                     N_("invalid number after '.'"));
4452              if (! key->schar--)
4453                {
4454                  /* Provoke with 'sort -k1.0' */
4455                  badfieldspec (optarg, N_("character offset is zero"));
4456                }
4457            }
4458          if (! (key->sword || key->schar))
4459            key->sword = SIZE_MAX;
4460          s = set_ordering (s, key, bl_start);
4461          if (*s != ',')
4462            {
4463              key->eword = SIZE_MAX;
4464              key->echar = 0;
4465            }
4466          else
4467            {
4468              /* Get POS2. */
4469              s = parse_field_count (s + 1, &key->eword,
4470                                     N_("invalid number after ','"));
4471              if (! key->eword--)
4472                {
4473                  /* Provoke with 'sort -k1,0' */
4474                  badfieldspec (optarg, N_("field number is zero"));
4475                }
4476              if (*s == '.')
4477                {
4478                  s = parse_field_count (s + 1, &key->echar,
4479                                         N_("invalid number after '.'"));
4480                }
4481              s = set_ordering (s, key, bl_end);
4482            }
4483          if (*s)
4484            badfieldspec (optarg, N_("stray character in field spec"));
4485          insertkey (key);
4486          break;
4487
4488        case 'm':
4489          mergeonly = true;
4490          break;
4491
4492        case NMERGE_OPTION:
4493          specify_nmerge (oi, c, optarg);
4494          break;
4495
4496        case 'o':
4497          if (outfile && !STREQ (outfile, optarg))
4498            error (SORT_FAILURE, 0, _("multiple output files specified"));
4499          outfile = optarg;
4500          break;
4501
4502        case RANDOM_SOURCE_OPTION:
4503          if (random_source && !STREQ (random_source, optarg))
4504            error (SORT_FAILURE, 0, _("multiple random sources specified"));
4505          random_source = optarg;
4506          break;
4507
4508        case 's':
4509          stable = true;
4510          break;
4511
4512        case 'S':
4513          specify_sort_size (oi, c, optarg);
4514          break;
4515
4516        case 't':
4517          {
4518            char newtab = optarg[0];
4519            if (! newtab)
4520              error (SORT_FAILURE, 0, _("empty tab"));
4521            if (optarg[1])
4522              {
4523                if (STREQ (optarg, "\\0"))
4524                  newtab = '\0';
4525                else
4526                  {
4527                    /* Provoke with 'sort -txx'.  Complain about
4528                       "multi-character tab" instead of "multibyte tab", so
4529                       that the diagnostic's wording does not need to be
4530                       changed once multibyte characters are supported.  */
4531                    error (SORT_FAILURE, 0, _("multi-character tab %s"),
4532                           quote (optarg));
4533                  }
4534              }
4535            if (tab != TAB_DEFAULT && tab != newtab)
4536              error (SORT_FAILURE, 0, _("incompatible tabs"));
4537            tab = newtab;
4538          }
4539          break;
4540
4541        case 'T':
4542          add_temp_dir (optarg);
4543          break;
4544
4545        case PARALLEL_OPTION:
4546          nthreads = specify_nthreads (oi, c, optarg);
4547          break;
4548
4549        case 'u':
4550          unique = true;
4551          break;
4552
4553        case 'y':
4554          /* Accept and ignore e.g. -y0 for compatibility with Solaris 2.x
4555             through Solaris 7.  It is also accepted by many non-Solaris
4556             "sort" implementations, e.g., AIX 5.2, HP-UX 11i v2, IRIX 6.5.
4557             -y is marked as obsolete starting with Solaris 8 (1999), but is
4558             still accepted as of Solaris 10 prerelease (2004).
4559
4560             Solaris 2.5.1 "sort -y 100" reads the input file "100", but
4561             emulate Solaris 8 and 9 "sort -y 100" which ignores the "100",
4562             and which in general ignores the argument after "-y" if it
4563             consists entirely of digits (it can even be empty).  */
4564          if (optarg == argv[optind - 1])
4565            {
4566              char const *p;
4567              for (p = optarg; ISDIGIT (*p); p++)
4568                continue;
4569              optind -= (*p != '\0');
4570            }
4571          break;
4572
4573        case 'z':
4574          eolchar = 0;
4575          break;
4576
4577        case_GETOPT_HELP_CHAR;
4578
4579        case_GETOPT_VERSION_CHAR (PROGRAM_NAME, AUTHORS);
4580
4581        default:
4582          usage (SORT_FAILURE);
4583        }
4584    }
4585
4586  if (files_from)
4587    {
4588      FILE *stream;
4589
4590      /* When using --files0-from=F, you may not specify any files
4591         on the command-line.  */
4592      if (nfiles)
4593        {
4594          error (0, 0, _("extra operand %s"), quoteaf (files[0]));
4595          fprintf (stderr, "%s\n",
4596                   _("file operands cannot be combined with --files0-from"));
4597          usage (SORT_FAILURE);
4598        }
4599
4600      if (STREQ (files_from, "-"))
4601        stream = stdin;
4602      else
4603        {
4604          stream = fopen (files_from, "r");
4605          if (stream == NULL)
4606            error (SORT_FAILURE, errno, _("cannot open %s for reading"),
4607                   quoteaf (files_from));
4608        }
4609
4610      readtokens0_init (&tok);
4611
4612      if (! readtokens0 (stream, &tok) || fclose (stream) != 0)
4613        error (SORT_FAILURE, 0, _("cannot read file names from %s"),
4614               quoteaf (files_from));
4615
4616      if (tok.n_tok)
4617        {
4618          size_t i;
4619          free (files);
4620          files = tok.tok;
4621          nfiles = tok.n_tok;
4622          for (i = 0; i < nfiles; i++)
4623            {
4624              if (STREQ (files[i], "-"))
4625                error (SORT_FAILURE, 0, _("when reading file names from stdin, "
4626                                          "no file name of %s allowed"),
4627                       quoteaf (files[i]));
4628              else if (files[i][0] == '\0')
4629                {
4630                  /* Using the standard 'filename:line-number:' prefix here is
4631                     not totally appropriate, since NUL is the separator,
4632                     not NL, but it might be better than nothing.  */
4633                  unsigned long int file_number = i + 1;
4634                  error (SORT_FAILURE, 0,
4635                         _("%s:%lu: invalid zero-length file name"),
4636                         quotef (files_from), file_number);
4637                }
4638            }
4639        }
4640      else
4641        error (SORT_FAILURE, 0, _("no input from %s"),
4642               quoteaf (files_from));
4643    }
4644
4645  /* Inheritance of global options to individual keys. */
4646  for (key = keylist; key; key = key->next)
4647    {
4648      if (default_key_compare (key) && !key->reverse)
4649        {
4650          key->ignore = gkey.ignore;
4651          key->translate = gkey.translate;
4652          key->skipsblanks = gkey.skipsblanks;
4653          key->skipeblanks = gkey.skipeblanks;
4654          key->month = gkey.month;
4655          key->numeric = gkey.numeric;
4656          key->general_numeric = gkey.general_numeric;
4657          key->human_numeric = gkey.human_numeric;
4658          key->version = gkey.version;
4659          key->random = gkey.random;
4660          key->reverse = gkey.reverse;
4661        }
4662
4663      need_random |= key->random;
4664    }
4665
4666  if (!keylist && !default_key_compare (&gkey))
4667    {
4668      gkey_only = true;
4669      insertkey (&gkey);
4670      need_random |= gkey.random;
4671    }
4672
4673  check_ordering_compatibility ();
4674
4675  if (debug)
4676    {
4677      if (checkonly || outfile)
4678        {
4679          static char opts[] = "X --debug";
4680          opts[0] = (checkonly ? checkonly : 'o');
4681          incompatible_options (opts);
4682        }
4683
4684      /* Always output the locale in debug mode, since this
4685         is such a common source of confusion.  */
4686      if (hard_LC_COLLATE)
4687        error (0, 0, _("using %s sorting rules"),
4688               quote (setlocale (LC_COLLATE, NULL)));
4689      else
4690        {
4691          /* OpenBSD can only set some categories with LC_ALL above,
4692             so set LC_COLLATE explicitly to flag errors.  */
4693          if (locale_ok)
4694            locale_ok = !! setlocale (LC_COLLATE, "");
4695          error (0, 0, "%s%s", locale_ok ? "" : _("failed to set locale; "),
4696                 _("using simple byte comparison"));
4697        }
4698      key_warnings (&gkey, gkey_only);
4699    }
4700
4701  reverse = gkey.reverse;
4702
4703  if (need_random)
4704    random_md5_state_init (random_source);
4705
4706  if (temp_dir_count == 0)
4707    {
4708      char const *tmp_dir = getenv ("TMPDIR");
4709      add_temp_dir (tmp_dir ? tmp_dir : DEFAULT_TMPDIR);
4710    }
4711
4712  if (nfiles == 0)
4713    {
4714      nfiles = 1;
4715      free (files);
4716      files = xmalloc (sizeof *files);
4717      *files = (char *) "-";
4718    }
4719
4720  /* Need to re-check that we meet the minimum requirement for memory
4721     usage with the final value for NMERGE. */
4722  if (0 < sort_size)
4723    sort_size = MAX (sort_size, MIN_SORT_SIZE);
4724
4725  if (checkonly)
4726    {
4727      if (nfiles > 1)
4728        error (SORT_FAILURE, 0, _("extra operand %s not allowed with -%c"),
4729               quoteaf (files[1]), checkonly);
4730
4731      if (outfile)
4732        {
4733          static char opts[] = {0, 'o', 0};
4734          opts[0] = checkonly;
4735          incompatible_options (opts);
4736        }
4737
4738      /* POSIX requires that sort return 1 IFF invoked with -c or -C and the
4739         input is not properly sorted.  */
4740      return check (files[0], checkonly) ? EXIT_SUCCESS : SORT_OUT_OF_ORDER;
4741    }
4742
4743  /* Check all inputs are accessible, or exit immediately.  */
4744  check_inputs (files, nfiles);
4745
4746  /* Check output is writable, or exit immediately.  */
4747  check_output (outfile);
4748
4749  if (mergeonly)
4750    {
4751      struct sortfile *sortfiles = xcalloc (nfiles, sizeof *sortfiles);
4752      size_t i;
4753
4754      for (i = 0; i < nfiles; ++i)
4755        sortfiles[i].name = files[i];
4756
4757      merge (sortfiles, 0, nfiles, outfile);
4758      IF_LINT (free (sortfiles));
4759    }
4760  else
4761    {
4762      if (!nthreads)
4763        {
4764          unsigned long int np = num_processors (NPROC_CURRENT_OVERRIDABLE);
4765          nthreads = MIN (np, DEFAULT_MAX_THREADS);
4766        }
4767
4768      /* Avoid integer overflow later.  */
4769      size_t nthreads_max = SIZE_MAX / (2 * sizeof (struct merge_node));
4770      nthreads = MIN (nthreads, nthreads_max);
4771
4772      sort (files, nfiles, outfile, nthreads);
4773    }
4774
4775#ifdef lint
4776  if (files_from)
4777    readtokens0_free (&tok);
4778  else
4779    free (files);
4780#endif
4781
4782  if (have_read_stdin && fclose (stdin) == EOF)
4783    die (_("close failed"), "-");
4784
4785  return EXIT_SUCCESS;
4786}
4787