--- tsearch.3.orig 2007-03-06 15:44:54.000000000 -0800
+++ tsearch.3 2007-03-06 16:04:48.000000000 -0800
@@ -31,18 +31,36 @@
.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 *
-.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 *
-.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 *
-.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
-.Fn twalk "const void *root" "void (*compar) (const void *, VISIT, int)"
+.Fo twalk
+.Fa "const void *root"
+.Fa "void (*compar) (const void *node, VISIT order, int level)"
+.Fc
.Sh DESCRIPTION
The
.Fn tdelete ,
@@ -50,39 +68,46 @@
.Fn tsearch ,
and
.Fn twalk
-functions manage binary search trees based on algorithms T and D
+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
+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
-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 ,
-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
+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
+function is identical to
.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
-is inserted into the tree and a pointer to it is returned.
+into the tree and returns a pointer to the node.
If
.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
-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
@@ -93,20 +118,44 @@
.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
-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).
+.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 SEE ALSO
.Xr bsearch 3 ,
.Xr hsearch 3 ,
@@ -125,7 +174,7 @@
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