[Bug libc/5223] New: tsearch returns node instead of key

[Bug libc/5223] New: tsearch returns node instead of key

[andreas dot abel at ifi dot lmu dot de]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 2205 bytes --]

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.

[Bug libc/5223] tsearch returns node instead of key

[schwab at suse dot de]

------- Additional Comments From schwab at suse dot de  2007-10-27 17:47 -------
It returns a pointer to the element (node), not the key (which is the first 
pointer in the node).

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |INVALID


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.