CODEWITHSUNDEEP
cpointersstructcastingqsort
abcxyz
abcxyz

Reputation: 147

qsort() and casting operation

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;

Upvotes: 2

Views: 512

Answers (4)

AnT stands with Russia
AnT stands with Russia

Reputation: 320531

The comparison function receives pointers to array elements. If your array contains elements of some type T, then your comparison function will receive const void * pointers that should be interpreted as const T * pointers.

In your case T is equal to struct mystruct * (since your array contains pointers). In that case const T * is equivalent to struct mystruct * const*, which is exactly what you see in your code.

In order to make your code easier to understand you can actually literally introduce a typedef name T into the function and split your conversions/dereferences into separate individual steps

int myptrstructcmp(const void *p1, const void *p2)
{
  typedef mystruct *T;             // array elements are pointers
  const T *pel1 = p1, *pel2 = p2;  // pointers to array elements
  T sp1 = *pe1, sp2 = *pe2;        // values of array elemnts

This is equivalent to what you have in the original code;

Upvotes: 1

koan911
koan911

Reputation: 370

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.

Upvotes: 3

Jonathan Leffler
Jonathan Leffler

Reputation: 753970

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().

Upvotes: 4

alk
alk

Reputation: 70931

From man qsort:

[...] comparison function [..] which is called with two arguments that point to the objects being compared.

"the objects being compared" are the elements of the array passed to qsort() and as this array to be sorted holds pointers the comparsion function receives pointer to pointer as arguments.

To get the array's elements from the arguments passed to the comparsion function those arguments need to be de-referenced though.

Upvotes: 2

Related Questions