qsort type casting pointers in c-CodePudding

This is a simple code to practice qsort function in C.

int compareF(const void *a, const void *b) {
    // return (*(int**)a)[0] - (*(int**)b)[0];  
    const int *pr1 = *(const int **)a;
    const int *pr2 = *(const int **)b;
    return pr1[0] - pr2[0];
}

int main() {
    int *array[] = {(int[]){2,2,3}, (int[]){1,2,1},(int[]){1,3,3},(int[]){0,2,3},(int[]){1,2,0}};
    qsort(array, 5, sizeof(int[3]), compareF);
    for (int i = 0; i < 5; i  ) {
        for (int j = 0; j < 3; j  ) {
            printf("%d ", array[i][j]);
        }
        printf("\n");
    }
  return (0);
}

I don't grasp line 3 and 4 of why it is type-casted this way with pointers. This is my understanding. Firstly, it doesn't matter how we use syntax whether we set new variables to save parameters or not like those two return states are just same. Secondly, it needs to be type cased since parameters are void type so function does not know the type. First * is for dereferencing parameter a so that It has an access to the address a. And we use int** because..?

There's 2d integer array in main function. CompareF function only takes array[0] and array[1] as parameter each time in my understanding. So I don't get why it is typed cased with two **.

Same code with only one line of code modified

int array[3][2]= {{1,4},{3,6},{2,8}};

when array is defined this way, is type casting happened in same way?

const int *pr1 = *(const int[])a;
const int *pr2 = *(const int[])b;

const int *pr1 = (const int*)a;
const int *pr2 = (const int*)b;

First case doesn't work and second one does. But doesn't it need * to dereference? like

const int *pr1 = *(const int*)a;
const int *pr2 = *(const int*)b;

CodePudding user response：

For starters this call of qsort

qsort(array, 5, sizeof(int[2]), compareF);

is incorrect. The third parameter is the size of elements of the array. As the type of elements of the array is int * then the third parameter must be sizeof( int * ) or that is the same sizeof( *array )

qsort(array, 5, sizeof( *array ), compareF);

The function qsort passes pointers to elements of the array to the comparison function compareF as pointers of the type const void *.

As the elements if the array have the type int * then a pointer to an element of the array has the type int **.

So within the function compareF you need to cast the pointers of the type const void * to types const int **. Dereferencing such a pointer like

const int *pr1 = *(const int **)a;

you will get an element of the original array.

As the elements of the array point to first elements of compound literals that have the type int[3] then for example the expression pr1[0] within teh comparison function gives the first element of a compound literal, the expression pr1[1] gives the second element of the compound literal and so on.

In general using this return statement

return pr1[0] - pr2[0];

is incorrect because the supplied expression can produce an overflow for the signed integer type int.

It is more interesting to sort the elements (pointers to first elements of compound literals) of the original array comparing all elements of compound literals.

Here is a demonstration program.

#include <stdio.h>
#include <stdlib.h>

enum { M = 3 };

int compareF( const void *a, const void *b ) 
{
    const int *pr1 = *( const int ** )a;
    const int *pr2 = *( const int ** )b;
    
    size_t i = 0;
    while ( i != M && pr1[i] == pr2[i] )   i;
    
    return i == M ? 0 : ( pr2[i] < pr1[i] ) - ( pr1[i] < pr2[i] );
}

int main(void) 
{
    int * array[] = 
    {
        (int[M]){2,2,3}, 
        (int[M]){1,2,1},
        (int[M]){1,3,3},
        (int[M]){0,2,3},
        (int[M]){1,2,0}
    };
    
    const size_t N = sizeof( array ) / sizeof( *array );
    
    qsort( array, N, sizeof( *array ), compareF );
    
    for ( size_t i = 0; i < N; i   )
    {
        for ( size_t j = 0; j < M; j   )
        {
            printf( "%d ", array[i][j] );
        }
        
        putchar( '\n' );
    }
}

The program output is

As you can see if first elements of two compound literals are equal each other then second elements are compared and so on.

CodePudding user response：

The compare function passed to qsort is called anytime any two array elements are to be compared, and it is taking the address of each of those array elements.

You have an array of int * that is being sorted, so the address of each of those elements has type int **. That matches the type that the parameters of compareF are casted to. Dereferencing those pointers then gives us a value of type int * which is what is actually contained in the array.

Also, the third parameter to qsort is not correct. The array elements do not have type int[2] but instead have type int *. If an int is 4 bytes and a pointer is 8 bytes then they happen to be the same, but you can't depend on that.