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