Path: utzoo!utgpu!watserv1!watmath!att!linac!pacific.mps.ohio-state.edu!zaphod.mps.ohio-state.edu!sdd.hp.com!spool2.mu.edu!uunet!cbmvax!amix!ford
From: ford@amix.commodore.com (Mike "Ford" Ditto)
Newsgroups: comp.bugs.sys5
Subject: tsearch(3) and tfind return incorrect pointers
Summary: return value is pointer to the correct value
Keywords: tsearch(3)
Message-ID: <888@amix.commodore.com>
Date: 23 Jan 91 06:22:52 GMT
Reply-To: ford@amix.commodore.com (Mike "Ford" Ditto)
Organization: Commodore-Amiga Unix Development
Lines: 64


I had an occation to use the SysV tree manipulation routines in libc
(tsearch(3)) for the first time today, and discovered that they don't
work.

My code goes something like this (after puting many data into the
tree):

	struct foo *p = tfind(key, &root, compare_func);
	if (p)
	    ...

Well, it turns out that p is (correctly) null if the key is not
matched, but when there is a match, the return value is NOT the same
value that was originally entered into the tree.

The documentation for tsearch() says:

						    If there is	a
     datum in the tree equal to	*key (the  value  pointed  to  by
     key), a pointer to	this found datum is returned.  Otherwise,
     *key is inserted,	and  a	pointer	 to  it	 returned.

And tfind():

     Like tsearch, tfind will search for a  datum  in  the  tree,
     returning	a  pointer to it if found.


According to that, both functions should return the exact same key
pointer which was passed to tsearch originally.  But what they really
return is a pointer to a node of the internal tree structure kept by
the tsearch functions.  The first field of this structure is the key
value that should have been returned.

To quote the code:

		int r = (*compar)(key, (*rootp)->key);
		if (r == 0)
			return ((VOID *)*rootp);

I claim that the return value should be (*rootp)->key.

This seems to be true in R3.2 as well as R4.0.  As far as I can tell,
these functions have never worked as the documentation describes.  I
can imagine someone using them if they knew that the return value was
really the *address* of the pointer to the datum, but the SVR4 man
page and the SVID issue 2 both document otherwise.

The code is so obviously broken, and has been broken for so long, that
I wondered if it might be the documentation that is wrong, but the
documented behavior is obviously much more appropriate.  I suspect
that, simply, nobody has ever used or tested these functions.

The fix is very obvious to someone with source (3 places where a ->key
needs to be added), but I can post a patch if anyone thinks it is
appropriate.

					-=] Ford [=-

"Goodbye, goodbye, goodbye, goodbye,	(In Real Life:  Mike Ditto)
 goodbye, goodbye, goodbye."		ford@amix.commodore.com
 - Oingo Boingo, "Goodbye, Goodbye"	uunet!cbmvax!ditto
					ford@kenobi.commodore.com