Accessing node data through POSIX tdelete()

Question

The manpage for the POSIX binary tree functions includes the following statements:

tdelete() returns a pointer to the parent of the item deleted, or NULL if the item was not found.

tdelete() frees the memory required for the node in the tree. The user is responsible for freeing the memory for the corresponding data.

This means that there is no way to get access to a node's data for a given key from a tdelete() call. One would be required to call tfind() (rather than tsearch() so as not to add the given key), perform destruction of the node's data, and then call tdelete() with the same key to remove the node from the binary tree.

Have I interpreted this correctly? Is there some way around what I perceive to be limitations with this approach?

1. If the key is heap-allocated, it can't be freed (or made useless to the comparison function in use) before the node is deleted. This requires calling tfind() to obtain a pointer to the data, tdelete() to remove the node, and then destroying the data retrieved from the tfind() call.
2. Two lookups are required to delete a node and destroy it's enclosed data.

Answer 1

Matt, I think that your interpretation is correct. For individual deletion of elements this seems unavoidable. (But anyhow it is only a factor of 2 for an operation of \Omega \log N cost ;)

Long time that I didn't use these function, but looking through old code it looks that you can avoid part of the overhead if you destroy the tree all at once (if this is your case) by using two calls of twalk:

1. count the number N of elements in your tree with an appropriate call to twalk
2. allocate an array of size N of pointers to tree items
3. fill this array by a second twalk through the tree
4. run through this array and for each tree node first delete its data and then the node itself

If your really need such a thing you can find a thread safe C++ encapsulation of these calls in our library parXXL in the directory par/sys.