我能用memcmp和qsort一起使用吗？

Question

我正在制作一种C语言动态数组库，有点像。请注意，我是为了好玩才做的，所以请不要推荐现有的成百上千个库。

我开始实现排序。该数组具有任意元素大小，定义为结构体：

typedef struct {
  //[PRIVATE] Pointer to array data
  void *array;
  //[READONLY] How many elements are in array
  size_t length;
  //[PRIVATE] How many elements can further fit in array (allocated memory)
  size_t size;
  //[PRIVATE] Bytes per element
  size_t elm_size;
} Array;

我最初准备从排序函数开始：

/** sorts the array using provided comparator method
 * if metod not provided, memcmp is used
 * Comparator signature
 *  int my_comparator ( const void * ptr1, const void * ptr2, size_t type_size );
**/
void array_sort(Array* a, int(*comparator)(const void*, const void*, size_t)) {
    if(comparator == NULL)
        comparator = &memcmp;
    // Sorting algorithm should follow
}

然而我学到了关于qsort：

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

显然，我可以把我的内部数组传递给qsort。我只需要调用它：

qsort (a->array, a->length, a->elm_size, comparator_callback);

但是有一个陷阱 - qsort的比较函数签名如下：

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

memcmp 的函数签名是：

int memcmp ( const void * ptr1, const void * ptr2, size_t type_size );

qsort的回调函数中缺少元素大小，这意味着当传递NULL作为回调时，我不能再拥有通用比较器函数。我可以手动生成多达X字节的比较器，但这听起来很丑陋。

我可以在使用memcpy的同时使用qsort（或其他内置排序功能）吗？还是我必须在内置比较器和内置排序函数之间进行选择？

- Tomáš Zato

---

“所以请不要推荐成千上万的现有库。”我笑了。 - Ryan Haining

传递给比较函数的指针将是数组指针。您可以将它们转换为数组，然后使用该结构的长度成员来确定要比较的字节数。 - JJF

qsort 函数中的元素大小不应该是你的数组的 elm_size 吗？ - Jongware

但是有一个问题 - qsort的比较器签名看起来像这样：...这是因为你将比较函数传递给最后一个参数，而不是数组。 - Weather Vane

@RadLexus 当然可以...也许我的问题表述不够清晰。我的问题是无法将那个大小传递给memcpy函数。默认比较函数需要知道元素的大小 - 恰恰因为它接收两个数组指针，而且并不知道它们的大小。 - Tomáš Zato

Answer 1

C11为您提供了一个（虽然可选的）qsort_s函数，旨在处理这种特定情况。它允许您将用户提供的 void *值 - 上下文指针 - 从调用代码传递到比较器函数。在这种情况下，比较器回调具有以下签名。

int (*compar)(const void *x, const void *y, void *context)

在最简单的情况下，您可以将大小值的指针作为上下文传递。

#define __STDC_WANT_LIB_EXT1__ 1
#include <stdlib.h>
...

int comparator_callback(const void *x, const void *y, void *context)
{
  size_t elm_size = *(const size_t *) context;
  return memcmp(x, y, elm_size);
}

...
qsort_s(a->array, a->length, a->elm_size, comparator_callback, &a->elm_size);

或者将指向整个数组对象的指针作为上下文传递可能更加合理。

一些基于*nix的实现已经提供了类似的qsort_r函数，尽管它是非标准的。

- AnT stands with Russia

---

我在作业中使用这个库，需要C99，但我还是点赞了，因为它通常很有用。 - Tomáš Zato

Answer 2

一种非线程安全的方式是使用私有全局变量来传递大小。

static size_t compareSize = 0;

int defaultComparator(const void *p1, const void *p2) {
  return memcmp(p1, p2, compareSize);
}

void array_sort(Array* a, int(*comparator)(const void*, const void*, size_t)) {
    if(comparator == NULL) {
      compareSize = a->elm_size;
      comparator = &defaultComparator;
    }
    // Sorting algorithm should follow
}

你可以通过将compareSize设置为线程本地变量（__thread）来使其线程安全。

- Bryan Chen

---

我曾经考虑过这个，但对我来说是不可行的，即使我认为我不会在任何多线程中使用它。如果那是唯一的选择，我宁愿从GNU C库复制并编辑qsort。 - Tomáš Zato

为什么？在C语言中，全局变量有时是不可避免的。通过将其设置为内部链接，我认为没有任何问题。 - Bryan Chen

我对C语言不是很有经验，我不知道这个。你能详细说明一下如何使用__thread吗？它是否可移植？ - Tomáš Zato

__thread是GCC的扩展，而thread_local则是C11中的关键字。您可以在这里阅读更多信息。 - Bryan Chen

Answer 3

qsort() API是简单时代的遗产。从qsort()调用传递一个额外的“环境”指针到每个比较中，这将允许您以线程安全的方式传递对象大小和任何其他必要的上下文。

但实际上它并不存在。@BryanChen的方法是唯一合理的方法。

我写这篇答案的主要原因是要指出，很少有情况下memcmp会做出有用的事情。没有多少种对象按照组成部分unsigned char的字典顺序进行比较是有意义的。

当然，以这种方式比较struct是危险的，因为填充字节值是未指定的。即使相等性比较也可能失败。换句话说，

struct foo { int i; };

void bar(void) { 
  struct foo a, b;
  a.i = b.i = 0;
  if (memcmp(&a, &b, sizeof a) == 0) printf("equal!");
}

根据C标准，可能不会打印任何内容！

另一个例子：对于像无符号整数这样简单的类型，大端和小端存储顺序会有不同的排序方式。

unsigned a = 0x0102;
unsigned b = 0x0201;
printf("%s", memcmp(&a, &b, sizeof a) < 0 ? "Less!" : "More!");

该代码将根据运行它的机器打印Less或More。

实际上，我唯一能想象得到与memcmp比较有意义的对象类型是相等大小的无符号字节块。这不是排序的常见用例。

总之，一个提供memcmp作为比较函数的库注定会容易出错。有人会尝试将其用作替代专门比较的方法，而这种方法确实是获得所需结果的唯一方法。

- Gene

---

虽然特定的排序可能与平台有关，但这并不意味着在 OP 的上下文中具体的排序很重要。也许 OP 只关心等价元素的分组，而不是元素的相对位置。本质上，C++ std::unordered_set 中的元素排序方式可能（并且将）因平台/实现而异，但这仍然不会限制 std::unordered_set 的预期用途。 - AnT stands with Russia

@AnT 他说他正在构建一个动态数组库。我认为合理的假设是它所包含的类型是任意的。通过字节逐位地按字典顺序比较任意类型几乎没有意义。 - Gene