空指针算法与解引用

Question

我看了一个通用的快速排序实现，快速排序函数的参数之一是一个void指针，我看到了空指针上的ff算法，所以我想知道它实际上做了什么，甚至可能吗？

void _qsort(void *v, int size, int left, int right, int (*comp)(void *, void *));

void swap(void *v1, void *v2, int size) {
    char buffer[size];
    memcpy(buffer, v1, size);
    memcpy(v1, v2, size);
    memcpy(v2, buffer, size);
}

这个部分出现在上面定义的快速排序的正文中：

    void *vl = (char *)(v + (left * size));
    void *vr = (char *)(v + (mid * size));
    swap(vl, vr, size);

所以根据上面的代码，

v + (left * size)

• What

1. 怎么可能在void指针v上做算术，就像void *vl = (char *)(v + (left * size));部件的意思一样？如果是的话，为什么我们要将它分配给一个char指针？swap部件中的
2. ，到底发生了什么，比如vl和vr正在改变它们的内存位置、值或其他什么？

Answer 1

假设是正确的:C标准没有定义void指针上的算术。

您正在查看的程序使用了gcc、clang、tcc和许多其他支持的通用编译器扩展，该扩展在void指针上实现算术，就好像它们是字节指针一样。有了这个扩展，v + (left * size)表现为

    (void *)((char *)v + (left * size))

因此，声明void *vl = (char *)(v + (left * size));相当于：

    void *vl = (char *)((void *)((char *)v + (left * size)));

请注意，整个表达式在C中隐式转换为(void *)。

本声明可简化为：

    void *vl = (char *)v + left * size;

这可能是程序员想要写的，他们的错误没有被报告，因为编译器允许void *算法具有完全相同的效果。

关于第三个问题，swap函数使用v1和v2所指向的内存块的内容，使用v2字节的局部变量长度数组buffer交换内存块的内容。qsort通常是以相当小的元素大小调用的，因此这种方法是可以的，但是可以使用一个非常长的元素数组(超过几兆字节)调用qsort，并可能导致堆栈溢出。

以下是一个更安全的实现：

void swap(void *v1, void *v2, size_t size) {
    unsigned char *p1 = v1;
    unsigned char *p2 = v2;
    while (size >= 8) {
        char buffer[8];
        memcpy(buffer, p1, sizeof buffer);
        memcpy(p1, p2, sizeof buffer);
        memcpy(p2, buffer, sizeof buffer);
        p1 += sizeof buffer;
        p2 += sizeof buffer;
        size -= sizeof buffer;
    }
    if (size > 0) {
        if (size >= 4) {
            char buffer[4];
            memcpy(buffer, p1, sizeof buffer);
            memcpy(p1, p2, sizeof buffer);
            memcpy(p2, buffer, sizeof buffer);
            p1 += sizeof buffer;
            p2 += sizeof buffer;
            size -= sizeof buffer;
        }
        while (size > 0) {
            unsigned char temp = *p1;
            *p1 = *p2;
            *p2 = temp;
            p1++;
            p2++;
            size--;
        }
    }
}

还请注意以下意见：

标准库函数

• qsort有一个不同的原型：

Voidq排序( void *base，size_t nmemb，size_t size，int (*compar)(const *，const *));

不建议将

• 用于大小和索引值使用int。left * size可能会溢出64位size_t和32位int的系统上的大型数组：_qsort函数假定left * size和right * size在size_t类型的范围内，最多也不超过v所指数组的大小，但这个大小可能超过INT_MAX，导致int乘法出现未定义的行为溢出。正确的类型是size_t，函数开头的是否正确检查可以用来检测无效的参数。