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
36 " [FILE]...\n\nSorts lines of text in the specified files\n";
38 #ifdef BB_FEATURE_SORT_REVERSE
39 #define APPLY_REVERSE(x) (reverse ? -(x) : (x))
40 static int reverse = 0;
42 #define APPLY_REVERSE(x) (x)
45 /* typedefs _______________________________________________________________ */
49 char *data; /* line data */
50 struct Line *next; /* pointer to next line node */
53 /* singly-linked list of lines */
55 int len; /* number of Lines */
56 Line **sorted; /* array fed to qsort */
57 Line *head; /* head of List */
58 Line *current; /* current Line */
61 /* comparison function */
62 typedef int (Compare) (const void *, const void *);
65 /* methods ________________________________________________________________ */
67 static const int max = 1024;
70 static Line *line_alloc()
73 self = malloc(1 * sizeof(Line));
77 /* Construct Line from FILE* */
78 static Line *line_newFromFile(FILE * src)
83 if ((cstring = cstring_lineFromFile(src))) {
96 static Line *line_release(Line * self)
109 static int compare_ascii(const void *a, const void *b)
119 // fprintf(stdout, "> %p: %s< %p: %s", x, x->data, y, y->data);
120 return APPLY_REVERSE(strcmp(x->data, y->data));
124 static int compare_numeric(const void *a, const void *b)
135 xint = strtoul(x->data, NULL, 10);
136 yint = strtoul(y->data, NULL, 10);
138 return APPLY_REVERSE(xint - yint);
145 static List *list_init(List * self)
150 self->current = NULL;
154 /* for simplicity, the List gains ownership of the line */
155 static List *list_insert(List * self, Line * line)
161 /* first insertion */
162 if (self->head == NULL) {
164 self->current = line;
166 /* all subsequent insertions */
168 self->current->next = line;
169 self->current = line;
175 /* order the list according to compare() */
176 static List *list_sort(List * self, Compare * compare)
181 /* mallocate array of Line*s */
182 self->sorted = (Line **) malloc(self->len * sizeof(Line *));
183 if (self->sorted == NULL) {
187 /* fill array w/ List's contents */
191 self->sorted[i++] = line;
196 qsort(self->sorted, self->len, sizeof(Line *), compare);
200 /* precondition: list must be sorted */
201 static List *list_writeToFile(List * self, FILE * dst)
204 Line **line = self->sorted;
206 if (self->sorted == NULL) {
209 for (i = 0; i < self->len; i++) {
210 fprintf(dst, "%s", line[i]->data);
216 static void list_release(List * self)
231 int sort_main(int argc, char **argv)
240 compare = compare_ascii;
244 for (i = 1; i < argc; i++) {
245 if (argv[i][0] == '-') {
252 /* numeric comparison */
253 compare = compare_numeric;
255 #ifdef BB_FEATURE_SORT_REVERSE
262 fprintf(stderr, "sort: invalid option -- %c\n", opt);
270 /* this could be factored better */
274 while ((l = line_newFromFile(stdin))) {
275 list_insert(&list, l);
277 list_sort(&list, compare);
278 list_writeToFile(&list, stdout);
281 /* work w/ what's left in argv[] */
285 for (; i < argc; i++) {
286 src = fopen(argv[i], "r");
290 while ((l = line_newFromFile(src))) {
291 list_insert(&list, l);
295 list_sort(&list, compare);
296 list_writeToFile(&list, stdout);
303 /* $Id: sort.c,v 1.15 2000/04/17 04:22:09 beppu Exp $ */