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  .\"
 30  .Dd June 15, 1997
 31  .Dt TSEARCH 3
 32  .Os
 33  .Sh NAME
 34  .Nm tdelete ,
 35  .Nm tfind ,
 36  .Nm tsearch ,
 37  .Nm twalk
 38  .Nd manipulate binary search trees
 39  .Sh SYNOPSIS
 40  .In search.h
 41  .Ft void *
 42  .Fo tdelete
 43  .Fa "const void *restrict key"
 44  .Fa "void **restrict rootp"
 45  .Fa "int (*compar) (const void *key1, const void *key2)"
 46  .Fc
 47  .Ft void *
 48  .Fo tfind
 49  .Fa "const void *key"
 50  .Fa "void *const *rootp"
 51  .Fa "int (*compar) (const void *key1, const void *key2)"
 52  .Fc
 53  .Ft void *
 54  .Fo tsearch
 55  .Fa "const void *key"
 56  .Fa "void **rootp"
 57  .Fa "int (*compar) (const void *key1, const void *key2)"
 58  .Fc
 59  .Ft void
 60  .Fo twalk
 61  .Fa "const void *root"
 62  .Fa "void (*action) (const void *node, VISIT order, int level)"
 63  .Fc
 64  .Sh DESCRIPTION
 65  The
 66  .Fn tdelete ,
 67  .Fn tfind ,
 68  .Fn tsearch ,
 69  and
 70  .Fn twalk
 71  functions manage binary search trees, based on algorithms T and D
 72  from Knuth (6.2.2).
 73  The comparison function passed in by
 74  the user takes two arguments, each of which is a key
 75  pointer.
 76  This function has the same style of return values as
 77  .Xr strcmp 3 .
 78  .Pp
 79  The
 80  .Fn tfind
 81  function
 82  searches for a node whose key matches the argument
 83  .Fa key
 84  in the binary tree rooted at
 85  .Fa rootp ,
 86  returning a pointer to the node if it is found and NULL
 87  if it is not.
 88  .Pp
 89  Note that a node is itself a pointer to the key of the node.
 90  Thus, you should generally cast this result to a
 91  double pointer to the data type stored in the tree, for example
 92  (struct myType **), and use double indirection to retrieve the
 93  original key value.
 94  .Pp
 95  The
 96  .Fn tsearch
 97  function is identical to
 98  .Fn tfind
 99  except that, if no match is found,
100  it inserts a new node for the
101  .Fa key
102  into the tree and returns a pointer to the node.
103  If
104  .Fa rootp
105  points to a NULL value, a new binary search tree is created.
106  .Pp
107  The
108  .Fn tdelete
109  function deletes a node from the specified binary search tree
110  and returns a pointer to the parent of the node that was deleted.
111  It takes the same arguments as
112  .Fn tfind
113  and
114  .Fn tsearch .
115  If the node to be deleted is the root of the binary search tree,
116  .Fa rootp
117  will be adjusted.
118  .Pp
119  The
120  .Fn twalk
121  function walks the binary search tree rooted in
122  .Fa root
123  and calls the function
124  .Fa action
125  on each node.
126  The
127  .Fa action
128  function is called with three arguments: a pointer to the current node,
129  a value from the enum
130  .Sy "typedef enum { preorder, postorder, endorder, leaf } VISIT;"
131  specifying the traversal type, and a node level (where level
132  zero is the root of the tree).
133  .Pp
134  As
135  .Fn twalk
136  traverses the tree, it calls the
137  .Fa action
138  function with the traversal type "preorder"
139  before visiting the left subtree of the
140  .Fa node ,
141  with the
142  traversal type "postorder" before visiting the right subtree
143  of the
144  .Fa node ,
145  and with the traversal type "endorder" after
146  visiting the right subtree of the
147  .Fa node .
148  .Pp.
149  The
150  .Fa action
151  function is called only once for a leaf-node, with the
152  traversal type "leaf."
153  .Pp
154  Note: the names for the traversal types differ somewhat from
155  common parlance.  The traversal type "postorder" corresponds
156  to what would typically be referred to as in-order, and the
157  traversal type "endorder" corresponds to what would typically
158  be referred to as post-order.
159  .Sh RETURN VALUES
160  The
161  .Fn tsearch
162  function returns NULL if allocation of a new node fails (usually
163  due to a lack of free memory).
164  .Pp
165  The
166  .Fn tfind ,
167  .Fn tsearch ,
168  and
169  .Fn tdelete
170  functions
171  return NULL if
172  .Fa rootp
173  is NULL or the node cannot be found.
174  .Pp
175  The
176  .Fn twalk
177  function returns no value.
178  .Sh SEE ALSO
179  .Xr bsearch 3 ,
180  .Xr hsearch 3 ,
181  .Xr lsearch 3