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