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