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