2 * Copyright (c) 1991, 1993, 1994
3 * The Regents of the University of California. All rights reserved.
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.
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
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.
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
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 $
43 #include <sys/param.h>
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.
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 */
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 */
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 */
79 INPUT input1 = { NULL, 0, 0, 1, NULL, 0, 0, 0, 0 },
80 input2 = { NULL, 0, 0, 2, NULL, 0, 0, 0, 0 };
83 u_long filenum; /* file number */
84 u_long fieldno; /* field number */
86 OLIST *olist; /* output field list */
87 u_long olistcnt; /* output field list count */
88 u_long olistalloc; /* output field allocated count */
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) */
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 *);
108 main(int argc, char **argv)
111 int aflag, ch, cval, vflag;
114 setlocale(LC_ALL, "");
121 while ((ch = getopt(argc, argv, "\01a:e:j:1:2:o:t:v:")) != -1) {
123 case '\01': /* See comment in obsolete(). */
125 F1->unpair = F2->unpair = 1;
128 if ((F1->joinf = strtol(optarg, &end, 10)) < 1)
129 errx(1, "-1 option field number less than 1");
131 errx(1, "illegal field number -- %s", optarg);
135 if ((F2->joinf = strtol(optarg, &end, 10)) < 1)
136 errx(1, "-2 option field number less than 1");
138 errx(1, "illegal field number -- %s", optarg);
143 switch(strtol(optarg, &end, 10)) {
151 errx(1, "-a option file number not 1 or 2");
155 errx(1, "illegal file number -- %s", optarg);
161 if ((F1->joinf = F2->joinf =
162 strtol(optarg, &end, 10)) < 1)
163 errx(1, "-j option field number less than 1");
165 errx(1, "illegal field number -- %s", optarg);
174 if (strlen(tabchar = optarg) != 1)
175 errx(1, "illegal tab character specification");
180 switch (strtol(optarg, &end, 10)) {
188 errx(1, "-v option file number not 1 or 2");
192 errx(1, "illegal file number -- %s", optarg);
203 errx(1, "the -a and -v options are mutually exclusive");
208 /* Open the files; "-" means stdin. */
209 if (!strcmp(*argv, "-"))
211 else if ((F1->fp = fopen(*argv, "r")) == NULL)
214 if (!strcmp(*argv, "-"))
216 else if ((F2->fp = fopen(*argv, "r")) == NULL)
218 if (F1->fp == stdin && F2->fp == stdin)
219 errx(1, "only one input file may be stdin");
223 while (F1->setcnt && F2->setcnt) {
224 cval = cmp(F1->set, F1->joinf, F2->set, F2->joinf);
226 /* Oh joy, oh rapture, oh beauty divine! */
231 } else if (cval < 0) {
232 /* File 1 takes the lead... */
237 /* File 2 takes the lead... */
245 * Now that one of the files is used up, optionally output any
246 * remaining lines from the other file.
264 LINE *lp, *lastlp, tmp;
270 * Read all of the lines from an input file that have the same
274 for (lastlp = NULL;; ++F->setcnt) {
276 * If we're out of space to hold line structures, allocate
277 * more. Initialize the structure so that we know that this
280 if (F->setcnt == F->setalloc) {
283 if ((F->set = realloc(F->set,
284 F->setalloc * sizeof(LINE))) == NULL)
286 memset(F->set + cnt, 0, 50 * sizeof(LINE));
288 /* re-set lastlp in case it moved */
290 lastlp = &F->set[F->setcnt - 1];
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.
300 lp = &F->set[F->setcnt];
302 lastlp = &F->set[F->setcnt - 1];
304 tmp = F->set[F->setcnt];
305 F->set[F->setcnt] = F->set[F->pushback];
306 F->set[F->pushback] = tmp;
310 if ((bp = fgetln(F->fp, &len)) == NULL)
312 if (lp->linealloc <= len + 1) {
313 lp->linealloc += MAX(100, len + 1 - lp->linealloc);
315 realloc(lp->line, lp->linealloc)) == NULL)
318 memmove(lp->line, bp, len);
320 /* Replace trailing newline, if it exists. */
321 if (bp[len - 1] == '\n')
322 lp->line[len - 1] = '\0';
324 lp->line[len] = '\0';
327 /* Split the line into fields, allocate space as necessary. */
329 while ((fieldp = strsep(&bp, tabchar)) != NULL) {
330 if (spans && *fieldp == '\0')
332 if (lp->fieldcnt == lp->fieldalloc) {
333 lp->fieldalloc += 50;
334 if ((lp->fields = realloc(lp->fields,
335 lp->fieldalloc * sizeof(char *))) == NULL)
338 lp->fields[lp->fieldcnt++] = fieldp;
341 /* See if the join field value has changed. */
342 if (lastlp != NULL && cmp(lp, F->joinf, lastlp, F->joinf)) {
344 F->pushback = F->setcnt;
351 cmp(LINE *lp1, u_long fieldno1, LINE *lp2, u_long fieldno2)
353 if (lp1->fieldcnt <= fieldno1)
354 return (lp2->fieldcnt <= fieldno2 ? 0 : 1);
355 if (lp2->fieldcnt <= fieldno2)
357 return (strcoll(lp1->fields[fieldno1], lp2->fields[fieldno2]));
361 joinlines(INPUT *F1, INPUT *F2)
363 unsigned int cnt1, cnt2;
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.
371 for (cnt1 = 0; cnt1 < F1->setcnt; ++cnt1)
372 outoneline(F1, &F1->set[cnt1]);
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]);
381 outoneline(INPUT *F, LINE *lp)
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.
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);
400 for (cnt = 0; cnt < lp->fieldcnt; ++cnt)
401 outfield(lp, cnt, 0);
409 outtwoline(INPUT *F1, LINE *lp1, INPUT *F2, LINE *lp2)
413 /* Output a pair of lines according to the join list (if any). */
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);
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);
427 * Output the join field, then the remaining fields from F1
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);
445 outfield(LINE *lp, u_long fieldno, int out_empty)
448 (void)printf("%c", *tabchar);
449 if (!ferror(stdout)) {
450 if (lp->fieldcnt <= fieldno || out_empty) {
452 (void)printf("%s", empty);
454 if (*lp->fields[fieldno] == '\0')
456 (void)printf("%s", lp->fields[fieldno]);
464 * Convert an output list argument "2.1, 1.3, 2.4" into an array of output
468 fieldarg(char *option)
470 u_long fieldno, filenum;
473 while ((token = strsep(&option, ", \t")) != NULL) {
477 filenum = fieldno = 0;
478 else if ((token[0] == '1' || token[0] == '2') &&
480 filenum = token[0] - '0';
481 fieldno = strtol(token + 2, &end, 10);
483 errx(1, "malformed -o option field");
485 errx(1, "field numbers are 1 based");
488 errx(1, "malformed -o option field");
489 if (olistcnt == olistalloc) {
491 if ((olist = realloc(olist,
492 olistalloc * sizeof(OLIST))) == NULL)
495 olist[olistcnt].filenum = filenum;
496 olist[olistcnt].fieldno = fieldno;
502 obsolete(char **argv)
507 while ((ap = *++argv) != NULL) {
508 /* Return if "--". */
509 if (ap[0] == '-' && ap[1] == '-')
511 /* skip if not an option */
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.)
525 if (ap[2] == '\0' && (argv[1] == NULL ||
526 (strcmp(argv[1], "1") != 0 &&
527 strcmp(argv[1], "2") != 0))) {
529 warnx("-a option used without an argument; "
530 "reverting to historical behavior");
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.
555 jbad: errx(1, "illegal option -- %s", ap);
561 * The original join allowed "-o arg arg".
562 * Convert to "-o arg -o arg".
566 for (p = argv + 2; *p; ++p) {
567 if ((p[0][0] != '1' && p[0][0] != '2') ||
571 if (len - 2 != strspn(*p + 2, "0123456789"))
573 if ((t = malloc(len + 3)) == NULL)
577 memmove(t + 2, *p, len + 1);
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");