home *** CD-ROM | disk | FTP | other *** search
/ Shareware Overload / ShartewareOverload.cdr / progm / cpgms.zip / FGREP.C < prev    next >
C/C++ Source or Header  |  1985-11-17  |  24KB  |  948 lines
  1. /* FGREP.C  - Search File(s) for Fixed Pattern(s)
  2.  *
  3.  * Version 1.01      February 11th, 1985
  4.  *
  5.  * Modifications:
  6.  *    V1.00 (84/12/01)    - beta test release
  7.  *    V1.01 (85/01/01)    - added -P option
  8.  *                        - improved command line validation
  9.  *    V1.02 (85/01/06)    - modified "run_fsa()" and "bd_move()"
  10.  *    V1.03 (85/02/11)    - added -S option
  11.  *
  12.  * Copyright 1985:        Ian Ashdown
  13.  *                        by Heart Software
  14.  *                        1089 West 21st Street
  15.  *                        North Vancouver, B.C V7P 2C6
  16.  *
  17.  * This program may be copied for personal, non-commercial use
  18.  * only, provided that the above copyright notice is included in
  19.  * all copies of the source code.  Copying for any other use
  20.  * without previously obtaining the written permission of the
  21.  * author is prohibited.
  22.  *
  23.  * Machine readable versions of this program may be purchased for
  24.  * $35.00 (U.S.) from byHeart Software.  Supported disk formats
  25.  * are CP/M 8" SSSD and PC-DOS (v2.x) 5-1/4" DSDD.
  26.  *
  27.  * Notes:
  28.  *
  29.  * The algorithm used in this program constructs a deterministic
  30.  * finite state automaton (FSA) for pattern matching from the sub-
  31.  * strings, then uses the FSA to process the text string in one
  32.  * pass.  The time taken to construct the FSA is proportional to
  33.  * the sum of the lengths of the substrings.  The number of
  34.  * state transitions made by the FSA in processing the text
  35.  * string is independent of the number of substrings.
  36.  *
  37.  * Algorithm Source:
  38.  *
  39.  * "Efficient String Matching: An Aid to Bibliographic Search"
  40.  * Alfred V. Aho & Margaret J. Corasick
  41.  * Communications of the ACM
  42.  * pp. 333-340, Vol. 18 No. 6 (June '75)
  43.  *
  44.  * USAGE: fgrep [-vclnhyefxps] [strings] <files>
  45.  *
  46.  * where:
  47.  *
  48.  *        -v        All lines but those matched are  printed.
  49.  *        -c        Only a count of the matching lines is printed.
  50.  *        -l        The names of the files with matching lines are
  51.  *                listed (once), separated by newlines.
  52.  *        -n        Each line is preceded by its line number in the
  53.  *                file.
  54.  *        -h        Do not print filename headers with output lines.
  55.  *        -y        All characters in the file are mapped to upper
  56.  *                case before matching.  (This is the default if the
  57.  *                string is given in the command line under CP/M,
  58.  *                as CP/M maps everything on the command line to
  59.  *                upper case.  Use the -f option if you need both
  60.  *                lower and upper case.)    Not a true UNIX "fgrep"
  61.  *                option (normally available under "grep" only),
  62.  *                but too useful to leave out.
  63.  *        -e        <string>.  Same as a string argument, but useful
  64.  *                when the string begins with a '-'.
  65.  *        -f        <file>.  The strings (separated by newlines) are
  66.  *                taken from a file.  If several strings are listed
  67.  *                in the file, then a match is flagged if any of
  68.  *                the strings are matched.  If -f is given, any
  69.  *                following argument on the command line is taken
  70.  *                to be a filename.
  71.  *        -x        Only lines matched in their entirety are printed.
  72.  *        -p        Each matched line is preceded by the matching
  73.  *                substring(s).  Not a UNIX "fgrep" option, but too
  74.  *                useful to leave out.
  75.  *        -s        No output is produced, only status.  Used when
  76.  *                "fgrep" is run as a process that returns a
  77.  *                status value to its parent process.  Under CP/M, a
  78.  *                non-zero value returned by "exit()" may terminate
  79.  *                a submit file that initiated the program,
  80.  *                although this is implementation-dependant.
  81.  *
  82.  * DIAGNOSTICS:
  83.  *
  84.  * Exit status is 0 if any matches are found, 1 if none, 2 for
  85.  * error condition.
  86.  *
  87.  * BUGS:
  88.  *
  89.  * The following UNIX-specific optiono is not supported:
  90.  *
  91.  *        -b        Each line is preceded by the block number in
  92.  *                which it was found.
  93.  *
  94.  *
  95.  * Lines are limited to 256 characters.
  96.  *
  97.  */
  98.  
  99. /*** Definitions ***/
  100. #define TRUE        -1
  101. #define FALSE        0
  102. #define MAX_LINE    257    /* Maximum number of characters */
  103.                         /* per line plus NULL delimiter */
  104. /* #define CP/M  */           /* Comment out for compilation */
  105.                         /* under UNIX */
  106. #define MSDOS         1    /* 1 if running under MSDOS, else 0 */
  107. #define DESMET        1    /* 1 if using the DeSmet C compiler, else 0 */
  108.  
  109. #define CMD_ERR     0    /* Error Codes */
  110. #define OPT_ERR     1
  111. #define INP_ERR     2
  112. #define STR_ERR     3
  113. #define MEM_ERR     4
  114.  
  115. /*** TYPEDEFS ***/
  116. typedef int BOOL;        /* BOOLEAN FLAG */
  117.  
  118. /*** Data Structures ***/
  119.  
  120.  
  121. char    *documentation[] = {
  122. "fgrep search a set of files for one or more strings",
  123. "   fgrep [flags] [string] file_list [>file]",
  124. "",
  125. "Flags are single characters preceeded by '-':",
  126. "   -v      All lines but those matched are sent to STDOUT.",
  127. "   -c      Only a count of the matching lines is output.",
  128. "   -l      Only names of the files with matching lines are output.",
  129. "   -n      Each line is preceeded by its line number.",
  130. "   -h      Do not output filename headers with output lines.",
  131. "   -y      The input file is mapped to upper case prior to matching.",
  132. "   -e      <string>.  Same as string argument, but useful when the ",
  133. "   -f      <file>.  The strings (separated by newlines) are taken ",
  134. "           from a file. A match is flagged if any string is matched. ",
  135. "           The next argument is taken to be a filename. ",
  136. "   -x      Only lines matched in their entirety are output.",
  137. "   -s      No output is produced, only ERRORLEVEL.  Used in BAT files.",
  138. " ",
  139. "  ERRORLEVEL is set to zero if any matches are found, one if none are ",
  140. "         found, and two for error conditions.",
  141. " ",
  142. "The file_list is a list of files (wildcards are acceptable).",
  143. "",
  144. "Output is to stdout.  To print add >PRN: to your command.",
  145. 0 };
  146.  
  147. /*  Queue element  */
  148.  
  149. typedef struct queue
  150. {
  151.     struct state_el *s_ptr;
  152.     struct queue *next_elq;
  153. } QUEUE;
  154.  
  155. /*  Transition element    */
  156. typedef struct transition
  157. {
  158.     char lchar;                        /* Transition character */
  159.     struct state_el *nextst_ptr;    /* Transition state pointer */
  160.     struct transition *next_el;
  161. } TRANSITION;
  162.  
  163. /*  FSA state element  */
  164. typedef struct state_el
  165. {
  166.     TRANSITION *go_ls;                /* Pointer to head of "go" list */
  167.     TRANSITION *mv_ls;                /* Pointer to head of "move" list */
  168.     struct state_el *fail_state;    /* "failure" transition state */
  169.     char *out_str;                    /* Terminal state message (if any) */
  170. } FSA;
  171.  
  172. /*** Gloval Variables and Structures ***/
  173. /*  Dummy "failure" state  */
  174. FSA FAIL_STATE;
  175.  
  176. /* Define a separate data structure for State 0 of the FSA to
  177.  * speed processing of the input while the FSA is in that state.
  178.  * Since the Aho-Corasick algorithm only defines "go" transitions
  179.  * for this state (one for each valid input character) and no
  180.  * "failure" transitions or output messages, only an array of
  181.  * "go" transition state numbers is needed.  The array is accessed
  182.  * directly, using the input character as the index.
  183.  */
  184.  
  185. FSA *MZ[128];            /* State 0 of FSA */
  186.  
  187. BOOL vflag = FALSE,        /* Command-line option flags  */
  188.      cflag = FALSE,
  189.      lflag = FALSE,
  190.      nflag = FALSE,
  191.      hflag = FALSE,
  192.      yflag = FALSE,
  193.      eflag = FALSE,
  194.      fflag = FALSE,
  195.      xflag = FALSE,
  196.      pflag = FALSE,
  197.      dflag = FALSE,
  198.      sflag = FALSE;
  199.  
  200. /*** Include Files ***/
  201. #include <stdio.h>
  202. #if DESMET
  203. #else
  204. #include <ctype.h>
  205. #endif
  206.  
  207. /*** Main Body of Program ***/
  208.  
  209. int main(argc, argv)
  210. int argc;
  211. char **argv;
  212. {
  213.     char *temp, *p, *fexpnd();
  214.     BOOL match_flag = FALSE, proc_file();
  215.     void bd_go(), bd_move(), error();
  216.  
  217. /* Check for minimum number of command line arguments */
  218.     if (argc < 2)
  219.         error(CMD_ERR, NULL);
  220.  
  221.    if (argc == 2 && argv[1][0] == '?' && argv[1][1] == 0) {
  222.       help(documentation);
  223.       return;
  224.       }
  225.  
  226. /* Parse the command line for user-selected options */
  227.     while (--argc && (*++argv)[0] == '-' && eflag == FALSE)
  228.         for (temp = argv[0]+1; *temp != '\0'; temp++)
  229.             switch(toupper(*temp))
  230.             {
  231.  
  232.                 case '?':
  233.                    help(documentation);
  234.                    break;
  235.  
  236.                 case 'V':
  237.                     vflag = TRUE;
  238.                     break;
  239.                 case 'C':
  240.                     cflag = TRUE;
  241.                     break;
  242.                 case 'L':
  243.                     lflag = TRUE;
  244.                     break;
  245.                 case 'N':
  246.                     nflag = TRUE;
  247.                     break;
  248.                 case 'H':
  249.                     hflag = TRUE;
  250.                     break;
  251.                 case 'Y':
  252.                     yflag = TRUE;
  253.                     break;
  254.                 case 'E':
  255.                     eflag = TRUE;
  256.                     break;
  257.                 case 'F':
  258.                     fflag = TRUE;
  259.                     break;
  260.                 case 'X':
  261.                     xflag = TRUE;
  262.                     break;
  263.                 case 'P':
  264.                     pflag = TRUE;
  265.                     break;
  266.                 case 'D':
  267.                     dflag = TRUE;
  268.                     break;
  269.                 case 'S':
  270.                     sflag = TRUE;
  271.                     break;
  272.                 default:
  273.                     error(OPT_ERR, NULL);
  274.             }
  275.  
  276. /* "pflag" can only be TRUE if the following flags are FALSE */
  277.     if (vflag == TRUE || cflag == TRUE || lflag == TRUE ||
  278.         xflag == TRUE || sflag == TRUE)
  279.         pflag = FALSE;
  280.  
  281. /* Check for string (or string file) argument */
  282.     if (!argc)
  283.         error(CMD_ERR, NULL);
  284.  
  285. /*  show available space */
  286.     if (dflag)
  287.         printf(" Available Memory = %u \n", (unsigned)(_showsp() - _memory()));
  288.  
  289. /* Build the "go" transitions */
  290.     bd_go(*argv++);
  291.     argc--;
  292.  
  293. /* Build the "failure" and "move" transitions */
  294.     bd_move();
  295.  
  296. /* Process each of the input files if not "stdin". */
  297.     if (argc < 2)
  298.         hflag = TRUE;
  299.     if (!argc)
  300.     {
  301.         if (proc_file(NULL, FALSE) == TRUE && match_flag == FALSE)
  302.             match_flag = TRUE;
  303.     }
  304.     else
  305.         while (argc--) {
  306. #if MSDOS
  307.             while (p = fexpnd(*argv))     /* expand wildcards, etc */
  308. #else
  309.             if (p = *argv) 
  310. #endif
  311.                 if (proc_file(p, TRUE) == TRUE && match_flag == FALSE)
  312.                     match_flag = TRUE;
  313.             argv++;
  314.         }
  315.  
  316. /* Return status to the parent process. Status is zero if any
  317.  * matches are found, 1 if none.  */
  318.  
  319.     if (match_flag == TRUE)
  320.         exit(0);
  321.     else
  322.         exit(1);
  323.  
  324. }  /* end of main */
  325.  
  326.  
  327. /*** Functions and Procedures ***/
  328.  
  329. /* PROC_FILE() - Run the FSA on the input file "in_file".  Returns
  330.  *         TRUE if a match was found, FALSE otherwise.  */
  331.  
  332. BOOL proc_file(in_file, prt_flag)
  333. char *in_file;
  334. BOOL prt_flag;
  335. {
  336.     char buffer[MAX_LINE],        /* input string buffer */
  337.         *nl, *index(), *stoupper(), *fgets();
  338.  
  339.     long line_cnt = 0L,            /* line counter */
  340.         mtch_cnt  = 0L;         /* matched line counter  */
  341.     BOOL mtch_flag,             /* Matched line flag */
  342.         run_fsa();
  343.     FILE *in_fd, *fopen();
  344.     void error();
  345.  
  346.     if (in_file != NULL)        /* A file was specified as the input */
  347.     {
  348.         if (!(in_fd = fopen(in_file, "r")))
  349.             error(INP_ERR, in_file);
  350.     }
  351.     else
  352.         in_fd = stdin;
  353.  
  354.  
  355. /* Read in a line at a time for processing */
  356.     while (fgets(buffer, MAX_LINE, in_fd))
  357.     {
  358.         if (nl = index(buffer, '\n'))           /* remove newline */
  359.             *nl = '\0';
  360. #if DESMET
  361.         if (nl = index(buffer, '\r'))           /* remove carriage return */
  362.             *nl = '\0';
  363. #endif
  364. #ifdef CP/M
  365.         if (fflag == FALSE || yflag == TRUE)
  366.             stoupper(buffer);
  367. #else
  368.         if (yflag == TRUE)
  369.             stoupper(buffer);
  370. #endif
  371.         line_cnt++;
  372.         if ((mtch_flag = run_fsa(buffer)) == TRUE)
  373.             mtch_cnt++;        /* incr matched line counter */
  374.         if (cflag == FALSE && lflag == FALSE && sflag == FALSE &&
  375.             ((mtch_flag == TRUE && vflag == FALSE) ||
  376.             (mtch_flag == FALSE && vflag == TRUE)))
  377.         {
  378.             if (hflag == FALSE && prt_flag == TRUE)
  379.                 printf("%s: ", in_file);
  380.             if (nflag == TRUE)
  381.                 printf("%05ld: ", line_cnt);
  382.             puts(buffer);
  383. #if DESMET
  384.             puts("\n");
  385. #endif
  386.         }
  387.     }
  388.     if (lflag == TRUE && mtch_cnt > 0)
  389.         printf("%s\n", in_file);
  390.     else if (cflag == TRUE && sflag == FALSE)
  391.         printf("%ld\n", mtch_cnt);
  392.     if (in_file != NULL)
  393.         fclose(in_fd);
  394.     if (mtch_cnt)            /* match found? */
  395.         return TRUE;        /* ..yes */
  396.     else
  397.         return FALSE;        /* ..no  */
  398.  
  399. } /* end of proc_file  */
  400.  
  401.  
  402. /* RUN_FSA() - Run the finite state automaton with string "str"
  403.  *           as input.  Return TRUE if match, FALSE otherwise.
  404.  */
  405.  
  406. BOOL run_fsa(str)
  407. register char *str;
  408. {
  409.     register FSA *st_ptr;
  410.     char *message = NULL;
  411.     BOOL msg_flag = FALSE;
  412.     FSA *go(), *move();
  413.  
  414.     st_ptr = NULL;            /* Initialize FSA */
  415.     if (xflag == FALSE)
  416.     {
  417.         /* Process next input character in the string */
  418.         while (*str)
  419.         {
  420.             st_ptr = move(st_ptr, *str);
  421.  
  422.             /* print terminal state message and update FSA */
  423.             if (st_ptr == 0 && message)
  424.             {
  425.                 printf("\n--> %s ", message);
  426.                 message = NULL;
  427.                 st_ptr = move(st_ptr, *str);
  428.             }
  429.             str++;
  430.             if (st_ptr)
  431.                 if (st_ptr->out_str)    /* Terminal state */
  432.                     if (pflag == TRUE)
  433.                     {
  434.                         /* Save terminal state message */
  435.                         message = st_ptr->out_str;
  436.                         msg_flag = TRUE;
  437.                     }
  438.                     else
  439.                         return TRUE;
  440.         }
  441.         if (message)        /* Print any remaining terminal state message */
  442.             printf("\n--> %s ", message);
  443.         return msg_flag;
  444.     }
  445.     else    /* match exact lines only */
  446.     {
  447.         while(*str)
  448.         {
  449.             st_ptr = go(st_ptr, *str++);
  450.                 if (!st_ptr || st_ptr == &FAIL_STATE)
  451.                     return FALSE;        /* line not matched */
  452.         }
  453.         return TRUE;
  454.     }
  455. }   /* end of run_fsa  */
  456.  
  457.  
  458. /* GO() - Process "litchar" and return a pointer to the FSA's
  459.  *      corresponding "go" transition state.  If the character
  460.  *      is not in the FSA state's "go" transition list, then
  461.  *      return a pointer to FAIL_STATE.
  462.  */
  463.  
  464. FSA *go(st_ptr, litchar)
  465. FSA *st_ptr;
  466. register char litchar;
  467. {
  468.     register TRANSITION *current;
  469.  
  470.     /* If state 0, then access separate state 0 data structure of
  471.      * the FSA.  Note that there are no failure states defined for
  472.      * any input to FSA state 0.
  473.      */
  474.  
  475.     if (!st_ptr)
  476.         return MZ[litchar];
  477.     else
  478.     {
  479.         /* Point to the head of the linked list of "go" transitions
  480.          * associated with the state.
  481.          */
  482.  
  483.         current = st_ptr->go_ls;
  484.  
  485.         /* Transverse the list looking for a match to othe input
  486.          * character.
  487.          */
  488.  
  489.         while (current)
  490.         {
  491.             if (current->lchar == litchar)
  492.                 break;
  493.             current = current->next_el;
  494.         }
  495.  
  496.         /* Null value for "current" indicates end of list was reached
  497.          * without having found match to input character.
  498.          */
  499.  
  500.         return current ? current->nextst_ptr : &FAIL_STATE;
  501.     }
  502. }  /*  end of go  */
  503.  
  504.  
  505.  
  506. /* MOVE() - Process "litchar" and return a pointer to the FSA's
  507.  *        corresponding "move" transition state.
  508.  */
  509.  
  510. FSA *move(st_ptr, litchar)
  511. FSA *st_ptr;
  512. register char litchar;
  513. {
  514.     register TRANSITION *current;
  515.  
  516.     /* If state 0, then access separate state data structure of
  517.      * the FSA.
  518.      */
  519.  
  520.     if (!st_ptr)
  521.         return MZ[litchar];
  522.     else
  523.     {
  524.         /* Point to the head of the linked list of "move" transitions
  525.          * associated with the state.
  526.          */
  527.  
  528.         current = st_ptr->mv_ls;
  529.  
  530.         /* Transverse the list looking for a match to the input
  531.          * character.
  532.          */
  533.  
  534.         while (current)
  535.         {
  536.             if (current->lchar == litchar)
  537.                 break;
  538.             current = current->next_el;
  539.         }
  540.  
  541.         /* Null value for "current" indicates end of list was reached
  542.          * without having found match to input character.  The
  543.          * returned pointer is then to state 0.
  544.          */
  545.  
  546.         return current ? current->nextst_ptr : NULL;
  547.     }
  548. }  /* end of move()  */
  549.  
  550.  
  551.  
  552. /* BD_GO() - Build the "go" transitons for each state from the
  553.  *         command line arguments.
  554.  */
  555.  
  556. void bd_go(str)
  557. char *str;
  558. {
  559.     register char litchar;
  560.     char *nl,
  561.         buffer[MAX_LINE],            /* input string buffer    */
  562.         *stoupper(), *fgets(), *index();
  563.     FILE *str_fd, *fopen();
  564.     void error(), enter();
  565.  
  566.     /* Initialize FSA state 0 "go" transition array so that every
  567.      * invocation of "go()" with "state" = 0 initially returns a
  568.      * pointer to FAIL_STATE.
  569.      */
  570.  
  571.     for (litchar = 1; litchar <= 127; litchar++)
  572.         MZ[litchar] = &FAIL_STATE;
  573.  
  574.     /* If the -f option was selected, get the newline-separated
  575.      * strings from the file "str" one at a time and enter them
  576.      * into the FSA.  Otherwise, enter the string "str" into the
  577.      * FSA.
  578.      */
  579.  
  580.     if (fflag == TRUE)
  581.     {
  582.         if (!(str_fd = fopen(str, "r")))
  583.             error(STR_ERR, str);
  584.         while (fgets(buffer, MAX_LINE, str_fd))
  585.         {
  586.             if (nl = index(buffer, '\n'))   /* remove the newline */
  587.                 *nl = '\0';
  588. #if DESMET
  589.             if (nl = index(buffer, '\r'))           /* remove carriage return */
  590.                 *nl = '\0';
  591. #endif
  592.             if (yflag == TRUE) 
  593.                 stoupper(buffer);
  594.             enter(buffer);
  595.         }
  596.         fclose(str_fd);
  597.     }
  598.     else
  599.     {
  600.         if (yflag == TRUE) 
  601.             stoupper(str);
  602.         enter(str);
  603.     }
  604.  
  605.     /* For every input character that does not lead to a defined
  606.      * "go" transition from FSA state 0, set the corresponding
  607.      * element in the state 0 "go" trasitions array to indicate
  608.      * a "go" transtion to state 0.
  609.      */
  610.  
  611.     for (litchar = 1; litchar <= 127; litchar++)
  612.         if (MZ[litchar] == &FAIL_STATE)
  613.             MZ[litchar] = NULL;
  614.  
  615. } /* end of bd_go  */
  616.  
  617.  
  618.  
  619. /* ENTER() - Enter a string into the FSA by running each
  620.  *         character in thrun through the current partially-
  621.  *         built FSA.  When a failure occurs, add the remainder
  622.  *         of the string to the FSA as one new state per
  623.  *         character.  (Note the '\0' can never be a valid
  624.  *         character - C uses it to terminate a string.)
  625.  */
  626.  
  627. void enter(str)
  628. char *str;
  629. {
  630.     FSA *s, *go(), *create();
  631.     TRANSITION *current, *insert();
  632.     char *strsave();
  633.     register char *temp;
  634.     register FSA *st_ptr = NULL;   /* Start in FSA State 0 */
  635.     register FSA *nextst_ptr;
  636.     void error();
  637.  
  638.     /* Run each character in turn through partially-built FSA until
  639.      * a failure occurs.
  640.      */
  641.  
  642.     temp = str;
  643.     while ((s = go(st_ptr, *temp)) != &FAIL_STATE)
  644.     {
  645.         temp++;
  646.         st_ptr = s;
  647.     }
  648.  
  649.     /* Process the remainder of the string */
  650.  
  651.     while (*temp)
  652.     {
  653.         /* If a new state, then create a new state and insert
  654.          * transitiono character and "go" transition in current
  655.          * state. (Note special case of FSA state 0.)
  656.          */
  657.  
  658.         if (!st_ptr)
  659.             nextst_ptr = MZ[*temp++] = create();
  660.         else if (!(current = st_ptr->go_ls))
  661.         {
  662.             nextst_ptr = create();
  663.             st_ptr->go_ls = insert(nextst_ptr, *temp++);
  664.         }
  665.         else
  666.         {
  667.             /* ... or it was the character that the FSA returned a
  668.              * "failure" for.  Find the tail of the current state's list
  669.              * of "go" transitions, create a new state and append it
  670.              * to the current state's "go" list.
  671.              */
  672.  
  673.             while (current->next_el)
  674.                 current = current->next_el;
  675.             nextst_ptr = create();
  676.             current->next_el = insert(nextst_ptr, *temp++);
  677.         }
  678.         st_ptr = nextst_ptr;
  679.     }
  680.     /* Make string terminal state's output message */
  681.     st_ptr->out_str = strsave(str);
  682. }  /* end of enter() */
  683.  
  684.  
  685.  
  686. /* INSERT() - Create a new "go" transition and return a pointer
  687.  *          to it.
  688.  */
  689.  
  690. TRANSITION *insert(st_ptr, litchar)
  691. FSA *st_ptr;
  692. char litchar;
  693. {
  694.     TRANSITION *current;
  695.     char *malloc();
  696.     void error();
  697.  
  698.     if (!(current = (TRANSITION *)malloc(sizeof(TRANSITION))))
  699.         error(MEM_ERR, NULL);
  700.     current->lchar = litchar;
  701.     current->nextst_ptr = st_ptr;
  702.     current->next_el = NULL;
  703.     return current;
  704. }  /* end of insert() */
  705.  
  706.  
  707.  
  708. /* CREATE() - Create an FSA state and return a pointer to it. */
  709.  
  710. FSA *create()
  711. {
  712.     FSA *st_ptr;
  713.     char *malloc();
  714.     void error();
  715.  
  716.     if (!(st_ptr = (FSA *)malloc(sizeof(FSA))))
  717.         error(MEM_ERR, NULL);
  718.     st_ptr->go_ls = st_ptr->mv_ls = NULL;
  719.     st_ptr->fail_state = NULL;
  720.     st_ptr->out_str = NULL;
  721.     return st_ptr;
  722. }  /* end of create() */
  723.  
  724.  
  725. /* BD_MOVE - Build the "failure" and "move" transitions for
  726.  *         each state from the "go" transitions.
  727.  */
  728.  
  729. void bd_move()
  730. {
  731.     register char litchar;
  732.     register FSA *r,        /* temp FSA state pointers */
  733.             *s, *t;
  734.     FSA *go(), *move();
  735.     TRANSITION *current, *insert();
  736.     QUEUE *first,            /* pointer to head of queue */
  737.         *last;                /* pointer to tail of queue */
  738.     void add_queue(), delete_queue();
  739.  
  740.     if (dflag)
  741.         printf("BD_MOVE entry\n");
  742.  
  743.     last = first = NULL;    /* initialize the queue of FSA states */
  744.  
  745.     /* For each input character with a "go" transition out of FSA
  746.      * state 0, add a pointer to the "go" state to the queue.  Note
  747.      * that this will also serve as the "move" transition list for
  748.      * state 0.
  749.      */
  750.  
  751.     for (litchar = 1; litchar <= 127; litchar++)
  752.         if (s = go(NULL, litchar))
  753.             add_queue(&first, &last, s);
  754.  
  755.     /* While there are still state pointers in the queue, do ... */
  756.  
  757.     while (first)
  758.     {
  759.         /* remove state "r" pointer from the head of the queue */
  760.  
  761.         r = first->s_ptr;
  762.         delete_queue(&first);
  763.  
  764.         /* Skip (terminal state with no "go" transitions */
  765.  
  766.         if (!r->go_ls)
  767.             continue;
  768.  
  769.         /* Make "move" transition list for terminal state same as its
  770.          * "go" transition list.
  771.          */
  772.  
  773.         if (r->out_str)
  774.             r->mv_ls = r->go_ls;
  775.  
  776.         /* For every input to state "r" that has a "go" transition to
  777.          * state "s", do ... */
  778.  
  779.         for (litchar = 1; litchar <= 127; litchar++)
  780.         {
  781.             if ((s = go(r, litchar)) != &FAIL_STATE)
  782.             {
  783.                 /* If a defined "go" transition exists for state "r" on
  784.                  * input "litchar", add a pointer to state "s" to the
  785.                  * end of the queue.
  786.                  */
  787.  
  788.                 add_queue(&first, &last, s);
  789.  
  790.                 /* Calculate the "failure" transition of state "s" using
  791.                  * the following algorithm.
  792.                  */
  793.  
  794.                 t = r->fail_state;
  795.                 while (go(t, litchar) == &FAIL_STATE)
  796.                     t = t->fail_state;
  797.                 s->fail_state = go(t, litchar);
  798.             }
  799.             else
  800.             {
  801.                 /* ... otherwise set the pointer to state "s" to a
  802.                  * pointer to the precalculated "move" transition of
  803.                  * state "r"'s failure state on input "litchar".
  804.                  */
  805.  
  806.                 s = move(r->fail_state, litchar);
  807.             }
  808.  
  809.             /* Add state "s" as the "move" transition for state "r" on
  810.              * input "litchar" only if it is not state 0 and "r" is not
  811.              * a terminal state.
  812.              */
  813.  
  814.             if (dflag)
  815.                 printf("BD_MOVE ready to build move(s,a)\n");
  816.  
  817.             if (s && !r->out_str) {
  818.                 if (dflag)
  819.                     printf("BD_MOVE about to insert move(s,a)\n");
  820.  
  821.                 if (!r->mv_ls)        /* 1st instance of the list? */
  822.                     current = r->mv_ls = insert(s, litchar);
  823.                 else
  824.                     current = current->next_el = insert(s, litchar);
  825.             }
  826.  
  827.         }
  828.     }
  829.     if (dflag)
  830.         printf("BD_MOVE exit\n");
  831. } /* end of bd_move() */
  832.  
  833.  
  834.  
  835. /* ADD_QUEUE - Add an instance to the tail of a queue. */
  836.  
  837. void add_queue(head_ptr, tail_ptr, st_ptr)
  838. QUEUE **head_ptr, **tail_ptr;
  839. FSA *st_ptr;
  840. {
  841.     QUEUE *pq;
  842.     char *malloc();
  843.     void error();
  844.  
  845.     /* Allocate the necessary memory and set the variables */
  846.  
  847.     if (dflag)
  848.         printf("ADD_QUEUE h=%x t=%x s=%x\n", head_ptr, tail_ptr, st_ptr);
  849.  
  850.     if (!(pq = (QUEUE *)malloc(sizeof(QUEUE))))
  851.         error(MEM_ERR, NULL);
  852.     pq->s_ptr = st_ptr;
  853.     pq->next_elq = NULL;
  854.  
  855.     if (!*head_ptr)     /* 1st instance of the queue?  */
  856.         *tail_ptr = *head_ptr = pq;
  857.     else                /* no, just another one */
  858.         *tail_ptr = (*tail_ptr)->next_elq = pq;
  859.  
  860. }  /* end of add_queue() */
  861.  
  862.  
  863.  
  864. /* DELETE_QUEUE() - Delete an instance from the head of queue */
  865.  
  866. void delete_queue(head_ptr)
  867. QUEUE **head_ptr;
  868. {
  869.  
  870.     if (dflag)
  871.         printf("del_QUEUE h=%x \n", head_ptr);
  872.  
  873.     *head_ptr = (*head_ptr)->next_elq;
  874. }  /* end of delete_queue() */
  875.  
  876.  
  877. /* STRSAVE() - Save a string somewhere in memory. */
  878.  
  879. char *strsave(str)
  880. char *str;
  881. {
  882.     int strlen();
  883.     char *p, *malloc();
  884.     void error();
  885.  
  886.     if (p = malloc(strlen(str) + 1))
  887.         strcpy(p, str);
  888.     else
  889.         error(MEM_ERR, NULL);
  890.     return p;
  891. }  /* end of strsave() */
  892.  
  893.  
  894.  
  895.  
  896. /* STOUPPER() - Map entire string pointed to by :str: to upper
  897.  *        case.
  898.  */
  899.  
  900. char *stoupper(str)
  901. register char *str;
  902. {
  903.     register char *temp;
  904.  
  905.     temp = str;
  906.     while (*temp)
  907.         *temp++ = toupper(*temp);
  908.     return str;
  909. }  /* end of stoupper() */
  910.  
  911.  
  912.  
  913. /* ERROR() - Error reporting.  Returns an exit status ofo 2 to the
  914.  *         parent process.
  915.  */
  916.  
  917. void error(n, str)
  918. int n;
  919. char *str;
  920. {
  921.     fprintf(stderr, "\007\n*** ERROR - ");
  922.     switch(n)
  923.     {
  924.         case CMD_ERR:
  925.             fprintf(stderr, "Illegal command line");
  926.             break;
  927.         case OPT_ERR:
  928.             fprintf(stderr, "Illegal command line option");
  929.             break;
  930.         case INP_ERR:
  931.             fprintf(stderr, "Can't open input file %s", str);
  932.             break;
  933.         case STR_ERR:
  934.             fprintf(stderr, "Can't open string file %s", str);
  935.             break;
  936.         case MEM_ERR:
  937.             fprintf(stderr, "Out of memory");
  938.             break;
  939.         default:
  940.             break;
  941.     }
  942.     fprintf(stderr, " ***\n\nUsage: fgrep [-vclnhyefxps]");
  943.     fprintf(stderr, " [strings] <files>\n");
  944.     exit(2);
  945. }  /* end of error() */
  946.  
  947. /* end of fgrep.c */
  948.