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 = xmalloc(1 * sizeof(Line));
71 /* Construct Line from FILE* */
72 static Line *line_newFromFile(FILE * src)
77 if ((cstring = get_line_from_file(src))) {
87 static Line *line_release(Line * self)
100 static int compare_ascii(const void *a, const void *b)
110 // fprintf(stdout, "> %p: %s< %p: %s", x, x->data, y, y->data);
111 return APPLY_REVERSE(strcmp(x->data, y->data));
115 static int compare_numeric(const void *a, const void *b)
126 xint = strtoul(x->data, NULL, 10);
127 yint = strtoul(y->data, NULL, 10);
129 return APPLY_REVERSE(xint - yint);
136 static List *list_init(List * self)
141 self->current = NULL;
145 /* for simplicity, the List gains ownership of the line */
146 static List *list_insert(List * self, Line * line)
152 /* first insertion */
153 if (self->head == NULL) {
155 self->current = line;
157 /* all subsequent insertions */
159 self->current->next = line;
160 self->current = line;
166 /* order the list according to compare() */
167 static List *list_sort(List * self, Compare * compare)
172 /* mallocate array of Line*s */
173 self->sorted = (Line **) xmalloc(self->len * sizeof(Line *));
175 /* fill array w/ List's contents */
179 self->sorted[i++] = line;
184 qsort(self->sorted, self->len, sizeof(Line *), compare);
188 /* precondition: list must be sorted */
189 static List *list_writeToFile(List * self, FILE * dst)
192 Line **line = self->sorted;
194 if (self->sorted == NULL) {
197 for (i = 0; i < self->len; i++) {
198 fprintf(dst, "%s", line[i]->data);
204 static void list_release(List * self)
219 int sort_main(int argc, char **argv)
228 compare = compare_ascii;
232 for (i = 1; i < argc; i++) {
233 if (argv[i][0] == '-') {
240 /* numeric comparison */
241 compare = compare_numeric;
243 #ifdef BB_FEATURE_SORT_REVERSE
250 error_msg("invalid option -- %c\n", opt);
261 while ((l = line_newFromFile(stdin))) {
262 list_insert(&list, l);
267 /* work w/ what's left in argv[] */
270 for (; i < argc; i++) {
271 src = fopen(argv[i], "r");
275 while ((l = line_newFromFile(src))) {
276 list_insert(&list, l);
282 list_sort(&list, compare);
283 list_writeToFile(&list, stdout);
289 /* $Id: sort.c,v 1.24 2000/12/07 19:56:48 markw Exp $ */