What are the parameters in this C qsort function call?

Question

qsort(bt->rw[t], bt->num[t], 
      sizeof(TRELLIS_ATOM *), 
      (int (*)(const void *,const void *))compare_wid);

bt->rw[t] is a pointer to struct pointer, bt->[num] is an int, I don't understand what that fourth parameter is, except that compare_wid is a function defined somewhere as follows:

static int compare_wid( TRELLIS_ATOM* a, TRELLIS_ATOM* b )
{
   ...
   return x;
}

Answer 1

I will get to the meaning of the line in a bit, but before I do that, let's get some of the basics of why qsort() needs its final parameter of the type it needs. qsort() is a function that can sort any type of data.

You provide it with:

• a base pointer, which points to the start of a contiguous block of data,
• the number of elements in the block,
• the size of one data member, and
• a function that compares two data values.

Since a sorting algorithm in general doesn't depend upon the type of the data being sorted, qsort() can be written without the knowledge of what data types it is sorting. But to be able to do that, qsort() takes void * parameters, which means "generic pointer" in C.

Let's say you have an array of unsorted int values:

#define N 1024
int data[N] = { 10, 2, 3, -1, ... } /* 1024 values */

Then you can sort them by calling qsort():

qsort(data, N, sizeof data[0], compare_int);

data is of type int * when passed to qsort(), and the first parameter of qsort() is of type void *. Since any object pointer can be converted to void * in C, this is OK. The next two arguments are okay too. The final argument, compare_int, should be a function that takes two const void * parameters and returns an int. The function will be called by qsort() with pairs of pointers from &data[0] to &data[N-1] as many times as it needs.

To declare a function f() that "takes two const void * parameters and returns int":

int f(const void *, const void *);

If one wants to declare a function pointer that we can set to f, the pointer is declared as:

int (*pf)(const void *, const void *);
pf = f;

The parentheses are required, because otherwise pf would be a function returning an int *. Now, pf is a pointer to a function returning int.

Getting back to our int sorting algorithm, and from the above, we could define compare_int() as:

int compare_int(const void *a, const void *b)
{
    const int *the_a = a;
    const int *the_b = b;
    if (*the_a > *the_b) return 1;
    else if (*the_a < *the_b) return -1;
    else return 0;
}

While writing compare_int(), we know that the pointers passed are int * disguised as void *, so we convert them back to int *, which is OK, and then we compare the numbers.

Now, we turn our attention to the code in question:

static int compare_wid( TRELLIS_ATOM* a, TRELLIS_ATOM* b )

means that compare_wid is a function that takes two TRELLIS_ATOM * parameters, and returns an int. As we just saw, the last argument to qsort() should be a function that is of type:

int (*)(const void *, const void *)

I.e., a function taking two const void * parameters and returning int. Since the types don't match, the programmer cast compare_wid() to the type required by qsort().

However, this has problems. A function of type:

int (*)(TRELLIS_ATOM *, TRELLIS_ATOM *)

is not equivalent to a function of type:

int (*)(const void *, const void *)

so it's not guaranteed if the cast will work. It is much more easier, correct, and standard to declare compare_wid() as:

static int compare_wid(const void *a, const void *b);

And the definition of compare_wid() should look like:

static int compare_wid(const void *a, const void *b)
{
    const TRELLIS_ATOM *the_a = a;
    const TRELLIS_ATOM *the_b = b;
    ...
    /* Now do what you have to do to compare the_a and the_b */
    return x;
}

If you do that, you won't need the cast in the call to qsort(), and your program will not only be easier to read, but also correct.

If you can't change compare_wid(), then write another function:

static int compare_stub(const void *a, const void *b)
{
    return compare_wid(a, b);
}

and call qsort() with compare_stub() (without the cast) instead of compare_wid().

Edit: Based upon many of the wrong answers, here is a test program:

$ cat qs.c
#include <stdio.h>
#include <stdlib.h>

struct one_int {
    int num;
};

#ifdef WRONG
static int compare(const struct one_int *a, const struct one_int *b)
{
#else
static int compare(const void *a_, const void *b_)
{
    const struct one_int *a = a_;
    const struct one_int *b = b_;
#endif
    if (a->num > b->num) return 1;
    else if (a->num < b->num) return -1;
    else return 0;
}

int main(void)
{
    struct one_int data[] = {
        { 42 },
        { 1 },
        { 100 }
    };
    size_t n = sizeof data / sizeof data[0];

    qsort(data, n, sizeof data[0], compare);
    return 0;
}

Compiling with compare() defined as taking two const struct one_int * values:

$ gcc -DWRONG -ansi -pedantic -W -Wall qs.c
qs.c: In function `main':
qs.c:32: warning: passing argument 4 of `qsort' from incompatible pointer type

Compiling with the correct definition:

$ gcc -ansi -pedantic -W -Wall qs.c
$

Edit 2: There seems to be some confusion about the legality of using compare_wid as-it-is for the final argument to qsort(). The comp.lang.c FAQ, question 13.9 has a good explanation (emphasis mine):

To understand why the curious pointer conversions in a qsort comparison function are necessary (and why a cast of the function pointer when calling qsort can't help), it's useful to think about how qsort works. qsort doesn't know anything about the type or representation of the data being sorted: it just shuffles around little chunks of memory. (All it knows about the chunks is their size, which you specify in qsort's third argument.) To determine whether two chunks need swapping, qsort calls your comparison function. (To swap them, it uses the equivalent of memcpy.)

Since qsort deals in a generic way with chunks of memory of unknown type, it uses generic pointers (void *) to refer to them. When qsort calls your comparison function, it passes as arguments two generic pointers to the chunks to be compared. Since it passes generic pointers, your comparison function must accept generic pointers, and convert the pointers back to their appropriate type before manipulating them (i.e. before performing the comparison). A void pointer is not the same type as a structure pointer, and on some machines it may have a different size or representation (which is why these casts are required for correctness).

As mentioned in the FAQ, also see this.

Answer 2

(int (*)(const void *,const void *)) means "treat what follows as a pointer to a function that takes two parameters of type const void* and returns an int". compare_wid is indeed a function that can be treated this way.

qsort will call this function to perform comparisons between items when sorting: if the integer it returns is zero, the items are assumed to be equal, otherwise the sign of the integer is used to order them.