Double pointer indirection when passing an array to a function

Question

I wanted to brush up on my knowledge of algorithms and I've been using the following book: Algorithms in a nutshell

At page 65 they print an algorithm for insertion sort. The algorithm is pretty simple and straightforward to understand. My issue comes from the way they implemented it. I work mostly in managed languages (C#/Java) so my pointer kung fu is kinda rusty. Here is the code sample they provide:

void sortPointers(void **ar, int n, int(*cmp)(const void *, const void *)) {
    int j;
    for(j = 1; j < n; j++) {
        int i = j - 1;
        void* value = ar[j];

        while(i >= 0 && cmp(ar[i], value) > 0) {
            ar[i+1] = ar[i];
            i--;
        }

        ar[i+1] = value;
    }
}

Here is what I added to have a working example:

int cmp(const void* t1, const void* t2) {
    if(t1 > t2) {
        return 1;
    }
    else if(t2 > t1) {
        return -1;
    }
    else {
        return 0;
    }
}

void main() {
    int values[] = { 51, 3, 5, 60, 9, 2, 7};

    sortPointers((void**)values, 7, cmp);

    for(int i = 0; i < 7; i++) {
        cout << values[i] <<  " ";
    }
}

While this works I do not completely understand why and how? Also, why does the (void **) cast in the main function work, why did they use a double pointer indirection etc.?

Back in school the only place we used multiple indirection was when dynamically allocating multidimensional arrays. The only other use I know of, is when you need to be able to modify the address the pointer you are passing to the method holds.

Furthermore I went ahead and modified the code to look like this and it works just fine:

void sortPointers2(int* arr, int n, int (*cmp)(int, int)) {
    int j;
    for(j = 1; j < n; j++) {
        int i = j - 1;
        int value = arr[j];

        while(i >= 0 && cmp(arr[i], value) > 0) { 
            arr[i+1] = arr[i];
            i--;
        }

        arr[i+1] = value;
    }
}

int cmp2(int t1, int t2) {
    if(t1 > t2) {
        return 1;
    }
    else if(t2 > t1) {
        return -1;
    }
    else {
        return 0;
    }
}

void main() {
    int values[] = { 51, 3, 5, 60, 9, 2, 7};

    sortPointers2(values, 7, cmp2);

    for(int i = 0; i < 7; i++) {
        cout << values[i] <<  " ";
    }
}

I'm pretty sure I am missing something fundamental and obvious. Thank you for anybody reading this and chipping in with an idea or two. Let me know if you need any additional details or if I messed up the terminology.

EDIT: fixed typo in the first cmp function

Answer 1

If I'm following the example correctly, they use a void ** because it is really a (void *)[]; an array of untyped memory. The compare function is given two pointers to untyped memory (void *), and is asked to compare the data.

What you don't understand is that in the first example, your array should be an array of pointers, not an array of values. Your array should look like:

int *val0 = malloc(sizeof(int)); *val0 = 51;
int *val1 = malloc(sizeof(int)); *val1 = 3;
// ... for all values
int *values[] = { val0, val1, val2, ... };

Then the compare function cmp needs to return a comparison value based on the values, not the pointers that it is given. Code:

int cmp(const void* t1, const void* t2) {
    if((const int)(*t1) > (const int)(*t2)) {
        return 1;
    }
    else if((const int)(*t2) > (const int)(*t1)) {
        return -1;
    }
    else {
        return 0;
    }
}

This way, given pointers to untyped memory, your compare function would find the two integers at those pointers, and compare those values.

The only reason your cmp function worked with the book's code is because you were telling the sorting function that your array was full of pointers to untyped memory, when it was really just an array of integers. Your comparison function would then be given pointers to memory, which were really just integers, and then compare the pointers as if they were values. In this case, they were.

The reason the book's algorithm uses a void ** is because that way it is generic. The sort function can take an array holding any data at all, and give the generic data to the compare function, which can dereference the pointers and interpret the data at those addresses however it wishes.