Differential D54365 Diff 168714 lib/libc/stdlib/tdestroy.c

Changeset View

Standalone View

View Options

lib/libc/stdlib/tdestroy.c

This file was added.

ziaeeUnsubmitted

Done

- /*-

+ /*

* SPDX-License-Identifier: BSD-2-Clause

This hyphen was for a long abandoned parser, and has been removed from the style guides.

Also, the copyright line comes before the SPDX line when omiting the license body.

ziaee: This hyphen was for a long abandoned parser, and has been removed from the style guides. Also…

* 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 *

alcUnsubmitted

Done

tn_leftmost would be clearer than tn_last.

alc: tn_leftmost would be clearer than tn_last.

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

alcUnsubmitted

Done

The other web page points out that you can eliminate this loop by swapping the order of the assignment to ->llink and the identical loop below. That is likely beneficial by a tiny amount.

alc: The other web page points out that you can eliminate this loop by swapping the order of the…

kibAuthorUnsubmitted

Done

I just need to calculate the leftmost starting from tn then. Also, I moved the inner loop into the helper, IMO it is easier to read this way.

kib: I just need to calculate the leftmost starting from tn then. Also, I moved the inner loop into…

* and in https://devblogs.microsoft.com/oldnewthing/20251107-00/?p=111774.

void

tdestroy(void *rootp, void (*node_free)(void *))

{

dougmUnsubmitted

Done

void

tdestroy(void *rootp, void (*node_free)(void *))

{

+ posix_tnode *tn, **tp, *tn_leftmost, *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.

+ */

+ tp = &tn;

+ tn_leftmost = tn;

+ while (tn_leftmost->llink != NULL) {

+ xtn = tn_leftmost->llink;

+ if (xtn != 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);

+ tn = xtn;

+ }

+ {

posix_tnode *tn, *tn_leftmost, *xtn;

It appears to me that for a tree with all rlink == NULL for every node, this will take n*n time to destroy a tree of n nodes.

I tried writing something that would delete any node the first time it was visited if it had only one non-NULL child. That should address the performance problem. It is untested.

dougm: It appears to me that for a tree with all rlink == NULL for every node, this will take n*n time…

dougmUnsubmitted

Done

I need to edit a line of that. So I'll just dump the whole edited thing there:

void
tdestroy(void *rootp, void (*node_free)(void *))
{
	posix_tnode *tn, **tp, *tn_leftmost, *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.
		 */
		tp = &tn;
		tn_leftmost = tn;
		while (tn_leftmost->llink != NULL) {
			xtn = tn_leftmost->llink;
			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);
		tn = xtn;
	}
}

dougm: I need to edit a line of that. So I'll just dump the whole edited thing there: ``` void…

alcUnsubmitted

Done

The current version should 2 * n, not n * n.

alc: The current version should 2 * n, not n * n.

kibAuthorUnsubmitted

Done

Indeed, the version that did tn_leftmost = tdestroy_find_leftmost(tn) is O(n^2) for the case of tree without right branches, but the current version recomputes tn_leftmost only once.

kib: Indeed, the version that did `tn_leftmost = tdestroy_find_leftmost(tn)` is O(n^2) for the case…

alcUnsubmitted

Done

I think that it makes sense to fix @dougm 's version, and use it. The effect being that we will only touch nodes with no right child once rather than twice.

alc: I think that it makes sense to fix @dougm 's version, and use it. The effect being that we…

dougmUnsubmitted

Done

Not needed.

dougm: Not needed.

posix_tnode *tn, *tn_leftmost, *xtn;

tn = rootp;

if (tn == NULL)

dougmUnsubmitted

Done

Putting the 'find' loop here means that after reading one field of tn, we may read many more nodes before we read the other fields of tn, and take a needless cache miss on account of that. Why not put the 'find' loop after 'tn = xtn;'?

dougm: Putting the 'find' loop here means that after reading one field of tn, we may read many more…

kibAuthorUnsubmitted

Done

I believe that at this point it is possible that e.g. tn == tn_leftmost, so moving the loop down would access the freed memory.

kib: I believe that at this point it is possible that e.g. tn == tn_leftmost, so moving the loop…

return;

dougmUnsubmitted

Done

This comment needs to be updated.

dougm: This comment needs to be updated.

if (node_free == NULL)

dougmUnsubmitted

Done

* found a node without right subtree while

- * descending, it can be imediately freed, and the

+ * descending, it can be immediately freed, and the

* tree is collapsed by moving the left subtree up.

dougm:

node_free = nul_node_free;

alcUnsubmitted

Done

The stackexchange version initializes tn_leftmost to tn before the outer loop. Then, you can pass tn_leftmost to tdestroy_find_leftmost() here. Otherwise, tdestroy_find_leftmost() is going to be applied to some nodes multiple times, not just once.

alc: The stackexchange version initializes tn_leftmost to tn before the outer loop. Then, you can…

kibAuthorUnsubmitted

Done

This does not work for the same reason as I explained to Doug: sometimes tn_leftmost is same as tn, which is already freed.

kib: This does not work for the same reason as I explained to Doug: sometimes tn_leftmost is same as…

alcUnsubmitted

Done

Yes, you are right. The "golf" version, i.e.,

void f(Node* t)
{
        Node*o,*l    = t;

        for(;t;free(o))
        {
            for(;l->left;l = l->left);
            l->left = t->right;
            o = t;
            t = t->left;
        }
}

is broken in that way. Go back to calling tdestroy_find_leftmost() before the outer loop to initialize tn_leftmost, and updating ->llink before calling tdestroy_find_leftmost() inside the loop. Then, you can safely pass tn_leftmost to tdestroy_find_leftmost() inside the loop, and avoid tdestroy_find_leftmost() iterating over some nodes multiple times.

alc: Yes, you are right. The "golf" version, i.e., ``` void f(Node* t) { Node*o,*l = t…

tn_leftmost = tn;

alcUnsubmitted

Done

The other version puts this block inside an if (tn->rlink != NULL) {, avoiding a store of NULL to memory when there is no right subtree (at the cost of introducing a conditional branch to the case where the right subtree is non-empty).

alc: The other version puts this block inside an `if (tn->rlink != NULL) {`, avoiding a store of…

alcUnsubmitted

Done

tn_leftmost = tdestroy_find_leftmost(tn);

- if (tn->rlink != NULL)

+ if (tn->rlink != NULL) {

tn_leftmost->llink = tn->rlink;

+ tn_leftmost = tn_leftmost->llink;

+ }

* At this point, all children of tn have been

On second thought, wouldn't this added assignment solve the problem?

alc: On second thought, wouldn't this added assignment solve the problem?

while (tn != NULL) {

dougmUnsubmitted

Not Done

This was previously initialized before the loop, and here. I think the one outside the loop should be restored, and this one dropped.

dougm: This was previously initialized before the loop, and here. I think the one outside the loop…

kibAuthorUnsubmitted

Done

This segfaults.

kib: This segfaults.

* 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

dougmUnsubmitted

Not Done

tn_leftmost = tn_leftmost->llink;

was here before I started messing with things. Shouldn't it still be?

dougm: tn_leftmost = tn_leftmost->llink; was here before I started messing with things. Shouldn't it…

kibAuthorUnsubmitted

Done

And this segfaults.

I believe any free of a node must recalculate tn_leftmost.

kib: And this segfaults. I believe any free of a node must recalculate tn_leftmost.

* left child as the new root.

xtn = tn->llink;

node_free(tn->key);

free(tn);

tn = xtn;

}