diff options
Diffstat (limited to 'src/lib/libc/string/bm.3')
| -rw-r--r-- | src/lib/libc/string/bm.3 | 116 |
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 |
| 40 | bm_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 |
| 47 | bm_pat * | 42 | .Fd #include <sys/types.h> |
| 48 | .br | 43 | .Fd #include <bm.h> |
| 49 | bm_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" \ |
| 51 | u_char * | 46 | "const unsigned char freq[256]" |
| 52 | .br | 47 | .Ft unsigned char * |
| 53 | bm_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 |
| 55 | void | 50 | .Fn bm_free "bm_pat *pdesc" |
| 56 | .br | 51 | .Sh DESCRIPTION |
| 57 | bm_free(bm_pat *pdesc); | ||
| 58 | .SH DESCRIPTION | ||
| 59 | These routines implement an efficient mechanism to find an | 52 | These routines implement an efficient mechanism to find an |
| 60 | occurrence of a byte string within another byte string. | 53 | occurrence of a byte string within another byte string. |
| 61 | .PP | 54 | .Pp |
| 62 | .I Bm_comp | 55 | .Fn bm_comp |
| 63 | evaluates the | 56 | evaluates |
| 64 | .I patlen | 57 | .Fa patlen |
| 65 | bytes starting at | 58 | bytes starting at |
| 66 | .IR pattern , | 59 | .Fa pattern |
| 67 | and returns a pointer to a structure describing them. | 60 | and returns a pointer to a structure describing them. |
| 68 | The bytes referenced by | 61 | The bytes referenced by |
| 69 | .I pattern | 62 | .Fa pattern |
| 70 | may be of any value. | 63 | may be of any value. |
| 71 | .PP | 64 | .Pp |
| 72 | The search takes advantage of the frequency distribution of the | 65 | The search takes advantage of the frequency distribution of the |
| 73 | bytes in the text to be searched. | 66 | bytes in the text to be searched. |
| 74 | If specified, | 67 | If specified, |
| 75 | .I freq | 68 | .Ar freq |
| 76 | should be an array of 256 values, | 69 | should be an array of 256 values, |
| 77 | with higher values indicating that the corresponding character occurs | 70 | with higher values indicating that the corresponding character occurs |
| 78 | more frequently. | 71 | more 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 |
| 80 | than optimal performance, not incorrect results.) | 73 | than optimal performance, not incorrect results.) |
| 81 | If | 74 | If |
| 82 | .I freq | 75 | .Ar freq |
| 83 | is NULL, | 76 | is |
| 77 | .Dv NULL , | ||
| 84 | a system default table is used. | 78 | a system default table is used. |
| 85 | .PP | 79 | .Pp |
| 86 | .I Bm_exec | 80 | .Fn bm_exec |
| 87 | returns a pointer to the leftmost occurrence of the string given to | 81 | returns a pointer to the leftmost occurrence of the string given to |
| 88 | .I bm_comp | 82 | .Fn bm_comp |
| 89 | within | 83 | within |
| 90 | .IR text , | 84 | .Ar text , |
| 91 | or NULL if none occurs. | 85 | or |
| 86 | .Dv NULL | ||
| 87 | if none occurs. | ||
| 92 | The number of bytes in | 88 | The number of bytes in |
| 93 | .I text | 89 | .Ar text |
| 94 | must be specified by | 90 | must be specified by |
| 95 | .IR len . | 91 | .Ar len . |
| 96 | .PP | 92 | .Pp |
| 97 | Space allocated for the returned description is discarded | 93 | Space allocated for the returned description is discarded |
| 98 | by calling | 94 | by calling |
| 99 | .I bm_free | 95 | .Fn bm_free |
| 100 | with the returned description as an argument. | 96 | with the returned description as an argument. |
| 101 | .PP | 97 | .Pp |
| 102 | The asymptotic speed of | 98 | The asymptotic speed of |
| 103 | .I bm_exec | 99 | .Fn bm_exec |
| 104 | is | 100 | is |
| 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 |
| 112 | Hume and Sunday, | 108 | .%A Daniel Sunday |
| 113 | Software Practice and Experience, | 109 | .%J "Software Practice and Experience" |
| 114 | Vol. 21, 11 (November 1991) pp. 1221-48. | 110 | .%V Volume 21, 11 (November 1991) |
| 111 | .%P 1221-48 | ||
| 112 | .Re | ||
