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