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