2 * Mini sort implementation for busybox
5 * Copyright (C) 1999 by Lineo, inc.
6 * Written by John Beppu <beppu@lineo.com>
8 * This program is free software; you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License as published by
10 * the Free Software Foundation; either version 2 of the License, or
11 * (at your option) any later version.
13 * This program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * General Public License for more details.
18 * You should have received a copy of the GNU General Public License
19 * along with this program; if not, write to the Free Software
20 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
25 #include <sys/types.h>
31 static const char sort_usage[] =
32 "Usage: sort [OPTION]... [FILE]...\n\n"
35 /* typedefs _______________________________________________________________ */
39 char *data; /* line data */
40 struct Line *next; /* pointer to next line node */
43 /* singly-linked list of lines */
45 int len; /* number of Lines */
46 Line **sorted; /* array fed to qsort */
48 Line *head; /* head of List */
49 Line *current; /* current Line */
52 /* comparison function */
53 typedef int (Compare)(const void *, const void *);
56 /* methods ________________________________________________________________ */
58 static const int max = 1024;
65 self = malloc(1 * sizeof(Line));
69 /* Initialize Line with string */
71 line_init(Line *self, const char *string)
73 self->data = malloc((strlen(string) + 1) * sizeof(char));
74 if (self->data == NULL) { return NULL; }
75 strcpy(self->data, string);
80 /* Construct Line from FILE* */
82 line_newFromFile(FILE *src)
87 if (fgets(buffer, max, src)) {
89 if (self == NULL) { return NULL; }
90 line_init(self, buffer);
98 line_release(Line *self)
112 compare_ascii(const void *a, const void *b)
122 // fprintf(stdout, "> %p: %s< %p: %s", x, x->data, y, y->data);
123 return strcmp(x->data, y->data);
128 compare_numeric(const void *a, const void *b)
139 xint = strtoul(x->data, NULL, 10);
140 yint = strtoul(y->data, NULL, 10);
142 return (xint - yint);
150 list_init(List *self)
155 self->current = NULL;
159 /* for simplicity, the List gains ownership of the line */
161 list_insert(List *self, Line *line)
163 if (line == NULL) { return NULL; }
165 /* first insertion */
166 if (self->head == NULL) {
168 self->current = line;
170 /* all subsequent insertions */
172 self->current->next = line;
173 self->current = line;
179 /* order the list according to compare() */
181 list_sort(List *self, Compare *compare)
186 /* mallocate array of Line*s */
187 self->sorted = (Line **) malloc(self->len * sizeof(Line*));
188 if (self->sorted == NULL) { return NULL; }
190 /* fill array w/ List's contents */
194 self->sorted[i++] = line;
199 qsort(self->sorted, self->len, sizeof(Line*), compare);
203 /* precondition: list must be sorted */
205 list_writeToFile(List *self, FILE* dst)
208 Line **line = self->sorted;
210 if (self->sorted == NULL) { return NULL; }
211 for (i = 0; i < self->len; i++) {
212 fprintf(dst, "%s", line[i]->data);
219 list_release(List *self)
235 * to insert lines into
236 * then I need to sort this list
237 * and finally print it
241 sort_main(int argc, char **argv)
250 compare = compare_ascii;
254 for (i = 1; i < argc; i++) {
255 if (argv[i][0] == '-') {
259 /* what's the diff between -g && -n? */
260 compare = compare_numeric;
266 /* what's the diff between -g && -n? */
267 compare = compare_numeric;
273 fprintf(stderr, "sort: invalid option -- %c\n", opt);
281 /* this could be factored better */
285 while ( (l = line_newFromFile(stdin))) {
286 list_insert(&list, l);
288 list_sort(&list, compare);
289 list_writeToFile(&list, stdout);
292 /* work w/ what's left in argv[] */
296 for ( ; i < argc; i++) {
297 src = fopen(argv[i], "r");
298 if (src == NULL) { break; }
299 while ( (l = line_newFromFile(src))) {
300 list_insert(&list, l);
304 list_sort(&list, compare);
305 list_writeToFile(&list, stdout);
312 /* $Id: sort.c,v 1.8 1999/12/23 22:46:10 beppu Exp $ */