From 4aca87515a5083ae0e31ce3177189fd43b6d05ac Mon Sep 17 00:00:00 2001 From: Andreas Baumann Date: Sat, 3 Jan 2015 13:58:15 +0100 Subject: patch to Vanilla Tomato 1.28 --- release/src/router/busybox/coreutils/sort.c | 438 +++++++++++++++++++++++----- 1 file changed, 372 insertions(+), 66 deletions(-) (limited to 'release/src/router/busybox/coreutils/sort.c') diff --git a/release/src/router/busybox/coreutils/sort.c b/release/src/router/busybox/coreutils/sort.c index 8cc4d888..fad6d124 100644 --- a/release/src/router/busybox/coreutils/sort.c +++ b/release/src/router/busybox/coreutils/sort.c @@ -1,100 +1,406 @@ /* vi: set sw=4 ts=4: */ /* - * Mini sort implementation for busybox + * SuS3 compliant sort implementation for busybox * - * Copyright (C) 2000 by Matt Kraai + * Copyright (C) 2004 by Rob Landley * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. + * MAINTAINER: Rob Landley * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - * General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * Licensed under GPLv2 or later, see file LICENSE in this tarball for details. * + * See SuS3 sort standard at: + * http://www.opengroup.org/onlinepubs/007904975/utilities/sort.html */ -/* BB_AUDIT SUSv3 _NOT_ compliant -- a number of options are not supported. */ -/* http://www.opengroup.org/onlinepubs/007904975/utilities/sort.html */ +#include "libbb.h" -/* Mar 16, 2003 Manuel Novoa III (mjn3@codepoet.org) - * - * Now does proper error checking on i/o. Plus some space savings. - */ +/* This is a NOEXEC applet. Be very careful! */ + + +/* + sort [-m][-o output][-bdfinru][-t char][-k keydef]... [file...] + sort -c [-bdfinru][-t char][-k keydef][file] +*/ + +/* These are sort types */ +static const char OPT_STR[] ALIGN1 = "ngMucszbrdfimS:T:o:k:t:"; +enum { + FLAG_n = 1, /* Numeric sort */ + FLAG_g = 2, /* Sort using strtod() */ + FLAG_M = 4, /* Sort date */ +/* ucsz apply to root level only, not keys. b at root level implies bb */ + FLAG_u = 8, /* Unique */ + FLAG_c = 0x10, /* Check: no output, exit(!ordered) */ + FLAG_s = 0x20, /* Stable sort, no ascii fallback at end */ + FLAG_z = 0x40, /* Input and output is NUL terminated, not \n */ +/* These can be applied to search keys, the previous four can't */ + FLAG_b = 0x80, /* Ignore leading blanks */ + FLAG_r = 0x100, /* Reverse */ + FLAG_d = 0x200, /* Ignore !(isalnum()|isspace()) */ + FLAG_f = 0x400, /* Force uppercase */ + FLAG_i = 0x800, /* Ignore !isprint() */ + FLAG_m = 0x1000, /* ignored: merge already sorted files; do not sort */ + FLAG_S = 0x2000, /* ignored: -S, --buffer-size=SIZE */ + FLAG_T = 0x4000, /* ignored: -T, --temporary-directory=DIR */ + FLAG_o = 0x8000, + FLAG_k = 0x10000, + FLAG_t = 0x20000, + FLAG_bb = 0x80000000, /* Ignore trailing blanks */ +}; + +#if ENABLE_FEATURE_SORT_BIG +static char key_separator; -#include -#include -#include -#include -#include "busybox.h" -#include "libcoreutils/coreutils.h" +static struct sort_key { + struct sort_key *next_key; /* linked list */ + unsigned range[4]; /* start word, start char, end word, end char */ + unsigned flags; +} *key_list; -static int compare_ascii(const void *x, const void *y) +static char *get_key(char *str, struct sort_key *key, int flags) { - return strcmp(*(char **)x, *(char **)y); + int start = 0, end = 0, len, j; + unsigned i; + + /* Special case whole string, so we don't have to make a copy */ + if (key->range[0] == 1 && !key->range[1] && !key->range[2] && !key->range[3] + && !(flags & (FLAG_b | FLAG_d | FLAG_f | FLAG_i | FLAG_bb)) + ) { + return str; + } + + /* Find start of key on first pass, end on second pass */ + len = strlen(str); + for (j = 0; j < 2; j++) { + if (!key->range[2*j]) + end = len; + /* Loop through fields */ + else { + end = 0; + for (i = 1; i < key->range[2*j] + j; i++) { + if (key_separator) { + /* Skip body of key and separator */ + while (str[end]) { + if (str[end++] == key_separator) + break; + } + } else { + /* Skip leading blanks */ + while (isspace(str[end])) + end++; + /* Skip body of key */ + while (str[end]) { + if (isspace(str[end])) + break; + end++; + } + } + } + } + if (!j) start = end; + } + /* Strip leading whitespace if necessary */ +//XXX: skip_whitespace() + if (flags & FLAG_b) + while (isspace(str[start])) start++; + /* Strip trailing whitespace if necessary */ + if (flags & FLAG_bb) + while (end > start && isspace(str[end-1])) end--; + /* Handle offsets on start and end */ + if (key->range[3]) { + end += key->range[3] - 1; + if (end > len) end = len; + } + if (key->range[1]) { + start += key->range[1] - 1; + if (start > len) start = len; + } + /* Make the copy */ + if (end < start) end = start; + str = xstrndup(str+start, end-start); + /* Handle -d */ + if (flags & FLAG_d) { + for (start = end = 0; str[end]; end++) + if (isspace(str[end]) || isalnum(str[end])) + str[start++] = str[end]; + str[start] = '\0'; + } + /* Handle -i */ + if (flags & FLAG_i) { + for (start = end = 0; str[end]; end++) + if (isprint(str[end])) + str[start++] = str[end]; + str[start] = '\0'; + } + /* Handle -f */ + if (flags & FLAG_f) + for (i = 0; str[i]; i++) + str[i] = toupper(str[i]); + + return str; } -static int compare_numeric(const void *x, const void *y) +static struct sort_key *add_key(void) { - int z = atoi(*(char **)x) - atoi(*(char **)y); - return z ? z : strcmp(*(char **)x, *(char **)y); + struct sort_key **pkey = &key_list; + while (*pkey) + pkey = &((*pkey)->next_key); + return *pkey = xzalloc(sizeof(struct sort_key)); } -int sort_main(int argc, char **argv) +#define GET_LINE(fp) \ + ((option_mask32 & FLAG_z) \ + ? bb_get_chunk_from_file(fp, NULL) \ + : xmalloc_fgetline(fp)) +#else +#define GET_LINE(fp) xmalloc_fgetline(fp) +#endif + +/* Iterate through keys list and perform comparisons */ +static int compare_keys(const void *xarg, const void *yarg) { - FILE *fp; - char *line, **lines = NULL; - int i, nlines = 0, inc; - int (*compare)(const void *, const void *) = compare_ascii; + int flags = option_mask32, retval = 0; + char *x, *y; - int flags; +#if ENABLE_FEATURE_SORT_BIG + struct sort_key *key; - bb_default_error_retval = 2; + for (key = key_list; !retval && key; key = key->next_key) { + flags = key->flags ? key->flags : option_mask32; + /* Chop out and modify key chunks, handling -dfib */ + x = get_key(*(char **)xarg, key, flags); + y = get_key(*(char **)yarg, key, flags); +#else + /* This curly bracket serves no purpose but to match the nesting + level of the for () loop we're not using */ + { + x = *(char **)xarg; + y = *(char **)yarg; +#endif + /* Perform actual comparison */ + switch (flags & 7) { + default: + bb_error_msg_and_die("unknown sort type"); + break; + /* Ascii sort */ + case 0: +#if ENABLE_LOCALE_SUPPORT + retval = strcoll(x, y); +#else + retval = strcmp(x, y); +#endif + break; +#if ENABLE_FEATURE_SORT_BIG + case FLAG_g: { + char *xx, *yy; + double dx = strtod(x, &xx); + double dy = strtod(y, &yy); + /* not numbers < NaN < -infinity < numbers < +infinity) */ + if (x == xx) + retval = (y == yy ? 0 : -1); + else if (y == yy) + retval = 1; + /* Check for isnan */ + else if (dx != dx) + retval = (dy != dy) ? 0 : -1; + else if (dy != dy) + retval = 1; + /* Check for infinity. Could underflow, but it avoids libm. */ + else if (1.0 / dx == 0.0) { + if (dx < 0) + retval = (1.0 / dy == 0.0 && dy < 0) ? 0 : -1; + else + retval = (1.0 / dy == 0.0 && dy > 0) ? 0 : 1; + } else if (1.0 / dy == 0.0) + retval = (dy < 0) ? 1 : -1; + else + retval = (dx > dy) ? 1 : ((dx < dy) ? -1 : 0); + break; + } + case FLAG_M: { + struct tm thyme; + int dx; + char *xx, *yy; + + xx = strptime(x, "%b", &thyme); + dx = thyme.tm_mon; + yy = strptime(y, "%b", &thyme); + if (!xx) + retval = (!yy) ? 0 : -1; + else if (!yy) + retval = 1; + else + retval = (dx == thyme.tm_mon) ? 0 : dx - thyme.tm_mon; + break; + } + /* Full floating point version of -n */ + case FLAG_n: { + double dx = atof(x); + double dy = atof(y); + retval = (dx > dy) ? 1 : ((dx < dy) ? -1 : 0); + break; + } + } /* switch */ + /* Free key copies. */ + if (x != *(char **)xarg) free(x); + if (y != *(char **)yarg) free(y); + /* if (retval) break; - done by for () anyway */ +#else + /* Integer version of -n for tiny systems */ + case FLAG_n: + retval = atoi(x) - atoi(y); + break; + } /* switch */ +#endif + } /* for */ + + /* Perform fallback sort if necessary */ + if (!retval && !(option_mask32 & FLAG_s)) + retval = strcmp(*(char **)xarg, *(char **)yarg); + + if (flags & FLAG_r) return -retval; + return retval; +} + +#if ENABLE_FEATURE_SORT_BIG +static unsigned str2u(char **str) +{ + unsigned long lu; + if (!isdigit((*str)[0])) + bb_error_msg_and_die("bad field specification"); + lu = strtoul(*str, str, 10); + if ((sizeof(long) > sizeof(int) && lu > INT_MAX) || !lu) + bb_error_msg_and_die("bad field specification"); + return lu; +} +#endif - flags = bb_getopt_ulflags(argc, argv, "nru"); - if (flags & 1) { - compare = compare_numeric; +int sort_main(int argc, char **argv) MAIN_EXTERNALLY_VISIBLE; +int sort_main(int argc UNUSED_PARAM, char **argv) +{ + FILE *fp, *outfile = stdout; + char *line, **lines = NULL; + char *str_ignored, *str_o, *str_t; + llist_t *lst_k = NULL; + int i, flag; + int linecount = 0; + + xfunc_error_retval = 2; + + /* Parse command line options */ + /* -o and -t can be given at most once */ + opt_complementary = "o--o:t--t:" /* -t, -o: maximum one of each */ + "k::"; /* -k takes list */ + getopt32(argv, OPT_STR, &str_ignored, &str_ignored, &str_o, &lst_k, &str_t); +#if ENABLE_FEATURE_SORT_BIG + if (option_mask32 & FLAG_o) outfile = xfopen_for_write(str_o); + if (option_mask32 & FLAG_t) { + if (!str_t[0] || str_t[1]) + bb_error_msg_and_die("bad -t parameter"); + key_separator = str_t[0]; } + /* parse sort key */ + while (lst_k) { + enum { + FLAG_allowed_for_k = + FLAG_n | /* Numeric sort */ + FLAG_g | /* Sort using strtod() */ + FLAG_M | /* Sort date */ + FLAG_b | /* Ignore leading blanks */ + FLAG_r | /* Reverse */ + FLAG_d | /* Ignore !(isalnum()|isspace()) */ + FLAG_f | /* Force uppercase */ + FLAG_i | /* Ignore !isprint() */ + 0 + }; + struct sort_key *key = add_key(); + char *str_k = llist_pop(&lst_k); + const char *temp2; - argv += optind; - if (!*argv) { - *--argv = "-"; + i = 0; /* i==0 before comma, 1 after (-k3,6) */ + while (*str_k) { + /* Start of range */ + /* Cannot use bb_strtou - suffix can be a letter */ + key->range[2*i] = str2u(&str_k); + if (*str_k == '.') { + str_k++; + key->range[2*i+1] = str2u(&str_k); + } + while (*str_k) { + if (*str_k == ',' && !i++) { + str_k++; + break; + } /* no else needed: fall through to syntax error + because comma isn't in OPT_STR */ + temp2 = strchr(OPT_STR, *str_k); + if (!temp2) + bb_error_msg_and_die("unknown key option"); + flag = 1 << (temp2 - OPT_STR); + if (flag & ~FLAG_allowed_for_k) + bb_error_msg_and_die("unknown sort type"); + /* b after ',' means strip _trailing_ space */ + if (i && flag == FLAG_b) flag = FLAG_bb; + key->flags |= flag; + str_k++; + } + } } +#endif + /* global b strips leading and trailing spaces */ + if (option_mask32 & FLAG_b) option_mask32 |= FLAG_bb; + /* Open input files and read data */ + argv += optind; + if (!*argv) + *--argv = (char*)"-"; do { - fp = xgetoptfile_sort_uniq(argv, "r"); - while ((line = bb_get_chomped_line_from_file(fp)) != NULL) { - lines = xrealloc(lines, sizeof(char *) * (nlines + 1)); - lines[nlines++] = line; + /* coreutils 6.9 compat: abort on first open error, + * do not continue to next file: */ + fp = xfopen_stdin(*argv); + for (;;) { + line = GET_LINE(fp); + if (!line) break; + lines = xrealloc_vector(lines, 6, linecount); + lines[linecount++] = line; } - bb_xferror(fp, *argv); - bb_fclose_nonstdin(fp); + fclose_if_not_stdin(fp); } while (*++argv); - /* sort it */ - qsort(lines, nlines, sizeof(char *), compare); - - /* print it */ - i = 0; - --nlines; - if ((inc = 1 - (flags & 2)) < 0) { /* reverse */ - i = nlines; +#if ENABLE_FEATURE_SORT_BIG + /* if no key, perform alphabetic sort */ + if (!key_list) + add_key()->range[0] = 1; + /* handle -c */ + if (option_mask32 & FLAG_c) { + int j = (option_mask32 & FLAG_u) ? -1 : 0; + for (i = 1; i < linecount; i++) + if (compare_keys(&lines[i-1], &lines[i]) > j) { + fprintf(stderr, "Check line %d\n", i); + return EXIT_FAILURE; + } + return EXIT_SUCCESS; } - flags &= 4; - - while (nlines >= 0) { - if (!flags || !nlines || strcmp(lines[i+inc], lines[i])) { - puts(lines[i]); +#endif + /* Perform the actual sort */ + qsort(lines, linecount, sizeof(char *), compare_keys); + /* handle -u */ + if (option_mask32 & FLAG_u) { + flag = 0; + /* coreutils 6.3 drop lines for which only key is the same */ + /* -- disabling last-resort compare... */ + option_mask32 |= FLAG_s; + for (i = 1; i < linecount; i++) { + if (!compare_keys(&lines[flag], &lines[i])) + free(lines[i]); + else + lines[++flag] = lines[i]; } - i += inc; - --nlines; + if (linecount) linecount = flag+1; } + /* Print it */ + flag = (option_mask32 & FLAG_z) ? '\0' : '\n'; + for (i = 0; i < linecount; i++) + fprintf(outfile, "%s%c", lines[i], flag); - bb_fflush_stdout_and_exit(EXIT_SUCCESS); + fflush_stdout_and_exit(EXIT_SUCCESS); } -- cgit v1.2.3-54-g00ecf