Minor cleanups. Document -j in usage.
[dragonfly.git] / usr.bin / join / join.c
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  * @(#) 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.4 2004/08/25 01:43:43 dillon Exp $
41  */
42
43 #include <sys/param.h>
44
45 #include <err.h>
46 #include <errno.h>
47 #include <locale.h>
48 #include <stdio.h>
49 #include <stdlib.h>
50 #include <string.h>
51 #include <unistd.h>
52
53 /*
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.
58  */
59 typedef struct {
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 */
65 } LINE;
66
67 typedef struct {
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 */
72
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 */
78 } INPUT;
79 INPUT input1 = { NULL, 0, 0, 1, NULL, 0, 0, 0, 0 },
80       input2 = { NULL, 0, 0, 2, NULL, 0, 0, 0, 0 };
81
82 typedef struct {
83         u_long  filenum;        /* file number */
84         u_long  fieldno;        /* field number */
85 } OLIST;
86 OLIST *olist;                   /* output field list */
87 u_long olistcnt;                /* output field list count */
88 u_long olistalloc;              /* output field allocated count */
89
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) */
96
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 *);
104 void slurp(INPUT *);
105 void usage(void);
106
107 int
108 main(int argc, char **argv)
109 {
110         INPUT *F1, *F2;
111         int aflag, ch, cval, vflag;
112         char *end;
113
114         setlocale(LC_ALL, "");
115
116         F1 = &input1;
117         F2 = &input2;
118
119         aflag = vflag = 0;
120         obsolete(argv);
121         while ((ch = getopt(argc, argv, "\01a:e:j:1:2:o:t:v:")) != -1) {
122                 switch (ch) {
123                 case '\01':             /* See comment in obsolete(). */
124                         aflag = 1;
125                         F1->unpair = F2->unpair = 1;
126                         break;
127                 case '1':
128                         if ((F1->joinf = strtol(optarg, &end, 10)) < 1)
129                                 errx(1, "-1 option field number less than 1");
130                         if (*end)
131                                 errx(1, "illegal field number -- %s", optarg);
132                         --F1->joinf;
133                         break;
134                 case '2':
135                         if ((F2->joinf = strtol(optarg, &end, 10)) < 1)
136                                 errx(1, "-2 option field number less than 1");
137                         if (*end)
138                                 errx(1, "illegal field number -- %s", optarg);
139                         --F2->joinf;
140                         break;
141                 case 'a':
142                         aflag = 1;
143                         switch(strtol(optarg, &end, 10)) {
144                         case 1:
145                                 F1->unpair = 1;
146                                 break;
147                         case 2:
148                                 F2->unpair = 1;
149                                 break;
150                         default:
151                                 errx(1, "-a option file number not 1 or 2");
152                                 break;
153                         }
154                         if (*end)
155                                 errx(1, "illegal file number -- %s", optarg);
156                         break;
157                 case 'e':
158                         empty = optarg;
159                         break;
160                 case 'j':
161                         if ((F1->joinf = F2->joinf =
162                             strtol(optarg, &end, 10)) < 1)
163                                 errx(1, "-j option field number less than 1");
164                         if (*end)
165                                 errx(1, "illegal field number -- %s", optarg);
166                         --F1->joinf;
167                         --F2->joinf;
168                         break;
169                 case 'o':
170                         fieldarg(optarg);
171                         break;
172                 case 't':
173                         spans = 0;
174                         if (strlen(tabchar = optarg) != 1)
175                                 errx(1, "illegal tab character specification");
176                         break;
177                 case 'v':
178                         vflag = 1;
179                         joinout = 0;
180                         switch (strtol(optarg, &end, 10)) {
181                         case 1:
182                                 F1->unpair = 1;
183                                 break;
184                         case 2:
185                                 F2->unpair = 1;
186                                 break;
187                         default:
188                                 errx(1, "-v option file number not 1 or 2");
189                                 break;
190                         }
191                         if (*end)
192                                 errx(1, "illegal file number -- %s", optarg);
193                         break;
194                 case '?':
195                 default:
196                         usage();
197                 }
198         }
199         argc -= optind;
200         argv += optind;
201
202         if (aflag && vflag)
203                 errx(1, "the -a and -v options are mutually exclusive");
204
205         if (argc != 2)
206                 usage();
207
208         /* Open the files; "-" means stdin. */
209         if (!strcmp(*argv, "-"))
210                 F1->fp = stdin;
211         else if ((F1->fp = fopen(*argv, "r")) == NULL)
212                 err(1, "%s", *argv);
213         ++argv;
214         if (!strcmp(*argv, "-"))
215                 F2->fp = stdin;
216         else if ((F2->fp = fopen(*argv, "r")) == NULL)
217                 err(1, "%s", *argv);
218         if (F1->fp == stdin && F2->fp == stdin)
219                 errx(1, "only one input file may be stdin");
220
221         slurp(F1);
222         slurp(F2);
223         while (F1->setcnt && F2->setcnt) {
224                 cval = cmp(F1->set, F1->joinf, F2->set, F2->joinf);
225                 if (cval == 0) {
226                         /* Oh joy, oh rapture, oh beauty divine! */
227                         if (joinout)
228                                 joinlines(F1, F2);
229                         slurp(F1);
230                         slurp(F2);
231                 } else if (cval < 0) {
232                         /* File 1 takes the lead... */
233                         if (F1->unpair)
234                                 joinlines(F1, NULL);
235                         slurp(F1);
236                 } else {
237                         /* File 2 takes the lead... */
238                         if (F2->unpair)
239                                 joinlines(F2, NULL);
240                         slurp(F2);
241                 }
242         }
243
244         /*
245          * Now that one of the files is used up, optionally output any
246          * remaining lines from the other file.
247          */
248         if (F1->unpair)
249                 while (F1->setcnt) {
250                         joinlines(F1, NULL);
251                         slurp(F1);
252                 }
253         if (F2->unpair)
254                 while (F2->setcnt) {
255                         joinlines(F2, NULL);
256                         slurp(F2);
257                 }
258         exit(0);
259 }
260
261 void
262 slurp(INPUT *F)
263 {
264         LINE *lp, *lastlp, tmp;
265         size_t len;
266         int cnt;
267         char *bp, *fieldp;
268
269         /*
270          * Read all of the lines from an input file that have the same
271          * join field.
272          */
273         F->setcnt = 0;
274         for (lastlp = NULL;; ++F->setcnt) {
275                 /*
276                  * If we're out of space to hold line structures, allocate
277                  * more.  Initialize the structure so that we know that this
278                  * is new space.
279                  */
280                 if (F->setcnt == F->setalloc) {
281                         cnt = F->setalloc;
282                         F->setalloc += 50;
283                         if ((F->set = realloc(F->set,
284                             F->setalloc * sizeof(LINE))) == NULL)
285                                 err(1, NULL);
286                         memset(F->set + cnt, 0, 50 * sizeof(LINE));
287
288                         /* re-set lastlp in case it moved */
289                         if (lastlp != NULL)
290                                 lastlp = &F->set[F->setcnt - 1];
291                 }
292
293                 /*
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.
299                  */
300                 lp = &F->set[F->setcnt];
301                 if (F->setcnt)
302                         lastlp = &F->set[F->setcnt - 1];
303                 if (F->pushbool) {
304                         tmp = F->set[F->setcnt];
305                         F->set[F->setcnt] = F->set[F->pushback];
306                         F->set[F->pushback] = tmp;
307                         F->pushbool = 0;
308                         continue;
309                 }
310                 if ((bp = fgetln(F->fp, &len)) == NULL)
311                         return;
312                 if (lp->linealloc <= len + 1) {
313                         lp->linealloc += MAX(100, len + 1 - lp->linealloc);
314                         if ((lp->line =
315                             realloc(lp->line, lp->linealloc)) == NULL)
316                                 err(1, NULL);
317                 }
318                 memmove(lp->line, bp, len);
319
320                 /* Replace trailing newline, if it exists. */
321                 if (bp[len - 1] == '\n')
322                         lp->line[len - 1] = '\0';
323                 else
324                         lp->line[len] = '\0';
325                 bp = lp->line;
326
327                 /* Split the line into fields, allocate space as necessary. */
328                 lp->fieldcnt = 0;
329                 while ((fieldp = strsep(&bp, tabchar)) != NULL) {
330                         if (spans && *fieldp == '\0')
331                                 continue;
332                         if (lp->fieldcnt == lp->fieldalloc) {
333                                 lp->fieldalloc += 50;
334                                 if ((lp->fields = realloc(lp->fields,
335                                     lp->fieldalloc * sizeof(char *))) == NULL)
336                                         err(1, NULL);
337                         }
338                         lp->fields[lp->fieldcnt++] = fieldp;
339                 }
340
341                 /* See if the join field value has changed. */
342                 if (lastlp != NULL && cmp(lp, F->joinf, lastlp, F->joinf)) {
343                         F->pushbool = 1;
344                         F->pushback = F->setcnt;
345                         break;
346                 }
347         }
348 }
349
350 int
351 cmp(LINE *lp1, u_long fieldno1, LINE *lp2, u_long fieldno2)
352 {
353         if (lp1->fieldcnt <= fieldno1)
354                 return (lp2->fieldcnt <= fieldno2 ? 0 : 1);
355         if (lp2->fieldcnt <= fieldno2)
356                 return (-1);
357         return (strcoll(lp1->fields[fieldno1], lp2->fields[fieldno2]));
358 }
359
360 void
361 joinlines(INPUT *F1, INPUT *F2)
362 {
363         unsigned int cnt1, cnt2;
364
365         /*
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.
369          */
370         if (F2 == NULL) {
371                 for (cnt1 = 0; cnt1 < F1->setcnt; ++cnt1)
372                         outoneline(F1, &F1->set[cnt1]);
373                 return;
374         }
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]);
378 }
379
380 void
381 outoneline(INPUT *F, LINE *lp)
382 {
383         unsigned int cnt;
384
385         /*
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.
389          */
390         if (olist)
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);
396                         else
397                                 outfield(lp, 0, 1);
398                 }
399         else
400                 for (cnt = 0; cnt < lp->fieldcnt; ++cnt)
401                         outfield(lp, cnt, 0);
402         (void)printf("\n");
403         if (ferror(stdout))
404                 err(1, "stdout");
405         needsep = 0;
406 }
407
408 void
409 outtwoline(INPUT *F1, LINE *lp1, INPUT *F2, LINE *lp2)
410 {
411         unsigned int cnt;
412
413         /* Output a pair of lines according to the join list (if any). */
414         if (olist)
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);
419                                 else
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);
425         else {
426                 /*
427                  * Output the join field, then the remaining fields from F1
428                  * and F2.
429                  */
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);
437         }
438         (void)printf("\n");
439         if (ferror(stdout))
440                 err(1, "stdout");
441         needsep = 0;
442 }
443
444 void
445 outfield(LINE *lp, u_long fieldno, int out_empty)
446 {
447         if (needsep++)
448                 (void)printf("%c", *tabchar);
449         if (!ferror(stdout)) {
450                 if (lp->fieldcnt <= fieldno || out_empty) {
451                         if (empty != NULL)
452                                 (void)printf("%s", empty);
453                 } else {
454                         if (*lp->fields[fieldno] == '\0')
455                                 return;
456                         (void)printf("%s", lp->fields[fieldno]);
457                 }
458         }
459         if (ferror(stdout))
460                 err(1, "stdout");
461 }
462
463 /*
464  * Convert an output list argument "2.1, 1.3, 2.4" into an array of output
465  * fields.
466  */
467 void
468 fieldarg(char *option)
469 {
470         u_long fieldno, filenum;
471         char *end, *token;
472
473         while ((token = strsep(&option, ", \t")) != NULL) {
474                 if (*token == '\0')
475                         continue;
476                 if (token[0] == '0')
477                         filenum = fieldno = 0;
478                 else if ((token[0] == '1' || token[0] == '2') &&
479                     token[1] == '.') {
480                         filenum = token[0] - '0';
481                         fieldno = strtol(token + 2, &end, 10);
482                         if (*end)
483                                 errx(1, "malformed -o option field");
484                         if (fieldno == 0)
485                                 errx(1, "field numbers are 1 based");
486                         --fieldno;
487                 } else
488                         errx(1, "malformed -o option field");
489                 if (olistcnt == olistalloc) {
490                         olistalloc += 50;
491                         if ((olist = realloc(olist,
492                             olistalloc * sizeof(OLIST))) == NULL)
493                                 err(1, NULL);
494                 }
495                 olist[olistcnt].filenum = filenum;
496                 olist[olistcnt].fieldno = fieldno;
497                 ++olistcnt;
498         }
499 }
500
501 void
502 obsolete(char **argv)
503 {
504         unsigned int len;
505         char **p, *ap, *t;
506
507         while ((ap = *++argv) != NULL) {
508                 /* Return if "--". */
509                 if (ap[0] == '-' && ap[1] == '-')
510                         return;
511                 /* skip if not an option */
512                 if (ap[0] != '-')
513                         continue;
514                 switch (ap[1]) {
515                 case 'a':
516                         /*
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.)
524                          */
525                         if (ap[2] == '\0' && (argv[1] == NULL ||
526                             (strcmp(argv[1], "1") != 0 &&
527                             strcmp(argv[1], "2") != 0))) {
528                                 ap[1] = '\01';
529                                 warnx("-a option used without an argument; "
530                                     "reverting to historical behavior");
531                         }
532                         break;
533                 case 'j':
534                         /*
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.
538                          */
539                         switch(ap[2]) {
540                         case '1':
541                                 if (ap[3] != '\0')
542                                         goto jbad;
543                                 ap[1] = '1';
544                                 ap[2] = '\0';
545                                 break;
546                         case '2':
547                                 if (ap[3] != '\0')
548                                         goto jbad;
549                                 ap[1] = '2';
550                                 ap[2] = '\0';
551                                 break;
552                         case '\0':
553                                 break;
554                         default:
555 jbad:                           errx(1, "illegal option -- %s", ap);
556                                 usage();
557                         }
558                         break;
559                 case 'o':
560                         /*
561                          * The original join allowed "-o arg arg".
562                          * Convert to "-o arg -o arg".
563                          */
564                         if (ap[2] != '\0')
565                                 break;
566                         for (p = argv + 2; *p; ++p) {
567                                 if (p[0][0] == '0' || (p[0][0] != '1' &&
568                                     p[0][0] != '2' || p[0][1] != '.'))
569                                         break;
570                                 len = strlen(*p);
571                                 if (len - 2 != strspn(*p + 2, "0123456789"))
572                                         break;
573                                 if ((t = malloc(len + 3)) == NULL)
574                                         err(1, NULL);
575                                 t[0] = '-';
576                                 t[1] = 'o';
577                                 memmove(t + 2, *p, len + 1);
578                                 *p = t;
579                         }
580                         argv = p - 1;
581                         break;
582                 }
583         }
584 }
585
586 void
587 usage(void)
588 {
589         (void)fprintf(stderr, "%s %s\n%s\n",
590             "usage: join [-a fileno | -v fileno ] [-e string] [-j fileno field]"
591             "            [-1 field] [-2 field] [-o list] [-t char] file1 file2\n");
592         exit(1);
593 }