sflfind.c

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

/*  ----------------------------------------------------------------<Prolog>-
    Name:       sflfind.c
    Title:      Fast string searching functions
    Package:    Standard Function Library (SFL)

    Written:    1996/04/24  iMatix SFL project team <[e-mail]>
    Revised:    1998/05/04

    Copyright:  Copyright (c) 1996-2000 iMatix Corporation
    License:    This is free software; you can redistribute it and/or modify
                it under the terms of the SFL License Agreement as provided
                in the file LICENSE.TXT.  This software is distributed in
                the hope that it will be useful, but without any warranty.
 ------------------------------------------------------------------</Prolog>-*/

#include "prelude.h"                    /*  Universal header file            */
#include "sflfind.h"                    /*  Prototypes for functions         */


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

    Synopsis: Searches for a 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.  If you repeatedly scan for the
    same pattern, use the repeat_find argument.  If this is TRUE, the
    function does not re-parse the pattern.  You must of course call the
    function with repeat_find equal to FALSE the first time.  This function
    is meant to handle  character data, and is most effective when you work
    with large strings.  To search binary data use memfind().  Will not work
    on multibyte characters.

    Examples:
    char *result;

    result = strfind ("abracadabra", "cad", FALSE);
    if (result)
        puts (result);
    ---------------------------------------------------------------------[>]-*/

char *
strfind (const char *string,            /*  String containing data           */
         const char *pattern,           /*  Pattern to search for            */
         Bool repeat_find)              /*  Same pattern as last time        */
{
    static size_t
        searchbuf [256];                /*  Fixed search buffer              */

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

    return (char *) memfind_rb (string,    strlen (string),
                                pattern,   strlen (pattern),
                                searchbuf, &repeat_find);
}


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

    Synopsis: Searches for a 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.  This function is meant to handle
    character data, and is most effective when you work with large strings.
    To search binary data use memfind().  Will not work on multibyte
    characters.  Reentrant.

    Examples:
    char *result;

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

char *
strfind_r (const char *string,          /*  String containing data           */
           const char *pattern)         /*  Pattern to search for            */
{
    size_t
        searchbuf [256];                /*  One-time search buffer           */
    Bool
        secondtime = FALSE;             /*  Search buffer init needed        */

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

    return (char *) memfind_rb (string,    strlen (string),
                                pattern,   strlen (pattern),
                                searchbuf, &secondtime);
}


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

    Synopsis: Searches for a 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.  Supports more efficient repeat
    searches (for the same pattern), through a supplied search buffer.  The
    search buffer must be long enough to contain 256 (2**8) size_t entries.
    On the first call repeat_find must be set to FALSE.  After the search
    buffer has been initialised, repeat_find will be set to TRUE by the
    function, avoiding the search buffer initialisation on later calls.

    This function is most effective when repeated searches are made for
    the same pattern in one or more strings.  This function is meant to
    handle  character data, and is most effective when you work with
    large strings.  To search binary data use memfind().  Will not work
    on multibyte characters.  Reentrant.

    Examples:
    char   *result;
    Bool   repeat_search = FALSE;
    size_t searchbuf[256];

    result = strfind_rb ("abracadabra", "cad", searchbuf, &repeat_search);
    if (result)
      {
        puts (result);
        result = strfind_rb ("cad/cam", "cad", searchbuf, &repeat_search);
        if (result)
            puts (result);
      }
    ---------------------------------------------------------------------[>]-*/

char *
strfind_rb (const char *string,         /*  String containing data           */
            const char *pattern,        /*  Pattern to search for            */
            size_t     *shift,          /*  Working buffer between searches  */
            Bool       *repeat_find)    /*  Flag for first/later search      */
{
    ASSERT (string);                    /*  Expect non-NULL pointers, but    */
    ASSERT (pattern);                   /*  fall through if not debugging    */
    ASSERT (shift);
    ASSERT (repeat_find);

    return (char *) memfind_rb (string,    strlen (string),
                                pattern,   strlen (pattern),
                                shift,     repeat_find);
}


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

    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.  If you repeatedly scan for the same pattern, use the repeat_find
    argument.  If this is TRUE, the function does not re-parse the pattern.
    This function is meant to handle binary data.  If you need to search
    strings, use the strfind_r or strfind_rb() functions.  Non-Reentrant.
    ---------------------------------------------------------------------[>]-*/

void *
memfind (const void  *block,            /*  Block containing data            */
         size_t       block_size,       /*  Size of block in bytes           */
         const void  *pattern,          /*  Pattern to search for            */
         size_t       pattern_size,     /*  Size of pattern block            */
         Bool         repeat_find)      /*  Same pattern as last time        */
{
    static size_t
        searchbuf [256];                /*  Static shared search buffer      */

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

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

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

    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.

    This function is meant to handle binary data, for a single search for
    a given pattern.  If you need to search strings, use the strfind_r()
    or strfind_rb() functions.  If you want to do efficient repeated searches
    for one pattern, use memfind_rb().  Reentrant.
    ---------------------------------------------------------------------[>]-*/

void *
memfind_r (const void  *block,          /*  Block containing data            */
           size_t       block_size,     /*  Size of block in bytes           */
           const void  *pattern,        /*  Pattern to search for            */
           size_t       pattern_size)   /*  Size of pattern block            */
{
    size_t
        searchbuf [256];                /*  One-time search buffer           */
    Bool