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