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 | * |
Erik Andersen | 61677fe | 2000-04-13 01:18:56 +0000 | [diff] [blame] | 6 | * Copyright (C) 1999,2000 by Lineo, inc. |
John Beppu | c0ca473 | 1999-12-21 20:00:35 +0000 | [diff] [blame] | 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 | 029011b | 2000-03-04 21:19:32 +0000 | [diff] [blame] | 32 | static const char sort_usage[] = "sort [-n]" |
| 33 | #ifdef BB_FEATURE_SORT_REVERSE |
| 34 | " [-r]" |
| 35 | #endif |
Erik Andersen | 5e1189e | 2000-04-15 16:34:54 +0000 | [diff] [blame] | 36 | " [FILE]...\n\nSorts lines of text in the specified files\n"; |
Erik Andersen | 029011b | 2000-03-04 21:19:32 +0000 | [diff] [blame] | 37 | |
| 38 | #ifdef BB_FEATURE_SORT_REVERSE |
| 39 | #define APPLY_REVERSE(x) (reverse ? -(x) : (x)) |
| 40 | static int reverse = 0; |
| 41 | #else |
| 42 | #define APPLY_REVERSE(x) (x) |
| 43 | #endif |
John Beppu | c0ca473 | 1999-12-21 20:00:35 +0000 | [diff] [blame] | 44 | |
John Beppu | f3e5904 | 1999-12-22 22:24:52 +0000 | [diff] [blame] | 45 | /* typedefs _______________________________________________________________ */ |
John Beppu | c0ca473 | 1999-12-21 20:00:35 +0000 | [diff] [blame] | 46 | |
| 47 | /* line node */ |
John Beppu | f3e5904 | 1999-12-22 22:24:52 +0000 | [diff] [blame] | 48 | typedef struct Line { |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 49 | char *data; /* line data */ |
| 50 | struct Line *next; /* pointer to next line node */ |
John Beppu | c0ca473 | 1999-12-21 20:00:35 +0000 | [diff] [blame] | 51 | } Line; |
| 52 | |
| 53 | /* singly-linked list of lines */ |
| 54 | typedef struct { |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 55 | int len; /* number of Lines */ |
| 56 | Line **sorted; /* array fed to qsort */ |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 57 | Line *head; /* head of List */ |
| 58 | Line *current; /* current Line */ |
John Beppu | c0ca473 | 1999-12-21 20:00:35 +0000 | [diff] [blame] | 59 | } List; |
| 60 | |
John Beppu | f3e5904 | 1999-12-22 22:24:52 +0000 | [diff] [blame] | 61 | /* comparison function */ |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 62 | typedef int (Compare) (const void *, const void *); |
John Beppu | f3e5904 | 1999-12-22 22:24:52 +0000 | [diff] [blame] | 63 | |
John Beppu | c0ca473 | 1999-12-21 20:00:35 +0000 | [diff] [blame] | 64 | |
John Beppu | 38efa79 | 1999-12-22 00:30:29 +0000 | [diff] [blame] | 65 | /* methods ________________________________________________________________ */ |
John Beppu | c0ca473 | 1999-12-21 20:00:35 +0000 | [diff] [blame] | 66 | |
| 67 | static const int max = 1024; |
| 68 | |
John Beppu | 38efa79 | 1999-12-22 00:30:29 +0000 | [diff] [blame] | 69 | /* mallocate Line */ |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 70 | static Line *line_alloc() |
John Beppu | c0ca473 | 1999-12-21 20:00:35 +0000 | [diff] [blame] | 71 | { |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 72 | Line *self; |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 73 | self = malloc(1 * sizeof(Line)); |
| 74 | return self; |
John Beppu | 38efa79 | 1999-12-22 00:30:29 +0000 | [diff] [blame] | 75 | } |
| 76 | |
John Beppu | 38efa79 | 1999-12-22 00:30:29 +0000 | [diff] [blame] | 77 | /* Construct Line from FILE* */ |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 78 | static Line *line_newFromFile(FILE * src) |
John Beppu | 38efa79 | 1999-12-22 00:30:29 +0000 | [diff] [blame] | 79 | { |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 80 | Line *self; |
John Beppu | 5a728cf | 2000-04-17 04:22:09 +0000 | [diff] [blame] | 81 | char *cstring = NULL; |
John Beppu | 38efa79 | 1999-12-22 00:30:29 +0000 | [diff] [blame] | 82 | |
John Beppu | 5a728cf | 2000-04-17 04:22:09 +0000 | [diff] [blame] | 83 | if ((cstring = cstring_lineFromFile(src))) { |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 84 | self = line_alloc(); |
| 85 | if (self == NULL) { |
| 86 | return NULL; |
| 87 | } |
John Beppu | 5a728cf | 2000-04-17 04:22:09 +0000 | [diff] [blame] | 88 | self->data = cstring; |
| 89 | self->next = NULL; |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 90 | return self; |
| 91 | } |
| 92 | return NULL; |
John Beppu | c0ca473 | 1999-12-21 20:00:35 +0000 | [diff] [blame] | 93 | } |
| 94 | |
John Beppu | 019513a | 1999-12-22 17:57:31 +0000 | [diff] [blame] | 95 | /* Line destructor */ |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 96 | static Line *line_release(Line * self) |
John Beppu | 019513a | 1999-12-22 17:57:31 +0000 | [diff] [blame] | 97 | { |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 98 | if (self->data) { |
| 99 | free(self->data); |
| 100 | free(self); |
| 101 | } |
| 102 | return self; |
John Beppu | 019513a | 1999-12-22 17:57:31 +0000 | [diff] [blame] | 103 | } |
| 104 | |
John Beppu | c0ca473 | 1999-12-21 20:00:35 +0000 | [diff] [blame] | 105 | |
| 106 | /* Comparison */ |
| 107 | |
John Beppu | 568cb7b | 1999-12-22 23:02:12 +0000 | [diff] [blame] | 108 | /* ascii order */ |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 109 | static int compare_ascii(const void *a, const void *b) |
John Beppu | f3e5904 | 1999-12-22 22:24:52 +0000 | [diff] [blame] | 110 | { |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 111 | Line **doh; |
| 112 | Line *x, *y; |
John Beppu | 568cb7b | 1999-12-22 23:02:12 +0000 | [diff] [blame] | 113 | |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 114 | doh = (Line **) a; |
| 115 | x = *doh; |
| 116 | doh = (Line **) b; |
| 117 | y = *doh; |
John Beppu | 568cb7b | 1999-12-22 23:02:12 +0000 | [diff] [blame] | 118 | |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 119 | // fprintf(stdout, "> %p: %s< %p: %s", x, x->data, y, y->data); |
Erik Andersen | 029011b | 2000-03-04 21:19:32 +0000 | [diff] [blame] | 120 | return APPLY_REVERSE(strcmp(x->data, y->data)); |
John Beppu | f3e5904 | 1999-12-22 22:24:52 +0000 | [diff] [blame] | 121 | } |
John Beppu | c0ca473 | 1999-12-21 20:00:35 +0000 | [diff] [blame] | 122 | |
John Beppu | 568cb7b | 1999-12-22 23:02:12 +0000 | [diff] [blame] | 123 | /* numeric order */ |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 124 | static int compare_numeric(const void *a, const void *b) |
John Beppu | f3e5904 | 1999-12-22 22:24:52 +0000 | [diff] [blame] | 125 | { |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 126 | Line **doh; |
| 127 | Line *x, *y; |
| 128 | int xint, yint; |
John Beppu | ee512a3 | 1999-12-23 00:02:49 +0000 | [diff] [blame] | 129 | |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 130 | doh = (Line **) a; |
| 131 | x = *doh; |
| 132 | doh = (Line **) b; |
| 133 | y = *doh; |
John Beppu | ee512a3 | 1999-12-23 00:02:49 +0000 | [diff] [blame] | 134 | |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 135 | xint = strtoul(x->data, NULL, 10); |
| 136 | yint = strtoul(y->data, NULL, 10); |
John Beppu | ee512a3 | 1999-12-23 00:02:49 +0000 | [diff] [blame] | 137 | |
Erik Andersen | 029011b | 2000-03-04 21:19:32 +0000 | [diff] [blame] | 138 | return APPLY_REVERSE(xint - yint); |
John Beppu | f3e5904 | 1999-12-22 22:24:52 +0000 | [diff] [blame] | 139 | } |
John Beppu | c0ca473 | 1999-12-21 20:00:35 +0000 | [diff] [blame] | 140 | |
| 141 | |
| 142 | /* List */ |
| 143 | |
John Beppu | 38efa79 | 1999-12-22 00:30:29 +0000 | [diff] [blame] | 144 | /* */ |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 145 | static List *list_init(List * self) |
John Beppu | 38efa79 | 1999-12-22 00:30:29 +0000 | [diff] [blame] | 146 | { |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 147 | self->len = 0; |
| 148 | self->sorted = NULL; |
| 149 | self->head = NULL; |
| 150 | self->current = NULL; |
| 151 | return self; |
John Beppu | 38efa79 | 1999-12-22 00:30:29 +0000 | [diff] [blame] | 152 | } |
John Beppu | c0ca473 | 1999-12-21 20:00:35 +0000 | [diff] [blame] | 153 | |
John Beppu | 38efa79 | 1999-12-22 00:30:29 +0000 | [diff] [blame] | 154 | /* for simplicity, the List gains ownership of the line */ |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 155 | static List *list_insert(List * self, Line * line) |
John Beppu | 38efa79 | 1999-12-22 00:30:29 +0000 | [diff] [blame] | 156 | { |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 157 | if (line == NULL) { |
| 158 | return NULL; |
| 159 | } |
John Beppu | c0ca473 | 1999-12-21 20:00:35 +0000 | [diff] [blame] | 160 | |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 161 | /* first insertion */ |
| 162 | if (self->head == NULL) { |
| 163 | self->head = line; |
| 164 | self->current = line; |
John Beppu | c0ca473 | 1999-12-21 20:00:35 +0000 | [diff] [blame] | 165 | |
John Beppu | 5a728cf | 2000-04-17 04:22:09 +0000 | [diff] [blame] | 166 | /* all subsequent insertions */ |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 167 | } else { |
| 168 | self->current->next = line; |
| 169 | self->current = line; |
| 170 | } |
| 171 | self->len++; |
| 172 | return self; |
John Beppu | 38efa79 | 1999-12-22 00:30:29 +0000 | [diff] [blame] | 173 | } |
| 174 | |
John Beppu | f3e5904 | 1999-12-22 22:24:52 +0000 | [diff] [blame] | 175 | /* order the list according to compare() */ |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 176 | static List *list_sort(List * self, Compare * compare) |
John Beppu | f3e5904 | 1999-12-22 22:24:52 +0000 | [diff] [blame] | 177 | { |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 178 | int i; |
| 179 | Line *line; |
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 | /* mallocate array of Line*s */ |
| 182 | self->sorted = (Line **) malloc(self->len * sizeof(Line *)); |
| 183 | if (self->sorted == NULL) { |
| 184 | return NULL; |
| 185 | } |
John Beppu | f3e5904 | 1999-12-22 22:24:52 +0000 | [diff] [blame] | 186 | |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 187 | /* 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 Beppu | f3e5904 | 1999-12-22 22:24:52 +0000 | [diff] [blame] | 194 | |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 195 | /* apply qsort */ |
| 196 | qsort(self->sorted, self->len, sizeof(Line *), compare); |
| 197 | return self; |
John Beppu | f3e5904 | 1999-12-22 22:24:52 +0000 | [diff] [blame] | 198 | } |
John Beppu | 38efa79 | 1999-12-22 00:30:29 +0000 | [diff] [blame] | 199 | |
| 200 | /* precondition: list must be sorted */ |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 201 | static List *list_writeToFile(List * self, FILE * dst) |
John Beppu | 38efa79 | 1999-12-22 00:30:29 +0000 | [diff] [blame] | 202 | { |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 203 | int i; |
| 204 | Line **line = self->sorted; |
John Beppu | f3e5904 | 1999-12-22 22:24:52 +0000 | [diff] [blame] | 205 | |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 206 | 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 Beppu | 38efa79 | 1999-12-22 00:30:29 +0000 | [diff] [blame] | 213 | } |
| 214 | |
| 215 | /* deallocate */ |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 216 | static void list_release(List * self) |
John Beppu | 38efa79 | 1999-12-22 00:30:29 +0000 | [diff] [blame] | 217 | { |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 218 | Line *i; |
| 219 | Line *die; |
John Beppu | 019513a | 1999-12-22 17:57:31 +0000 | [diff] [blame] | 220 | |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 221 | i = self->head; |
| 222 | while (i) { |
| 223 | die = i; |
| 224 | i = die->next; |
| 225 | line_release(die); |
| 226 | } |
John Beppu | 38efa79 | 1999-12-22 00:30:29 +0000 | [diff] [blame] | 227 | } |
John Beppu | c0ca473 | 1999-12-21 20:00:35 +0000 | [diff] [blame] | 228 | |
| 229 | |
John Beppu | c0ca473 | 1999-12-21 20:00:35 +0000 | [diff] [blame] | 230 | |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 231 | int sort_main(int argc, char **argv) |
John Beppu | c0ca473 | 1999-12-21 20:00:35 +0000 | [diff] [blame] | 232 | { |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 233 | int i; |
| 234 | char opt; |
| 235 | List list; |
| 236 | Line *l; |
| 237 | Compare *compare; |
John Beppu | c0ca473 | 1999-12-21 20:00:35 +0000 | [diff] [blame] | 238 | |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 239 | /* init */ |
| 240 | compare = compare_ascii; |
| 241 | list_init(&list); |
John Beppu | c0ca473 | 1999-12-21 20:00:35 +0000 | [diff] [blame] | 242 | |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 243 | /* parse argv[] */ |
| 244 | for (i = 1; i < argc; i++) { |
| 245 | if (argv[i][0] == '-') { |
| 246 | opt = argv[i][1]; |
| 247 | switch (opt) { |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 248 | case 'h': |
| 249 | usage(sort_usage); |
| 250 | break; |
| 251 | case 'n': |
Erik Andersen | 029011b | 2000-03-04 21:19:32 +0000 | [diff] [blame] | 252 | /* numeric comparison */ |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 253 | compare = compare_numeric; |
| 254 | break; |
Erik Andersen | 029011b | 2000-03-04 21:19:32 +0000 | [diff] [blame] | 255 | #ifdef BB_FEATURE_SORT_REVERSE |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 256 | case 'r': |
| 257 | /* reverse */ |
Erik Andersen | 029011b | 2000-03-04 21:19:32 +0000 | [diff] [blame] | 258 | reverse = 1; |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 259 | break; |
Erik Andersen | 029011b | 2000-03-04 21:19:32 +0000 | [diff] [blame] | 260 | #endif |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 261 | 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 Beppu | c0ca473 | 1999-12-21 20:00:35 +0000 | [diff] [blame] | 282 | } else { |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 283 | 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 Beppu | c0ca473 | 1999-12-21 20:00:35 +0000 | [diff] [blame] | 298 | } |
John Beppu | c0ca473 | 1999-12-21 20:00:35 +0000 | [diff] [blame] | 299 | |
Erik Andersen | e49d5ec | 2000-02-08 19:58:47 +0000 | [diff] [blame] | 300 | exit(0); |
John Beppu | c0ca473 | 1999-12-21 20:00:35 +0000 | [diff] [blame] | 301 | } |
| 302 | |
John Beppu | 5a728cf | 2000-04-17 04:22:09 +0000 | [diff] [blame] | 303 | /* $Id: sort.c,v 1.15 2000/04/17 04:22:09 beppu Exp $ */ |