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