c-qsort比较器分段故障

Question

我正在用C编写一个数据结构库，计划用于个人项目（我确实意识到有通用库可用，但我认为这将是一次很棒的学习体验）。在这样做的过程中，我创建了一个数据结构，它与内置的Python list实现非常相似（就公开的操作而言）。

我在为这个结构编写一些单元测试时，偶然发现qsort比较器函数有一些困难。我已经浏览了大量关于同一问题的SO回复，但推荐的修复程序似乎都不起作用。

下面给出的相关代码（由于长度原因，其他代码被省略了，但如果需要的话，我很乐意把它带进来）：

typedef struct glist glist;
struct glist {
    void **data;
    size_t len;
    size_t cap;
    int (*cmp)(void const*, void const*);
    void (*free)(void*);
};
static int list_test_comparator(const void *left, void const *right);
glist* glist_new(int (*cmpfn)(const void*, const void*), void (*freefn)(void*)) {
    glist *list = malloc(sizeof(glist));
    if (!list) {
        return NULL;
    }
    size_t cap = sizeof(void*) * 10;
    list->data = calloc(cap, cap);
    if (!list->data) {
        free(list);
        return NULL;
    }
    list->len = 0;
    list->cap = 10;
    list->cmp = cmpfn;
    list->free = freefn;
    return list;
}
void glist_sort(glist *list) {
    if ((!list) || (list->len == 0)) {return;}
    qsort(list->data, list->len, sizeof(void *), list->cmp);
}
static int list_test_comparator(const void *left, const void *right) {
    const char *l = left;
    const char *r = right;
    printf("Left: %s %pn", l, left);
    printf("Right: %s %pn", r, right);
    int res = strcmp(l, r);
    printf("Res: %dn", res);
    return res;
}
/* Run by CUnit before and after each test case */
void list_test_setup(void) {
    list_test = glist_new(list_test_comparator, free);
}
void list_test_sort(void) {
    for (int i = 0; i < 15; i++) {
        char *some = "%d";
        char *next = malloc(20);
        CU_ASSERT_FATAL(next != NULL);
        sprintf(next, some, rand());
        CU_ASSERT(glist_append(list_test, next) == true);
    }
    /* Note that this is a CUnit test with setup function creating 
     * the structure with the above defined list_test_comparator func */
    glist_sort(list_test);
    int val;
    int prev = -1; /* rand() should always return value between 0 and RAND_MAX */
    for (int i = 0; i < 15; i++) {
        char *test = glist_get(list_test, i);
        sscanf(test, "%*s %d", &val);
        CU_ASSERT(val <= prev);
        prev = val;
    }
}

正如我上面提到的，我在类似的问题中尝试了许多建议（取消对cast的引用指针，将我的调用更改为qsort，等等）。去引用技巧const char *l = *(const char**)left;导致segfault（和Valgrind进入无限循环）。

我甚至到了这样一个地步（你可以在上面的比较器中看到一些），我开始在比较器之前和内部打印指针位置，我发现大多数指针位置都不一样。

部分输出：

/* Before sort */
282475249 0x7fb629c04f30
1622650073 0x7fb629c04f50
984943658 0x7fb629c04f70
1144108930 0x7fb629c04f90
470211272 0x7fb629c04fb0
101027544 0x7fb629c04fd0
1457850878 0x7fb629c04ff0
1458777923 0x7fb629c05010
2007237709 0x7fb629c05030
823564440 0x7fb629c05050
1115438165 0x7fb629c05200
1784484492 0x7fb629c053b0
74243042 0x7fb629c053d0
114807987 0x7fb629c053f0
/* In comparator */
Left: O?)? 0x7fb629c05070
Right: O?)? 0x7fb629c050a8
Res: -224
Left: ?O?)? 0x7fb629c050a8
Right: ?O?)? 0x7fb629c050e0
Res: -4
Left: 0O?)? 0x7fb629c05078
Right: 0O?)? 0x7fb629c05070
Res: -192

我对这个问题的最佳猜测是，qsort在某种程度上没有得到关于我的内部数据结构中的正确信息，所以它给了我不正确的指针偏移量。

其他相关信息：

• 操作系统X 10.10.2

• cc -v说

  Apple LLVM version 6.0 (clang-600.0.57) (based on LLVM 3.5svn)
  Target: x86_64-apple-darwin14.1.0
  Thread model: posix
  

• 我的所有其他单元测试都通过了。这些测试包括基本的insert和remove，以及一个返回给定元素索引的函数（使用上面的比较器）。

编辑：显示更多代码。

Answer 1

我想你误解了比较器接收指针的内容。它接收一个指向保存数据的内存的指针。因此，如果你的数据是void，它会接收到伪装成void的void指针。

要解决此问题，请尝试以下代码：

static int list_test_comparator(const void *left, const void *right) {
    const void *leftptr = *(const void**)left;
    const void *rightptr = *(const void**)right;
    const char *l = leftptr;
    const char *r = rightptr;
    printf("Left: %s %pn", l, left);
    printf("Right: %s %pn", r, right);
    int res = strcmp(l, r);
    printf("Res: %dn", res);
    return res;
}

我现在不能测试我的代码，因为你的代码中缺少glist_append和glist_get，但这就是应该使用qsort的方式。