sort.c

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