Casting pointers to void to pointers to pointers to type A and dereferencing vs. Casting pointers to void to type A: Why?

Question

I am just starting to learn C. Any help is appreciated!

I have an array of pointers to a struct, and I want to use the built-in qsort function to sort the array according to values in the structs the pointers point to. I am trying to use a compare function as demonstrated in the official docs.

The following version fails:

int compare_nodes(const void* a, const void* b){
    const struct ListNode * ptr1 = ((const struct ListNode *) a);
    const struct ListNode * ptr2 = ((const struct ListNode *) b);
    // const struct ListNode * ptr1 = *((const struct ListNode **) a);
    // const struct ListNode * ptr2 = *((const struct ListNode **) b);
    int arg1 = ptr1 -> val;
    int arg2 = ptr2 -> val;

    if(arg1 < arg2) return -1;
    if(arg1 > arg2) return 1;
    return 0;
}

This version succeeds:

    int compare_nodes(const void* a, const void* b){
    // const struct ListNode * ptr1 = ((const struct ListNode *) a);
    // const struct ListNode * ptr2 = ((const struct ListNode *) b);
    const struct ListNode * ptr1 = *((const struct ListNode **) a);
    const struct ListNode * ptr2 = *((const struct ListNode **) b);
    int arg1 = ptr1 -> val;
    int arg2 = ptr2 -> val;

    if(arg1 < arg2) return -1;
    if(arg1 > arg2) return 1;
    return 0;
}

I do not understand the difference between the two versions:

1. If casting only tells the compiler how to interpret the address the pointer points to, what is the problem in version 1? Is it not enough to tell the compiler to interpret the pointer to void as a pointer to struct ListNode? Why do I need to add a layer of indirection with casting, just to then remove one layer with dereferencing?
2. Does C's pass-by-value play any role here? I could not think of any reason why by myself.

I found the following resources about this question. Although they seemed to explain this problem (especially resource 6), I did not understand them:

1. What are the rules for casting pointers in C?

2. Typecasting of pointers in C

3. Pointer type casting and dereferencing

4. What are the rules for casting pointers in C?

5. What does a C cast really do?

6. https://cboard.cprogramming.com/c-programming/102056-casting-pointer-pointer.html

Here's the full code:

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


struct ListNode {
    int val;
    struct ListNode *next;
};

int calc_list_length(struct ListNode * head){
    int target = 0;
    struct ListNode * tmp = head;

    while (tmp)
    {
        target++;
        tmp = tmp -> next;
    }
    
    return target;
}

int compare_nodes(const void* a, const void* b){
    // const struct ListNode * ptr1 = ((const struct ListNode *) a);
    // const struct ListNode * ptr2 = ((const struct ListNode *) b);
    const struct ListNode * ptr1 = *((const struct ListNode **) a);
    const struct ListNode * ptr2 = *((const struct ListNode **) b);
    int arg1 = ptr1 -> val;
    int arg2 = ptr2 -> val;

    if(arg1 < arg2) return -1;
    if(arg1 > arg2) return 1;
    return 0;
}

struct ListNode* sortList(struct ListNode* head){
    if(!head) return NULL;

    int list_length = calc_list_length(head);
    struct ListNode * tmp = head;

    struct ListNode * arr[list_length];
    for (int i = 0; i < list_length; i++)
    {
        arr[i] = tmp;
        tmp = tmp -> next;
    }

    for (int i = 0; i < list_length; i++) {
        printf("%d ", arr[i] -> val);
    }
    printf("\n");
    
    qsort(arr, list_length, sizeof(struct ListNode *), compare_nodes);

    for (int i = 0; i < list_length; i++) {
        printf("%d ", arr[i] -> val);
    }
    printf("\n");
}

int main(){
    // [2,1,4,3]
    struct ListNode node4 = {.val = 3, . next = NULL};
    struct ListNode * ptr4 = &node4;

    struct ListNode node3 = {.val = 4, .next = ptr4};
    struct ListNode * ptr3 = &node3;

    struct ListNode node2 = {.val = 1, .next = ptr3};
    struct ListNode * ptr2 = &node2;

    struct ListNode node1 = {.val = 2, .next = ptr2};
    struct ListNode * ptr1 = &node1;

    sortList(ptr1);

    getchar();
    return 0;    
}

Thanks in advance. I hope you point me in the right direction.

Answer 1

The qsort passes pointers to the array elements using the pointer-to operator &.

So it can pass, for example, &arr[0] and &arr[1] as arguments to your comparison function.

Since arr is an array of pointers, where every element is a pointer, then a pointer to one element must by definition be a pointer to a pointer.

So the arguments passed to your compare_nodes structure are pointers to pointers to ListNode structures.

Answer 2

The function qsort is declared like

void qsort(void *base, size_t nmemb, size_t size, 
           int (*compar)(const void *, const void *));

That is the function deals with pointers of the type void *. It passes to the comparison function two pointers of the type const void * that point to elements of the underlying array.

You declared an array of pointers

struct ListNode * arr[list_length];

Its elements of the type ListNode * are passed to the comparison function by reference through pointers to them.

In fact the function passes to the comparison function pointers of the type ListNode ** that are passed as pointers of the type const void *. You may imagine this the following way

const void *p = &arr[i];

where the expression &arr[i] has the type ListNode **.

Of course the function qsort actually does not know the actual type of elements of the array. It uses the following pointer arithmetic

const void *p = ( char * )base + i * size;

Thus within the comparison function you need to do the "reverse" casting like

const struct ListNode * ptr1 = *((const struct ListNode **) a);

where ptr1 is an element of the original array that is passed to the comparison function by reference trough a pointer to it..

Answer 3

The fact that the qsort() function passes pointers to the array elements to your comparator function, rather than passing the array elements directly by value, is due to how qsort() was designed, and is not required by the core C language itself.

I can easily write a sorting function that sorts an array of pointers, with the following signature:

void my_sort_pointers(const void **array, size_t nmemb, 
                      int (*compar)(const void *, const void *));

and it accepts a comparator function that is passed the array elements (the pointers) directly. Then your comparator function would not have to dereference the argument to get the actual values to be compared.

However, my sorting function above would not be able to sort, say, an array of floats, because it would not be able to pass two float arguments to a comparator function that is supposed to take two pointers. Even if you made a comparator function that took two floats, you would not be able to pass it to the function above, because the function pointer types are incompatible, and even if you somehow casted the type, it would still not work because the C code inside the function, which thinks it is calling a function that takes two pointers, cannot call a function that actually takes two floats, because the function signatures are incompatible.

So to be able to sort arrays of different types under this design, I would have to have another sorting function that sorts an array of floats:

void my_sort_floats(float *base, size_t nmemb, 
                    int (*compar)(float, float));

and another sorting function that sorts an array of ints, etc. And since there can be an unlimited types of structs, with different sizes, you can never make functions that can handle all of them. Even if only basic types are supported, it would require several different functions. The designers of the C standard library decided that it would be a better design to make a single sorting function that works for all types, by passing a pointer to the array element to the comparator functon instead.

This design makes a lot of sense when you understand the limitations of C. (In C++, it would be possible to use generics to write a generic sorting function that works for any type, and has a comparator that is passed the array elements by value. But C doesn't have generics.) But it is a design decision of the qsort() function API nevertheless, and sorting functions in C (at least if they only accept a particular type) do not necessarily have to work this way. So you would only know that qsort() is supposed to be used in this way by reading the specification of qsort().