src/join.c

   1 /* join - join lines of two files on a common field
   2    Copyright (C) 1991 Free Software Foundation, Inc.
   3
   4    This program is free software; you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation; either version 2, or (at your option)
   7    any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program; if not, write to the Free Software
  16    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  17
  18    Written by Mike Haertel, mike@gnu.ai.mit.edu. */
  19
  20 #ifdef HAVE_CONFIG_H
  21 #if defined (CONFIG_BROKETS)
  22 /* We use <config.h> instead of "config.h" so that a compilation
  23    using -I. -I$srcdir will use ./config.h rather than $srcdir/config.h
  24    (which it would do because it found this file in $srcdir).  */
  25 #include <config.h>
  26 #else
  27 #include "config.h"
  28 #endif
  29 #endif
  30
  31 /* Get isblank from GNU libc.  */
  32 #define _GNU_SOURCE
  33
  34 #include <stdio.h>
  35 #include <sys/types.h>
  36 #include <getopt.h>
  37 #include "system.h"
  38 #include "version.h"
  39 #include "long-options.h"
  40
  41 char *xmalloc ();
  42 char *xrealloc ();
  43 void error ();
  44 static void usage ();
  45
  46 #define min(A, B) ((A) < (B) ? (A) : (B))
  47 #define max(A, B) ((A) > (B) ? (A) : (B))
  48
  49 /* An element of the list describing the format of each
  50    output line. */
  51 struct outlist
  52 {
  53   int file;                     /* File to take field from (1 or 2). */
  54   int field;                    /* Field number to print. */
  55   struct outlist *next;
  56 };
  57
  58 /* A field of a line. */
  59 struct field
  60 {
  61   char *beg;                    /* First character in field. */
  62   char *lim;                    /* Character after last character in field. */
  63 };
  64
  65 /* A line read from an input file.  Newlines are not stored. */
  66 struct line
  67 {
  68   char *beg;                    /* First character in line. */
  69   char *lim;                    /* Character after last character in line. */
  70   int nfields;                  /* Number of elements in `fields'. */
  71   struct field *fields;
  72 };
  73
  74 /* One or more consecutive lines read from a file that all have the
  75    same join field value. */
  76 struct seq
  77 {
  78   int count;                    /* Elements used in `lines'. */
  79   int alloc;                    /* Elements allocated in `lines'. */
  80   struct line *lines;
  81 };
  82
  83 /* The name this program was run with. */
  84 char *program_name;
  85
  86 /* If nonzero, print unpairable lines in file 1 or 2. */
  87 static int print_unpairables_1, print_unpairables_2;
  88
  89 /* If nonzero, print pairable lines. */
  90 static int print_pairables;
  91
  92 /* Empty output field filler. */
  93 static char *empty_filler;
  94
  95 /* Field to join on. */
  96 static int join_field_1, join_field_2;
  97
  98 /* List of fields to print. */
  99 static struct outlist *outlist;
 100
 101 /* Last element in `outlist', where a new element can be added. */
 102 static struct outlist *outlist_end;
 103
 104 /* Tab character separating fields; if this is NUL fields are separated
 105    by any nonempty string of white space, otherwise by exactly one
 106    tab character. */
 107 static char tab;
 108
 109 /* When using getopt_long_only, no long option can start with
 110    a character that is a short option. */
 111 static struct option const longopts[] =
 112 {
 113   {"j", required_argument, NULL, 'j'},
 114   {"j1", required_argument, NULL, '1'},
 115   {"j2", required_argument, NULL, '2'},
 116   {NULL, 0, NULL, 0}
 117 };
 118
 119 /* Used to print non-joining lines */
 120 static struct line blank1;
 121 static struct line blank2;
 122
 123 /* Fill in the `fields' structure in LINE. */
 124
 125 static void
 126 xfields (line)
 127      struct line *line;
 128 {
 129   static int nfields = 2;
 130   int i;
 131   register char *ptr, *lim;
 132
 133   line->fields = (struct field *) xmalloc (nfields * sizeof (struct field));
 134
 135   ptr = line->beg;
 136   lim = line->lim;
 137
 138   for (i = 0; ptr < lim; ++i)
 139     {
 140       if (i == nfields)
 141         {
 142           nfields *= 2;
 143           line->fields = (struct field *)
 144             xrealloc ((char *) line->fields, nfields * sizeof (struct field));
 145         }
 146       if (tab)
 147         {
 148           line->fields[i].beg = ptr;
 149           while (ptr < lim && *ptr != tab)
 150             ++ptr;
 151           line->fields[i].lim = ptr;
 152           if (ptr < lim)
 153             ++ptr;
 154         }
 155       else
 156         {
 157           line->fields[i].beg = ptr;
 158           while (ptr < lim && !ISSPACE (*ptr))
 159             ++ptr;
 160           line->fields[i].lim = ptr;
 161           while (ptr < lim && ISSPACE (*ptr))
 162             ++ptr;
 163         }
 164     }
 165
 166   line->nfields = i;
 167 }
 168
 169 /* Read a line from FP into LINE and split it into fields.
 170    Return 0 if EOF, 1 otherwise. */
 171
 172 static int
 173 get_line (fp, line)
 174      FILE *fp;
 175      struct line *line;
 176 {
 177   static int linesize = 80;
 178   int c, i;
 179   char *ptr;
 180
 181   if (feof (fp))
 182     return 0;
 183
 184   ptr = xmalloc (linesize);
 185
 186   for (i = 0; (c = getc (fp)) != EOF && c != '\n'; ++i)
 187     {
 188       if (i == linesize)
 189         {
 190           linesize *= 2;
 191           ptr = xrealloc (ptr, linesize);
 192         }
 193       ptr[i] = c;
 194     }
 195
 196   if (c == EOF && i == 0)
 197     {
 198       free (ptr);
 199       return 0;
 200     }
 201
 202   line->beg = ptr;
 203   line->lim = line->beg + i;
 204   xfields (line);
 205   return 1;
 206 }
 207
 208 static void
 209 freeline (line)
 210      struct line *line;
 211 {
 212   free ((char *) line->fields);
 213   free (line->beg);
 214 }
 215
 216 static void
 217 initseq (seq)
 218      struct seq *seq;
 219 {
 220   seq->count = 0;
 221   seq->alloc = 1;
 222   seq->lines = (struct line *) xmalloc (seq->alloc * sizeof (struct line));
 223 }
 224
 225 /* Read a line from FP and add it to SEQ.  Return 0 if EOF, 1 otherwise. */
 226
 227 static int
 228 getseq (fp, seq)
 229      FILE *fp;
 230      struct seq *seq;
 231 {
 232   if (seq->count == seq->alloc)
 233     {
 234       seq->alloc *= 2;
 235       seq->lines = (struct line *)
 236         xrealloc ((char *) seq->lines, seq->alloc * sizeof (struct line));
 237     }
 238
 239   if (get_line (fp, &seq->lines[seq->count]))
 240     {
 241       ++seq->count;
 242       return 1;
 243     }
 244   return 0;
 245 }
 246
 247 static void
 248 delseq (seq)
 249      struct seq *seq;
 250 {
 251   free ((char *) seq->lines);
 252 }
 253
 254 /* Return <0 if the join field in LINE1 compares less than the one in LINE2;
 255    >0 if it compares greater; 0 if it compares equal. */
 256
 257 static int
 258 keycmp (line1, line2)
 259      struct line *line1;
 260      struct line *line2;
 261 {
 262   char *beg1, *beg2;            /* Start of field to compare in each file. */
 263   int len1, len2;               /* Length of fields to compare. */
 264   int diff;
 265
 266   if (join_field_1 < line1->nfields)
 267     {
 268       beg1 = line1->fields[join_field_1].beg;
 269       len1 = line1->fields[join_field_1].lim
 270         - line1->fields[join_field_1].beg;
 271     }
 272   else
 273     {
 274       beg1 = NULL;
 275       len1 = 0;
 276     }
 277
 278   if (join_field_2 < line2->nfields)
 279     {
 280       beg2 = line2->fields[join_field_2].beg;
 281       len2 = line2->fields[join_field_2].lim
 282         - line2->fields[join_field_2].beg;
 283     }
 284   else
 285     {
 286       beg2 = NULL;
 287       len2 = 0;
 288     }
 289
 290   if (len1 == 0)
 291     return len2 == 0 ? 0 : -1;
 292   if (len2 == 0)
 293     return 1;
 294   diff = memcmp (beg1, beg2, min (len1, len2));
 295   if (diff)
 296     return diff;
 297   return len1 - len2;
 298 }
 299
 300 /* Print field N of LINE if it exists and is nonempty, otherwise
 301    `empty_filler' if it is nonempty. */
 302
 303 static void
 304 prfield (n, line)
 305      int n;
 306      struct line *line;
 307 {
 308   int len;
 309
 310   if (n < line->nfields)
 311     {
 312       len = line->fields[n].lim - line->fields[n].beg;
 313       if (len)
 314         fwrite (line->fields[n].beg, 1, len, stdout);
 315       else if (empty_filler)
 316         fputs (empty_filler, stdout);
 317     }
 318   else if (empty_filler)
 319     fputs (empty_filler, stdout);
 320 }
 321
 322 /* Print LINE, with its fields separated by `tab'. */
 323
 324 static void
 325 prline (line)
 326      struct line *line;
 327 {
 328   int i;
 329
 330   for (i = 0; i < line->nfields; ++i)
 331     {
 332       prfield (i, line);
 333       if (i == line->nfields - 1)
 334         putchar ('\n');
 335       else
 336         putchar (tab ? tab : ' ');
 337     }
 338 }
 339
 340 /* Print the join of LINE1 and LINE2. */
 341
 342 static void
 343 prjoin (line1, line2)
 344      struct line *line1;
 345      struct line *line2;
 346 {
 347   if (outlist)
 348     {
 349       struct outlist *o;
 350
 351       prfield (outlist->field - 1, outlist->file == 1 ? line1 : line2);
 352       for (o = outlist->next; o; o = o->next)
 353         {
 354           putchar (tab ? tab : ' ');
 355           prfield (o->field - 1, o->file == 1 ? line1 : line2);
 356         }
 357       putchar ('\n');
 358     }
 359   else
 360     {
 361       int i;
 362
 363       prfield (join_field_1, line1);
 364       for (i = 0; i < join_field_1 && i < line1->nfields; ++i)
 365         {
 366           putchar (tab ? tab : ' ');
 367           prfield (i, line1);
 368         }
 369       for (i = join_field_1 + 1; i < line1->nfields; ++i)
 370         {
 371           putchar (tab ? tab : ' ');
 372           prfield (i, line1);
 373         }
 374
 375       for (i = 0; i < join_field_2 && i < line2->nfields; ++i)
 376         {
 377           putchar (tab ? tab : ' ');
 378           prfield (i, line2);
 379         }
 380       for (i = join_field_2 + 1; i < line2->nfields; ++i)
 381         {
 382           putchar (tab ? tab : ' ');
 383           prfield (i, line2);
 384         }
 385       putchar ('\n');
 386     }
 387 }
 388
 389 /* Print the join of the files in FP1 and FP2. */
 390
 391 static void
 392 join (fp1, fp2)
 393      FILE *fp1;
 394      FILE *fp2;
 395 {
 396   struct seq seq1, seq2;
 397   struct line line;
 398   int diff, i, j, eof1, eof2;
 399
 400   /* Read the first line of each file. */
 401   initseq (&seq1);
 402   getseq (fp1, &seq1);
 403   initseq (&seq2);
 404   getseq (fp2, &seq2);
 405
 406   while (seq1.count && seq2.count)
 407     {
 408       diff = keycmp (&seq1.lines[0], &seq2.lines[0]);
 409       if (diff < 0)
 410         {
 411           if (print_unpairables_1)
 412             prjoin (&seq1.lines[0], &blank2);
 413           freeline (&seq1.lines[0]);
 414           seq1.count = 0;
 415           getseq (fp1, &seq1);
 416           continue;
 417         }
 418       if (diff > 0)
 419         {
 420           if (print_unpairables_2)
 421             prjoin (&blank1, &seq2.lines[0]);
 422           freeline (&seq2.lines[0]);
 423           seq2.count = 0;
 424           getseq (fp2, &seq2);
 425           continue;
 426         }
 427
 428       /* Keep reading lines from file1 as long as they continue to
 429          match the current line from file2. */
 430       eof1 = 0;
 431       do
 432         if (!getseq (fp1, &seq1))
 433           {
 434             eof1 = 1;
 435             ++seq1.count;
 436             break;
 437           }
 438       while (!keycmp (&seq1.lines[seq1.count - 1], &seq2.lines[0]));
 439
 440       /* Keep reading lines from file2 as long as they continue to
 441          match the current line from file1. */
 442       eof2 = 0;
 443       do
 444         if (!getseq (fp2, &seq2))
 445           {
 446             eof2 = 1;
 447             ++seq2.count;
 448             break;
 449           }
 450       while (!keycmp (&seq1.lines[0], &seq2.lines[seq2.count - 1]));
 451
 452       if (print_pairables)
 453         {
 454           for (i = 0; i < seq1.count - 1; ++i)
 455             for (j = 0; j < seq2.count - 1; ++j)
 456               prjoin (&seq1.lines[i], &seq2.lines[j]);
 457         }
 458
 459       for (i = 0; i < seq1.count - 1; ++i)
 460         freeline (&seq1.lines[i]);
 461       if (!eof1)
 462         {
 463           seq1.lines[0] = seq1.lines[seq1.count - 1];
 464           seq1.count = 1;
 465         }
 466       else
 467         seq1.count = 0;
 468
 469       for (i = 0; i < seq2.count - 1; ++i)
 470         freeline (&seq2.lines[i]);
 471       if (!eof2)
 472         {
 473           seq2.lines[0] = seq2.lines[seq2.count - 1];
 474           seq2.count = 1;
 475         }
 476       else
 477         seq2.count = 0;
 478     }
 479
 480   if (print_unpairables_1 && seq1.count)
 481     {
 482       prjoin(&seq1.lines[0], &blank2);
 483       freeline (&seq1.lines[0]);
 484       while (get_line (fp1, &line))
 485         {
 486           prjoin(&line, &blank2);
 487           freeline (&line);
 488         }
 489     }
 490
 491   if (print_unpairables_2 && seq2.count)
 492     {
 493       prjoin(&blank1, &seq2.lines[0]);
 494       freeline (&seq2.lines[0]);
 495       while (get_line (fp2, &line))
 496         {
 497           prjoin(&blank1, &line);
 498           freeline (&line);
 499         }
 500     }
 501
 502   delseq (&seq1);
 503   delseq (&seq2);
 504 }
 505
 506 /* Add a field spec for field FIELD of file FILE to `outlist' and return 1,
 507    unless either argument is invalid; then just return 0. */
 508
 509 static int
 510 add_field (file, field)
 511      int file;
 512      int field;
 513 {
 514   struct outlist *o;
 515
 516   if (file < 1 || file > 2 || field < 1)
 517     return 0;
 518   o = (struct outlist *) xmalloc (sizeof (struct outlist));
 519   o->file = file;
 520   o->field = field;
 521   o->next = NULL;
 522
 523   /* Add to the end of the list so the fields are in the right order. */
 524   if (outlist == NULL)
 525     outlist = o;
 526   else
 527     outlist_end->next = o;
 528   outlist_end = o;
 529
 530   return 1;
 531 }
 532
 533 /* Add the comma or blank separated field spec(s) in STR to `outlist'.
 534    Return the number of fields added. */
 535
 536 static int
 537 add_field_list (str)
 538      char *str;
 539 {
 540   int added = 0;
 541   int file = -1, field = -1;
 542   int dot_found = 0;
 543
 544   for (; *str; str++)
 545     {
 546       if (*str == ',' || ISBLANK (*str))
 547         {
 548           added += add_field (file, field);
 549           switch (file) {
 550            case 1: blank1.nfields = max(blank1.nfields, field); break;
 551            case 2: blank2.nfields = max(blank2.nfields, field); break;
 552           }
 553           file = field = -1;
 554           dot_found = 0;
 555         }
 556       else if (*str == '.')
 557         dot_found = 1;
 558       else if (ISDIGIT (*str))
 559         {
 560           if (!dot_found)
 561             {
 562               if (file == -1)
 563                 file = 0;
 564               file = file * 10 + *str - '0';
 565             }
 566           else
 567             {
 568               if (field == -1)
 569                 field = 0;
 570               field = field * 10 + *str - '0';
 571             }
 572         }
 573       else
 574         return 0;
 575     }
 576
 577   added += add_field (file, field);
 578   return added;
 579 }
 580
 581 /* Create a blank line with COUNT fields separated by tabs. */
 582
 583 void
 584 make_blank (blank, count)
 585      struct line *blank;
 586      int count;
 587 {
 588   int i;
 589   blank->beg = xmalloc(blank->nfields + 1);
 590   blank->fields = (struct field *)xmalloc(sizeof(struct field) * count);
 591   for (i = 0; i < blank->nfields; i++) {
 592     blank->beg[i] = '\t';
 593     blank->fields[i].lim = blank->fields[i].beg = &blank->beg[i];
 594   }
 595   blank->beg[i] = '\0';
 596   blank->lim = &blank->beg[i];
 597 }
 598
 599 void
 600 main (argc, argv)
 601      int argc;
 602      char *argv[];
 603 {
 604   char *names[2];
 605   FILE *fp1, *fp2;
 606   int optc, prev_optc = 0, nfiles, val;
 607
 608   blank1.nfields = 1;
 609   blank2.nfields = 1;
 610
 611   program_name = argv[0];
 612
 613   parse_long_options (argc, argv, usage);
 614
 615   /* Now that we've seen the options, we can construct the blank line
 616      structures.  */
 617   make_blank(&blank1, blank1.nfields);
 618   make_blank(&blank2, blank2.nfields);
 619
 620   nfiles = 0;
 621   print_pairables = 1;
 622
 623   while ((optc = getopt_long_only (argc, argv, "-a:e:1:2:o:t:v:", longopts,
 624                                    (int *) 0)) != EOF)
 625     {
 626       switch (optc)
 627         {
 628         case 0:
 629           break;
 630
 631         case 'a':
 632           val = atoi (optarg);
 633           if (val == 1)
 634             print_unpairables_1 = 1;
 635           else if (val == 2)
 636             print_unpairables_2 = 1;
 637           else
 638             error (2, 0, "invalid file number for `-a'");
 639           break;
 640
 641         case 'e':
 642           empty_filler = optarg;
 643           break;
 644
 645         case '1':
 646           val = atoi (optarg);
 647           if (val <= 0)
 648             error (2, 0, "invalid field number for `-1'");
 649           join_field_1 = val - 1;
 650           break;
 651
 652         case '2':
 653           val = atoi (optarg);
 654           if (val <= 0)
 655             error (2, 0, "invalid field number for `-2'");
 656           join_field_2 = val - 1;
 657           break;
 658
 659         case 'j':
 660           val = atoi (optarg);
 661           if (val <= 0)
 662             error (2, 0, "invalid field number for `-j'");
 663           join_field_1 = join_field_2 = val - 1;
 664           break;
 665
 666         case 'o':
 667           if (add_field_list (optarg) == 0)
 668             error (2, 0, "invalid field list for `-o'");
 669           break;
 670
 671         case 't':
 672           tab = *optarg;
 673           break;
 674
 675         case 'v':
 676           val = atoi (optarg);
 677           if (val == 1)
 678             print_unpairables_1 = 1;
 679           else if (val == 2)
 680             print_unpairables_2 = 1;
 681           else
 682             error (2, 0, "invalid file number for `-v'");
 683           print_pairables = 0;
 684           break;
 685
 686         case 1:                 /* Non-option argument. */
 687           if (prev_optc == 'o')
 688             {
 689               /* Might be continuation of args to -o. */
 690               if (add_field_list (optarg) > 0)
 691                 continue;       /* Don't change `prev_optc'. */
 692             }
 693
 694           if (nfiles > 1)
 695             usage (1);
 696           names[nfiles++] = optarg;
 697           break;
 698
 699         case '?':
 700           usage (1);
 701         }
 702       prev_optc = optc;
 703     }
 704
 705   if (nfiles != 2)
 706     usage (1);
 707
 708   fp1 = strcmp (names[0], "-") ? fopen (names[0], "r") : stdin;
 709   if (!fp1)
 710     error (1, errno, "%s", names[0]);
 711   fp2 = strcmp (names[1], "-") ? fopen (names[1], "r") : stdin;
 712   if (!fp2)
 713     error (1, errno, "%s", names[1]);
 714   if (fp1 == fp2)
 715     error (1, errno, "both files cannot be standard input");
 716   join (fp1, fp2);
 717
 718   if ((fp1 == stdin || fp2 == stdin) && fclose (stdin) == EOF)
 719     error (1, errno, "-");
 720   if (ferror (stdout) || fclose (stdout) == EOF)
 721     error (1, errno, "write error");
 722
 723   exit (0);
 724 }
 725
 726 static void
 727 usage (status)
 728      int status;
 729 {
 730   if (status != 0)
 731     fprintf (stderr, "Try `%s --help' for more information.\n",
 732              program_name);
 733   else
 734     {
 735       printf ("\
 736 Usage: %s [OPTION]... FILE1 FILE2\n\
 737 ",
 738               program_name);
 739       printf ("\
 740 \n\
 741   -a SIDE          print unpairable lines coming from file SIDE\n\
 742   -e EMPTY         replace missing input fields with EMPTY\n\
 743   -j FIELD         join on this FIELD for both files\n\
 744   -[j]SIDE FIELD   join on this FIELD for file SIDE\n\
 745   -o FORMAT        obey FORMAT while constructing output line\n\
 746   -t CHAR          use CHAR as input and output field separator\n\
 747   -v SIDE          like -a SIDE, but suppress joined output lines\n\
 748   --help           display this help and exit\n\
 749   --version        output version information and exit\n\
 750 \n\
 751 When FILE1 or FILE2 is -, not both, read standard input.  SIDE is 1\n\
 752 for FILE1 or 2 for FILE2.  Unless -t CHAR is given, leading blanks\n\
 753 separate fields and are ignored, else fields are separated by CHAR.\n\
 754 Any FIELD is a field number counted from 1.  FORMAT is one or more\n\
 755 comma or blank separated specifications, each being `SIDE.FIELD'.\n\
 756 Default FORMAT outputs the join field, the remaining fields from\n\
 757 FILE1, the remaining fields from FILE2, all separated by CHAR.\n\
 758 ");
 759     }
 760   exit (status);
 761 }