blob: 49eb4fd728b8eb325e905416de31f31daf9b8edb [file] [log] [blame]
Erik Andersene49d5ec2000-02-08 19:58:47 +00001/* vi: set sw=4 ts=4: */
John Beppuc0ca4731999-12-21 20:00:35 +00002/*
John Beppu568cb7b1999-12-22 23:02:12 +00003 * Mini sort implementation for busybox
John Beppuc0ca4731999-12-21 20:00:35 +00004 *
5 *
Erik Andersen61677fe2000-04-13 01:18:56 +00006 * Copyright (C) 1999,2000 by Lineo, inc.
John Beppuc0ca4731999-12-21 20:00:35 +00007 * Written by John Beppu <beppu@lineo.com>
8 *
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.
13 *
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.
18 *
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
22 *
23 */
24
25#include "internal.h"
26#include <sys/types.h>
27#include <fcntl.h>
28#include <dirent.h>
29#include <stdio.h>
30#include <errno.h>
31
Erik Andersen029011b2000-03-04 21:19:32 +000032static const char sort_usage[] = "sort [-n]"
33#ifdef BB_FEATURE_SORT_REVERSE
34" [-r]"
35#endif
Erik Andersen5e1189e2000-04-15 16:34:54 +000036" [FILE]...\n\nSorts lines of text in the specified files\n";
Erik Andersen029011b2000-03-04 21:19:32 +000037
38#ifdef BB_FEATURE_SORT_REVERSE
39#define APPLY_REVERSE(x) (reverse ? -(x) : (x))
40static int reverse = 0;
41#else
42#define APPLY_REVERSE(x) (x)
43#endif
John Beppuc0ca4731999-12-21 20:00:35 +000044
John Beppuf3e59041999-12-22 22:24:52 +000045/* typedefs _______________________________________________________________ */
John Beppuc0ca4731999-12-21 20:00:35 +000046
47/* line node */
John Beppuf3e59041999-12-22 22:24:52 +000048typedef struct Line {
Erik Andersene49d5ec2000-02-08 19:58:47 +000049 char *data; /* line data */
50 struct Line *next; /* pointer to next line node */
John Beppuc0ca4731999-12-21 20:00:35 +000051} Line;
52
53/* singly-linked list of lines */
54typedef struct {
Erik Andersene49d5ec2000-02-08 19:58:47 +000055 int len; /* number of Lines */
56 Line **sorted; /* array fed to qsort */
Erik Andersene49d5ec2000-02-08 19:58:47 +000057 Line *head; /* head of List */
58 Line *current; /* current Line */
John Beppuc0ca4731999-12-21 20:00:35 +000059} List;
60
John Beppuf3e59041999-12-22 22:24:52 +000061/* comparison function */
Erik Andersene49d5ec2000-02-08 19:58:47 +000062typedef int (Compare) (const void *, const void *);
John Beppuf3e59041999-12-22 22:24:52 +000063
John Beppuc0ca4731999-12-21 20:00:35 +000064
John Beppu38efa791999-12-22 00:30:29 +000065/* methods ________________________________________________________________ */
John Beppuc0ca4731999-12-21 20:00:35 +000066
67static const int max = 1024;
68
John Beppu38efa791999-12-22 00:30:29 +000069/* mallocate Line */
Erik Andersene49d5ec2000-02-08 19:58:47 +000070static Line *line_alloc()
John Beppuc0ca4731999-12-21 20:00:35 +000071{
Erik Andersene49d5ec2000-02-08 19:58:47 +000072 Line *self;
Erik Andersene49d5ec2000-02-08 19:58:47 +000073 self = malloc(1 * sizeof(Line));
74 return self;
John Beppu38efa791999-12-22 00:30:29 +000075}
76
John Beppu38efa791999-12-22 00:30:29 +000077/* Construct Line from FILE* */
Erik Andersene49d5ec2000-02-08 19:58:47 +000078static Line *line_newFromFile(FILE * src)
John Beppu38efa791999-12-22 00:30:29 +000079{
Erik Andersene49d5ec2000-02-08 19:58:47 +000080 Line *self;
John Beppu5a728cf2000-04-17 04:22:09 +000081 char *cstring = NULL;
John Beppu38efa791999-12-22 00:30:29 +000082
John Beppu5a728cf2000-04-17 04:22:09 +000083 if ((cstring = cstring_lineFromFile(src))) {
Erik Andersene49d5ec2000-02-08 19:58:47 +000084 self = line_alloc();
85 if (self == NULL) {
86 return NULL;
87 }
John Beppu5a728cf2000-04-17 04:22:09 +000088 self->data = cstring;
89 self->next = NULL;
Erik Andersene49d5ec2000-02-08 19:58:47 +000090 return self;
91 }
92 return NULL;
John Beppuc0ca4731999-12-21 20:00:35 +000093}
94
John Beppu019513a1999-12-22 17:57:31 +000095/* Line destructor */
Erik Andersene49d5ec2000-02-08 19:58:47 +000096static Line *line_release(Line * self)
John Beppu019513a1999-12-22 17:57:31 +000097{
Erik Andersene49d5ec2000-02-08 19:58:47 +000098 if (self->data) {
99 free(self->data);
100 free(self);
101 }
102 return self;
John Beppu019513a1999-12-22 17:57:31 +0000103}
104
John Beppuc0ca4731999-12-21 20:00:35 +0000105
106/* Comparison */
107
John Beppu568cb7b1999-12-22 23:02:12 +0000108/* ascii order */
Erik Andersene49d5ec2000-02-08 19:58:47 +0000109static int compare_ascii(const void *a, const void *b)
John Beppuf3e59041999-12-22 22:24:52 +0000110{
Erik Andersene49d5ec2000-02-08 19:58:47 +0000111 Line **doh;
112 Line *x, *y;
John Beppu568cb7b1999-12-22 23:02:12 +0000113
Erik Andersene49d5ec2000-02-08 19:58:47 +0000114 doh = (Line **) a;
115 x = *doh;
116 doh = (Line **) b;
117 y = *doh;
John Beppu568cb7b1999-12-22 23:02:12 +0000118
Erik Andersene49d5ec2000-02-08 19:58:47 +0000119 // fprintf(stdout, "> %p: %s< %p: %s", x, x->data, y, y->data);
Erik Andersen029011b2000-03-04 21:19:32 +0000120 return APPLY_REVERSE(strcmp(x->data, y->data));
John Beppuf3e59041999-12-22 22:24:52 +0000121}
John Beppuc0ca4731999-12-21 20:00:35 +0000122
John Beppu568cb7b1999-12-22 23:02:12 +0000123/* numeric order */
Erik Andersene49d5ec2000-02-08 19:58:47 +0000124static int compare_numeric(const void *a, const void *b)
John Beppuf3e59041999-12-22 22:24:52 +0000125{
Erik Andersene49d5ec2000-02-08 19:58:47 +0000126 Line **doh;
127 Line *x, *y;
128 int xint, yint;
John Beppuee512a31999-12-23 00:02:49 +0000129
Erik Andersene49d5ec2000-02-08 19:58:47 +0000130 doh = (Line **) a;
131 x = *doh;
132 doh = (Line **) b;
133 y = *doh;
John Beppuee512a31999-12-23 00:02:49 +0000134
Erik Andersene49d5ec2000-02-08 19:58:47 +0000135 xint = strtoul(x->data, NULL, 10);
136 yint = strtoul(y->data, NULL, 10);
John Beppuee512a31999-12-23 00:02:49 +0000137
Erik Andersen029011b2000-03-04 21:19:32 +0000138 return APPLY_REVERSE(xint - yint);
John Beppuf3e59041999-12-22 22:24:52 +0000139}
John Beppuc0ca4731999-12-21 20:00:35 +0000140
141
142/* List */
143
John Beppu38efa791999-12-22 00:30:29 +0000144/* */
Erik Andersene49d5ec2000-02-08 19:58:47 +0000145static List *list_init(List * self)
John Beppu38efa791999-12-22 00:30:29 +0000146{
Erik Andersene49d5ec2000-02-08 19:58:47 +0000147 self->len = 0;
148 self->sorted = NULL;
149 self->head = NULL;
150 self->current = NULL;
151 return self;
John Beppu38efa791999-12-22 00:30:29 +0000152}
John Beppuc0ca4731999-12-21 20:00:35 +0000153
John Beppu38efa791999-12-22 00:30:29 +0000154/* for simplicity, the List gains ownership of the line */
Erik Andersene49d5ec2000-02-08 19:58:47 +0000155static List *list_insert(List * self, Line * line)
John Beppu38efa791999-12-22 00:30:29 +0000156{
Erik Andersene49d5ec2000-02-08 19:58:47 +0000157 if (line == NULL) {
158 return NULL;
159 }
John Beppuc0ca4731999-12-21 20:00:35 +0000160
Erik Andersene49d5ec2000-02-08 19:58:47 +0000161 /* first insertion */
162 if (self->head == NULL) {
163 self->head = line;
164 self->current = line;
John Beppuc0ca4731999-12-21 20:00:35 +0000165
John Beppu5a728cf2000-04-17 04:22:09 +0000166 /* all subsequent insertions */
Erik Andersene49d5ec2000-02-08 19:58:47 +0000167 } else {
168 self->current->next = line;
169 self->current = line;
170 }
171 self->len++;
172 return self;
John Beppu38efa791999-12-22 00:30:29 +0000173}
174
John Beppuf3e59041999-12-22 22:24:52 +0000175/* order the list according to compare() */
Erik Andersene49d5ec2000-02-08 19:58:47 +0000176static List *list_sort(List * self, Compare * compare)
John Beppuf3e59041999-12-22 22:24:52 +0000177{
Erik Andersene49d5ec2000-02-08 19:58:47 +0000178 int i;
179 Line *line;
John Beppuf3e59041999-12-22 22:24:52 +0000180
Erik Andersene49d5ec2000-02-08 19:58:47 +0000181 /* mallocate array of Line*s */
182 self->sorted = (Line **) malloc(self->len * sizeof(Line *));
183 if (self->sorted == NULL) {
184 return NULL;
185 }
John Beppuf3e59041999-12-22 22:24:52 +0000186
Erik Andersene49d5ec2000-02-08 19:58:47 +0000187 /* fill array w/ List's contents */
188 i = 0;
189 line = self->head;
190 while (line) {
191 self->sorted[i++] = line;
192 line = line->next;
193 }
John Beppuf3e59041999-12-22 22:24:52 +0000194
Erik Andersene49d5ec2000-02-08 19:58:47 +0000195 /* apply qsort */
196 qsort(self->sorted, self->len, sizeof(Line *), compare);
197 return self;
John Beppuf3e59041999-12-22 22:24:52 +0000198}
John Beppu38efa791999-12-22 00:30:29 +0000199
200/* precondition: list must be sorted */
Erik Andersene49d5ec2000-02-08 19:58:47 +0000201static List *list_writeToFile(List * self, FILE * dst)
John Beppu38efa791999-12-22 00:30:29 +0000202{
Erik Andersene49d5ec2000-02-08 19:58:47 +0000203 int i;
204 Line **line = self->sorted;
John Beppuf3e59041999-12-22 22:24:52 +0000205
Erik Andersene49d5ec2000-02-08 19:58:47 +0000206 if (self->sorted == NULL) {
207 return NULL;
208 }
209 for (i = 0; i < self->len; i++) {
210 fprintf(dst, "%s", line[i]->data);
211 }
212 return self;
John Beppu38efa791999-12-22 00:30:29 +0000213}
214
215/* deallocate */
Erik Andersene49d5ec2000-02-08 19:58:47 +0000216static void list_release(List * self)
John Beppu38efa791999-12-22 00:30:29 +0000217{
Erik Andersene49d5ec2000-02-08 19:58:47 +0000218 Line *i;
219 Line *die;
John Beppu019513a1999-12-22 17:57:31 +0000220
Erik Andersene49d5ec2000-02-08 19:58:47 +0000221 i = self->head;
222 while (i) {
223 die = i;
224 i = die->next;
225 line_release(die);
226 }
John Beppu38efa791999-12-22 00:30:29 +0000227}
John Beppuc0ca4731999-12-21 20:00:35 +0000228
229
John Beppuc0ca4731999-12-21 20:00:35 +0000230
Erik Andersene49d5ec2000-02-08 19:58:47 +0000231int sort_main(int argc, char **argv)
John Beppuc0ca4731999-12-21 20:00:35 +0000232{
Erik Andersene49d5ec2000-02-08 19:58:47 +0000233 int i;
234 char opt;
235 List list;
236 Line *l;
237 Compare *compare;
John Beppuc0ca4731999-12-21 20:00:35 +0000238
Erik Andersene49d5ec2000-02-08 19:58:47 +0000239 /* init */
240 compare = compare_ascii;
241 list_init(&list);
John Beppuc0ca4731999-12-21 20:00:35 +0000242
Erik Andersene49d5ec2000-02-08 19:58:47 +0000243 /* parse argv[] */
244 for (i = 1; i < argc; i++) {
245 if (argv[i][0] == '-') {
246 opt = argv[i][1];
247 switch (opt) {
Erik Andersene49d5ec2000-02-08 19:58:47 +0000248 case 'h':
249 usage(sort_usage);
250 break;
251 case 'n':
Erik Andersen029011b2000-03-04 21:19:32 +0000252 /* numeric comparison */
Erik Andersene49d5ec2000-02-08 19:58:47 +0000253 compare = compare_numeric;
254 break;
Erik Andersen029011b2000-03-04 21:19:32 +0000255#ifdef BB_FEATURE_SORT_REVERSE
Erik Andersene49d5ec2000-02-08 19:58:47 +0000256 case 'r':
257 /* reverse */
Erik Andersen029011b2000-03-04 21:19:32 +0000258 reverse = 1;
Erik Andersene49d5ec2000-02-08 19:58:47 +0000259 break;
Erik Andersen029011b2000-03-04 21:19:32 +0000260#endif
Erik Andersene49d5ec2000-02-08 19:58:47 +0000261 default:
262 fprintf(stderr, "sort: invalid option -- %c\n", opt);
263 usage(sort_usage);
264 }
265 } else {
266 break;
267 }
268 }
269
270 /* this could be factored better */
271
272 /* work w/ stdin */
273 if (i >= argc) {
274 while ((l = line_newFromFile(stdin))) {
275 list_insert(&list, l);
276 }
277 list_sort(&list, compare);
278 list_writeToFile(&list, stdout);
279 list_release(&list);
280
281 /* work w/ what's left in argv[] */
John Beppuc0ca4731999-12-21 20:00:35 +0000282 } else {
Erik Andersene49d5ec2000-02-08 19:58:47 +0000283 FILE *src;
284
285 for (; i < argc; i++) {
286 src = fopen(argv[i], "r");
287 if (src == NULL) {
288 break;
289 }
290 while ((l = line_newFromFile(src))) {
291 list_insert(&list, l);
292 }
293 fclose(src);
294 }
295 list_sort(&list, compare);
296 list_writeToFile(&list, stdout);
297 list_release(&list);
John Beppuc0ca4731999-12-21 20:00:35 +0000298 }
John Beppuc0ca4731999-12-21 20:00:35 +0000299
Erik Andersene49d5ec2000-02-08 19:58:47 +0000300 exit(0);
John Beppuc0ca4731999-12-21 20:00:35 +0000301}
302
John Beppu5a728cf2000-04-17 04:22:09 +0000303/* $Id: sort.c,v 1.15 2000/04/17 04:22:09 beppu Exp $ */