这个C qsort函数调用中的参数是什么？

Question

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

bt->rw[t]是一个指向结构指针指针，bt->[num]是一个int，我不知道第四个参数是什么，除了compare_wid是一个定义如下的函数：

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

Answer 1

(int (*)(const void *,const void *))的意思是“将后面的内容视为指向一个函数的指针，该函数接受两个类型为const void*的参数并返回一个int”。compare_wid确实是一个可以这样处理的函数。

排序时，qsort将调用此函数来执行项之间的比较:如果它返回的整数为零，则假定项相等，否则使用整数的符号对它们进行排序。

Answer 2

稍后我将解释这一行的含义，但在此之前，让我们先了解一下为什么qsort()需要它所需类型的最后一个参数。qsort()是一个可以对任何类型的数据进行排序的函数。

您可以通过以下方式提供它：

• 基指针，指向连续数据块的开始，
• 块中元素的数量，
• 一个数据成员的大小，
• 比较两个数据值的函数。

由于排序算法通常不依赖于要排序的数据的类型，因此可以在不知道排序的数据类型的情况下编写qsort()。但是为了能够做到这一点，qsort()接受void *参数，这在C中的意思是“通用指针”。

假设您有一个未排序的int值数组：

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

然后，您可以通过调用qsort()对它们进行排序

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

将data传递给qsort()时，其类型为int *，而qsort()的第一个参数的类型为void *。因为在C中任何对象指针都可以转换为void *，所以这是可以的。接下来的两个参数也没问题。最后一个参数compare_int应该是一个接受两个const void *参数并返回一个int的函数。该函数将被qsort()使用从&data[0]到&data[N-1]的指针对调用所需的次数。

要声明一个“接受两个const void *参数并返回int”的函数f()：

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

如果要声明一个我们可以设置为f的函数指针，则该指针声明为：

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

括号是必需的，因为否则pf将是一个返回int *的函数。现在，pf是指向返回int的函数的指针。

回到我们的int排序算法，根据上面的内容，我们可以将compare_int()定义为：

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;
}

在编写compare_int()时，我们知道传递的指针是伪装成void *的int *，所以我们将它们转换回int *，这是可以的，然后我们比较数字。

现在，我们将注意力转向有问题的代码：

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

意味着compare_wid是一个接受两个TRELLIS_ATOM *参数的函数，并返回一个int。正如我们刚刚看到的，qsort()的最后一个参数应该是以下类型的函数：

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

即接受两个const void *参数并返回int的函数。由于类型不匹配，程序员将compare_wid()转换为qsort()所需的类型。

然而，这也有问题。类型的函数：

int (*)(TRELLIS_ATOM *, TRELLIS_ATOM *)

不等同于以下类型的函数：

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

因此，不能保证强制转换是否能正常工作。将compare_wid()声明为：

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

compare_wid()的定义应该如下所示：

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;
}

如果这样做，您就不需要在调用qsort()时进行强制转换，而且您的程序不仅更容易阅读，而且也更正确。

如果你不能改变compare_wid()，那就写另一个函数：

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

并使用compare_stub() (不带强制转换)而不是compare_wid()调用qsort()。

编辑:基于许多错误的答案，下面是一个测试程序：

$ 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;
}

使用定义为接受两个const struct one_int *值的compare()进行编译：

$ 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

使用正确的定义进行编译：

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

编辑2:对于qsort()的最后一个参数，按原样使用compare_wid的合法性似乎有些混乱。comp.lang.c FAQ, question 13.9有一个很好的解释(重点是我的)：

要理解为什么需要在qsort比较函数中进行奇怪的指针转换(以及为什么在调用qsort时对函数指针进行强制转换无济于事)，可以考虑一下qsort是如何工作的。qsort不知道要排序的数据的类型或表示:它只处理小的内存块。(它只知道块的大小，这是在qsort的第三个参数中指定的。)为了确定两个块是否需要交换，qsort调用比较函数(为了交换它们，它使用memcpy的等价物)。

由于qsort以泛型方式处理未知类型的内存块，因此它使用泛型指针(void *)来引用它们。当qsort调用您的比较函数时，它将两个指向要比较的块的通用指针作为参数传递。由于它传递的是泛型指针，所以比较函数必须接受泛型指针，并在操作它们之前(即在执行比较之前)将指针转换回其适当的类型。void指针与结构指针的类型不同，在某些机器上，它可能具有不同的大小或表示形式(这就是为什么需要这些强制转换才能保证正确性)。

如常见问题解答中所述，另请参阅this。

Answer 3

qsort

void qsort ( void * base, size_t num, size_t size, 
                    int ( * comparator ) ( const void *, const void * ) );

comparator：比较两个元素的函数。该函数应遵循以下原型：

整型比较器( const void * elem1，const void * elem2 )；

该函数必须接受两个参数，它们是指向元素的指针，类型转换为void*。这些参数应该转换回某个数据类型并进行比较。

此函数的返回值应表示通过分别返回负值、零或正值，是否认为elem1小于、等于或大于elem2。