Libc-997.1.1.tar.gz

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

diff --git a/stdlib/FreeBSD/tsearch.3 b/stdlib/FreeBSD/tsearch.3
index 6c5ee0ebe180c43dada977aabc666d3c6674bb92..9d7a863206aab5ab83f221f707437dbfdcb3e1d3 100644 (file)
--- a/stdlib/FreeBSD/tsearch.3
+++ b/stdlib/FreeBSD/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.12 2002/12/19 09:40:24 ru 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 * restrict key" "void ** restrict 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 * const *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,37 +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
 The
 .Fn tfind
 function
 .Xr strcmp 3 .
 .Pp
 The
 .Fn tfind
 function

-searches for the datum matched by the argument
+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

+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
 The
 .Fn tsearch

-function
-is identical to
+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
 The
 .Fn tdelete
 .Pp
 The
 .Fn tdelete

-function
-deletes a node from the specified binary search tree and returns
-a pointer to the parent of the node to be deleted.
+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


@@ -91,24 +118,44 @@ will be adjusted.
 .Pp
 The
 .Fn twalk
 .Pp
 The
 .Fn twalk

-function
-walks the binary search tree rooted in
+function walks the binary search tree rooted in

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

-function
-is called with three arguments: a pointer to the current node,
+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
 .Sh RETURN VALUES
 The
 .Fn tsearch


@@ -123,8 +170,12 @@ and
 functions
 return NULL if
 .Fa rootp
 functions
 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