Libc-763.11.tar.gz

[apple/libc.git] / stdlib / tsearch.3

diff --git a/stdlib/tsearch.3 b/stdlib/tsearch.3
index a36fe894f0b30fa9311e3cd101b708d02432d95f..9d7a863206aab5ab83f221f707437dbfdcb3e1d3 100644 (file)
--- a/stdlib/tsearch.3
+++ b/stdlib/tsearch.3
@@ -25,24 +25,42 @@
 .\" ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 .\"
 .\"    OpenBSD: tsearch.3,v 1.2 1998/06/21 22:13:49 millert Exp
 .\" ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 .\"
 .\"    OpenBSD: tsearch.3,v 1.2 1998/06/21 22:13:49 millert Exp

-.\" $FreeBSD: src/lib/libc/stdlib/tsearch.3,v 1.7 2001/09/07 14:46:36 asmodai Exp $
+.\" $FreeBSD: src/lib/libc/stdlib/tsearch.3,v 1.15 2006/06/23 13:36:33 keramida Exp $

 .\"
 .Dd June 15, 1997
 .Dt TSEARCH 3
 .Os
 .Sh NAME
 .\"
 .Dd June 15, 1997
 .Dt TSEARCH 3
 .Os
 .Sh NAME

-.Nm tsearch , tfind , tdelete , twalk
+.Nm tdelete ,
+.Nm tfind ,
+.Nm tsearch ,
+.Nm twalk

 .Nd manipulate binary search trees
 .Sh SYNOPSIS
 .In search.h
 .Ft void *
 .Nd manipulate binary search trees
 .Sh SYNOPSIS
 .In search.h
 .Ft void *

-.Fn tdelete "const void *key" "void **rootp" "int (*compar) (const void *, const void *)"
+.Fo tdelete
+.Fa "const void *restrict key"
+.Fa "void **restrict rootp"
+.Fa "int (*compar) (const void *key1, const void *key2)"
+.Fc

 .Ft void *
 .Ft void *

-.Fn tfind "const void *key" "void **rootp" "int (*compar) (const void *, const void *)"
+.Fo tfind
+.Fa "const void *key"
+.Fa "void *const *rootp"
+.Fa "int (*compar) (const void *key1, const void *key2)"
+.Fc

 .Ft void *
 .Ft void *

-.Fn tsearch "const void *key" "void **rootp" "int (*compar) (const void *, const void *)"
+.Fo tsearch
+.Fa "const void *key"
+.Fa "void **rootp"
+.Fa "int (*compar) (const void *key1, const void *key2)"
+.Fc

 .Ft void
 .Ft void

-.Fn twalk "const void *root" "void (*compar) (const void *, VISIT, int)"
+.Fo twalk
+.Fa "const void *root"
+.Fa "void (*action) (const void *node, VISIT order, int level)"
+.Fc

 .Sh DESCRIPTION
 The
 .Fn tdelete ,
 .Sh DESCRIPTION
 The
 .Fn tdelete ,


@@ -50,31 +68,46 @@ The
 .Fn tsearch ,
 and
 .Fn twalk
 .Fn tsearch ,
 and
 .Fn twalk

-functions manage binary search trees based on algorithms T and D
-from Knuth (6.2.2).  The comparison function passed in by
-the user has the same style of return values as
+functions manage binary search trees, based on algorithms T and D
+from Knuth (6.2.2).
+The comparison function passed in by
+the user takes two arguments, each of which is a key
+pointer.
+This function has the same style of return values as

 .Xr strcmp 3 .
 .Pp
 .Xr strcmp 3 .
 .Pp

-.Fn Tfind
-searches for the datum matched by the argument
+The
+.Fn tfind
+function
+searches for a node whose key matches the argument

 .Fa key
 in the binary tree rooted at
 .Fa rootp ,
 .Fa key
 in the binary tree rooted at
 .Fa rootp ,

-returning a pointer to the datum if it is found and NULL
+returning a pointer to the node if it is found and NULL

 if it is not.
 .Pp
 if it is not.
 .Pp

