C qsortのこのコードの意味は何ですか？

debugcn 投稿 Dev

mathcom

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

user824425

そのコードを見つけたところはどこでも、おそらくそれを間違ってコピーしたでしょう。libutilCanuから非常によく似たコードを見つけました：

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 $");

ですから、* BSDlibcの実装から得たと思います。実際、FreeBSDのクイックソート実装にはSWAPINITマクロが含まれています（ではありません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。
condition_twoあるtrueときesの倍数ではありませんlong。
condition_threeあるtrueときes、正確ですlong。

結果として、

swaptype == 2 交換について賢くするための要素についての十分な保証がない場合です。
swaptype == 1long境界に沿って整列された要素を持つ配列を対象としています（注：ただし、必ずしもlongとして整列されている必要はありません！）。
swaptype == 0前の説明に一致し、longサイズも同じ要素を持つ配列を対象としています。