src/join.c

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