From nobody Wed Nov 18 13:15:22 2026 X-Original-To: dev-commits-src-all@mlmmj.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id 4jV2CG6tNzz71gYn for ; Wed, 18 Nov 2026 13:15:22 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange x25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by mx1.freebsd.org (Postfix) with ESMTPS id 4jV2CG5hlwz3L6w for ; Wed, 18 Nov 2026 13:15:22 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1795007722; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=EJ4lchSpXQvN0dGlZO1IW2T1wipSxr4JE0+I7/i3UY4=; b=EF2ceKGeVSKF6RwX6hT0lqblKmriTVgYi/urbQBiddrrk5Y7KivICbAH8BUJGGEfOxlaKE ciX3cYyb7xBt74azN1VcHt+LjnDb8PtqqBOLL+XHQoSM6X15qZfQxjp6X0HNOsib2j9YMJ tLwhxTb3UjuRjPGVsB3/5DRZOe24tfiQOni4rndBfFWBqh+rNMtV+l5YQAjt5NEilyLoiZ agRj1seLNsBplM6eMrICs8HYnIYxBQS/bq8ot/CqBmE9w6+ChPHUEdjhqqfycIYJFzvfnr L8FOz1OOBcEcTqD4o73L5b/AX5kDuz1YtFScqlzQwZ07LXPrSAfmhl0rpuzQMA== ARC-Seal: i=1; a=rsa-sha256; d=freebsd.org; s=dkim; cv=none; t=1795007722; b=sGN7yikhNNAdhppO7BvFmWbv/yPjb9wVcfT4R70d2ERPrqhzF3C5Vd6ktuiTisczRcGo4P i43pabglv75QdkbV9N/AdChNGZ3DY87Fca6j054aHCT55qIWuolMLNb2jqJzVabGqKycOX 3ElzQ2ZhBBNStNy8Hsp8pXiFeTdiKbC2+KkNlucqGyXeSpOnHJ99HddUvGQEXxSxMyrg74 GTLLrxO/44R6PHjMiizBmgvj3GsuhUkmJvl6kMbzGokHqklkmmnGonav9KmU3PXMKa27VL FeWfWrA1VfFNvl0vs6usqtibFgmrPMrBUcbncT0kifAxXK95PNVuo2oWPi8fwg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1795007722; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=EJ4lchSpXQvN0dGlZO1IW2T1wipSxr4JE0+I7/i3UY4=; b=uQLl9atQQgUXEYx2sjX+U8My8ysIv3XjbAVBPqsEmQEaH3SSr7Dk68JVSFdDbAaMTYUZBt s8b9OETd5P3/tLzcv1Lnge17oVLh7X1lFqph8r8nvuKuVkST4mefFZqWjOrBXpy8gEJCEl dggCEh+MvT9cEVEuoZ8C1zerj/YbocwAGKG0pKRpZao+Ku4vHyYXCdSKXccA6PfBXBV9xC PsiBCOQBCIJfa+Bj+6/0nhF04xZM3DOvVwSSvC/ezVemgJGq5UcxxDgzk2OitaS/j+Pb5P Llj3VWvvgiG2W8dYIvcuuaUC8+P+VpPGZULWgn/6WhaL1QJEYaApkxryYgr1zQ== ARC-Authentication-Results: i=1; mx1.freebsd.org; none Received: from gitrepo.freebsd.org (gitrepo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:5]) by mxrelay.nyi.freebsd.org (Postfix) with ESMTP id 4jV2CG5MFXzFjb for ; Wed, 18 Nov 2026 13:15:22 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from git (uid 1279) (envelope-from git@FreeBSD.org) id 14ce2 by gitrepo.freebsd.org (DragonFly Mail Agent v0.13+ on gitrepo.freebsd.org); Wed, 18 Nov 2026 13:15:22 +0000 To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org From: Aymeric Wibo Subject: git: 5ddfe1e2e9ee - main - tsearch.3: Clarify node vs. key and improve markup List-Archive: https://lists.freebsd.org/archives/dev-commits-src-all X-BeenThere: dev-commits-src-all@freebsd.org List-Id: Commit messages for all branches of the src repository List-Post: List-Help: List-Subscribe: List-Unsubscribe: List-Owner: Precedence: list MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Git-Committer: obiwac X-Git-Repository: src X-Git-Refname: refs/heads/main X-Git-Reftype: branch X-Git-Commit: 5ddfe1e2e9ee23fc131080147039cf101d9203a6 Auto-Submitted: auto-generated Date: Wed, 18 Nov 2026 13:15:22 +0000 Message-Id: <6afda4ea.14ce2.27502fe5@gitrepo.freebsd.org> The branch main has been updated by obiwac: URL: https://cgit.FreeBSD.org/src/commit/?id=5ddfe1e2e9ee23fc131080147039cf101d9203a6 commit 5ddfe1e2e9ee23fc131080147039cf101d9203a6 Author: Aymeric Wibo AuthorDate: 2026-11-17 16:19:10 +0000 Commit: Aymeric Wibo 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