sort.c

   1 /*
   2  * Mini find 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 static int
 111 compare_ascii(const void *a, const void *b)
 112 {
 113     return 0;
 114 }
 115
 116 static int
 117 compare_numeric(const void *a, const void *b)
 118 {
 119     return 0;
 120 }
 121
 122
 123 /* List */
 124
 125 /* */
 126 static List *
 127 list_init(List *self)
 128 {
 129     self->len     = 0;
 130     self->sorted  = NULL;
 131     self->head    = NULL;
 132     self->current = NULL;
 133     return self;
 134 }
 135
 136 /* for simplicity, the List gains ownership of the line */
 137 static List *
 138 list_insert(List *self, Line *line)
 139 {
 140     if (line == NULL) { return NULL; }
 141
 142     /* first insertion */
 143     if (self->head == NULL) {
 144         self->head    = line;
 145         self->current = line;
 146
 147     /* all subsequent insertions */
 148     } else {
 149         /* <?> the following cast shouldn't be necessary */
 150         self->current->next = line;
 151         self->current       = line;
 152     }
 153     self->len++;
 154     return self;
 155 }
 156
 157 /* order the list according to compare() */
 158 static List *
 159 list_sort(List *self, Compare *compare)
 160 {
 161     int     i;
 162     Line    *line;
 163
 164     /* mallocate array of Line*s */
 165     self->sorted = (Line **) malloc(self->len * sizeof(Line*));
 166     if (self->sorted == NULL) { return NULL; }
 167
 168     /* fill array w/ List's contents */
 169     i = 0;
 170     line = self->head;
 171     while (line) {
 172         self->sorted[i++] = line;
 173         line = line->next;
 174     }
 175
 176     /* apply qsort */
 177     qsort(self->sorted, sizeof(Line*), self->len, compare);
 178     return self;
 179 }
 180
 181 /* precondition:  list must be sorted */
 182 static List *
 183 list_writeToFile(List *self, FILE* dst)
 184 {
 185     int i;
 186     Line **line = self->sorted;
 187
 188     if (self->sorted == NULL) { return NULL; }
 189     for (i = 0; i < self->len; i++) {
 190         fprintf(dst, "%s", line[i]->data);
 191     }
 192     return self;
 193 }
 194
 195 /* deallocate */
 196 static void
 197 list_release(List *self)
 198 {
 199     Line *i;
 200     Line *die;
 201
 202     i = self->head;
 203     while (i) {
 204         die = i;
 205         i = die->next;
 206         line_release(die);
 207     }
 208 }
 209
 210
 211 /*
 212  * I need a list
 213  * to insert lines into
 214  * then I need to sort this list
 215  * and finally print it
 216  */
 217
 218 int
 219 sort_main(int argc, char **argv)
 220 {
 221     int     i;
 222     char    opt;
 223     List    list;
 224     Line    *l;
 225
 226     /* default behaviour */
 227
 228     /* parse argv[] */
 229     for (i = 1; i < argc; i++) {
 230         if (argv[i][0] == '-') {
 231             opt = argv[i][1];
 232             switch (opt) {
 233                 case 'h':
 234                     usage(sort_usage);
 235                     break;
 236                 default:
 237                     fprintf(stderr, "sort: invalid option -- %c\n", opt);
 238                     usage(sort_usage);
 239             }
 240         } else {
 241             break;
 242         }
 243     }
 244
 245     /* initialize list */
 246     list_init(&list);
 247
 248     /* go through remaining args (if any) */
 249     if (i >= argc) {
 250         while ( (l = line_newFromFile(stdin))) {
 251             list_insert(&list, l);
 252         }
 253         list_sort(&list, compare_ascii);
 254         list_writeToFile(&list, stdout);
 255         list_release(&list);
 256     } else {
 257         for ( ; i < argc; i++) {
 258         }
 259     }
 260
 261     exit(0);
 262 }
 263
 264 /* $Id: sort.c,v 1.4 1999/12/22 22:24:52 beppu Exp $ */
 265 /* $Log: sort.c,v $
 266  * Revision 1.4  1999/12/22 22:24:52  beppu
 267  *      the base is nearly done.
 268  *      need to implement various comparison functions, now.
 269  * */