转换函数指针

Question

我正在编写一个函数，它接收一个指向比较函数的指针和一个 MyStructs 的数组，并且应该根据比较函数对数组进行排序：

void myStructSort(
                  struct MyStruct *arr,
                  int size,
                  int (*comp)(const struct MyStruct *, const struct MyStruct *)) {
  qsort(arr, size, sizeof(struct MyStruct), comp);
}

不幸的是，这无法编译，因为 qsort 期望比较器接收 void * 个参数而不是 const struct MyStruct *。我想到了几个不好的解决方案，想知道正确的解决方案是什么。

选项 1

将 comp 转换为 int (*)(const void *, const void*)。这编译但未定义的行为（见 this SO question）。

选项 2

创建一个全局变量int (*global_comp)(const struct MyStruct *, const struct MyStruct *)并在myStructSort中设置global_comp=comp。然后创建一个函数：

int delegatingComp(const void *a, const void *b) {
  return globalComp((const struct MyStruct *)a, (const struct MyStruct *)b);
}

并在 myStructSort 调用 qsort(arr, size, sizeof(struct MyStruct), delegatingComp)。这个问题是 icky 全局变量。

选项 3

重新实现 qsort。这在功能上是安全的，但却是非常糟糕的做法。

有神奇完美的第四种选择吗？

编辑

我无法更改 myStructSort 的 API，我正在使用 gcc c99 -Wall -Wextra -Wvla.

编译我的代码

Answer 1

以下方法仅适用于 gcc。它是 gnu 扩展的一部分。进一步请参考https://gcc.gnu.org/onlinedocs/gcc-4.8.5/gcc/Nested-Functions.html#Nested-Functions

首先让我们确定 qsort 的原型在 such a form:

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

那么你可以：

void myStructSort(
                  struct MyStruct *arr,
                  int size,
                  int (*comp)(const struct MyStruct *, const struct MyStruct *)) {
  int comparator(const void * a, const void *b) {
    return comp((const struct MyStruct *)a, (const struct MyStruct *)b);
  }
  qsort(arr, size, sizeof *arr, comparator);
}

但同样，由于它使用 gnu 扩展，不要期望太多的可移植性。

关于您的评论：对于现代 gcc，gnu 标准是默认的，而不是 iso 标准。具体来说，最新的 gcc 应该使用 gnu11 标准。年纪大的正在使用 gnu89。所以，我不知道你的命令行参数，但如果 -std 没有设置，这将起作用。

以下是取自 info gcc 的示例，以防万一 link 已死。它显示了嵌套函数的类似闭包的用法：

 bar (int *array, int offset, int size)
 {
   int access (int *array, int index)
     { return array[index + offset]; }
   int i;
   /* ... */
   for (i = 0; i < size; i++)
     /* ... */ access (array, i) /* ... */
 }

Answer 2

选项 2 破坏了线程安全，所以我不会选择那个。

正如您指出的那样，选项 3 完全错误。没有理由重新实现快速排序并可能犯错误。

选项 1 是 UB，但它适用于任何健全的编译器。如果您选择此选项，请务必添加评论。

我也会考虑：

选项 4. 重新设计 myStructSort 的接口以获取 int (*)(const void *, const void*) 或完全废弃它并直接调用 qsort。基本上把它发回给建筑师，因为他做出了一个糟糕的设计选择。

Answer 3

如果您使用的是 gcc，那么您可以在 glibc 中使用自 2.8 以来的 qsort_r 函数，它允许您使用用户提供的附加参数指定一个比较器函数：

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

当然，这不是可移植的，它需要您定义功能测试宏：

#define _GNU_SOURCE

(在 FreeBSD 上 —— 大概 Mac OS X —— 有一个类似但不兼容的 qsort_r；区别在于用户提供的上下文参数是作为比较函数的 first 参数提供，而不是最后一个参数。）

但是如果你有它，它可以让你避免选项 2 中的全局：

/* This struct avoids the issue of casting a function pointer to
 * a void*, which is not guaranteed to work. It might not be
 * necessary, but I know of no guarantees.
 */
typedef struct CompContainer {
   int (*comp_func)(const struct MyStruct *, const struct MyStruct *);
} CompContainer;

int delegatingComp(const void *a, const void *b, void* comp) {
  return ((CompContainer*)comp)->comp_func((const struct MyStruct *)a,
                                           (const struct MyStruct *)b);
}

void myStructSort(
              struct MyStruct *arr,
              int size,
              int (*comp_func)(const struct MyStruct *,
                               const struct MyStruct *)) {
  const CompContainer comp = {comp_func};
  qsort_r(arr, size, sizeof(struct MyStruct), delegatingComp, &comp);
}

(Live on ideone)

Answer 4

唯一明智的选择是重写您创建的界面，或者创建一个新界面。

I've done something very similar with bubble sort on another answer of mine.

简而言之，对于 C，您希望排序函数的形式为：

void* bubbleSort(void* arr, int (*compareFcn)(void*, void*),
    size_t sizeOfElement, size_t numElements)

您的比较函数的形式为：

int compareFunction(void *a, void *b);

Answer 5

正确的做法是在比较函数中从void const *转换为MyStruct const *。

这对于第一个对象来说是明确定义的，因为传递给比较函数的指针是通过从 MyStruct const * 到 void const * 的转换创建的，并将指针转换为 void 返回其原始类型是允许的（而且它确实是唯一的）。

对于其他数组成员，假设将void const *转换为char const *，加上对象的偏移量，通过对象大小乘以对象在数组中的位置生成, 并将其转换回 void const * 将提供一个可以转换回 MyStruct const *.

的指针

这是一个大胆的假设，但通常是可行的。可能存在这不起作用的极端情况，但通常编译器将任何 struct foo 填充为其对齐的倍数，以确保数组成员的起始地址具有 sizeof(struct foo).[=24 的距离=]

转换函数指针通常是不安全的，需要避免，因为不同的数据类型可能有不同的表示形式——例如，void * 必须能够表达每个可能的地址，因为它可以被转换来自 char *，而 MyStruct * 保证有一些最低有效位被清除，因为任何有效对象都会被对齐——所以这些类型的调用约定完全有可能是不同。

转换函数指针

Casting function pointers

c

function-pointers

qsort