C standard function 'tdelete()' has a memory bug since its inception | Hacker News Reader

C standard function 'tdelete()' has a memory bug since its inception

cee.studio

3 pointscee-studio8 comments

Quoting from "man tdelete": tdelete() returns a pointer to the parent of the node deleted, or NULL if the item was not found. If the deleted node was the root node, tdelete() returns a dangling pointer that must not be accessed.

The quote in TFA is incomplete. The design of tdelete is quite bad, but I would argue that it is not a memory bug. A bug would occur when the caller of tdelete ignores the spec and dereferences the dangling pointer.

https://linux.die.net/man/3/tdelete does not have it. My man does not have it. I'm curious what system do you use.

linux.die.net man-pages are crap. See e.g. man7.org for better ones: https://man7.org/linux/man-pages/man3/tdelete.3.html

> The tdelete() function shall return a pointer to the parent of the deleted node, or an unspecified non-null pointer if the deleted node was the root node, or a null pointer if the node is not found.

Oh and here is Ubuntu man pages, seeing that they are online and all:

https://manpages.ubuntu.com/manpages/focal/en/man3/tdelete.3...

Thanks for pointing out the updated man page. This is much better. But the another question is how developers are supposed to know which node is the root node, which is supposed to be opaque.

You have to know the root of the tree to do anything:

           void *tsearch(const void *key, void **rootp,
                           int (*compar)(const void *, const void *));

           void *tfind(const void *key, void *const *rootp,
                           int (*compar)(const void *, const void *));

    ...

    rootp points to a variable which points to the root of the tree.

You can't operate on a tree unless you have a pointer to it, i.e., it's root.

Pop OS 20.04, which is derived from Ubuntu 20.04.

The man page on macOS High Sierra 10.13.6 states:

"The tdelete() function deletes a node from the specified binary search tree and returns a pointer to the parent of the node that was deleted. It takes the same arguments as tfind() and tsearch(). If the node to be deleted is the root of the binary search tree, rootp will be adjusted."

It seems reasonable to infer that if a tree has only 1 node that node is the root node.

If I'm wrong I'd appreciate an explanation; I'm only a hobbyist programmer and my understanding of these things is limited.

Misleading headline: tdelete() is not a "C standard function", but a POSIX function (as the linked article says).

Reply on news.ycombinator.com