| iMatix home page | << | < | > | >> |
![]() Version 1.91 |
#include "sflfind.h" char * txtfind (const char *string, /* String containing data */ const char *pattern) /* Pattern to search for */
Searches for a case-insensitive text pattern in a string using the Boyer-Moore-Horspool-Sunday algorithm. The string and pattern are null-terminated strings. Returns a pointer to the first occurance of the pattern if found within the string, or NULL if the pattern was not found. Will match strings irrespective of case. To match exact strings, use strfind(). Will not work on multibyte characters. Reentrant.
char *result; result = txtfind ("AbracaDabra", "cad"); if (result) puts (result);
{ int shift [256]; /* Shift distance for each value */ size_t string_size, pattern_size, byte_nbr, /* Distance through block */ match_size, /* Size of matched part */ limit; /* Last potiental match point */ const char *match_ptr = NULL; ASSERT (string); /* Expect non-NULL pointers, but */ ASSERT (pattern); /* fail gracefully if not debugging */ if (string == NULL || pattern == NULL) return (NULL); string_size = strlen (string); pattern_size = strlen (pattern); /* Pattern must be smaller or equal in size to string */ if (string_size < pattern_size) return (NULL); /* Otherwise it cannot be found */ if (pattern_size == 0) /* Empty string matches at start */ return (char *)string; /* Build the shift table */ /* The shift table determines how far to shift before trying to match */ /* again, if a match at this point fails. If the byte after where the */ /* end of our pattern falls is not in our pattern, then we start to */ /* match again after that byte; otherwise we line up the last occurence */ /* of that byte in our pattern under that byte, and try match again. */ for (byte_nbr = 0; byte_nbr < 256; byte_nbr++) shift [byte_nbr] = pattern_size + 1; for (byte_nbr = 0; byte_nbr < pattern_size; byte_nbr++) shift [(byte) tolower (pattern [byte_nbr])] = pattern_size - byte_nbr; /* Search for the string. If we don't find a match, move up by the */ /* amount we computed in the shift table above, to find location of */ /* the next potiental match. */ limit = string_size - pattern_size + 1; ASSERT (limit > 0); for (byte_nbr = 0; byte_nbr < limit; byte_nbr += shift [(byte) tolower (string [byte_nbr + pattern_size])]) { ASSERT (byte_nbr >= 0 && byte_nbr < (string_size - pattern_size) + 1); /* If the first byte matches, compare rest of pattern */ if (tolower (string [byte_nbr]) == tolower (*pattern)) { match_ptr = string + byte_nbr + 1; match_size = 1; do { /* Loop invarients */ ASSERT (match_size > 0 && match_size <= pattern_size); ASSERT (match_ptr != NULL && match_ptr > string && match_ptr <= string+string_size); ASSERT (match_ptr == (string + byte_nbr + match_size)); /* If all matched, return pointer to start of match */ if (match_size == pattern_size) return ((char *) string + byte_nbr); ASSERT (match_size < pattern_size && match_ptr < string+string_size); } while (tolower (*match_ptr++) == tolower (pattern [match_size++])); } ASSERT (byte_nbr + pattern_size <= string_size); } return (NULL); /* Found nothing */ }
| << | < | > | >> |
![]() |