diff options
| -rw-r--r-- | coreutils/sort.c | 397 |
1 files changed, 215 insertions, 182 deletions
diff --git a/coreutils/sort.c b/coreutils/sort.c index a6c56ad88..5f91bcb44 100644 --- a/coreutils/sort.c +++ b/coreutils/sort.c @@ -39,11 +39,10 @@ static int global_flags; #define FLAG_bb 32768 /* Ignore trailing blanks */ -#ifdef CONFIG_FEATURE_SORT_BIG +#if ENABLE_FEATURE_SORT_BIG static char key_separator; -static struct sort_key -{ +static struct sort_key { struct sort_key *next_key; /* linked list */ unsigned short range[4]; /* start word, start char, end word, end char */ int flags; @@ -54,270 +53,304 @@ static char *get_key(char *str, struct sort_key *key, int flags) int start = 0, end = 0, len, i, j; /* Special case whole string, so we don't have to make a copy */ - if(key->range[0]==1 && !key->range[1] && !key->range[2] && !key->range[3] - && !(flags&(FLAG_b&FLAG_d&FLAG_f&FLAG_i&FLAG_bb))) return str; - /* Find start of key on first pass, end on second pass*/ - len=strlen(str); + if (key->range[0] == 1 && !key->range[1] && !key->range[2] && !key->range[3] + && !(flags & (FLAG_b | FLAG_d | FLAG_f | FLAG_i | FLAG_bb)) + ) { + return str; + } - for(j=0;j<2;j++) { - if(!key->range[2*j]) end=len; + /* Find start of key on first pass, end on second pass*/ + len = strlen(str); + for (j = 0; j < 2; j++) { + if (!key->range[2*j]) + end = len; /* Loop through fields */ else { - end=0; - for(i=1;i<key->range[2*j]+j;i++) { + end = 0; + for (i = 1; i < key->range[2*j] + j; i++) { /* Skip leading blanks or first separator */ - if(str[end]) { - if(!key_separator && isspace(str[end])) - while(isspace(str[end])) end++; + if (str[end]) { + if (!key_separator && isspace(str[end])) +/* TODO: remove "&& isspace(str[end])" */ + while (isspace(str[end])) end++; } /* Skip body of key */ - for(;str[end];end++) { - if(key_separator) { - if(str[end]==key_separator) break; - } else if(isspace(str[end])) break; + for (; str[end]; end++) { + if (key_separator) { + if (str[end] == key_separator) + break; + } else { + if (isspace(str[end])) + break; + } } } } - if(!j) start=end; + if (!j) start = end; } /* Key with explicit separator starts after separator */ - if(key_separator && str[start]==key_separator) start++; + if (key_separator && str[start] == key_separator) + start++; /* Strip leading whitespace if necessary */ //XXX: skip_whitespace() - if(flags&FLAG_b) while(isspace(str[start])) start++; + if (flags & FLAG_b) + while (isspace(str[start])) start++; /* Strip trailing whitespace if necessary */ - if(flags&FLAG_bb) while(end>start && isspace(str[end-1])) end--; + if (flags & FLAG_bb) + while (end > start && isspace(str[end-1])) end--; /* Handle offsets on start and end */ - if(key->range[3]) { - end+=key->range[3]-1; - if(end>len) end=len; + if (key->range[3]) { + end += key->range[3] - 1; + if (end > len) end = len; } - if(key->range[1]) { - start+=key->range[1]-1; - if(start>len) start=len; + if (key->range[1]) { + start += key->range[1] - 1; + if (start > len) start = len; } /* Make the copy */ - if(end<start) end=start; - str=xstrndup(str+start,end-start); + if (end < start) end = start; + str = xstrndup(str+start, end-start); /* Handle -d */ - if(flags&FLAG_d) { - for(start=end=0;str[end];end++) - if(isspace(str[end]) || isalnum(str[end])) str[start++]=str[end]; - str[start]=0; + if (flags & FLAG_d) { + for (start = end = 0; str[end]; end++) + if (isspace(str[end]) || isalnum(str[end])) + str[start++] = str[end]; + str[start] = '\0'; } /* Handle -i */ - if(flags&FLAG_i) { - for(start=end=0;str[end];end++) - if(isprint(str[end])) str[start++]=str[end]; - str[start]=0; + if (flags & FLAG_i) { + for (start = end = 0; str[end]; end++) + if (isprint(str[end])) + str[start++] = str[end]; + str[start] = '\0'; } /* Handle -f */ - if(flags*FLAG_f) for(i=0;str[i];i++) str[i]=toupper(str[i]); + if (flags & FLAG_f) + for (i = 0; str[i]; i++) + str[i] = toupper(str[i]); return str; } static struct sort_key *add_key(void) { - struct sort_key **pkey=&key_list; - while(*pkey) pkey=&((*pkey)->next_key); + struct sort_key **pkey = &key_list; + while (*pkey) + pkey = &((*pkey)->next_key); return *pkey = xzalloc(sizeof(struct sort_key)); } -#define GET_LINE(fp) (global_flags&FLAG_z) ? bb_get_chunk_from_file(fp,NULL) \ - : xmalloc_getline(fp) +#define GET_LINE(fp) \ + ((global_flags & FLAG_z) \ + ? bb_get_chunk_from_file(fp, NULL) \ + : xmalloc_getline(fp)) #else -#define GET_LINE(fp) xmalloc_getline(fp) +#define GET_LINE(fp) xmalloc_getline(fp) #endif /* Iterate through keys list and perform comparisons */ static int compare_keys(const void *xarg, const void *yarg) { - int flags=global_flags,retval=0; - char *x,*y; + int flags = global_flags, retval = 0; + char *x, *y; -#ifdef CONFIG_FEATURE_SORT_BIG +#if ENABLE_FEATURE_SORT_BIG struct sort_key *key; - for(key=key_list;!retval && key;key=key->next_key) { - flags=(key->flags) ? key->flags : global_flags; + for (key = key_list; !retval && key; key = key->next_key) { + flags = (key->flags) ? key->flags : global_flags; /* Chop out and modify key chunks, handling -dfib */ - x=get_key(*(char **)xarg,key,flags); - y=get_key(*(char **)yarg,key,flags); + x = get_key(*(char **)xarg, key, flags); + y = get_key(*(char **)yarg, key, flags); #else /* This curly bracket serves no purpose but to match the nesting level of the for() loop we're not using */ { - x=*(char **)xarg; - y=*(char **)yarg; + x = *(char **)xarg; + y = *(char **)yarg; #endif /* Perform actual comparison */ - switch(flags&7) { - default: - bb_error_msg_and_die("unknown sort type"); - break; - /* Ascii sort */ - case 0: - retval=strcmp(x,y); - break; -#ifdef CONFIG_FEATURE_SORT_BIG - case FLAG_g: - { - char *xx,*yy; - double dx=strtod(x,&xx), dy=strtod(y,&yy); - /* not numbers < NaN < -infinity < numbers < +infinity) */ - if(x==xx) retval=(y==yy ? 0 : -1); - else if(y==yy) retval=1; - /* Check for isnan */ - else if(dx != dx) retval = (dy != dy) ? 0 : -1; - else if(dy != dy) retval = 1; - /* Check for infinity. Could underflow, but it avoids libm. */ - else if(1.0/dx == 0.0) { - if(dx<0) retval=((1.0/dy == 0.0 && dy<0) ? 0 : -1); - else retval=((1.0/dy == 0.0 && dy>0) ? 0 : 1); - } else if(1.0/dy == 0.0) retval=dy<0 ? 1 : -1; - else retval=dx>dy ? 1 : (dx<dy ? -1 : 0); - break; - } - case FLAG_M: - { - struct tm thyme; - int dx; - char *xx,*yy; + switch (flags & 7) { + default: + bb_error_msg_and_die("unknown sort type"); + break; + /* Ascii sort */ + case 0: + retval = strcmp(x, y); + break; +#if ENABLE_FEATURE_SORT_BIG + case FLAG_g: { + char *xx, *yy; + double dx = strtod(x, &xx), dy = strtod(y, &yy); + /* not numbers < NaN < -infinity < numbers < +infinity) */ + if (x == xx) + retval = (y == yy ? 0 : -1); + else if (y == yy) + retval = 1; + /* Check for isnan */ + else if (dx != dx) + retval = (dy != dy) ? 0 : -1; + else if (dy != dy) + retval = 1; + /* Check for infinity. Could underflow, but it avoids libm. */ + else if (1.0 / dx == 0.0) { + if (dx < 0) + retval = (1.0 / dy == 0.0 && dy < 0) ? 0 : -1; + else + retval = (1.0 / dy == 0.0 && dy > 0) ? 0 : 1; + } else if (1.0 / dy == 0.0) + retval = (dy < 0) ? 1 : -1; + else + retval = (dx > dy) ? 1 : ((dx < dy) ? -1 : 0); + break; + } + case FLAG_M: { + struct tm thyme; + int dx; + char *xx, *yy; - xx=strptime(x,"%b",&thyme); - dx=thyme.tm_mon; - yy=strptime(y,"%b",&thyme); - if(!xx) retval=(!yy ? 0 : -1); - else if(!yy) retval=1; - else retval=(dx==thyme.tm_mon ? 0 : dx-thyme.tm_mon); - break; - } - /* Full floating point version of -n */ - case FLAG_n: - { - double dx=atof(x),dy=atof(y); - retval=dx>dy ? 1 : (dx<dy ? -1 : 0); - break; - } + xx = strptime(x, "%b", &thyme); + dx = thyme.tm_mon; + yy = strptime(y, "%b", &thyme); + if (!xx) + retval = (!yy) ? 0 : -1; + else if (!yy) + retval = 1; + else + retval = (dx==thyme.tm_mon) ? 0 : dx-thyme.tm_mon; + break; + } + /* Full floating point version of -n */ + case FLAG_n: { + double dx = atof(x), dy =atof(y); + retval = (dx > dy) ? 1 : ((dx < dy) ? -1 : 0); + break; + } } /* Free key copies. */ - if(x!=*(char **)xarg) free(x); - if(y!=*(char **)yarg) free(y); - if(retval) break; + if (x != *(char **)xarg) free(x); + if (y != *(char **)yarg) free(y); + if (retval) break; #else - /* Integer version of -n for tiny systems */ - case FLAG_n: - retval=atoi(x)-atoi(y); - break; + /* Integer version of -n for tiny systems */ + case FLAG_n: + retval = atoi(x) - atoi(y); + break; } #endif } /* Perform fallback sort if necessary */ - if(!retval && !(global_flags&FLAG_s)) - retval=strcmp(*(char **)xarg, *(char **)yarg); - return ((flags&FLAG_r)?-1:1)*retval; + if (!retval && !(global_flags & FLAG_s)) + retval = strcmp(*(char **)xarg, *(char **)yarg); + + if (flags & FLAG_r) return -retval; + return retval; } int sort_main(int argc, char **argv) { - FILE *fp,*outfile=NULL; - int linecount=0,i,flag; - char *line,**lines=NULL,*optlist="ngMucszbrdfimS:T:o:k:t:"; + FILE *fp, *outfile = NULL; + int linecount = 0, i, flag; + char *line, **lines = NULL, *optlist = "ngMucszbrdfimS:T:o:k:t:"; int c; xfunc_error_retval = 2; /* Parse command line options */ - while((c=getopt(argc,argv,optlist))>0) { - line=strchr(optlist,c); - if(!line) bb_show_usage(); - switch(*line) { -#ifdef CONFIG_FEATURE_SORT_BIG - case 'o': - if(outfile) bb_error_msg_and_die("too many -o"); - outfile=xfopen(optarg,"w"); - break; - case 't': - if(key_separator || optarg[1]) - bb_error_msg_and_die("too many -t"); - key_separator=*optarg; - break; - /* parse sort key */ - case 'k': - { - struct sort_key *key=add_key(); - char *temp, *temp2; + while ((c = getopt(argc, argv, optlist)) > 0) { + line = strchr(optlist, c); + if (!line) bb_show_usage(); + switch (*line) { +#if ENABLE_FEATURE_SORT_BIG + case 'o': + if (outfile) bb_error_msg_and_die("too many -o"); + outfile = xfopen(optarg, "w"); + break; + case 't': + if (key_separator || optarg[1]) + bb_error_msg_and_die("too many -t"); + key_separator = *optarg; + break; + /* parse sort key */ + case 'k': { + struct sort_key *key = add_key(); + char *temp, *temp2; - temp=optarg; - for(i=0;*temp;) { - /* Start of range */ - key->range[2*i]=(unsigned short)strtol(temp,&temp,10); - if(*temp=='.') - key->range[(2*i)+1]=(unsigned short)strtol(temp+1,&temp,10); - for(;*temp;temp++) { - if(*temp==',' && !i++) { - temp++; - break; - } /* no else needed: fall through to syntax error - because comma isn't in optlist */ - temp2=strchr(optlist,*temp); - flag=(1<<(temp2-optlist)); - if(!temp2 || (flag>FLAG_M && flag<FLAG_b)) - bb_error_msg_and_die("unknown key option"); - /* b after , means strip _trailing_ space */ - if(i && flag==FLAG_b) flag=FLAG_bb; - key->flags|=flag; - } + temp = optarg; + for (i = 0; *temp;) { + /* Start of range */ + key->range[2*i] = (unsigned short)strtol(temp, &temp, 10); + if (*temp == '.') + key->range[(2*i)+1] = (unsigned short)strtol(temp+1, &temp, 10); + for (; *temp; temp++) { + if (*temp == ',' && !i++) { + temp++; + break; + } /* no else needed: fall through to syntax error + because comma isn't in optlist */ + temp2 = strchr(optlist, *temp); + flag = (1 << (temp2 - optlist)); + if (!temp2 || (flag > FLAG_M && flag < FLAG_b)) + bb_error_msg_and_die("unknown key option"); + /* b after ',' means strip _trailing_ space */ + if (i && flag == FLAG_b) flag = FLAG_bb; + key->flags |= flag; } - break; } + break; + } #endif - default: - global_flags|=(1<<(line-optlist)); - /* global b strips leading and trailing spaces */ - if(global_flags&FLAG_b) global_flags|=FLAG_bb; - break; + default: + global_flags |= (1 << (line - optlist)); + /* global b strips leading and trailing spaces */ + if (global_flags & FLAG_b) global_flags |= FLAG_bb; + break; } } /* Open input files and read data */ - for(i=argv[optind] ? optind : optind-1;argv[i];i++) { - if(i<optind || (*argv[i]=='-' && !argv[i][1])) fp=stdin; - else fp=xfopen(argv[i],"r"); - for(;;) { - line=GET_LINE(fp); - if(!line) break; - if(!(linecount&63)) - lines=xrealloc(lines, sizeof(char *)*(linecount+64)); - lines[linecount++]=line; + for (i = argv[optind] ? optind : optind-1; argv[i]; i++) { + fp = stdin; + if (i >= optind && (argv[i][0] != '-' || argv[i][1])) + fp = xfopen(argv[i], "r"); + for (;;) { + line = GET_LINE(fp); + if (!line) break; + if (!(linecount & 63)) + lines = xrealloc(lines, sizeof(char *) * (linecount + 64)); + lines[linecount++] = line; } fclose(fp); } -#ifdef CONFIG_FEATURE_SORT_BIG +#if ENABLE_FEATURE_SORT_BIG /* if no key, perform alphabetic sort */ - if(!key_list) add_key()->range[0]=1; + if (!key_list) + add_key()->range[0] = 1; /* handle -c */ - if(global_flags&FLAG_c) { - int j=(global_flags&FLAG_u) ? -1 : 0; - for(i=1;i<linecount;i++) - if(compare_keys(&lines[i-1],&lines[i])>j) { - fprintf(stderr,"Check line %d\n",i); + if (global_flags & FLAG_c) { + int j = (global_flags & FLAG_u) ? -1 : 0; + for (i = 1; i < linecount; i++) + if (compare_keys(&lines[i-1], &lines[i]) > j) { + fprintf(stderr, "Check line %d\n", i); return 1; } return 0; } #endif /* Perform the actual sort */ - qsort(lines,linecount,sizeof(char *),compare_keys); + qsort(lines, linecount, sizeof(char *), compare_keys); /* handle -u */ - if(global_flags&FLAG_u) { - for(flag=0,i=1;i<linecount;i++) { - if(!compare_keys(&lines[flag],&lines[i])) free(lines[i]); - else lines[++flag]=lines[i]; + if (global_flags & FLAG_u) { + for (flag = 0, i = 1; i < linecount; i++) { + if (!compare_keys(&lines[flag], &lines[i])) + free(lines[i]); + else + lines[++flag] = lines[i]; } - if(linecount) linecount=flag+1; + if (linecount) linecount = flag+1; } /* Print it */ - if(!outfile) outfile=stdout; - for(i=0;i<linecount;i++) fprintf(outfile,"%s\n",lines[i]); + if (!outfile) outfile = stdout; + for (i = 0; i < linecount; i++) + fprintf(outfile, "%s\n", lines[i]); + fflush_stdout_and_exit(EXIT_SUCCESS); } |