mat@mole-end.UUCP (Mark A Terribile) (01/03/91)
> >Both qsort() and bsearch() require a pointer to a function which [takes] > >two parameters of type pointer-to-void. ... that the function ... will > >almost immediately cast [them to] pointer-to-T is utterly irrelevant. > ... It is always possible to cast a pointer to anything to a pointer > to void. But it is not guaranteed that you can cast a pointer to > void back to its original. ... Eh? So long as it's not a pointer-to-function, it sure is guaranteed possible, or I'm a monkey's uncle. (Which I ain't. So there.) > >Remember that qsort() cannot know the real type of the objects it is > >sorting. > Again I agree with Ron. qsort/bsearch should be templated functions. > Better yet they should be member functions embedded in some kind of > container class. I think that we've been railroaded up a type system branch line and out onto a siding with no end-of-track warning and no bumber. Fust of all, the ``array'' 'pon which qsort() and it's ilk work must be a true homogeneous array. In other words, everything's gotta be the same size so the exchanges will work and everything's gotta have enough the same structure that the comparison functions will work. This may mean that qsort() or its buddies is to be given an array of pointers. Second, the real conflict isn't between void* and XYZ* and it has nothing to do with MI. NOTHING, NOTHING, NOTHING, NOTHING. NO THING. NOT A THING IN THIS WORLD. NOTHING. The MI problem occurs when you have pointers that are stored as derived* and interpreted as base* . That problem *COULD* occur here, but it's not an essential part of the problem. In other words, it's a herring that has gone beyond red and is well on its way to scarlet. The problem is that qsort() wants to use a generic pointer ( void* ) to address its `stuff' and so it wants to call a compare function that looks like int compare( void*, void* ) while the function will necessarily be of type int compare( const Stuff*, const Stuff* ) (or const Stuff**, const Stuff** , or whatever). Thus, qsort takes (or SHOULD take) as a parameter an argument of the form int (*cmpr_fun)( void*, void* ) and we want to pass it an argument of the form int (*cmpr_fun)( const Stuff*, const Stuff* ) This means that we must coerce (by cast) a pointer-to-function of one type to the type of the other pointer-to-function. I want to believe that this is harmless; I am inclined to believe that on most machines it is, so long as we supply the compare function and it knows what of what Stuff we are asking qsort() to speak. (What if it's not harmless? More a little later ...) What is probably DISASTROUS is to use the ellipsis in declaring qsort() . If qsort() 's argument is of the form int (*cmpr_fun)( ... ) the function may get called (and under some MS-DOS compilers, *WILL* get called) with an entirely different calling sequence, such that the function will misunderstand its arguments and even its call/return sequence. What compilers and why? The Glockenspiel port of cfront , at least, and because ordinary member functions of fixed signature can be called using the Pascal calling sequence, which is smaller and faster than the C calling sequence (because the size of the argument list to be released in the Pascal calling sequence is known definitely to the callED function, which can specify in the return statement that the stack is to be so adjusted--and this is not possible in the C calling sequence, in which the callING function must strip the arguments). (Unfortunately, if the Pascal calling sequence is used, the function is marked as Pascal in the object file and the frotzenglarken linker insists on ignoring case when comparing function names.) In other words, Sun Microsystems has indeed made a horrible mistake. You've just got to trust the user to pun the types correctly here, at least until we get a better solution. The ellipsis is dead wrong. Once again, for those who came late: The ellipsis in the prototype of the compare function pointer in the prototype for qsort() (or any other generic sorting or searching function) is ABSOLUTELY, POSITIVELY, IRRETREVIEVABLY, D-E-A-D DEAD WRONG. But isn't this a matter for the ANSI committee, as well as for Sun? I wish them well, I sure do ... Templates can provide a better solution, provided that it's not necessary to either (a) compile in a whole new version of the qsort() code for each type to be handled, or (b) introduce additional out-of-line function calls into each internal step of the sort. But templates don't answer the problem completely. What happens if you have something like a database engine that has to handle whatever types and sizes are thrown at it without recompilation? Then you need the flexibility provided by the current qsort() . There's another problem, and a it's real killer. What if void* is different in size and even in how (e.g., in what register or stack) it must be passed from Stuff* ? Then you CAN'T pass an int (*cmpr_fun)( const Stuff*, const Stuff* ) to qsort() (which, remember, wants an int (*cmpr_fun)( void*, void* ) . This means that if your compare function is int strcmp( const char*, const char* ) , you really DO have to wrap it in a function like int str_as_void_cmp( const void* s1, const void* s2 ) { return strcmp( (const char*) s1, (const char*) s2 ); } Furthermore, it won't do any good to declare it inline, because a REAL pointer and REAL operations are needed. Again, templates can help. It would also be nice (and may become important in the world of C++ and templates) if global optimizers realized that all F() does is call G() with exactly the same (to the machine) parameters, and replace the call to F() outright with the call to G() . This requires optimization AFTER symbol resolution but before relocation--in other words, optimization BETWEEN THE LINKING PHASES. Such may be a real need in C++ with templates. Of course, if the function F() is declared inline, the code generator has information sufficient to perform the optimization, IF its optimizer can make use of the information. Again, it may become important to do so soon. (Instead of removing the call to F() , it may be possible to turn F() into a jump into a point inside G() and perhaps just after G()'s prologue--if the appropriate label is available.) Such optimization would allow us to write the `correct' code (correct in that we explicitly type-pun and take responsibility for the consequences) while allowing the code to run without extra cost on machines on which that is indeed possible. -- (This man's opinions are his own.) From mole-end Mark Terribile
rfg@NCD.COM (Ron Guilmette) (01/13/91)
In article <465@mole-end.UUCP> mat@mole-end.UUCP (Mark A Terribile) writes:
+> >Both qsort() and bsearch() require a pointer to a function which [takes]
+> >two parameters of type pointer-to-void. ... that the function ... will
+> >almost immediately cast [them to] pointer-to-T is utterly irrelevant.
+
...
+Second, the real conflict isn't between void* and XYZ* and it has nothing
+to do with MI. NOTHING, NOTHING, NOTHING, NOTHING. NO THING. NOT A THING IN
+THIS WORLD. NOTHING. The MI problem occurs when you have pointers that are
+stored as derived* and interpreted as base* . That problem *COULD* occur
+here, but it's not an essential part of the problem. In other words, it's a
+herring that has gone beyond red and is well on its way to scarlet.
As you say, that problem can occur in the context under discussion, and
I think that it is a real problem and not a red herring.
+What is probably DISASTROUS is to use the ellipsis in declaring qsort() .
+If qsort() 's argument is of the form int (*cmpr_fun)( ... ) the function
+may get called (and under some MS-DOS compilers, *WILL* get called) with an
+entirely different calling sequence, such that the function will misunderstand
+its arguments and even its call/return sequence.
...
+In other words, Sun Microsystems has indeed made a horrible mistake.
OK. We are in agreement about that. Doug L. ? Where are you where we need
you?
Will this be fixed in a future release?
+Templates can provide a better solution...
Again, we agree.
+But templates don't answer the problem completely. What happens if you
+have something like a database engine that has to handle whatever types and
+sizes are thrown at it without recompilation? ...
Perhaps such things are bad candidates for being coded in a quasi-
strongly-typed language like C++.
--
// Ron Guilmette - C++ Entomologist
// Internet: rfg@ncd.com uucp: ...uunet!lupine!rfg
// Motto: If it sticks, force it. If it breaks, it needed replacing anyway.