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