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