[comp.bugs.sys5] tsearch

ford@amix.commodore.com (Mike "Ford" Ditto) (01/23/91)

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

gwyn@smoke.brl.mil (Doug Gwyn) (01/24/91)

In article <888@amix.commodore.com> ford@amix.commodore.com (Mike "Ford" Ditto) writes:
>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.

Actually, they DO work, but the interface documentation is botched
beyond belief, and when it was reworked for SVID 3 (and SVR4), the
types were gotten utterly wrong.  Consequently I avoid the library
versions and use my own implementation with proper types, etc.

Some time ago, Gary Moss <Moss@BRL.MIL> published his implementation
of these functions; you might contact him for a copy.

allbery@NCoast.ORG (Brandon S. Allbery KB8JRR) (01/24/91)

As quoted from <888@amix.commodore.com> by ford@amix.commodore.com (Mike "Ford" Ditto):
+---------------
| 						    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.
+---------------

It does not say that "key" is returned, it says that "*key is inserted and a
pointer to it is returned".  This is perfectly consistent with what in fact
happens --- it does *not* say that the pointer is the same one that is passed
in, note! --- and I have used tsearch/tfind in a number of programs without
problems.  Admittedly, the manpage could be more clearly worded, but it is
correct as it is.

+---------------
| According to that, both functions should return the exact same key
| pointer which was passed to tsearch originally.  But what they really
+---------------

No, this is *not* what the quoted manpage says!  The manpage neither confirms
nor denies that your key might be *copied* and a pointer to the copy returned.
But if tsearch() were supposed to return "key", the manpage would say so; it
would not use the wording that it in fact does.

++Brandon
-- 
Me: Brandon S. Allbery			    VHF/UHF: KB8JRR on 220, 2m, 440
Internet: allbery@NCoast.ORG		    Packet: KB8JRR @ WA8BXN
America OnLine: KB8JRR			    AMPR: KB8JRR.AmPR.ORG [44.70.4.88]
uunet!usenet.ins.cwru.edu!ncoast!allbery    Delphi: ALLBERY