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

Last change on this file since 821 was 821, checked in by Bruno Cornec, 14 years ago

Addition of busybox 1.2.1 as a mindi-busybox new package
This should avoid delivering binary files in mindi not built there (Fedora and Debian are quite serious about that)

File size: 8.9 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 <ctype.h>
16#include <math.h>
17#include <stdio.h>
18#include <stdlib.h>
19#include <string.h>
20#include <time.h>
21#include <unistd.h>
22#include "busybox.h"
23
24static int global_flags;
25
26/*
27    sort [-m][-o output][-bdfinru][-t char][-k keydef]... [file...]
28    sort -c [-bdfinru][-t char][-k keydef][file]
29*/
30
31/* These are sort types */
32#define FLAG_n          1       /* Numeric sort */
33#define FLAG_g          2       /* Sort using strtod() */
34#define FLAG_M          4       /* Sort date */
35/* ucsz apply to root level only, not keys.  b at root level implies bb */
36#define FLAG_u          8       /* Unique */
37#define FLAG_c          16      /* Check: no output, exit(!ordered) */
38#define FLAG_s          32      /* Stable sort, no ascii fallback at end */
39#define FLAG_z          64      /* Input is null terminated, not \n */
40/* These can be applied to search keys, the previous four can't */
41#define FLAG_b          128     /* Ignore leading blanks */
42#define FLAG_r          256     /* Reverse */
43#define FLAG_d          512     /* Ignore !(isalnum()|isspace()) */
44#define FLAG_f          1024    /* Force uppercase */
45#define FLAG_i          2048    /* Ignore !isprint() */
46#define FLAG_bb         32768   /* Ignore trailing blanks  */
47
48
49#ifdef CONFIG_FEATURE_SORT_BIG
50static char key_separator;
51
52static struct sort_key
53{
54    struct sort_key *next_key;  /* linked list */
55    unsigned short range[4];    /* start word, start char, end word, end char */
56    int flags;
57} *key_list;
58
59static char *get_key(char *str, struct sort_key *key, int flags)
60{
61    int start=0,end,len,i,j;
62
63    /* Special case whole string, so we don't have to make a copy */
64    if(key->range[0]==1 && !key->range[1] && !key->range[2] && !key->range[3]
65        && !(flags&(FLAG_b&FLAG_d&FLAG_f&FLAG_i&FLAG_bb))) return str;
66    /* Find start of key on first pass, end on second pass*/
67    len=strlen(str);
68
69    for(j=0;j<2;j++) {
70        if(!key->range[2*j]) end=len;
71        /* Loop through fields */
72        else {
73            end=0;
74            for(i=1;i<key->range[2*j]+j;i++) {
75                /* Skip leading blanks or first separator */
76                if(str[end]) {
77                    if(!key_separator && isspace(str[end]))
78                        while(isspace(str[end])) end++;
79                }
80                /* Skip body of key */
81                for(;str[end];end++) {
82                    if(key_separator) {
83                        if(str[end]==key_separator) break;
84                    } else if(isspace(str[end])) break;
85                }
86            }
87        }
88        if(!j) start=end;
89    }
90    /* Key with explicit separator starts after separator */
91    if(key_separator && str[start]==key_separator) start++;
92    /* Strip leading whitespace if necessary */
93    if(flags&FLAG_b) while(isspace(str[start])) start++;
94    /* Strip trailing whitespace if necessary */
95    if(flags&FLAG_bb) while(end>start && isspace(str[end-1])) end--;
96    /* Handle offsets on start and end */
97    if(key->range[3]) {
98        end+=key->range[3]-1;
99        if(end>len) end=len;
100    }
101    if(key->range[1]) {
102        start+=key->range[1]-1;
103        if(start>len) start=len;
104    }
105    /* Make the copy */
106    if(end<start) end=start;
107    str=bb_xstrndup(str+start,end-start);
108    /* Handle -d */
109    if(flags&FLAG_d) {
110        for(start=end=0;str[end];end++)
111            if(isspace(str[end]) || isalnum(str[end])) str[start++]=str[end];
112        str[start]=0;
113    }
114    /* Handle -i */
115    if(flags&FLAG_i) {
116        for(start=end=0;str[end];end++)
117            if(isprint(str[end])) str[start++]=str[end];
118        str[start]=0;
119    }
120    /* Handle -f */
121    if(flags*FLAG_f) for(i=0;str[i];i++) str[i]=toupper(str[i]);
122
123    return str;
124}
125
126static struct sort_key *add_key(void)
127{
128    struct sort_key **pkey=&key_list;
129    while(*pkey) pkey=&((*pkey)->next_key);
130    return *pkey=xcalloc(1,sizeof(struct sort_key));
131}
132
133#define GET_LINE(fp) (global_flags&FLAG_z) ? bb_get_chunk_from_file(fp,NULL) \
134                                           : bb_get_chomped_line_from_file(fp)
135#else
136#define GET_LINE(fp)        bb_get_chomped_line_from_file(fp)
137#endif
138
139/* Iterate through keys list and perform comparisons */
140static int compare_keys(const void *xarg, const void *yarg)
141{
142    int flags=global_flags,retval=0;
143    char *x,*y;
144
145#ifdef CONFIG_FEATURE_SORT_BIG
146    struct sort_key *key;
147
148    for(key=key_list;!retval && key;key=key->next_key) {
149        flags=(key->flags) ? key->flags : global_flags;
150        /* Chop out and modify key chunks, handling -dfib */
151        x=get_key(*(char **)xarg,key,flags);
152        y=get_key(*(char **)yarg,key,flags);
153#else
154    /* This curly bracket serves no purpose but to match the nesting
155       level of the for() loop we're not using */
156    {
157        x=*(char **)xarg;
158        y=*(char **)yarg;
159#endif
160        /* Perform actual comparison */
161        switch(flags&7) {
162            default:
163                bb_error_msg_and_die("Unknown sort type.");
164                break;
165            /* Ascii sort */
166            case 0:
167                retval=strcmp(x,y);
168                break;
169#ifdef CONFIG_FEATURE_SORT_BIG
170            case FLAG_g:
171            {
172                char *xx,*yy;
173                double dx=strtod(x,&xx), dy=strtod(y,&yy);
174                /* not numbers < NaN < -infinity < numbers < +infinity) */
175                if(x==xx) retval=(y==yy ? 0 : -1);
176                else if(y==yy) retval=1;
177                /* Check for isnan */
178                else if(dx != dx) retval = (dy != dy) ? 0 : -1;
179                else if(dy != dy) retval = 1;
180                /* Check for infinity.  Could underflow, but it avoids libm. */
181                else if(1.0/dx == 0.0) {
182                    if(dx<0) retval=((1.0/dy == 0.0 && dy<0) ? 0 : -1);
183                    else retval=((1.0/dy == 0.0 && dy>0) ? 0 : 1);
184                } else if(1.0/dy == 0.0) retval=dy<0 ? 1 : -1;
185                else retval=dx>dy ? 1 : (dx<dy ? -1 : 0);
186                break;
187            }
188            case FLAG_M:
189            {
190                struct tm thyme;
191                int dx;
192                char *xx,*yy;
193
194                xx=strptime(x,"%b",&thyme);
195                dx=thyme.tm_mon;
196                yy=strptime(y,"%b",&thyme);
197                if(!xx) retval=(!yy ? 0 : -1);
198                else if(!yy) retval=1;
199                else retval=(dx==thyme.tm_mon ? 0 : dx-thyme.tm_mon);
200                break;
201            }
202            /* Full floating point version of -n */
203            case FLAG_n:
204            {
205                double dx=atof(x),dy=atof(y);
206                retval=dx>dy ? 1 : (dx<dy ? -1 : 0);
207                break;
208            }
209        }
210        /* Free key copies. */
211        if(x!=*(char **)xarg) free(x);
212        if(y!=*(char **)yarg) free(y);
213        if(retval) break;
214#else
215            /* Integer version of -n for tiny systems */
216            case FLAG_n:
217                retval=atoi(x)-atoi(y);
218                break;
219        }
220#endif
221    }
222    /* Perform fallback sort if necessary */
223    if(!retval && !(global_flags&FLAG_s))
224            retval=strcmp(*(char **)xarg, *(char **)yarg);
225//dprintf(2,"reverse=%d\n",flags&FLAG_r);
226    return ((flags&FLAG_r)?-1:1)*retval;
227}
228
229int sort_main(int argc, char **argv)
230{
231    FILE *fp,*outfile=NULL;
232    int linecount=0,i,flag;
233    char *line,**lines=NULL,*optlist="ngMucszbrdfimS:T:o:k:t:";
234    int c;
235
236    bb_default_error_retval = 2;
237    /* Parse command line options */
238    while((c=getopt(argc,argv,optlist))>0) {
239        line=strchr(optlist,c);
240        if(!line) bb_show_usage();
241        switch(*line) {
242#ifdef CONFIG_FEATURE_SORT_BIG
243            case 'o':
244                if(outfile) bb_error_msg_and_die("Too many -o.");
245                outfile=bb_xfopen(optarg,"w");
246                break;
247            case 't':
248                if(key_separator || optarg[1])
249                    bb_error_msg_and_die("Too many -t.");
250                key_separator=*optarg;
251                break;
252            /* parse sort key */
253            case 'k':
254            {
255                struct sort_key *key=add_key();
256                char *temp, *temp2;
257
258                temp=optarg;
259                for(i=0;*temp;) {
260                    /* Start of range */
261                    key->range[2*i]=(unsigned short)strtol(temp,&temp,10);
262                    if(*temp=='.')
263                        key->range[(2*i)+1]=(unsigned short)strtol(temp+1,&temp,10);
264                    for(;*temp;temp++) {
265                        if(*temp==',' && !i++) {
266                            temp++;
267                            break;
268                        } /* no else needed: fall through to syntax error
269                             because comma isn't in optlist */
270                        temp2=strchr(optlist,*temp);
271                        flag=(1<<(temp2-optlist));
272                        if(!temp2 || (flag>FLAG_M && flag<FLAG_b))
273                            bb_error_msg_and_die("Unknown key option.");
274                        /* b after , means strip _trailing_ space */
275                        if(i && flag==FLAG_b) flag=FLAG_bb;
276                        key->flags|=flag;
277                    }
278                }
279                break;
280            }
281#endif
282            default:
283                global_flags|=(1<<(line-optlist));
284                /* global b strips leading and trailing spaces */
285                if(global_flags&FLAG_b) global_flags|=FLAG_bb;
286                break;
287        }
288    }
289    /* Open input files and read data */
290    for(i=argv[optind] ? optind : optind-1;argv[i];i++) {
291        if(i<optind || (*argv[i]=='-' && !argv[i][1])) fp=stdin;
292        else fp=bb_xfopen(argv[i],"r");
293        for(;;) {
294            line=GET_LINE(fp);
295            if(!line) break;
296            if(!(linecount&63))
297                lines=xrealloc(lines, sizeof(char *)*(linecount+64));
298            lines[linecount++]=line;
299        }
300        fclose(fp);
301    }
302#ifdef CONFIG_FEATURE_SORT_BIG
303    /* if no key, perform alphabetic sort */
304    if(!key_list) add_key()->range[0]=1;
305    /* handle -c */
306    if(global_flags&FLAG_c) {
307        int j=(global_flags&FLAG_u) ? -1 : 0;
308        for(i=1;i<linecount;i++)
309            if(compare_keys(&lines[i-1],&lines[i])>j) {
310                fprintf(stderr,"Check line %d\n",i);
311                return 1;
312            }
313        return 0;
314    }
315#endif
316    /* Perform the actual sort */
317    qsort(lines,linecount,sizeof(char *),compare_keys);
318    /* handle -u */
319    if(global_flags&FLAG_u) {
320        for(flag=0,i=1;i<linecount;i++) {
321            if(!compare_keys(&lines[flag],&lines[i])) free(lines[i]);
322            else lines[++flag]=lines[i];
323        }
324        if(linecount) linecount=flag+1;
325    }
326    /* Print it */
327    if(!outfile) outfile=stdout;
328    for(i=0;i<linecount;i++) fprintf(outfile,"%s\n",lines[i]);
329    bb_fflush_stdout_and_exit(EXIT_SUCCESS);
330}
Note: See TracBrowser for help on using the repository browser.