coreutils/sort.c

   1 /* vi: set sw=4 ts=4: */
   2 /*
   3  * Mini sort implementation for busybox
   4  *
   5  *
   6  * Copyright (C) 1999 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 [OPTION]... [FILE]...\n\n";
  33
  34 /* typedefs _______________________________________________________________ */
  35
  36 /* line node */
  37 typedef struct Line {
  38         char *data;                                     /* line data */
  39         struct Line *next;                      /* pointer to next line node */
  40 } Line;
  41
  42 /* singly-linked list of lines */
  43 typedef struct {
  44         int len;                                        /* number of Lines */
  45         Line **sorted;                          /* array fed to qsort */
  46
  47         Line *head;                                     /* head of List */
  48         Line *current;                          /* current Line */
  49 } List;
  50
  51 /* comparison function */
  52 typedef int (Compare) (const void *, const void *);
  53
  54
  55 /* methods ________________________________________________________________ */
  56
  57 static const int max = 1024;
  58
  59 /* mallocate Line */
  60 static Line *line_alloc()
  61 {
  62         Line *self;
  63
  64         self = malloc(1 * sizeof(Line));
  65         return self;
  66 }
  67
  68 /* Initialize Line with string */
  69 static Line *line_init(Line * self, const char *string)
  70 {
  71         self->data = malloc((strlen(string) + 1) * sizeof(char));
  72
  73         if (self->data == NULL) {
  74                 return NULL;
  75         }
  76         strcpy(self->data, string);
  77         self->next = NULL;
  78         return self;
  79 }
  80
  81 /* Construct Line from FILE* */
  82 static Line *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) {
  90                         return NULL;
  91                 }
  92                 line_init(self, buffer);
  93                 return self;
  94         }
  95         return NULL;
  96 }
  97
  98 /* Line destructor */
  99 static Line *line_release(Line * self)
 100 {
 101         if (self->data) {
 102                 free(self->data);
 103                 free(self);
 104         }
 105         return self;
 106 }
 107
 108
 109 /* Comparison */
 110
 111 /* ascii order */
 112 static int 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 compare_numeric(const void *a, const void *b)
 128 {
 129         Line **doh;
 130         Line *x, *y;
 131         int xint, yint;
 132
 133         doh = (Line **) a;
 134         x = *doh;
 135         doh = (Line **) b;
 136         y = *doh;
 137
 138         xint = strtoul(x->data, NULL, 10);
 139         yint = strtoul(y->data, NULL, 10);
 140
 141         return (xint - yint);
 142 }
 143
 144
 145 /* List */
 146
 147 /* */
 148 static List *list_init(List * self)
 149 {
 150         self->len = 0;
 151         self->sorted = NULL;
 152         self->head = NULL;
 153         self->current = NULL;
 154         return self;
 155 }
 156
 157 /* for simplicity, the List gains ownership of the line */
 158 static List *list_insert(List * self, Line * line)
 159 {
 160         if (line == NULL) {
 161                 return NULL;
 162         }
 163
 164         /* first insertion */
 165         if (self->head == NULL) {
 166                 self->head = line;
 167                 self->current = line;
 168
 169                 /* all subsequent insertions */
 170         } else {
 171                 self->current->next = line;
 172                 self->current = line;
 173         }
 174         self->len++;
 175         return self;
 176 }
 177
 178 /* order the list according to compare() */
 179 static List *list_sort(List * self, Compare * compare)
 180 {
 181         int i;
 182         Line *line;
 183
 184         /* mallocate array of Line*s */
 185         self->sorted = (Line **) malloc(self->len * sizeof(Line *));
 186         if (self->sorted == NULL) {
 187                 return NULL;
 188         }
 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 *list_writeToFile(List * self, FILE * dst)
 205 {
 206         int i;
 207         Line **line = self->sorted;
 208
 209         if (self->sorted == NULL) {
 210                 return NULL;
 211         }
 212         for (i = 0; i < self->len; i++) {
 213                 fprintf(dst, "%s", line[i]->data);
 214         }
 215         return self;
 216 }
 217
 218 /* deallocate */
 219 static void 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 sort_main(int argc, char **argv)
 241 {
 242         int i;
 243         char opt;
 244         List list;
 245         Line *l;
 246         Compare *compare;
 247
 248         /* init */
 249         compare = compare_ascii;
 250         list_init(&list);
 251
 252         /* parse argv[] */
 253         for (i = 1; i < argc; i++) {
 254                 if (argv[i][0] == '-') {
 255                         opt = argv[i][1];
 256                         switch (opt) {
 257                         case 'g':
 258                                 /* what's the diff between -g && -n? */
 259                                 compare = compare_numeric;
 260                                 break;
 261                         case 'h':
 262                                 usage(sort_usage);
 263                                 break;
 264                         case 'n':
 265                                 /* what's the diff between -g && -n? */
 266                                 compare = compare_numeric;
 267                                 break;
 268                         case 'r':
 269                                 /* reverse */
 270                                 break;
 271                         default:
 272                                 fprintf(stderr, "sort: invalid option -- %c\n", opt);
 273                                 usage(sort_usage);
 274                         }
 275                 } else {
 276                         break;
 277                 }
 278         }
 279
 280         /* this could be factored better */
 281
 282         /* work w/ stdin */
 283         if (i >= argc) {
 284                 while ((l = line_newFromFile(stdin))) {
 285                         list_insert(&list, l);
 286                 }
 287                 list_sort(&list, compare);
 288                 list_writeToFile(&list, stdout);
 289                 list_release(&list);
 290
 291                 /* work w/ what's left in argv[] */
 292         } else {
 293                 FILE *src;
 294
 295                 for (; i < argc; i++) {
 296                         src = fopen(argv[i], "r");
 297                         if (src == NULL) {
 298                                 break;
 299                         }
 300                         while ((l = line_newFromFile(src))) {
 301                                 list_insert(&list, l);
 302                         }
 303                         fclose(src);
 304                 }
 305                 list_sort(&list, compare);
 306                 list_writeToFile(&list, stdout);
 307                 list_release(&list);
 308         }
 309
 310         exit(0);
 311 }
 312
 313 /* $Id: sort.c,v 1.11 2000/02/08 19:58:47 erik Exp $ */