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