Page MenuHomeFreeBSD
Files F141172204

D54365.id168611.diff
No OneTemporary
Actions

D54365.id168611.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
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,55 @@
+
+#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 described by Raymond Chen 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;
+
+ /* Find the leftmost node. */
+ tn_leftmost = tn;
+ while (tn_leftmost->llink != NULL)
+ tn_leftmost = tn_leftmost->llink;
+
+ while (tn != NULL) {
+ /*
+ * Make the right subtree the left subtree of the
+ * leftmost node.
+ */
+ tn_leftmost->llink = tn->rlink;
+
+ /*
+ * Find the new leftmost node.
+ */
+ while (tn_leftmost->llink != NULL)
+ tn_leftmost = tn_leftmost->llink;
+
+ /*
+ * We have arranged for the eventual deletion of all
+ * the children. Now we can delete the root node and
+ * promote the left child to be the new root.
+ */
+ xtn = tn->llink;
+ node_free(tn->key);
+ free(tn);
+ tn = xtn;
+ }
+}

File Metadata

Mime Type
text/plain
Expires
Fri, Jan 2, 9:16 PM (22 h, 4 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
27462575
Default Alt Text
D54365.id168611.diff (3 KB)

Event Timeline