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

Question

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

其中a是数组地址的开始，n是sizeof数组，es是sizeof数组元素。

我读了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*)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; 

此代码很可能illegitimally（因为版权许可的条款受到侵犯）从FreeBSD的libc中复制：

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

所以我猜你从* BSD libc实现中获得它。 Indeedd 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。除此之外，你的翻译是正确的。

---

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

• condition_one是true时a不是long -aligned。
• condition_two是true当es不是long的倍数。
• 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)是未定义的太：

当两个指针相减，既应指向同一阵列对象，或一个过去的数组对象的最后一个元素的元素;结果是两个数组元素的下标差异。

（C11草案N1570，部分6.5.6，在93和94页第9节）

这不完全在C11阐明，但空指针是不一样的阵列作为组成部分对象指向a，所以违反了指针算术的基本规则，所以行为是不确定的。

Answer 2

宏正试图用一种语言C来检查对齐方式，这种方式并不能真正支持这种测试。所以我们从我们的指针中减去空指针来获得一个整数，然后取模长度的一个长度。如果结果为零，则数据是长期对齐的，我们可以访问多长时间。如果不是，我们可以尝试其他方案。

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如果a是不一个n字节边界，其中n处于long字节数上对齐，或者如果es是不是long大小的整数倍;否则
• 1如果es不等于long的大小;否则
• 0

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

您特意问：

但我不明白为什么类型的转换实现，（字符*）一个。

，由于指针的算术运算是在定义的执行指向的类型，因此（1）中，相符的节目不能与void *执行算术，和（2）的代码希望相减的结果与sizeof运算符（字节）的结果相同。

这条线的含义是什么？

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

这条线不会出现在你提出的宏，这是因为不对称的括号的不是一个完整的表达。它似乎试图确定a是否指向一个n-字节边界，其中n如上定义，但是再次评估指针差异具有未定义的行为。还要注意，对于整数x,x % sizeof(long) == 1在布尔上下文中评估的含义与在相同上下文中评估的x % sizeof(long)不同。后者在你描述的上下文中更有意义。