NetNews Usenet Archive 1992 #26/NN_1992_26.iso/spool/comp/lang/cplus/16173

Text File | 1992-11-12 | 4.9 KB | 160 lines

Newsgroups: comp.lang.c++
Path: sparky!uunet!charon.amdahl.com!pacbell.com!sgiblab!zaphod.mps.ohio-state.edu!pacific.mps.ohio-state.edu!linac!att!cbnewsk!pegasus!hansen
From: [e-mail] (Tony L. Hansen)
Subject: Re: Making qsort type-safe
Organization: AT&T
Date: Thu, 12 Nov 1992 19:42:07 GMT
Message-ID: <[e-mail]>
Summary: it can be done, almost
Keywords: sorting, templates, qsort
References: <[e-mail]>
Sender: [e-mail] (tony.l.hansen)
Lines: 146

< From: [e-mail] (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
                [e-mail], [e-mail]
                att!pegasus!hansen, attmail!tony