home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 2 BBS / 02-BBS.zip / MSGDP206.SZH / BMG.C < prev    next >
C/C++ Source or Header  |  1990-06-17  |  3KB  |  118 lines
  1. /*
  2.  *    bmg.c ->    Boyer-Moore-Gosper search routines
  3.  *
  4.  * Adapted from:
  5.  *     Boyer/Moore/Gosper-assisted 'egrep' search, with delta0 table as in
  6.  *     original paper (CACM, October, 1977).    No delta1 or delta2.  According to
  7.  *     experiment (Horspool, Soft. Prac. Exp., 1982), delta2 is of minimal
  8.  *     practical value.  However, to improve for worst case input, integrating
  9.  *     the improved Galil strategies (Apostolico/Giancarlo, Siam. J. Comput.,
  10.  *     February 1986) deserves consideration.
  11.  *
  12.  *     James A. Woods                 Copyright (c) 1986
  13.  *     NASA Ames Research Center
  14.  *
  15.  * 29 April 1986    Jeff Mogul    Stanford
  16.  *    Adapted as a set of subroutines for use by a program. No
  17.  *    regular-expression support.
  18.  *
  19.  * 29 August 1986    Frank Whaley    Beyond Words
  20.  *    Trimmed for speed and other dirty tricks.
  21.  */
  22.  
  23. #include <ctype.h>
  24. #include <string.h>
  25. #include <stdio.h>
  26. #include "bmg.h"
  27.  
  28. #ifdef __MSC__
  29. #define strcmpl stricmp
  30. #define strncmpi strnicmp
  31. #endif
  32.  
  33.  
  34. #ifdef __TURBOC__
  35. #define strcmpl strcmpi
  36. #endif
  37.  
  38. #if defined (__ZTC__)
  39. int _pascal strncmpi(char *s, char *t, int n);
  40. #endif
  41.  
  42.  
  43.  
  44. /*
  45.  *    bmgCompile() -> compile Boyer-Moore delta table
  46.  *
  47.  *    bmgCompile() compiles the delta table for the given search string, and
  48.  *     initializes the search argument structure.  This structure must be
  49.  *     passed to the bmgSearch() function described below.
  50.  */
  51.  
  52.  
  53. void _pascal bmgCompile(char *pat, bmgARG *arg, int ignore)
  54.  
  55.     {
  56.     int i,        /*    general ctr     */
  57.         patlen;     /*    pattern length    */
  58.  
  59.     patlen = strlen(pat);
  60.  
  61.     strcpy(arg->pat, pat);
  62.     if ((arg->ignore = (char) ignore) != 0)
  63.         strlwr(arg->pat);
  64.  
  65.     memset(arg->delta, patlen, 256);
  66.  
  67.     for (i = 0; i < patlen; ++i)
  68.         arg->delta[pat[i]] = (char) (patlen - i - 1);
  69.  
  70.     if (ignore) /*    tweak upper case if ignore on  */
  71.         for (i = 0; i < patlen; ++i)
  72.             arg->delta[toupper(pat[i])] = (char) (patlen - i - 1);
  73.     }
  74.  
  75.  
  76. /*
  77.  *    bmgSearch() ->    scan for match
  78.  *
  79.  *    bmgSearch() performs a Boyer-Moore-Gosper search of the given buffer
  80.  *     for the string described by the given search argument structure.  The
  81.  *     match action function "action" will be called for each match found.
  82.  *     This function should return non-zero to continue searching, or 0 to
  83.  *     terminate the search.    bmgSearch() returns the total number of
  84.  *     matches found.
  85.  */
  86.  
  87. char *pascal bmgSearch(char * buffer, int buflen, bmgARG *arg)
  88.  
  89.     {
  90.     char    *s;     /*    temp ptr for comparisons    */
  91.     int inc,        /*    position increment        */
  92.         k,        /*    current buffer index    */
  93.         patlen;     /*    pattern length        */
  94.  
  95.     k = (patlen = strlen(arg->pat)) - 1;
  96.  
  97.     for (;;)
  98.         {
  99.         while (((inc = arg->delta[buffer[k]]) != 0) &&
  100.             ((k += inc) < buflen))
  101.             ;
  102.         if (k >= buflen)
  103.             break;
  104.  
  105.         s = buffer + (k++ - (patlen - 1));
  106.         if (!(arg->ignore ? strncmpi(s, arg->pat, patlen) : strncmp(s, arg->pat, patlen)))
  107.             return (s);
  108.         }
  109.  
  110.     return (NULL);
  111.     }
  112.  
  113.  
  114. /*
  115.  *    END of bmg.c
  116.  */
  117.  
  118.