summaryrefslogtreecommitdiff
path: root/src/lib/libc/string/bm.3
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/libc/string/bm.3')
-rw-r--r--src/lib/libc/string/bm.3116
1 files changed, 57 insertions, 59 deletions
diff --git a/src/lib/libc/string/bm.3 b/src/lib/libc/string/bm.3
index 2264a6a1c4..749ffc9b74 100644
--- a/src/lib/libc/string/bm.3
+++ b/src/lib/libc/string/bm.3
@@ -12,11 +12,7 @@
12.\" 2. Redistributions in binary form must reproduce the above copyright 12.\" 2. Redistributions in binary form must reproduce the above copyright
13.\" notice, this list of conditions and the following disclaimer in the 13.\" notice, this list of conditions and the following disclaimer in the
14.\" documentation and/or other materials provided with the distribution. 14.\" documentation and/or other materials provided with the distribution.
15.\" 3. All advertising materials mentioning features or use of this software 15.\" 3. Neither the name of the University nor the names of its contributors
16.\" must display the following acknowledgement:
17.\" This product includes software developed by the University of
18.\" California, Berkeley and its contributors.
19.\" 4. Neither the name of the University nor the names of its contributors
20.\" may be used to endorse or promote products derived from this software 16.\" may be used to endorse or promote products derived from this software
21.\" without specific prior written permission. 17.\" without specific prior written permission.
22.\" 18.\"
@@ -32,83 +28,85 @@
32.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 28.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
33.\" SUCH DAMAGE. 29.\" SUCH DAMAGE.
34.\" 30.\"
35.\" from: @(#)bm.3 8.4 (Berkeley) 6/21/94 31.\" $OpenBSD: bm.3,v 1.9 2007/05/31 19:19:32 jmc Exp $
36.\" $Id: bm.3,v 1.1.1.1 1995/10/18 08:42:20 deraadt Exp $
37.\" 32.\"
38.TH BM 3 33.Dd $Mdocdate: May 31 2007 $
39.SH NAME 34.Dt BM 3
40bm_comp, bm_exec, bm_free \- Boyer-Moore string search 35.Os
41.SH SYNOPSIS 36.Sh NAME
42.ft B 37.Nm bm_comp ,
43#include <sys/types.h> 38.Nm bm_exec ,
44.br 39.Nm bm_free
45#include <bm.h> 40.Nd Boyer-Moore string search
46.sp 41.Sh SYNOPSIS
47bm_pat * 42.Fd #include <sys/types.h>
48.br 43.Fd #include <bm.h>
49bm_comp(u_char *pattern, size_t patlen, u_char freq[256]); 44.Ft bm_pat *
50.sp 45.Fn bm_comp "const unsigned char *pattern" "size_t patlen" \
51u_char * 46 "const unsigned char freq[256]"
52.br 47.Ft unsigned char *
53bm_exec(bm_pat *pdesc, u_char *text, size_t len); 48.Fn bm_exec "bm_pat *pdesc" "unsigned char *text" "size_t len"
54.sp 49.Ft void
55void 50.Fn bm_free "bm_pat *pdesc"
56.br 51.Sh DESCRIPTION
57bm_free(bm_pat *pdesc);
58.SH DESCRIPTION
59These routines implement an efficient mechanism to find an 52These routines implement an efficient mechanism to find an
60occurrence of a byte string within another byte string. 53occurrence of a byte string within another byte string.
61.PP 54.Pp
62.I Bm_comp 55.Fn bm_comp
63evaluates the 56evaluates
64.I patlen 57.Fa patlen
65bytes starting at 58bytes starting at
66.IR pattern , 59.Fa pattern
67and returns a pointer to a structure describing them. 60and returns a pointer to a structure describing them.
68The bytes referenced by 61The bytes referenced by
69.I pattern 62.Fa pattern
70may be of any value. 63may be of any value.
71.PP 64.Pp
72The search takes advantage of the frequency distribution of the 65The search takes advantage of the frequency distribution of the
73bytes in the text to be searched. 66bytes in the text to be searched.
74If specified, 67If specified,
75.I freq 68.Ar freq
76should be an array of 256 values, 69should be an array of 256 values,
77with higher values indicating that the corresponding character occurs 70with higher values indicating that the corresponding character occurs
78more frequently. 71more frequently.
79(A less than optimal frequency distribution can only result in less 72(A less than optimal frequency distribution can only result in less
80than optimal performance, not incorrect results.) 73than optimal performance, not incorrect results.)
81If 74If
82.I freq 75.Ar freq
83is NULL, 76is
77.Dv NULL ,
84a system default table is used. 78a system default table is used.
85.PP 79.Pp
86.I Bm_exec 80.Fn bm_exec
87returns a pointer to the leftmost occurrence of the string given to 81returns a pointer to the leftmost occurrence of the string given to
88.I bm_comp 82.Fn bm_comp
89within 83within
90.IR text , 84.Ar text ,
91or NULL if none occurs. 85or
86.Dv NULL
87if none occurs.
92The number of bytes in 88The number of bytes in
93.I text 89.Ar text
94must be specified by 90must be specified by
95.IR len . 91.Ar len .
96.PP 92.Pp
97Space allocated for the returned description is discarded 93Space allocated for the returned description is discarded
98by calling 94by calling
99.I bm_free 95.Fn bm_free
100with the returned description as an argument. 96with the returned description as an argument.
101.PP 97.Pp
102The asymptotic speed of 98The asymptotic speed of
103.I bm_exec 99.Fn bm_exec
104is 100is
105.RI O( len / patlen ). 101.Pf O Ns Pq len / patlen .
106.PP 102.Sh SEE ALSO
107.SH "SEE ALSO" 103.Xr regexp 3 ,
108.IR regexp (3), 104.Xr strstr 3
109.IR strstr (3) 105.Rs
110.sp 106.%R "Fast String Searching"
111.IR "Fast String Searching" , 107.%A Andrew Hume
112Hume and Sunday, 108.%A Daniel Sunday
113Software Practice and Experience, 109.%J "Software Practice and Experience"
114Vol. 21, 11 (November 1991) pp. 1221-48. 110.%V Volume 21, 11 (November 1991)
111.%P 1221-48
112.Re