Import join from OpenBSD

join is in GNU coreutils, but not in Busybox. It is needed by GNUlib,
which is needed in turn to build coreutils.

Extracting join from coreutils is a huge task, but the BSD implementation
is very clean so we can use it to break the circular dependency.

1 files changed, 679 insertions, 0 deletions

diff --git a/join.c b/join.c
new file mode 100644
index 0000000..4fa6c21
--- /dev/null
+++ b/join.c
@@ -0,0 +1,679 @@
+/* $OpenBSD: join.c,v 1.21 2009/10/27 23:59:39 deraadt Exp $    */
+
+/*-
+ * Copyright (c) 1991, 1993, 1994
+ *  The Regents of the University of California.  All rights reserved.
+ *
+ * This code is derived from software contributed to Berkeley by
+ * Steve Hayman of the Computer Science Department, Indiana University,
+ * Michiro Hikida and David Goodenough.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. Neither the name of the University nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#include <sys/param.h>
+
+#include <err.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+/* Required for Baserock build */
+
+#include <getopt.h>
+
+char *fgetln(FILE *stream, size_t *p_len) {
+    static char *buffer = NULL;
+    static size_t buffer_len = 0;
+    size_t len;
+    char c;
+
+    len = 0;
+    while(1) {
+        if (feof(stream)) {
+            *p_len = len;
+            return len == 0? NULL : buffer;
+        }
+
+        c = fgetc(stream);
+        if (c == '\n' || c == -1) {
+            *p_len = len;
+            return len == 0? NULL: buffer;
+        }
+
+        if (len >= buffer_len) {
+            buffer_len = buffer_len==0? 80: buffer_len*2;
+            buffer = realloc(buffer, buffer_len);
+        }
+        buffer[len] = c;
+        len ++;
+    }
+}
+
+/* End of Baserock fluff */
+
+/*
+ * There's a structure per input file which encapsulates the state of the
+ * file.  We repeatedly read lines from each file until we've read in all
+ * the consecutive lines from the file with a common join field.  Then we
+ * compare the set of lines with an equivalent set from the other file.
+ */
+typedef struct {
+    char *line;         /* line */
+    u_long linealloc;       /* line allocated count */
+    char **fields;          /* line field(s) */
+    u_long fieldcnt;        /* line field(s) count */
+    u_long fieldalloc;      /* line field(s) allocated count */
+    u_long cfieldc;         /* current field count */
+    long     fpos;          /* fpos of start of field */
+} LINE;
+
+typedef struct {
+    FILE *fp;           /* file descriptor */
+    u_long joinf;           /* join field (-1, -2, -j) */
+    int unpair;         /* output unpairable lines (-a) */
+    u_long number;          /* 1 for file 1, 2 for file 2 */
+    LINE *set;          /* set of lines with same field */
+    int pushbool;           /* if pushback is set */
+    u_long pushback;        /* line on the stack */
+    u_long setcnt;          /* set count */
+    u_long setalloc;        /* set allocated count */
+    u_long setusedc;        /* sets used  */
+} INPUT;
+INPUT input1 = { NULL, 0, 0, 1, NULL, 0, 0, 0, 0, 0 },
+      input2 = { NULL, 0, 0, 2, NULL, 0, 0, 0, 0, 0 };
+
+typedef struct {
+    u_long  filenum;    /* file number */
+    u_long  fieldno;    /* field number */
+} OLIST;
+OLIST *olist;           /* output field list */
+u_long olistcnt;        /* output field list count */
+u_long olistalloc;      /* output field allocated count */
+
+int joinout = 1;        /* show lines with matched join fields (-v) */
+int needsep;            /* need separator character */
+int spans = 1;          /* span multiple delimiters (-t) */
+char *empty;            /* empty field replacement string (-e) */
+char *tabchar = " \t";      /* delimiter characters (-t) */
+
+int  cmp(LINE *, u_long, LINE *, u_long);
+void fieldarg(char *);
+void joinlines(INPUT *, INPUT *);
+void obsolete(char **);
+void outfield(LINE *, u_long, int);
+void outoneline(INPUT *, LINE *);
+void outtwoline(INPUT *, LINE *, INPUT *, LINE *);
+void slurp(INPUT *);
+void slurpit(INPUT *);
+void usage(void);
+
+int
+main(int argc, char *argv[])
+{
+    INPUT *F1, *F2;
+    int aflag, ch, cval, vflag;
+    char *end;
+
+    F1 = &input1;
+    F2 = &input2;
+
+    aflag = vflag = 0;
+    obsolete(argv);
+    while ((ch = getopt(argc, argv, "\01a:e:j:1:2:o:t:v:")) != -1) {
+        switch (ch) {
+        case '\01':     /* See comment in obsolete(). */
+            aflag = 1;
+            F1->unpair = F2->unpair = 1;
+            break;
+        case '1':
+            if ((F1->joinf = strtol(optarg, &end, 10)) < 1)
+                errx(1, "-1 option field number less than 1");
+            if (*end)
+                errx(1, "illegal field number -- %s", optarg);
+            --F1->joinf;
+            break;
+        case '2':
+            if ((F2->joinf = strtol(optarg, &end, 10)) < 1)
+                errx(1, "-2 option field number less than 1");
+            if (*end)
+                errx(1, "illegal field number -- %s", optarg);
+            --F2->joinf;
+            break;
+        case 'a':
+            aflag = 1;
+            switch(strtol(optarg, &end, 10)) {
+            case 1:
+                F1->unpair = 1;
+                break;
+            case 2:
+                F2->unpair = 1;
+                break;
+            default:
+                errx(1, "-a option file number not 1 or 2");
+                break;
+            }
+            if (*end)
+                errx(1, "illegal file number -- %s", optarg);
+            break;
+        case 'e':
+            empty = optarg;
+            break;
+        case 'j':
+            if ((F1->joinf = F2->joinf = strtol(optarg, &end, 10)) < 1)
+                errx(1, "-j option field number less than 1");
+            if (*end)
+                errx(1, "illegal field number -- %s", optarg);
+            --F1->joinf;
+            --F2->joinf;
+            break;
+        case 'o':
+            fieldarg(optarg);
+            break;
+        case 't':
+            spans = 0;
+            if (strlen(tabchar = optarg) != 1)
+                errx(1, "illegal tab character specification");
+            break;
+        case 'v':
+            vflag = 1;
+            joinout = 0;
+            switch (strtol(optarg, &end, 10)) {
+            case 1:
+                F1->unpair = 1;
+                break;
+            case 2:
+                F2->unpair = 1;
+                break;
+            default:
+                errx(1, "-v option file number not 1 or 2");
+                break;
+            }
+            if (*end)
+                errx(1, "illegal file number -- %s", optarg);
+            break;
+        case '?':
+        default:
+            usage();
+        }
+    }
+    argc -= optind;
+    argv += optind;
+
+    if (aflag && vflag)
+        errx(1, "the -a and -v options are mutually exclusive");
+
+    if (argc != 2)
+        usage();
+
+    /* Open the files; "-" means stdin. */
+    if (!strcmp(*argv, "-"))
+        F1->fp = stdin;
+    else if ((F1->fp = fopen(*argv, "r")) == NULL)
+        err(1, "%s", *argv);
+    ++argv;
+    if (!strcmp(*argv, "-"))
+        F2->fp = stdin;
+    else if ((F2->fp = fopen(*argv, "r")) == NULL)
+        err(1, "%s", *argv);
+    if (F1->fp == stdin && F2->fp == stdin)
+        errx(1, "only one input file may be stdin");
+
+    F1->setusedc = 0;
+    F2->setusedc = 0;
+    slurp(F1);
+    slurp(F2);
+    F1->set->cfieldc = 0;
+    F2->set->cfieldc = 0;
+
+    /*
+     * We try to let the files have the same field value, advancing
+     * whoever falls behind and always advancing the file(s) we output
+     * from.
+    */
+    while (F1->setcnt && F2->setcnt) {
+        cval = cmp(F1->set, F1->joinf, F2->set, F2->joinf);
+        if (cval == 0) {
+            /* Oh joy, oh rapture, oh beauty divine! */
+            if (joinout)
+                joinlines(F1, F2);
+            slurp(F1);
+            slurp(F2);
+        }
+        else {
+            if (F1->unpair
+            && (cval < 0 || F2->set->cfieldc == F2->setusedc -1)) {
+                joinlines(F1, NULL);
+                slurp(F1);
+            }
+            else if (cval < 0)  
+                /* File 1 takes the lead... */
+                slurp(F1);
+            if (F2->unpair
+            && (cval > 0 || F1->set->cfieldc == F1->setusedc -1)) {
+                joinlines(F2, NULL);
+                slurp(F2);
+            }
+            else if (cval > 0)
+                /* File 2 takes the lead... */
+                slurp(F2);
+        }
+    }
+
+    /*
+     * Now that one of the files is used up, optionally output any
+     * remaining lines from the other file.
+     */
+    if (F1->unpair)
+        while (F1->setcnt) {
+            joinlines(F1, NULL);
+            slurp(F1);
+        }
+    if (F2->unpair)
+        while (F2->setcnt) {
+            joinlines(F2, NULL);
+            slurp(F2);
+        }
+
+    return 0;
+}
+
+/* wrapper around slurpit() to keep track of what field we are on */
+void slurp(INPUT *F)
+{
+    long fpos;
+    u_long cfieldc;
+
+    if (F->set == NULL) {
+        fpos = 0;
+        cfieldc = 0;    
+    }
+    else {
+        fpos = F->set->fpos;
+        cfieldc = F->set->cfieldc;
+    }
+    slurpit(F);
+    if (F->set == NULL)
+        return;
+    else if (fpos != F->set->fpos)
+        F->set->cfieldc = cfieldc+1;
+}   
+
+void
+slurpit(INPUT *F)
+{
+    LINE *lp, *lastlp, tmp;
+    size_t len;
+    u_long cnt;
+    char *bp, *fieldp;
+    long fpos;
+    /*
+     * Read all of the lines from an input file that have the same
+     * join field.
+     */
+
+    F->setcnt = 0;
+    for (lastlp = NULL; ; ++F->setcnt, lastlp = lp) {
+        /*
+         * If we're out of space to hold line structures, allocate
+         * more.  Initialize the structure so that we know that this
+         * is new space.
+         */
+        if (F->setcnt == F->setalloc) {
+            LINE *p;
+            u_long newsize = F->setalloc + 50;
+            cnt = F->setalloc;
+            if ((p = realloc(F->set,
+                newsize * sizeof(LINE))) == NULL)
+                err(1, NULL);
+            F->set = p;
+            F->setalloc = newsize;
+            memset(F->set + cnt, 0, 50 * sizeof(LINE));
+            /* re-set lastlp in case it moved */
+            if (lastlp != NULL)
+                lastlp = &F->set[F->setcnt - 1];
+        }
+        /*
+         * Get any pushed back line, else get the next line.  Allocate
+         * space as necessary.  If taking the line from the stack swap
+         * the two structures so that we don't lose space allocated to
+         * either structure.  This could be avoided by doing another
+         * level of indirection, but it's probably okay as is.
+         */
+        lp = &F->set[F->setcnt];
+        if (F->pushbool) {
+            tmp = F->set[F->setcnt];
+            F->set[F->setcnt] = F->set[F->pushback];
+            F->set[F->pushback] = tmp;
+            F->pushbool = 0;
+            continue;
+        }
+        if ((bp = fgetln(F->fp, &len)) == NULL)
+            return;
+        /*
+         * we depend on knowing on what field we are, one safe way is
+         * the file position.
+        */
+        fpos = ftell(F->fp) - len;
+        if (lp->linealloc <= len + 1) {
+            char *p;
+            u_long newsize = lp->linealloc +
+                MAX(100, len + 1 - lp->linealloc);
+            if ((p = realloc(lp->line, newsize)) == NULL)
+                err(1, NULL);
+            lp->line = p;
+            lp->linealloc = newsize;
+        }
+        F->setusedc++;
+        memmove(lp->line, bp, len);
+        lp->fpos = fpos;
+        /* Replace trailing newline, if it exists. */
+        if (bp[len - 1] == '\n')
+            lp->line[len - 1] = '\0';
+        else
+            lp->line[len] = '\0';
+        bp = lp->line;
+
+        /* Split the line into fields, allocate space as necessary. */
+        lp->fieldcnt = 0;
+        while ((fieldp = strsep(&bp, tabchar)) != NULL) {
+            if (spans && *fieldp == '\0')
+                continue;
+            if (lp->fieldcnt == lp->fieldalloc) {
+                char **p;
+                u_long newsize = lp->fieldalloc + 50;
+                if ((p = realloc(lp->fields,
+                    newsize * sizeof(char *))) == NULL)
+                    err(1, NULL);
+                lp->fields = p;
+                lp->fieldalloc = newsize;
+            }
+            lp->fields[lp->fieldcnt++] = fieldp;
+        }
+
+        /* See if the join field value has changed. */
+        if (lastlp != NULL && cmp(lp, F->joinf, lastlp, F->joinf)) {
+            F->pushbool = 1;
+            F->pushback = F->setcnt;
+            break;
+        }
+    }
+}
+
+int
+cmp(LINE *lp1, u_long fieldno1, LINE *lp2, u_long fieldno2)
+{
+    if (lp1->fieldcnt <= fieldno1)
+        return (-1);
+    else if (lp2->fieldcnt <= fieldno2)
+        return (1);
+    return (strcmp(lp1->fields[fieldno1], lp2->fields[fieldno2]));
+}
+
+void
+joinlines(INPUT *F1, INPUT *F2)
+{
+    u_long cnt1, cnt2;
+
+    /*
+     * Output the results of a join comparison.  The output may be from
+     * either file 1 or file 2 (in which case the first argument is the
+     * file from which to output) or from both.
+     */
+    if (F2 == NULL) {
+        for (cnt1 = 0; cnt1 < F1->setcnt; ++cnt1)
+            outoneline(F1, &F1->set[cnt1]);
+        return;
+    }
+    for (cnt1 = 0; cnt1 < F1->setcnt; ++cnt1)
+        for (cnt2 = 0; cnt2 < F2->setcnt; ++cnt2)
+            outtwoline(F1, &F1->set[cnt1], F2, &F2->set[cnt2]);
+}
+
+void
+outoneline(INPUT *F, LINE *lp)
+{
+    u_long cnt;
+
+    /*
+     * Output a single line from one of the files, according to the
+     * join rules.  This happens when we are writing unmatched single
+     * lines.  Output empty fields in the right places.
+     */
+    if (olist)
+        for (cnt = 0; cnt < olistcnt; ++cnt) {
+            if (olist[cnt].filenum == F->number)
+                outfield(lp, olist[cnt].fieldno, 0);
+            else if (olist[cnt].filenum == 0)
+                outfield(lp, F->joinf, 0);
+            else
+                outfield(lp, 0, 1);
+        }
+    else {
+        /*
+         * Output the join field, then the remaining fields from F
+         */
+        outfield(lp, F->joinf, 0);
+        for (cnt = 0; cnt < lp->fieldcnt; ++cnt)
+            if (F->joinf != cnt)
+                outfield(lp, cnt, 0);
+    }
+
+    putchar('\n');
+    if (ferror(stdout))
+        err(1, "stdout");
+    needsep = 0;
+}
+
+void
+outtwoline(INPUT *F1, LINE *lp1, INPUT *F2, LINE *lp2)
+{
+    u_long cnt;
+
+    /* Output a pair of lines according to the join list (if any). */
+    if (olist) {
+        for (cnt = 0; cnt < olistcnt; ++cnt)
+            if (olist[cnt].filenum == 0) {
+                if (lp1->fieldcnt >= F1->joinf)
+                    outfield(lp1, F1->joinf, 0);
+                else
+                    outfield(lp2, F2->joinf, 0);
+            } else if (olist[cnt].filenum == 1)
+                outfield(lp1, olist[cnt].fieldno, 0);
+            else /* if (olist[cnt].filenum == 2) */
+                outfield(lp2, olist[cnt].fieldno, 0);
+    } else {
+        /*
+         * Output the join field, then the remaining fields from F1
+         * and F2.
+         */
+        outfield(lp1, F1->joinf, 0);
+        for (cnt = 0; cnt < lp1->fieldcnt; ++cnt)
+            if (F1->joinf != cnt)
+                outfield(lp1, cnt, 0);
+        for (cnt = 0; cnt < lp2->fieldcnt; ++cnt)
+            if (F2->joinf != cnt)
+                outfield(lp2, cnt, 0);
+    }
+    putchar('\n');
+    if (ferror(stdout))
+        err(1, "stdout");
+    needsep = 0;
+}
+
+void
+outfield(LINE *lp, u_long fieldno, int out_empty)
+{
+    if (needsep++)
+        putchar((int)*tabchar);
+    if (!ferror(stdout)) {
+        if (lp->fieldcnt <= fieldno || out_empty) {
+            if (empty != NULL)
+                fputs(empty, stdout);
+        } else {
+            if (*lp->fields[fieldno] == '\0')
+                return;
+            fputs(lp->fields[fieldno], stdout);
+        }
+    }
+    if (ferror(stdout))
+        err(1, "stdout");
+}
+
+/*
+ * Convert an output list argument "2.1, 1.3, 2.4" into an array of output
+ * fields.
+ */
+void
+fieldarg(char *option)
+{
+    u_long fieldno, filenum;
+    char *end, *token;
+
+    while ((token = strsep(&option, ", \t")) != NULL) {
+        if (*token == '\0')
+            continue;
+        if (token[0] == '0')
+            filenum = fieldno = 0;
+        else if ((token[0] == '1' || token[0] == '2') &&
+            token[1] == '.') {
+            filenum = token[0] - '0';
+            fieldno = strtol(token + 2, &end, 10);
+            if (*end)
+                errx(1, "malformed -o option field");
+            if (fieldno == 0)
+                errx(1, "field numbers are 1 based");
+            --fieldno;
+        } else
+            errx(1, "malformed -o option field");
+        if (olistcnt == olistalloc) {
+            OLIST *p;
+            u_long newsize = olistalloc + 50;
+            if ((p = realloc(olist,
+                newsize * sizeof(OLIST))) == NULL)
+                err(1, NULL);
+            olist = p;
+            olistalloc = newsize;
+        }
+        olist[olistcnt].filenum = filenum;
+        olist[olistcnt].fieldno = fieldno;
+        ++olistcnt;
+    }
+}
+
+void
+obsolete(char **argv)
+{
+    size_t len;
+    char **p, *ap, *t;
+
+    while ((ap = *++argv) != NULL) {
+        /* Return if "--". */
+        if (ap[0] == '-' && ap[1] == '-')
+            return;
+        /* skip if not an option */
+        if (ap[0] != '-')
+            continue;
+        switch (ap[1]) {
+        case 'a':
+            /* 
+             * The original join allowed "-a", which meant the
+             * same as -a1 plus -a2.  POSIX 1003.2, Draft 11.2
+             * only specifies this as "-a 1" and "a -2", so we
+             * have to use another option flag, one that is
+             * unlikely to ever be used or accidentally entered
+             * on the command line.  (Well, we could reallocate
+             * the argv array, but that hardly seems worthwhile.)
+             */
+            if (ap[2] == '\0' && (argv[1] == NULL ||
+                (strcmp(argv[1], "1") != 0 &&
+                strcmp(argv[1], "2") != 0))) {
+                ap[1] = '\01';
+                warnx("-a option used without an argument; "
+                    "reverting to historical behavior");
+            }
+            break;
+        case 'j':
+            /*
+             * The original join allowed "-j[12] arg" and "-j arg".
+             * Convert the former to "-[12] arg".  Don't convert
+             * the latter since getopt(3) can handle it.
+             */
+            switch(ap[2]) {
+            case '1':
+            case '2':
+                if (ap[3] != '\0')
+                    goto jbad;
+                ap[1] = ap[2];
+                ap[2] = '\0';
+                break;
+            case '\0':
+                break;
+            default:
+jbad:               warnx("unknown option -- %s", ap + 1);
+                usage();
+            }
+            break;
+        case 'o':
+            /*
+             * The original join allowed "-o arg arg".
+             * Convert to "-o arg -o arg".
+             */
+            if (ap[2] != '\0' || argv[1] == NULL)
+                break;
+            for (p = argv + 2; *p != NULL; ++p) {
+                if (p[0][0] == '0' || ((p[0][0] != '1' &&
+                    p[0][0] != '2') || p[0][1] != '.'))
+                    break;
+                len = strlen(*p);
+                if (len - 2 != strspn(*p + 2, "0123456789"))
+                    break;
+                if ((t = malloc(len + 3)) == NULL)
+                    err(1, NULL);
+                t[0] = '-';
+                t[1] = 'o';
+                memmove(t + 2, *p, len + 1);
+                *p = t;
+            }
+            argv = p - 1;
+            break;
+        }
+    }
+}
+
+void
+usage(void)
+{
+    int len;
+    extern char *__progname;
+
+    len = strlen(__progname) + sizeof("usage: ");
+    (void)fprintf(stderr, "usage: %s [-1 field] [-2 field] "
+        "[-a file_number | -v file_number] [-e string]\n"
+        "%*s[-o list] [-t char] file1 file2\n",
+        __progname, len, "");
+    exit(1);
+}
+