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