1 files changed, 66 insertions, 0 deletions
diff --git a/lib/libc/stdlib/tdestroy.c b/lib/libc/stdlib/tdestroy.c
new file mode 100644
index 000000000000..2aeb02228e46
--- /dev/null
+++ b/lib/libc/stdlib/tdestroy.c
@@ -0,0 +1,66 @@
+/*
+ * 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)
+{
+}
+
+void
+tdestroy(void *rootp, void (*node_free)(void *))
+{
+	posix_tnode *back, *curr, **front;
+
+	if (rootp == NULL)
+		return;
+	if (node_free == NULL)
+		node_free = nul_node_free;
+
+	back = rootp;
+	front = &back;
+
+	for (;;) {
+		/*
+		 * The sequence of nodes from back to just before *front linked
+		 * by llink have been found to have non-NULL rlink.
+		 *
+		 * Extend *front to (*front)->llink, deleting *front from the
+		 * sequence if it has a NULL rlink.
+		 */
+		curr = *front;
+		if (curr->rlink != NULL)
+			front = &curr->llink;
+		else {
+			*front = curr->llink;
+			node_free(curr->key);
+			free(curr);
+		}
+		if (*front != NULL)
+			continue;
+		if (back == NULL)
+			break;
+
+		/*
+		 * The sequence cannot be extended because *front is NULL.  Make
+		 * the rlink of the back node the new *front, the llink of the
+		 * back node the new back, and free the old back node.
+		 */
+		curr = back;
+		back = curr->llink;
+		if (back == NULL)
+			front = &back;
+		*front = curr->rlink;
+		node_free(curr->key);
+		free(curr);
+	}
+}