Page MenuHomeFreeBSD
Files F140790524

D54365.diff
No OneTemporary
Actions

D54365.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
@@ -1,19 +1,76 @@
# machine-independent stdlib sources
.PATH: ${LIBC_SRCTOP}/${LIBC_ARCH}/stdlib ${LIBC_SRCTOP}/stdlib
-MISRCS+=C99_Exit.c a64l.c abort.c abs.c atexit.c atof.c atoi.c atol.c atoll.c \
- bsearch.c bsearch_b.c \
- cxa_thread_atexit.c cxa_thread_atexit_impl.c \
- div.c exit.c getenv.c getopt.c getopt_long.c \
- getsubopt.c hcreate.c hcreate_r.c hdestroy_r.c heapsort.c heapsort_b.c \
- hsearch_r.c imaxabs.c imaxdiv.c \
- insque.c l64a.c labs.c ldiv.c llabs.c lldiv.c lsearch.c memalignment.c \
- merge.c mergesort_b.c ptsname.c qsort.c qsort_r.c qsort_r_compat.c \
- qsort_s.c quick_exit.c radixsort.c rand.c \
- random.c reallocarray.c reallocf.c realpath.c recallocarray.c remque.c \
- set_constraint_handler_s.c strfmon.c strtoimax.c \
- strtol.c strtold.c strtoll.c strtoq.c strtoul.c strtonum.c strtoull.c \
- strtoumax.c strtouq.c system.c tdelete.c tfind.c tsearch.c twalk.c
+MISRCS+= \
+ C99_Exit.c \
+ a64l.c \
+ abort.c \
+ abs.c \
+ atexit.c \
+ atof.c \
+ atoi.c \
+ atol.c \
+ atoll.c \
+ bsearch.c \
+ bsearch_b.c \
+ cxa_thread_atexit.c \
+ cxa_thread_atexit_impl.c \
+ div.c \
+ exit.c \
+ getenv.c \
+ getopt.c \
+ getopt_long.c \
+ getsubopt.c \
+ hcreate.c \
+ hcreate_r.c \
+ hdestroy_r.c \
+ heapsort.c \
+ heapsort_b.c \
+ hsearch_r.c \
+ imaxabs.c \
+ imaxdiv.c \
+ insque.c \
+ l64a.c \
+ labs.c \
+ ldiv.c \
+ llabs.c \
+ lldiv.c \
+ lsearch.c \
+ memalignment.c \
+ merge.c \
+ mergesort_b.c \
+ ptsname.c \
+ qsort.c \
+ qsort_r.c \
+ qsort_r_compat.c \
+ qsort_s.c \
+ quick_exit.c \
+ radixsort.c \
+ rand.c \
+ random.c \
+ reallocarray.c \
+ reallocf.c \
+ realpath.c \
+ recallocarray.c \
+ remque.c \
+ set_constraint_handler_s.c \
+ strfmon.c \
+ strtoimax.c \
+ strtol.c \
+ strtold.c \
+ strtoll.c \
+ strtoq.c \
+ strtoul.c \
+ strtonum.c \
+ strtoull.c \
+ strtoumax.c \
+ strtouq.c \
+ system.c \
+ tdelete.c \
+ tdestroy.c \
+ tfind.c \
+ tsearch.c \
+ twalk.c
CFLAGS.qsort.c+= -Wsign-compare
@@ -90,4 +147,5 @@
strtoul.3 strtoumax.3
MLINKS+=tsearch.3 tdelete.3 \
tsearch.3 tfind.3 \
- tsearch.3 twalk.3
+ tsearch.3 twalk.3 \
+ tsearch.3 tdestroy.3
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,73 @@
+/*
+ * 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)
+{
+}
+
+/*
+ * This algorithm for non-recursive non-allocating destruction of the tree
+ * is based on what 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, **tp, *xtn;
+
+ tn = rootp;
+ if (tn == NULL)
+ return;
+ if (node_free == NULL)
+ node_free = nul_node_free;
+
+ for (;;) {
+ /*
+ * Make the right subtree the left subtree of the
+ * leftmost node, and recalculate the leftmost. If we
+ * found a node without right subtree while
+ * descending, it can be imediately freed, and the
+ * tree is collapsed by moving the left subtree up.
+ */
+ tp = &tn;
+ tn_leftmost = tn;
+ while ((xtn = tn_leftmost->llink) != NULL) {
+ if (tn_leftmost->rlink != NULL) {
+ tp = &tn_leftmost->llink;
+ } else {
+ node_free(tn_leftmost->key);
+ free(tn_leftmost);
+ *tp = xtn;
+ }
+ tn_leftmost = xtn;
+ }
+ if (tn == NULL)
+ break;
+ tn_leftmost->llink = tn->rlink;
+
+ /*
+ * 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);
+ if (xtn == NULL)
+ break;
+ tn = xtn;
+ }
+}
diff --git a/lib/libc/stdlib/tsearch.3 b/lib/libc/stdlib/tsearch.3
--- a/lib/libc/stdlib/tsearch.3
+++ b/lib/libc/stdlib/tsearch.3
@@ -36,6 +36,7 @@
.In search.h
.Ft void *
.Fn tdelete "const void * restrict key" "posix_tnode ** restrict rootp" "int (*compar) (const void *, const void *)"
+.Fn tdestroy "posix_tnode *root" "(void (*node_free)(void *)"
.Ft posix_tnode *
.Fn tfind "const void *key" "posix_tnode * const *rootp" "int (*compar) (const void *, const void *)"
.Ft posix_tnode *
@@ -45,6 +46,7 @@
.Sh DESCRIPTION
The
.Fn tdelete ,
+.Fn tdestroy ,
.Fn tfind ,
.Fn tsearch ,
and
@@ -95,6 +97,13 @@
will be adjusted.
.Pp
The
+.Fn tdestroy
+function destroys the whole search tree, freeing all allocated nodes.
+If tree keys need special handling on free, the
+.Fa node_free
+function can be provided, which is called on each key.
+.Pp
+The
.Fn twalk
function
walks the binary search tree rooted in
@@ -128,7 +137,9 @@
.Pp
The
.Fn twalk
-function returns no value.
+and
+.Fn tdestroy
+functions return no value.
.Sh EXAMPLES
This example uses
.Fn tsearch
@@ -184,6 +195,7 @@
tdelete(four, &root, comp);
twalk(root, printwalk);
+ tdestroy(root, NULL);
return 0;
}
.Ed
@@ -192,8 +204,17 @@
.Xr hsearch 3 ,
.Xr lsearch 3
.Sh STANDARDS
-These functions conform to
+These
+.Fn tdelete ,
+.Fn tfind ,
+.Fn tsearch ,
+and
+.Fn twalk
+functions conform to
.St -p1003.1-2008 .
+The
+.Fn tdestroy
+function is the glibc extension.
.Pp
The
.Fa posix_tnode
diff --git a/lib/libc/tests/stdlib/tsearch_test.c b/lib/libc/tests/stdlib/tsearch_test.c
--- a/lib/libc/tests/stdlib/tsearch_test.c
+++ b/lib/libc/tests/stdlib/tsearch_test.c
@@ -147,10 +147,75 @@
ATF_CHECK_EQ(NULL, root);
}
+static int nodes;
+
+struct my_data {
+ int key;
+};
+
+static struct my_data *
+new_my_data(int key)
+{
+ struct my_data *res;
+
+ res = malloc(sizeof(struct my_data));
+ res->key = key;
+ nodes++;
+ return (res);
+}
+
+void
+free_my_data(void *mdp)
+{
+ free(mdp);
+ nodes--;
+}
+
+static int
+compare_my_data(const void *mdp1, const void *mdp2)
+{
+ const struct my_data *md1, *md2;
+
+ md1 = mdp1;
+ md2 = mdp2;
+
+ return (md1->key - md2->key);
+}
+
+static posix_tnode *root = NULL;
+
+static void
+insert(int x)
+{
+ struct my_data *md;
+
+ md = new_my_data(x);
+ tsearch(md, &root, compare_my_data);
+}
+
+ATF_TC_WITHOUT_HEAD(tdestroy_test);
+ATF_TC_BODY(tdestroy_test, tc)
+{
+ root = NULL;
+ insert(1);
+ insert(100);
+ insert(1000);
+ insert(5);
+ insert(6);
+ insert(12);
+ insert(2000);
+ insert(3);
+
+ ATF_CHECK_EQ(8, nodes);
+ tdestroy(root, free_my_data);
+ ATF_CHECK_EQ(0, nodes);
+}
+
ATF_TP_ADD_TCS(tp)
{
ATF_TP_ADD_TC(tp, tsearch_test);
+ ATF_TP_ADD_TC(tp, tdestroy_test);
return (atf_no_error());
}

File Metadata

Mime Type
text/plain
Expires
Mon, Dec 29, 2:08 AM (2 h, 42 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
27345997
Default Alt Text
D54365.diff (7 KB)

Event Timeline