git: b8c99e7d912f - main - libc: add glibc-compatible tdestroy(3)

The branch main has been updated by kib:

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

commit b8c99e7d912f0dad84cec80f8c4331646b87a3ec
Author:     Konstantin Belousov <kib@FreeBSD.org>
AuthorDate: 2025-12-25 23:38:25 +0000
Commit:     Konstantin Belousov <kib@FreeBSD.org>
CommitDate: 2025-12-29 17:18:55 +0000

    libc: add glibc-compatible tdestroy(3)
    
    The function clears the whole tree.
    
    Relnotes:       yes
    Reviewed by:    alc, emaste
    Discussed with: dougm
    Sponsored by:   The FreeBSD Foundation
    MFC after:      1 week
    Differential revision:  https://reviews.freebsd.org/D54365
---
 include/search.h             |  1 +
 lib/libc/stdlib/Makefile.inc |  1 +
 lib/libc/stdlib/Symbol.map   |  1 +
 lib/libc/stdlib/tdestroy.c   | 68 ++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 71 insertions(+)

diff --git a/include/search.h b/include/search.h
index 0615da2b42ba..5ac25a0d491f 100644
--- a/include/search.h
+++ b/include/search.h
@@ -77,6 +77,7 @@ void	 twalk(const posix_tnode *, void (*)(const posix_tnode *, VISIT, int));
 int	 hcreate_r(size_t, struct hsearch_data *);
 void	 hdestroy_r(struct hsearch_data *);
 int	 hsearch_r(ENTRY, ACTION, ENTRY **, struct hsearch_data *);
+void	 tdestroy(void *, void (*)(void *));
 #endif
 
 __END_DECLS
diff --git a/lib/libc/stdlib/Makefile.inc b/lib/libc/stdlib/Makefile.inc
index 37a927b0597b..e46a8d7340b2 100644
--- a/lib/libc/stdlib/Makefile.inc
+++ b/lib/libc/stdlib/Makefile.inc
@@ -67,6 +67,7 @@ MISRCS+= \
 	strtouq.c \
 	system.c \
 	tdelete.c \
+	tdestroy.c \
 	tfind.c \
 	tsearch.c \
 	twalk.c
diff --git a/lib/libc/stdlib/Symbol.map b/lib/libc/stdlib/Symbol.map
index 8b7e97c3cbdc..03a6d0b543ac 100644
--- a/lib/libc/stdlib/Symbol.map
+++ b/lib/libc/stdlib/Symbol.map
@@ -134,6 +134,7 @@ FBSD_1.8 {
 FBSD_1.9 {
 	memalignment;
 	recallocarray;
+	tdestroy;
 };
 
 FBSDprivate_1.0 {
diff --git a/lib/libc/stdlib/tdestroy.c b/lib/libc/stdlib/tdestroy.c
new file mode 100644
index 000000000000..c324e151da11
--- /dev/null
+++ b/lib/libc/stdlib/tdestroy.c
@@ -0,0 +1,68 @@
+/*
+ * Copyright 2025 The FreeBSD Foundation
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ *
+ * This software was developed by Konstantin Belousov <kib@FreeBSD.org>
+ * under sponsorship from the FreeBSD Foundation.
+ */
+
+#define	_SEARCH_PRIVATE
+#include <search.h>
+#include <stdlib.h>
+
+static void
+nul_node_free(void *node __unused)
+{
+}
+
+/* Find the leftmost node. */
+static posix_tnode *
+tdestroy_find_leftmost(posix_tnode *tn)
+{
+	while (tn->llink != NULL)
+		tn = tn->llink;
+	return (tn);
+}
+
+/*
+ * This algorithm for non-recursive non-allocating destruction of the tree
+ * is described in
+ * https://codegolf.stackexchange.com/questions/478/free-a-binary-tree/489#489P
+ * and in https://devblogs.microsoft.com/oldnewthing/20251107-00/?p=111774.
+ */
+void
+tdestroy(void *rootp, void (*node_free)(void *))
+{
+	posix_tnode *tn, *tn_leftmost, *xtn;
+
+	tn = rootp;
+	if (tn == NULL)
+		return;
+	if (node_free == NULL)
+		node_free = nul_node_free;
+	tn_leftmost = tn;
+
+	while (tn != NULL) {
+		/*
+		 * Make the right subtree the left subtree of the
+		 * leftmost node, and recalculate the leftmost.
+		 */
+		tn_leftmost = tdestroy_find_leftmost(tn_leftmost);
+		if (tn->rlink != NULL) {
+			tn_leftmost->llink = tn->rlink;
+			tn_leftmost = tn_leftmost->llink;
+		}
+
+		/*
+		 * At this point, all children of tn have been
+		 * arranged to be reachable via tn->left. We can
+		 * safely delete the current node and advance to its
+		 * left child as the new root.
+		 */
+		xtn = tn->llink;
+		node_free(tn->key);
+		free(tn);
+		tn = xtn;
+	}
+}