git: 5ddfe1e2e9ee - main - tsearch.3: Clarify node vs. key and improve markup

From: Aymeric Wibo <obiwac_at_FreeBSD.org>
Date: Wed, 18 Nov 2026 13:15:22 UTC
The branch main has been updated by obiwac:

URL: https://cgit.FreeBSD.org/src/commit/?id=5ddfe1e2e9ee23fc131080147039cf101d9203a6

commit 5ddfe1e2e9ee23fc131080147039cf101d9203a6
Author:     Aymeric Wibo <obiwac@FreeBSD.org>
AuthorDate: 2026-11-17 16:19:10 +0000
Commit:     Aymeric Wibo <obiwac@FreeBSD.org>
CommitDate: 2026-11-18 13:14:39 +0000

    tsearch.3: Clarify node vs. key and improve markup
    
    Pull in clarifications from Apple's libc: describe the comparison
    function's arguments as key pointers, refer to the nodes returned by
    tfind() and tsearch() rather than to the "datum", explain how to get a
    node's key, note that the action function is called only once for leaf
    nodes, and note about how VISIT names don't map to the usual traversal
    order nomenclature.
    
    The paragraph about the first member of a node being a pointer to its
    key was rewritten, as Apple's wording was not strictly accurate.
    
    Apple's Libc also has a paragraph describing what each traversal order
    does, but it is mostly redundant, so it is not included here.
    
    While here, mark up NULL and the VISIT values with .Dv, move the VISIT
    typedef into a literal block, and fix mandoc lint warnings.
    
    MFC after:      3 days
    Reviewed by:    ziaee
    Obtained from:  https://github.com/apple-oss-distributions/libc (partially)
    Sponsored by:   Klara, Inc.
    Differential Revision:  https://reviews.freebsd.org/D61677
---
 lib/libc/stdlib/tsearch.3 | 65 +++++++++++++++++++++++++++++++++++++----------
 1 file changed, 52 insertions(+), 13 deletions(-)

diff --git a/lib/libc/stdlib/tsearch.3 b/lib/libc/stdlib/tsearch.3
index 936036e5f51a..657acdfedf18 100644
--- a/lib/libc/stdlib/tsearch.3
+++ b/lib/libc/stdlib/tsearch.3
@@ -59,30 +59,42 @@ the advantage of calling the comparison function relatively
 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,14 +129,36 @@ The
 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).
+.Vt VISIT
+specifying the traversal type, and a node level
+.Pq where level 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
-due to a lack of free memory).
+function returns
+.Dv NULL
+if allocation of a new node fails
+.Pq usually due to a lack of free memory .
 .Pp
 The
 .Fn tfind ,
@@ -132,9 +166,13 @@ The
 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 @@ to search for four strings in
 .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