libc: add glibc-compatible tdestroy(3)

[kib]

Summary

The function clears the whole tree.


libc/stdlib/Makefile: one line for each source file name

[kib]

Ed, could you please advise, is it feasible to take this implementation into our libc for licensing considerations? E.g., could I put the 2bsd license on it, since I read the algorithm on the web page and then wrote the code for our posix_tnode binary tree.

The problem is, the algorithm is described by its author in the form of C code, see the web page. I believe this is very elegant solution, much simpler than Morris-style reuse of llink as the parent pointer.

[alc]

Curiously, the blogger's previous post contains a link to this page

https://codegolf.stackexchange.com/questions/478/free-a-binary-tree/489#489P

which contains almost the same code as the 3rd ranked solution.

lib/libc/stdlib/tdestroy.c

20

tn_leftmost would be clearer than tn_last.

[dougm]

lib/libc/stdlib/tdestroy.c

40

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;'?

[kib]

lib/libc/stdlib/tdestroy.c

40

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]

In D54365#1242424, @alc wrote:

Curiously, the blogger's previous post contains a link to this page

https://codegolf.stackexchange.com/questions/478/free-a-binary-tree/489#489P

which contains almost the same code as the 3rd ranked solution.

Allow me to reformulate, you mean that the algorithm presented is not unique and is relatively wide known, so I can put the proper FF copyright and license without causing the authorship issue. Am I right?

[kib]

s/tn_last/tn_leftmost/

[emaste]

It looks like the comments are obtained directly from Raymond Chen's blog.

Here's a suggestion for a possibly improved final comment:

At this point, all children of 'node' have been arranged to be reachable via node->left. We can safely delete the current node and advance to its left child as the new root.

Other than that the original source is credited and I think this change is OK.

We'll want a man page as well (lmk if you want someone to pick that up).

[alc]

In D54365#1242517, @kib wrote:

In D54365#1242424, @alc wrote:

Curiously, the blogger's previous post contains a link to this page

https://codegolf.stackexchange.com/questions/478/free-a-binary-tree/489#489P

which contains almost the same code as the 3rd ranked solution.

Allow me to reformulate, you mean that the algorithm presented is not unique and is relatively wide known, so I can put the proper FF copyright and license without causing the authorship issue. Am I right?

Yes. As evidence, you could cite both sources. My only concern with respect to copyright would be the final comment. The earlier comments are straightforward descriptions of the code.

lib/libc/stdlib/tdestroy.c

34–44

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]

lib/libc/stdlib/tdestroy.c

30–31

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.

[kib]

Handle code suggestions by alc.
Add man page.

[kib]

lib/libc/stdlib/tdestroy.c

30–31

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.

[alc]

lib/libc/stdlib/tdestroy.c

43

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.

[kib]

lib/libc/stdlib/tdestroy.c

43

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

[ziaee]

Relnotes: yes?

[alc]

lib/libc/stdlib/tdestroy.c

43

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.

44–45

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

[kib]

In D54365#1242661, @ziaee wrote:

Relnotes: yes?

Ok, I added this tag.

[kib]

Switch back to start left downwalk with tn_leftmost.
Add SPDF/copyright comment.

[kib]

Add test

[ziaee]

lib/libc/stdlib/tdestroy.c

2

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.

[kib]

Tweak the license block.

[dougm]

lib/libc/stdlib/tdestroy.c

36

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]

lib/libc/stdlib/tdestroy.c

36

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;
	}
}

[alc]

lib/libc/stdlib/tdestroy.c

36

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

[kib]

lib/libc/stdlib/tdestroy.c

36

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]

Fix test