Re: Pointer initialization.

From: Chris Torek (nospam_at_torek.net)
Date: 05/23/04 

Date: 23 May 2004 16:29:47 GMT

>In article <40B0AC33.E2CD86BA@cast-com.net>
> "Stephen L." <sdlnospamar@cast-com.net> wrote:
>> Are you saying that `sizeof (AUX_RGBImageRec *) != sizeof (void *)'?

Possibly, yes.

>> So, `AUX_RGBImageRec *' could _never_ be used inside the
>> compare function of `qsort(3C)' since its pointer size may
>> be different than the size of a `void *'?!!!

In article <news:christian.bau-66F5C6.16485323052004@slb-newsm1.svr.pol.co.uk>
Christian Bau <christian.bau@cbau.freeserve.co.uk> writes:
>When you pass a pointer to qsort, you cast it to void*. Same thing as
>when you pass a short to a function that has a long argument.

Indeed. It might be worth expanding on this, though.

Suppose you have a qsort-callable function:

    /* compare left- and right-side "zorg"s */
    int zorgcompare(const void *l0, const void *r0) {
        const struct zorg *l = l0; /* to sort an array of "zorg"s */
        const struct zorg *r = r0; /* if array of ptrs, make these "**" */
        ... code to compare them ...
        return whatever;
    }

Now let us also suppose you have an unusual machine in which "struct
zorg *" is (say) four bytes long, but "void *" is 1048576 bytes
long (one megabyte). (Outrageous? Perhaps, but "Exaggeration of
System Parameters" is quite a good way of figuring out whether
something will break under stress. Apply a little ESP in your
daily life as an engineer or programmer!) When you call qsort()
to sort an array of "struct zorg" you do this:

    struct zorg the_array[N];
    ... fill in the_array[i] ...
    /*
     * The "void *" conversion happens even without the cast, and
     * normally I suggest leaving it out, but it is here to show
     * the explicit conversion. The value of n here is in [0..N),
     * i.e., no more than the upper limit N.
     */
    qsort((void *)&the_array[0], n, sizeof(struct zorg), zorgcompare);

Or, if zorgcompare() uses "const struct zorg **", you do this:

    struct zorg *the_array[N];
    ... set up the_array[i], where i is in [0..n) and n <= N ...
    ... fill in the_array[i][0] (typically via the_array[i]->field
        rather than the_array[i][0].field) ...
    qsort((void *)&the_array[0], n, sizeof(struct zorg *), zorgcompare);

In each case, you take a four-byte "struct zorg *" or "struct zorg **"
and convert it to one of these 1-megabyte-wide "void *"s.

Clearly, four bytes fit within a million.

Now qsort() does its thing, no doubt using "const char *" internally
because arithmetic is forbidden on "void *" pointers, on the bytes
that make up "the_array". As qsort() comes up with pointers pointing
to (each first byte of) the_array[i], it passes them, in "void *"
format -- one megabyte each -- to zorgcompare().

It is zorgcompare()'s job to extract the four *useful* bytes out
of the one-million, and use those to compare the desired "zorg"s.
Clearly, if the four bytes have a well-defined location within the
megabyte, the compiler will be able to pluck them out and use them.

In other words, it all works, despite the fact that, on this odd
machine, "void *" is ENORMOUS compared to other pointer types.

"But isn't this inefficient?" Yes, it is horrendously inefficient,
which is why real machines never use one-megabyte "void *" pointers.
You can trust the folks who write compilers to figure out some way
to make "void *" reasonably efficient on your machine. Obviously
"one megabyte" is not required, and chances are "four bytes" will
do the trick just fine, and parameter-passing will be efficient.

But if you have a sufficiently oddball machine, "void *" really
MIGHT be slightly less efficient than "struct zorg *" -- and if
your compiler writers are not supremely clever, AND you have this
weird kind of computer, AND "void *" parameter passing is noticeably
slow, AND all the parameter-passing involved in qsort() is making
your program run unacceptably slowly -- well, if all of these
amazing coincidences *all* turn out to be the case at once, *then*
you might want to use something other than qsort() and its
"void *"s. Until that proves to be the case, though, you might as
well just write the clearest, simplest code you can. Chances are,
any problems you run into will not have anything to do with
"void *" being inefficient. 

-- 
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W)  +1 801 277 2603
email: forget about it   http://web.torek.net/torek/index.html
Reading email is like searching for food in the garbage, thanks to spammers.

Relevant Pages

  • Re: Can I Trust Pointer Arithmetic In Re-Allocated Memory?
    ... You can't do pointer arithmetic on a void* value. ... qsort behaves in a manner consistent with its specification. ... actually works as advertised...but doesn't mean that the cast is ...
    (comp.lang.c)
  • Re: qsort semantics
    ... The description of the qsort function says that I ... int cmp(const void *a, const void *b) { ... You cast a to "pointer to an array of N char". ...
    (comp.lang.c)
  • Re: sort array
    ... use any casts, and I get rid of the slightly silly (myBool? ... > conversions of pointers through pointer to void from pointer to type ... 'compare' is a poor name for a 'qsort' comparison function. ...
    (alt.comp.lang.learn.c-cpp)
  • Re: smuggling data in and out of alarm handlers and the like
    ... alarm handlers or the compare function used by qsort. ... use global variables. ... static int realCompare(const void *p, const void *q, ...
    (comp.lang.c)
  • Re: How do you track type information when converting int* to void*
    ... Often a function doesn't need to know anything about the type pointed to, so using void* allows one function to work on many types. ... The best example is probably qsort(), where the comparison function gets a void*. ... of the pointer, ...
    (comp.lang.c)