1 /* vi: set sw=4 ts=4: */
3 * Mini sort implementation for busybox
6 * Copyright (C) 1999,2000 by Lineo, inc.
7 * Written by John Beppu <beppu@lineo.com>
9 * This program is free software; you can redistribute it and/or modify
10 * it under the terms of the GNU General Public License as published by
11 * the Free Software Foundation; either version 2 of the License, or
12 * (at your option) any later version.
14 * This program is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 * General Public License for more details.
19 * You should have received a copy of the GNU General Public License
20 * along with this program; if not, write to the Free Software
21 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
26 #include <sys/types.h>
32 static const char sort_usage[] = "sort [-n]"
33 #ifdef BB_FEATURE_SORT_REVERSE
37 #ifndef BB_FEATURE_TRIVIAL_HELP
38 "\nSorts lines of text in the specified files\n"
42 #ifdef BB_FEATURE_SORT_REVERSE
43 #define APPLY_REVERSE(x) (reverse ? -(x) : (x))
44 static int reverse = 0;
46 #define APPLY_REVERSE(x) (x)
49 /* typedefs _______________________________________________________________ */
53 char *data; /* line data */
54 struct Line *next; /* pointer to next line node */
57 /* singly-linked list of lines */
59 int len; /* number of Lines */
60 Line **sorted; /* array fed to qsort */
61 Line *head; /* head of List */
62 Line *current; /* current Line */
65 /* comparison function */
66 typedef int (Compare) (const void *, const void *);
69 /* methods ________________________________________________________________ */
71 static const int max = 1024;
74 static Line *line_alloc()
77 self = malloc(1 * sizeof(Line));
81 /* Construct Line from FILE* */
82 static Line *line_newFromFile(FILE * src)
87 if ((cstring = get_line_from_file(src))) {
100 static Line *line_release(Line * self)
113 static int compare_ascii(const void *a, const void *b)
123 // fprintf(stdout, "> %p: %s< %p: %s", x, x->data, y, y->data);
124 return APPLY_REVERSE(strcmp(x->data, y->data));
128 static int compare_numeric(const void *a, const void *b)
139 xint = strtoul(x->data, NULL, 10);
140 yint = strtoul(y->data, NULL, 10);
142 return APPLY_REVERSE(xint - yint);
149 static List *list_init(List * self)
154 self->current = NULL;
158 /* for simplicity, the List gains ownership of the line */
159 static List *list_insert(List * self, Line * line)
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() */
180 static List *list_sort(List * self, Compare * compare)
185 /* mallocate array of Line*s */
186 self->sorted = (Line **) malloc(self->len * sizeof(Line *));
187 if (self->sorted == NULL) {
191 /* fill array w/ List's contents */
195 self->sorted[i++] = line;
200 qsort(self->sorted, self->len, sizeof(Line *), compare);
204 /* precondition: list must be sorted */
205 static List *list_writeToFile(List * self, FILE * dst)
208 Line **line = self->sorted;
210 if (self->sorted == NULL) {
213 for (i = 0; i < self->len; i++) {
214 fprintf(dst, "%s", line[i]->data);
220 static void list_release(List * self)
235 int sort_main(int argc, char **argv)
244 compare = compare_ascii;
248 for (i = 1; i < argc; i++) {
249 if (argv[i][0] == '-') {
256 /* numeric comparison */
257 compare = compare_numeric;
259 #ifdef BB_FEATURE_SORT_REVERSE
266 fprintf(stderr, "sort: invalid option -- %c\n", opt);
274 /* this could be factored better */
278 while ((l = line_newFromFile(stdin))) {
279 list_insert(&list, l);
281 list_sort(&list, compare);
282 list_writeToFile(&list, stdout);
285 /* work w/ what's left in argv[] */
289 for (; i < argc; i++) {
290 src = fopen(argv[i], "r");
294 while ((l = line_newFromFile(src))) {
295 list_insert(&list, l);
299 list_sort(&list, compare);
300 list_writeToFile(&list, stdout);
307 /* $Id: sort.c,v 1.18 2000/06/28 22:15:26 markw Exp $ */