sflfind.c

短小精悍的C语言标准函数库。提供450个以上的可移植的算法和工具代码。

        secondtime  = FALSE;

    ASSERT (block);                     /*  Expect non-NULL pointers, but    */
    ASSERT (pattern);                   /*  full through if not debugging    */

    return memfind_rb (block, block_size, pattern, pattern_size,
                       searchbuf, &secondtime);
}


/*  ---------------------------------------------------------------------[<]-
    Function: memfind_rb

    Synopsis: Searches for a pattern in a block of memory using the Boyer-
    Moore-Horspool-Sunday algorithm.  The block and pattern may contain any
    values; you must explicitly provide their lengths.  Returns a pointer to
    the pattern if found within the block, or NULL if the pattern was not
    found.  On the first search with a given pattern, *repeat_find should
    be FALSE.  It will be set to TRUE after the shift table is initialised,
    allowing the initialisation phase to be skipped on subsequent searches.
    shift must point to an array big enough to hold 256 (8**2) size_t values.

    This function is meant to handle binary data, for repeated searches
    for the same pattern.  If you need to search strings, use the
    strfind_r() or strfind_rb() functions.  If you wish to search for a
    pattern only once consider using memfind_r(). Reentrant.
    ---------------------------------------------------------------------[>]-*/

void *
memfind_rb (const void  *in_block,      /*  Block containing data            */
            size_t       block_size,    /*  Size of block in bytes           */
            const void  *in_pattern,    /*  Pattern to search for            */
            size_t       pattern_size,  /*  Size of pattern block            */
            size_t      *shift,         /*  Shift table (search buffer)      */
            Bool        *repeat_find)   /*  TRUE: search buffer already init */
{
    size_t
        byte_nbr,                       /*  Distance through block           */
        match_size;                     /*  Size of matched part             */
    const byte
        *match_base = NULL,             /*  Base of match of pattern         */
        *match_ptr  = NULL,             /*  Point within current match       */
        *limit      = NULL;             /*  Last potiental match point       */
    const byte
        *block   = (byte *) in_block,   /*  Concrete pointer to block data   */
        *pattern = (byte *) in_pattern; /*  Concrete pointer to search value */

    ASSERT (block);                     /*  Expect non-NULL pointers, but    */
    ASSERT (pattern);                   /*  fail gracefully if not debugging */
    ASSERT (shift);                     /*  NULL repeat_find => is false     */
    if (block == NULL || pattern == NULL || shift == NULL)
        return (NULL);

    /*  Pattern must be smaller or equal in size to string                   */
    if (block_size < pattern_size)
        return (NULL);                  /*  Otherwise it's not found         */

    if (pattern_size == 0)              /*  Empty patterns match at start    */
        return ((void *)block);

    /*  Build the shift table unless we're continuing a previous search      */

    /*  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.    */

    if (!repeat_find || !*repeat_find)
      {
        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) pattern [byte_nbr]] = pattern_size - byte_nbr;

        if (repeat_find)
            *repeat_find = TRUE;
      }

    /*  Search for the block, each time jumping up by the amount             */
    /*  computed in the shift table                                          */

    limit = block + (block_size - pattern_size + 1);
    ASSERT (limit > block);

    for (match_base = block;
         match_base < limit;
         match_base += shift [*(match_base + pattern_size)])
      {
        match_ptr  = match_base;
        match_size = 0;

        /*  Compare pattern until it all matches, or we find a difference    */
        while (*match_ptr++ == pattern [match_size++])
          {
            ASSERT (match_size <= pattern_size && 
                    match_ptr == (match_base + match_size));

            /*  If we found a match, return the start address                */
            if (match_size >= pattern_size)
              return ((void*)(match_base));

          }
      }
    return (NULL);                      /*  Found nothing                    */
}


/*  ---------------------------------------------------------------------[<]-
    Function: txtfind

    Synopsis: 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 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.

    Examples:
    char *result;

    result = txtfind ("AbracaDabra", "cad");
    if (result)
        puts (result);
    ---------------------------------------------------------------------[>]-*/

char *
txtfind (const char *string,            /*  String containing data           */
         const char *pattern)           /*  Pattern to search for            */
{
    size_t
        shift [256];                    /*  Shift distance for each value    */
    size_t
        string_size,
        pattern_size,
        byte_nbr,                       /*  Index into byte array            */
        match_size;                     /*  Size of matched part             */
    const char
        *match_base = NULL,             /*  Base of match of pattern         */
        *match_ptr  = NULL,             /*  Point within current match       */
        *limit      = NULL;             /*  Last potiental match point       */

    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 + (string_size - pattern_size + 1);
    ASSERT (limit > string);

    for (match_base = string;
         match_base < limit;
         match_base += shift [(byte) tolower (*(match_base + pattern_size))])
      {
        match_ptr  = match_base;
        match_size = 0;

        /*  Compare pattern until it all matches, or we find a difference    */
        while (tolower (*match_ptr++) == tolower (pattern [match_size++]))
          {
            ASSERT (match_size <= pattern_size && 
                    match_ptr == (match_base + match_size));

            /*  If we found a match, return the start address                */
            if (match_size >= pattern_size)
                return ((char *)(match_base));
          }
      }
    return (NULL);                      /*  Found nothing                    */
}