cde/lib/DtSearch/bmstrstr.c

   1 /*
   2  *   COMPONENT_NAME: austext
   3  *
   4  *   FUNCTIONS: bmhcore
   5  *              bmhtable_build
   6  *              bmstrstr
   7  *              main
   8  *
   9  *   ORIGINS: 27
  10  *
  11  *
  12  *   (C) COPYRIGHT International Business Machines Corp. 1992,1995
  13  *   All Rights Reserved
  14  *   Licensed Materials - Property of IBM
  15  *   US Government Users Restricted Rights - Use, duplication or
  16  *   disclosure restricted by GSA ADP Schedule Contract with IBM Corp.
  17  */
  18 /************************* BMSTRSTR.C ****************************
  19  * $TOG: bmstrstr.c /main/6 1998/04/17 11:25:23 mgreess $
  20  * Original module named fastsearch.c
  21  * and included colocation string search functions.
  22  * Modification of Boyer-Moore-Horspool algorithm,
  23  * Sec 10.5.2 of Information Retrieval, Frakes and Baeza-Yates, editors.
  24  * Provides a generalized boyer-moore
  25  * strstr() function.  The table used in the BMH algorithm is
  26  * generated in a separate function to improve efficiency when
  27  * looking for the same substring pattern in multiple text strings.
  28  * The 'length' arguments can be passed if known, or passed as
  29  * strlen(xxx) if not known.  HOWEVER the string arrays MUST be at
  30  * least 1 char larger then strlen() says ('cause we insert a \0).
  31  * This whole thing has been coded for SPEED!
  32  *
  33  * $Log$
  34  * Revision 2.2  1995/10/26  15:37:42  miker
  35  * Added prolog.
  36  *
  37  * Revision 2.1  1995/09/22  19:10:39  miker
  38  * Freeze DtSearch 0.1, AusText 2.1.8
  39  *
  40  * Revision 1.2  1995/08/31  22:12:05  miker
  41  * Minor changes for DtSearch.
  42  */
  43 #include "SearchP.h"
  44 #include <stdio.h>
  45 #include <string.h>
  46 #include <sys/param.h>
  47
  48 #ifndef _AIX
  49 #define __strcmp        strcmp
  50 #endif
  51
  52 /*********#define TEST_BMSTRSTR**************/
  53
  54 /****************************************/
  55 /*                                      */
  56 /*            bmhtable_build            */
  57 /*                                      */
  58 /****************************************/
  59 /* Builds the table for search substring 'pattern'
  60  * used by the BMH core search algorithm.
  61  * 'patlen' is the string length of 'pattern'.
  62  * The caller defines and passes 'bmhtable',
  63  * an array of long integers (size_t) of size MAX_BMHTAB.
  64  * This function initializes bmhtable for later search call.
  65  */
  66 void            bmhtable_build (
  67                     unsigned char *pattern,
  68                     size_t patlen,
  69                     size_t * bmhtable)
  70 {
  71     int             k;
  72
  73     for (k = 0; k < MAX_BMHTAB; k++)
  74         bmhtable[k] = patlen;
  75     patlen--;
  76     for (k = 0; k < patlen; k++)
  77         bmhtable[pattern[k]] = (patlen - k);
  78     return;
  79 }  /* bmhtable_build() */
  80
  81
  82 /****************************************/
  83 /*                                      */
  84 /*               bmhcore                */
  85 /*                                      */
  86 /****************************************/
  87 /* Performs 'core' BMH search after bmhtable is built.
  88  * Returns ptr to first occurrence of pattern in text or NULL.
  89  * WARNING! IF EITHER txtlen OR patlen <= 0, THIS FUNCTION WILL CRASH!!!
  90  * Pattern and patlen MUST BE identical with those used to build
  91  * bmhtable.
  92  */
  93
  94 char           *bmhcore (
  95                     unsigned char       *text,
  96                     size_t              txtlen,
  97                     unsigned char       *pattern,
  98                     size_t              patlen,
  99                     size_t              *bmhtable)
 100 {
 101     register unsigned char
 102                 lastchar = pattern[patlen - 1];
 103     register unsigned char
 104                 textchar;
 105     register unsigned char
 106                 *cp;
 107     register unsigned char
 108                 *last;
 109     int         savechar;
 110     int         savechar2;
 111     unsigned char
 112                 *result = NULL;
 113
 114     /* Terminate pattern with a char we KNOW is not in text.
 115      * Note that this requires string to have room for \0 at end.
 116      */
 117     savechar = pattern[patlen];
 118     pattern[patlen] = '\0';
 119
 120     last = text + txtlen;
 121     for (cp = text + patlen - 1; cp < last; cp += bmhtable[textchar]) {
 122         /*
 123          * Check if last character matches. If it doesn't, no need
 124          * to check any further.
 125          */
 126         if ((textchar = *cp) != lastchar)
 127             continue;
 128         savechar2 = cp[1];
 129         cp[1] = '\0';
 130         if (!__strcmp ((char *) (cp + 1 - patlen), (char *) pattern))
 131             result = cp + 1 - patlen;
 132         cp[1] = savechar2;
 133         if (result)
 134             break;
 135     }
 136     pattern[patlen] = savechar; /* restore last char */
 137     return (char *) result;
 138 }  /* bmhcore() */
 139
 140
 141 /****************************************/
 142 /*                                      */
 143 /*               bmstrstr               */
 144 /*                                      */
 145 /****************************************/
 146 /* Search in text [1..txtlen] for pattern [1..patlen].
 147  * Returns ptr to first occurrence of pattern, or NULL.
 148  */
 149 char           *bmstrstr (
 150                     unsigned char *text,
 151                     size_t txtlen,
 152                     unsigned char *pattern,
 153                     size_t patlen)
 154 {
 155     size_t          bmhtable[MAX_BMHTAB];
 156
 157     bmhtable_build (pattern, patlen, bmhtable);
 158     return bmhcore (text, txtlen, pattern, patlen, bmhtable);
 159 }  /* bmstrstr() */
 160
 161
 162 #ifdef TEST_BMSTRSTR    /* for test only */
 163 #include <sys/stat.h>
 164 /****************************************/
 165 /*                                      */
 166 /*                 main                 */
 167 /*                                      */
 168 /****************************************/
 169 /* tests bmstrstr() against standard strstr() on a specified file */
 170 main ()
 171 {
 172     FILE           *f;
 173     struct stat     statbuf;
 174     size_t          fsize = 0L;
 175     char            fname[BUFSIZ+1];
 176     char            pattern[MAXPATHLEN+1];
 177     char           *readbuf = NULL;
 178     char           *ptr;
 179
 180 MAIN_LOOP:
 181     printf ("\nEnter a filename (Ctrl-C quits) > ");
 182
 183     *fname = '\0';
 184     fgets (fname, sizeof(fname), stdin);
 185     if (strlen(fname) && fname[strlen(fname)-1] == '\n')
 186       fname[strlen(fname)-1] = '\0';
 187
 188     if ((f = fopen (fname, "r")) == NULL) {
 189         printf ("Can't open '%s': %s\n", fname, strerror (errno));
 190         goto MAIN_LOOP;
 191     }
 192
 193     fstat (fileno (f), &statbuf);
 194     if (fsize > statbuf.st_size) {
 195         free (readbuf);
 196         readbuf = NULL;
 197     }
 198     fsize = statbuf.st_size;
 199     if (readbuf == NULL)
 200         readbuf = malloc (fsize + 64L);
 201
 202     fread (readbuf, fsize, 1L, f);
 203     fclose (f);
 204
 205     printf ("Enter a search pattern > ");
 206
 207     *pattern = '\0';
 208     fgets (pattern, sizeof(pattern), stdin);
 209     if (strlen(pattern) && pattern[strlen(pattern)-1] == '\n')
 210       pattern[strlen(pattern)-1] = '\0';
 211
 212     ptr = bmstrstr (readbuf, fsize, pattern, strlen (pattern));
 213     if (ptr == NULL)
 214         puts ("bmstrstr: Pattern not found.");
 215     else
 216         printf ("bmstrstr: Pattern found at offset %ld.\n", ptr - readbuf);
 217
 218     ptr = strstr (readbuf, pattern);
 219     if (ptr == NULL)
 220         puts ("strstr:   Pattern not found.");
 221     else
 222         printf ("strstr:   Pattern found at offset %ld.\n", ptr - readbuf);
 223
 224     goto MAIN_LOOP;
 225 }  /* main() test program */
 226
 227 #endif
 228
 229 /************************* BMSTRSTR.C ****************************/