usr.bin/sort/init.c

   1 /*      $NetBSD: init.c,v 1.27 2010/06/06 00:00:33 wiz Exp $    */
   2
   3 /*-
   4  * Copyright (c) 2000-2003 The NetBSD Foundation, Inc.
   5  * All rights reserved.
   6  *
   7  * This code is derived from software contributed to The NetBSD Foundation
   8  * by Ben Harris and Jaromir Dolecek.
   9  *
  10  * Redistribution and use in source and binary forms, with or without
  11  * modification, are permitted provided that the following conditions
  12  * are met:
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
  20  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
  21  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  22  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
  23  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  24  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  25  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  26  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  27  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  28  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  29  * POSSIBILITY OF SUCH DAMAGE.
  30  */
  31
  32 /*-
  33  * Copyright (c) 1993
  34  *      The Regents of the University of California.  All rights reserved.
  35  *
  36  * This code is derived from software contributed to Berkeley by
  37  * Peter McIlroy.
  38  *
  39  * Redistribution and use in source and binary forms, with or without
  40  * modification, are permitted provided that the following conditions
  41  * are met:
  42  * 1. Redistributions of source code must retain the above copyright
  43  *    notice, this list of conditions and the following disclaimer.
  44  * 2. Redistributions in binary form must reproduce the above copyright
  45  *    notice, this list of conditions and the following disclaimer in the
  46  *    documentation and/or other materials provided with the distribution.
  47  * 3. Neither the name of the University nor the names of its contributors
  48  *    may be used to endorse or promote products derived from this software
  49  *    without specific prior written permission.
  50  *
  51  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  52  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  53  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  54  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  55  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  56  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  57  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  58  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  59  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  60  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  61  * SUCH DAMAGE.
  62  */
  63
  64 #include "sort.h"
  65
  66 #include <ctype.h>
  67 #include <string.h>
  68
  69 static void insertcol(struct field *);
  70 static const char *setcolumn(const char *, struct field *);
  71
  72 /*
  73  * masks of ignored characters.
  74  */
  75 static u_char dtable[NBINS], itable[NBINS];
  76
  77 /*
  78  * parsed key options
  79  */
  80 struct coldesc *clist = NULL;
  81 int ncols = 0;
  82
  83 /*
  84  * clist (list of columns which correspond to one or more icol or tcol)
  85  * is in increasing order of columns.
  86  * Fields are kept in increasing order of fields.
  87  */
  88
  89 /*
  90  * keep clist in order--inserts a column in a sorted array
  91  */
  92 static void
  93 insertcol(struct field *field)
  94 {
  95         int i;
  96         struct coldesc *p;
  97
  98         /* Make space for new item */
  99         p = realloc(clist, (ncols + 2) * sizeof(*clist));
 100         if (!p)
 101                 err(1, "realloc");
 102         clist = p;
 103         memset(&clist[ncols], 0, sizeof(clist[ncols]));
 104
 105         for (i = 0; i < ncols; i++)
 106                 if (field->icol.num <= clist[i].num)
 107                         break;
 108         if (field->icol.num != clist[i].num) {
 109                 memmove(clist+i+1, clist+i, sizeof(COLDESC)*(ncols-i));
 110                 clist[i].num = field->icol.num;
 111                 ncols++;
 112         }
 113         if (field->tcol.num && field->tcol.num != field->icol.num) {
 114                 for (i = 0; i < ncols; i++)
 115                         if (field->tcol.num <= clist[i].num)
 116                                 break;
 117                 if (field->tcol.num != clist[i].num) {
 118                         memmove(clist+i+1, clist+i,sizeof(COLDESC)*(ncols-i));
 119                         clist[i].num = field->tcol.num;
 120                         ncols++;
 121                 }
 122         }
 123 }
 124
 125 /*
 126  * matches fields with the appropriate columns--n^2 but who cares?
 127  */
 128 void
 129 fldreset(struct field *fldtab)
 130 {
 131         int i;
 132
 133         fldtab[0].tcol.p = clist + ncols - 1;
 134         for (++fldtab; fldtab->icol.num; ++fldtab) {
 135                 for (i = 0; fldtab->icol.num != clist[i].num; i++)
 136                         ;
 137                 fldtab->icol.p = clist + i;
 138                 if (!fldtab->tcol.num)
 139                         continue;
 140                 for (i = 0; fldtab->tcol.num != clist[i].num; i++)
 141                         ;
 142                 fldtab->tcol.p = clist + i;
 143         }
 144 }
 145
 146 /*
 147  * interprets a column in a -k field
 148  */
 149 static const char *
 150 setcolumn(const char *pos, struct field *cur_fld)
 151 {
 152         struct column *col;
 153         char *npos;
 154         int tmp;
 155         col = cur_fld->icol.num ? (&cur_fld->tcol) : (&cur_fld->icol);
 156         col->num = (int) strtol(pos, &npos, 10);
 157         pos = npos;
 158         if (col->num <= 0 && !(col->num == 0 && col == &(cur_fld->tcol)))
 159                 errx(2, "field numbers must be positive");
 160         if (*pos == '.') {
 161                 if (!col->num)
 162                         errx(2, "cannot indent end of line");
 163                 ++pos;
 164                 col->indent = (int) strtol(pos, &npos, 10);
 165                 pos = npos;
 166                 if (&cur_fld->icol == col)
 167                         col->indent--;
 168                 if (col->indent < 0)
 169                         errx(2, "illegal offset");
 170         }
 171         for(; (tmp = optval(*pos, cur_fld->tcol.num)); pos++)
 172                 cur_fld->flags |= tmp;
 173         if (cur_fld->icol.num == 0)
 174                 cur_fld->icol.num = 1;
 175         return (pos);
 176 }
 177
 178 int
 179 setfield(const char *pos, struct field *cur_fld, int gflag)
 180 {
 181         cur_fld->mask = NULL;
 182
 183         pos = setcolumn(pos, cur_fld);
 184         if (*pos == '\0')                       /* key extends to EOL. */
 185                 cur_fld->tcol.num = 0;
 186         else {
 187                 if (*pos != ',')
 188                         errx(2, "illegal field descriptor");
 189                 setcolumn((++pos), cur_fld);
 190         }
 191         if (!cur_fld->flags)
 192                 cur_fld->flags = gflag;
 193         if (REVERSE)
 194                 /* A local 'r' doesn't invert the global one */
 195                 cur_fld->flags &= ~R;
 196
 197         /* Assign appropriate mask table and weight table. */
 198         cur_fld->weights = weight_tables[cur_fld->flags & (R | F)];
 199         if (cur_fld->flags & I)
 200                 cur_fld->mask = itable;
 201         else if (cur_fld->flags & D)
 202                 cur_fld->mask = dtable;
 203
 204         cur_fld->flags |= (gflag & (BI | BT));
 205         if (!cur_fld->tcol.indent)      /* BT has no meaning at end of field */
 206                 cur_fld->flags &= ~BT;
 207
 208         if (cur_fld->tcol.num
 209             && !(!(cur_fld->flags & BI) && cur_fld->flags & BT)
 210             && (cur_fld->tcol.num <= cur_fld->icol.num
 211                     /* indent if 0 -> end of field, i.e. okay */
 212                     && cur_fld->tcol.indent != 0
 213                     && cur_fld->tcol.indent < cur_fld->icol.indent))
 214                 errx(2, "fields out of order");
 215
 216         insertcol(cur_fld);
 217         return (cur_fld->tcol.num);
 218 }
 219
 220 int
 221 optval(int desc, int tcolflag)
 222 {
 223         switch(desc) {
 224         case 'b':
 225                 if (!tcolflag)
 226                         return BI;
 227                 else
 228                         return BT;
 229         case 'd': return D;
 230         case 'f': return F;
 231         case 'i': return I;
 232         case 'l': return L;
 233         case 'n': return N;
 234         case 'r': return R;
 235         default:  return 0;
 236         }
 237 }
 238
 239 /*
 240  * Return true if the options found in ARG, according to the getopt
 241  * spec in OPTS, require an additional argv word as an option
 242  * argument.
 243  */
 244 static int
 245 options_need_argument(const char *arg, const char *opts)
 246 {
 247         size_t pos;
 248         const char *s;
 249
 250         /*assert(arg[0] == '-');*/
 251
 252         pos = 1;
 253         while (arg[pos]) {
 254                 s = strchr(opts, arg[pos]);
 255                 if (s == NULL) {
 256                         /* invalid option */
 257                         return 0;
 258                 }
 259                 if (s[1] == ':') {
 260                         /* option requires argument */
 261                         if (arg[pos+1] == '\0') {
 262                                 /* no argument in this arg */
 263                                 return 1;
 264                         }
 265                         else {
 266                                 /* argument is in this arg; no more options */
 267                                 return 0;
 268                         }
 269                 }
 270                 pos++;
 271         }
 272         return 0;
 273 }
 274
 275 /*
 276  * Replace historic +SPEC arguments with appropriate -kSPEC.
 277  *
 278  * The form can be either a single +SPEC or a pair +SPEC -SPEC.
 279  * The following -SPEC is not recognized unless it follows
 280  * immediately.
 281  */
 282 void
 283 fixit(int *argc, char **argv, const char *opts)
 284 {
 285         int i, j, sawplus;
 286         char *vpos, *tpos, spec[20];
 287         int col, indent;
 288         size_t sz;
 289
 290         sawplus = 0;
 291         for (i = 1; i < *argc; i++) {
 292                 /*
 293                  * This loop must stop exactly where getopt will stop.
 294                  * Otherwise it turns e.g. "sort x +3" into "sort x
 295                  * -k4.1", which will croak if +3 was in fact really a
 296                  * file name. In order to do this reliably we need to
 297                  * be able to identify argv words that are option
 298                  * arguments.
 299                  */
 300
 301                 if (!strcmp(argv[i], "--")) {
 302                         /* End of options; stop. */
 303                         break;
 304                 }
 305
 306                 if (argv[i][0] == '+') {
 307                         /* +POS argument */
 308                         sawplus = 1;
 309                 } else if (argv[i][0] == '-' && sawplus &&
 310                            isdigit((unsigned char)argv[i][1])) {
 311                         /* -POS argument */
 312                         sawplus = 0;
 313                 } else if (argv[i][0] == '-') {
 314                         /* other option */
 315                         sawplus = 0;
 316                         if (options_need_argument(argv[i], opts)) {
 317                                 /* skip over the argument */
 318                                 i++;
 319                         }
 320                         continue;
 321                 } else {
 322                         /* not an option at all; stop */
 323                         sawplus = 0;
 324                         break;
 325                 }
 326
 327                 /*
 328                  * At this point argv[i] is an old-style spec. The
 329                  * sawplus flag used by the above loop logic also
 330                  * tells us if it's a +SPEC or -SPEC.
 331                  */
 332
 333                 /* parse spec */
 334                 tpos = argv[i]+1;
 335                 col = (int)strtol(tpos, &tpos, 10);
 336                 if (*tpos == '.') {
 337                         ++tpos;
 338                         indent = (int) strtol(tpos, &tpos, 10);
 339                 } else
 340                         indent = 0;
 341                 /* tpos now points to the optional flags */
 342
 343                 /*
 344                  * In the traditional form, x.0 means beginning of line;
 345                  * in the new form, x.0 means end of line. Adjust the
 346                  * value of INDENT accordingly.
 347                  */
 348                 if (sawplus) {
 349                         /* +POS */
 350                         col += 1;
 351                         indent += 1;
 352                 } else {
 353                         /* -POS */
 354                         if (indent > 0)
 355                                 col += 1;
 356                 }
 357
 358                 /* make the new style spec */
 359                 sz = snprintf(spec, sizeof(spec), "%d.%d%s", col, indent,
 360                     tpos);
 361
 362                 if (sawplus) {
 363                         /* Replace the +POS argument with new-style -kSPEC */
 364                         asprintf(&vpos, "-k%s", spec);
 365                         argv[i] = vpos;
 366                 } else {
 367                         /*
 368                          * Append the spec to the one from the
 369                          * preceding +POS argument, and remove the
 370                          * current argv element entirely.
 371                          */
 372                         asprintf(&vpos, "%s,%s", argv[i-1], spec);
 373                         free(argv[i-1]);
 374                         argv[i-1] = vpos;
 375                         for (j=i; j < *argc; j++)
 376                                 argv[j] = argv[j+1];
 377                         *argc -= 1;
 378                         i--;
 379                 }
 380         }
 381 }
 382
 383 /*
 384  * ascii, Rascii, Ftable, and RFtable map
 385  *
 386  * Sorting 'weight' tables.
 387  * Convert 'ascii' characters into their sort order.
 388  * The 'F' variants fold lower case to upper equivalent
 389  * The 'R' variants are for reverse sorting.
 390  *
 391  * The record separator (REC_D) never needs a weight, this frees one
 392  * byte value as an 'end of key' marker. This must be 0 for normal
 393  * weight tables, and 0xff for reverse weight tables - and is used
 394  * to terminate keys so that short keys sort before (after if reverse)
 395  * longer keys.
 396  *
 397  * The field separator has a normal weight - although it cannot occur
 398  * within a key unless it is the default (space+tab).
 399  *
 400  * All other bytes map to the appropriate value for the sort order.
 401  * Numeric sorts don't need any tables, they are reversed by negation.
 402  *
 403  * Global reverse sorts are done by writing the sorted keys in reverse
 404  * order - the sort itself is stil forwards.
 405  * This means that weights are only ever used when generating keys, any
 406  * sort of the original data bytes is always forwards and unweighted.
 407  *
 408  * Note: this is only good for ASCII sorting.  For different LC 's,
 409  * all bets are off.
 410  *
 411  * itable[] and dtable[] are the masks for -i (ignore non-printables)
 412  * and -d (only sort blank and alphanumerics).
 413  */
 414 void
 415 settables(void)
 416 {
 417         int i;
 418         int next_weight = 1;
 419         int rev_weight = 254;
 420
 421         ascii[REC_D] = 0;
 422         Rascii[REC_D] = 255;
 423         Ftable[REC_D] = 0;
 424         RFtable[REC_D] = 255;
 425
 426         for (i = 0; i < 256; i++) {
 427                 if (i == REC_D)
 428                         continue;
 429                 ascii[i] = next_weight;
 430                 Rascii[i] = rev_weight;
 431                 if (Ftable[i] == 0) {
 432                         Ftable[i] = next_weight;
 433                         RFtable[i] = rev_weight;
 434                         Ftable[tolower(i)] = next_weight;
 435                         RFtable[tolower(i)] = rev_weight;
 436                 }
 437                 next_weight++;
 438                 rev_weight--;
 439
 440                 if (i == '\n' || isprint(i))
 441                         itable[i] = 1;
 442
 443                 if (i == '\n' || i == '\t' || i == ' ' || isalnum(i))
 444                         dtable[i] = 1;
 445         }
 446 }