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