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