1 /* sort - sort lines of text (with all kinds of options).
2 Copyright (C) 1988-2012 Free Software Foundation, Inc.
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.
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.
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/>.
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.
21 Ørn E. Hansen added NLS support in 1997. */
27 #include <sys/resource.h>
28 #include <sys/types.h>
36 #include "filevercmp.h"
37 #include "hard-locale.h"
40 #include "ignore-value.h"
49 #include "readtokens0.h"
52 #include "strnumcmp.h"
54 #include "xnanosleep.h"
58 struct rlimit { size_t rlim_cur; };
59 # define getrlimit(Resource, Rlp) (-1)
62 /* The official name of this program (e.g., no 'g' prefix). */
63 #define PROGRAM_NAME "sort"
66 proper_name ("Mike Haertel"), \
67 proper_name ("Paul Eggert")
69 #if HAVE_LANGINFO_CODESET
70 # include <langinfo.h>
73 /* Use SA_NOCLDSTOP as a proxy for whether the sigaction machinery is
76 # define SA_NOCLDSTOP 0
77 /* No sigprocmask. Always 'return' zero. */
78 # define sigprocmask(How, Set, Oset) (0)
80 # if ! HAVE_SIGINTERRUPT
81 # define siginterrupt(sig, flag) /* empty */
85 #if !defined OPEN_MAX && defined NR_OPEN
86 # define OPEN_MAX NR_OPEN
92 #define UCHAR_LIM (UCHAR_MAX + 1)
95 # define long_double long double
97 # define long_double double
99 # define strtold strtod
102 #ifndef DEFAULT_TMPDIR
103 # define DEFAULT_TMPDIR "/tmp"
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)
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. */
119 enum { SUBTHREAD_LINES_HEURISTIC = 128 * 1024 };
120 verify (4 <= SUBTHREAD_LINES_HEURISTIC);
122 /* The number of threads after which there are
123 diminishing performance gains. */
124 enum { DEFAULT_MAX_THREADS = 8 };
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,
133 /* POSIX says any other irregular exit must exit with a status
134 code greater than 1. */
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,
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
154 /* Level of the end-of-merge node, one level above the root. */
157 /* Level of the root node in merge tree. */
161 /* The representation of the decimal point in the current locale. */
162 static int decimal_point;
164 /* Thousands separator; if -1, then there isn't one. */
165 static int thousands_sep;
167 /* Nonzero if the corresponding locales are hard. */
168 static bool hard_LC_COLLATE;
170 static bool hard_LC_TIME;
173 #define NONZERO(x) ((x) != 0)
175 /* The kind of blanks for '-b' to skip in various options. */
176 enum blanktype { bl_start, bl_end, bl_both };
178 /* The character marking end of line. Default to \n. */
179 static char eolchar = '\n';
181 /* Lines are held in core as counted strings. */
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. */
193 char *buf; /* Dynamically allocated buffer,
194 partitioned into 3 regions:
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. */
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 xor 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. */
238 /* Binary merge tree node. */
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. */
256 /* Priority queue of merge nodes. */
257 struct merge_node_queue
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
265 /* FIXME: None of these tables work with multibyte character sets.
266 Also, there are many other bugs when handling multibyte characters.
267 One way to fix this is to rewrite 'sort' to use wide characters
268 internally, but doing this with good performance is a bit
271 /* Table of blanks. */
272 static bool blanks[UCHAR_LIM];
274 /* Table of non-printing characters. */
275 static bool nonprinting[UCHAR_LIM];
277 /* Table of non-dictionary characters (not letters, digits, or blanks). */
278 static bool nondictionary[UCHAR_LIM];
280 /* Translation table folding lower case to upper. */
281 static char fold_toupper[UCHAR_LIM];
283 #define MONTHS_PER_YEAR 12
285 /* Table mapping month names to integers.
286 Alphabetic order allows binary search. */
287 static struct month monthtab[] =
303 /* During the merge phase, the number of files to merge at once. */
304 #define NMERGE_DEFAULT 16
306 /* Minimum size for a merge or check buffer. */
307 #define MIN_MERGE_BUFFER_SIZE (2 + sizeof (struct line))
309 /* Minimum sort size; the code might not work with smaller sizes. */
310 #define MIN_SORT_SIZE (nmerge * MIN_MERGE_BUFFER_SIZE)
312 /* The number of bytes needed for a merge or check buffer, which can
313 function relatively efficiently even if it holds only one line. If
314 a longer line is seen, this value is increased. */
315 static size_t merge_buffer_size = MAX (MIN_MERGE_BUFFER_SIZE, 256 * 1024);
317 /* The approximate maximum number of bytes of main memory to use, as
318 specified by the user. Zero if the user has not specified a size. */
319 static size_t sort_size;
321 /* The initial allocation factor for non-regular files.
322 This is used, e.g., when reading from a pipe.
323 Don't make it too big, since it is multiplied by ~130 to
324 obtain the size of the actual buffer sort will allocate.
325 Also, there may be 8 threads all doing this at the same time. */
326 #define INPUT_FILE_SIZE_GUESS (128 * 1024)
328 /* Array of directory names in which any temporary files are to be created. */
329 static char const **temp_dirs;
331 /* Number of temporary directory names used. */
332 static size_t temp_dir_count;
334 /* Number of allocated slots in temp_dirs. */
335 static size_t temp_dir_alloc;
337 /* Flag to reverse the order of all comparisons. */
340 /* Flag for stable sort. This turns off the last ditch bytewise
341 comparison of lines, and instead leaves lines in the same order
342 they were read if all keys compare equal. */
345 /* If TAB has this value, blanks separate fields. */
346 enum { TAB_DEFAULT = CHAR_MAX + 1 };
348 /* Tab character separating fields. If TAB_DEFAULT, then fields are
349 separated by the empty string between a non-blank character and a blank
351 static int tab = TAB_DEFAULT;
353 /* Flag to remove consecutive duplicate lines from the output.
354 Only the last of a sequence of equal lines will be output. */
357 /* Nonzero if any of the input files are the standard input. */
358 static bool have_read_stdin;
360 /* List of key field comparisons to be tried. */
361 static struct keyfield *keylist;
363 /* Program used to (de)compress temp files. Must accept -d. */
364 static char const *compress_program;
366 /* Annotate the output with extra info to aid the user. */
369 /* Maximum number of files to merge in one go. If more than this
370 number are present, temp files will be used. */
371 static unsigned int nmerge = NMERGE_DEFAULT;
373 /* Report MESSAGE for FILE, then clean up and exit.
374 If FILE is null, it represents standard output. */
376 static void die (char const *, char const *) ATTRIBUTE_NORETURN;
378 die (char const *message, char const *file)
380 error (0, errno, "%s: %s", message, file ? file : _("standard output"));
387 if (status != EXIT_SUCCESS)
392 Usage: %s [OPTION]... [FILE]...\n\
393 or: %s [OPTION]... --files0-from=F\n\
395 program_name, program_name);
397 Write sorted concatenation of all FILE(s) to standard output.\n\
401 Mandatory arguments to long options are mandatory for short options too.\n\
408 -b, --ignore-leading-blanks ignore leading blanks\n\
409 -d, --dictionary-order consider only blanks and alphanumeric characters\
411 -f, --ignore-case fold lower case to upper case characters\n\
414 -g, --general-numeric-sort compare according to general numerical value\n\
415 -i, --ignore-nonprinting consider only printable characters\n\
416 -M, --month-sort compare (unknown) < 'JAN' < ... < 'DEC'\n\
419 -h, --human-numeric-sort compare human readable numbers (e.g., 2K 1G)\n\
422 -n, --numeric-sort compare according to string numerical value\n\
423 -R, --random-sort sort by random hash of keys\n\
424 --random-source=FILE get random bytes from FILE\n\
425 -r, --reverse reverse the result of comparisons\n\
428 --sort=WORD sort according to WORD:\n\
429 general-numeric -g, human-numeric -h, month -M,\
431 numeric -n, random -R, version -V\n\
432 -V, --version-sort natural sort of (version) numbers within text\n\
440 --batch-size=NMERGE merge at most NMERGE inputs at once;\n\
441 for more use temp files\n\
444 -c, --check, --check=diagnose-first check for sorted input; do not sort\n\
445 -C, --check=quiet, --check=silent like -c, but do not report first bad line\
447 --compress-program=PROG compress temporaries with PROG;\n\
448 decompress them with PROG -d\n\
451 --debug annotate the part of the line used to sort,\n\
452 and warn about questionable usage to stderr\n\
453 --files0-from=F read input from the files specified by\n\
454 NUL-terminated names in file F;\n\
455 If F is - then read names from standard input\n\
458 -k, --key=KEYDEF sort via a key; KEYDEF gives location and type\n\
459 -m, --merge merge already sorted files; do not sort\n\
462 -o, --output=FILE write result to FILE instead of standard output\n\
463 -s, --stable stabilize sort by disabling last-resort comparison\
465 -S, --buffer-size=SIZE use SIZE for main memory buffer\n\
468 -t, --field-separator=SEP use SEP instead of non-blank to blank transition\n\
469 -T, --temporary-directory=DIR use DIR for temporaries, not $TMPDIR or %s;\n\
470 multiple options specify multiple directories\n\
471 --parallel=N change the number of sorts run concurrently to N\n\
472 -u, --unique with -c, check for strict ordering;\n\
473 without -c, output only the first of an equal run\
477 -z, --zero-terminated end lines with 0 byte, not newline\n\
479 fputs (HELP_OPTION_DESCRIPTION, stdout);
480 fputs (VERSION_OPTION_DESCRIPTION, stdout);
483 KEYDEF is F[.C][OPTS][,F[.C][OPTS]] for start and stop position, where F is a\n\
484 field number and C a character position in the field; both are origin 1, and\n\
485 the stop position defaults to the line's end. If neither -t nor -b is in\n\
486 effect, characters in a field are counted from the beginning of the preceding\n\
487 whitespace. OPTS is one or more single-letter ordering options [bdfgiMhnRrV],\
489 which override global ordering options for that key. If no key is given, use\n\
490 the entire line as the key.\n\
492 SIZE may be followed by the following multiplicative suffixes:\n\
495 % 1% of memory, b 1, K 1024 (default), and so on for M, G, T, P, E, Z, Y.\n\
497 With no FILE, or when FILE is -, read standard input.\n\
500 The locale specified by the environment affects sort order.\n\
501 Set LC_ALL=C to get the traditional sort order that uses\n\
502 native byte values.\n\
504 emit_ancillary_info ();
510 /* For long options that have no equivalent short option, use a
511 non-character as a pseudo short option, starting with CHAR_MAX + 1. */
514 CHECK_OPTION = CHAR_MAX + 1,
515 COMPRESS_PROGRAM_OPTION,
516 DEBUG_PROGRAM_OPTION,
519 RANDOM_SOURCE_OPTION,
524 static char const short_options[] = "-bcCdfghik:mMno:rRsS:t:T:uVy:z";
526 static struct option const long_options[] =
528 {"ignore-leading-blanks", no_argument, NULL, 'b'},
529 {"check", optional_argument, NULL, CHECK_OPTION},
530 {"compress-program", required_argument, NULL, COMPRESS_PROGRAM_OPTION},
531 {"debug", no_argument, NULL, DEBUG_PROGRAM_OPTION},
532 {"dictionary-order", no_argument, NULL, 'd'},
533 {"ignore-case", no_argument, NULL, 'f'},
534 {"files0-from", required_argument, NULL, FILES0_FROM_OPTION},
535 {"general-numeric-sort", no_argument, NULL, 'g'},
536 {"ignore-nonprinting", no_argument, NULL, 'i'},
537 {"key", required_argument, NULL, 'k'},
538 {"merge", no_argument, NULL, 'm'},
539 {"month-sort", no_argument, NULL, 'M'},
540 {"numeric-sort", no_argument, NULL, 'n'},
541 {"human-numeric-sort", no_argument, NULL, 'h'},
542 {"version-sort", no_argument, NULL, 'V'},
543 {"random-sort", no_argument, NULL, 'R'},
544 {"random-source", required_argument, NULL, RANDOM_SOURCE_OPTION},
545 {"sort", required_argument, NULL, SORT_OPTION},
546 {"output", required_argument, NULL, 'o'},
547 {"reverse", no_argument, NULL, 'r'},
548 {"stable", no_argument, NULL, 's'},
549 {"batch-size", required_argument, NULL, NMERGE_OPTION},
550 {"buffer-size", required_argument, NULL, 'S'},
551 {"field-separator", required_argument, NULL, 't'},
552 {"temporary-directory", required_argument, NULL, 'T'},
553 {"unique", no_argument, NULL, 'u'},
554 {"zero-terminated", no_argument, NULL, 'z'},
555 {"parallel", required_argument, NULL, PARALLEL_OPTION},
556 {GETOPT_HELP_OPTION_DECL},
557 {GETOPT_VERSION_OPTION_DECL},
561 #define CHECK_TABLE \
563 _ct_("silent", 'C') \
564 _ct_("diagnose-first", 'c')
566 static char const *const check_args[] =
568 #define _ct_(_s, _c) _s,
572 static char const check_types[] =
574 #define _ct_(_s, _c) _c,
580 _st_("general-numeric", 'g') \
581 _st_("human-numeric", 'h') \
583 _st_("numeric", 'n') \
584 _st_("random", 'R') \
587 static char const *const sort_args[] =
589 #define _st_(_s, _c) _s,
593 static char const sort_types[] =
595 #define _st_(_s, _c) _c,
600 /* The set of signals that are caught. */
601 static sigset_t caught_signals;
603 /* Critical section status. */
610 /* Enter a critical section. */
611 static struct cs_status
614 struct cs_status status;
615 status.valid = (sigprocmask (SIG_BLOCK, &caught_signals, &status.sigs) == 0);
619 /* Leave a critical section. */
621 cs_leave (struct cs_status status)
625 /* Ignore failure when restoring the signal mask. */
626 sigprocmask (SIG_SETMASK, &status.sigs, NULL);
630 /* Possible states for a temp file. If compressed, the file's status
631 is unreaped or reaped, depending on whether 'sort' has waited for
632 the subprocess to finish. */
633 enum { UNCOMPRESSED, UNREAPED, REAPED };
635 /* The list of temporary files. */
638 struct tempnode *volatile next;
639 pid_t pid; /* The subprocess PID; undefined if state == UNCOMPRESSED. */
641 char name[1]; /* Actual size is 1 + file name length. */
643 static struct tempnode *volatile temphead;
644 static struct tempnode *volatile *temptail = &temphead;
646 /* A file to be sorted. */
649 /* The file's name. */
652 /* Nonnull if this is a temporary file, in which case NAME == TEMP->name. */
653 struct tempnode *temp;
656 /* Map PIDs of unreaped subprocesses to their struct tempnode objects. */
657 static Hash_table *proctab;
659 enum { INIT_PROCTAB_SIZE = 47 };
662 proctab_hasher (void const *entry, size_t tabsize)
664 struct tempnode const *node = entry;
665 return node->pid % tabsize;
669 proctab_comparator (void const *e1, void const *e2)
671 struct tempnode const *n1 = e1;
672 struct tempnode const *n2 = e2;
673 return n1->pid == n2->pid;
676 /* The number of unreaped child processes. */
679 static bool delete_proc (pid_t);
681 /* If PID is positive, wait for the child process with that PID to
682 exit, and assume that PID has already been removed from the process
683 table. If PID is 0 or -1, clean up some child that has exited (by
684 waiting for it, and removing it from the proc table) and return the
685 child's process ID. However, if PID is 0 and no children have
686 exited, return 0 without waiting. */
692 pid_t cpid = waitpid ((pid ? pid : -1), &status, (pid ? 0 : WNOHANG));
695 error (SORT_FAILURE, errno, _("waiting for %s [-d]"),
697 else if (0 < cpid && (0 < pid || delete_proc (cpid)))
699 if (! WIFEXITED (status) || WEXITSTATUS (status))
700 error (SORT_FAILURE, 0, _("%s [-d] terminated abnormally"),
708 /* TEMP represents a new process; add it to the process table. Create
709 the process table the first time it's called. */
712 register_proc (struct tempnode *temp)
716 proctab = hash_initialize (INIT_PROCTAB_SIZE, NULL,
724 temp->state = UNREAPED;
726 if (! hash_insert (proctab, temp))
730 /* If PID is in the process table, remove it and return true.
731 Otherwise, return false. */
734 delete_proc (pid_t pid)
736 struct tempnode test;
739 struct tempnode *node = hash_delete (proctab, &test);
742 node->state = REAPED;
746 /* Remove PID from the process table, and wait for it to exit if it
750 wait_proc (pid_t pid)
752 if (delete_proc (pid))
756 /* Reap any exited children. Do not block; reap only those that have
762 while (0 < nprocs && reap (0))
766 /* Reap at least one exited child, waiting if necessary. */
775 /* Reap all children, waiting if necessary. */
784 /* Clean up any remaining temporary files. */
789 struct tempnode const *node;
791 for (node = temphead; node; node = node->next)
796 /* Cleanup actions to take when exiting. */
803 /* Clean up any remaining temporary files in a critical section so
804 that a signal handler does not try to clean them too. */
805 struct cs_status cs = cs_enter ();
813 /* Create a new temporary file, returning its newly allocated tempnode.
814 Store into *PFD the file descriptor open for writing.
815 If the creation fails, return NULL and store -1 into *PFD if the
816 failure is due to file descriptor exhaustion and
817 SURVIVE_FD_EXHAUSTION; otherwise, die. */
819 static struct tempnode *
820 create_temp_file (int *pfd, bool survive_fd_exhaustion)
822 static char const slashbase[] = "/sortXXXXXX";
823 static size_t temp_dir_index;
826 char const *temp_dir = temp_dirs[temp_dir_index];
827 size_t len = strlen (temp_dir);
828 struct tempnode *node =
829 xmalloc (offsetof (struct tempnode, name) + len + sizeof slashbase);
830 char *file = node->name;
833 memcpy (file, temp_dir, len);
834 memcpy (file + len, slashbase, sizeof slashbase);
836 if (++temp_dir_index == temp_dir_count)
839 /* Create the temporary file in a critical section, to avoid races. */
845 temptail = &node->next;
853 if (! (survive_fd_exhaustion && errno == EMFILE))
854 error (SORT_FAILURE, errno, _("cannot create temporary file in %s"),
864 /* Return a stream for FILE, opened with mode HOW. A null FILE means
865 standard output; HOW should be "w". When opening for input, "-"
866 means standard input. To avoid confusion, do not return file
867 descriptors STDIN_FILENO, STDOUT_FILENO, or STDERR_FILENO when
868 opening an ordinary FILE. Return NULL if unsuccessful.
870 fadvise() is used to specify an access pattern for input files.
871 There are a few hints we could possibly provide,
872 and after careful testing it was decided that
873 specifying POSIX_FADV_SEQUENTIAL was not detrimental
874 to any cases. On Linux 2.6.31, this option doubles
875 the size of read ahead performed and thus was seen to
878 Sorting with a smaller internal buffer
879 Reading from faster flash devices
881 In _addition_ one could also specify other hints...
883 POSIX_FADV_WILLNEED was tested, but Linux 2.6.31
884 at least uses that to _synchronously_ prepopulate the cache
885 with the specified range. While sort does need to
886 read all of its input before outputting, a synchronous
887 read of the whole file up front precludes any processing
888 that sort could do in parallel with the system doing
889 read ahead of the data. This was seen to have negative effects
890 in a couple of cases:
892 Sorting with a smaller internal buffer
893 Note this option was seen to shorten the runtime for sort
894 on a multicore system with lots of RAM and other processes
895 competing for CPU. It could be argued that more explicit
896 scheduling hints with 'nice' et. al. are more appropriate
899 POSIX_FADV_NOREUSE is a possibility as it could lower
900 the priority of input data in the cache as sort will
901 only need to process it once. However its functionality
902 has changed over Linux kernel versions and as of 2.6.31
903 it does nothing and thus we can't depend on what it might
906 POSIX_FADV_DONTNEED is not appropriate for user specified
907 input files, but for temp files we do want to drop the
908 cache immediately after processing. This is done implicitly
909 however when the files are unlinked. */
912 stream_open (char const *file, char const *how)
918 if (STREQ (file, "-"))
920 have_read_stdin = true;
924 fp = fopen (file, how);
925 fadvise (fp, FADVISE_SEQUENTIAL);
927 else if (*how == 'w')
929 if (file && ftruncate (STDOUT_FILENO, 0) != 0)
930 error (EXIT_FAILURE, errno, _("%s: error truncating"),
935 assert (!"unexpected mode passed to stream_open");
940 /* Same as stream_open, except always return a non-null value; die on
944 xfopen (char const *file, char const *how)
946 FILE *fp = stream_open (file, how);
948 die (_("open failed"), file);
952 /* Close FP, whose name is FILE, and report any errors. */
955 xfclose (FILE *fp, char const *file)
960 /* Allow reading stdin from tty more than once. */
966 /* Don't close stdout just yet. close_stdout does that. */
967 if (fflush (fp) != 0)
968 die (_("fflush failed"), file);
972 if (fclose (fp) != 0)
973 die (_("close failed"), file);
979 move_fd_or_die (int oldfd, int newfd)
983 if (dup2 (oldfd, newfd) < 0)
984 error (SORT_FAILURE, errno, _("dup2 failed"));
989 /* Fork a child process for piping to and do common cleanup. The
990 TRIES parameter tells us how many times to try to fork before
991 giving up. Return the PID of the child, or -1 (setting errno)
995 pipe_fork (int pipefds[2], size_t tries)
997 #if HAVE_WORKING_FORK
998 struct tempnode *saved_temphead;
1000 double wait_retry = 0.25;
1001 pid_t pid IF_LINT ( = -1);
1002 struct cs_status cs;
1004 if (pipe (pipefds) < 0)
1007 /* At least NMERGE + 1 subprocesses are needed. More could be created, but
1008 uncontrolled subprocess generation can hurt performance significantly.
1009 Allow at most NMERGE + 2 subprocesses, on the theory that there
1010 may be some useful parallelism by letting compression for the
1011 previous merge finish (1 subprocess) in parallel with the current
1012 merge (NMERGE + 1 subprocesses). */
1014 if (nmerge + 1 < nprocs)
1019 /* This is so the child process won't delete our temp files
1020 if it receives a signal before exec-ing. */
1022 saved_temphead = temphead;
1026 saved_errno = errno;
1028 temphead = saved_temphead;
1031 errno = saved_errno;
1033 if (0 <= pid || errno != EAGAIN)
1037 xnanosleep (wait_retry);
1045 saved_errno = errno;
1048 errno = saved_errno;
1052 close (STDIN_FILENO);
1053 close (STDOUT_FILENO);
1060 #else /* ! HAVE_WORKING_FORK */
1065 /* Create a temporary file and, if asked for, start a compressor
1066 to that file. Set *PFP to the file handle and return
1067 the address of the new temp node. If the creation
1068 fails, return NULL if the failure is due to file descriptor
1069 exhaustion and SURVIVE_FD_EXHAUSTION; otherwise, die. */
1071 static struct tempnode *
1072 maybe_create_temp (FILE **pfp, bool survive_fd_exhaustion)
1075 struct tempnode *node = create_temp_file (&tempfd, survive_fd_exhaustion);
1079 node->state = UNCOMPRESSED;
1081 if (compress_program)
1085 node->pid = pipe_fork (pipefds, MAX_FORK_TRIES_COMPRESS);
1090 tempfd = pipefds[1];
1092 register_proc (node);
1094 else if (node->pid == 0)
1097 move_fd_or_die (tempfd, STDOUT_FILENO);
1098 move_fd_or_die (pipefds[0], STDIN_FILENO);
1100 if (execlp (compress_program, compress_program, (char *) NULL) < 0)
1101 error (SORT_FAILURE, errno, _("couldn't execute %s"),
1106 *pfp = fdopen (tempfd, "w");
1108 die (_("couldn't create temporary file"), node->name);
1113 /* Create a temporary file and, if asked for, start a compressor
1114 to that file. Set *PFP to the file handle and return the address
1115 of the new temp node. Die on failure. */
1117 static struct tempnode *
1118 create_temp (FILE **pfp)
1120 return maybe_create_temp (pfp, false);
1123 /* Open a compressed temp file and start a decompression process through
1124 which to filter the input. Return NULL (setting errno to
1125 EMFILE) if we ran out of file descriptors, and die on any other
1129 open_temp (struct tempnode *temp)
1131 int tempfd, pipefds[2];
1134 if (temp->state == UNREAPED)
1135 wait_proc (temp->pid);
1137 tempfd = open (temp->name, O_RDONLY);
1141 pid_t child = pipe_fork (pipefds, MAX_FORK_TRIES_DECOMPRESS);
1146 if (errno != EMFILE)
1147 error (SORT_FAILURE, errno, _("couldn't create process for %s -d"),
1155 move_fd_or_die (tempfd, STDIN_FILENO);
1156 move_fd_or_die (pipefds[1], STDOUT_FILENO);
1158 execlp (compress_program, compress_program, "-d", (char *) NULL);
1159 error (SORT_FAILURE, errno, _("couldn't execute %s -d"),
1164 register_proc (temp);
1168 fp = fdopen (pipefds[0], "r");
1171 int saved_errno = errno;
1173 errno = saved_errno;
1181 /* Append DIR to the array of temporary directory names. */
1183 add_temp_dir (char const *dir)
1185 if (temp_dir_count == temp_dir_alloc)
1186 temp_dirs = X2NREALLOC (temp_dirs, &temp_dir_alloc);
1188 temp_dirs[temp_dir_count++] = dir;
1191 /* Remove NAME from the list of temporary files. */
1194 zaptemp (char const *name)
1196 struct tempnode *volatile *pnode;
1197 struct tempnode *node;
1198 struct tempnode *next;
1200 int unlink_errno = 0;
1201 struct cs_status cs;
1203 for (pnode = &temphead; (node = *pnode)->name != name; pnode = &node->next)
1206 if (node->state == UNREAPED)
1207 wait_proc (node->pid);
1209 /* Unlink the temporary file in a critical section to avoid races. */
1212 unlink_status = unlink (name);
1213 unlink_errno = errno;
1217 if (unlink_status != 0)
1218 error (0, unlink_errno, _("warning: cannot remove: %s"), name);
1224 #if HAVE_NL_LANGINFO
1227 struct_month_cmp (void const *m1, void const *m2)
1229 struct month const *month1 = m1;
1230 struct month const *month2 = m2;
1231 return strcmp (month1->name, month2->name);
1236 /* Initialize the character class tables. */
1243 for (i = 0; i < UCHAR_LIM; ++i)
1245 blanks[i] = !! isblank (i);
1246 nonprinting[i] = ! isprint (i);
1247 nondictionary[i] = ! isalnum (i) && ! isblank (i);
1248 fold_toupper[i] = toupper (i);
1251 #if HAVE_NL_LANGINFO
1252 /* If we're not in the "C" locale, read different names for months. */
1255 for (i = 0; i < MONTHS_PER_YEAR; i++)
1262 s = nl_langinfo (ABMON_1 + i);
1264 monthtab[i].name = name = xmalloc (s_len + 1);
1265 monthtab[i].val = i + 1;
1267 for (j = k = 0; j < s_len; j++)
1268 if (! isblank (to_uchar (s[j])))
1269 name[k++] = fold_toupper[to_uchar (s[j])];
1272 qsort (monthtab, MONTHS_PER_YEAR, sizeof *monthtab, struct_month_cmp);
1277 /* Specify how many inputs may be merged at once.
1278 This may be set on the command-line with the
1279 --batch-size option. */
1281 specify_nmerge (int oi, char c, char const *s)
1284 struct rlimit rlimit;
1285 enum strtol_error e = xstrtoumax (s, NULL, 10, &n, NULL);
1287 /* Try to find out how many file descriptors we'll be able
1288 to open. We need at least nmerge + 3 (STDIN_FILENO,
1289 STDOUT_FILENO and STDERR_FILENO). */
1290 unsigned int max_nmerge = ((getrlimit (RLIMIT_NOFILE, &rlimit) == 0
1295 if (e == LONGINT_OK)
1299 e = LONGINT_OVERFLOW;
1304 error (0, 0, _("invalid --%s argument %s"),
1305 long_options[oi].name, quote (s));
1306 error (SORT_FAILURE, 0,
1307 _("minimum --%s argument is %s"),
1308 long_options[oi].name, quote ("2"));
1310 else if (max_nmerge < nmerge)
1312 e = LONGINT_OVERFLOW;
1319 if (e == LONGINT_OVERFLOW)
1321 char max_nmerge_buf[INT_BUFSIZE_BOUND (max_nmerge)];
1322 error (0, 0, _("--%s argument %s too large"),
1323 long_options[oi].name, quote (s));
1324 error (SORT_FAILURE, 0,
1325 _("maximum --%s argument with current rlimit is %s"),
1326 long_options[oi].name,
1327 uinttostr (max_nmerge, max_nmerge_buf));
1330 xstrtol_fatal (e, oi, c, long_options, s);
1333 /* Specify the amount of main memory to use when sorting. */
1335 specify_sort_size (int oi, char c, char const *s)
1339 enum strtol_error e = xstrtoumax (s, &suffix, 10, &n, "EgGkKmMPtTYZ");
1341 /* The default unit is KiB. */
1342 if (e == LONGINT_OK && ISDIGIT (suffix[-1]))
1344 if (n <= UINTMAX_MAX / 1024)
1347 e = LONGINT_OVERFLOW;
1350 /* A 'b' suffix means bytes; a '%' suffix means percent of memory. */
1351 if (e == LONGINT_INVALID_SUFFIX_CHAR && ISDIGIT (suffix[-1]) && ! suffix[1])
1360 double mem = physmem_total () * n / 100;
1362 /* Use "<", not "<=", to avoid problems with rounding. */
1363 if (mem < UINTMAX_MAX)
1369 e = LONGINT_OVERFLOW;
1374 if (e == LONGINT_OK)
1376 /* If multiple sort sizes are specified, take the maximum, so
1377 that option order does not matter. */
1384 sort_size = MAX (sort_size, MIN_SORT_SIZE);
1388 e = LONGINT_OVERFLOW;
1391 xstrtol_fatal (e, oi, c, long_options, s);
1394 /* Specify the number of threads to spawn during internal sort. */
1396 specify_nthreads (int oi, char c, char const *s)
1398 unsigned long int nthreads;
1399 enum strtol_error e = xstrtoul (s, NULL, 10, &nthreads, "");
1400 if (e == LONGINT_OVERFLOW)
1402 if (e != LONGINT_OK)
1403 xstrtol_fatal (e, oi, c, long_options, s);
1404 if (SIZE_MAX < nthreads)
1405 nthreads = SIZE_MAX;
1407 error (SORT_FAILURE, 0, _("number in parallel must be nonzero"));
1411 /* Return the default sort size. */
1413 default_sort_size (void)
1415 /* Let SIZE be MEM, but no more than the maximum object size or
1416 system resource limits. Don't bother to check for values like
1417 RLIM_INFINITY since in practice they are not much less than SIZE_MAX. */
1418 size_t size = SIZE_MAX;
1419 struct rlimit rlimit;
1420 if (getrlimit (RLIMIT_DATA, &rlimit) == 0 && rlimit.rlim_cur < size)
1421 size = rlimit.rlim_cur;
1423 if (getrlimit (RLIMIT_AS, &rlimit) == 0 && rlimit.rlim_cur < size)
1424 size = rlimit.rlim_cur;
1427 /* Leave a large safety margin for the above limits, as failure can
1428 occur when they are exceeded. */
1432 /* Leave a 1/16 margin for RSS to leave room for code, stack, etc.
1433 Exceeding RSS is not fatal, but can be quite slow. */
1434 if (getrlimit (RLIMIT_RSS, &rlimit) == 0 && rlimit.rlim_cur / 16 * 15 < size)
1435 size = rlimit.rlim_cur / 16 * 15;
1438 /* Let MEM be available memory or 1/8 of total memory, whichever
1440 double avail = physmem_available ();
1441 double total = physmem_total ();
1442 double mem = MAX (avail, total / 8);
1444 /* Return the minimum of MEM and SIZE, but no less than
1445 MIN_SORT_SIZE. Avoid the MIN macro here, as it is not quite
1446 right when only one argument is floating point. */
1449 return MAX (size, MIN_SORT_SIZE);
1452 /* Return the sort buffer size to use with the input files identified
1453 by FPS and FILES, which are alternate names of the same files.
1454 NFILES gives the number of input files; NFPS may be less. Assume
1455 that each input line requires LINE_BYTES extra bytes' worth of line
1456 information. Do not exceed the size bound specified by the user
1457 (or a default size bound, if the user does not specify one). */
1460 sort_buffer_size (FILE *const *fps, size_t nfps,
1461 char *const *files, size_t nfiles,
1464 /* A bound on the input size. If zero, the bound hasn't been
1466 static size_t size_bound;
1468 /* In the worst case, each input byte is a newline. */
1469 size_t worst_case_per_input_byte = line_bytes + 1;
1471 /* Keep enough room for one extra input line and an extra byte.
1472 This extra room might be needed when preparing to read EOF. */
1473 size_t size = worst_case_per_input_byte + 1;
1477 for (i = 0; i < nfiles; i++)
1483 if ((i < nfps ? fstat (fileno (fps[i]), &st)
1484 : STREQ (files[i], "-") ? fstat (STDIN_FILENO, &st)
1485 : stat (files[i], &st))
1487 die (_("stat failed"), files[i]);
1489 if (S_ISREG (st.st_mode))
1490 file_size = st.st_size;
1493 /* The file has unknown size. If the user specified a sort
1494 buffer size, use that; otherwise, guess the size. */
1497 file_size = INPUT_FILE_SIZE_GUESS;
1502 size_bound = sort_size;
1504 size_bound = default_sort_size ();
1507 /* Add the amount of memory needed to represent the worst case
1508 where the input consists entirely of newlines followed by a
1509 single non-newline. Check for overflow. */
1510 worst_case = file_size * worst_case_per_input_byte + 1;
1511 if (file_size != worst_case / worst_case_per_input_byte
1512 || size_bound - size <= worst_case)
1520 /* Initialize BUF. Reserve LINE_BYTES bytes for each line; LINE_BYTES
1521 must be at least sizeof (struct line). Allocate ALLOC bytes
1525 initbuf (struct buffer *buf, size_t line_bytes, size_t alloc)
1527 /* Ensure that the line array is properly aligned. If the desired
1528 size cannot be allocated, repeatedly halve it until allocation
1529 succeeds. The smaller allocation may hurt overall performance,
1530 but that's better than failing. */
1533 alloc += sizeof (struct line) - alloc % sizeof (struct line);
1534 buf->buf = malloc (alloc);
1538 if (alloc <= line_bytes + 1)
1542 buf->line_bytes = line_bytes;
1544 buf->used = buf->left = buf->nlines = 0;
1548 /* Return one past the limit of the line array. */
1550 static inline struct line *
1551 buffer_linelim (struct buffer const *buf)
1553 return (struct line *) (buf->buf + buf->alloc);
1556 /* Return a pointer to the first character of the field specified
1560 begfield (struct line const *line, struct keyfield const *key)
1562 char *ptr = line->text, *lim = ptr + line->length - 1;
1563 size_t sword = key->sword;
1564 size_t schar = key->schar;
1566 /* The leading field separator itself is included in a field when -t
1569 if (tab != TAB_DEFAULT)
1570 while (ptr < lim && sword--)
1572 while (ptr < lim && *ptr != tab)
1578 while (ptr < lim && sword--)
1580 while (ptr < lim && blanks[to_uchar (*ptr)])
1582 while (ptr < lim && !blanks[to_uchar (*ptr)])
1586 /* If we're ignoring leading blanks when computing the Start
1587 of the field, skip past them here. */
1588 if (key->skipsblanks)
1589 while (ptr < lim && blanks[to_uchar (*ptr)])
1592 /* Advance PTR by SCHAR (if possible), but no further than LIM. */
1593 ptr = MIN (lim, ptr + schar);
1598 /* Return the limit of (a pointer to the first character after) the field
1599 in LINE specified by KEY. */
1602 limfield (struct line const *line, struct keyfield const *key)
1604 char *ptr = line->text, *lim = ptr + line->length - 1;
1605 size_t eword = key->eword, echar = key->echar;
1608 eword++; /* Skip all of end field. */
1610 /* Move PTR past EWORD fields or to one past the last byte on LINE,
1611 whichever comes first. If there are more than EWORD fields, leave
1612 PTR pointing at the beginning of the field having zero-based index,
1613 EWORD. If a delimiter character was specified (via -t), then that
1614 'beginning' is the first character following the delimiting TAB.
1615 Otherwise, leave PTR pointing at the first 'blank' character after
1616 the preceding field. */
1617 if (tab != TAB_DEFAULT)
1618 while (ptr < lim && eword--)
1620 while (ptr < lim && *ptr != tab)
1622 if (ptr < lim && (eword || echar))
1626 while (ptr < lim && eword--)
1628 while (ptr < lim && blanks[to_uchar (*ptr)])
1630 while (ptr < lim && !blanks[to_uchar (*ptr)])
1634 #ifdef POSIX_UNSPECIFIED
1635 /* The following block of code makes GNU sort incompatible with
1636 standard Unix sort, so it's ifdef'd out for now.
1637 The POSIX spec isn't clear on how to interpret this.
1638 FIXME: request clarification.
1640 From: kwzh@gnu.ai.mit.edu (Karl Heuer)
1641 Date: Thu, 30 May 96 12:20:41 -0400
1642 [Translated to POSIX 1003.1-2001 terminology by Paul Eggert.]
1644 [...]I believe I've found another bug in 'sort'.
1649 $ textutils-1.15/src/sort -k1.7,1.7 </tmp/sort.in
1652 $ /bin/sort -k1.7,1.7 </tmp/sort.in
1656 Unix sort produced the answer I expected: sort on the single character
1657 in column 7. GNU sort produced different results, because it disagrees
1658 on the interpretation of the key-end spec "M.N". Unix sort reads this
1659 as "skip M-1 fields, then N-1 characters"; but GNU sort wants it to mean
1660 "skip M-1 fields, then either N-1 characters or the rest of the current
1661 field, whichever comes first". This extra clause applies only to
1662 key-ends, not key-starts.
1665 /* Make LIM point to the end of (one byte past) the current field. */
1666 if (tab != TAB_DEFAULT)
1669 newlim = memchr (ptr, tab, lim - ptr);
1677 while (newlim < lim && blanks[to_uchar (*newlim)])
1679 while (newlim < lim && !blanks[to_uchar (*newlim)])
1685 if (echar != 0) /* We need to skip over a portion of the end field. */
1687 /* If we're ignoring leading blanks when computing the End
1688 of the field, skip past them here. */
1689 if (key->skipeblanks)
1690 while (ptr < lim && blanks[to_uchar (*ptr)])
1693 /* Advance PTR by ECHAR (if possible), but no further than LIM. */
1694 ptr = MIN (lim, ptr + echar);
1700 /* Fill BUF reading from FP, moving buf->left bytes from the end
1701 of buf->buf to the beginning first. If EOF is reached and the
1702 file wasn't terminated by a newline, supply one. Set up BUF's line
1703 table too. FILE is the name of the file corresponding to FP.
1704 Return true if some input was read. */
1707 fillbuf (struct buffer *buf, FILE *fp, char const *file)
1709 struct keyfield const *key = keylist;
1711 size_t line_bytes = buf->line_bytes;
1712 size_t mergesize = merge_buffer_size - MIN_MERGE_BUFFER_SIZE;
1717 if (buf->used != buf->left)
1719 memmove (buf->buf, buf->buf + buf->used - buf->left, buf->left);
1720 buf->used = buf->left;
1726 char *ptr = buf->buf + buf->used;
1727 struct line *linelim = buffer_linelim (buf);
1728 struct line *line = linelim - buf->nlines;
1729 size_t avail = (char *) linelim - buf->nlines * line_bytes - ptr;
1730 char *line_start = buf->nlines ? line->text + line->length : buf->buf;
1732 while (line_bytes + 1 < avail)
1734 /* Read as many bytes as possible, but do not read so many
1735 bytes that there might not be enough room for the
1736 corresponding line array. The worst case is when the
1737 rest of the input file consists entirely of newlines,
1738 except that the last byte is not a newline. */
1739 size_t readsize = (avail - 1) / (line_bytes + 1);
1740 size_t bytes_read = fread (ptr, 1, readsize, fp);
1741 char *ptrlim = ptr + bytes_read;
1743 avail -= bytes_read;
1745 if (bytes_read != readsize)
1748 die (_("read failed"), file);
1752 if (buf->buf == ptrlim)
1754 if (line_start != ptrlim && ptrlim[-1] != eol)
1759 /* Find and record each line in the just-read input. */
1760 while ((p = memchr (ptr, eol, ptrlim - ptr)))
1762 /* Delimit the line with NUL. This eliminates the need to
1763 temporarily replace the last byte with NUL when calling
1764 xmemcoll(), which increases performance. */
1768 line->text = line_start;
1769 line->length = ptr - line_start;
1770 mergesize = MAX (mergesize, line->length);
1771 avail -= line_bytes;
1775 /* Precompute the position of the first key for
1777 line->keylim = (key->eword == SIZE_MAX
1779 : limfield (line, key));
1781 if (key->sword != SIZE_MAX)
1782 line->keybeg = begfield (line, key);
1785 if (key->skipsblanks)
1786 while (blanks[to_uchar (*line_start)])
1788 line->keybeg = line_start;
1800 buf->used = ptr - buf->buf;
1801 buf->nlines = buffer_linelim (buf) - line;
1802 if (buf->nlines != 0)
1804 buf->left = ptr - line_start;
1805 merge_buffer_size = mergesize + MIN_MERGE_BUFFER_SIZE;
1810 /* The current input line is too long to fit in the buffer.
1811 Double the buffer size and try again, keeping it properly
1813 size_t line_alloc = buf->alloc / sizeof (struct line);
1814 buf->buf = x2nrealloc (buf->buf, &line_alloc, sizeof (struct line));
1815 buf->alloc = line_alloc * sizeof (struct line);
1820 /* Table that maps characters to order-of-magnitude values. */
1821 static char const unit_order[UCHAR_LIM] =
1823 #if ! ('K' == 75 && 'M' == 77 && 'G' == 71 && 'T' == 84 && 'P' == 80 \
1824 && 'E' == 69 && 'Z' == 90 && 'Y' == 89 && 'k' == 107)
1825 /* This initializer syntax works on all C99 hosts. For now, use
1826 it only on non-ASCII hosts, to ease the pain of porting to
1827 pre-C99 ASCII hosts. */
1828 ['K']=1, ['M']=2, ['G']=3, ['T']=4, ['P']=5, ['E']=6, ['Z']=7, ['Y']=8,
1831 /* Generate the following table with this command:
1832 perl -e 'my %a=(k=>1, K=>1, M=>2, G=>3, T=>4, P=>5, E=>6, Z=>7, Y=>8);
1833 foreach my $i (0..255) {my $c=chr($i); $a{$c} ||= 0;print "$a{$c}, "}'\
1835 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1836 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1837 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 0, 3,
1838 0, 0, 0, 1, 0, 2, 0, 0, 5, 0, 0, 0, 4, 0, 0, 0, 0, 8, 7, 0, 0, 0, 0, 0,
1839 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1840 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1841 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1842 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1843 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1844 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1845 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
1849 /* Return an integer that represents the order of magnitude of the
1850 unit following the number. The number may contain thousands
1851 separators and a decimal point, but it may not contain leading blanks.
1852 Negative numbers get negative orders; zero numbers have a zero order. */
1854 static int _GL_ATTRIBUTE_PURE
1855 find_unit_order (char const *number)
1857 bool minus_sign = (*number == '-');
1858 char const *p = number + minus_sign;
1862 /* Scan to end of number.
1863 Decimals or separators not followed by digits stop the scan.
1864 Numbers ending in decimals or separators are thus considered
1865 to be lacking in units.
1866 FIXME: add support for multibyte thousands_sep and decimal_point. */
1870 while (ISDIGIT (ch = *p++))
1871 nonzero |= ch - '0';
1873 while (ch == thousands_sep);
1875 if (ch == decimal_point)
1876 while (ISDIGIT (ch = *p++))
1877 nonzero |= ch - '0';
1881 int order = unit_order[ch];
1882 return (minus_sign ? -order : order);
1888 /* Compare numbers A and B ending in units with SI or IEC prefixes
1889 <none/unknown> < K/k < M < G < T < P < E < Z < Y */
1892 human_numcompare (char const *a, char const *b)
1894 while (blanks[to_uchar (*a)])
1896 while (blanks[to_uchar (*b)])
1899 int diff = find_unit_order (a) - find_unit_order (b);
1900 return (diff ? diff : strnumcmp (a, b, decimal_point, thousands_sep));
1903 /* Compare strings A and B as numbers without explicitly converting them to
1904 machine numbers. Comparatively slow for short strings, but asymptotically
1908 numcompare (char const *a, char const *b)
1910 while (blanks[to_uchar (*a)])
1912 while (blanks[to_uchar (*b)])
1915 return strnumcmp (a, b, decimal_point, thousands_sep);
1918 /* Work around a problem whereby the long double value returned by glibc's
1919 strtold ("NaN", ...) contains uninitialized bits: clear all bytes of
1920 A and B before calling strtold. FIXME: remove this function once
1921 gnulib guarantees that strtold's result is always well defined. */
1923 nan_compare (char const *sa, char const *sb)
1926 memset (&a, 0, sizeof a);
1927 a = strtold (sa, NULL);
1930 memset (&b, 0, sizeof b);
1931 b = strtold (sb, NULL);
1933 return memcmp (&a, &b, sizeof a);
1937 general_numcompare (char const *sa, char const *sb)
1939 /* FIXME: maybe add option to try expensive FP conversion
1940 only if A and B can't be compared more cheaply/accurately. */
1944 long_double a = strtold (sa, &ea);
1945 long_double b = strtold (sb, &eb);
1947 /* Put conversion errors at the start of the collating sequence. */
1949 return sb == eb ? 0 : -1;
1953 /* Sort numbers in the usual way, where -0 == +0. Put NaNs after
1954 conversion errors but before numbers; sort them by internal
1955 bit-pattern, for lack of a more portable alternative. */
1961 : nan_compare (sa, sb));
1964 /* Return an integer in 1..12 of the month name MONTH.
1965 Return 0 if the name in S is not recognized. */
1968 getmonth (char const *month, char **ea)
1971 size_t hi = MONTHS_PER_YEAR;
1973 while (blanks[to_uchar (*month)])
1978 size_t ix = (lo + hi) / 2;
1979 char const *m = month;
1980 char const *n = monthtab[ix].name;
1988 return monthtab[ix].val;
1990 if (to_uchar (fold_toupper[to_uchar (*m)]) < to_uchar (*n))
1995 else if (to_uchar (fold_toupper[to_uchar (*m)]) > to_uchar (*n))
2007 /* A randomly chosen MD5 state, used for random comparison. */
2008 static struct md5_ctx random_md5_state;
2010 /* Initialize the randomly chosen MD5 state. */
2013 random_md5_state_init (char const *random_source)
2015 unsigned char buf[MD5_DIGEST_SIZE];
2016 struct randread_source *r = randread_new (random_source, sizeof buf);
2018 die (_("open failed"), random_source);
2019 randread (r, buf, sizeof buf);
2020 if (randread_free (r) != 0)
2021 die (_("close failed"), random_source);
2022 md5_init_ctx (&random_md5_state);
2023 md5_process_bytes (buf, sizeof buf, &random_md5_state);
2026 /* This is like strxfrm, except it reports any error and exits. */
2029 xstrxfrm (char *restrict dest, char const *restrict src, size_t destsize)
2032 size_t translated_size = strxfrm (dest, src, destsize);
2036 error (0, errno, _("string transformation failed"));
2037 error (0, 0, _("set LC_ALL='C' to work around the problem"));
2038 error (SORT_FAILURE, 0,
2039 _("the untransformed string was %s"),
2040 quotearg_n_style (0, locale_quoting_style, src));
2043 return translated_size;
2046 /* Compare the keys TEXTA (of length LENA) and TEXTB (of length LENB)
2047 using one or more random hash functions. TEXTA[LENA] and
2048 TEXTB[LENB] must be zero. */
2051 compare_random (char *restrict texta, size_t lena,
2052 char *restrict textb, size_t lenb)
2054 /* XFRM_DIFF records the equivalent of memcmp on the transformed
2055 data. This is used to break ties if there is a checksum
2056 collision, and this is good enough given the astronomically low
2057 probability of a collision. */
2060 char stackbuf[4000];
2061 char *buf = stackbuf;
2062 size_t bufsize = sizeof stackbuf;
2063 void *allocated = NULL;
2064 uint32_t dig[2][MD5_DIGEST_SIZE / sizeof (uint32_t)];
2065 struct md5_ctx s[2];
2066 s[0] = s[1] = random_md5_state;
2068 if (hard_LC_COLLATE)
2070 char const *lima = texta + lena;
2071 char const *limb = textb + lenb;
2075 /* Transform the text into the basis of comparison, so that byte
2076 strings that would otherwise considered to be equal are
2077 considered equal here even if their bytes differ.
2079 Each time through this loop, transform one
2080 null-terminated string's worth from TEXTA or from TEXTB
2081 or both. That way, there's no need to store the
2082 transformation of the whole line, if it contains many
2083 null-terminated strings. */
2085 /* Store the transformed data into a big-enough buffer. */
2087 /* A 3X size guess avoids the overhead of calling strxfrm
2088 twice on typical implementations. Don't worry about
2089 size_t overflow, as the guess need not be correct. */
2090 size_t guess_bufsize = 3 * (lena + lenb) + 2;
2091 if (bufsize < guess_bufsize)
2093 bufsize = MAX (guess_bufsize, bufsize * 3 / 2);
2095 buf = allocated = malloc (bufsize);
2099 bufsize = sizeof stackbuf;
2104 (texta < lima ? xstrxfrm (buf, texta, bufsize) + 1 : 0);
2105 bool a_fits = sizea <= bufsize;
2108 ? (xstrxfrm ((a_fits ? buf + sizea : NULL), textb,
2109 (a_fits ? bufsize - sizea : 0))
2113 if (! (a_fits && sizea + sizeb <= bufsize))
2115 bufsize = sizea + sizeb;
2116 if (bufsize < SIZE_MAX / 3)
2117 bufsize = bufsize * 3 / 2;
2119 buf = allocated = xmalloc (bufsize);
2121 strxfrm (buf, texta, sizea);
2123 strxfrm (buf + sizea, textb, sizeb);
2126 /* Advance past NULs to the next part of each input string,
2127 exiting the loop if both strings are exhausted. When
2128 exiting the loop, prepare to finish off the tiebreaker
2129 comparison properly. */
2131 texta += strlen (texta) + 1;
2133 textb += strlen (textb) + 1;
2134 if (! (texta < lima || textb < limb))
2136 lena = sizea; texta = buf;
2137 lenb = sizeb; textb = buf + sizea;
2141 /* Accumulate the transformed data in the corresponding
2143 md5_process_bytes (buf, sizea, &s[0]);
2144 md5_process_bytes (buf + sizea, sizeb, &s[1]);
2146 /* Update the tiebreaker comparison of the transformed data. */
2149 xfrm_diff = memcmp (buf, buf + sizea, MIN (sizea, sizeb));
2151 xfrm_diff = (sizea > sizeb) - (sizea < sizeb);
2156 /* Compute and compare the checksums. */
2157 md5_process_bytes (texta, lena, &s[0]); md5_finish_ctx (&s[0], dig[0]);
2158 md5_process_bytes (textb, lenb, &s[1]); md5_finish_ctx (&s[1], dig[1]);
2159 int diff = memcmp (dig[0], dig[1], sizeof dig[0]);
2161 /* Fall back on the tiebreaker if the checksums collide. */
2166 xfrm_diff = memcmp (texta, textb, MIN (lena, lenb));
2168 xfrm_diff = (lena > lenb) - (lena < lenb);
2179 /* Return the printable width of the block of memory starting at
2180 TEXT and ending just before LIM, counting each tab as one byte.
2181 FIXME: Should we generally be counting non printable chars? */
2184 debug_width (char const *text, char const *lim)
2186 size_t width = mbsnwidth (text, lim - text, 0);
2188 width += (*text++ == '\t');
2192 /* For debug mode, "underline" a key at the
2193 specified offset and screen width. */
2196 mark_key (size_t offset, size_t width)
2202 printf (_("^ no match for key\n"));
2213 /* Return true if KEY is a numeric key. */
2216 key_numeric (struct keyfield const *key)
2218 return key->numeric || key->general_numeric || key->human_numeric;
2221 /* For LINE, output a debugging line that underlines KEY in LINE.
2222 If KEY is null, underline the whole line. */
2225 debug_key (struct line const *line, struct keyfield const *key)
2227 char *text = line->text;
2229 char *lim = text + line->length - 1;
2233 if (key->sword != SIZE_MAX)
2234 beg = begfield (line, key);
2235 if (key->eword != SIZE_MAX)
2236 lim = limfield (line, key);
2238 if (key->skipsblanks || key->month || key_numeric (key))
2243 while (blanks[to_uchar (*beg)])
2246 char *tighter_lim = beg;
2250 else if (key->month)
2251 getmonth (beg, &tighter_lim);
2252 else if (key->general_numeric)
2253 ignore_value (strtold (beg, &tighter_lim));
2254 else if (key->numeric || key->human_numeric)
2256 char *p = beg + (beg < lim && *beg == '-');
2257 bool found_digit = false;
2262 while (ISDIGIT (ch = *p++))
2265 while (ch == thousands_sep);
2267 if (ch == decimal_point)
2268 while (ISDIGIT (ch = *p++))
2272 tighter_lim = p - ! (key->human_numeric && unit_order[ch]);
2282 size_t offset = debug_width (text, beg);
2283 size_t width = debug_width (beg, lim);
2284 mark_key (offset, width);
2287 /* Debug LINE by underlining its keys. */
2290 debug_line (struct line const *line)
2292 struct keyfield const *key = keylist;
2295 debug_key (line, key);
2296 while (key && ((key = key->next) || ! (unique || stable)));
2299 /* Return whether sorting options specified for key. */
2302 default_key_compare (struct keyfield const *key)
2304 return ! (key->ignore
2308 || key_numeric (key)
2312 /* || key->reverse */
2316 /* Convert a key to the short options used to specify it. */
2319 key_to_opts (struct keyfield const *key, char *opts)
2321 if (key->skipsblanks || key->skipeblanks)
2322 *opts++ = 'b';/* either disables global -b */
2323 if (key->ignore == nondictionary)
2327 if (key->general_numeric)
2329 if (key->human_numeric)
2331 if (key->ignore == nonprinting)
2346 /* Output data independent key warnings to stderr. */
2349 key_warnings (struct keyfield const *gkey, bool gkey_only)
2351 struct keyfield const *key;
2352 struct keyfield ugkey = *gkey;
2353 unsigned long keynum = 1;
2355 for (key = keylist; key; key = key->next, keynum++)
2357 if (key->obsolete_used)
2359 size_t sword = key->sword;
2360 size_t eword = key->eword;
2361 char tmp[INT_BUFSIZE_BOUND (uintmax_t)];
2362 /* obsolescent syntax +A.x -B.y is equivalent to:
2363 -k A+1.x+1,B.y (when y = 0)
2364 -k A+1.x+1,B+1.y (when y > 0) */
2365 char obuf[INT_BUFSIZE_BOUND (sword) * 2 + 4]; /* +# -# */
2366 char nbuf[INT_BUFSIZE_BOUND (sword) * 2 + 5]; /* -k #,# */
2370 if (sword == SIZE_MAX)
2373 po = stpcpy (stpcpy (po, "+"), umaxtostr (sword, tmp));
2374 pn = stpcpy (stpcpy (pn, "-k "), umaxtostr (sword + 1, tmp));
2375 if (key->eword != SIZE_MAX)
2377 stpcpy (stpcpy (po, " -"), umaxtostr (eword + 1, tmp));
2378 stpcpy (stpcpy (pn, ","),
2379 umaxtostr (eword + 1
2380 + (key->echar == SIZE_MAX), tmp));
2382 error (0, 0, _("obsolescent key %s used; consider %s instead"),
2383 quote_n (0, obuf), quote_n (1, nbuf));
2386 /* Warn about field specs that will never match. */
2387 if (key->sword != SIZE_MAX && key->eword < key->sword)
2388 error (0, 0, _("key %lu has zero width and will be ignored"), keynum);
2390 /* Warn about significant leading blanks. */
2391 bool implicit_skip = key_numeric (key) || key->month;
2392 bool maybe_space_aligned = !hard_LC_COLLATE && default_key_compare (key)
2393 && !(key->schar || key->echar);
2394 bool line_offset = key->eword == 0 && key->echar != 0; /* -k1.x,1.y */
2395 if (!gkey_only && tab == TAB_DEFAULT && !line_offset
2396 && ((!key->skipsblanks && !(implicit_skip || maybe_space_aligned))
2397 || (!key->skipsblanks && key->schar)
2398 || (!key->skipeblanks && key->echar)))
2399 error (0, 0, _("leading blanks are significant in key %lu; "
2400 "consider also specifying 'b'"), keynum);
2402 /* Warn about numeric comparisons spanning fields,
2403 as field delimiters could be interpreted as part
2404 of the number (maybe only in other locales). */
2405 if (!gkey_only && key_numeric (key))
2407 size_t sword = key->sword + 1;
2408 size_t eword = key->eword + 1;
2411 if (!eword || sword < eword)
2412 error (0, 0, _("key %lu is numeric and spans multiple fields"),
2416 /* Flag global options not copied or specified in any key. */
2417 if (ugkey.ignore && (ugkey.ignore == key->ignore))
2418 ugkey.ignore = NULL;
2419 if (ugkey.translate && (ugkey.translate == key->translate))
2420 ugkey.translate = NULL;
2421 ugkey.skipsblanks &= !key->skipsblanks;
2422 ugkey.skipeblanks &= !key->skipeblanks;
2423 ugkey.month &= !key->month;
2424 ugkey.numeric &= !key->numeric;
2425 ugkey.general_numeric &= !key->general_numeric;
2426 ugkey.human_numeric &= !key->human_numeric;
2427 ugkey.random &= !key->random;
2428 ugkey.version &= !key->version;
2429 ugkey.reverse &= !key->reverse;
2432 /* Warn about ignored global options flagged above.
2433 Note if gkey is the only one in the list, all flags are cleared. */
2434 if (!default_key_compare (&ugkey)
2435 || (ugkey.reverse && (stable || unique) && keylist))
2437 bool ugkey_reverse = ugkey.reverse;
2438 if (!(stable || unique))
2439 ugkey.reverse = false;
2440 /* The following is too big, but guaranteed to be "big enough". */
2441 char opts[sizeof short_options];
2442 key_to_opts (&ugkey, opts);
2444 ngettext ("option '-%s' is ignored",
2445 "options '-%s' are ignored",
2446 select_plural (strlen (opts))), opts);
2447 ugkey.reverse = ugkey_reverse;
2449 if (ugkey.reverse && !(stable || unique) && keylist)
2450 error (0, 0, _("option '-r' only applies to last-resort comparison"));
2453 /* Compare two lines A and B trying every key in sequence until there
2454 are no more keys or a difference is found. */
2457 keycompare (struct line const *a, struct line const *b)
2459 struct keyfield *key = keylist;
2461 /* For the first iteration only, the key positions have been
2462 precomputed for us. */
2463 char *texta = a->keybeg;
2464 char *textb = b->keybeg;
2465 char *lima = a->keylim;
2466 char *limb = b->keylim;
2472 char const *translate = key->translate;
2473 bool const *ignore = key->ignore;
2475 /* Treat field ends before field starts as empty fields. */
2476 lima = MAX (texta, lima);
2477 limb = MAX (textb, limb);
2479 /* Find the lengths. */
2480 size_t lena = lima - texta;
2481 size_t lenb = limb - textb;
2483 if (hard_LC_COLLATE || key_numeric (key)
2484 || key->month || key->random || key->version)
2491 char enda IF_LINT (= 0);
2492 char endb IF_LINT (= 0);
2493 void *allocated IF_LINT (= NULL);
2494 char stackbuf[4000];
2496 if (ignore || translate)
2498 /* Compute with copies of the keys, which are the result of
2499 translating or ignoring characters, and which need their
2504 /* Allocate space for copies. */
2505 size_t size = lena + 1 + lenb + 1;
2506 if (size <= sizeof stackbuf)
2507 ta = stackbuf, allocated = NULL;
2509 ta = allocated = xmalloc (size);
2512 /* Put into each copy a version of the key in which the
2513 requested characters are ignored or translated. */
2514 for (tlena = i = 0; i < lena; i++)
2515 if (! (ignore && ignore[to_uchar (texta[i])]))
2516 ta[tlena++] = (translate
2517 ? translate[to_uchar (texta[i])]
2521 for (tlenb = i = 0; i < lenb; i++)
2522 if (! (ignore && ignore[to_uchar (textb[i])]))
2523 tb[tlenb++] = (translate
2524 ? translate[to_uchar (textb[i])]
2530 /* Use the keys in-place, temporarily null-terminated. */
2531 ta = texta; tlena = lena; enda = ta[tlena]; ta[tlena] = '\0';
2532 tb = textb; tlenb = lenb; endb = tb[tlenb]; tb[tlenb] = '\0';
2536 diff = numcompare (ta, tb);
2537 else if (key->general_numeric)
2538 diff = general_numcompare (ta, tb);
2539 else if (key->human_numeric)
2540 diff = human_numcompare (ta, tb);
2541 else if (key->month)
2542 diff = getmonth (ta, NULL) - getmonth (tb, NULL);
2543 else if (key->random)
2544 diff = compare_random (ta, tlena, tb, tlenb);
2545 else if (key->version)
2546 diff = filevercmp (ta, tb);
2549 /* Locale-dependent string sorting. This is slower than
2550 C-locale sorting, which is implemented below. */
2552 diff = - NONZERO (tlenb);
2553 else if (tlenb == 0)
2556 diff = xmemcoll0 (ta, tlena + 1, tb, tlenb + 1);
2559 if (ignore || translate)
2569 #define CMP_WITH_IGNORE(A, B) \
2574 while (texta < lima && ignore[to_uchar (*texta)]) \
2576 while (textb < limb && ignore[to_uchar (*textb)]) \
2578 if (! (texta < lima && textb < limb)) \
2580 diff = to_uchar (A) - to_uchar (B); \
2587 diff = (texta < lima) - (textb < limb); \
2592 CMP_WITH_IGNORE (translate[to_uchar (*texta)],
2593 translate[to_uchar (*textb)]);
2595 CMP_WITH_IGNORE (*texta, *textb);
2598 diff = - NONZERO (lenb);
2605 while (texta < lima && textb < limb)
2607 diff = (to_uchar (translate[to_uchar (*texta++)])
2608 - to_uchar (translate[to_uchar (*textb++)]));
2615 diff = memcmp (texta, textb, MIN (lena, lenb));
2619 diff = lena < lenb ? -1 : lena != lenb;
2629 /* Find the beginning and limit of the next field. */
2630 if (key->eword != SIZE_MAX)
2631 lima = limfield (a, key), limb = limfield (b, key);
2633 lima = a->text + a->length - 1, limb = b->text + b->length - 1;
2635 if (key->sword != SIZE_MAX)
2636 texta = begfield (a, key), textb = begfield (b, key);
2639 texta = a->text, textb = b->text;
2640 if (key->skipsblanks)
2642 while (texta < lima && blanks[to_uchar (*texta)])
2644 while (textb < limb && blanks[to_uchar (*textb)])
2655 return key->reverse ? -diff : diff;
2658 /* Compare two lines A and B, returning negative, zero, or positive
2659 depending on whether A compares less than, equal to, or greater than B. */
2662 compare (struct line const *a, struct line const *b)
2667 /* First try to compare on the specified keys (if any).
2668 The only two cases with no key at all are unadorned sort,
2669 and unadorned sort -r. */
2672 diff = keycompare (a, b);
2673 if (diff || unique || stable)
2677 /* If the keys all compare equal (or no keys were specified)
2678 fall through to the default comparison. */
2679 alen = a->length - 1, blen = b->length - 1;
2682 diff = - NONZERO (blen);
2685 else if (hard_LC_COLLATE)
2687 /* Note xmemcoll0 is a performance enhancement as
2688 it will not unconditionally write '\0' after the
2689 passed in buffers, which was seen to give around
2690 a 3% increase in performance for short lines. */
2691 diff = xmemcoll0 (a->text, alen + 1, b->text, blen + 1);
2693 else if (! (diff = memcmp (a->text, b->text, MIN (alen, blen))))
2694 diff = alen < blen ? -1 : alen != blen;
2696 return reverse ? -diff : diff;
2699 /* Write LINE to output stream FP; the output file's name is
2700 OUTPUT_FILE if OUTPUT_FILE is nonnull, and is the standard output
2701 otherwise. If debugging is enabled and FP is standard output,
2702 append some debugging information. */
2705 write_line (struct line const *line, FILE *fp, char const *output_file)
2707 char *buf = line->text;
2708 size_t n_bytes = line->length;
2709 char *ebuf = buf + n_bytes;
2711 if (!output_file && debug)
2713 /* Convert TAB to '>' and EOL to \n, and then output debugging info. */
2714 char const *c = buf;
2723 if (fputc (wc, fp) == EOF)
2724 die (_("write failed"), output_file);
2732 if (fwrite (buf, 1, n_bytes, fp) != n_bytes)
2733 die (_("write failed"), output_file);
2738 /* Check that the lines read from FILE_NAME come in order. Return
2739 true if they are in order. If CHECKONLY == 'c', also print a
2740 diagnostic (FILE_NAME, line number, contents of line) to stderr if
2741 they are not in order. */
2744 check (char const *file_name, char checkonly)
2746 FILE *fp = xfopen (file_name, "r");
2747 struct buffer buf; /* Input buffer. */
2748 struct line temp; /* Copy of previous line. */
2750 uintmax_t line_number = 0;
2751 struct keyfield const *key = keylist;
2752 bool nonunique = ! unique;
2753 bool ordered = true;
2755 initbuf (&buf, sizeof (struct line),
2756 MAX (merge_buffer_size, sort_size));
2759 while (fillbuf (&buf, fp, file_name))
2761 struct line const *line = buffer_linelim (&buf);
2762 struct line const *linebase = line - buf.nlines;
2764 /* Make sure the line saved from the old buffer contents is
2765 less than or equal to the first line of the new buffer. */
2766 if (alloc && nonunique <= compare (&temp, line - 1))
2770 if (checkonly == 'c')
2772 struct line const *disorder_line = line - 1;
2773 uintmax_t disorder_line_number =
2774 buffer_linelim (&buf) - disorder_line + line_number;
2775 char hr_buf[INT_BUFSIZE_BOUND (disorder_line_number)];
2776 fprintf (stderr, _("%s: %s:%s: disorder: "),
2777 program_name, file_name,
2778 umaxtostr (disorder_line_number, hr_buf));
2779 write_line (disorder_line, stderr, _("standard error"));
2787 /* Compare each line in the buffer with its successor. */
2788 while (linebase < --line)
2789 if (nonunique <= compare (line, line - 1))
2790 goto found_disorder;
2792 line_number += buf.nlines;
2794 /* Save the last line of the buffer. */
2795 if (alloc < line->length)
2802 alloc = line->length;
2806 while (alloc < line->length);
2809 temp.text = xmalloc (alloc);
2811 memcpy (temp.text, line->text, line->length);
2812 temp.length = line->length;
2815 temp.keybeg = temp.text + (line->keybeg - line->text);
2816 temp.keylim = temp.text + (line->keylim - line->text);
2820 xfclose (fp, file_name);
2826 /* Open FILES (there are NFILES of them) and store the resulting array
2827 of stream pointers into (*PFPS). Allocate the array. Return the
2828 number of successfully opened files, setting errno if this value is
2829 less than NFILES. */
2832 open_input_files (struct sortfile *files, size_t nfiles, FILE ***pfps)
2834 FILE **fps = *pfps = xnmalloc (nfiles, sizeof *fps);
2837 /* Open as many input files as we can. */
2838 for (i = 0; i < nfiles; i++)
2840 fps[i] = (files[i].temp && files[i].temp->state != UNCOMPRESSED
2841 ? open_temp (files[i].temp)
2842 : stream_open (files[i].name, "r"));
2850 /* Merge lines from FILES onto OFP. NTEMPS is the number of temporary
2851 files (all of which are at the start of the FILES array), and
2852 NFILES is the number of files; 0 <= NTEMPS <= NFILES <= NMERGE.
2853 FPS is the vector of open stream corresponding to the files.
2854 Close input and output streams before returning.
2855 OUTPUT_FILE gives the name of the output file. If it is NULL,
2856 the output file is standard output. */
2859 mergefps (struct sortfile *files, size_t ntemps, size_t nfiles,
2860 FILE *ofp, char const *output_file, FILE **fps)
2862 struct buffer *buffer = xnmalloc (nfiles, sizeof *buffer);
2863 /* Input buffers for each file. */
2864 struct line saved; /* Saved line storage for unique check. */
2865 struct line const *savedline = NULL;
2866 /* &saved if there is a saved line. */
2867 size_t savealloc = 0; /* Size allocated for the saved line. */
2868 struct line const **cur = xnmalloc (nfiles, sizeof *cur);
2869 /* Current line in each line table. */
2870 struct line const **base = xnmalloc (nfiles, sizeof *base);
2871 /* Base of each line table. */
2872 size_t *ord = xnmalloc (nfiles, sizeof *ord);
2873 /* Table representing a permutation of fps,
2874 such that cur[ord[0]] is the smallest line
2875 and will be next output. */
2879 struct keyfield const *key = keylist;
2882 /* Read initial lines from each input file. */
2883 for (i = 0; i < nfiles; )
2885 initbuf (&buffer[i], sizeof (struct line),
2886 MAX (merge_buffer_size, sort_size / nfiles));
2887 if (fillbuf (&buffer[i], fps[i], files[i].name))
2889 struct line const *linelim = buffer_linelim (&buffer[i]);
2890 cur[i] = linelim - 1;
2891 base[i] = linelim - buffer[i].nlines;
2896 /* fps[i] is empty; eliminate it from future consideration. */
2897 xfclose (fps[i], files[i].name);
2901 zaptemp (files[i].name);
2903 free (buffer[i].buf);
2905 for (j = i; j < nfiles; ++j)
2907 files[j] = files[j + 1];
2908 fps[j] = fps[j + 1];
2913 /* Set up the ord table according to comparisons among input lines.
2914 Since this only reorders two items if one is strictly greater than
2915 the other, it is stable. */
2916 for (i = 0; i < nfiles; ++i)
2918 for (i = 1; i < nfiles; ++i)
2919 if (0 < compare (cur[ord[i - 1]], cur[ord[i]]))
2920 t = ord[i - 1], ord[i - 1] = ord[i], ord[i] = t, i = 0;
2922 /* Repeatedly output the smallest line until no input remains. */
2925 struct line const *smallest = cur[ord[0]];
2927 /* If uniquified output is turned on, output only the first of
2928 an identical series of lines. */
2931 if (savedline && compare (savedline, smallest))
2934 write_line (&saved, ofp, output_file);
2939 if (savealloc < smallest->length)
2944 savealloc = smallest->length;
2947 while ((savealloc *= 2) < smallest->length);
2950 saved.text = xmalloc (savealloc);
2952 saved.length = smallest->length;
2953 memcpy (saved.text, smallest->text, saved.length);
2957 saved.text + (smallest->keybeg - smallest->text);
2959 saved.text + (smallest->keylim - smallest->text);
2964 write_line (smallest, ofp, output_file);
2966 /* Check if we need to read more lines into core. */
2967 if (base[ord[0]] < smallest)
2968 cur[ord[0]] = smallest - 1;
2971 if (fillbuf (&buffer[ord[0]], fps[ord[0]], files[ord[0]].name))
2973 struct line const *linelim = buffer_linelim (&buffer[ord[0]]);
2974 cur[ord[0]] = linelim - 1;
2975 base[ord[0]] = linelim - buffer[ord[0]].nlines;
2979 /* We reached EOF on fps[ord[0]]. */
2980 for (i = 1; i < nfiles; ++i)
2981 if (ord[i] > ord[0])
2984 xfclose (fps[ord[0]], files[ord[0]].name);
2985 if (ord[0] < ntemps)
2988 zaptemp (files[ord[0]].name);
2990 free (buffer[ord[0]].buf);
2991 for (i = ord[0]; i < nfiles; ++i)
2993 fps[i] = fps[i + 1];
2994 files[i] = files[i + 1];
2995 buffer[i] = buffer[i + 1];
2996 cur[i] = cur[i + 1];
2997 base[i] = base[i + 1];
2999 for (i = 0; i < nfiles; ++i)
3000 ord[i] = ord[i + 1];
3005 /* The new line just read in may be larger than other lines
3006 already in main memory; push it back in the queue until we
3007 encounter a line larger than it. Optimize for the common
3008 case where the new line is smallest. */
3013 size_t ord0 = ord[0];
3014 size_t count_of_smaller_lines;
3018 int cmp = compare (cur[ord0], cur[ord[probe]]);
3019 if (cmp < 0 || (cmp == 0 && ord0 < ord[probe]))
3023 probe = (lo + hi) / 2;
3026 count_of_smaller_lines = lo - 1;
3027 for (j = 0; j < count_of_smaller_lines; j++)
3028 ord[j] = ord[j + 1];
3029 ord[count_of_smaller_lines] = ord0;
3033 if (unique && savedline)
3035 write_line (&saved, ofp, output_file);
3039 xfclose (ofp, output_file);
3047 /* Merge lines from FILES onto OFP. NTEMPS is the number of temporary
3048 files (all of which are at the start of the FILES array), and
3049 NFILES is the number of files; 0 <= NTEMPS <= NFILES <= NMERGE.
3050 Close input and output files before returning.
3051 OUTPUT_FILE gives the name of the output file.
3053 Return the number of files successfully merged. This number can be
3054 less than NFILES if we ran low on file descriptors, but in this
3055 case it is never less than 2. */
3058 mergefiles (struct sortfile *files, size_t ntemps, size_t nfiles,
3059 FILE *ofp, char const *output_file)
3062 size_t nopened = open_input_files (files, nfiles, &fps);
3063 if (nopened < nfiles && nopened < 2)
3064 die (_("open failed"), files[nopened].name);
3065 mergefps (files, ntemps, nopened, ofp, output_file, fps);
3069 /* Merge into T (of size NLINES) the two sorted arrays of lines
3070 LO (with NLINES / 2 members), and
3071 T - (NLINES / 2) (with NLINES - NLINES / 2 members).
3072 T and LO point just past their respective arrays, and the arrays
3073 are in reverse order. NLINES must be at least 2. */
3076 mergelines (struct line *restrict t, size_t nlines,
3077 struct line const *restrict lo)
3079 size_t nlo = nlines / 2;
3080 size_t nhi = nlines - nlo;
3081 struct line *hi = t - nlo;
3084 if (compare (lo - 1, hi - 1) <= 0)
3089 /* HI must equal T now, and there is no need to copy from
3108 /* Sort the array LINES with NLINES members, using TEMP for temporary space.
3109 Do this all within one thread. NLINES must be at least 2.
3110 If TO_TEMP, put the sorted output into TEMP, and TEMP is as large as LINES.
3111 Otherwise the sort is in-place and TEMP is half-sized.
3112 The input and output arrays are in reverse order, and LINES and
3113 TEMP point just past the end of their respective arrays.
3115 Use a recursive divide-and-conquer algorithm, in the style
3116 suggested by Knuth volume 3 (2nd edition), exercise 5.2.4-23. Use
3117 the optimization suggested by exercise 5.2.4-10; this requires room
3118 for only 1.5*N lines, rather than the usual 2*N lines. Knuth
3119 writes that this memory optimization was originally published by
3120 D. A. Bell, Comp J. 1 (1958), 75. */
3123 sequential_sort (struct line *restrict lines, size_t nlines,
3124 struct line *restrict temp, bool to_temp)
3128 /* Declare 'swap' as int, not bool, to work around a bug
3129 <http://lists.gnu.org/archive/html/bug-coreutils/2005-10/msg00086.html>
3130 in the IBM xlc 6.0.0.0 compiler in 64-bit mode. */
3131 int swap = (0 < compare (&lines[-1], &lines[-2]));
3134 temp[-1] = lines[-1 - swap];
3135 temp[-2] = lines[-2 + swap];
3139 temp[-1] = lines[-1];
3140 lines[-1] = lines[-2];
3141 lines[-2] = temp[-1];
3146 size_t nlo = nlines / 2;
3147 size_t nhi = nlines - nlo;
3148 struct line *lo = lines;
3149 struct line *hi = lines - nlo;
3151 sequential_sort (hi, nhi, temp - (to_temp ? nlo : 0), to_temp);
3153 sequential_sort (lo, nlo, temp, !to_temp);
3158 struct line const *sorted_lo;
3169 mergelines (dest, nlines, sorted_lo);
3173 static struct merge_node *init_node (struct merge_node *restrict,
3174 struct merge_node *restrict,
3175 struct line *, size_t, size_t, bool);
3178 /* Create and return a merge tree for NTHREADS threads, sorting NLINES
3179 lines, with destination DEST. */
3180 static struct merge_node *
3181 merge_tree_init (size_t nthreads, size_t nlines, struct line *dest)
3183 struct merge_node *merge_tree = xmalloc (2 * sizeof *merge_tree * nthreads);
3185 struct merge_node *root = merge_tree;
3186 root->lo = root->hi = root->end_lo = root->end_hi = NULL;
3188 root->nlo = root->nhi = nlines;
3189 root->parent = NULL;
3190 root->level = MERGE_END;
3191 root->queued = false;
3192 pthread_mutex_init (&root->lock, NULL);
3194 init_node (root, root + 1, dest, nthreads, nlines, false);
3198 /* Destroy the merge tree. */
3200 merge_tree_destroy (struct merge_node *merge_tree)
3205 /* Initialize a merge tree node and its descendants. The node's
3206 parent is PARENT. The node and its descendants are taken from the
3207 array of nodes NODE_POOL. Their destination starts at DEST; they
3208 will consume NTHREADS threads. The total number of sort lines is
3209 TOTAL_LINES. IS_LO_CHILD is true if the node is the low child of
3212 static struct merge_node *
3213 init_node (struct merge_node *restrict parent,
3214 struct merge_node *restrict node_pool,
3215 struct line *dest, size_t nthreads,
3216 size_t total_lines, bool is_lo_child)
3218 size_t nlines = (is_lo_child ? parent->nlo : parent->nhi);
3219 size_t nlo = nlines / 2;
3220 size_t nhi = nlines - nlo;
3221 struct line *lo = dest - total_lines;
3222 struct line *hi = lo - nlo;
3223 struct line **parent_end = (is_lo_child ? &parent->end_lo : &parent->end_hi);
3225 struct merge_node *node = node_pool++;
3226 node->lo = node->end_lo = lo;
3227 node->hi = node->end_hi = hi;
3228 node->dest = parent_end;
3231 node->parent = parent;
3232 node->level = parent->level + 1;
3233 node->queued = false;
3234 pthread_mutex_init (&node->lock, NULL);
3238 size_t lo_threads = nthreads / 2;
3239 size_t hi_threads = nthreads - lo_threads;
3240 node->lo_child = node_pool;
3241 node_pool = init_node (node, node_pool, lo, lo_threads,
3243 node->hi_child = node_pool;
3244 node_pool = init_node (node, node_pool, hi, hi_threads,
3245 total_lines, false);
3249 node->lo_child = NULL;
3250 node->hi_child = NULL;
3256 /* Compare two merge nodes A and B for priority. */
3259 compare_nodes (void const *a, void const *b)
3261 struct merge_node const *nodea = a;
3262 struct merge_node const *nodeb = b;
3263 if (nodea->level == nodeb->level)
3264 return (nodea->nlo + nodea->nhi) < (nodeb->nlo + nodeb->nhi);
3265 return nodea->level < nodeb->level;
3268 /* Lock a merge tree NODE. */
3271 lock_node (struct merge_node *node)
3273 pthread_mutex_lock (&node->lock);
3276 /* Unlock a merge tree NODE. */
3279 unlock_node (struct merge_node *node)
3281 pthread_mutex_unlock (&node->lock);
3284 /* Destroy merge QUEUE. */
3287 queue_destroy (struct merge_node_queue *queue)
3289 heap_free (queue->priority_queue);
3290 pthread_cond_destroy (&queue->cond);
3291 pthread_mutex_destroy (&queue->mutex);
3294 /* Initialize merge QUEUE, allocating space suitable for a maximum of
3295 NTHREADS threads. */
3298 queue_init (struct merge_node_queue *queue, size_t nthreads)
3300 /* Though it's highly unlikely all nodes are in the heap at the same
3301 time, the heap should accommodate all of them. Counting a NULL
3302 dummy head for the heap, reserve 2 * NTHREADS nodes. */
3303 queue->priority_queue = heap_alloc (compare_nodes, 2 * nthreads);
3304 pthread_mutex_init (&queue->mutex, NULL);
3305 pthread_cond_init (&queue->cond, NULL);
3308 /* Insert NODE into QUEUE. The caller either holds a lock on NODE, or
3309 does not need to lock NODE. */
3312 queue_insert (struct merge_node_queue *queue, struct merge_node *node)
3314 pthread_mutex_lock (&queue->mutex);
3315 heap_insert (queue->priority_queue, node);
3316 node->queued = true;
3317 pthread_mutex_unlock (&queue->mutex);
3318 pthread_cond_signal (&queue->cond);
3321 /* Pop the top node off the priority QUEUE, lock the node, return it. */
3323 static struct merge_node *
3324 queue_pop (struct merge_node_queue *queue)
3326 struct merge_node *node;
3327 pthread_mutex_lock (&queue->mutex);
3328 while (! (node = heap_remove_top (queue->priority_queue)))
3329 pthread_cond_wait (&queue->cond, &queue->mutex);
3330 pthread_mutex_unlock (&queue->mutex);
3332 node->queued = false;
3336 /* Output LINE to TFP, unless -u is specified and the line compares
3337 equal to the previous line. TEMP_OUTPUT is the name of TFP, or
3338 is null if TFP is standard output.
3340 This function does not save the line for comparison later, so it is
3341 appropriate only for internal sort. */
3344 write_unique (struct line const *line, FILE *tfp, char const *temp_output)
3346 static struct line saved;
3350 if (saved.text && ! compare (line, &saved))
3355 write_line (line, tfp, temp_output);
3358 /* Merge the lines currently available to a NODE in the binary
3359 merge tree. Merge a number of lines appropriate for this merge
3360 level, assuming TOTAL_LINES is the total number of lines.
3362 If merging at the top level, send output to TFP. TEMP_OUTPUT is
3363 the name of TFP, or is null if TFP is standard output. */
3366 mergelines_node (struct merge_node *restrict node, size_t total_lines,
3367 FILE *tfp, char const *temp_output)
3369 struct line *lo_orig = node->lo;
3370 struct line *hi_orig = node->hi;
3371 size_t to_merge = MAX_MERGE (total_lines, node->level);
3375 if (node->level > MERGE_ROOT)
3377 /* Merge to destination buffer. */
3378 struct line *dest = *node->dest;
3379 while (node->lo != node->end_lo && node->hi != node->end_hi && to_merge--)
3380 if (compare (node->lo - 1, node->hi - 1) <= 0)
3381 *--dest = *--node->lo;
3383 *--dest = *--node->hi;
3385 merged_lo = lo_orig - node->lo;
3386 merged_hi = hi_orig - node->hi;
3388 if (node->nhi == merged_hi)
3389 while (node->lo != node->end_lo && to_merge--)
3390 *--dest = *--node->lo;
3391 else if (node->nlo == merged_lo)
3392 while (node->hi != node->end_hi && to_merge--)
3393 *--dest = *--node->hi;
3398 /* Merge directly to output. */
3399 while (node->lo != node->end_lo && node->hi != node->end_hi && to_merge--)
3401 if (compare (node->lo - 1, node->hi - 1) <= 0)
3402 write_unique (--node->lo, tfp, temp_output);
3404 write_unique (--node->hi, tfp, temp_output);
3407 merged_lo = lo_orig - node->lo;
3408 merged_hi = hi_orig - node->hi;
3410 if (node->nhi == merged_hi)
3412 while (node->lo != node->end_lo && to_merge--)
3413 write_unique (--node->lo, tfp, temp_output);
3415 else if (node->nlo == merged_lo)
3417 while (node->hi != node->end_hi && to_merge--)
3418 write_unique (--node->hi, tfp, temp_output);
3423 merged_lo = lo_orig - node->lo;
3424 merged_hi = hi_orig - node->hi;
3425 node->nlo -= merged_lo;
3426 node->nhi -= merged_hi;
3429 /* Into QUEUE, insert NODE if it is not already queued, and if one of
3430 NODE's children has available lines and the other either has
3431 available lines or has exhausted its lines. */
3434 queue_check_insert (struct merge_node_queue *queue, struct merge_node *node)
3438 bool lo_avail = (node->lo - node->end_lo) != 0;
3439 bool hi_avail = (node->hi - node->end_hi) != 0;
3440 if (lo_avail ? hi_avail || ! node->nhi : hi_avail && ! node->nlo)
3441 queue_insert (queue, node);
3445 /* Into QUEUE, insert NODE's parent if the parent can now be worked on. */
3448 queue_check_insert_parent (struct merge_node_queue *queue,
3449 struct merge_node *node)
3451 if (node->level > MERGE_ROOT)
3453 lock_node (node->parent);
3454 queue_check_insert (queue, node->parent);
3455 unlock_node (node->parent);
3457 else if (node->nlo + node->nhi == 0)
3459 /* If the MERGE_ROOT NODE has finished merging, insert the
3461 queue_insert (queue, node->parent);
3465 /* Repeatedly pop QUEUE for a node with lines to merge, and merge at least
3466 some of those lines, until the MERGE_END node is popped.
3467 TOTAL_LINES is the total number of lines. If merging at the top
3468 level, send output to TFP. TEMP_OUTPUT is the name of TFP, or is
3469 null if TFP is standard output. */
3472 merge_loop (struct merge_node_queue *queue,
3473 size_t total_lines, FILE *tfp, char const *temp_output)
3477 struct merge_node *node = queue_pop (queue);
3479 if (node->level == MERGE_END)
3482 /* Reinsert so other threads can pop it. */
3483 queue_insert (queue, node);
3486 mergelines_node (node, total_lines, tfp, temp_output);
3487 queue_check_insert (queue, node);
3488 queue_check_insert_parent (queue, node);
3495 static void sortlines (struct line *restrict, size_t, size_t,
3496 struct merge_node *, struct merge_node_queue *,
3497 FILE *, char const *);
3499 /* Thread arguments for sortlines_thread. */
3503 /* Source, i.e., the array of lines to sort. This points just past
3504 the end of the array. */
3507 /* Number of threads to use. If 0 or 1, sort single-threaded. */
3510 /* Number of lines in LINES and DEST. */
3511 size_t const total_lines;
3513 /* Merge node. Lines from this node and this node's sibling will merged
3514 to this node's parent. */
3515 struct merge_node *const node;
3517 /* The priority queue controlling available work for the entire
3519 struct merge_node_queue *const queue;
3521 /* If at the top level, the file to output to, and the file's name.
3522 If the file is standard output, the file's name is null. */
3524 char const *output_temp;
3527 /* Like sortlines, except with a signature acceptable to pthread_create. */
3530 sortlines_thread (void *data)
3532 struct thread_args const *args = data;
3533 sortlines (args->lines, args->nthreads, args->total_lines,
3534 args->node, args->queue, args->tfp,
3539 /* Sort lines, possibly in parallel. The arguments are as in struct
3542 The algorithm has three phases: node creation, sequential sort,
3545 During node creation, sortlines recursively visits each node in the
3546 binary merge tree and creates a NODE structure corresponding to all the
3547 future line merging NODE is responsible for. For each call to
3548 sortlines, half the available threads are assigned to each recursive
3549 call, until a leaf node having only 1 available thread is reached.
3551 Each leaf node then performs two sequential sorts, one on each half of
3552 the lines it is responsible for. It records in its NODE structure that
3553 there are two sorted sublists available to merge from, and inserts its
3554 NODE into the priority queue.
3556 The binary merge phase then begins. Each thread drops into a loop
3557 where the thread retrieves a NODE from the priority queue, merges lines
3558 available to that NODE, and potentially insert NODE or its parent back
3559 into the queue if there are sufficient available lines for them to
3560 merge. This continues until all lines at all nodes of the merge tree
3561 have been merged. */
3564 sortlines (struct line *restrict lines, size_t nthreads,
3565 size_t total_lines, struct merge_node *node,
3566 struct merge_node_queue *queue, FILE *tfp, char const *temp_output)
3568 size_t nlines = node->nlo + node->nhi;
3570 /* Calculate thread arguments. */
3571 size_t lo_threads = nthreads / 2;
3572 size_t hi_threads = nthreads - lo_threads;
3574 struct thread_args args = {lines, lo_threads, total_lines,
3575 node->lo_child, queue, tfp, temp_output};
3577 if (nthreads > 1 && SUBTHREAD_LINES_HEURISTIC <= nlines
3578 && pthread_create (&thread, NULL, sortlines_thread, &args) == 0)
3580 sortlines (lines - node->nlo, hi_threads, total_lines,
3581 node->hi_child, queue, tfp, temp_output);
3582 pthread_join (thread, NULL);
3586 /* Nthreads = 1, this is a leaf NODE, or pthread_create failed.
3587 Sort with 1 thread. */
3588 size_t nlo = node->nlo;
3589 size_t nhi = node->nhi;
3590 struct line *temp = lines - total_lines;
3592 sequential_sort (lines - nlo, nhi, temp - nlo / 2, false);
3594 sequential_sort (lines, nlo, temp, false);
3596 /* Update merge NODE. No need to lock yet. */
3598 node->hi = lines - nlo;
3599 node->end_lo = lines - nlo;
3600 node->end_hi = lines - nlo - nhi;
3602 queue_insert (queue, node);
3603 merge_loop (queue, total_lines, tfp, temp_output);
3606 pthread_mutex_destroy (&node->lock);
3609 /* Scan through FILES[NTEMPS .. NFILES-1] looking for files that are
3610 the same as OUTFILE. If found, replace each with the same
3611 temporary copy that can be merged into OUTFILE without destroying
3612 OUTFILE before it is completely read. This temporary copy does not
3613 count as a merge temp, so don't worry about incrementing NTEMPS in
3614 the caller; final cleanup will remove it, not zaptemp.
3616 This test ensures that an otherwise-erroneous use like
3617 "sort -m -o FILE ... FILE ..." copies FILE before writing to it.
3618 It's not clear that POSIX requires this nicety.
3619 Detect common error cases, but don't try to catch obscure cases like
3620 "cat ... FILE ... | sort -m -o FILE"
3621 where traditional "sort" doesn't copy the input and where
3622 people should know that they're getting into trouble anyway.
3623 Catching these obscure cases would slow down performance in
3627 avoid_trashing_input (struct sortfile *files, size_t ntemps,
3628 size_t nfiles, char const *outfile)
3631 bool got_outstat = false;
3632 struct stat outstat;
3633 struct tempnode *tempcopy = NULL;
3635 for (i = ntemps; i < nfiles; i++)
3637 bool is_stdin = STREQ (files[i].name, "-");
3641 if (outfile && STREQ (outfile, files[i].name) && !is_stdin)
3647 if (fstat (STDOUT_FILENO, &outstat) != 0)
3653 ? fstat (STDIN_FILENO, &instat)
3654 : stat (files[i].name, &instat))
3656 && SAME_INODE (instat, outstat));
3664 tempcopy = create_temp (&tftp);
3665 mergefiles (&files[i], 0, 1, tftp, tempcopy->name);
3668 files[i].name = tempcopy->name;
3669 files[i].temp = tempcopy;
3674 /* Scan the input files to ensure all are accessible.
3675 Otherwise exit with a diagnostic.
3677 Note this will catch common issues with permissions etc.
3678 but will fail to notice issues where you can open() but not read(),
3679 like when a directory is specified on some systems.
3680 Catching these obscure cases could slow down performance in
3684 check_inputs (char *const *files, size_t nfiles)
3687 for (i = 0; i < nfiles; i++)
3689 if (STREQ (files[i], "-"))
3692 if (euidaccess (files[i], R_OK) != 0)
3693 die (_("cannot read"), files[i]);
3697 /* Ensure a specified output file can be created or written to,
3698 and point stdout to it. Do not truncate the file.
3699 Exit with a diagnostic on failure. */
3702 check_output (char const *outfile)
3706 int outfd = open (outfile, O_WRONLY | O_CREAT | O_BINARY, MODE_RW_UGO);
3708 die (_("open failed"), outfile);
3709 move_fd_or_die (outfd, STDOUT_FILENO);
3713 /* Merge the input FILES. NTEMPS is the number of files at the
3714 start of FILES that are temporary; it is zero at the top level.
3715 NFILES is the total number of files. Put the output in
3716 OUTPUT_FILE; a null OUTPUT_FILE stands for standard output. */
3719 merge (struct sortfile *files, size_t ntemps, size_t nfiles,
3720 char const *output_file)
3722 while (nmerge < nfiles)
3724 /* Number of input files processed so far. */
3727 /* Number of output files generated so far. */
3730 /* nfiles % NMERGE; this counts input files that are left over
3731 after all full-sized merges have been done. */
3734 /* Number of easily-available slots at the next loop iteration. */
3737 /* Do as many NMERGE-size merges as possible. In the case that
3738 nmerge is bogus, increment by the maximum number of file
3739 descriptors allowed. */
3740 for (out = in = 0; nmerge <= nfiles - in; out++)
3743 struct tempnode *temp = create_temp (&tfp);
3744 size_t num_merged = mergefiles (&files[in], MIN (ntemps, nmerge),
3745 nmerge, tfp, temp->name);
3746 ntemps -= MIN (ntemps, num_merged);
3747 files[out].name = temp->name;
3748 files[out].temp = temp;
3752 remainder = nfiles - in;
3753 cheap_slots = nmerge - out % nmerge;
3755 if (cheap_slots < remainder)
3757 /* So many files remain that they can't all be put into the last
3758 NMERGE-sized output window. Do one more merge. Merge as few
3759 files as possible, to avoid needless I/O. */
3760 size_t nshortmerge = remainder - cheap_slots + 1;
3762 struct tempnode *temp = create_temp (&tfp);
3763 size_t num_merged = mergefiles (&files[in], MIN (ntemps, nshortmerge),
3764 nshortmerge, tfp, temp->name);
3765 ntemps -= MIN (ntemps, num_merged);
3766 files[out].name = temp->name;
3767 files[out++].temp = temp;
3771 /* Put the remaining input files into the last NMERGE-sized output
3772 window, so they will be merged in the next pass. */
3773 memmove (&files[out], &files[in], (nfiles - in) * sizeof *files);
3778 avoid_trashing_input (files, ntemps, nfiles, output_file);
3780 /* We aren't guaranteed that this final mergefiles will work, therefore we
3781 try to merge into the output, and then merge as much as we can into a
3782 temp file if we can't. Repeat. */
3786 /* Merge directly into the output file if possible. */
3788 size_t nopened = open_input_files (files, nfiles, &fps);
3790 if (nopened == nfiles)
3792 FILE *ofp = stream_open (output_file, "w");
3795 mergefps (files, ntemps, nfiles, ofp, output_file, fps);
3798 if (errno != EMFILE || nopened <= 2)
3799 die (_("open failed"), output_file);
3801 else if (nopened <= 2)
3802 die (_("open failed"), files[nopened].name);
3804 /* We ran out of file descriptors. Close one of the input
3805 files, to gain a file descriptor. Then create a temporary
3806 file with our spare file descriptor. Retry if that failed
3807 (e.g., some other process could open a file between the time
3808 we closed and tried to create). */
3810 struct tempnode *temp;
3814 xfclose (fps[nopened], files[nopened].name);
3815 temp = maybe_create_temp (&tfp, ! (nopened <= 2));
3819 /* Merge into the newly allocated temporary. */
3820 mergefps (&files[0], MIN (ntemps, nopened), nopened, tfp, temp->name,
3822 ntemps -= MIN (ntemps, nopened);
3823 files[0].name = temp->name;
3824 files[0].temp = temp;
3826 memmove (&files[1], &files[nopened], (nfiles - nopened) * sizeof *files);
3828 nfiles -= nopened - 1;
3832 /* Sort NFILES FILES onto OUTPUT_FILE. Use at most NTHREADS threads. */
3835 sort (char *const *files, size_t nfiles, char const *output_file,
3839 IF_LINT (buf.buf = NULL);
3841 bool output_file_created = false;
3847 char const *temp_output;
3848 char const *file = *files;
3849 FILE *fp = xfopen (file, "r");
3852 size_t bytes_per_line;
3858 while (tmp < nthreads)
3863 bytes_per_line = (mult * sizeof (struct line));
3866 bytes_per_line = sizeof (struct line) * 3 / 2;
3869 initbuf (&buf, bytes_per_line,
3870 sort_buffer_size (&fp, 1, files, nfiles, bytes_per_line));
3875 while (fillbuf (&buf, fp, file))
3879 if (buf.eof && nfiles
3880 && (bytes_per_line + 1
3881 < (buf.alloc - buf.used - bytes_per_line * buf.nlines)))
3883 /* End of file, but there is more input and buffer room.
3884 Concatenate the next input file; this is faster in
3886 buf.left = buf.used;
3890 line = buffer_linelim (&buf);
3891 if (buf.eof && !nfiles && !ntemps && !buf.left)
3894 tfp = xfopen (output_file, "w");
3895 temp_output = output_file;
3896 output_file_created = true;
3901 temp_output = create_temp (&tfp)->name;
3905 struct merge_node_queue queue;
3906 queue_init (&queue, nthreads);
3907 struct merge_node *merge_tree =
3908 merge_tree_init (nthreads, buf.nlines, line);
3909 struct merge_node *root = merge_tree + 1;
3911 sortlines (line, nthreads, buf.nlines, root,
3912 &queue, tfp, temp_output);
3913 queue_destroy (&queue);
3914 pthread_mutex_destroy (&root->lock);
3915 merge_tree_destroy (merge_tree);
3918 write_unique (line - 1, tfp, temp_output);
3920 xfclose (tfp, temp_output);
3922 if (output_file_created)
3931 if (! output_file_created)
3934 struct tempnode *node = temphead;
3935 struct sortfile *tempfiles = xnmalloc (ntemps, sizeof *tempfiles);
3936 for (i = 0; node; i++)
3938 tempfiles[i].name = node->name;
3939 tempfiles[i].temp = node;
3942 merge (tempfiles, ntemps, ntemps, output_file);
3949 /* Insert a malloc'd copy of key KEY_ARG at the end of the key list. */
3952 insertkey (struct keyfield *key_arg)
3954 struct keyfield **p;
3955 struct keyfield *key = xmemdup (key_arg, sizeof *key);
3957 for (p = &keylist; *p; p = &(*p)->next)
3963 /* Report a bad field specification SPEC, with extra info MSGID. */
3965 static void badfieldspec (char const *, char const *)
3968 badfieldspec (char const *spec, char const *msgid)
3970 error (SORT_FAILURE, 0, _("%s: invalid field specification %s"),
3971 _(msgid), quote (spec));
3975 /* Report incompatible options. */
3977 static void incompatible_options (char const *) ATTRIBUTE_NORETURN;
3979 incompatible_options (char const *opts)
3981 error (SORT_FAILURE, 0, _("options '-%s' are incompatible"), opts);
3985 /* Check compatibility of ordering options. */
3988 check_ordering_compatibility (void)
3990 struct keyfield *key;
3992 for (key = keylist; key; key = key->next)
3993 if (1 < (key->numeric + key->general_numeric + key->human_numeric
3994 + key->month + (key->version | key->random | !!key->ignore)))
3996 /* The following is too big, but guaranteed to be "big enough". */
3997 char opts[sizeof short_options];
3998 /* Clear flags we're not interested in. */
3999 key->skipsblanks = key->skipeblanks = key->reverse = false;
4000 key_to_opts (key, opts);
4001 incompatible_options (opts);
4005 /* Parse the leading integer in STRING and store the resulting value
4006 (which must fit into size_t) into *VAL. Return the address of the
4007 suffix after the integer. If the value is too large, silently
4008 substitute SIZE_MAX. If MSGID is NULL, return NULL after
4009 failure; otherwise, report MSGID and exit on failure. */
4012 parse_field_count (char const *string, size_t *val, char const *msgid)
4017 switch (xstrtoumax (string, &suffix, 10, &n, ""))
4020 case LONGINT_INVALID_SUFFIX_CHAR:
4025 case LONGINT_OVERFLOW:
4026 case LONGINT_OVERFLOW | LONGINT_INVALID_SUFFIX_CHAR:
4030 case LONGINT_INVALID:
4032 error (SORT_FAILURE, 0, _("%s: invalid count at start of %s"),
4033 _(msgid), quote (string));
4040 /* Handle interrupts and hangups. */
4043 sighandler (int sig)
4046 signal (sig, SIG_IGN);
4050 signal (sig, SIG_DFL);
4054 /* Set the ordering options for KEY specified in S.
4055 Return the address of the first character in S that
4056 is not a valid ordering option.
4057 BLANKTYPE is the kind of blanks that 'b' should skip. */
4060 set_ordering (char const *s, struct keyfield *key, enum blanktype blanktype)
4067 if (blanktype == bl_start || blanktype == bl_both)
4068 key->skipsblanks = true;
4069 if (blanktype == bl_end || blanktype == bl_both)
4070 key->skipeblanks = true;
4073 key->ignore = nondictionary;
4076 key->translate = fold_toupper;
4079 key->general_numeric = true;
4082 key->human_numeric = true;
4085 /* Option order should not matter, so don't let -i override
4086 -d. -d implies -i, but -i does not imply -d. */
4088 key->ignore = nonprinting;
4094 key->numeric = true;
4100 key->reverse = true;
4103 key->version = true;
4113 /* Initialize KEY. */
4115 static struct keyfield *
4116 key_init (struct keyfield *key)
4118 memset (key, 0, sizeof *key);
4119 key->eword = SIZE_MAX;
4124 main (int argc, char **argv)
4126 struct keyfield *key;
4127 struct keyfield key_buf;
4128 struct keyfield gkey;
4129 bool gkey_only = false;
4133 bool mergeonly = false;
4134 char *random_source = NULL;
4135 bool need_random = false;
4136 size_t nthreads = 0;
4138 bool posixly_correct = (getenv ("POSIXLY_CORRECT") != NULL);
4139 bool obsolete_usage = (posix2_version () < 200112);
4141 char *files_from = NULL;
4143 char const *outfile = NULL;
4145 initialize_main (&argc, &argv);
4146 set_program_name (argv[0]);
4147 setlocale (LC_ALL, "");
4148 bindtextdomain (PACKAGE, LOCALEDIR);
4149 textdomain (PACKAGE);
4151 initialize_exit_failure (SORT_FAILURE);
4153 hard_LC_COLLATE = hard_locale (LC_COLLATE);
4154 #if HAVE_NL_LANGINFO
4155 hard_LC_TIME = hard_locale (LC_TIME);
4158 /* Get locale's representation of the decimal point. */
4160 struct lconv const *locale = localeconv ();
4162 /* If the locale doesn't define a decimal point, or if the decimal
4163 point is multibyte, use the C locale's decimal point. FIXME:
4164 add support for multibyte decimal points. */
4165 decimal_point = to_uchar (locale->decimal_point[0]);
4166 if (! decimal_point || locale->decimal_point[1])
4167 decimal_point = '.';
4169 /* FIXME: add support for multibyte thousands separators. */
4170 thousands_sep = to_uchar (*locale->thousands_sep);
4171 if (! thousands_sep || locale->thousands_sep[1])
4175 have_read_stdin = false;
4180 static int const sig[] =
4182 /* The usual suspects. */
4183 SIGALRM, SIGHUP, SIGINT, SIGPIPE, SIGQUIT, SIGTERM,
4200 enum { nsigs = ARRAY_CARDINALITY (sig) };
4203 struct sigaction act;
4205 sigemptyset (&caught_signals);
4206 for (i = 0; i < nsigs; i++)
4208 sigaction (sig[i], NULL, &act);
4209 if (act.sa_handler != SIG_IGN)
4210 sigaddset (&caught_signals, sig[i]);
4213 act.sa_handler = sighandler;
4214 act.sa_mask = caught_signals;
4217 for (i = 0; i < nsigs; i++)
4218 if (sigismember (&caught_signals, sig[i]))
4219 sigaction (sig[i], &act, NULL);
4221 for (i = 0; i < nsigs; i++)
4222 if (signal (sig[i], SIG_IGN) != SIG_IGN)
4224 signal (sig[i], sighandler);
4225 siginterrupt (sig[i], 1);
4229 signal (SIGCHLD, SIG_DFL); /* Don't inherit CHLD handling from parent. */
4231 /* The signal mask is known, so it is safe to invoke exit_cleanup. */
4232 atexit (exit_cleanup);
4235 gkey.sword = SIZE_MAX;
4237 files = xnmalloc (argc, sizeof *files);
4241 /* Parse an operand as a file after "--" was seen; or if
4242 pedantic and a file was seen, unless the POSIX version
4243 predates 1003.1-2001 and -c was not seen and the operand is
4244 "-o FILE" or "-oFILE". */
4248 || (posixly_correct && nfiles != 0
4249 && ! (obsolete_usage
4252 && argv[optind][0] == '-' && argv[optind][1] == 'o'
4253 && (argv[optind][2] || optind + 1 != argc)))
4254 || ((c = getopt_long (argc, argv, short_options,
4260 files[nfiles++] = argv[optind++];
4266 if (optarg[0] == '+')
4268 bool minus_pos_usage = (optind != argc && argv[optind][0] == '-'
4269 && ISDIGIT (argv[optind][1]));
4270 obsolete_usage |= minus_pos_usage && !posixly_correct;
4273 /* Treat +POS1 [-POS2] as a key if possible; but silently
4274 treat an operand as a file if it is not a valid +POS1. */
4275 key = key_init (&key_buf);
4276 s = parse_field_count (optarg + 1, &key->sword, NULL);
4278 s = parse_field_count (s + 1, &key->schar, NULL);
4279 if (! (key->sword || key->schar))
4280 key->sword = SIZE_MAX;
4281 if (! s || *set_ordering (s, key, bl_start))
4285 if (minus_pos_usage)
4287 char const *optarg1 = argv[optind++];
4288 s = parse_field_count (optarg1 + 1, &key->eword,
4289 N_("invalid number after '-'"));
4290 /* When called with a non-NULL message ID,
4291 parse_field_count cannot return NULL. Tell static
4292 analysis tools that dereferencing S is safe. */
4295 s = parse_field_count (s + 1, &key->echar,
4296 N_("invalid number after '.'"));
4297 if (!key->echar && key->eword)
4299 /* obsolescent syntax +A.x -B.y is equivalent to:
4300 -k A+1.x+1,B.y (when y = 0)
4301 -k A+1.x+1,B+1.y (when y > 0)
4302 So eword is decremented as in the -k case
4303 only when the end field (B) is specified and
4307 if (*set_ordering (s, key, bl_end))
4308 badfieldspec (optarg1,
4309 N_("stray character in field spec"));
4311 key->obsolete_used = true;
4317 files[nfiles++] = optarg;
4321 c = XARGMATCH ("--sort", optarg, sort_args, sort_types);
4338 set_ordering (str, &gkey, bl_both);
4344 ? XARGMATCH ("--check", optarg, check_args, check_types)
4349 if (checkonly && checkonly != c)
4350 incompatible_options ("cC");
4354 case COMPRESS_PROGRAM_OPTION:
4355 if (compress_program && !STREQ (compress_program, optarg))
4356 error (SORT_FAILURE, 0, _("multiple compress programs specified"));
4357 compress_program = optarg;
4360 case DEBUG_PROGRAM_OPTION:
4364 case FILES0_FROM_OPTION:
4365 files_from = optarg;
4369 key = key_init (&key_buf);
4372 s = parse_field_count (optarg, &key->sword,
4373 N_("invalid number at field start"));
4376 /* Provoke with 'sort -k0' */
4377 badfieldspec (optarg, N_("field number is zero"));
4381 s = parse_field_count (s + 1, &key->schar,
4382 N_("invalid number after '.'"));
4385 /* Provoke with 'sort -k1.0' */
4386 badfieldspec (optarg, N_("character offset is zero"));
4389 if (! (key->sword || key->schar))
4390 key->sword = SIZE_MAX;
4391 s = set_ordering (s, key, bl_start);
4394 key->eword = SIZE_MAX;
4400 s = parse_field_count (s + 1, &key->eword,
4401 N_("invalid number after ','"));
4404 /* Provoke with 'sort -k1,0' */
4405 badfieldspec (optarg, N_("field number is zero"));
4409 s = parse_field_count (s + 1, &key->echar,
4410 N_("invalid number after '.'"));
4412 s = set_ordering (s, key, bl_end);
4415 badfieldspec (optarg, N_("stray character in field spec"));
4424 specify_nmerge (oi, c, optarg);
4428 if (outfile && !STREQ (outfile, optarg))
4429 error (SORT_FAILURE, 0, _("multiple output files specified"));
4433 case RANDOM_SOURCE_OPTION:
4434 if (random_source && !STREQ (random_source, optarg))
4435 error (SORT_FAILURE, 0, _("multiple random sources specified"));
4436 random_source = optarg;
4444 specify_sort_size (oi, c, optarg);
4449 char newtab = optarg[0];
4451 error (SORT_FAILURE, 0, _("empty tab"));
4454 if (STREQ (optarg, "\\0"))
4458 /* Provoke with 'sort -txx'. Complain about
4459 "multi-character tab" instead of "multibyte tab", so
4460 that the diagnostic's wording does not need to be
4461 changed once multibyte characters are supported. */
4462 error (SORT_FAILURE, 0, _("multi-character tab %s"),
4466 if (tab != TAB_DEFAULT && tab != newtab)
4467 error (SORT_FAILURE, 0, _("incompatible tabs"));
4473 add_temp_dir (optarg);
4476 case PARALLEL_OPTION:
4477 nthreads = specify_nthreads (oi, c, optarg);
4485 /* Accept and ignore e.g. -y0 for compatibility with Solaris 2.x
4486 through Solaris 7. It is also accepted by many non-Solaris
4487 "sort" implementations, e.g., AIX 5.2, HP-UX 11i v2, IRIX 6.5.
4488 -y is marked as obsolete starting with Solaris 8 (1999), but is
4489 still accepted as of Solaris 10 prerelease (2004).
4491 Solaris 2.5.1 "sort -y 100" reads the input file "100", but
4492 emulate Solaris 8 and 9 "sort -y 100" which ignores the "100",
4493 and which in general ignores the argument after "-y" if it
4494 consists entirely of digits (it can even be empty). */
4495 if (optarg == argv[optind - 1])
4498 for (p = optarg; ISDIGIT (*p); p++)
4500 optind -= (*p != '\0');
4508 case_GETOPT_HELP_CHAR;
4510 case_GETOPT_VERSION_CHAR (PROGRAM_NAME, AUTHORS);
4513 usage (SORT_FAILURE);
4521 /* When using --files0-from=F, you may not specify any files
4522 on the command-line. */
4525 error (0, 0, _("extra operand %s"), quote (files[0]));
4526 fprintf (stderr, "%s\n",
4527 _("file operands cannot be combined with --files0-from"));
4528 usage (SORT_FAILURE);
4531 if (STREQ (files_from, "-"))
4535 stream = fopen (files_from, "r");
4537 error (SORT_FAILURE, errno, _("cannot open %s for reading"),
4538 quote (files_from));
4541 readtokens0_init (&tok);
4543 if (! readtokens0 (stream, &tok) || fclose (stream) != 0)
4544 error (SORT_FAILURE, 0, _("cannot read file names from %s"),
4545 quote (files_from));
4553 for (i = 0; i < nfiles; i++)
4555 if (STREQ (files[i], "-"))
4556 error (SORT_FAILURE, 0, _("when reading file names from stdin, "
4557 "no file name of %s allowed"),
4559 else if (files[i][0] == '\0')
4561 /* Using the standard 'filename:line-number:' prefix here is
4562 not totally appropriate, since NUL is the separator,
4563 not NL, but it might be better than nothing. */
4564 unsigned long int file_number = i + 1;
4565 error (SORT_FAILURE, 0,
4566 _("%s:%lu: invalid zero-length file name"),
4567 quotearg_colon (files_from), file_number);
4572 error (SORT_FAILURE, 0, _("no input from %s"),
4573 quote (files_from));
4576 /* Inheritance of global options to individual keys. */
4577 for (key = keylist; key; key = key->next)
4579 if (default_key_compare (key) && !key->reverse)
4581 key->ignore = gkey.ignore;
4582 key->translate = gkey.translate;
4583 key->skipsblanks = gkey.skipsblanks;
4584 key->skipeblanks = gkey.skipeblanks;
4585 key->month = gkey.month;
4586 key->numeric = gkey.numeric;
4587 key->general_numeric = gkey.general_numeric;
4588 key->human_numeric = gkey.human_numeric;
4589 key->version = gkey.version;
4590 key->random = gkey.random;
4591 key->reverse = gkey.reverse;
4594 need_random |= key->random;
4597 if (!keylist && !default_key_compare (&gkey))
4601 need_random |= gkey.random;
4604 check_ordering_compatibility ();
4608 if (checkonly || outfile)
4610 static char opts[] = "X --debug";
4611 opts[0] = (checkonly ? checkonly : 'o');
4612 incompatible_options (opts);
4615 /* Always output the locale in debug mode, since this
4616 is such a common source of confusion. */
4617 if (hard_LC_COLLATE)
4618 error (0, 0, _("using %s sorting rules"),
4619 quote (setlocale (LC_COLLATE, NULL)));
4621 error (0, 0, _("using simple byte comparison"));
4622 key_warnings (&gkey, gkey_only);
4625 reverse = gkey.reverse;
4628 random_md5_state_init (random_source);
4630 if (temp_dir_count == 0)
4632 char const *tmp_dir = getenv ("TMPDIR");
4633 add_temp_dir (tmp_dir ? tmp_dir : DEFAULT_TMPDIR);
4638 static char *minus = (char *) "-";
4644 /* Need to re-check that we meet the minimum requirement for memory
4645 usage with the final value for NMERGE. */
4647 sort_size = MAX (sort_size, MIN_SORT_SIZE);
4652 error (SORT_FAILURE, 0, _("extra operand %s not allowed with -%c"),
4653 quote (files[1]), checkonly);
4657 static char opts[] = {0, 'o', 0};
4658 opts[0] = checkonly;
4659 incompatible_options (opts);
4662 /* POSIX requires that sort return 1 IFF invoked with -c or -C and the
4663 input is not properly sorted. */
4664 exit (check (files[0], checkonly) ? EXIT_SUCCESS : SORT_OUT_OF_ORDER);
4667 /* Check all inputs are accessible, or exit immediately. */
4668 check_inputs (files, nfiles);
4670 /* Check output is writable, or exit immediately. */
4671 check_output (outfile);
4675 struct sortfile *sortfiles = xcalloc (nfiles, sizeof *sortfiles);
4678 for (i = 0; i < nfiles; ++i)
4679 sortfiles[i].name = files[i];
4681 merge (sortfiles, 0, nfiles, outfile);
4682 IF_LINT (free (sortfiles));
4688 unsigned long int np = num_processors (NPROC_CURRENT_OVERRIDABLE);
4689 nthreads = MIN (np, DEFAULT_MAX_THREADS);
4692 /* Avoid integer overflow later. */
4693 size_t nthreads_max = SIZE_MAX / (2 * sizeof (struct merge_node));
4694 nthreads = MIN (nthreads, nthreads_max);
4696 sort (files, nfiles, outfile, nthreads);
4699 if (have_read_stdin && fclose (stdin) == EOF)
4700 die (_("close failed"), "-");
4702 exit (EXIT_SUCCESS);