home *** CD-ROM | disk | FTP | other *** search
/ Point Programming 1 / PPROG1.ISO / c / snippets / bmhisrch.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-04-03  |  3.1 KB  |  95 lines
  1. /*
  2. **  Case-Insensitive Boyer-Moore-Horspool pattern match
  3. **
  4. **  Public Domain version by Thad Smith 7/21/1992,
  5. **  based on a 7/92 public domain BMH version by Raymond Gardner.
  6. **
  7. **  This program is written in ANSI C and inherits the compilers
  8. **  ability (or lack thereof) to support non-"C" locales by use of
  9. **  toupper() and tolower() to perform case conversions.
  10. **  Limitation: pattern length + string length must be less than 32767.
  11. **
  12. **  10/21/93 rdg  Fixed bugs found by Jeff Dunlop
  13. */
  14.  
  15. #include <limits.h>
  16. #include <stdlib.h>
  17. #include <string.h>
  18. #include <ctype.h>
  19.  
  20. typedef unsigned char uchar;
  21.  
  22. #define LARGE 32767             /* flag for last character match    */
  23.  
  24. static int patlen;              /* # chars in pattern               */
  25. static int skip[UCHAR_MAX+1];   /* skip-ahead count for test chars  */
  26. static int skip2;               /* skip-ahead after non-match with
  27.                                 ** matching final character         */
  28. static uchar *pat = NULL;       /* uppercase copy of pattern        */
  29.  
  30. /*
  31. ** bmhi_init() is called prior to bmhi_search() to calculate the
  32. ** skip array for the given pattern.
  33. ** Error: exit(1) is called if no memory is available.
  34. */
  35.  
  36. void bmhi_init(const char *pattern)
  37. {
  38.       int i, lastpatchar;
  39.       patlen = strlen(pattern);
  40.  
  41.       /* Make uppercase copy of pattern */
  42.  
  43.       pat = realloc ((void*)pat, patlen);
  44.       if (!pat)
  45.             exit(1);
  46.       for (i=0; i < patlen; i++)
  47.             pat[i] = toupper(pattern[i]);
  48.  
  49.       /* initialize skip array */
  50.  
  51.       for ( i = 0; i <= UCHAR_MAX; ++i )                    /* rdg 10/93 */
  52.             skip[i] = patlen;
  53.       for ( i = 0; i < patlen - 1; ++i )
  54.       {
  55.             skip[        pat[i] ] = patlen - i - 1;
  56.             skip[tolower(pat[i])] = patlen - i - 1;
  57.       }
  58.       lastpatchar = pat[patlen - 1];
  59.       skip[        lastpatchar ] = LARGE;
  60.       skip[tolower(lastpatchar)] = LARGE;
  61.       skip2 = patlen;                     /* Horspool's fixed second shift */
  62.       for (i = 0; i < patlen - 1; ++i)
  63.       {
  64.             if ( pat[i] == lastpatchar )
  65.                   skip2 = patlen - i - 1;
  66.       }
  67. }
  68.  
  69. char *bmhi_search(const char *string, const int stringlen)
  70. {
  71.       int i, j;
  72.       char *s;
  73.  
  74.       i = patlen - 1 - stringlen;
  75.       if (i >= 0)
  76.             return NULL;
  77.       string += stringlen;
  78.       for ( ;; )
  79.       {
  80.             while ( (i += skip[((uchar *)string)[i]]) < 0 )
  81.                   ;                           /* mighty fast inner loop */
  82.             if (i < (LARGE - stringlen))
  83.                   return NULL;
  84.             i -= LARGE;
  85.             j = patlen - 1;
  86.             s = (char *)string + (i - j);
  87.             while ( --j >= 0 && toupper(s[j]) == pat[j] )
  88.                   ;
  89.             if ( j < 0 )                                    /* rdg 10/93 */
  90.                   return s;                                 /* rdg 10/93 */
  91.             if ( (i += skip2) >= 0 )                        /* rdg 10/93 */
  92.                   return NULL;                              /* rdg 10/93 */
  93.       }
  94. }
  95.