diff options
Diffstat (limited to 'src/lib/libc/stdlib/tsearch.3')
| -rw-r--r-- | src/lib/libc/stdlib/tsearch.3 | 127 |
1 files changed, 127 insertions, 0 deletions
diff --git a/src/lib/libc/stdlib/tsearch.3 b/src/lib/libc/stdlib/tsearch.3 new file mode 100644 index 0000000000..b000a0a8b1 --- /dev/null +++ b/src/lib/libc/stdlib/tsearch.3 | |||
| @@ -0,0 +1,127 @@ | |||
| 1 | .\" Copyright (c) 1997 Todd C. Miller <Todd.Miller@courtesan.com> | ||
| 2 | .\" All rights reserved. | ||
| 3 | .\" | ||
| 4 | .\" Redistribution and use in source and binary forms, with or without | ||
| 5 | .\" modification, are permitted provided that the following conditions | ||
| 6 | .\" are met: | ||
| 7 | .\" 1. Redistributions of source code must retain the above copyright | ||
| 8 | .\" notice, this list of conditions and the following disclaimer. | ||
| 9 | .\" 2. Redistributions in binary form must reproduce the above copyright | ||
| 10 | .\" notice, this list of conditions and the following disclaimer in the | ||
| 11 | .\" documentation and/or other materials provided with the distribution. | ||
| 12 | .\" 3. The name of the author may not be used to endorse or promote products | ||
| 13 | .\" derived from this software without specific prior written permission. | ||
| 14 | .\" | ||
| 15 | .\" THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, | ||
| 16 | .\" INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY | ||
| 17 | .\" AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL | ||
| 18 | .\" THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, | ||
| 19 | .\" EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, | ||
| 20 | .\" PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; | ||
| 21 | .\" OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, | ||
| 22 | .\" WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR | ||
| 23 | .\" OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF | ||
| 24 | .\" ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | ||
| 25 | .\" | ||
| 26 | .\" $OpenBSD: tsearch.3,v 1.9 2000/08/09 15:51:21 aaron Exp $ | ||
| 27 | .\" | ||
| 28 | .Dd June 15, 1997 | ||
| 29 | .Dt TSEARCH 3 | ||
| 30 | .Os | ||
| 31 | .Sh NAME | ||
| 32 | .Nm tsearch , | ||
| 33 | .Nm tfind , | ||
| 34 | .Nm tdelete , | ||
| 35 | .Nm twalk | ||
| 36 | .Nd manipulate binary search trees | ||
| 37 | .Sh SYNOPSIS | ||
| 38 | .Fd #include <search.h> | ||
| 39 | .Ft void * | ||
| 40 | .Fn tdelete "const void *key" "void **rootp" "int (*compar) (const void *, const void *)" | ||
| 41 | .Ft void * | ||
| 42 | .Fn tfind "const void *key" "void * const *rootp" "int (*compar) (const void *, const void *)" | ||
| 43 | .Ft void * | ||
| 44 | .Fn tsearch "const void *key" "void **rootp" "int (*compar) (const void *, const void *)" | ||
| 45 | .Ft void | ||
| 46 | .Fn twalk "const void *root" "void (*action) (const void *, VISIT, int)" | ||
| 47 | .Sh DESCRIPTION | ||
| 48 | The | ||
| 49 | .Fn tdelete , | ||
| 50 | .Fn tfind , | ||
| 51 | .Fn tsearch , | ||
| 52 | and | ||
| 53 | .Fn twalk | ||
| 54 | functions manage binary search trees based on algorithms T and D | ||
| 55 | from Knuth (6.2.2). | ||
| 56 | The comparison function passed in by | ||
| 57 | the user has the same style of return values as | ||
| 58 | .Xr strcmp 3 . | ||
| 59 | .Pp | ||
| 60 | .Fn tfind | ||
| 61 | searches for the datum matched by the argument | ||
| 62 | .Fa key | ||
| 63 | in the binary tree rooted at | ||
| 64 | .Fa rootp , | ||
| 65 | returning a pointer to the datum if it is found and | ||
| 66 | .Dv NULL | ||
| 67 | if it is not. | ||
| 68 | .Pp | ||
| 69 | .Fn tsearch | ||
| 70 | is identical to | ||
| 71 | .Fn tfind | ||
| 72 | except that if no match is found, | ||
| 73 | .Fa key | ||
| 74 | is inserted into the tree and a pointer to it is returned. | ||
| 75 | If | ||
| 76 | .Fa rootp | ||
| 77 | points to a null value a new binary search tree is created. | ||
| 78 | .Pp | ||
| 79 | .Fn tdelete | ||
| 80 | deletes a node from the specified binary search tree and returns | ||
| 81 | a pointer to the parent of the node to be deleted. | ||
| 82 | It takes the same arguments as | ||
| 83 | .Fn tfind | ||
| 84 | and | ||
| 85 | .Fn tsearch . | ||
| 86 | If the node to be deleted is the root of the binary search tree, | ||
| 87 | .Fa rootp | ||
| 88 | will be adjusted. | ||
| 89 | .Pp | ||
| 90 | .Fn twalk | ||
| 91 | walks the binary search tree rooted in | ||
| 92 | .Fa root | ||
| 93 | and calls the function | ||
| 94 | .Fa action | ||
| 95 | on each node. | ||
| 96 | .Fa action | ||
| 97 | is called with three arguments: a pointer to the current node, | ||
| 98 | a value from the enum | ||
| 99 | .Sy "typedef enum { preorder, postorder, endorder, leaf } VISIT;" | ||
| 100 | specifying the traversal type, and a node level (where level | ||
| 101 | zero is the root of the tree). | ||
| 102 | .Sh SEE ALSO | ||
| 103 | .Xr bsearch 3 , | ||
| 104 | .Xr lsearch 3 | ||
| 105 | .Sh RETURN VALUES | ||
| 106 | The | ||
| 107 | .Fn tsearch | ||
| 108 | function returns | ||
| 109 | .Dv NULL | ||
| 110 | if allocation of a new node fails (usually | ||
| 111 | due to a lack of free memory). | ||
| 112 | .Pp | ||
| 113 | .Fn tfind , | ||
| 114 | .Fn tsearch , | ||
| 115 | and | ||
| 116 | .Fn tdelete | ||
| 117 | return | ||
| 118 | .Dv NULL | ||
| 119 | if | ||
| 120 | .Fa rootp | ||
| 121 | is | ||
| 122 | .Dv NULL | ||
| 123 | or the datum cannot be found. | ||
| 124 | .Pp | ||
| 125 | The | ||
| 126 | .Fn twalk | ||
| 127 | function returns no value. | ||