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 #ifdef BB_FEATURE_SORT_REVERSE
33 #define APPLY_REVERSE(x) (reverse ? -(x) : (x))
34 static int reverse = 0;
36 #define APPLY_REVERSE(x) (x)
39 /* typedefs _______________________________________________________________ */
43 char *data; /* line data */
44 struct Line *next; /* pointer to next line node */
47 /* singly-linked list of lines */
49 int len; /* number of Lines */
50 Line **sorted; /* array fed to qsort */
51 Line *head; /* head of List */
52 Line *current; /* current Line */
55 /* comparison function */
56 typedef int (Compare) (const void *, const void *);
59 /* methods ________________________________________________________________ */
61 static const int max = 1024;
64 static Line *line_alloc()
67 self = malloc(1 * sizeof(Line));
71 /* Construct Line from FILE* */
72 static Line *line_newFromFile(FILE * src)
77 if ((cstring = get_line_from_file(src))) {
90 static Line *line_release(Line * self)
103 static int compare_ascii(const void *a, const void *b)
113 // fprintf(stdout, "> %p: %s< %p: %s", x, x->data, y, y->data);
114 return APPLY_REVERSE(strcmp(x->data, y->data));
118 static int compare_numeric(const void *a, const void *b)
129 xint = strtoul(x->data, NULL, 10);
130 yint = strtoul(y->data, NULL, 10);
132 return APPLY_REVERSE(xint - yint);
139 static List *list_init(List * self)
144 self->current = NULL;
148 /* for simplicity, the List gains ownership of the line */
149 static List *list_insert(List * self, Line * line)
155 /* first insertion */
156 if (self->head == NULL) {
158 self->current = line;
160 /* all subsequent insertions */
162 self->current->next = line;
163 self->current = line;
169 /* order the list according to compare() */
170 static List *list_sort(List * self, Compare * compare)
175 /* mallocate array of Line*s */
176 self->sorted = (Line **) malloc(self->len * sizeof(Line *));
177 if (self->sorted == NULL) {
181 /* fill array w/ List's contents */
185 self->sorted[i++] = line;
190 qsort(self->sorted, self->len, sizeof(Line *), compare);
194 /* precondition: list must be sorted */
195 static List *list_writeToFile(List * self, FILE * dst)
198 Line **line = self->sorted;
200 if (self->sorted == NULL) {
203 for (i = 0; i < self->len; i++) {
204 fprintf(dst, "%s", line[i]->data);
210 static void list_release(List * self)
225 int sort_main(int argc, char **argv)
234 compare = compare_ascii;
238 for (i = 1; i < argc; i++) {
239 if (argv[i][0] == '-') {
246 /* numeric comparison */
247 compare = compare_numeric;
249 #ifdef BB_FEATURE_SORT_REVERSE
256 errorMsg("invalid option -- %c\n", opt);
264 /* this could be factored better */
268 while ((l = line_newFromFile(stdin))) {
269 list_insert(&list, l);
271 list_sort(&list, compare);
272 list_writeToFile(&list, stdout);
275 /* work w/ what's left in argv[] */
279 for (; i < argc; i++) {
280 src = fopen(argv[i], "r");
284 while ((l = line_newFromFile(src))) {
285 list_insert(&list, l);
289 list_sort(&list, compare);
290 list_writeToFile(&list, stdout);
297 /* $Id: sort.c,v 1.20 2000/07/16 20:57:15 kraai Exp $ */