home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume2 / bgrep / bgrep.c < prev   
Encoding:
C/C++ Source or Header  |  1986-11-30  |  8.4 KB  |  446 lines
  1. /* bgrep --- grep using Boyer-Moore pattern matcher */
  2.  
  3. /*
  4.  * All the wrapper code (argument and file handling, printing, etc.) by
  5.  * Arnold Robbins, gatech!arnold
  6.  *
  7.  * Boyer-Moore pattern matching, coded by Roy Mongiovi, gatech!gitpyr!roy
  8.  * and edited some by Arnold Robbins.
  9.  *
  10.  * No warranty of suitability for any purpose, either expressed
  11.  * or implied, is made.
  12.  */
  13.  
  14. #include <stdio.h>
  15. #include <ctype.h>
  16.  
  17. #define TRUE    1
  18. #define FALSE    0
  19.  
  20. #define MAXPATS    120        /* (arbitrary maximum number of patterns */
  21. #define MAXLINE    (256 + 1)
  22.  
  23. /*
  24.  * command line options
  25.  */
  26.  
  27. int Allbut = FALSE;        /* print lines that don't match pattern */
  28. int Exact = FALSE;        /* only print lines that match exactly */
  29. int Countlines = FALSE;        /* only print a count of matching lines */
  30. int Listnames = FALSE;        /* only list file names that match */
  31. int Numberlines = FALSE;    /* print relative line number */
  32. int Silent = FALSE;        /* don't print anything, just exit */
  33. int Monocase = FALSE;        /* ignore case distinctions */
  34.  
  35. /*
  36.  * variables
  37.  */
  38.  
  39. long Curline = 0;        /* current file input line */
  40. long Lines_matched = 0;        /* how many lines matched the pattern */
  41.  
  42. int Lotsafiles = FALSE;        /* are there more than one file? */
  43. int Pat_length[MAXPATS];    /* length of pattern */
  44. int Line_length = 0;        /* length of line */
  45. int Couldnt_open_files = FALSE;    /* one or more files could not be opened */
  46. int Exit_val = 0;        /* return code status */
  47. int Curpat = 0;            /* current pattern comparing against */
  48. int Numpats = 0;        /* total number of patterns */
  49.  
  50. char Inbuf[MAXLINE];        /* input buffer */
  51. char Pattern[MAXPATS][MAXLINE];    /* pattern to be matched; init = NULs */
  52. char *Program = NULL;        /* program name */
  53.  
  54. int Argc;            /* make argc and argv global */
  55. char **Argv;
  56.  
  57. extern char *basename();    /* leaf file of a pathname */
  58.  
  59. main (argc, argv, envp)
  60. int argc;
  61. char **argv, **envp;
  62. {
  63.     register int i, j;
  64.     char *index();
  65.  
  66.     Program = basename (argv[0]);
  67.     Argc = argc;
  68.     Argv = argv;
  69.  
  70.     parse_args ();        /* deal with command line */
  71.  
  72.     if (Pattern[0][0] == '\0')    /* not from -f or -e */
  73.     {
  74.         if (Argv[0] == NULL)    /* no string given */
  75.             usage ();
  76.         setpats (Argv[0]);
  77.         Argc--;
  78.         Argv++;
  79.     }
  80.  
  81.     for (Curpat = 0; Curpat <= Numpats; Curpat++)
  82.     {
  83.         if (Monocase)
  84.             mapdown (Pattern[Curpat]);
  85.  
  86.         Pat_length[Curpat] = strlen (Pattern[Curpat]);
  87.         initialize ();        /* set up necessary tables */
  88.     }
  89.  
  90.     Lotsafiles = (Argc > 1);    /* more than one file left */
  91.  
  92.     if (Argc == 0)        /* search stdin */
  93.         process ("-");
  94.     else
  95.         for (i = 0; Argv[i] != NULL; i++)
  96.             process (Argv[i]);
  97.     
  98.     if (! Silent && Countlines)
  99.         printf ("%ld\n", Lines_matched);
  100.  
  101.     if (Lines_matched == 0)
  102.         exit (1);
  103.     else if (Couldnt_open_files)
  104.         exit (2);
  105.     else
  106.         exit (0);
  107. }
  108.  
  109. /* process --- start doing the work on each file */
  110.  
  111. process (infile)
  112. register char *infile;
  113. {
  114.     FILE *fp;
  115.     int c;
  116.     int success;
  117.     long prev_lines_matched = Lines_matched;    /* save count */
  118.  
  119.     Curline = 0;    /* reset for each file */
  120.  
  121.     if (infile[0] == '-' && infile[1] == '\0')
  122.         fp = stdin;
  123.     else if ((fp = fopen (infile, "r")) == NULL)
  124.     {
  125.         Couldnt_open_files = TRUE;
  126.         perror (infile);
  127.         return;
  128.     }
  129.  
  130.     while (fgets (Inbuf, sizeof Inbuf, fp) != NULL)
  131.     {
  132.         Curline++;
  133.         if (Monocase)
  134.             mapdown (Inbuf);
  135.         Line_length = strlen (Inbuf);
  136.  
  137.         /* first, throw away rest of a truncated input line */
  138.         if (Inbuf[Line_length - 1] != '\n')
  139.             while ((c = getc (fp)) != '\n')
  140.                 ;
  141.         else
  142.             Inbuf[--Line_length] = '\0';
  143.             /* newline is there, nuke it */
  144.  
  145.         for (Curpat = 0; Curpat <= Numpats; Curpat++)
  146.         {
  147.             if (success = match ())
  148.                 Lines_matched++;
  149.             /* do any necessary output */
  150.             if (! Silent && ! Countlines && ! Listnames &&
  151.                 ((success != FALSE) ^ (Allbut != FALSE)))
  152.                 /* either success, or Allbut, but not both,
  153.                    and not neither */
  154.             {
  155.                 if (Lotsafiles)
  156.                     printf ("%s: ", infile);
  157.                 if (Numberlines)
  158.                     printf ("%ld: ", Curline);
  159.                 printf ("%s\n", Inbuf);
  160.             }
  161.         }
  162.     }
  163.  
  164.     fclose (fp);
  165.     if (! Silent && Listnames && prev_lines_matched < Lines_matched)
  166.         printf ("%s\n", infile);
  167. }
  168.  
  169. /* parse_args --- check out command line arguments */
  170.  
  171. parse_args ()
  172. {
  173.     register int i,j;
  174.  
  175.     if (Argc == 1)
  176.         usage ();
  177.  
  178.     for (Argc--, Argv++; Argv[0] != NULL && Argv[0][0] == '-'; Argc--, Argv++)
  179.     {
  180.         int cheat = FALSE;
  181.  
  182.         for (j = 1; Argv[0][j] != '\0'; j++)
  183.         {
  184.             switch (Argv[0][j]) {
  185.             case 'c':
  186.                 Countlines = TRUE;
  187.                 break;
  188.  
  189.             case 'e':
  190.                 strcpy (Pattern[0], Argv[1]);
  191.                 Pattern[0][sizeof Pattern[0] - 1] = '\0';
  192.                 cheat = TRUE;
  193.                 continue;
  194.  
  195.             case 'f':
  196.                 patfromfile (Argv[1]);
  197.                 cheat = TRUE;
  198.                 continue;
  199.  
  200.             case 'i':
  201.             case 'y':
  202.                 Monocase = TRUE;
  203.                 break;
  204.  
  205.             case 'l':
  206.                 Listnames = TRUE;
  207.                 break;
  208.  
  209.             case 'n':
  210.                 Numberlines = TRUE;
  211.                 break;
  212.  
  213.             case 's':
  214.                 Silent = TRUE;
  215.                 break;
  216.  
  217.             case 'v':
  218.                 Allbut = TRUE;
  219.                 break;
  220.  
  221.             case 'x':
  222.                 Exact = TRUE;
  223.                 break;
  224.  
  225.             default:
  226.                 usage ();
  227.                 break;
  228.             }
  229.         }
  230.         if (cheat)
  231.         {
  232.             cheat = FALSE;
  233.             Argc--;
  234.             Argv++;
  235.             /* boy is this stuff a kludge! */
  236.         }
  237.     }
  238.  
  239.     /* check for argument conflicts */
  240.     if (
  241.         (Silent &&
  242.             (Allbut || Exact || Countlines || Listnames ||
  243.                 Numberlines))
  244.         ||
  245.         (Allbut && Exact)
  246.         ||
  247.         (Countlines && Listnames)
  248.     )
  249.     {
  250.         fprintf (stderr, "%s: argument conflict -- see the man page\n",
  251.             Program);
  252.         usage ();    /* will exit */
  253.     }
  254. }
  255.  
  256. /* mapdown --- remove case distinctions in a string */
  257.  
  258. mapdown (str)
  259. register char *str;
  260. {
  261.     register int i;
  262.  
  263.     for (i = 0; str[i] != '\0'; i++)
  264.         if (isupper (str[i]))
  265.             str[i] = tolower (str[i]);
  266. }
  267.  
  268. /* return basename part of a pathname, if '/'s are present */
  269.  
  270. char *basename (str)
  271. register char *str;
  272. {
  273.     register int i = 0;
  274.     register int j = 0;
  275.  
  276.     for (; str[i] != '\0'; i++)
  277.         if (str[i] == '/')
  278.             j = i;
  279.     
  280.     if (j != 0)
  281.         return (& str[++j]);
  282.     else
  283.         return (str);
  284. }
  285.  
  286. /* usage --- print usage message and die */
  287.  
  288. usage ()
  289. {
  290.     fprintf (stderr, "usage: %s [-vxclnisef] [string] [files]\n",
  291.             Program);
  292.     exit (2);
  293. }
  294.  
  295. /* index --- do index by hand so it'll work on any Unix */
  296.  
  297. char *index (str, c)
  298. char *str, c;
  299. {
  300.     for (; *str; str++)
  301.         if (*str == c)
  302.             return (str);
  303.     
  304.     return (NULL);
  305. }
  306.  
  307. /* patfromfile --- retrieve the pattern from the named file */
  308.  
  309. patfromfile (infile)
  310. char *infile;
  311. {
  312.     register int i, j;
  313.     register FILE *fp;
  314.     register int c;
  315.  
  316.     if ((fp = fopen (infile, "r")) == NULL ||
  317.             (c = getc (fp)) == EOF)
  318.     {
  319.         perror (infile);    /* be like standard grep */
  320.         exit (2);
  321.     }
  322.     else
  323.         ungetc (c, fp);
  324.  
  325.     for (i = 0; fgets (Pattern[i], MAXLINE, fp) != NULL; i++)
  326.     {
  327.         if (i >= 120)
  328.         {
  329.             fprintf (stderr, "%s: Only %d strings allowed\n",
  330.                 Program, MAXPATS);
  331.             exit (2);
  332.         }
  333.         j = strlen (Pattern[i]);
  334.         if (Pattern[i][j - 1] == '\n')
  335.             Pattern[i][--j] = '\0';
  336.     }
  337.     Numpats = i - 1;
  338.  
  339.     fclose (fp);
  340. }
  341.  
  342. /* setpats --- set up the patterns from a string */
  343.  
  344. setpats (str)
  345. register char *str;
  346. {
  347.     register int i, j;
  348.  
  349.     while (*str == '\n' || *str == '\r')
  350.         str++;
  351.  
  352.     for (i = j = 0; *str; str++)
  353.     {
  354.         if (*str == '\n')
  355.         {
  356.             Pattern[i][j] = '\0';
  357.             j = 0;
  358.             i++;
  359.         }
  360.         else
  361.             Pattern[i][j++] = *str;
  362.     }
  363.     Numpats = i;
  364. }
  365.  
  366. /* begin magic stuff for Boyer-Moore pattern matching */
  367.  
  368. int D1[MAXPATS][128];
  369. int D2[MAXPATS][128];
  370.  
  371. int F[MAXPATS][128];
  372.  
  373. initialize ()
  374. {
  375.     register int i, t;
  376.  
  377.     for (i = 0; i < 128; i++)
  378.         D1[Curpat][i] = Pat_length[Curpat];
  379.     
  380.     for (i = 0; i < Pat_length[Curpat]; i++)
  381.         D1[Curpat][Pattern[Curpat][i]] = Pat_length[Curpat] - i - 1;
  382.     
  383.     for (i = 0; i < Pat_length[Curpat]; i++)
  384.         D2[Curpat][i] = (Pat_length[Curpat] << 1) - i - 1;
  385.     
  386.     for (i = (t = Pat_length[Curpat]) - 1; i >= 0; i--, t--)
  387.         for (F[Curpat][i] = t; t < Pat_length[Curpat]
  388.             && Pattern[Curpat][i] != Pattern[Curpat][t];
  389.                             t = F[Curpat][t])
  390.             if (Pat_length[Curpat] - i - 1 < D2[Curpat][t])
  391.                 D2[Curpat][t] = Pat_length[Curpat] - i - 1;
  392.  
  393.     for (i = 0; i <= t; i++)
  394.         if (Pat_length[Curpat] + t - i < D2[Curpat][i])
  395.             D2[Curpat][i] = Pat_length[Curpat] + t - i;
  396. }
  397.  
  398. /* match --- do Boyer-Moore pattern search on input buffer */
  399.  
  400. match ()
  401. {
  402.     register int i, j;
  403.  
  404.     if (Exact && Pat_length[Curpat] != Line_length)
  405.         return FALSE;
  406.  
  407.     i = Pat_length[Curpat] - 1;
  408.  
  409.     while (i < Line_length)
  410.     {
  411.         j = Pat_length[Curpat] - 1;
  412.         while (j >= 0)
  413.         {
  414.             if (Inbuf[i] == Pattern[Curpat][j])
  415.                 i--, j--;
  416.             else
  417.                 break;
  418.         }
  419.  
  420.         if (j < 0)
  421.         {
  422.             /* found a match */
  423.             return TRUE;
  424.             /*
  425.              * note: if we were going to seach for further matches
  426.              * on the input line, we would do this:
  427.              *
  428.              * i += Pat_length[Curpat] + 1;
  429.              *
  430.              * which shifts right by Pat_length[Curpat] + 1 places
  431.              */
  432.         }
  433.         else
  434.         {
  435.             j = (D1[Curpat][Inbuf[i]] >= D2[Curpat][j]) ?
  436.                 D1[Curpat][Inbuf[i]]
  437.             :
  438.                 D2[Curpat][j];
  439.             i += j;
  440.             /* shift right by j places */
  441.         }
  442.     }
  443.  
  444.     return FALSE;
  445. }
  446.