search.h: tdelete ()?

[Ivan Shmakov]

I've got interested in using the search.h functions, yet I don't
seem to understand the meaning of the tdelete ()'s return value
description. Which is [1]:

[...] 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.

[1] http://pubs.opengroup.org/onlinepubs/9699919799/functions/tdelete.html

Somehow, I fail to understand if there's any valid way to use
the value returned, other than to check whether there was
actually a matching node in the tree or not.

Given that tsearch () may associate an arbitrary pointer with a
node of the tree, I'd expect for tdelete () to be able to return
that pointer somehow (so that, e. g., one may free () the
referenced memory.) Do I understand it correctly that to
properly remove the node and the associated memory object one
has to walk over the tree twice instead, e. g. as shown below?

#if 1
myobj *op
= tfind (key, &tree, myobj_cmp);
if (op != 0) {
tdelete (key, &tree, myobj_cmp);
myobj_free (op);
}
#else
/* instead of: */
myobj *op
= tdelete_and_return (key, &tree, myobj_cmp);
/* assuming myobj_free () ignores null pointers */
myobj_free (op);
#endif

TIA.

 

[Barry Schwarz]

I've got interested in using the search.h functions, yet I don't
seem to understand the meaning of the tdelete ()'s return value
description. Which is [1]:

[...] 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.

[1] http://pubs.opengroup.org/onlinepubs/9699919799/functions/tdelete.html

Somehow, I fail to understand if there's any valid way to use
the value returned, other than to check whether there was
actually a matching node in the tree or not.

Given that tsearch () may associate an arbitrary pointer with a
node of the tree, I'd expect for tdelete () to be able to return
that pointer somehow (so that, e. g., one may free () the
referenced memory.) Do I understand it correctly that to
properly remove the node and the associated memory object one
has to walk over the tree twice instead, e. g. as shown below?

Since tdelete() actually DELETES the node, not just removes it from
the tree, the node's memory address officially becomes indeterminate
and cannot be evaluated for any purpose. The best tdelete() can do is
tell you where the node used to be in the tree.

You do not free the memory, tdelete() already did.

Furthermore, if tdelete() cannot find the key node in the tree (note
the search is conducted by node values, not node addresses), then it
simply returns NULL.

#if 1
myobj *op
= tfind (key, &tree, myobj_cmp);
if (op != 0) {

None of the above is needed.

tdelete (key, &tree, myobj_cmp);

This will work properly whether the key exists in the tree or not.

myobj_free (op);

At this point, the value in op is indeterminate. You are attempting
to free something that has already been freed.

}
#else
/* instead of: */
myobj *op
= tdelete_and_return (key, &tree, myobj_cmp);
/* assuming myobj_free () ignores null pointers */
myobj_free (op);

This entire branch of code is based on a false premise.

 

[glen herrmannsfeldt]

I've got interested in using the search.h functions, yet I don't
seem to understand the meaning of the tdelete ()'s return value
description. Which is [1]:

[...] 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.

[1] http://pubs.opengroup.org/onlinepubs/9699919799/functions/tdelete.html

Somehow, I fail to understand if there's any valid way to use
the value returned, other than to check whether there was
actually a matching node in the tree or not.

The one I have doesn't have that comment, but it probably does
something similar.

Seems like the usual use is to test for null or not.

As the root doesn't have a parent, it can't return a pointer to
the parent when the root node is deleted.

Given that tsearch () may associate an arbitrary pointer with a
node of the tree, I'd expect for tdelete () to be able to return
that pointer somehow (so that, e. g., one may free () the
referenced memory.) Do I understand it correctly that to
properly remove the node and the associated memory object one
has to walk over the tree twice instead, e. g. as shown below?

Seems to me that you use tfind(), delete the associated memory,
then tdelete(). I suppose it would be a little faster to delete
given the node pointer than having it search the tree again,
but then again, it should all be in cache.

-- glen

 

[glen herrmannsfeldt]

(snip)

Since tdelete() actually DELETES the node, not just removes it from
the tree, the node's memory address officially becomes indeterminate
and cannot be evaluated for any purpose. The best tdelete() can do is
tell you where the node used to be in the tree.

You do not free the memory, tdelete() already did.

That is what I thought he meant at first, but consider that the node
might contain a pointer to malloc()'ed memory. Then again, it might not.

If it does, you might want to free() that before you tdelete().

A call that would delete given the node address would be a little
more convenient, but not much.

-- glen

 

[James Kuyper]

I've got interested in using the search.h functions, yet I don't
seem to understand the meaning of the tdelete ()'s return value
description. Which is [1]:

[...] 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.

[1] http://pubs.opengroup.org/onlinepubs/9699919799/functions/tdelete.html

Your reference to that web page implies that it's a POSIX function, in
which case you'll get get better answers to your questions in a forum
specific to POSIX, such as comp.unix.programmer.

 

[Ivan Shmakov]

[Cross-posting to news:comp.unix.programmer, as suggested.]

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.
[1] http://pubs.opengroup.org/onlinepubs/9699919799/functions/tdelete.html
Somehow, I fail to understand if there's any valid way to use the
value returned, other than to check whether there was actually a
matching node in the tree or not.

[...]

Since tdelete() actually DELETES the node, not just removes it from
the tree, the node's memory address officially becomes indeterminate
and cannot be evaluated for any purpose. The best tdelete() can do
is tell you where the node used to be in the tree.

And yet I'm interested not in the node itself, but its, well,
"payload pointer." As in:

struct binary_tree_node {
struct binary_tree_node *less, *greater;
void *payload;
};

That is what I thought he meant at first, but consider that the node
might contain a pointer to malloc()'ed memory. Then again, it might
not.

In my case, it's actually a pointer returned by malloc (), which
points to a structure, one of whose fields is, in turn, a
malloc ()-ed pointer, or 0. (Which then may point to an array
of malloc ()-ed pointers, unless 0.)

Thus, as one can see, there's quite a few free ()-s to consider.
(Which tdelete (), being ignorant of the data structures
involved, just won't be able to do by itself.)

If it does, you might want to free() that before you tdelete().

A call that would delete given the node address would be a little
more convenient,
Yes.

but not much.

Well, the good point is that it's a tree, and thus can be
searched through in logarithmic time...

Thanks. (I guess I've been thinking too much into this.)