Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 1 | /* vi: set sw=4 ts=4: */ |
John Beppu | c0ca473 | 1999-12-21 20:00:35 +0000 | [diff] [blame] | 2 | /* |
John Beppu | 568cb7b | 1999-12-22 23:02:12 +0000 | [diff] [blame] | 3 | * Mini sort implementation for busybox |
John Beppu | c0ca473 | 1999-12-21 20:00:35 +0000 | [diff] [blame] | 4 | * |
| 5 | * |
| 6 | * Copyright (C) 1999 by Lineo, inc. |
| 7 | * 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 Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 32 | static const char sort_usage[] = "sort [OPTION]... [FILE]...\n\n"; |
John Beppu | c0ca473 | 1999-12-21 20:00:35 +0000 | [diff] [blame] | 33 | |
John Beppu | f3e5904 | 1999-12-22 22:24:52 +0000 | [diff] [blame] | 34 | /* typedefs _______________________________________________________________ */ |
John Beppu | c0ca473 | 1999-12-21 20:00:35 +0000 | [diff] [blame] | 35 | |
| 36 | /* line node */ |
John Beppu | f3e5904 | 1999-12-22 22:24:52 +0000 | [diff] [blame] | 37 | typedef struct Line { |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 38 | char *data; /* line data */ |
| 39 | struct Line *next; /* pointer to next line node */ |
John Beppu | c0ca473 | 1999-12-21 20:00:35 +0000 | [diff] [blame] | 40 | } Line; |
| 41 | |
| 42 | /* singly-linked list of lines */ |
| 43 | typedef struct { |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 44 | int len; /* number of Lines */ |
| 45 | Line **sorted; /* array fed to qsort */ |
John Beppu | 38efa79 | 1999-12-22 00:30:29 +0000 | [diff] [blame] | 46 | |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 47 | Line *head; /* head of List */ |
| 48 | Line *current; /* current Line */ |
John Beppu | c0ca473 | 1999-12-21 20:00:35 +0000 | [diff] [blame] | 49 | } List; |
| 50 | |
John Beppu | f3e5904 | 1999-12-22 22:24:52 +0000 | [diff] [blame] | 51 | /* comparison function */ |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 52 | typedef int (Compare) (const void *, const void *); |
John Beppu | f3e5904 | 1999-12-22 22:24:52 +0000 | [diff] [blame] | 53 | |
John Beppu | c0ca473 | 1999-12-21 20:00:35 +0000 | [diff] [blame] | 54 | |
John Beppu | 38efa79 | 1999-12-22 00:30:29 +0000 | [diff] [blame] | 55 | /* methods ________________________________________________________________ */ |
John Beppu | c0ca473 | 1999-12-21 20:00:35 +0000 | [diff] [blame] | 56 | |
| 57 | static const int max = 1024; |
| 58 | |
John Beppu | 38efa79 | 1999-12-22 00:30:29 +0000 | [diff] [blame] | 59 | /* mallocate Line */ |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 60 | static Line *line_alloc() |
John Beppu | c0ca473 | 1999-12-21 20:00:35 +0000 | [diff] [blame] | 61 | { |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 62 | Line *self; |
| 63 | |
| 64 | self = malloc(1 * sizeof(Line)); |
| 65 | return self; |
John Beppu | 38efa79 | 1999-12-22 00:30:29 +0000 | [diff] [blame] | 66 | } |
| 67 | |
| 68 | /* Initialize Line with string */ |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 69 | static Line *line_init(Line * self, const char *string) |
John Beppu | 38efa79 | 1999-12-22 00:30:29 +0000 | [diff] [blame] | 70 | { |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 71 | self->data = malloc((strlen(string) + 1) * sizeof(char)); |
| 72 | |
| 73 | if (self->data == NULL) { |
| 74 | return NULL; |
| 75 | } |
| 76 | strcpy(self->data, string); |
| 77 | self->next = NULL; |
| 78 | return self; |
John Beppu | 38efa79 | 1999-12-22 00:30:29 +0000 | [diff] [blame] | 79 | } |
| 80 | |
| 81 | /* Construct Line from FILE* */ |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 82 | static Line *line_newFromFile(FILE * src) |
John Beppu | 38efa79 | 1999-12-22 00:30:29 +0000 | [diff] [blame] | 83 | { |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 84 | char buffer[max]; |
| 85 | Line *self; |
John Beppu | 38efa79 | 1999-12-22 00:30:29 +0000 | [diff] [blame] | 86 | |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 87 | if (fgets(buffer, max, src)) { |
| 88 | self = line_alloc(); |
| 89 | if (self == NULL) { |
| 90 | return NULL; |
| 91 | } |
| 92 | line_init(self, buffer); |
| 93 | return self; |
| 94 | } |
| 95 | return NULL; |
John Beppu | c0ca473 | 1999-12-21 20:00:35 +0000 | [diff] [blame] | 96 | } |
| 97 | |
John Beppu | 019513a | 1999-12-22 17:57:31 +0000 | [diff] [blame] | 98 | /* Line destructor */ |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 99 | static Line *line_release(Line * self) |
John Beppu | 019513a | 1999-12-22 17:57:31 +0000 | [diff] [blame] | 100 | { |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 101 | if (self->data) { |
| 102 | free(self->data); |
| 103 | free(self); |
| 104 | } |
| 105 | return self; |
John Beppu | 019513a | 1999-12-22 17:57:31 +0000 | [diff] [blame] | 106 | } |
| 107 | |
John Beppu | c0ca473 | 1999-12-21 20:00:35 +0000 | [diff] [blame] | 108 | |
| 109 | /* Comparison */ |
| 110 | |
John Beppu | 568cb7b | 1999-12-22 23:02:12 +0000 | [diff] [blame] | 111 | /* ascii order */ |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 112 | static int compare_ascii(const void *a, const void *b) |
John Beppu | f3e5904 | 1999-12-22 22:24:52 +0000 | [diff] [blame] | 113 | { |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 114 | Line **doh; |
| 115 | Line *x, *y; |
John Beppu | 568cb7b | 1999-12-22 23:02:12 +0000 | [diff] [blame] | 116 | |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 117 | doh = (Line **) a; |
| 118 | x = *doh; |
| 119 | doh = (Line **) b; |
| 120 | y = *doh; |
John Beppu | 568cb7b | 1999-12-22 23:02:12 +0000 | [diff] [blame] | 121 | |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 122 | // fprintf(stdout, "> %p: %s< %p: %s", x, x->data, y, y->data); |
| 123 | return strcmp(x->data, y->data); |
John Beppu | f3e5904 | 1999-12-22 22:24:52 +0000 | [diff] [blame] | 124 | } |
John Beppu | c0ca473 | 1999-12-21 20:00:35 +0000 | [diff] [blame] | 125 | |
John Beppu | 568cb7b | 1999-12-22 23:02:12 +0000 | [diff] [blame] | 126 | /* numeric order */ |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 127 | static int compare_numeric(const void *a, const void *b) |
John Beppu | f3e5904 | 1999-12-22 22:24:52 +0000 | [diff] [blame] | 128 | { |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 129 | Line **doh; |
| 130 | Line *x, *y; |
| 131 | int xint, yint; |
John Beppu | ee512a3 | 1999-12-23 00:02:49 +0000 | [diff] [blame] | 132 | |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 133 | doh = (Line **) a; |
| 134 | x = *doh; |
| 135 | doh = (Line **) b; |
| 136 | y = *doh; |
John Beppu | ee512a3 | 1999-12-23 00:02:49 +0000 | [diff] [blame] | 137 | |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 138 | xint = strtoul(x->data, NULL, 10); |
| 139 | yint = strtoul(y->data, NULL, 10); |
John Beppu | ee512a3 | 1999-12-23 00:02:49 +0000 | [diff] [blame] | 140 | |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 141 | return (xint - yint); |
John Beppu | f3e5904 | 1999-12-22 22:24:52 +0000 | [diff] [blame] | 142 | } |
John Beppu | c0ca473 | 1999-12-21 20:00:35 +0000 | [diff] [blame] | 143 | |
| 144 | |
| 145 | /* List */ |
| 146 | |
John Beppu | 38efa79 | 1999-12-22 00:30:29 +0000 | [diff] [blame] | 147 | /* */ |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 148 | static List *list_init(List * self) |
John Beppu | 38efa79 | 1999-12-22 00:30:29 +0000 | [diff] [blame] | 149 | { |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 150 | self->len = 0; |
| 151 | self->sorted = NULL; |
| 152 | self->head = NULL; |
| 153 | self->current = NULL; |
| 154 | return self; |
John Beppu | 38efa79 | 1999-12-22 00:30:29 +0000 | [diff] [blame] | 155 | } |
John Beppu | c0ca473 | 1999-12-21 20:00:35 +0000 | [diff] [blame] | 156 | |
John Beppu | 38efa79 | 1999-12-22 00:30:29 +0000 | [diff] [blame] | 157 | /* for simplicity, the List gains ownership of the line */ |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 158 | static List *list_insert(List * self, Line * line) |
John Beppu | 38efa79 | 1999-12-22 00:30:29 +0000 | [diff] [blame] | 159 | { |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 160 | if (line == NULL) { |
| 161 | return NULL; |
| 162 | } |
John Beppu | c0ca473 | 1999-12-21 20:00:35 +0000 | [diff] [blame] | 163 | |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 164 | /* first insertion */ |
| 165 | if (self->head == NULL) { |
| 166 | self->head = line; |
| 167 | self->current = line; |
John Beppu | c0ca473 | 1999-12-21 20:00:35 +0000 | [diff] [blame] | 168 | |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 169 | /* all subsequent insertions */ |
| 170 | } else { |
| 171 | self->current->next = line; |
| 172 | self->current = line; |
| 173 | } |
| 174 | self->len++; |
| 175 | return self; |
John Beppu | 38efa79 | 1999-12-22 00:30:29 +0000 | [diff] [blame] | 176 | } |
| 177 | |
John Beppu | f3e5904 | 1999-12-22 22:24:52 +0000 | [diff] [blame] | 178 | /* order the list according to compare() */ |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 179 | static List *list_sort(List * self, Compare * compare) |
John Beppu | f3e5904 | 1999-12-22 22:24:52 +0000 | [diff] [blame] | 180 | { |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 181 | int i; |
| 182 | Line *line; |
John Beppu | f3e5904 | 1999-12-22 22:24:52 +0000 | [diff] [blame] | 183 | |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 184 | /* mallocate array of Line*s */ |
| 185 | self->sorted = (Line **) malloc(self->len * sizeof(Line *)); |
| 186 | if (self->sorted == NULL) { |
| 187 | return NULL; |
| 188 | } |
John Beppu | f3e5904 | 1999-12-22 22:24:52 +0000 | [diff] [blame] | 189 | |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 190 | /* fill array w/ List's contents */ |
| 191 | i = 0; |
| 192 | line = self->head; |
| 193 | while (line) { |
| 194 | self->sorted[i++] = line; |
| 195 | line = line->next; |
| 196 | } |
John Beppu | f3e5904 | 1999-12-22 22:24:52 +0000 | [diff] [blame] | 197 | |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 198 | /* apply qsort */ |
| 199 | qsort(self->sorted, self->len, sizeof(Line *), compare); |
| 200 | return self; |
John Beppu | f3e5904 | 1999-12-22 22:24:52 +0000 | [diff] [blame] | 201 | } |
John Beppu | 38efa79 | 1999-12-22 00:30:29 +0000 | [diff] [blame] | 202 | |
| 203 | /* precondition: list must be sorted */ |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 204 | static List *list_writeToFile(List * self, FILE * dst) |
John Beppu | 38efa79 | 1999-12-22 00:30:29 +0000 | [diff] [blame] | 205 | { |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 206 | int i; |
| 207 | Line **line = self->sorted; |
John Beppu | f3e5904 | 1999-12-22 22:24:52 +0000 | [diff] [blame] | 208 | |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 209 | if (self->sorted == NULL) { |
| 210 | return NULL; |
| 211 | } |
| 212 | for (i = 0; i < self->len; i++) { |
| 213 | fprintf(dst, "%s", line[i]->data); |
| 214 | } |
| 215 | return self; |
John Beppu | 38efa79 | 1999-12-22 00:30:29 +0000 | [diff] [blame] | 216 | } |
| 217 | |
| 218 | /* deallocate */ |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 219 | static void list_release(List * self) |
John Beppu | 38efa79 | 1999-12-22 00:30:29 +0000 | [diff] [blame] | 220 | { |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 221 | Line *i; |
| 222 | Line *die; |
John Beppu | 019513a | 1999-12-22 17:57:31 +0000 | [diff] [blame] | 223 | |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 224 | i = self->head; |
| 225 | while (i) { |
| 226 | die = i; |
| 227 | i = die->next; |
| 228 | line_release(die); |
| 229 | } |
John Beppu | 38efa79 | 1999-12-22 00:30:29 +0000 | [diff] [blame] | 230 | } |
John Beppu | c0ca473 | 1999-12-21 20:00:35 +0000 | [diff] [blame] | 231 | |
| 232 | |
| 233 | /* |
| 234 | * I need a list |
| 235 | * to insert lines into |
| 236 | * then I need to sort this list |
| 237 | * and finally print it |
| 238 | */ |
| 239 | |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 240 | int sort_main(int argc, char **argv) |
John Beppu | c0ca473 | 1999-12-21 20:00:35 +0000 | [diff] [blame] | 241 | { |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 242 | int i; |
| 243 | char opt; |
| 244 | List list; |
| 245 | Line *l; |
| 246 | Compare *compare; |
John Beppu | c0ca473 | 1999-12-21 20:00:35 +0000 | [diff] [blame] | 247 | |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 248 | /* init */ |
| 249 | compare = compare_ascii; |
| 250 | list_init(&list); |
John Beppu | c0ca473 | 1999-12-21 20:00:35 +0000 | [diff] [blame] | 251 | |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 252 | /* parse argv[] */ |
| 253 | for (i = 1; i < argc; i++) { |
| 254 | if (argv[i][0] == '-') { |
| 255 | opt = argv[i][1]; |
| 256 | switch (opt) { |
| 257 | case 'g': |
| 258 | /* what's the diff between -g && -n? */ |
| 259 | compare = compare_numeric; |
| 260 | break; |
| 261 | case 'h': |
| 262 | usage(sort_usage); |
| 263 | break; |
| 264 | case 'n': |
| 265 | /* what's the diff between -g && -n? */ |
| 266 | compare = compare_numeric; |
| 267 | break; |
| 268 | case 'r': |
| 269 | /* reverse */ |
| 270 | break; |
| 271 | default: |
| 272 | fprintf(stderr, "sort: invalid option -- %c\n", opt); |
| 273 | usage(sort_usage); |
| 274 | } |
| 275 | } else { |
| 276 | break; |
| 277 | } |
| 278 | } |
| 279 | |
| 280 | /* this could be factored better */ |
| 281 | |
| 282 | /* work w/ stdin */ |
| 283 | if (i >= argc) { |
| 284 | while ((l = line_newFromFile(stdin))) { |
| 285 | list_insert(&list, l); |
| 286 | } |
| 287 | list_sort(&list, compare); |
| 288 | list_writeToFile(&list, stdout); |
| 289 | list_release(&list); |
| 290 | |
| 291 | /* work w/ what's left in argv[] */ |
John Beppu | c0ca473 | 1999-12-21 20:00:35 +0000 | [diff] [blame] | 292 | } else { |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 293 | FILE *src; |
| 294 | |
| 295 | for (; i < argc; i++) { |
| 296 | src = fopen(argv[i], "r"); |
| 297 | if (src == NULL) { |
| 298 | break; |
| 299 | } |
| 300 | while ((l = line_newFromFile(src))) { |
| 301 | list_insert(&list, l); |
| 302 | } |
| 303 | fclose(src); |
| 304 | } |
| 305 | list_sort(&list, compare); |
| 306 | list_writeToFile(&list, stdout); |
| 307 | list_release(&list); |
John Beppu | c0ca473 | 1999-12-21 20:00:35 +0000 | [diff] [blame] | 308 | } |
John Beppu | c0ca473 | 1999-12-21 20:00:35 +0000 | [diff] [blame] | 309 | |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 310 | exit(0); |
John Beppu | c0ca473 | 1999-12-21 20:00:35 +0000 | [diff] [blame] | 311 | } |
| 312 | |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 313 | /* $Id: sort.c,v 1.11 2000/02/08 19:58:47 erik Exp $ */ |