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