1.\" $NetBSD: bm.3,v 1.9 2016/01/23 00:43:42 dholland 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 "unsigned char *pattern" "size_t patlen" "unsigned char freq[256]" 50.Ft unsigned char * 51.Fn bm_exec "bm_pat *pdesc" "unsigned 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 80.Dv NULL , 81a system default table is used. 82.Pp 83.Fn bm_exec 84returns a pointer to the leftmost occurrence of the string given to 85.Fn bm_comp 86within 87.Fa text , 88or 89.Dv NULL 90if none occurs. 91The number of bytes in 92.Fa text 93must be specified by 94.Fa len . 95.Pp 96Space allocated for the returned description is discarded 97by calling 98.Fn bm_free 99with the returned description as an argument. 100.Pp 101The asymptotic speed of 102.Fn bm_exec 103is 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 115