From: hansen@pegasus.att.com (Tony L. Hansen)
Subject: Re: Making qsort type-safe
Organization: AT&T
Date: Thu, 12 Nov 1992 19:42:07 GMT
Summary: it can be done, almost
Keywords: sorting, templates, qsort

< From: sdm@cs.brown.edu (Scott Meyers)
< ...
< So I thought of doing this:
<
<     template<class T>
<     inline
<     void safeQSort(T array[], int arraySize,
<                    int (*cmp)(const T *val1, const T *val2)) 
<     {
<         qsort(array, arraySize, sizeof(T), cmp);
<     }
< 
< However, this fails to compile, because the function pointer in safeQSort
< isn't type-compatible with the one in qsort.  That is, there is no
< automatic conversion from
< 
<     int (*)(const T*, const T*)
< 
< to
< 
<     int (*)(const void*, const void*)
< 
< I pacified the compiler with a cast:
< 
<     typedef int (*CMP)(const void*, const void*);
< 
<     template<class T>
<     inline
<     void safeQSort(T array[], int arraySize,
<                    int (*cmp)(const T *val1, const T *val2)) 
<     {
<         qsort(array, arraySize, sizeof(T), (CMP) cmp);
<     }
< 
< But casts make me queasy, especially so after the mail I got telling me
< about bit pattern conversions when types change.  So -- is this a safe
< thing to do, or does the devil lurk within?

Same trap. Consider a machine with the following bit pattern scenarios:

	A void* takes up 34 bits, encapsulated in a 64-bit quantity.

	However, a long* takes up 32 bits.

	When a void* gets converted to a long*, it's shifted right 2 bits
	and the top 4 bytes lopped off. When a long* gets converted to a
	void*, 4 bytes get added to the top and it's all shifted left 2
	bits.

Now, consider what happens when sorting an array of longs, with the
following comparison function:

	int lcmp(const long *a, const long *b)
	{ return *a - *b; }

When lcmp is invoked in your example above. The bit pattern passed to cmp
on the stack will be

	+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
	|    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |
	|    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |    |
	+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
	
	<---------------- a+0 -----------------> <---------------- a+1 ----------------->

But lcmp is only expecting 4 bytes per address, or

	+----+----+----+----+----+----+----+----+
	|    |    |    |    |    |    |    |    |
	|    |    |    |    |    |    |    |    |
	+----+----+----+----+----+----+----+----+
	
	<------ a+0 -------> <------ a+1 ------->

In other words, the address associated with the first pointer will be
interpretted as the two separate addresses.

The same trap as before is involved: an implicit type conversion has
occurred via the stack without going through an explicit cast.

Sorry.

By the way, here's a completely typesafe safeQsort(). It uses a template
helper class.

----------------------------------------------------------------
#include <stdlib.h>
#include <iostream.h>

// template helper class
template <class T>
class safecmpclass
{
public:
    static int cmp(const void*, const void*);
};

// invoke the proper op< for the values
template <class T>
int safecmpclass<T>::cmp(const void *pa, const void *pb)
{
    const T *a = (const T*)pa;
    const T *b = (const T*)pb;
    return (*a < *b) ? -1 :
	   (*b < *a) ? 1 : 0;
}

// the safe qsort() function
template<class T>
void safeQSort(T array[], int arraySize)
{
    qsort(array, arraySize, sizeof(T), safecmpclass<T>::cmp);
}

// test it out
main()
{
    // 30 random numbers
    static long foo[30] = {
	30639, 31938, 2675, 6031, 18500, 8736, 32276, 2499, 28250, 29533,
	8213, 30663, 15787, 19914, 1511, 25501, 26627, 6526, 14472, 25778,
	12134, 3604, 16527, 28926, 3841, 1833, 26361, 7136, 1745, 9364
    };

    // sort it
    safeQSort(foo, 30);

    // print out the sorted array
    for (int i = 0; i < 30; i++)
	cout << "foo[" << i << "] = " << foo[i] << "\n";
    return 0;
}
----------------------------------------------------------------

Is that the end of the story, though? No, of course not, because just
swapping the bits around may not be sufficient to swap a[0] and a[1]. They
may truly have to be swapped using assignments, and qsort provides no way to
do that.

The bottom line is that trying to use the C function qsort() to implement a
true qsort will always lead to a problem. However, if you limit yourself to
using it only with simple structures, you can do it.

					Tony Hansen
			    hansen@pegasus.att.com, tony@attmail.com
				att!pegasus!hansen, attmail!tony
Newsgroups: comp.lang.c++