blob: b0bf6e49478f2e1b55a4e9b081c9c2e91efdb78e [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
Eric Andersen3570a342000-09-25 21:45:58 +000025#include "busybox.h"
John Beppuc0ca4731999-12-21 20:00:35 +000026#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 +000032#ifdef BB_FEATURE_SORT_REVERSE
33#define APPLY_REVERSE(x) (reverse ? -(x) : (x))
34static int reverse = 0;
35#else
36#define APPLY_REVERSE(x) (x)
37#endif
John Beppuc0ca4731999-12-21 20:00:35 +000038
John Beppuf3e59041999-12-22 22:24:52 +000039/* typedefs _______________________________________________________________ */
John Beppuc0ca4731999-12-21 20:00:35 +000040
41/* line node */
John Beppuf3e59041999-12-22 22:24:52 +000042typedef struct Line {
Erik Andersene49d5ec2000-02-08 19:58:47 +000043 char *data; /* line data */
44 struct Line *next; /* pointer to next line node */
John Beppuc0ca4731999-12-21 20:00:35 +000045} Line;
46
47/* singly-linked list of lines */
48typedef struct {
Erik Andersene49d5ec2000-02-08 19:58:47 +000049 int len; /* number of Lines */
50 Line **sorted; /* array fed to qsort */
Erik Andersene49d5ec2000-02-08 19:58:47 +000051 Line *head; /* head of List */
52 Line *current; /* current Line */
John Beppuc0ca4731999-12-21 20:00:35 +000053} List;
54
John Beppuf3e59041999-12-22 22:24:52 +000055/* comparison function */
Erik Andersene49d5ec2000-02-08 19:58:47 +000056typedef int (Compare) (const void *, const void *);
John Beppuf3e59041999-12-22 22:24:52 +000057
John Beppuc0ca4731999-12-21 20:00:35 +000058
John Beppu38efa791999-12-22 00:30:29 +000059/* methods ________________________________________________________________ */
John Beppuc0ca4731999-12-21 20:00:35 +000060
61static const int max = 1024;
62
John Beppu38efa791999-12-22 00:30:29 +000063/* mallocate Line */
Erik Andersene49d5ec2000-02-08 19:58:47 +000064static Line *line_alloc()
John Beppuc0ca4731999-12-21 20:00:35 +000065{
Erik Andersene49d5ec2000-02-08 19:58:47 +000066 Line *self;
Matt Kraai322ae932000-09-13 02:46:14 +000067 self = xmalloc(1 * sizeof(Line));
Erik Andersene49d5ec2000-02-08 19:58:47 +000068 return self;
John Beppu38efa791999-12-22 00:30:29 +000069}
70
John Beppu38efa791999-12-22 00:30:29 +000071/* Construct Line from FILE* */
Erik Andersene49d5ec2000-02-08 19:58:47 +000072static Line *line_newFromFile(FILE * src)
John Beppu38efa791999-12-22 00:30:29 +000073{
Erik Andersene49d5ec2000-02-08 19:58:47 +000074 Line *self;
John Beppu5a728cf2000-04-17 04:22:09 +000075 char *cstring = NULL;
John Beppu38efa791999-12-22 00:30:29 +000076
Mark Whitley1ca41772000-06-28 22:15:26 +000077 if ((cstring = get_line_from_file(src))) {
Erik Andersene49d5ec2000-02-08 19:58:47 +000078 self = line_alloc();
John Beppu5a728cf2000-04-17 04:22:09 +000079 self->data = cstring;
80 self->next = NULL;
Erik Andersene49d5ec2000-02-08 19:58:47 +000081 return self;
82 }
83 return NULL;
John Beppuc0ca4731999-12-21 20:00:35 +000084}
85
John Beppu019513a1999-12-22 17:57:31 +000086/* Line destructor */
Erik Andersene49d5ec2000-02-08 19:58:47 +000087static Line *line_release(Line * self)
John Beppu019513a1999-12-22 17:57:31 +000088{
Erik Andersene49d5ec2000-02-08 19:58:47 +000089 if (self->data) {
90 free(self->data);
91 free(self);
92 }
93 return self;
John Beppu019513a1999-12-22 17:57:31 +000094}
95
John Beppuc0ca4731999-12-21 20:00:35 +000096
97/* Comparison */
98
John Beppu568cb7b1999-12-22 23:02:12 +000099/* ascii order */
Erik Andersene49d5ec2000-02-08 19:58:47 +0000100static int compare_ascii(const void *a, const void *b)
John Beppuf3e59041999-12-22 22:24:52 +0000101{
John Beppu8d369e92000-09-28 17:49:59 +0000102 Line **val;
Erik Andersene49d5ec2000-02-08 19:58:47 +0000103 Line *x, *y;
John Beppu568cb7b1999-12-22 23:02:12 +0000104
John Beppu8d369e92000-09-28 17:49:59 +0000105 val = (Line **) a;
106 x = *val;
107 val = (Line **) b;
108 y = *val;
John Beppu568cb7b1999-12-22 23:02:12 +0000109
Erik Andersene49d5ec2000-02-08 19:58:47 +0000110 // fprintf(stdout, "> %p: %s< %p: %s", x, x->data, y, y->data);
Erik Andersen029011b2000-03-04 21:19:32 +0000111 return APPLY_REVERSE(strcmp(x->data, y->data));
John Beppuf3e59041999-12-22 22:24:52 +0000112}
John Beppuc0ca4731999-12-21 20:00:35 +0000113
John Beppu568cb7b1999-12-22 23:02:12 +0000114/* numeric order */
Erik Andersene49d5ec2000-02-08 19:58:47 +0000115static int compare_numeric(const void *a, const void *b)
John Beppuf3e59041999-12-22 22:24:52 +0000116{
John Beppu8d369e92000-09-28 17:49:59 +0000117 Line **val;
Erik Andersene49d5ec2000-02-08 19:58:47 +0000118 Line *x, *y;
119 int xint, yint;
John Beppuee512a31999-12-23 00:02:49 +0000120
John Beppu8d369e92000-09-28 17:49:59 +0000121 val = (Line **) a;
122 x = *val;
123 val = (Line **) b;
124 y = *val;
John Beppuee512a31999-12-23 00:02:49 +0000125
Erik Andersene49d5ec2000-02-08 19:58:47 +0000126 xint = strtoul(x->data, NULL, 10);
127 yint = strtoul(y->data, NULL, 10);
John Beppuee512a31999-12-23 00:02:49 +0000128
Erik Andersen029011b2000-03-04 21:19:32 +0000129 return APPLY_REVERSE(xint - yint);
John Beppuf3e59041999-12-22 22:24:52 +0000130}
John Beppuc0ca4731999-12-21 20:00:35 +0000131
132
133/* List */
134
John Beppu38efa791999-12-22 00:30:29 +0000135/* */
Erik Andersene49d5ec2000-02-08 19:58:47 +0000136static List *list_init(List * self)
John Beppu38efa791999-12-22 00:30:29 +0000137{
Erik Andersene49d5ec2000-02-08 19:58:47 +0000138 self->len = 0;
139 self->sorted = NULL;
140 self->head = NULL;
141 self->current = NULL;
142 return self;
John Beppu38efa791999-12-22 00:30:29 +0000143}
John Beppuc0ca4731999-12-21 20:00:35 +0000144
John Beppu38efa791999-12-22 00:30:29 +0000145/* for simplicity, the List gains ownership of the line */
Erik Andersene49d5ec2000-02-08 19:58:47 +0000146static List *list_insert(List * self, Line * line)
John Beppu38efa791999-12-22 00:30:29 +0000147{
Erik Andersene49d5ec2000-02-08 19:58:47 +0000148 if (line == NULL) {
149 return NULL;
150 }
John Beppuc0ca4731999-12-21 20:00:35 +0000151
Erik Andersene49d5ec2000-02-08 19:58:47 +0000152 /* first insertion */
153 if (self->head == NULL) {
154 self->head = line;
155 self->current = line;
John Beppuc0ca4731999-12-21 20:00:35 +0000156
John Beppu5a728cf2000-04-17 04:22:09 +0000157 /* all subsequent insertions */
Erik Andersene49d5ec2000-02-08 19:58:47 +0000158 } else {
159 self->current->next = line;
160 self->current = line;
161 }
162 self->len++;
163 return self;
John Beppu38efa791999-12-22 00:30:29 +0000164}
165
John Beppuf3e59041999-12-22 22:24:52 +0000166/* order the list according to compare() */
Erik Andersene49d5ec2000-02-08 19:58:47 +0000167static List *list_sort(List * self, Compare * compare)
John Beppuf3e59041999-12-22 22:24:52 +0000168{
Erik Andersene49d5ec2000-02-08 19:58:47 +0000169 int i;
170 Line *line;
John Beppuf3e59041999-12-22 22:24:52 +0000171
Erik Andersene49d5ec2000-02-08 19:58:47 +0000172 /* mallocate array of Line*s */
Matt Kraai322ae932000-09-13 02:46:14 +0000173 self->sorted = (Line **) xmalloc(self->len * sizeof(Line *));
John Beppuf3e59041999-12-22 22:24:52 +0000174
Erik Andersene49d5ec2000-02-08 19:58:47 +0000175 /* fill array w/ List's contents */
176 i = 0;
177 line = self->head;
178 while (line) {
179 self->sorted[i++] = line;
180 line = line->next;
181 }
John Beppuf3e59041999-12-22 22:24:52 +0000182
Erik Andersene49d5ec2000-02-08 19:58:47 +0000183 /* apply qsort */
184 qsort(self->sorted, self->len, sizeof(Line *), compare);
185 return self;
John Beppuf3e59041999-12-22 22:24:52 +0000186}
John Beppu38efa791999-12-22 00:30:29 +0000187
188/* precondition: list must be sorted */
Erik Andersene49d5ec2000-02-08 19:58:47 +0000189static List *list_writeToFile(List * self, FILE * dst)
John Beppu38efa791999-12-22 00:30:29 +0000190{
Erik Andersene49d5ec2000-02-08 19:58:47 +0000191 int i;
192 Line **line = self->sorted;
John Beppuf3e59041999-12-22 22:24:52 +0000193
Erik Andersene49d5ec2000-02-08 19:58:47 +0000194 if (self->sorted == NULL) {
195 return NULL;
196 }
197 for (i = 0; i < self->len; i++) {
198 fprintf(dst, "%s", line[i]->data);
199 }
200 return self;
John Beppu38efa791999-12-22 00:30:29 +0000201}
202
203/* deallocate */
Erik Andersene49d5ec2000-02-08 19:58:47 +0000204static void list_release(List * self)
John Beppu38efa791999-12-22 00:30:29 +0000205{
Erik Andersene49d5ec2000-02-08 19:58:47 +0000206 Line *i;
207 Line *die;
John Beppu019513a1999-12-22 17:57:31 +0000208
Erik Andersene49d5ec2000-02-08 19:58:47 +0000209 i = self->head;
210 while (i) {
211 die = i;
212 i = die->next;
213 line_release(die);
214 }
John Beppu38efa791999-12-22 00:30:29 +0000215}
John Beppuc0ca4731999-12-21 20:00:35 +0000216
217
John Beppuc0ca4731999-12-21 20:00:35 +0000218
Erik Andersene49d5ec2000-02-08 19:58:47 +0000219int sort_main(int argc, char **argv)
John Beppuc0ca4731999-12-21 20:00:35 +0000220{
Erik Andersene49d5ec2000-02-08 19:58:47 +0000221 int i;
222 char opt;
223 List list;
224 Line *l;
225 Compare *compare;
John Beppuc0ca4731999-12-21 20:00:35 +0000226
Erik Andersene49d5ec2000-02-08 19:58:47 +0000227 /* init */
228 compare = compare_ascii;
229 list_init(&list);
John Beppuc0ca4731999-12-21 20:00:35 +0000230
Erik Andersene49d5ec2000-02-08 19:58:47 +0000231 /* parse argv[] */
232 for (i = 1; i < argc; i++) {
233 if (argv[i][0] == '-') {
234 opt = argv[i][1];
235 switch (opt) {
Erik Andersene49d5ec2000-02-08 19:58:47 +0000236 case 'h':
237 usage(sort_usage);
238 break;
239 case 'n':
Erik Andersen029011b2000-03-04 21:19:32 +0000240 /* numeric comparison */
Erik Andersene49d5ec2000-02-08 19:58:47 +0000241 compare = compare_numeric;
242 break;
Erik Andersen029011b2000-03-04 21:19:32 +0000243#ifdef BB_FEATURE_SORT_REVERSE
Erik Andersene49d5ec2000-02-08 19:58:47 +0000244 case 'r':
245 /* reverse */
Erik Andersen029011b2000-03-04 21:19:32 +0000246 reverse = 1;
Erik Andersene49d5ec2000-02-08 19:58:47 +0000247 break;
Erik Andersen029011b2000-03-04 21:19:32 +0000248#endif
Erik Andersene49d5ec2000-02-08 19:58:47 +0000249 default:
Mark Whitleyf57c9442000-12-07 19:56:48 +0000250 error_msg("invalid option -- %c\n", opt);
Erik Andersene49d5ec2000-02-08 19:58:47 +0000251 usage(sort_usage);
252 }
253 } else {
254 break;
255 }
256 }
257
Erik Andersene49d5ec2000-02-08 19:58:47 +0000258 if (i >= argc) {
John Beppu8d369e92000-09-28 17:49:59 +0000259
260 /* work w/ stdin */
Erik Andersene49d5ec2000-02-08 19:58:47 +0000261 while ((l = line_newFromFile(stdin))) {
262 list_insert(&list, l);
263 }
John Beppu8d369e92000-09-28 17:49:59 +0000264
265 } else {
Erik Andersene49d5ec2000-02-08 19:58:47 +0000266
267 /* work w/ what's left in argv[] */
Erik Andersene49d5ec2000-02-08 19:58:47 +0000268 FILE *src;
269
270 for (; i < argc; i++) {
271 src = fopen(argv[i], "r");
272 if (src == NULL) {
273 break;
274 }
275 while ((l = line_newFromFile(src))) {
276 list_insert(&list, l);
277 }
278 fclose(src);
279 }
John Beppu8d369e92000-09-28 17:49:59 +0000280
John Beppuc0ca4731999-12-21 20:00:35 +0000281 }
John Beppu8d369e92000-09-28 17:49:59 +0000282 list_sort(&list, compare);
283 list_writeToFile(&list, stdout);
284 list_release(&list);
John Beppuc0ca4731999-12-21 20:00:35 +0000285
Eric Andersenb6106152000-06-19 17:25:40 +0000286 return(0);
John Beppuc0ca4731999-12-21 20:00:35 +0000287}
288
Mark Whitleyf57c9442000-12-07 19:56:48 +0000289/* $Id: sort.c,v 1.24 2000/12/07 19:56:48 markw Exp $ */