Page Menu
Home
FreeBSD
Search
Configure Global Search
Log In
Files
F177681109
D61677.1795020048.diff
No One
Temporary
Actions
View File
Edit File
Delete File
View Transforms
Subscribe
Flag For Later
Award Token
Authored By
Unknown
Size
2 KB
Referenced Files
None
Subscribers
None
D61677.1795020048.diff
View Options
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
Details
Attached
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)
Attached To
Mode
D61677: tsearch.3: Clarify node vs. key and improve markup
Attached
Detach File
Event Timeline