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 "Usage: 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 = (Line *) *doh;
 119     doh = (Line **) b;
 120     y = (Line *) *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     return 0;
 131 }
 132
 133
 134 /* List */
 135
 136 /* */
 137 static List *
 138 list_init(List *self)
 139 {
 140     self->len     = 0;
 141     self->sorted  = NULL;
 142     self->head    = NULL;
 143     self->current = NULL;
 144     return self;
 145 }
 146
 147 /* for simplicity, the List gains ownership of the line */
 148 static List *
 149 list_insert(List *self, Line *line)
 150 {
 151     if (line == NULL) { return NULL; }
 152
 153     /* first insertion */
 154     if (self->head == NULL) {
 155         self->head    = line;
 156         self->current = line;
 157
 158     /* all subsequent insertions */
 159     } else {
 160         self->current->next = line;
 161         self->current       = line;
 162     }
 163     self->len++;
 164     return self;
 165 }
 166
 167 /* order the list according to compare() */
 168 static List *
 169 list_sort(List *self, Compare *compare)
 170 {
 171     int     i;
 172     Line    *line;
 173
 174     /* mallocate array of Line*s */
 175     self->sorted = (Line **) malloc(self->len * sizeof(Line*));
 176     if (self->sorted == NULL) { return NULL; }
 177
 178     /* fill array w/ List's contents */
 179     i = 0;
 180     line = self->head;
 181     while (line) {
 182         self->sorted[i++] = line;
 183         line = line->next;
 184     }
 185
 186     /* apply qsort */
 187     qsort(self->sorted, self->len, sizeof(Line*), compare);
 188     return self;
 189 }
 190
 191 /* precondition:  list must be sorted */
 192 static List *
 193 list_writeToFile(List *self, FILE* dst)
 194 {
 195     int i;
 196     Line **line = self->sorted;
 197
 198     if (self->sorted == NULL) { return NULL; }
 199     for (i = 0; i < self->len; i++) {
 200         fprintf(dst, "%s", line[i]->data);
 201     }
 202     return self;
 203 }
 204
 205 /* deallocate */
 206 static void
 207 list_release(List *self)
 208 {
 209     Line *i;
 210     Line *die;
 211
 212     i = self->head;
 213     while (i) {
 214         die = i;
 215         i = die->next;
 216         line_release(die);
 217     }
 218 }
 219
 220
 221 /*
 222  * I need a list
 223  * to insert lines into
 224  * then I need to sort this list
 225  * and finally print it
 226  */
 227
 228 int
 229 sort_main(int argc, char **argv)
 230 {
 231     int     i;
 232     char    opt;
 233     List    list;
 234     Line    *l;
 235
 236     /* default behaviour */
 237
 238     /* parse argv[] */
 239     for (i = 1; i < argc; i++) {
 240         if (argv[i][0] == '-') {
 241             opt = argv[i][1];
 242             switch (opt) {
 243                 case 'h':
 244                     usage(sort_usage);
 245                     break;
 246                 default:
 247                     fprintf(stderr, "sort: invalid option -- %c\n", opt);
 248                     usage(sort_usage);
 249             }
 250         } else {
 251             break;
 252         }
 253     }
 254
 255     /* initialize list */
 256     list_init(&list);
 257
 258     /* go through remaining args (if any) */
 259     if (i >= argc) {
 260         while ( (l = line_newFromFile(stdin))) {
 261             list_insert(&list, l);
 262         }
 263         list_sort(&list, compare_ascii);
 264         list_writeToFile(&list, stdout);
 265         list_release(&list);
 266     } else {
 267         for ( ; i < argc; i++) {
 268         }
 269     }
 270
 271     exit(0);
 272 }
 273
 274 /* $Id: sort.c,v 1.6 1999/12/22 23:02:12 beppu Exp $ */
 275 /*
 276  * $Log: sort.c,v $
 277  * Revision 1.6  1999/12/22 23:02:12  beppu
 278  *      oops..  qsort(2) misunderstanding on my part.
 279  *      it's ok, now.
 280  *
 281  * Revision 1.5  1999/12/22 22:27:01  beppu
 282  * playing w/ $Log: sort.c,v $
 283  * playing w/ Revision 1.6  1999/12/22 23:02:12  beppu
 284  * playing w/   oops..  qsort(2) misunderstanding on my part.
 285  * playing w/   it's ok, now.
 286  * playing w/
 287  *
 288  */