usr.bin/join/join.c

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