NAME    [Toc]    [Back]

     bm_comp, bm_exec, bm_free - Boyer-Moore string search

SYNOPSIS    [Toc]    [Back]

     #include <sys/types.h>
     #include <bm.h>

     bm_pat *
     bm_comp(u_char *pattern, size_t patlen, u_char freq[256]);

     u_char *
     bm_exec(bm_pat *pdesc, u_char *text, size_t len);

     void
     bm_free(bm_pat *pdesc);

DESCRIPTION    [Toc]    [Back]

     These routines implement an efficient mechanism to  find  an
occurrence of
     a byte string within another byte string.

     bm_comp() evaluates patlen bytes starting at pattern and returns a pointer
 to a structure describing them.  The bytes referenced  by
pattern may
     be of any value.

     The  search takes advantage of the frequency distribution of
the bytes in
     the text to be searched.  If specified, freq  should  be  an
array of 256
     values, with higher values indicating that the corresponding
character
     occurs more frequently.  (A less than optimal frequency distribution can
     only  result in less than optimal performance, not incorrect
results.)  If
     freq is NULL, a system default table is used.

     bm_exec() returns a pointer to the  leftmost  occurrence  of
the string given
  to  bm_comp()  within text, or NULL if none occurs.  The
number of bytes
     in text must be specified by len.

     Space allocated for the returned description is discarded by
calling
     bm_free() with the returned description as an argument.

     The asymptotic speed of bm_exec() is O(len / patlen).

SEE ALSO    [Toc]    [Back]

     regexp(3), strstr(3)

     Andrew   Hume  and  Daniel  Sunday,  Software  Practice  and
Experience, Fast
     String Searching, Volume 21, 11 (November 1991), 1221-48.

OpenBSD     3.6                           June      29,      1999