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