xref: /dragonfly/lib/libc/stdlib/tsearch.3 (revision cd1c6085) 
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.15 2006/06/23 13:36:33 keramida Exp $
29.\" $DragonFly: src/lib/libc/stdlib/tsearch.c,v 1.6 2005/11/24 17:18:30 swildner Exp $
30.\"
31.Dd June 15, 1997
32.Dt TSEARCH 3
33.Os
34.Sh NAME
35.Nm tsearch ,
36.Nm tfind ,
37.Nm tdelete ,
38.Nm twalk
39.Nd manipulate binary search trees
40.Sh LIBRARY
41.Lb libc
42.Sh SYNOPSIS
43.In search.h
44.Ft void *
45.Fn tdelete "const void * restrict key" "void ** restrict rootp" "int (*compar) (const void *, const void *)"
46.Ft void *
47.Fn tfind "const void *key" "void * const *rootp" "int (*compar) (const void *, const void *)"
48.Ft void *
49.Fn tsearch "const void *key" "void **rootp" "int (*compar) (const void *, const void *)"
50.Ft void
51.Fn twalk "const void *root" "void (*action) (const void *, VISIT, int)"
52.Sh DESCRIPTION
53The
54.Fn tdelete ,
55.Fn tfind ,
56.Fn tsearch ,
57and
58.Fn twalk
59functions manage binary search trees based on algorithms T and D
60from Knuth (6.2.2).
61The comparison function passed in by
62the user has the same style of return values as
63.Xr strcmp 3 .
64.Pp
65The
66.Fn tfind
67function
68searches for the datum matched by the argument
69.Fa key
70in the binary tree rooted at
71.Fa rootp ,
72returning a pointer to the datum if it is found and NULL
73if it is not.
74.Pp
75The
76.Fn tsearch
77function
78is identical to
79.Fn tfind
80except that if no match is found,
81.Fa key
82is inserted into the tree and a pointer to it is returned.
83If
84.Fa rootp
85points to a NULL value a new binary search tree is created.
86.Pp
87The
88.Fn tdelete
89function
90deletes a node from the specified binary search tree and returns
91a pointer to the parent of the node to be deleted.
92It takes the same arguments as
93.Fn tfind
94and
95.Fn tsearch .
96If the node to be deleted is the root of the binary search tree,
97.Fa rootp
98will be adjusted.
99.Pp
100The
101.Fn twalk
102function
103walks the binary search tree rooted in
104.Fa root
105and calls the function
106.Fa action
107on each node.
108The
109.Fa action
110function
111is called with three arguments: a pointer to the current node,
112a value from the enum
113.Sy "typedef enum { preorder, postorder, endorder, leaf } VISIT;"
114specifying the traversal type, and a node level (where level
115zero is the root of the tree).
116.Sh RETURN VALUES
117The
118.Fn tsearch
119function returns NULL if allocation of a new node fails (usually
120due to a lack of free memory).
121.Pp
122The
123.Fn tfind ,
124.Fn tsearch ,
125and
126.Fn tdelete
127functions
128return NULL if
129.Fa rootp
130is NULL or the datum cannot be found.
131.Pp
132The
133.Fn twalk
134function returns no value.
135.Sh SEE ALSO
136.Xr bsearch 3 ,
137.Xr hsearch 3 ,
138.Xr lsearch 3
139