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 "busybox.h"
  26 #include <sys/types.h>
  27 #include <fcntl.h>
  28 #include <dirent.h>
  29 #include <stdio.h>
  30 #include <errno.h>
  31
  32 #ifdef BB_FEATURE_SORT_REVERSE
  33 #define APPLY_REVERSE(x) (reverse ? -(x) : (x))
  34 static int reverse = 0;
  35 #else
  36 #define APPLY_REVERSE(x) (x)
  37 #endif
  38
  39 /* typedefs _______________________________________________________________ */
  40
  41 /* line node */
  42 typedef struct Line {
  43         char *data;                                     /* line data */
  44         struct Line *next;                      /* pointer to next line node */
  45 } Line;
  46
  47 /* singly-linked list of lines */
  48 typedef struct {
  49         int len;                                        /* number of Lines */
  50         Line **sorted;                          /* array fed to qsort */
  51         Line *head;                                     /* head of List */
  52         Line *current;                          /* current Line */
  53 } List;
  54
  55 /* comparison function */
  56 typedef int (Compare) (const void *, const void *);
  57
  58
  59 /* methods ________________________________________________________________ */
  60
  61 static const int max = 1024;
  62
  63 /* mallocate Line */
  64 static Line *line_alloc()
  65 {
  66         Line *self;
  67         self = xmalloc(1 * sizeof(Line));
  68         return self;
  69 }
  70
  71 /* Construct Line from FILE* */
  72 static Line *line_newFromFile(FILE * src)
  73 {
  74         Line *self;
  75         char *cstring = NULL;
  76
  77         if ((cstring = get_line_from_file(src))) {
  78                 self = line_alloc();
  79                 self->data = cstring;
  80                 self->next = NULL;
  81                 return self;
  82         }
  83         return NULL;
  84 }
  85
  86 /* Line destructor */
  87 static Line *line_release(Line * self)
  88 {
  89         if (self->data) {
  90                 free(self->data);
  91                 free(self);
  92         }
  93         return self;
  94 }
  95
  96
  97 /* Comparison */
  98
  99 /* ascii order */
 100 static int compare_ascii(const void *a, const void *b)
 101 {
 102         Line **val;
 103         Line *x, *y;
 104
 105         val = (Line **) a;
 106         x = *val;
 107         val = (Line **) b;
 108         y = *val;
 109
 110         // fprintf(stdout, "> %p: %s< %p: %s", x, x->data, y, y->data);
 111         return APPLY_REVERSE(strcmp(x->data, y->data));
 112 }
 113
 114 /* numeric order */
 115 static int compare_numeric(const void *a, const void *b)
 116 {
 117         Line **val;
 118         Line *x, *y;
 119         int xint, yint;
 120
 121         val = (Line **) a;
 122         x = *val;
 123         val = (Line **) b;
 124         y = *val;
 125
 126         xint = strtoul(x->data, NULL, 10);
 127         yint = strtoul(y->data, NULL, 10);
 128
 129         return APPLY_REVERSE(xint - yint);
 130 }
 131
 132
 133 /* List */
 134
 135 /* */
 136 static List *list_init(List * self)
 137 {
 138         self->len = 0;
 139         self->sorted = NULL;
 140         self->head = NULL;
 141         self->current = NULL;
 142         return self;
 143 }
 144
 145 /* for simplicity, the List gains ownership of the line */
 146 static List *list_insert(List * self, Line * line)
 147 {
 148         if (line == NULL) {
 149                 return NULL;
 150         }
 151
 152         /* first insertion */
 153         if (self->head == NULL) {
 154                 self->head = line;
 155                 self->current = line;
 156
 157         /* all subsequent insertions */
 158         } else {
 159                 self->current->next = line;
 160                 self->current = line;
 161         }
 162         self->len++;
 163         return self;
 164 }
 165
 166 /* order the list according to compare() */
 167 static List *list_sort(List * self, Compare * compare)
 168 {
 169         int i;
 170         Line *line;
 171
 172         /* mallocate array of Line*s */
 173         self->sorted = (Line **) xmalloc(self->len * sizeof(Line *));
 174
 175         /* fill array w/ List's contents */
 176         i = 0;
 177         line = self->head;
 178         while (line) {
 179                 self->sorted[i++] = line;
 180                 line = line->next;
 181         }
 182
 183         /* apply qsort */
 184         qsort(self->sorted, self->len, sizeof(Line *), compare);
 185         return self;
 186 }
 187
 188 /* precondition:  list must be sorted */
 189 static List *list_writeToFile(List * self, FILE * dst)
 190 {
 191         int i;
 192         Line **line = self->sorted;
 193
 194         if (self->sorted == NULL) {
 195                 return NULL;
 196         }
 197         for (i = 0; i < self->len; i++) {
 198                 fprintf(dst, "%s", line[i]->data);
 199         }
 200         return self;
 201 }
 202
 203 /* deallocate */
 204 static void list_release(List * self)
 205 {
 206         Line *i;
 207         Line *die;
 208
 209         i = self->head;
 210         while (i) {
 211                 die = i;
 212                 i = die->next;
 213                 line_release(die);
 214         }
 215 }
 216
 217
 218
 219 int sort_main(int argc, char **argv)
 220 {
 221         int i;
 222         char opt;
 223         List list;
 224         Line *l;
 225         Compare *compare;
 226
 227         /* init */
 228         compare = compare_ascii;
 229         list_init(&list);
 230
 231         /* parse argv[] */
 232         for (i = 1; i < argc; i++) {
 233                 if (argv[i][0] == '-') {
 234                         opt = argv[i][1];
 235                         switch (opt) {
 236                         case 'h':
 237                                 usage(sort_usage);
 238                                 break;
 239                         case 'n':
 240                                 /* numeric comparison */
 241                                 compare = compare_numeric;
 242                                 break;
 243 #ifdef BB_FEATURE_SORT_REVERSE
 244                         case 'r':
 245                                 /* reverse */
 246                                 reverse = 1;
 247                                 break;
 248 #endif
 249                         default:
 250                                 errorMsg("invalid option -- %c\n", opt);
 251                                 usage(sort_usage);
 252                         }
 253                 } else {
 254                         break;
 255                 }
 256         }
 257
 258         if (i >= argc) {
 259
 260         /* work w/ stdin */
 261                 while ((l = line_newFromFile(stdin))) {
 262                         list_insert(&list, l);
 263                 }
 264
 265         } else {
 266
 267                 /* work w/ what's left in argv[] */
 268                 FILE *src;
 269
 270                 for (; i < argc; i++) {
 271                         src = fopen(argv[i], "r");
 272                         if (src == NULL) {
 273                                 break;
 274                         }
 275                         while ((l = line_newFromFile(src))) {
 276                                 list_insert(&list, l);
 277                         }
 278                         fclose(src);
 279                 }
 280
 281         }
 282     list_sort(&list, compare);
 283     list_writeToFile(&list, stdout);
 284     list_release(&list);
 285
 286         return(0);
 287 }
 288
 289 /* $Id: sort.c,v 1.23 2000/09/28 17:49:59 beppu Exp $ */