这段代码在 C qsort 中的含义是什么？

Question

void qsort (void *a, size_t n, size_t es, int (*compare)(const void *, const void *)

其中a为数组起始地址，n为数组大小，es为数组元素大小。

看不懂的C语言qsort源码。代码如下

#define SWAPINT(a,es) swaptype = ((char*)a- (char*)0 % sizeof(long) || \
        es % sizeof(long) ? 2: es == sizeof(long)? 0 : 1

我解释这个宏，

if(((char*)a- (char*)0)% sizeof(long))==1 || es % sizeof(long)==1)
     swaptype = 2;
else if(es== sizeof(long))
     swaptype = 0;
else
     swaptype = 1;

但是不明白为什么要进行类型转换，(char*)a.

这条线是什么意思？

(char*)a- (char*)0)% sizeof(long)==1

Answer 1

无论您在哪里找到该代码，您都可能将其复制错误。我在 libutil from Canu:

中发现了一些非常相似的代码

c.swaptype = ((char *)a - (char *)0) % sizeof(long) || \
  es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;

此代码可能是从 FreeBSD 的 libc 中非法复制的（因为违反了版权许可条款）：

//__FBSDID("$FreeBSD: src/lib/libc/stdlib/qsort.c,v 1.12 2002/09/10 02:04:49 wollman Exp $");

所以我猜您是从 *BSD libc 实现中获得的。事实上，FreeBSD 的快速排序实现包含 the SWAPINIT macro（不是 SWAPINT）：

#define SWAPINIT(TYPE, a, es) swaptype_ ## TYPE =       \
        ((char *)a - (char *)0) % sizeof(TYPE) ||       \
        es % sizeof(TYPE) ? 2 : es == sizeof(TYPE) ? 0 : 1;

经过解析，你应该会发现上面的代码和

大致相同

condition_one   = ((char *)a - (char *)0) % sizeof(long);
condition_two   = es %  sizeof(long);
condition_three = es == sizeof(long);
c.swaptype = (condition_one || condition_two) ? 2 : condition_three ? 0 : 1;

请注意，condition_two，作为条件，与es % sizeof(long) == 1不同，而是es % sizeof(long) != 0。除此之外，你的翻译是正确的。

这些条件的意图似乎如下：

a

long

condition_one 是 true。

es

long

condition_two 是 true。
condition_three 是 true 当 es 正好是 long.

因此，

swaptype == 2 是当你对元素没有足够的保证来巧妙地交换时，
swaptype == 1 适用于元素沿 long 边界对齐的数组（注意：但不一定 对齐为 长！），和
swaptype == 0 适用于与前面的描述相匹配的数组，这些数组也包含 long 大小的元素。

在这种情况下存在显式类型转换，因为 a 具有类型 void*、for which type arithmetic is undefined。但是，还要注意 ((char *)a - (char *)0) 也是未定义的：

When two pointers are subtracted, both shall point to elements of the same array object, or one past the last element of the array object; the result is the difference of the subscripts of the two array elements.

（C11 草案 N1570，第 6.5.6 节，第 93 和 94 页的第 9 条。）

在C11中没有明确说明，但是空指针与a指向的对象不属于同一个数组，所以违反了指针运算的基本规则，所以行为是未定义。

Answer 2

宏正在尝试用 C 语言检查对齐是否可移植，而 C 语言实际上不允许进行此类测试。所以我们从我们的指针中减去空指针以获得一个整数，然后取模 long 的大小。如果结果为零，则数据是长对齐的，我们可以像 long 一样访问。如果不是，我们可以尝试其他方案。

Answer 3

如评论中所述，您提供的宏定义不会扩展为有效的 C 代码，因为它涉及计算 (char*)0 % sizeof(long)，其中 % 的左侧操作数的类型为 char *。那不是整数类型，但是 % 的两个操作数都必须是整数类型。

另外，宏的展开有不平衡的括号。这并非 本质上 错误，但它使该宏难以使用。此外，即使在运算符优先级产生合理结果的情况下，使用括号和额外的空格也可以帮助人类解释代码，不会影响执行速度，并且可以忽略不计的额外编译成本。

因此，我认为所需的宏应该更像这样：

#define SWAPINT(a,es) swaptype = (                                  \
    ((((char*)a - (char*)0) % sizeof(long)) || (es % sizeof(long))) \
        ? 2                                                         \
        : ((es == sizeof(long)) ? 0 : 1))                           \
)

我会考虑将倒数第二行写成

        : (es != sizeof(long))

以稍微降低表达式的可理解性为代价来降低表达式的复杂性。无论如何，意图似乎是将 swaptype 设置为：

2 if a not 在 n 字节边界上对齐，其中 n 是long 中的字节，或者如果 es 不是 long 大小的整数倍；否则
1 if es 不等于 a long 的大小；否则
0

这与您的解释相似，但不完全相同。但是请注意，由于 (char*)a - (char*)0，即使这段代码也有未定义的行为。仅当两个指针都指向同一对象或刚好超过同一对象的末尾时，评估该差异才具有定义的行为，并且 (char *)0 不指向（或刚好超过）任何对象的末尾。

你具体问了：

But I don't understand why type conversion is implemented, (char*)a.

执行此操作是因为指针运算是根据指向的类型定义的，因此 (1)，符合要求的程序无法使用 void * 执行运算，并且 (2) 代码需要结果减法的单位与 sizeof 运算符（字节）的结果相同。

And what means of this line?
(char*)a- (char*)0)% sizeof(long)==1

该行没有出现在您提供的宏中，并且由于括号不平衡，它不是一个完整的表达式。它似乎试图确定 a 是否指向一个 n 字节边界，其中 n 如上定义，但同样，评估指针差异具有未定义的行为。另请注意，对于整数 x，在布尔上下文中计算的 x % sizeof(long) == 1 与在相同上下文中计算的 x % sizeof(long) 具有不同的含义。后者在您描述的上下文中更有意义。

这段代码在 C qsort 中的含义是什么？

What means of this code in C qsort?

c

qsort