Date: Fri, 16 Jan 2026 22:27:34 +0000 From: Doug Moore <dougm@FreeBSD.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org Subject: git: 988555e329d0 - main - tdestroy: don't visit one-child node twice Message-ID: <696abb56.35b8c.7fd6e468@gitrepo.freebsd.org>
index | next in thread | raw e-mail
The branch main has been updated by dougm: URL: https://cgit.FreeBSD.org/src/commit/?id=988555e329d00a47c42e5e849e78c1b8e4ce2e17 commit 988555e329d00a47c42e5e849e78c1b8e4ce2e17 Author: Doug Moore <dougm@FreeBSD.org> AuthorDate: 2026-01-16 22:26:09 +0000 Commit: Doug Moore <dougm@FreeBSD.org> CommitDate: 2026-01-16 22:26:09 +0000 tdestroy: don't visit one-child node twice Change tdestroy() to immediately free a node with no right child as soon as it is encountered. Currently, such nodes are visited twice before deletion. Reviewed by: kib Differential Revision: https://reviews.freebsd.org/D54699 --- lib/libc/stdlib/tdestroy.c | 66 ++++++++++++++++++++++------------------------ 1 file changed, 32 insertions(+), 34 deletions(-) diff --git a/lib/libc/stdlib/tdestroy.c b/lib/libc/stdlib/tdestroy.c index c324e151da11..2aeb02228e46 100644 --- a/lib/libc/stdlib/tdestroy.c +++ b/lib/libc/stdlib/tdestroy.c @@ -16,53 +16,51 @@ 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; + posix_tnode *back, *curr, **front; - tn = rootp; - if (tn == NULL) + if (rootp == NULL) return; if (node_free == NULL) node_free = nul_node_free; - tn_leftmost = tn; - while (tn != NULL) { + back = rootp; + front = &back; + + for (;;) { /* - * Make the right subtree the left subtree of the - * leftmost node, and recalculate the leftmost. + * 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. */ - tn_leftmost = tdestroy_find_leftmost(tn_leftmost); - if (tn->rlink != NULL) { - tn_leftmost->llink = tn->rlink; - tn_leftmost = tn_leftmost->llink; + 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; /* - * 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. + * 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. */ - xtn = tn->llink; - node_free(tn->key); - free(tn); - tn = xtn; + curr = back; + back = curr->llink; + if (back == NULL) + front = &back; + *front = curr->rlink; + node_free(curr->key); + free(curr); } }home | help
Want to link to this message? Use this
URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?696abb56.35b8c.7fd6e468>