sort.c

   1 /*
   2  * Mini sort implementation for busybox
   3  *
   4  *
   5  * Copyright (C) 1999 by Lineo, inc.
   6  * Written by John Beppu <beppu@lineo.com>
   7  *
   8  * This program is free software; you can redistribute it and/or modify
   9  * it under the terms of the GNU General Public License as published by
  10  * the Free Software Foundation; either version 2 of the License, or
  11  * (at your option) any later version.
  12  *
  13  * This program is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  16  * General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU General Public License
  19  * along with this program; if not, write to the Free Software
  20  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
  21  *
  22  */
  23
  24 #include "internal.h"
  25 #include <sys/types.h>
  26 #include <fcntl.h>
  27 #include <dirent.h>
  28 #include <stdio.h>
  29 #include <errno.h>
  30
  31 static const char sort_usage[] =
  32 "sort [OPTION]... [FILE]...\n\n"
  33 ;
  34
  35 /* typedefs _______________________________________________________________ */
  36
  37 /* line node */
  38 typedef struct Line {
  39     char        *data;      /* line data */
  40     struct Line *next;      /* pointer to next line node */
  41 } Line;
  42
  43 /* singly-linked list of lines */
  44 typedef struct {
  45     int         len;        /* number of Lines */
  46     Line        **sorted;   /* array fed to qsort */
  47
  48     Line        *head;      /* head of List */
  49     Line        *current;   /* current Line */
  50 } List;
  51
  52 /* comparison function */
  53 typedef int (Compare)(const void *, const void *);
  54
  55
  56 /* methods ________________________________________________________________ */
  57
  58 static const int max = 1024;
  59
  60 /* mallocate Line */
  61 static Line *
  62 line_alloc()
  63 {
  64     Line *self;
  65     self = malloc(1 * sizeof(Line));
  66     return self;
  67 }
  68
  69 /* Initialize Line with string */
  70 static Line *
  71 line_init(Line *self, const char *string)
  72 {
  73     self->data = malloc((strlen(string) + 1) * sizeof(char));
  74     if (self->data == NULL) { return NULL; }
  75     strcpy(self->data, string);
  76     self->next = NULL;
  77     return self;
  78 }
  79
  80 /* Construct Line from FILE* */
  81 static Line *
  82 line_newFromFile(FILE *src)
  83 {
  84     char    buffer[max];
  85     Line    *self;
  86
  87     if (fgets(buffer, max, src)) {
  88         self = line_alloc();
  89         if (self == NULL) { return NULL; }
  90         line_init(self, buffer);
  91         return self;
  92     }
  93     return NULL;
  94 }
  95
  96 /* Line destructor */
  97 static Line *
  98 line_release(Line *self)
  99 {
 100     if (self->data) {
 101         free(self->data);
 102         free(self);
 103     }
 104     return self;
 105 }
 106
 107
 108 /* Comparison */
 109
 110 /* ascii order */
 111 static int
 112 compare_ascii(const void *a, const void *b)
 113 {
 114     Line **doh;
 115     Line *x, *y;
 116
 117     doh = (Line **) a;
 118     x   = *doh;
 119     doh = (Line **) b;
 120     y   = *doh;
 121
 122     // fprintf(stdout, "> %p: %s< %p: %s", x, x->data, y, y->data);
 123     return strcmp(x->data, y->data);
 124 }
 125
 126 /* numeric order */
 127 static int
 128 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 (xint - yint);
 143 }
 144
 145
 146 /* List */
 147
 148 /* */
 149 static List *
 150 list_init(List *self)
 151 {
 152     self->len     = 0;
 153     self->sorted  = NULL;
 154     self->head    = NULL;
 155     self->current = NULL;
 156     return self;
 157 }
 158
 159 /* for simplicity, the List gains ownership of the line */
 160 static List *
 161 list_insert(List *self, Line *line)
 162 {
 163     if (line == NULL) { return NULL; }
 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 *
 181 list_sort(List *self, Compare *compare)
 182 {
 183     int     i;
 184     Line    *line;
 185
 186     /* mallocate array of Line*s */
 187     self->sorted = (Line **) malloc(self->len * sizeof(Line*));
 188     if (self->sorted == NULL) { return NULL; }
 189
 190     /* fill array w/ List's contents */
 191     i = 0;
 192     line = self->head;
 193     while (line) {
 194         self->sorted[i++] = line;
 195         line = line->next;
 196     }
 197
 198     /* apply qsort */
 199     qsort(self->sorted, self->len, sizeof(Line*), compare);
 200     return self;
 201 }
 202
 203 /* precondition:  list must be sorted */
 204 static List *
 205 list_writeToFile(List *self, FILE* dst)
 206 {
 207     int i;
 208     Line **line = self->sorted;
 209
 210     if (self->sorted == NULL) { return NULL; }
 211     for (i = 0; i < self->len; i++) {
 212         fprintf(dst, "%s", line[i]->data);
 213     }
 214     return self;
 215 }
 216
 217 /* deallocate */
 218 static void
 219 list_release(List *self)
 220 {
 221     Line *i;
 222     Line *die;
 223
 224     i = self->head;
 225     while (i) {
 226         die = i;
 227         i = die->next;
 228         line_release(die);
 229     }
 230 }
 231
 232
 233 /*
 234  * I need a list
 235  * to insert lines into
 236  * then I need to sort this list
 237  * and finally print it
 238  */
 239
 240 int
 241 sort_main(int argc, char **argv)
 242 {
 243     int     i;
 244     char    opt;
 245     List    list;
 246     Line    *l;
 247     Compare *compare;
 248
 249     /* init */
 250     compare = compare_ascii;
 251     list_init(&list);
 252
 253     /* parse argv[] */
 254     for (i = 1; i < argc; i++) {
 255         if (argv[i][0] == '-') {
 256             opt = argv[i][1];
 257             switch (opt) {
 258                 case 'g':
 259                     /* what's the diff between -g && -n? */
 260                     compare = compare_numeric;
 261                     break;
 262                 case 'h':
 263                     usage(sort_usage);
 264                     break;
 265                 case 'n':
 266                     /* what's the diff between -g && -n? */
 267                     compare = compare_numeric;
 268                     break;
 269                 case 'r':
 270                     /* reverse */
 271                     break;
 272                 default:
 273                     fprintf(stderr, "sort: invalid option -- %c\n", opt);
 274                     usage(sort_usage);
 275             }
 276         } else {
 277             break;
 278         }
 279     }
 280
 281     /* this could be factored better */
 282
 283     /* work w/ stdin */
 284     if (i >= argc) {
 285         while ( (l = line_newFromFile(stdin))) {
 286             list_insert(&list, l);
 287         }
 288         list_sort(&list, compare);
 289         list_writeToFile(&list, stdout);
 290         list_release(&list);
 291
 292     /* work w/ what's left in argv[] */
 293     } else {
 294         FILE    *src;
 295
 296         for ( ; i < argc; i++) {
 297             src = fopen(argv[i], "r");
 298             if (src == NULL) { break; }
 299             while ( (l = line_newFromFile(src))) {
 300                 list_insert(&list, l);
 301             }
 302             fclose(src);
 303         }
 304         list_sort(&list, compare);
 305         list_writeToFile(&list, stdout);
 306         list_release(&list);
 307     }
 308
 309     exit(0);
 310 }
 311
 312 /* $Id: sort.c,v 1.10 2000/02/07 05:29:42 erik Exp $ */