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. |
---|