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.

CodePudding user response：

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.

CodePudding user response：

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