X-Git-Url: https://git.librecmc.org/?a=blobdiff_plain;f=sort.c;h=0fe7bf99bb0ce7532ddc55669aa5e08706cbc35b;hb=f4acea8cf5175de2292c86b58f2f30d262f14345;hp=4ab673b4d397a86c71a25339aef6ce3197e574f2;hpb=c0ca473af9a5afd17fd6dd916bb6008a036efb20;p=oweals%2Fbusybox.git diff --git a/sort.c b/sort.c index 4ab673b4d..0fe7bf99b 100644 --- a/sort.c +++ b/sort.c @@ -1,5 +1,5 @@ /* - * Mini find implementation for busybox + * Mini sort implementation for busybox * * * Copyright (C) 1999 by Lineo, inc. @@ -32,52 +32,202 @@ static const char sort_usage[] = "Usage: sort [OPTION]... [FILE]...\n\n" ; +/* typedefs _______________________________________________________________ */ /* line node */ -typedef struct { - char *data; /* line data */ - struct Line *next; /* pointer to next line node */ +typedef struct Line { + char *data; /* line data */ + struct Line *next; /* pointer to next line node */ } Line; /* singly-linked list of lines */ typedef struct { - int len; /* number of Lines */ - Line *line; /* array fed to qsort */ - Line *head; /* head of List */ + int len; /* number of Lines */ + Line **sorted; /* array fed to qsort */ + + Line *head; /* head of List */ + Line *current; /* current Line */ } List; +/* comparison function */ +typedef int (Compare)(const void *, const void *); -/* Line methods */ + +/* methods ________________________________________________________________ */ static const int max = 1024; +/* mallocate Line */ +static Line * +line_alloc() +{ + Line *self; + self = malloc(1 * sizeof(Line)); + return self; +} + +/* Initialize Line with string */ static Line * -line_new() +line_init(Line *self, const char *string) { - char buffer[max]; + self->data = malloc((strlen(string) + 1) * sizeof(char)); + if (self->data == NULL) { return NULL; } + strcpy(self->data, string); + self->next = NULL; + return self; +} + +/* Construct Line from FILE* */ +static Line * +line_newFromFile(FILE *src) +{ + char buffer[max]; + Line *self; + + if (fgets(buffer, max, src)) { + self = line_alloc(); + if (self == NULL) { return NULL; } + line_init(self, buffer); + return self; + } + return NULL; +} + +/* Line destructor */ +static Line * +line_release(Line *self) +{ + if (self->data) { + free(self->data); + free(self); + } + return self; } /* Comparison */ +/* ascii order */ static int -compare_ascii(const void *, const void *); +compare_ascii(const void *a, const void *b) +{ + Line **doh; + Line *x, *y; + + doh = (Line **) a; + x = *doh; + doh = (Line **) b; + y = *doh; + // fprintf(stdout, "> %p: %s< %p: %s", x, x->data, y, y->data); + return strcmp(x->data, y->data); +} + +/* numeric order */ static int -compare_numeric(const void *, const void *); +compare_numeric(const void *a, const void *b) +{ + Line **doh; + Line *x, *y; + int xint, yint; + + doh = (Line **) a; + x = *doh; + doh = (Line **) b; + y = *doh; + + xint = strtoul(x->data, NULL, 10); + yint = strtoul(y->data, NULL, 10); + + return (xint - yint); +} /* List */ -static void -list_insert(); +/* */ +static List * +list_init(List *self) +{ + self->len = 0; + self->sorted = NULL; + self->head = NULL; + self->current = NULL; + return self; +} -static void -list_sort(); +/* for simplicity, the List gains ownership of the line */ +static List * +list_insert(List *self, Line *line) +{ + if (line == NULL) { return NULL; } + + /* first insertion */ + if (self->head == NULL) { + self->head = line; + self->current = line; + + /* all subsequent insertions */ + } else { + self->current->next = line; + self->current = line; + } + self->len++; + return self; +} + +/* order the list according to compare() */ +static List * +list_sort(List *self, Compare *compare) +{ + int i; + Line *line; + + /* mallocate array of Line*s */ + self->sorted = (Line **) malloc(self->len * sizeof(Line*)); + if (self->sorted == NULL) { return NULL; } + + /* fill array w/ List's contents */ + i = 0; + line = self->head; + while (line) { + self->sorted[i++] = line; + line = line->next; + } + + /* apply qsort */ + qsort(self->sorted, self->len, sizeof(Line*), compare); + return self; +} + +/* precondition: list must be sorted */ +static List * +list_writeToFile(List *self, FILE* dst) +{ + int i; + Line **line = self->sorted; + + if (self->sorted == NULL) { return NULL; } + for (i = 0; i < self->len; i++) { + fprintf(dst, "%s", line[i]->data); + } + return self; +} +/* deallocate */ static void -list_print(); +list_release(List *self) +{ + Line *i; + Line *die; + i = self->head; + while (i) { + die = i; + i = die->next; + line_release(die); + } +} /* @@ -90,19 +240,35 @@ list_print(); int sort_main(int argc, char **argv) { - int i; - char opt; + int i; + char opt; + List list; + Line *l; + Compare *compare; - /* default behaviour */ + /* init */ + compare = compare_ascii; + list_init(&list); /* parse argv[] */ for (i = 1; i < argc; i++) { if (argv[i][0] == '-') { opt = argv[i][1]; switch (opt) { + case 'g': + /* what's the diff between -g && -n? */ + compare = compare_numeric; + break; case 'h': usage(sort_usage); break; + case 'n': + /* what's the diff between -g && -n? */ + compare = compare_numeric; + break; + case 'r': + /* reverse */ + break; default: fprintf(stderr, "sort: invalid option -- %c\n", opt); usage(sort_usage); @@ -112,16 +278,35 @@ sort_main(int argc, char **argv) } } - /* go through remaining args (if any) */ + /* this could be factored better */ + + /* work w/ stdin */ if (i >= argc) { + while ( (l = line_newFromFile(stdin))) { + list_insert(&list, l); + } + list_sort(&list, compare); + list_writeToFile(&list, stdout); + list_release(&list); + /* work w/ what's left in argv[] */ } else { + FILE *src; + for ( ; i < argc; i++) { + src = fopen(argv[i], "r"); + if (src == NULL) { break; } + while ( (l = line_newFromFile(src))) { + list_insert(&list, l); + } + fclose(src); } + list_sort(&list, compare); + list_writeToFile(&list, stdout); + list_release(&list); } exit(0); } -/* $Date: 1999/12/21 20:00:35 $ */ -/* $Id: sort.c,v 1.1 1999/12/21 20:00:35 beppu Exp $ */ +/* $Id: sort.c,v 1.8 1999/12/23 22:46:10 beppu Exp $ */