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