This is the mail archive of the
glibc-bugs@sourceware.org
mailing list for the glibc project.
[Bug libc/5223] New: tsearch returns node instead of key
- From: "andreas dot abel at ifi dot lmu dot de" <sourceware-bugzilla at sourceware dot org>
- To: glibc-bugs at sources dot redhat dot com
- Date: 27 Oct 2007 13:56:00 -0000
- Subject: [Bug libc/5223] New: tsearch returns node instead of key
- Reply-to: sourceware-bugzilla at sourceware dot org
The specification:
http://www.gnu.org/software/libc/manual/html_node/Tree-Search-Function.html#Tree-Search-Function
? Function: void * tsearch (const void *key, void **rootp, comparison_fn_t compar)
...
The return value is a pointer to the matching element in the tree. If a new
element was created the pointer points to the new data (which is in fact key).
If an entry had to be created and the program ran out of space NULL is returned.
However, the implementation does not return the key, but the node. The user
does not know of nodes (an internal data structure of search trees), this
breakes the abstraction barrier.
This is the CVS version from today (1.13):
/* Find or insert datum into search tree.
KEY is the key to be located, ROOTP is the address of tree root,
COMPAR the ordering function. */
void *
__tsearch (const void *key, void **vrootp, __compar_fn_t compar)
{
node q;
...
while (*nextp != NULL)
{
node root = *rootp;
r = (*compar) (key, root->key);
if (r == 0)
return root; /* SHOULD BE root->key !! */
...
}
q = (struct node_t *) malloc (sizeof (struct node_t));
if (q != NULL)
{
*nextp = q; /* link new node to old */
q->key = key; /* initialize new node */
...
}
return q; /* SHOULD BE q->keq !! */
}
It is hard to believe this bug has survived until today.
Yet, the unit test
test-tsearch.c
does never test whether tsearch run with a new key returns actually this key.
Thanks for looking into this,
Andreas
--
Summary: tsearch returns node instead of key
Product: glibc
Version: unspecified
Status: NEW
Severity: normal
Priority: P2
Component: libc
AssignedTo: drepper at redhat dot com
ReportedBy: andreas dot abel at ifi dot lmu dot de
CC: andreas dot abel at ifi dot lmu dot de,glibc-bugs at
sources dot redhat dot com
GCC build triplet: CVS 1.13 (today)
http://sourceware.org/bugzilla/show_bug.cgi?id=5223
------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.