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