src/util/pacsort.c

   1 /*
   2  *  pacsort.c - a sort utility implementing alpm_pkg_vercmp
   3  *
   4  *  Copyright (c) 2010-2011 Pacman Development Team <pacman-dev@archlinux.org>
   5  *
   6  *  This program is free software; you can redistribute it and/or modify
   7  *  it under the terms of the GNU General Public License as published by
   8  *  the Free Software Foundation; either version 2 of the License, or
   9  *  (at your option) any later version.
  10  *
  11  *  This program is distributed in the hope that it will be useful,
  12  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  *  GNU General Public License for more details.
  15  *
  16  *  You should have received a copy of the GNU General Public License
  17  *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
  18  */
  19
  20 #include <errno.h>
  21 #include <getopt.h>
  22 #include <stdio.h>
  23 #include <stdlib.h>
  24 #include <string.h>
  25
  26 #include <alpm.h>
  27
  28 #define DELIM   ' '
  29
  30 struct buffer_t {
  31         char *mem;
  32         size_t len;
  33         size_t maxlen;
  34 };
  35
  36 struct list_t {
  37         char **list;
  38         size_t count;
  39         size_t maxcount;
  40 };
  41
  42 static struct options_t {
  43         int order;
  44         int sortkey;
  45         int null;
  46         char delim;
  47 } opts;
  48
  49 #ifndef HAVE_STRNDUP
  50 /* A quick and dirty implementation derived from glibc */
  51 static size_t strnlen(const char *s, size_t max)
  52 {
  53     register const char *p;
  54     for(p = s; *p && max--; ++p);
  55     return (p - s);
  56 }
  57
  58 char *strndup(const char *s, size_t n)
  59 {
  60   size_t len = strnlen(s, n);
  61   char *new = (char *) malloc(len + 1);
  62
  63   if(new == NULL)
  64     return NULL;
  65
  66   new[len] = '\0';
  67   return (char *)memcpy(new, s, len);
  68 }
  69 #endif
  70
  71 static struct buffer_t *buffer_new(size_t initial_size)
  72 {
  73         struct buffer_t *buf;
  74
  75         buf = calloc(1, sizeof(*buf));
  76         if(!buf) {
  77                 return NULL;
  78         }
  79
  80         buf->mem = calloc(initial_size, sizeof(char));
  81         if(!buf->mem) {
  82                 free(buf);
  83                 return NULL;
  84         }
  85
  86         buf->len = 0;
  87         buf->maxlen = initial_size;
  88
  89         return buf;
  90 }
  91
  92 static void buffer_free(struct buffer_t *buf)
  93 {
  94         if(!buf) {
  95                 return;
  96         }
  97
  98         if(buf->mem) {
  99                 free(buf->mem);
 100         }
 101
 102         free(buf);
 103 }
 104
 105 static int buffer_grow(struct buffer_t *buffer)
 106 {
 107         size_t newsz = buffer->maxlen * 2.5;
 108         buffer->mem = realloc(buffer->mem, newsz * sizeof(char));
 109         if(!buffer->mem) {
 110                 return 1;
 111         }
 112         buffer->maxlen = newsz;
 113
 114         return 0;
 115 }
 116
 117 static struct list_t *list_new(size_t initial_size)
 118 {
 119         struct list_t *list;
 120
 121         list = calloc(1, sizeof(struct list_t));
 122         if(!list) {
 123                 return NULL;
 124         }
 125
 126         list->list = calloc(initial_size, sizeof(char *));
 127         if(!list->list) {
 128                 free(list);
 129                 return NULL;
 130         }
 131
 132         list->maxcount = initial_size;
 133
 134         return list;
 135 }
 136
 137 static int list_grow(struct list_t *list)
 138 {
 139         size_t newsz = list->maxcount * 2.5;
 140         list->list = realloc(list->list, newsz * sizeof(char *));
 141         if(!list->list) {
 142                 return 1;
 143         }
 144
 145         list->maxcount = newsz;
 146
 147         return 0;
 148 }
 149
 150 static int list_add(struct list_t *list, char *name)
 151 {
 152         if(!list || !name) {
 153                 return 1;
 154         }
 155
 156         if(list->count + 1 >= list->maxcount) {
 157                 if(list_grow(list) != 0) {
 158                         return 1;
 159                 }
 160         }
 161
 162         list->list[list->count] = name;
 163         list->count++;
 164
 165         return 0;
 166 }
 167
 168 static void list_free(struct list_t *list)
 169 {
 170         size_t i;
 171
 172         if(!list) {
 173                 return;
 174         }
 175
 176         if(list->list) {
 177                 for(i = 0; i < list->count; i++) {
 178                         free(list->list[i]);
 179                 }
 180                 free(list->list);
 181         }
 182         free(list);
 183 }
 184
 185 static char *explode(struct buffer_t *buffer, struct list_t *list)
 186 {
 187         char *name, *ptr, *end;
 188         const char linedelim = opts.null ? '\0' : '\n';
 189
 190         ptr = buffer->mem;
 191         while((end = memchr(ptr, linedelim, &buffer->mem[buffer->len] - ptr))) {
 192                 *end = '\0';
 193                 name = strdup(ptr);
 194                 list_add(list, name);
 195                 ptr = end + 1;
 196         }
 197
 198         return ptr;
 199 }
 200
 201 static int splitfile(FILE *stream, struct buffer_t *buffer, struct list_t *list)
 202 {
 203         size_t nread;
 204         char *ptr;
 205
 206         while(!feof(stream)) {
 207                 /* check if a read of BUFSIZ chars will overflow */
 208                 if (buffer->len + BUFSIZ + 1 >= buffer->maxlen) {
 209                         if(buffer_grow(buffer) != 0) {
 210                                 return 1;
 211                         }
 212                 }
 213
 214                 nread = fread(&buffer->mem[buffer->len], 1, BUFSIZ, stream);
 215                 if(nread == 0) {
 216                         break; /* EOF */
 217                 }
 218                 buffer->len += nread;
 219
 220                 if((ptr = explode(buffer, list)) == NULL) {
 221                         return 1;
 222                 }
 223
 224                 if(ptr != buffer->mem) {
 225                         /* realign the data in the buffer */
 226                         buffer->len = &buffer->mem[buffer->len] - ptr;
 227                         memmove(&buffer->mem[0], ptr, buffer->len + 1);
 228                 }
 229         }
 230
 231         if(buffer->len) {
 232                 char *name = strndup(buffer->mem, buffer->len + 1);
 233                 if(list_add(list, name) != 0) {
 234                         return 1;
 235                 }
 236         }
 237
 238         return 0;
 239 }
 240
 241 /* returns a pointer to the nth column of a string without being destructive */
 242 static const char *nth_column(const char *string)
 243 {
 244         const char *prev, *ptr;
 245         int col;
 246
 247         ptr = prev = string;
 248         for(col = 1; ptr && col <= opts.sortkey; col++) {
 249                 prev = ptr;
 250                 ptr = strchr(ptr, opts.delim);
 251                 if(ptr) {
 252                         ptr++;
 253                 }
 254         }
 255
 256         return prev;
 257 }
 258
 259 static int vercmp(const void *p1, const void *p2)
 260 {
 261         const char *name1, *name2;
 262
 263         name1 = *(const char **)p1;
 264         name2 = *(const char **)p2;
 265
 266         if(opts.sortkey == 0) {
 267                 return opts.order * alpm_pkg_vercmp(name1, name2);
 268         } else {
 269                 return opts.order * alpm_pkg_vercmp(nth_column(name1), nth_column(name2));
 270         }
 271 }
 272
 273 static char escape_char(const char *string)
 274 {
 275         const size_t len = strlen(string);
 276
 277         if(!string || len > 2) {
 278                 return -1;
 279         }
 280
 281         if(len == 1) {
 282                 return *string;
 283         }
 284
 285         if(*string != '\\') {
 286                 return -1;
 287         }
 288
 289         switch(string[1]) {
 290                 case 't':
 291                         return '\t';
 292                 case 'n':
 293                         return '\n';
 294                 case 'v':
 295                         return '\v';
 296                 case '0':
 297                         return '\0';
 298                 default:
 299                         return -1;
 300         }
 301 }
 302
 303 static void usage(void)
 304 {
 305         fprintf(stderr, "pacsort v" PACKAGE_VERSION "\n"
 306                         "Usage: pacsort [options] [files...]\n\n"
 307                         "  -h, --help              display this help message\n"
 308                         "  -k, --key <index>       sort input starting on specified column\n"
 309                         "  -r, --reverse           sort in reverse order (default: oldest to newest)\n"
 310                         "  -t, --separator <sep>   specify field separator (default: space)\n"
 311                         "  -z, --null              lines end with null bytes, not newlines\n\n");
 312 }
 313
 314 static int parse_options(int argc, char **argv)
 315 {
 316         int opt;
 317
 318         static const struct option opttable[] = {
 319                 {"help",      no_argument,          0, 'h'},
 320                 {"key",       required_argument,    0, 'k'},
 321                 {"reverse",   no_argument,          0, 'r'},
 322                 {"separator", required_argument,    0, 't'},
 323                 {"null",      no_argument,          0, 'z'},
 324                 {0, 0, 0, 0}
 325         };
 326
 327         while((opt = getopt_long(argc, argv, "hk:rt:z", opttable, NULL)) != -1) {
 328                 switch(opt) {
 329                         case 'h':
 330                                 return 1;
 331                         case 'k':
 332                                 opts.sortkey = (int)strtol(optarg, NULL, 10);
 333                                 if(opts.sortkey <= 0) {
 334                                         fprintf(stderr, "error: invalid sort key -- %s\n", optarg);
 335                                         return 1;
 336                                 }
 337                                 break;
 338                         case 'r':
 339                                 opts.order = -1;
 340                                 break;
 341                         case 't':
 342                                 opts.delim = escape_char(optarg);
 343                                 if(opts.delim == -1) {
 344                                         fprintf(stderr, "error: invalid field separator -- `%s'\n", optarg);
 345                                         return 1;
 346                                 }
 347                                 break;
 348                         case 'z':
 349                                 opts.null = 1;
 350                                 break;
 351                         default:
 352                                 return 1;
 353                 }
 354         }
 355
 356         return 0;
 357 }
 358
 359 int main(int argc, char *argv[])
 360 {
 361         struct list_t *list;
 362         struct buffer_t *buffer;
 363         size_t i;
 364
 365         /* option defaults */
 366         opts.order = 1;
 367         opts.delim = DELIM;
 368         opts.sortkey = 0;
 369         opts.null = 0;
 370
 371         if(parse_options(argc, argv) != 0) {
 372                 usage();
 373                 return 2;
 374         }
 375
 376         list = list_new(100);
 377         buffer = buffer_new(BUFSIZ * 3);
 378
 379         if(optind == argc) {
 380                 if(splitfile(stdin, buffer, list) != 0) {
 381                         fprintf(stderr, "%s: memory exhausted\n", argv[0]);
 382                         return ENOMEM;
 383                 }
 384         } else {
 385                 while(optind < argc) {
 386                         FILE *input = fopen(argv[optind], "r");
 387                         if(input) {
 388                                 if(splitfile(input, buffer, list) != 0) {
 389                                         fprintf(stderr, "%s: memory exhausted\n", argv[0]);
 390                                         return ENOMEM;
 391                                 }
 392                                 fclose(input);
 393                         } else {
 394                                 fprintf(stderr, "%s: %s: %s\n", argv[0], argv[optind], strerror(errno));
 395                         }
 396                         optind++;
 397                 }
 398         }
 399
 400         if(list->count) {
 401                 const char linedelim = opts.null ? '\0' : '\n';
 402                 qsort(list->list, list->count, sizeof(char *), vercmp);
 403                 for(i = 0; i < list->count; i++) {
 404                         printf("%s%c", list->list[i], linedelim);
 405                 }
 406         }
 407
 408         list_free(list);
 409         buffer_free(buffer);
 410
 411         return 0;
 412 }
 413
 414 /* vim: set ts=2 sw=2 noet: */