Defect report from : Louis Strous , Private
(Please direct followup comments direct to yyyyyyyyyyyyyy@xxxxxxxxxxxxx)
@ page 0 line 0 section 0 comment {1}
Problem:
Edition of Specification (Year): 2004
Defect code : 2. Omission
Regarding the binary search tree interface,
http://www.opengroup.org/onlinepubs/009695399/functions/tdelete.html: This
interface is currently not symmetrical with respect to adding data to and
removing data from the binary tree. I believe this to be an omission.
The tsearch() function can be used to add a key (a pointer to a user-supplied
data record) to the binary tree, but there is (as far as I can tell) no
functionality to efficiently return this original key (and hence the original
data record) to the user at the end of removing that key from the binary tree.
The tdelete() function (which removes a key from the binary tree) does not
return the original key, but rather a pointer to the *parent* (in terms of the
binary tree) of the deleted key.
System resources are typically tied to the original key (e.g., it is typically
a pointer to dynamically allocated memory that contains the actual key value
and additional information whose retrieval through the key value is the purpose
of using the binary tree), so the user typically needs the original key, at the
very least to be able to properly deallocate the associated system resources.
Using the current interface, deleting the original key from the binary tree and
returning it to the user (i.e., the symmetrical reverse of adding the key to
the tree) requires using tfind() or tsearch() to locate the original key (based
on a key that is equal [according to the specified comparison function] but not
identical to the original key -- because it lacks the additional information),
and then tdelete() to remove it from the binary tree. This is inefficient,
because it requires the key to be searched in the binary tree *twice*: once
during the course of tfind() or tsearch(), and once more during the course of
tdelete().
Action:
Alternative 1: Adjust tdelete() so it returns the original key of the node to
be deleted, rather than the parent node. tdelete() can continue to return the
null pointer if the key could not be found. I imagine that this alternative is
out of the question because it is not backwardly compatible. However, I cannot
think of an application of the current interface where it is useful to know the
parent of a node that was just removed from a binary tree, so the chance of
breaking existing applications by adjusting tdelete() in the manner described
may be sufficiently remote.
Alternative 2: provide an alternative function tremove() that is equal in all
respects to tdelete() except that where tdelete() returns the parent node of
the removed node, tremove() returns the original key of the removed node.
SAMPLE USAGE:
void *root; /* the root of a binary tree built using tsearch */
char *key = "Jones, J.";
{
void *record, *data;
size_t keysize, datasize;
/* ... omitted code: set data, datasize, compar ... */
keysize = strlen(key) + 1;
/* construct the record */
record = malloc(keysize + datasize);
memcpy(record, key, keysize);
memcpy(record + keysize, data, datasize);
/* add it to the tree */
tsearch(record, &root, compar);
}
{
char *original_key;
/* remove the key from the tree */
original_key = tremove("Jones, J.", &root, compar);
/* and release its resources */
free(original_key);
/* "original_key" had the same value as "record" above */
}
|