我可以将 memcmp 与 qsort 一起使用吗？

Question

我正在制作 C 动态数组库，有点。请注意，我是在空闲时间做的，所以请不要推荐百万现有库。

我开始实施排序。该数组具有任意元素大小，定义为 struct:

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 字节元素大小的比较器，但这听起来很难看。

我可以将 qsort（或其他内置排序）与 memcpy 一起使用吗？还是我必须在内置比较器和内置排序功能之间进行选择？

Answer 1

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

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)

使其成为线程安全的

Answer 2

C11 为您提供了一个（当然是可选的）qsort_s function，旨在处理这种特定情况。它允许您将用户提供的 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 function，尽管它不是标准的。

Answer 3

qsort() API 是简单时代的遗产。应该有一个额外的 "environment" 指针从 qsort() 调用中原封不动地传递给每个比较。这将允许您以线程安全的方式传递对象大小和任何其他必要的上下文。

但它不在那里。 @BryanChen的方法是唯一合理的。

我写这个答案的主要原因是要指出 memcmp 在极少数情况下会做一些有用的事情。没有多少对象可以按组成 unsigned chars 的字典顺序进行比较是有意义的。

当然，以这种方式比较 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 ints 这样简单的东西，你会得到不同的大端存储顺序和小端存储顺序的排序顺序。

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

将打印 Less 或 More 取决于它所在的机器运行。

事实上，我能想到的唯一可以与 memcmp 进行比较的对象类型是大小相等的无符号字节块。这不是一个很常见的排序用例。

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

我可以将 memcmp 与 qsort 一起使用吗？

Can I use memcmp along with qsort?

c

arrays

memcpy

qsort