public inbox for glibc-bugs@sourceware.org
help / color / mirror / Atom feed
From: "andreas dot abel at ifi dot lmu dot de" <sourceware-bugzilla@sourceware.org>
To: glibc-bugs@sources.redhat.com
Subject: [Bug libc/5223] New: tsearch returns node instead of key
Date: Sat, 27 Oct 2007 13:56:00 -0000	[thread overview]
Message-ID: <20071027135600.5223.andreas.abel@ifi.lmu.de> (raw)

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


             reply	other threads:[~2007-10-27 13:56 UTC|newest]

Thread overview: 2+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2007-10-27 13:56 andreas dot abel at ifi dot lmu dot de [this message]
2007-10-27 17:47 ` [Bug libc/5223] " schwab at suse dot de

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20071027135600.5223.andreas.abel@ifi.lmu.de \
    --to=sourceware-bugzilla@sourceware.org \
    --cc=glibc-bugs@sources.redhat.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).