-.Fn Tsearch
-is identical to
+Note that a node is itself a pointer to the key of the node.
+Thus, you should generally cast this result to a
+double pointer to the data type stored in the tree, for example
+(struct myType **), and use double indirection to retrieve the
+original key value.
+.Pp
+The
+.Fn tsearch
+function is identical to

 .Fn tfind
 .Fn tfind

-except that if no match is found,
+except that, if no match is found,
+it inserts a new node for the

 .Fa key
 .Fa key

-is inserted into the tree and a pointer to it is returned.  If
+into the tree and returns a pointer to the node.
+If

 .Fa rootp
 .Fa rootp

-points to a NULL value a new binary search tree is created.
+points to a NULL value, a new binary search tree is created.

 .Pp
 .Pp

-.Fn Tdelete
-deletes a node from the specified binary search tree and returns
-a pointer to the parent of the node to be deleted.
+The
+.Fn tdelete
+function deletes a node from the specified binary search tree
+and returns a pointer to the parent of the node that was deleted.

 It takes the same arguments as
 .Fn tfind
 and
 It takes the same arguments as
 .Fn tfind
 and


@@ -83,36 +116,66 @@ If the node to be deleted is the root of the binary search tree,
 .Fa rootp
 will be adjusted.
 .Pp
 .Fa rootp
 will be adjusted.
 .Pp

-.Fn Twalk
-walks the binary search tree rooted in
+The
+.Fn twalk
+function walks the binary search tree rooted in

 .Fa root
 and calls the function
 .Fa action
 on each node.
 .Fa root
 and calls the function
 .Fa action
 on each node.

-.Fa Action
-is called with three arguments: a pointer to the current node,
+The
+.Fa action
+function is called with three arguments: a pointer to the current node,

 a value from the enum
 .Sy "typedef enum { preorder, postorder, endorder, leaf } VISIT;"
 specifying the traversal type, and a node level (where level
 zero is the root of the tree).
 a value from the enum
 .Sy "typedef enum { preorder, postorder, endorder, leaf } VISIT;"
 specifying the traversal type, and a node level (where level
 zero is the root of the tree).

-.Sh SEE ALSO
-.Xr bsearch 3 ,
-.Xr hsearch 3 ,
-.Xr lsearch 3
+.Pp
+As
+.Fn twalk
+traverses the tree, it calls the
+.Fa action
+function with the traversal type "preorder"
+before visiting the left subtree of the
+.Fa node ,
+with the
+traversal type "postorder" before visiting the right subtree
+of the
+.Fa node ,
+and with the traversal type "endorder" after
+visiting the right subtree of the
+.Fa node .
+.Pp.
+The
+.Fa action
+function is called only once for a leaf-node, with the
+traversal type "leaf."
+.Pp
+Note: the names for the traversal types differ somewhat from
+common parlance.  The traversal type "postorder" corresponds
+to what would typically be referred to as in-order, and the
+traversal type "endorder" corresponds to what would typically
+be referred to as post-order.

 .Sh RETURN VALUES
 The
 .Fn tsearch
 function returns NULL if allocation of a new node fails (usually
 due to a lack of free memory).
 .Pp
 .Sh RETURN VALUES
 The
 .Fn tsearch
 function returns NULL if allocation of a new node fails (usually
 due to a lack of free memory).
 .Pp

-.Fn Tfind ,
+The
+.Fn tfind ,

 .Fn tsearch ,
 and
 .Fn tdelete
 .Fn tsearch ,
 and
 .Fn tdelete

+functions

 return NULL if
 .Fa rootp
 return NULL if
 .Fa rootp

-is NULL or the datum cannot be found.
+is NULL or the node cannot be found.

 .Pp
 The
 .Fn twalk
 function returns no value.
 .Pp
 The
 .Fn twalk
 function returns no value.

+.Sh SEE ALSO
+.Xr bsearch 3 ,
+.Xr hsearch 3 ,
+.Xr lsearch 3