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