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 |
|
---|
24 | static 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
|
---|
50 | static char key_separator;
|
---|
51 |
|
---|
52 | static 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 |
|
---|
59 | static 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 |
|
---|
126 | static 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 */
|
---|
140 | static 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 |
|
---|
229 | int 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 | }
|
---|