usr.bin/join/join.c

   1 /*      $NetBSD: join.c,v 1.29 2008/07/21 14:19:23 lukem Exp $  */
   2
   3 /*-
   4  * Copyright (c) 1991 The Regents of the University of California.
   5  * All rights reserved.
   6  *
   7  * This code is derived from software contributed to Berkeley by
   8  * Steve Hayman of Indiana University, Michiro Hikida and David
   9  * Goodenough.
  10  *
  11  * Redistribution and use in source and binary forms, with or without
  12  * modification, are permitted provided that the following conditions
  13  * are met:
  14  * 1. Redistributions of source code must retain the above copyright
  15  *    notice, this list of conditions and the following disclaimer.
  16  * 2. Redistributions in binary form must reproduce the above copyright
  17  *    notice, this list of conditions and the following disclaimer in the
  18  *    documentation and/or other materials provided with the distribution.
  19  * 3. Neither the name of the University nor the names of its contributors
  20  *    may be used to endorse or promote products derived from this software
  21  *    without specific prior written permission.
  22  *
  23  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  24  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  25  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  26  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  27  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  28  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  29  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  30  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  31  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  32  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  33  * SUCH DAMAGE.
  34  */
  35
  36 #if HAVE_NBTOOL_CONFIG_H
  37 #include "nbtool_config.h"
  38 #endif
  39
  40 #include <sys/cdefs.h>
  41 #ifndef lint
  42 __COPYRIGHT("@(#) Copyright (c) 1991\
  43  The Regents of the University of California.  All rights reserved.");
  44 #endif /* not lint */
  45
  46 #ifndef lint
  47 #if 0
  48 static char sccsid[] = "from: @(#)join.c        5.1 (Berkeley) 11/18/91";
  49 #else
  50 __RCSID("$NetBSD: join.c,v 1.29 2008/07/21 14:19:23 lukem Exp $");
  51 #endif
  52 #endif /* not lint */
  53
  54 #include <sys/types.h>
  55 #include <ctype.h>
  56 #include <err.h>
  57 #include <errno.h>
  58 #include <stdio.h>
  59 #include <stdlib.h>
  60 #include <string.h>
  61 #include <unistd.h>
  62
  63 /*
  64  * There's a structure per input file which encapsulates the state of the
  65  * file.  We repeatedly read lines from each file until we've read in all
  66  * the consecutive lines from the file with a common join field.  Then we
  67  * compare the set of lines with an equivalent set from the other file.
  68  */
  69 typedef struct {
  70         char *line;             /* line */
  71         u_long linealloc;       /* line allocated count */
  72         char **fields;          /* line field(s) */
  73         u_long fieldcnt;        /* line field(s) count */
  74         u_long fieldalloc;      /* line field(s) allocated count */
  75 } LINE;
  76
  77 char nolineline[1] = { '\0' };
  78 LINE noline = {nolineline, 0, 0, 0, 0}; /* arg for outfield if no line to output */
  79
  80 typedef struct {
  81         FILE *fp;               /* file descriptor */
  82         u_long joinf;           /* join field (-1, -2, -j) */
  83         int unpair;             /* output unpairable lines (-a) */
  84         int number;             /* 1 for file 1, 2 for file 2 */
  85
  86         LINE *set;              /* set of lines with same field */
  87         u_long pushback;        /* line on the stack */
  88         u_long setcnt;          /* set count */
  89         u_long setalloc;        /* set allocated count */
  90 } INPUT;
  91 INPUT input1 = { NULL, 0, 0, 1, NULL, -1, 0, 0, },
  92       input2 = { NULL, 0, 0, 2, NULL, -1, 0, 0, };
  93
  94 typedef struct {
  95         u_long  fileno;         /* file number */
  96         u_long  fieldno;        /* field number */
  97 } OLIST;
  98 OLIST *olist;                   /* output field list */
  99 u_long olistcnt;                /* output field list count */
 100 u_long olistalloc;              /* output field allocated count */
 101
 102 int joinout = 1;                /* show lines with matched join fields (-v) */
 103 int needsep;                    /* need separator character */
 104 int spans = 1;                  /* span multiple delimiters (-t) */
 105 char *empty;                    /* empty field replacement string (-e) */
 106 const char *tabchar = " \t";    /* delimiter characters (-t) */
 107
 108 int  cmp(LINE *, u_long, LINE *, u_long);
 109 void enomem(void);
 110 void fieldarg(char *);
 111 void joinlines(INPUT *, INPUT *);
 112 int  main(int, char **);
 113 void obsolete(char **);
 114 void outfield(LINE *, u_long);
 115 void outoneline(INPUT *, LINE *);
 116 void outtwoline(INPUT *, LINE *, INPUT *, LINE *);
 117 void slurp(INPUT *);
 118 void usage(void);
 119
 120 int
 121 main(int argc, char *argv[])
 122 {
 123         INPUT *F1, *F2;
 124         int aflag, ch, cval, vflag;
 125         char *end;
 126
 127         F1 = &input1;
 128         F2 = &input2;
 129
 130         aflag = vflag = 0;
 131         obsolete(argv);
 132         while ((ch = getopt(argc, argv, "\01a:e:j:1:2:o:t:v:")) != -1) {
 133                 switch (ch) {
 134                 case '\01':
 135                         aflag = 1;
 136                         F1->unpair = F2->unpair = 1;
 137                         break;
 138                 case '1':
 139                         if ((F1->joinf = strtol(optarg, &end, 10)) < 1) {
 140                                 warnx("-1 option field number less than 1");
 141                                 usage();
 142                         }
 143                         if (*end) {
 144                                 warnx("illegal field number -- %s", optarg);
 145                                 usage();
 146                         }
 147                         --F1->joinf;
 148                         break;
 149                 case '2':
 150                         if ((F2->joinf = strtol(optarg, &end, 10)) < 1) {
 151                                 warnx("-2 option field number less than 1");
 152                                 usage();
 153                         }
 154                         if (*end) {
 155                                 warnx("illegal field number -- %s", optarg);
 156                                 usage();
 157                         }
 158                         --F2->joinf;
 159                         break;
 160                 case 'a':
 161                         aflag = 1;
 162                         switch(strtol(optarg, &end, 10)) {
 163                         case 1:
 164                                 F1->unpair = 1;
 165                                 break;
 166                         case 2:
 167                                 F2->unpair = 1;
 168                                 break;
 169                         default:
 170                                 warnx("-a option file number not 1 or 2");
 171                                 usage();
 172                                 break;
 173                         }
 174                         if (*end) {
 175                                 warnx("illegal file number -- %s", optarg);
 176                                 usage();
 177                         }
 178                         break;
 179                 case 'e':
 180                         empty = optarg;
 181                         break;
 182                 case 'j':
 183                         if ((F1->joinf = F2->joinf =
 184                             strtol(optarg, &end, 10)) < 1) {
 185                                 warnx("-j option field number less than 1");
 186                                 usage();
 187                         }
 188                         if (*end) {
 189                                 warnx("illegal field number -- %s", optarg);
 190                                 usage();
 191                         }
 192                         --F1->joinf;
 193                         --F2->joinf;
 194                         break;
 195                 case 'o':
 196                         fieldarg(optarg);
 197                         break;
 198                 case 't':
 199                         spans = 0;
 200                         if (strlen(tabchar = optarg) != 1) {
 201                                 warnx("illegal tab character specification");
 202                                 usage();
 203                         }
 204                         break;
 205                 case 'v':
 206                         vflag = 1;
 207                         joinout = 0;
 208                         switch(strtol(optarg, &end, 10)) {
 209                         case 1:
 210                                 F1->unpair = 1;
 211                                 break;
 212                         case 2:
 213                                 F2->unpair = 1;
 214                                 break;
 215                         default:
 216                                 warnx("-v option file number not 1 or 2");
 217                                 usage();
 218                                 break;
 219                         }
 220                         if (*end) {
 221                                 warnx("illegal file number -- %s", optarg);
 222                                 usage();
 223                         }
 224                         break;
 225                 case '?':
 226                 default:
 227                         usage();
 228                 }
 229         }
 230         argc -= optind;
 231         argv += optind;
 232
 233         if (aflag && vflag)
 234                 errx(1, "-a and -v options mutually exclusive");
 235
 236         if (argc != 2)
 237                 usage();
 238
 239         /* Open the files; "-" means stdin. */
 240         if (!strcmp(*argv, "-"))
 241                 F1->fp = stdin;
 242         else if ((F1->fp = fopen(*argv, "r")) == NULL)
 243                 err(1, "%s", *argv);
 244         ++argv;
 245         if (!strcmp(*argv, "-"))
 246                 F2->fp = stdin;
 247         else if ((F2->fp = fopen(*argv, "r")) == NULL)
 248                 err(1, "%s", *argv);
 249         if (F1->fp == stdin && F2->fp == stdin)
 250                 errx(1, "only one input file may be stdin");
 251
 252         slurp(F1);
 253         slurp(F2);
 254         while (F1->setcnt && F2->setcnt) {
 255                 cval = cmp(F1->set, F1->joinf, F2->set, F2->joinf);
 256                 if (cval == 0) {
 257                         /* Oh joy, oh rapture, oh beauty divine! */
 258                         if (joinout)
 259                                 joinlines(F1, F2);
 260                         slurp(F1);
 261                         slurp(F2);
 262                 } else if (cval < 0) {
 263                         /* File 1 takes the lead... */
 264                         if (F1->unpair)
 265                                 joinlines(F1, NULL);
 266                         slurp(F1);
 267                 } else {
 268                         /* File 2 takes the lead... */
 269                         if (F2->unpair)
 270                                 joinlines(F2, NULL);
 271                         slurp(F2);
 272                 }
 273         }
 274
 275         /*
 276          * Now that one of the files is used up, optionally output any
 277          * remaining lines from the other file.
 278          */
 279         if (F1->unpair)
 280                 while (F1->setcnt) {
 281                         joinlines(F1, NULL);
 282                         slurp(F1);
 283                 }
 284         if (F1->fp != stdin)
 285                 fclose(F1->fp);
 286
 287         if (F2->unpair)
 288                 while (F2->setcnt) {
 289                         joinlines(F2, NULL);
 290                         slurp(F2);
 291                 }
 292         if (F2->fp != stdin)
 293                 fclose(F2->fp);
 294
 295         return 0;
 296 }
 297
 298 void
 299 slurp(INPUT *F)
 300 {
 301         LINE *lp;
 302         LINE tmp;
 303         LINE *nline;
 304         size_t len;
 305         u_long cnt;
 306         char *bp, *fieldp;
 307         u_long nsize;
 308
 309         /*
 310          * Read all of the lines from an input file that have the same
 311          * join field.
 312          */
 313         for (F->setcnt = 0;; ++F->setcnt) {
 314                 /*
 315                  * If we're out of space to hold line structures, allocate
 316                  * more.  Initialize the structure so that we know that this
 317                  * is new space.
 318                  */
 319                 if (F->setcnt == F->setalloc) {
 320                         cnt = F->setalloc;
 321                         if (F->setalloc == 0)
 322                                 nsize = 64;
 323                         else
 324                                 nsize = F->setalloc << 1;
 325                         if ((nline = realloc(F->set,
 326                             nsize * sizeof(LINE))) == NULL)
 327                                 enomem();
 328                         F->set = nline;
 329                         F->setalloc = nsize;
 330                         memset(F->set + cnt, 0,
 331                             (F->setalloc - cnt) * sizeof(LINE));
 332                 }
 333
 334                 /*
 335                  * Get any pushed back line, else get the next line.  Allocate
 336                  * space as necessary.  If taking the line from the stack swap
 337                  * the two structures so that we don't lose the allocated space.
 338                  * This could be avoided by doing another level of indirection,
 339                  * but it's probably okay as is.
 340                  */
 341                 lp = &F->set[F->setcnt];
 342                 if (F->pushback != (u_long)-1) {
 343                         tmp = F->set[F->setcnt];
 344                         F->set[F->setcnt] = F->set[F->pushback];
 345                         F->set[F->pushback] = tmp;
 346                         F->pushback = (u_long)-1;
 347                         continue;
 348                 }
 349                 if ((bp = fgetln(F->fp, &len)) == NULL)
 350                         return;
 351                 if (lp->linealloc <= len + 1) {
 352                         char *n;
 353
 354                         if (lp->linealloc == 0)
 355                                 nsize = 128;
 356                         else
 357                                 nsize = lp->linealloc;
 358                         while (nsize <= len + 1)
 359                                 nsize <<= 1;
 360                         if ((n = realloc(lp->line,
 361                             nsize * sizeof(char))) == NULL)
 362                                 enomem();
 363                         lp->line = n;
 364                         lp->linealloc = nsize;
 365                 }
 366                 memmove(lp->line, bp, len);
 367
 368                 /* Replace trailing newline, if it exists. */
 369                 if (bp[len - 1] == '\n')
 370                         lp->line[len - 1] = '\0';
 371                 else
 372                         lp->line[len] = '\0';
 373                 bp = lp->line;
 374
 375                 /* Split the line into fields, allocate space as necessary. */
 376                 lp->fieldcnt = 0;
 377                 while ((fieldp = strsep(&bp, tabchar)) != NULL) {
 378                         if (spans && *fieldp == '\0')
 379                                 continue;
 380                         if (lp->fieldcnt == lp->fieldalloc) {
 381                                 char **n;
 382
 383                                 if (lp->fieldalloc == 0)
 384                                         nsize = 16;
 385                                 else
 386                                         nsize = lp->fieldalloc << 1;
 387                                 if ((n = realloc(lp->fields,
 388                                     nsize * sizeof(char *))) == NULL)
 389                                         enomem();
 390                                 lp->fields = n;
 391                                 lp->fieldalloc = nsize;
 392                         }
 393                         lp->fields[lp->fieldcnt++] = fieldp;
 394                 }
 395
 396                 /* See if the join field value has changed. */
 397                 if (F->setcnt && cmp(lp, F->joinf, lp - 1, F->joinf)) {
 398                         F->pushback = F->setcnt;
 399                         break;
 400                 }
 401         }
 402 }
 403
 404 int
 405 cmp(LINE *lp1, u_long fieldno1, LINE *lp2, u_long fieldno2)
 406 {
 407
 408         if (lp1->fieldcnt <= fieldno1)
 409                 return (lp2->fieldcnt <= fieldno2 ? 0 : 1);
 410         if (lp2->fieldcnt <= fieldno2)
 411                 return (-1);
 412         return (strcmp(lp1->fields[fieldno1], lp2->fields[fieldno2]));
 413 }
 414
 415 void
 416 joinlines(INPUT *F1, INPUT *F2)
 417 {
 418         u_long cnt1, cnt2;
 419
 420         /*
 421          * Output the results of a join comparison.  The output may be from
 422          * either file 1 or file 2 (in which case the first argument is the
 423          * file from which to output) or from both.
 424          */
 425         if (F2 == NULL) {
 426                 for (cnt1 = 0; cnt1 < F1->setcnt; ++cnt1)
 427                         outoneline(F1, &F1->set[cnt1]);
 428                 return;
 429         }
 430         for (cnt1 = 0; cnt1 < F1->setcnt; ++cnt1)
 431                 for (cnt2 = 0; cnt2 < F2->setcnt; ++cnt2)
 432                         outtwoline(F1, &F1->set[cnt1], F2, &F2->set[cnt2]);
 433 }
 434
 435 void
 436 outoneline(INPUT *F, LINE *lp)
 437 {
 438         u_long cnt;
 439
 440         /*
 441          * Output a single line from one of the files, according to the
 442          * join rules.  This happens when we are writing unmatched single
 443          * lines.  Output empty fields in the right places.
 444          */
 445         if (olist)
 446                 for (cnt = 0; cnt < olistcnt; ++cnt) {
 447                         if (olist[cnt].fileno == (u_long)F->number)
 448                                 outfield(lp, olist[cnt].fieldno);
 449                         else
 450                                 outfield(&noline, 1);
 451                 }
 452         else
 453                 for (cnt = 0; cnt < lp->fieldcnt; ++cnt)
 454                         outfield(lp, cnt);
 455         (void)printf("\n");
 456         if (ferror(stdout))
 457                 err(1, "stdout");
 458         needsep = 0;
 459 }
 460
 461 void
 462 outtwoline(INPUT *F1, LINE *lp1, INPUT *F2, LINE *lp2)
 463 {
 464         u_long cnt;
 465
 466         /* Output a pair of lines according to the join list (if any). */
 467         if (olist) {
 468                 for (cnt = 0; cnt < olistcnt; ++cnt)
 469                         if (olist[cnt].fileno == 1)
 470                                 outfield(lp1, olist[cnt].fieldno);
 471                         else /* if (olist[cnt].fileno == 2) */
 472                                 outfield(lp2, olist[cnt].fieldno);
 473         } else {
 474                 /*
 475                  * Output the join field, then the remaining fields from F1
 476                  * and F2.
 477                  */
 478                 outfield(lp1, F1->joinf);
 479                 for (cnt = 0; cnt < lp1->fieldcnt; ++cnt)
 480                         if (F1->joinf != cnt)
 481                                 outfield(lp1, cnt);
 482                 for (cnt = 0; cnt < lp2->fieldcnt; ++cnt)
 483                         if (F2->joinf != cnt)
 484                                 outfield(lp2, cnt);
 485         }
 486         (void)printf("\n");
 487         if (ferror(stdout))
 488                 err(1, "stdout");
 489         needsep = 0;
 490 }
 491
 492 void
 493 outfield(LINE *lp, u_long fieldno)
 494 {
 495         if (needsep++)
 496                 (void)printf("%c", *tabchar);
 497         if (!ferror(stdout)) {
 498                 if (lp->fieldcnt <= fieldno) {
 499                         if (empty != NULL)
 500                                 (void)printf("%s", empty);
 501                 } else {
 502                         if (*lp->fields[fieldno] == '\0')
 503                                 return;
 504                         (void)printf("%s", lp->fields[fieldno]);
 505                 }
 506         }
 507         if (ferror(stdout))
 508                 err(1, "stdout");
 509 }
 510
 511 /*
 512  * Convert an output list argument "2.1, 1.3, 2.4" into an array of output
 513  * fields.
 514  */
 515 void
 516 fieldarg(char *option)
 517 {
 518         u_long fieldno;
 519         char *end, *token;
 520         OLIST *n;
 521
 522         while ((token = strsep(&option, ", \t")) != NULL) {
 523                 if (*token == '\0')
 524                         continue;
 525                 if ((token[0] != '1' && token[0] != '2') || token[1] != '.')
 526                         errx(1, "malformed -o option field");
 527                 fieldno = strtol(token + 2, &end, 10);
 528                 if (*end)
 529                         errx(1, "malformed -o option field");
 530                 if (fieldno == 0)
 531                         errx(1, "field numbers are 1 based");
 532                 if (olistcnt == olistalloc) {
 533                         if ((n = realloc(olist,
 534                             (olistalloc + 50) * sizeof(OLIST))) == NULL)
 535                                 enomem();
 536                         olist = n;
 537                         olistalloc += 50;
 538                 }
 539                 olist[olistcnt].fileno = token[0] - '0';
 540                 olist[olistcnt].fieldno = fieldno - 1;
 541                 ++olistcnt;
 542         }
 543 }
 544
 545 void
 546 obsolete(char **argv)
 547 {
 548         size_t len;
 549         char **p, *ap, *t;
 550
 551         while ((ap = *++argv) != NULL) {
 552                 /* Return if "--". */
 553                 if (ap[0] == '-' && ap[1] == '-')
 554                         return;
 555                 switch (ap[1]) {
 556                 case 'a':
 557                         /*
 558                          * The original join allowed "-a", which meant the
 559                          * same as -a1 plus -a2.  POSIX 1003.2, Draft 11.2
 560                          * only specifies this as "-a 1" and "a -2", so we
 561                          * have to use another option flag, one that is
 562                          * unlikely to ever be used or accidentally entered
 563                          * on the command line.  (Well, we could reallocate
 564                          * the argv array, but that hardly seems worthwhile.)
 565                          */
 566                         if (ap[2] == '\0')
 567                                 ap[1] = '\01';
 568                         break;
 569                 case 'j':
 570                         /*
 571                          * The original join allowed "-j[12] arg" and "-j arg".
 572                          * Convert the former to "-[12] arg".  Don't convert
 573                          * the latter since getopt(3) can handle it.
 574                          */
 575                         switch(ap[2]) {
 576                         case '1':
 577                                 if (ap[3] != '\0')
 578                                         goto jbad;
 579                                 ap[1] = '1';
 580                                 ap[2] = '\0';
 581                                 break;
 582                         case '2':
 583                                 if (ap[3] != '\0')
 584                                         goto jbad;
 585                                 ap[1] = '2';
 586                                 ap[2] = '\0';
 587                                 break;
 588                         case '\0':
 589                                 break;
 590                         default:
 591 jbad:                           errx(1, "illegal option -- %s", ap);
 592                                 usage();
 593                         }
 594                         break;
 595                 case 'o':
 596                         /*
 597                          * The original join allowed "-o arg arg".  Convert to
 598                          * "-o arg -o arg".
 599                          */
 600                         if (ap[2] != '\0')
 601                                 break;
 602                         for (p = argv + 2; *p; ++p) {
 603                                 if ((p[0][0] != '1' && p[0][0] != '2') ||
 604                                     p[0][1] != '.')
 605                                         break;
 606                                 len = strlen(*p);
 607                                 if (len - 2 != strspn(*p + 2, "0123456789"))
 608                                         break;
 609                                 if ((t = malloc(len + 3)) == NULL)
 610                                         enomem();
 611                                 t[0] = '-';
 612                                 t[1] = 'o';
 613                                 memmove(t + 2, *p, len + 1);
 614                                 *p = t;
 615                         }
 616                         argv = p - 1;
 617                         break;
 618                 }
 619         }
 620 }
 621
 622 void
 623 enomem(void)
 624 {
 625         errx(1, "no memory");
 626 }
 627
 628 void
 629 usage(void)
 630 {
 631         (void)fprintf(stderr,
 632             "usage: %s [-a fileno | -v fileno] [-e string] [-j fileno field]\n"
 633             "            [-o list] [-t char] [-1 field] [-2 field] file1 file2\n",
 634             getprogname());
 635         exit(1);
 636 }