qsort() and casting operation

Question

Consider an array of pointers to structs. The following code is taken from an example you may find here. I'd like to get an explantation for those two rows of casting. I'm not familiar with this "double casting".

int myptrstructcmp(const void *p1, const void *p2)
{
    struct mystruct *sp1 = *(struct mystruct * const *)p1;
    struct mystruct *sp2 = *(struct mystruct * const *)p2;

I thought it should be:

int myptrstructcmp(const void *p1, const void *p2)
{
    struct mystruct *sp1 = (struct mystruct *)p1;
    struct mystruct *sp2 = (struct mystruct *)p2;

Answer 1

Suppose you were sorting an array of int. Your comparator would be passed a pair of int * disguised as void *; one level of indirection is added.

If you are sorting an array of struct mystruct *, your comparator is passed struct mystruct ** disguised as void *; one level of indirection is added.

What is the meaning of struct mystruct * const *? Without the const* it fails to cast correctly. Why?

Whaddya mean by 'without the const * it fails to cast correctly'? Without the const, it works OK. Without the second *, it doesn't work because the function is passed a struct mystruct ** (give or take some const-ness) and if you omit the second star, you are abusing the type system.

Consider:

struct mystruct
{
    int i;
};

int myptrstructcmp(const void *p1, const void *p2);
int myptrstructcmp(const void *p1, const void *p2)
{
    struct mystruct *sp1 = *(struct mystruct **)p1;
    struct mystruct *sp2 = *(struct mystruct **)p2;

    if (sp1->i < sp2->i)
        return -1;
    else if (sp1->i > sp2->i)
        return +1;
    else
        return 0;
}

This compiles fine. It also compiles fine when you add the const between the **. Personally, I'd not include the const in the casting. What I would do is const-qualify the sp1 and sp2 pointers:

    struct mystruct const *sp1 = *(struct mystruct **)p1;
    struct mystruct const *sp2 = *(struct mystruct **)p2;

or:

    const struct mystruct *sp1 = *(struct mystruct **)p1;
    const struct mystruct *sp2 = *(struct mystruct **)p2;

This promises not to modify the objects that they point at in the function, which is actually crucial to the correct performance of qsort().

Answer 2

Here's your clue — in the C FAQ you reference:

If, on the other hand, you're sorting pointers to structures, you'll need indirection,

You are sorting a list of pointers to structs. The pointers have to be juggled in the list by the sort, which means you are passing the pointers in the list by reference (via a pointer to a pointer) for comparison.