1.\" $NetBSD: bm.3,v 1.7 2003/08/07 16:43:47 agc 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 55These routines implement an efficient mechanism to find an 56occurrence of a byte string within another byte string. 57.Pp 58.Fn bm_comp 59evaluates the 60.Fa patlen 61bytes starting at 62.Fa pattern , 63and returns a pointer to a structure describing them. 64The bytes referenced by 65.Fa pattern 66may be of any value. 67.Pp 68The search takes advantage of the frequency distribution of the 69bytes in the text to be searched. 70If specified, 71.Fa freq 72should be an array of 256 values, 73with higher values indicating that the corresponding character occurs 74more frequently. 75(A less than optimal frequency distribution can only result in less 76than optimal performance, not incorrect results.) 77If 78.Fa freq 79is NULL, 80a system default table is used. 81.Pp 82.Fn bm_exec 83returns a pointer to the leftmost occurrence of the string given to 84.Fn bm_comp 85within 86.Fa text , 87or NULL if none occurs. 88The number of bytes in 89.Fa text 90must be specified by 91.Fa len . 92.Pp 93Space allocated for the returned description is discarded 94by calling 95.Fn bm_free 96with the returned description as an argument. 97.Pp 98The asymptotic speed of 99.Fn bm_exec 100is O(len/patlen). 101.Sh SEE ALSO 102.Xr regexp 3 , 103.Xr strstr 3 104.Rs 105.%A Hume and Sunday 106.%D November 1991 107.%J "Software Practice and Experience" 108.%P pp. 1221-48 109.%T "Fast String Searching" 110.%V Vol. 21, 11 111.Re 112