chip@tct.uucp (Chip Salzenberg) (12/25/90)
[This discussion is relevant to both the C and C++ languages; hence the cross-post. Please direct followups appropriately.] According to rfg@NCD.COM (Ron Guilmette): >Both qsort() and bsearch() have a similar need to be fed a pointer to a >function which itself takes two parameters of type pointer-to-T, where >the type T is the same for both of the two parameters (but is never >actually the type `void'). Bzzt. Thanks for playing, though. Both qsort() and bsearch() require a pointer to a function which does *actually* take two parameters of type pointer-to-void. The fact that the function in question will almost immediately cast those pointers into pointer-to-T is utterly irrelevant. Remember that qsort() cannot know the real type of the objects it is sorting. Remember also (as noted in an unquoted portion of Ron's article) that on word-addressed machines, pointer-to-T and pointer-to-void may differ in representation and/or size. It is therefore obvious that qsort() is unable to make a correct call to a function that has pointer parameters of any type other than pointer-to-void (or, equivalently, pointer-to-char). If you declare a comparison function that take parameters of type pointer-to-T, and pass the address of that function to qsort(), and qsort() still works, you're quite fortunate (or unfortunate, depending on how you look at it). But that doesn't change the fact that such a practice is not, nor can it ever be, portable. >But what if that compare routine is stashed away in a precompiled library? Then the person who wrote it doesn't know what he's doing, and you should stop using his code immediately. >In short, IT IS IMPOSSIBLE TO WRITE QSORT() ENTIRELY IN ANSI C OR IN C++ >IN SUCH A WAY THAT IT IS COMPLETELY PORTABLE. This statement is false. It is entirely possible to do so, thanks to ANSI's guarantee that pointer-to-char and pointer-to-void will always have identical representations. -- Chip Salzenberg at Teltronics/TCT <chip@tct.uucp>, <uunet!pdn!tct!chip> "Please don't send me any more of yer scandalous email, Mr. Salzenberg..." -- Bruce Becker
barmar@think.com (Barry Margolin) (12/26/90)
In article <277640DD.4A70@tct.uucp> chip@tct.uucp (Chip Salzenberg) writes: >>In short, IT IS IMPOSSIBLE TO WRITE QSORT() ENTIRELY IN ANSI C OR IN C++ >>IN SUCH A WAY THAT IT IS COMPLETELY PORTABLE. >This statement is false. It is entirely possible to do so, thanks to >ANSI's guarantee that pointer-to-char and pointer-to-void will always >have identical representations. I think Chip is correct about C, but not necessarily about C++. Actually, qsort() itself can be written portably in C++, but it's hard to write most comparison functions portably. The problem is that C++ has restrictions on casting from void* into <type>*. So, you can pass the void* parameters to the comparison function, but it may not be able to do anything with them. -- Barry Margolin, Thinking Machines Corp. barmar@think.com {uunet,harvard}!think!barmar
warsaw@nlm.nih.gov (Barry A. Warsaw) (12/26/90)
barmar> The problem is that C++ has restrictions on casting from barmar> void* into <type>*. Specifically, what are these restrictions? barmar> -- Barry Margolin, Thinking Machines Corp. -Barry NAME: Barry A. Warsaw INET: warsaw@nlm.nih.gov TELE: (301) 496-1936 UUCP: uunet!nlm.nih.gov!warsaw
barmar@think.com (Barry Margolin) (12/27/90)
In article <WARSAW.90Dec26104259@warsaw.nlm.nih.gov> warsaw@nlm.nih.gov writes: > barmar> The problem is that C++ has restrictions on casting from > barmar> void* into <type>*. >Specifically, what are these restrictions? A week or so ago someone mentioned in this list that there is a problem such conversions and multiple inheritance. However, I can't find any mention of it in the "C++ Primer". I think the problem he described was when a class D is derived from B1 and B2, and you have the following declarations: B1* b1p; B2* b2p; D* dp; void* vp; vp = (void*) dp;// OK, explicit cast is optional dp = (D*) vp; // OK, requires explicit cast b1p = (B1*) vp; // ?? b2p = (B2*) vp; // ?? One of the last two conversions is questionable because it requires the pointer to be offset to the beginning of the appropriate base portion of the object. However, the offset depends on the actual type of the object that vp is pointing to. Casting back to the type from which the void* was cast is easy, but casting to a base class effectively requires a virtual function call, and it's not clear that this is done automatically. This comes up because the comparison function may be designed to compare objects of a base class, so it will presumably first cast its void* argument to a <base>* and then do whatever it does. Actually, there *is* a solution. The routine that casts to void* (the caller of the qsort-like function) can first cast to the appropriate <base>*, e.g. vp = (void*) ((B1*) dp); b1p = (B1*) vp; This works because C++ always knows how to convert a derived pointer to any of its base class pointers. However, it's really inconvenient for the kinds of functions we're discussing (qsort() and bsearch()) because it doesn't allow arrays/trees to be operated on in place; the caller must build a second array/tree containing void* pointers whose values come from the above double cast, pass this to the function, and then cast the results back to the original types. -- Barry Margolin, Thinking Machines Corp. barmar@think.com {uunet,harvard}!think!barmar