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