1 /* $OpenBSD: join.c,v 1.28 2018/07/18 17:20:54 millert Exp $ */
4 * Copyright (c) 1991, 1993, 1994
5 * The Regents of the University of California. All rights reserved.
7 * This code is derived from software contributed to Berkeley by
8 * Steve Hayman of the Computer Science Department, Indiana University,
9 * Michiro Hikida and David Goodenough.
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions
14 * 1. Redistributions of source code must retain the above copyright
15 * notice, this list of conditions and the following disclaimer.
16 * 2. Redistributions in binary form must reproduce the above copyright
17 * notice, this list of conditions and the following disclaimer in the
18 * documentation and/or other materials provided with the distribution.
19 * 3. Neither the name of the University nor the names of its contributors
20 * may be used to endorse or promote products derived from this software
21 * without specific prior written permission.
23 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
24 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
25 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
26 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
27 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
28 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
29 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
30 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
32 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
42 #define MAXIMUM(a, b) (((a) > (b)) ? (a) : (b))
45 * There's a structure per input file which encapsulates the state of the
46 * file. We repeatedly read lines from each file until we've read in all
47 * the consecutive lines from the file with a common join field. Then we
48 * compare the set of lines with an equivalent set from the other file.
51 char *line
; /* line */
52 u_long linealloc
; /* line allocated count */
53 char **fields
; /* line field(s) */
54 u_long fieldcnt
; /* line field(s) count */
55 u_long fieldalloc
; /* line field(s) allocated count */
56 u_long cfieldc
; /* current field count */
57 long fpos
; /* fpos of start of field */
61 FILE *fp
; /* file descriptor */
62 u_long joinf
; /* join field (-1, -2, -j) */
63 int unpair
; /* output unpairable lines (-a) */
64 u_long number
; /* 1 for file 1, 2 for file 2 */
65 LINE
*set
; /* set of lines with same field */
66 int pushbool
; /* if pushback is set */
67 u_long pushback
; /* line on the stack */
68 u_long setcnt
; /* set count */
69 u_long setalloc
; /* set allocated count */
70 u_long setusedc
; /* sets used */
72 INPUT input1
= { NULL
, 0, 0, 1, NULL
, 0, 0, 0, 0, 0 },
73 input2
= { NULL
, 0, 0, 2, NULL
, 0, 0, 0, 0, 0 };
76 u_long filenum
; /* file number */
77 u_long fieldno
; /* field number */
79 OLIST
*olist
; /* output field list */
80 u_long olistcnt
; /* output field list count */
81 u_long olistalloc
; /* output field allocated count */
83 int joinout
= 1; /* show lines with matched join fields (-v) */
84 int needsep
; /* need separator character */
85 int spans
= 1; /* span multiple delimiters (-t) */
86 char *empty
; /* empty field replacement string (-e) */
87 char *tabchar
= " \t"; /* delimiter characters (-t) */
89 int cmp(LINE
*, u_long
, LINE
*, u_long
);
90 void fieldarg(char *);
91 void joinlines(INPUT
*, INPUT
*);
92 void obsolete(char **);
93 void outfield(LINE
*, u_long
, int);
94 void outoneline(INPUT
*, LINE
*);
95 void outtwoline(INPUT
*, LINE
*, INPUT
*, LINE
*);
97 void slurpit(INPUT
*);
101 main(int argc
, char *argv
[])
104 int aflag
, ch
, cval
, vflag
;
107 if (pledge("stdio rpath", NULL
) == -1)
115 while ((ch
= getopt(argc
, argv
, "\01a:e:j:1:2:o:t:v:")) != -1) {
117 case '\01': /* See comment in obsolete(). */
119 F1
->unpair
= F2
->unpair
= 1;
122 if ((F1
->joinf
= strtol(optarg
, &end
, 10)) < 1)
123 errx(1, "-1 option field number less than 1");
125 errx(1, "illegal field number -- %s", optarg
);
129 if ((F2
->joinf
= strtol(optarg
, &end
, 10)) < 1)
130 errx(1, "-2 option field number less than 1");
132 errx(1, "illegal field number -- %s", optarg
);
137 switch(strtol(optarg
, &end
, 10)) {
145 errx(1, "-a option file number not 1 or 2");
149 errx(1, "illegal file number -- %s", optarg
);
155 if ((F1
->joinf
= F2
->joinf
= strtol(optarg
, &end
, 10)) < 1)
156 errx(1, "-j option field number less than 1");
158 errx(1, "illegal field number -- %s", optarg
);
167 if (strlen(tabchar
= optarg
) != 1)
168 errx(1, "illegal tab character specification");
173 switch (strtol(optarg
, &end
, 10)) {
181 errx(1, "-v option file number not 1 or 2");
185 errx(1, "illegal file number -- %s", optarg
);
196 errx(1, "the -a and -v options are mutually exclusive");
201 /* Open the files; "-" means stdin. */
202 if (!strcmp(*argv
, "-"))
204 else if ((F1
->fp
= fopen(*argv
, "r")) == NULL
)
207 if (!strcmp(*argv
, "-"))
209 else if ((F2
->fp
= fopen(*argv
, "r")) == NULL
)
211 if (F1
->fp
== stdin
&& F2
->fp
== stdin
)
212 errx(1, "only one input file may be stdin");
214 if (pledge("stdio", NULL
) == -1)
221 F1
->set
->cfieldc
= 0;
222 F2
->set
->cfieldc
= 0;
225 * We try to let the files have the same field value, advancing
226 * whoever falls behind and always advancing the file(s) we output
229 while (F1
->setcnt
&& F2
->setcnt
) {
230 cval
= cmp(F1
->set
, F1
->joinf
, F2
->set
, F2
->joinf
);
232 /* Oh joy, oh rapture, oh beauty divine! */
240 && (cval
< 0 || F2
->set
->cfieldc
== F2
->setusedc
-1)) {
245 /* File 1 takes the lead... */
248 && (cval
> 0 || F1
->set
->cfieldc
== F1
->setusedc
-1)) {
253 /* File 2 takes the lead... */
259 * Now that one of the files is used up, optionally output any
260 * remaining lines from the other file.
276 /* wrapper around slurpit() to keep track of what field we are on */
282 if (F
->set
== NULL
) {
288 cfieldc
= F
->set
->cfieldc
;
293 else if (fpos
!= F
->set
->fpos
)
294 F
->set
->cfieldc
= cfieldc
+1;
300 LINE
*lp
, *lastlp
, tmp
;
304 char *bp
, *fieldp
, *line
;
307 * Read all of the lines from an input file that have the same
314 for (lastlp
= NULL
; ; ++F
->setcnt
, lastlp
= lp
) {
316 * If we're out of space to hold line structures, allocate
317 * more. Initialize the structure so that we know that this
320 if (F
->setcnt
== F
->setalloc
) {
322 u_long newsize
= F
->setalloc
+ 50;
324 if ((p
= reallocarray(F
->set
, newsize
, sizeof(LINE
)))
328 F
->setalloc
= newsize
;
329 memset(F
->set
+ cnt
, 0, 50 * sizeof(LINE
));
330 /* re-set lastlp in case it moved */
332 lastlp
= &F
->set
[F
->setcnt
- 1];
335 * Get any pushed back line, else get the next line. Allocate
336 * space as necessary. If taking the line from the stack swap
337 * the two structures so that we don't lose space allocated to
338 * either structure. This could be avoided by doing another
339 * level of indirection, but it's probably okay as is.
341 lp
= &F
->set
[F
->setcnt
];
343 tmp
= F
->set
[F
->setcnt
];
344 F
->set
[F
->setcnt
] = F
->set
[F
->pushback
];
345 F
->set
[F
->pushback
] = tmp
;
349 if ((len
= getline(&line
, &linesize
, F
->fp
)) == -1)
352 * we depend on knowing on what field we are, one safe way is
355 fpos
= ftell(F
->fp
) - len
;
357 /* Remove trailing newline, if it exists, and copy line. */
358 if (line
[len
- 1] == '\n')
360 if (lp
->linealloc
<= len
+ 1) {
362 u_long newsize
= lp
->linealloc
+
363 MAXIMUM(100, len
+ 1 - lp
->linealloc
);
364 if ((p
= realloc(lp
->line
, newsize
)) == NULL
)
367 lp
->linealloc
= newsize
;
370 memcpy(lp
->line
, line
, len
);
371 lp
->line
[len
] = '\0';
374 /* Split the line into fields, allocate space as necessary. */
377 while ((fieldp
= strsep(&bp
, tabchar
)) != NULL
) {
378 if (spans
&& *fieldp
== '\0')
380 if (lp
->fieldcnt
== lp
->fieldalloc
) {
382 u_long newsize
= lp
->fieldalloc
+ 50;
383 if ((p
= reallocarray(lp
->fields
, newsize
,
384 sizeof(char *))) == NULL
)
387 lp
->fieldalloc
= newsize
;
389 lp
->fields
[lp
->fieldcnt
++] = fieldp
;
392 /* See if the join field value has changed. */
393 if (lastlp
!= NULL
&& cmp(lp
, F
->joinf
, lastlp
, F
->joinf
)) {
395 F
->pushback
= F
->setcnt
;
403 cmp(LINE
*lp1
, u_long fieldno1
, LINE
*lp2
, u_long fieldno2
)
405 if (lp1
->fieldcnt
<= fieldno1
)
407 else if (lp2
->fieldcnt
<= fieldno2
)
409 return (strcmp(lp1
->fields
[fieldno1
], lp2
->fields
[fieldno2
]));
413 joinlines(INPUT
*F1
, INPUT
*F2
)
418 * Output the results of a join comparison. The output may be from
419 * either file 1 or file 2 (in which case the first argument is the
420 * file from which to output) or from both.
423 for (cnt1
= 0; cnt1
< F1
->setcnt
; ++cnt1
)
424 outoneline(F1
, &F1
->set
[cnt1
]);
427 for (cnt1
= 0; cnt1
< F1
->setcnt
; ++cnt1
)
428 for (cnt2
= 0; cnt2
< F2
->setcnt
; ++cnt2
)
429 outtwoline(F1
, &F1
->set
[cnt1
], F2
, &F2
->set
[cnt2
]);
433 outoneline(INPUT
*F
, LINE
*lp
)
438 * Output a single line from one of the files, according to the
439 * join rules. This happens when we are writing unmatched single
440 * lines. Output empty fields in the right places.
443 for (cnt
= 0; cnt
< olistcnt
; ++cnt
) {
444 if (olist
[cnt
].filenum
== F
->number
)
445 outfield(lp
, olist
[cnt
].fieldno
, 0);
446 else if (olist
[cnt
].filenum
== 0)
447 outfield(lp
, F
->joinf
, 0);
453 * Output the join field, then the remaining fields from F
455 outfield(lp
, F
->joinf
, 0);
456 for (cnt
= 0; cnt
< lp
->fieldcnt
; ++cnt
)
458 outfield(lp
, cnt
, 0);
468 outtwoline(INPUT
*F1
, LINE
*lp1
, INPUT
*F2
, LINE
*lp2
)
472 /* Output a pair of lines according to the join list (if any). */
474 for (cnt
= 0; cnt
< olistcnt
; ++cnt
)
475 if (olist
[cnt
].filenum
== 0) {
476 if (lp1
->fieldcnt
>= F1
->joinf
)
477 outfield(lp1
, F1
->joinf
, 0);
479 outfield(lp2
, F2
->joinf
, 0);
480 } else if (olist
[cnt
].filenum
== 1)
481 outfield(lp1
, olist
[cnt
].fieldno
, 0);
482 else /* if (olist[cnt].filenum == 2) */
483 outfield(lp2
, olist
[cnt
].fieldno
, 0);
486 * Output the join field, then the remaining fields from F1
489 outfield(lp1
, F1
->joinf
, 0);
490 for (cnt
= 0; cnt
< lp1
->fieldcnt
; ++cnt
)
491 if (F1
->joinf
!= cnt
)
492 outfield(lp1
, cnt
, 0);
493 for (cnt
= 0; cnt
< lp2
->fieldcnt
; ++cnt
)
494 if (F2
->joinf
!= cnt
)
495 outfield(lp2
, cnt
, 0);
504 outfield(LINE
*lp
, u_long fieldno
, int out_empty
)
507 putchar((int)*tabchar
);
508 if (!ferror(stdout
)) {
509 if (lp
->fieldcnt
<= fieldno
|| out_empty
) {
511 fputs(empty
, stdout
);
513 if (*lp
->fields
[fieldno
] == '\0')
515 fputs(lp
->fields
[fieldno
], stdout
);
523 * Convert an output list argument "2.1, 1.3, 2.4" into an array of output
527 fieldarg(char *option
)
529 u_long fieldno
, filenum
;
532 while ((token
= strsep(&option
, ", \t")) != NULL
) {
536 filenum
= fieldno
= 0;
537 else if ((token
[0] == '1' || token
[0] == '2') &&
539 filenum
= token
[0] - '0';
540 fieldno
= strtol(token
+ 2, &end
, 10);
542 errx(1, "malformed -o option field");
544 errx(1, "field numbers are 1 based");
547 errx(1, "malformed -o option field");
548 if (olistcnt
== olistalloc
) {
550 u_long newsize
= olistalloc
+ 50;
551 if ((p
= reallocarray(olist
, newsize
, sizeof(OLIST
)))
555 olistalloc
= newsize
;
557 olist
[olistcnt
].filenum
= filenum
;
558 olist
[olistcnt
].fieldno
= fieldno
;
564 obsolete(char **argv
)
569 while ((ap
= *++argv
) != NULL
) {
570 /* Return if "--". */
571 if (ap
[0] == '-' && ap
[1] == '-')
573 /* skip if not an option */
579 * The original join allowed "-a", which meant the
580 * same as -a1 plus -a2. POSIX 1003.2, Draft 11.2
581 * only specifies this as "-a 1" and "a -2", so we
582 * have to use another option flag, one that is
583 * unlikely to ever be used or accidentally entered
584 * on the command line. (Well, we could reallocate
585 * the argv array, but that hardly seems worthwhile.)
587 if (ap
[2] == '\0' && (argv
[1] == NULL
||
588 (strcmp(argv
[1], "1") != 0 &&
589 strcmp(argv
[1], "2") != 0))) {
591 warnx("-a option used without an argument; "
592 "reverting to historical behavior");
597 * The original join allowed "-j[12] arg" and "-j arg".
598 * Convert the former to "-[12] arg". Don't convert
599 * the latter since getopt(3) can handle it.
612 jbad
: warnx("unknown option -- %s", ap
+ 1);
618 * The original join allowed "-o arg arg".
619 * Convert to "-o arg -o arg".
621 if (ap
[2] != '\0' || argv
[1] == NULL
)
623 for (p
= argv
+ 2; *p
!= NULL
; ++p
) {
624 if (p
[0][0] == '0' || ((p
[0][0] != '1' &&
625 p
[0][0] != '2') || p
[0][1] != '.'))
628 if (len
- 2 != strspn(*p
+ 2, "0123456789"))
630 if ((t
= malloc(len
+ 3)) == NULL
)
634 memmove(t
+ 2, *p
, len
+ 1);
647 extern char *__progname
;
649 len
= strlen(__progname
) + sizeof("usage: ");
650 (void)fprintf(stderr
, "usage: %s [-1 field] [-2 field] "
651 "[-a file_number | -v file_number] [-e string]\n"
652 "%*s[-o list] [-t char] file1 file2\n",
653 __progname
, len
, "");