usr.bin/join/join.c

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