lib/libc/string/bm.3

   1 .\" $NetBSD: bm.3,v 1.8 2006/10/16 08:48:45 wiz Exp $
   2 .\"
   3 .\" Copyright (c) 1994
   4 .\"     The Regents of the University of California.  All rights reserved.
   5 .\"
   6 .\" This code is derived from software contributed to Berkeley by
   7 .\" Andrew Hume of AT&T Bell Laboratories.
   8 .\"
   9 .\" Redistribution and use in source and binary forms, with or without
  10 .\" modification, are permitted provided that the following conditions
  11 .\" are met:
  12 .\" 1. Redistributions of source code must retain the above copyright
  13 .\"    notice, this list of conditions and the following disclaimer.
  14 .\" 2. Redistributions in binary form must reproduce the above copyright
  15 .\"    notice, this list of conditions and the following disclaimer in the
  16 .\"    documentation and/or other materials provided with the distribution.
  17 .\" 3. Neither the name of the University nor the names of its contributors
  18 .\"    may be used to endorse or promote products derived from this software
  19 .\"    without specific prior written permission.
  20 .\"
  21 .\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  22 .\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  23 .\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  24 .\" ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  25 .\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  26 .\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  27 .\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28 .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29 .\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  30 .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  31 .\" SUCH DAMAGE.
  32 .\"
  33 .\"     from: @(#)bm.3  8.4 (Berkeley) 6/21/94
  34 .\"
  35 .Dd April 8, 2001
  36 .Dt BM 3
  37 .Os
  38 .Sh NAME
  39 .Nm bm_comp ,
  40 .Nm bm_exec ,
  41 .Nm bm_free
  42 .Nd Boyer-Moore string search
  43 .Sh LIBRARY
  44 .Lb libc
  45 .Sh SYNOPSIS
  46 .In sys/types.h
  47 .In bm.h
  48 .Ft bm_pat *
  49 .Fn bm_comp "u_char *pattern" "size_t patlen" "u_char freq[256]"
  50 .Ft u_char *
  51 .Fn bm_exec "bm_pat *pdesc" "u_char *text" "size_t len"
  52 .Ft void
  53 .Fn bm_free "bm_pat *pdesc"
  54 .Sh DESCRIPTION
  55 These routines implement an efficient mechanism to find an
  56 occurrence of a byte string within another byte string.
  57 .Pp
  58 .Fn bm_comp
  59 evaluates the
  60 .Fa patlen
  61 bytes starting at
  62 .Fa pattern ,
  63 and returns a pointer to a structure describing them.
  64 The bytes referenced by
  65 .Fa pattern
  66 may be of any value.
  67 .Pp
  68 The search takes advantage of the frequency distribution of the
  69 bytes in the text to be searched.
  70 If specified,
  71 .Fa freq
  72 should be an array of 256 values,
  73 with higher values indicating that the corresponding character occurs
  74 more frequently.
  75 (A less than optimal frequency distribution can only result in less
  76 than optimal performance, not incorrect results.)
  77 If
  78 .Fa freq
  79 is
  80 .Dv NULL ,
  81 a system default table is used.
  82 .Pp
  83 .Fn bm_exec
  84 returns a pointer to the leftmost occurrence of the string given to
  85 .Fn bm_comp
  86 within
  87 .Fa text ,
  88 or
  89 .Dv NULL
  90 if none occurs.
  91 The number of bytes in
  92 .Fa text
  93 must be specified by
  94 .Fa len .
  95 .Pp
  96 Space allocated for the returned description is discarded
  97 by calling
  98 .Fn bm_free
  99 with the returned description as an argument.
 100 .Pp
 101 The asymptotic speed of
 102 .Fn bm_exec
 103 is O(len/patlen).
 104 .Sh SEE ALSO
 105 .Xr regexp 3 ,
 106 .Xr strstr 3
 107 .Rs
 108 .%A Hume and Sunday
 109 .%D November 1991
 110 .%J "Software Practice and Experience"
 111 .%P pp. 1221-48
 112 .%T "Fast String Searching"
 113 .%V Vol. 21, 11
 114 .Re