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