source: MondoRescue/branches/stable/mindi-busybox/coreutils/sort.c @ 1770

Last change on this file since 1770 was 1770, checked in by Bruno Cornec, 12 years ago
  • Better output for mindi-busybox revision
  • Remove dummy file created on NFS - report from Arnaud Tiger <arnaud.tiger_at_hp.com>
  • strace useful for debug
  • fix new versions for pb (2.0.0 for mindi and 1.7.2 for mindi-busybox)
  • fix build process for mindi-busybox + options used in that version (dd for label-partitions-as-necessary)
  • fix typo in label-partitions-as-necessary which doesn't seem to work
  • Update to busybox 1.7.2
  • perl is now required at restore time to support uuid swap partitions (and will be used for many other thigs

in the future for sure)

  • next mindi version will be 2.0.0 due to all the changes made in it (udev may break working distros)
  • small optimization in mindi on keyboard handling (one single find instead of multiple)
  • better interaction for USB device when launching mindi manually
  • attempt to automatically guess block disk size for ramdisk
  • fix typos in bkphw
  • Fix the remaining problem with UUID support for swap partitions
  • Updates mondoarchive man page for USB support
  • Adds preliminary Hardware support to mindi (Proliant SSSTK)
  • Tries to add udev support also for rhel4
  • Fix UUID support which was still broken.
  • Be conservative in test for the start-nfs script
  • Update config file for mindi-busybox for 1.7.2 migration
  • Try to run around a busybox bug (1.2.2 pb on inexistant links)
  • Add build content for mindi-busybox in pb
  • Remove distributions content for mindi-busybox
  • Fix a warning on inexistant raidtab
  • Solve problem on tmpfs in restore init (Problem of inexistant symlink and busybox)
  • Create MONDO_CACHE and use it everywhere + creation at start
  • Really never try to eject a USB device
  • Fix a issue with &> usage (replaced with 1> and 2>)
  • Adds magic file to depllist in order to have file working + ldd which helps for debugging issues
  • tty modes correct to avoid sh error messages
  • Use ext3 normally and not ext2 instead
  • USB device should be corrected after reading (take 1st part)
  • Adds a mount_USB_here function derived from mount_CDROM_here
  • usb detection place before /dev detection in device name at restore time
  • Fix when restoring from USB: media is asked in interactive mode
  • Adds USB support for mondorestore
  • mount_cdrom => mount_media
  • elilo.efi is now searched throughout /boot/efi and not in a fixed place as there is no standard
  • untar-and-softlink => untar (+ interface change)
  • suppress useless softlinks creation/removal in boot process
  • avoids udevd messages on groups
  • Increase # of disks to 99 as in mindi at restore time (should be a conf file parameter)
  • skip existing big file creation
  • seems to work correctly for USB mindi boot
  • Adds group and tty link to udev conf
  • Always load usb-torage (even 2.6) to initiate USB bus discovery
  • Better printing of messages
  • Attempt to fix a bug in supporting OpenSusE 10.3 kernel for initramfs (mindi may now use multiple regex for kernel initrd detection)
  • Links were not correctly done as non relative for modules in mindi
  • exclusion of modules denied now works
  • Also create modules in their ordinary place, so that classical modprobe works + copy modules.dep
  • Fix bugs for DENY_MODS handling
  • Add device /dev/console for udev
  • ide-generic should now really be excluded
  • Fix a bug in major number for tty
  • If udev then adds modprobe/insmod to rootfs
  • tty0 is also cretaed with udev
  • ide-generic put rather in DENY_MODS
  • udevd remove from deplist s handled in mindi directly
  • better default for mindi when using --usb
  • Handles dynamically linked busybox (in case we want to use it soon ;-)
  • Adds fixed devices to create for udev
  • ide-generic should not be part of the initrd when using libata v2
  • support a dynamically linked udev (case on Ubuntu 7.10 and Mandriva 2008.0 so should be quite generic) This will give incitation to move to dyn. linked binaries in the initrd which will help for other tasks (ia6 4)
  • Improvement in udev support (do not use cl options not available in busybox)
  • Udev in mindi
    • auto creation of the right links at boot time with udev-links.conf(from Mandriva 2008.0)
    • rework startup of udev as current makes kernel crash (from Mandriva 2008.0)
    • add support for 64 bits udev
  • Try to render MyInsmod? silent at boot time
  • Adds udev support (mandatory for newest distributions to avoid remapping of devices in a different way as on the original system)
  • We also need vaft format support for USB boot
  • Adds libusual support (Ubuntu 7.10 needs it for USB)
  • Improve Ubuntu/Debian? keyboard detection and support
  • pbinit adapted to new pb (0.8.10). Filtering of docs done in it
  • Suppress some mondo warnings and errors on USB again
  • Tries to fix lack of files in deb mindi package
  • Verify should now work for USB devices
  • More log/mesages improvement for USB support
  • - Supress g_erase_tmpdir_and_scratchdir
  • Improve some log messages for USB support
  • Try to improve install in mindi to avoid issues with isolinux.cfg not installed vene if in the pkg :-(
  • Improve mindi-busybox build
  • In conformity with pb 0.8.9
  • Add support for Ubuntu 7.10 in build process
  • Add USB Key button to Menu UI (CD streamer removed)
  • Attempt to fix error messages on tmp/scratch files at the end by removing those dir at the latest possible.
  • Fix a bug linked to the size of the -E param which could be used (Arnaud Tiger/René? Ribaud).
  • Integrate ~/.pbrc content into mondorescue.pb (required project-builder >= 0.8.7)
  • Put mondorescue in conformity with new pb filtering rules
  • Add USB support at restore time (no test done yet). New start-usb script PB varibale added where useful
  • Unmounting USB device before removal of temporary scratchdir
  • Stil refining USB copy back to mondo (one command was not executed)
  • No need to have the image subdor in the csratchdir when USB.
  • umount the USB partition before attempting to use it
  • Remove useless copy from mindi to mondo at end of USB handling

(risky merge, we are raising the limits of 2 diverging branches. The status of stable is not completely sure as such. Will need lots of tests, but it's not yet done :-()
(merge -r1692:1769 $SVN_M/branches/2.2.5)

File size: 10.5 KB
Line 
1/* vi: set sw=4 ts=4: */
2/*
3 * SuS3 compliant sort implementation for busybox
4 *
5 * Copyright (C) 2004 by Rob Landley <rob@landley.net>
6 *
7 * MAINTAINER: Rob Landley <rob@landley.net>
8 *
9 * Licensed under GPLv2 or later, see file LICENSE in this tarball for details.
10 *
11 * See SuS3 sort standard at:
12 * http://www.opengroup.org/onlinepubs/007904975/utilities/sort.html
13 */
14
15#include "libbb.h"
16
17/* This is a NOEXEC applet. Be very careful! */
18
19
20/*
21    sort [-m][-o output][-bdfinru][-t char][-k keydef]... [file...]
22    sort -c [-bdfinru][-t char][-k keydef][file]
23*/
24
25/* These are sort types */
26static const char OPT_STR[] ALIGN1 = "ngMucszbrdfimS:T:o:k:t:";
27enum {
28    FLAG_n  = 1,            /* Numeric sort */
29    FLAG_g  = 2,            /* Sort using strtod() */
30    FLAG_M  = 4,            /* Sort date */
31/* ucsz apply to root level only, not keys.  b at root level implies bb */
32    FLAG_u  = 8,            /* Unique */
33    FLAG_c  = 0x10,         /* Check: no output, exit(!ordered) */
34    FLAG_s  = 0x20,         /* Stable sort, no ascii fallback at end */
35    FLAG_z  = 0x40,         /* Input is null terminated, not \n */
36/* These can be applied to search keys, the previous four can't */
37    FLAG_b  = 0x80,         /* Ignore leading blanks */
38    FLAG_r  = 0x100,        /* Reverse */
39    FLAG_d  = 0x200,        /* Ignore !(isalnum()|isspace()) */
40    FLAG_f  = 0x400,        /* Force uppercase */
41    FLAG_i  = 0x800,        /* Ignore !isprint() */
42    FLAG_m  = 0x1000,       /* ignored: merge already sorted files; do not sort */
43    FLAG_S  = 0x2000,       /* ignored: -S, --buffer-size=SIZE */
44    FLAG_T  = 0x4000,       /* ignored: -T, --temporary-directory=DIR */
45    FLAG_o  = 0x8000,
46    FLAG_k  = 0x10000,
47    FLAG_t  = 0x20000,
48    FLAG_bb = 0x80000000,   /* Ignore trailing blanks  */
49};
50
51#if ENABLE_FEATURE_SORT_BIG
52static char key_separator;
53
54static struct sort_key {
55    struct sort_key *next_key;  /* linked list */
56    unsigned range[4];  /* start word, start char, end word, end char */
57    unsigned flags;
58} *key_list;
59
60static char *get_key(char *str, struct sort_key *key, int flags)
61{
62    int start = 0, end = 0, len, i, j;
63
64    /* Special case whole string, so we don't have to make a copy */
65    if (key->range[0] == 1 && !key->range[1] && !key->range[2] && !key->range[3]
66     && !(flags & (FLAG_b | FLAG_d | FLAG_f | FLAG_i | FLAG_bb))
67    ) {
68        return str;
69    }
70
71    /* Find start of key on first pass, end on second pass */
72    len = strlen(str);
73    for (j = 0; j < 2; j++) {
74        if (!key->range[2*j])
75            end = len;
76        /* Loop through fields */
77        else {
78            end = 0;
79            for (i = 1; i < key->range[2*j] + j; i++) {
80                if (key_separator) {
81                    /* Skip body of key and separator */
82                    while (str[end]) {
83                        if (str[end++] == key_separator)
84                            break;
85                    }
86                } else {
87                    /* Skip leading blanks */
88                    while (isspace(str[end]))
89                        end++;
90                    /* Skip body of key */
91                    while (str[end]) {
92                        if (isspace(str[end]))
93                            break;
94                        end++;
95                    }
96                }
97            }
98        }
99        if (!j) start = end;
100    }
101    /* Strip leading whitespace if necessary */
102//XXX: skip_whitespace()
103    if (flags & FLAG_b)
104        while (isspace(str[start])) start++;
105    /* Strip trailing whitespace if necessary */
106    if (flags & FLAG_bb)
107        while (end > start && isspace(str[end-1])) end--;
108    /* Handle offsets on start and end */
109    if (key->range[3]) {
110        end += key->range[3] - 1;
111        if (end > len) end = len;
112    }
113    if (key->range[1]) {
114        start += key->range[1] - 1;
115        if (start > len) start = len;
116    }
117    /* Make the copy */
118    if (end < start) end = start;
119    str = xstrndup(str+start, end-start);
120    /* Handle -d */
121    if (flags & FLAG_d) {
122        for (start = end = 0; str[end]; end++)
123            if (isspace(str[end]) || isalnum(str[end]))
124                str[start++] = str[end];
125        str[start] = '\0';
126    }
127    /* Handle -i */
128    if (flags & FLAG_i) {
129        for (start = end = 0; str[end]; end++)
130            if (isprint(str[end]))
131                str[start++] = str[end];
132        str[start] = '\0';
133    }
134    /* Handle -f */
135    if (flags & FLAG_f)
136        for (i = 0; str[i]; i++)
137            str[i] = toupper(str[i]);
138
139    return str;
140}
141
142static struct sort_key *add_key(void)
143{
144    struct sort_key **pkey = &key_list;
145    while (*pkey)
146        pkey = &((*pkey)->next_key);
147    return *pkey = xzalloc(sizeof(struct sort_key));
148}
149
150#define GET_LINE(fp) \
151    ((option_mask32 & FLAG_z) \
152    ? bb_get_chunk_from_file(fp, NULL) \
153    : xmalloc_getline(fp))
154#else
155#define GET_LINE(fp) xmalloc_getline(fp)
156#endif
157
158/* Iterate through keys list and perform comparisons */
159static int compare_keys(const void *xarg, const void *yarg)
160{
161    int flags = option_mask32, retval = 0;
162    char *x, *y;
163
164#if ENABLE_FEATURE_SORT_BIG
165    struct sort_key *key;
166
167    for (key = key_list; !retval && key; key = key->next_key) {
168        flags = key->flags ? key->flags : option_mask32;
169        /* Chop out and modify key chunks, handling -dfib */
170        x = get_key(*(char **)xarg, key, flags);
171        y = get_key(*(char **)yarg, key, flags);
172#else
173    /* This curly bracket serves no purpose but to match the nesting
174       level of the for () loop we're not using */
175    {
176        x = *(char **)xarg;
177        y = *(char **)yarg;
178#endif
179        /* Perform actual comparison */
180        switch (flags & 7) {
181        default:
182            bb_error_msg_and_die("unknown sort type");
183            break;
184        /* Ascii sort */
185        case 0:
186#if ENABLE_LOCALE_SUPPORT
187            retval = strcoll(x, y);
188#else
189            retval = strcmp(x, y);
190#endif
191            break;
192#if ENABLE_FEATURE_SORT_BIG
193        case FLAG_g: {
194            char *xx, *yy;
195            double dx = strtod(x, &xx);
196            double dy = strtod(y, &yy);
197            /* not numbers < NaN < -infinity < numbers < +infinity) */
198            if (x == xx)
199                retval = (y == yy ? 0 : -1);
200            else if (y == yy)
201                retval = 1;
202            /* Check for isnan */
203            else if (dx != dx)
204                retval = (dy != dy) ? 0 : -1;
205            else if (dy != dy)
206                retval = 1;
207            /* Check for infinity.  Could underflow, but it avoids libm. */
208            else if (1.0 / dx == 0.0) {
209                if (dx < 0)
210                    retval = (1.0 / dy == 0.0 && dy < 0) ? 0 : -1;
211                else
212                    retval = (1.0 / dy == 0.0 && dy > 0) ? 0 : 1;
213            } else if (1.0 / dy == 0.0)
214                retval = (dy < 0) ? 1 : -1;
215            else
216                retval = (dx > dy) ? 1 : ((dx < dy) ? -1 : 0);
217            break;
218        }
219        case FLAG_M: {
220            struct tm thyme;
221            int dx;
222            char *xx, *yy;
223
224            xx = strptime(x, "%b", &thyme);
225            dx = thyme.tm_mon;
226            yy = strptime(y, "%b", &thyme);
227            if (!xx)
228                retval = (!yy) ? 0 : -1;
229            else if (!yy)
230                retval = 1;
231            else
232                retval = (dx == thyme.tm_mon) ? 0 : dx - thyme.tm_mon;
233            break;
234        }
235        /* Full floating point version of -n */
236        case FLAG_n: {
237            double dx = atof(x);
238            double dy = atof(y);
239            retval = (dx > dy) ? 1 : ((dx < dy) ? -1 : 0);
240            break;
241        }
242        } /* switch */
243        /* Free key copies. */
244        if (x != *(char **)xarg) free(x);
245        if (y != *(char **)yarg) free(y);
246        /* if (retval) break; - done by for () anyway */
247#else
248        /* Integer version of -n for tiny systems */
249        case FLAG_n:
250            retval = atoi(x) - atoi(y);
251            break;
252        } /* switch */
253#endif
254    } /* for */
255
256    /* Perform fallback sort if necessary */
257    if (!retval && !(option_mask32 & FLAG_s))
258        retval = strcmp(*(char **)xarg, *(char **)yarg);
259
260    if (flags & FLAG_r) return -retval;
261    return retval;
262}
263
264#if ENABLE_FEATURE_SORT_BIG
265static unsigned str2u(char **str)
266{
267    unsigned long lu;
268    if (!isdigit((*str)[0]))
269        bb_error_msg_and_die("bad field specification");
270    lu = strtoul(*str, str, 10);
271    if ((sizeof(long) > sizeof(int) && lu > INT_MAX) || !lu)
272        bb_error_msg_and_die("bad field specification");
273    return lu;
274}
275#endif
276
277int sort_main(int argc, char **argv);
278int sort_main(int argc, char **argv)
279{
280    FILE *fp, *outfile = stdout;
281    char *line, **lines = NULL;
282    char *str_ignored, *str_o, *str_t;
283    llist_t *lst_k = NULL;
284    int i, flag;
285    int linecount = 0;
286
287    xfunc_error_retval = 2;
288
289    /* Parse command line options */
290    /* -o and -t can be given at most once */
291    opt_complementary = "o--o:t--t:" /* -t, -o: maximum one of each */
292            "k::"; /* -k takes list */
293    getopt32(argv, OPT_STR, &str_ignored, &str_ignored, &str_o, &lst_k, &str_t);
294#if ENABLE_FEATURE_SORT_BIG
295    if (option_mask32 & FLAG_o) outfile = xfopen(str_o, "w");
296    if (option_mask32 & FLAG_t) {
297        if (!str_t[0] || str_t[1])
298            bb_error_msg_and_die("bad -t parameter");
299        key_separator = str_t[0];
300    }
301    /* parse sort key */
302    while (lst_k) {
303        enum {
304            FLAG_allowed_for_k =
305                FLAG_n | /* Numeric sort */
306                FLAG_g | /* Sort using strtod() */
307                FLAG_M | /* Sort date */
308                FLAG_b | /* Ignore leading blanks */
309                FLAG_r | /* Reverse */
310                FLAG_d | /* Ignore !(isalnum()|isspace()) */
311                FLAG_f | /* Force uppercase */
312                FLAG_i | /* Ignore !isprint() */
313            0
314        };
315        struct sort_key *key = add_key();
316        char *str_k = lst_k->data;
317        const char *temp2;
318
319        i = 0; /* i==0 before comma, 1 after (-k3,6) */
320        while (*str_k) {
321            /* Start of range */
322            /* Cannot use bb_strtou - suffix can be a letter */
323            key->range[2*i] = str2u(&str_k);
324            if (*str_k == '.') {
325                str_k++;
326                key->range[2*i+1] = str2u(&str_k);
327            }
328            while (*str_k) {
329                if (*str_k == ',' && !i++) {
330                    str_k++;
331                    break;
332                } /* no else needed: fall through to syntax error
333                     because comma isn't in OPT_STR */
334                temp2 = strchr(OPT_STR, *str_k);
335                if (!temp2)
336                    bb_error_msg_and_die("unknown key option");
337                flag = 1 << (temp2 - OPT_STR);
338                if (flag & ~FLAG_allowed_for_k)
339                    bb_error_msg_and_die("unknown sort type");
340                /* b after ',' means strip _trailing_ space */
341                if (i && flag == FLAG_b) flag = FLAG_bb;
342                key->flags |= flag;
343                str_k++;
344            }
345        }
346        /* leaking lst_k... */
347        lst_k = lst_k->link;
348    }
349#endif
350    /* global b strips leading and trailing spaces */
351    if (option_mask32 & FLAG_b) option_mask32 |= FLAG_bb;
352
353    /* Open input files and read data */
354    for (i = argv[optind] ? optind : optind-1; argv[i]; i++) {
355        fp = stdin;
356        if (i >= optind && NOT_LONE_DASH(argv[i]))
357            fp = xfopen(argv[i], "r");
358        for (;;) {
359            line = GET_LINE(fp);
360            if (!line) break;
361            if (!(linecount & 63))
362                lines = xrealloc(lines, sizeof(char *) * (linecount + 64));
363            lines[linecount++] = line;
364        }
365        fclose(fp);
366    }
367#if ENABLE_FEATURE_SORT_BIG
368    /* if no key, perform alphabetic sort */
369    if (!key_list)
370        add_key()->range[0] = 1;
371    /* handle -c */
372    if (option_mask32 & FLAG_c) {
373        int j = (option_mask32 & FLAG_u) ? -1 : 0;
374        for (i = 1; i < linecount; i++)
375            if (compare_keys(&lines[i-1], &lines[i]) > j) {
376                fprintf(stderr, "Check line %d\n", i);
377                return 1;
378            }
379        return 0;
380    }
381#endif
382    /* Perform the actual sort */
383    qsort(lines, linecount, sizeof(char *), compare_keys);
384    /* handle -u */
385    if (option_mask32 & FLAG_u) {
386        flag = 0;
387        /* coreutils 6.3 drop lines for which only key is the same */
388        /* -- disabling last-resort compare... */
389        option_mask32 |= FLAG_s;
390        for (i = 1; i < linecount; i++) {
391            if (!compare_keys(&lines[flag], &lines[i]))
392                free(lines[i]);
393            else
394                lines[++flag] = lines[i];
395        }
396        if (linecount) linecount = flag+1;
397    }
398    /* Print it */
399    for (i = 0; i < linecount; i++)
400        fprintf(outfile, "%s\n", lines[i]);
401
402    fflush_stdout_and_exit(EXIT_SUCCESS);
403}
Note: See TracBrowser for help on using the repository browser.