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.3109
1 files changed, 55 insertions, 54 deletions
diff --git a/src/lib/libc/string/bm.3 b/src/lib/libc/string/bm.3
index 2264a6a1c4..7138ee4271 100644
--- a/src/lib/libc/string/bm.3
+++ b/src/lib/libc/string/bm.3
@@ -32,83 +32,84 @@
32.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 32.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
33.\" SUCH DAMAGE. 33.\" SUCH DAMAGE.
34.\" 34.\"
35.\" from: @(#)bm.3 8.4 (Berkeley) 6/21/94 35.\" $OpenBSD: bm.3,v 1.6 2001/06/23 14:42:12 deraadt Exp $
36.\" $Id: bm.3,v 1.1.1.1 1995/10/18 08:42:20 deraadt Exp $
37.\" 36.\"
38.TH BM 3 37.Dd June 29, 1999
39.SH NAME 38.Dt BM 3
40bm_comp, bm_exec, bm_free \- Boyer-Moore string search 39.Os
41.SH SYNOPSIS 40.Sh NAME
42.ft B 41.Nm bm_comp ,
43#include <sys/types.h> 42.Nm bm_exec ,
44.br 43.Nm bm_free
45#include <bm.h> 44.Nd Boyer-Moore string search
46.sp 45.Sh SYNOPSIS
47bm_pat * 46.Fd #include <sys/types.h>
48.br 47.Fd #include <bm.h>
49bm_comp(u_char *pattern, size_t patlen, u_char freq[256]); 48.Ft bm_pat *
50.sp 49.Fn bm_comp "u_char *pattern" "size_t patlen" "u_char freq[256]"
51u_char * 50.Ft u_char *
52.br 51.Fn bm_exec "bm_pat *pdesc" "u_char *text" "size_t len"
53bm_exec(bm_pat *pdesc, u_char *text, size_t len); 52.Ft void
54.sp 53.Fn bm_free "bm_pat *pdesc"
55void 54.Sh DESCRIPTION
56.br
57bm_free(bm_pat *pdesc);
58.SH DESCRIPTION
59These routines implement an efficient mechanism to find an 55These routines implement an efficient mechanism to find an
60occurrence of a byte string within another byte string. 56occurrence of a byte string within another byte string.
61.PP 57.Pp
62.I Bm_comp 58.Fn bm_comp
63evaluates the 59evaluates
64.I patlen 60.Fa patlen
65bytes starting at 61bytes starting at
66.IR pattern , 62.Fa pattern
67and returns a pointer to a structure describing them. 63and returns a pointer to a structure describing them.
68The bytes referenced by 64The bytes referenced by
69.I pattern 65.Fa pattern
70may be of any value. 66may be of any value.
71.PP 67.Pp
72The search takes advantage of the frequency distribution of the 68The search takes advantage of the frequency distribution of the
73bytes in the text to be searched. 69bytes in the text to be searched.
74If specified, 70If specified,
75.I freq 71.Ar freq
76should be an array of 256 values, 72should be an array of 256 values,
77with higher values indicating that the corresponding character occurs 73with higher values indicating that the corresponding character occurs
78more frequently. 74more frequently.
79(A less than optimal frequency distribution can only result in less 75(A less than optimal frequency distribution can only result in less
80than optimal performance, not incorrect results.) 76than optimal performance, not incorrect results.)
81If 77If
82.I freq 78.Ar freq
83is NULL, 79is
80.Dv NULL ,
84a system default table is used. 81a system default table is used.
85.PP 82.Pp
86.I Bm_exec 83.Fn bm_exec
87returns a pointer to the leftmost occurrence of the string given to 84returns a pointer to the leftmost occurrence of the string given to
88.I bm_comp 85.Fn bm_comp
89within 86within
90.IR text , 87.Ar text ,
91or NULL if none occurs. 88or
89.Dv NULL
90if none occurs.
92The number of bytes in 91The number of bytes in
93.I text 92.Ar text
94must be specified by 93must be specified by
95.IR len . 94.Ar len .
96.PP 95.Pp
97Space allocated for the returned description is discarded 96Space allocated for the returned description is discarded
98by calling 97by calling
99.I bm_free 98.Fn bm_free
100with the returned description as an argument. 99with the returned description as an argument.
101.PP 100.Pp
102The asymptotic speed of 101The asymptotic speed of
103.I bm_exec 102.Fn bm_exec
104is 103is
105.RI O( len / patlen ). 104.Pf O Ns Pq len / patlen .
106.PP 105.Sh SEE ALSO
107.SH "SEE ALSO" 106.Xr regexp 3 ,
108.IR regexp (3), 107.Xr strstr 3
109.IR strstr (3) 108.Rs
110.sp 109.%R "Fast String Searching"
111.IR "Fast String Searching" , 110.%A Andrew Hume
112Hume and Sunday, 111.%A Daniel Sunday
113Software Practice and Experience, 112.%J "Software Practice and Experience"
114Vol. 21, 11 (November 1991) pp. 1221-48. 113.%V Volume 21, 11 (November 1991)
114.%P 1221-48
115.Re