Page MenuHomeFreeBSD
Files F142650535

D54365.id.diff
No OneTemporary
Actions

D54365.id.diff
View Options

diff --git a/include/search.h b/include/search.h
--- a/include/search.h
+++ b/include/search.h
@@ -77,6 +77,7 @@
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
--- a/lib/libc/stdlib/Makefile.inc
+++ b/lib/libc/stdlib/Makefile.inc
@@ -67,6 +67,7 @@
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
--- a/lib/libc/stdlib/Symbol.map
+++ b/lib/libc/stdlib/Symbol.map
@@ -134,6 +134,7 @@
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
--- /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;
+ }
+}

File Metadata

Mime Type
text/plain
Expires
Thu, Jan 22, 9:08 PM (5 h, 22 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
27863157
Default Alt Text
D54365.id.diff (2 KB)

Event Timeline