| 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 | }
|
|---|
