diff options
Diffstat (limited to 'sort.c')
| -rw-r--r-- | sort.c | 385 |
1 files changed, 193 insertions, 192 deletions
@@ -1,3 +1,4 @@ +/* vi: set sw=4 ts=4: */ /* * Mini sort implementation for busybox * @@ -28,29 +29,27 @@ #include <stdio.h> #include <errno.h> -static const char sort_usage[] = -"sort [OPTION]... [FILE]...\n\n" -; +static const char sort_usage[] = "sort [OPTION]... [FILE]...\n\n"; /* typedefs _______________________________________________________________ */ /* line node */ typedef struct Line { - char *data; /* line data */ - struct Line *next; /* pointer to next line node */ + 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 **sorted; /* array fed to qsort */ + int len; /* number of Lines */ + Line **sorted; /* array fed to qsort */ - Line *head; /* head of List */ - Line *current; /* current Line */ + Line *head; /* head of List */ + Line *current; /* current Line */ } List; /* comparison function */ -typedef int (Compare)(const void *, const void *); +typedef int (Compare) (const void *, const void *); /* methods ________________________________________________________________ */ @@ -58,175 +57,176 @@ typedef int (Compare)(const void *, const void *); static const int max = 1024; /* mallocate Line */ -static Line * -line_alloc() +static Line *line_alloc() { - Line *self; - self = malloc(1 * sizeof(Line)); - return self; + Line *self; + + self = malloc(1 * sizeof(Line)); + return self; } /* Initialize Line with string */ -static Line * -line_init(Line *self, const char *string) +static Line *line_init(Line * self, const char *string) { - self->data = malloc((strlen(string) + 1) * sizeof(char)); - if (self->data == NULL) { return NULL; } - strcpy(self->data, string); - self->next = NULL; - return self; + 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) +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; + 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) +static Line *line_release(Line * self) { - if (self->data) { - free(self->data); - free(self); - } - return self; + if (self->data) { + free(self->data); + free(self); + } + return self; } /* Comparison */ /* ascii order */ -static int -compare_ascii(const void *a, const void *b) +static int compare_ascii(const void *a, const void *b) { - Line **doh; - Line *x, *y; + Line **doh; + Line *x, *y; - doh = (Line **) a; - x = *doh; - doh = (Line **) b; - y = *doh; + 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); + // 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 *a, const void *b) +static int compare_numeric(const void *a, const void *b) { - Line **doh; - Line *x, *y; - int xint, yint; + Line **doh; + Line *x, *y; + int xint, yint; - doh = (Line **) a; - x = *doh; - doh = (Line **) b; - y = *doh; + doh = (Line **) a; + x = *doh; + doh = (Line **) b; + y = *doh; - xint = strtoul(x->data, NULL, 10); - yint = strtoul(y->data, NULL, 10); + xint = strtoul(x->data, NULL, 10); + yint = strtoul(y->data, NULL, 10); - return (xint - yint); + return (xint - yint); } /* List */ /* */ -static List * -list_init(List *self) +static List *list_init(List * self) { - self->len = 0; - self->sorted = NULL; - self->head = NULL; - self->current = NULL; - return self; + self->len = 0; + self->sorted = NULL; + self->head = NULL; + self->current = NULL; + return self; } /* for simplicity, the List gains ownership of the line */ -static List * -list_insert(List *self, Line *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; + 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) +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; + 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) +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; + 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_release(List *self) +static void list_release(List * self) { - Line *i; - Line *die; - - i = self->head; - while (i) { - die = i; - i = die->next; - line_release(die); - } + Line *i; + Line *die; + + i = self->head; + while (i) { + die = i; + i = die->next; + line_release(die); + } } @@ -237,76 +237,77 @@ list_release(List *self) * and finally print it */ -int -sort_main(int argc, char **argv) +int sort_main(int argc, char **argv) { - int i; - char opt; - List list; - Line *l; - Compare *compare; - - /* 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); - } - } else { - break; + int i; + char opt; + List list; + Line *l; + Compare *compare; + + /* 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); + } + } else { + break; + } } - } - /* this could be factored better */ + /* 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); + /* 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); } - list_sort(&list, compare); - list_writeToFile(&list, stdout); - list_release(&list); - } - exit(0); + exit(0); } -/* $Id: sort.c,v 1.10 2000/02/07 05:29:42 erik Exp $ */ +/* $Id: sort.c,v 1.11 2000/02/08 19:58:47 erik Exp $ */ |