Page MenuHomeFreeBSD

D61677.1795020048.diff
No OneTemporary

Authored By
Unknown
Size
2 KB
Referenced Files
None
Subscribers
None

D61677.1795020048.diff

diff --git a/lib/libc/stdlib/tsearch.3 b/lib/libc/stdlib/tsearch.3
--- a/lib/libc/stdlib/tsearch.3
+++ b/lib/libc/stdlib/tsearch.3
@@ -59,30 +59,42 @@
infrequently.
.Pp
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
+.Dv NULL
if it is not.
.Pp
+The first member of a node is a pointer to its key.
+Thus, you should generally cast this result to a
+double pointer to the data type stored in the tree, for example
+.Vt "struct foo **" ,
+and use double indirection to retrieve the
+original key value.
+.Pp
The
.Fn tsearch
function
is identical to
.Fn tfind
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
+.Dv NULL
+value a new binary search tree is created.
.Pp
The
.Fn tdelete
@@ -117,13 +129,35 @@
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;"
+.Vt VISIT
specifying the traversal type, and a node level (where level
-zero is the root of the tree).
+zero is the root of the tree):
+.Bd -literal -offset indent
+typedef enum { preorder, postorder, endorder, leaf } VISIT;
+.Ed
+.Pp
+The
+.Fa action
+function is called only once for a leaf node, with the
+traversal type
+.Dv leaf .
+.Pp
+Note: the names for the traversal types differ somewhat from
+common parlance.
+The traversal type
+.Dv postorder
+corresponds
+to what would typically be referred to as in-order, and the
+traversal type
+.Dv 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
+function returns
+.Dv NULL
+if allocation of a new node fails (usually
due to a lack of free memory).
.Pp
The
@@ -132,9 +166,13 @@
and
.Fn tdelete
functions
-return NULL if
+return
+.Dv NULL
+if
.Fa rootp
-is NULL or the datum cannot be found.
+is
+.Dv NULL
+or the node cannot be found.
.Pp
The
.Fn twalk
@@ -148,7 +186,8 @@
.Dv root .
Because the strings are not already present, they are added.
.Fn tsearch
-is called twice on the fourth string to demonstrate that a string is not added when it is already present.
+is called twice on the fourth string to demonstrate that a string is not added
+when it is already present.
.Fn tfind
is used to find the single instance of the fourth string, and
.Fn tdelete

File Metadata

Mime Type
text/plain
Expires
Wed, Nov 18, 4:40 PM (2 h, 49 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
41827844
Default Alt Text
D61677.1795020048.diff (2 KB)

Event Timeline