mathcom mathcom - 1 year ago 69
C Question

What means of this code in C qsort?

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

where a is a start of array address, n is sizeof array, es is sizeof array element.

I read the source code of qsort in C that I can't understand. the code is as follows.

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

I interpret this macro by,

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

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

And what means of this line?

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

Answer Source

Wherever you found that code, you probably copied it incorrectly. I found some very similar code in libutil from Canu:

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

This code was likely illegitimally (because the terms of the copyright license are violated) copied from FreeBSD's libc:

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

So I'm guessing you got it from a *BSD libc implementation. Indeedd FreeBSD's quicksort implementation contains the SWAPINIT macro (not SWAPINT):

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

After parsing, you should find that the above code is roughly the same as

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;

Note that condition_two, as a condition, is not the same as es % sizeof(long) == 1, but rather es % sizeof(long) != 0. Aside from that, your translation was correct.

The intent of these conditions seems to be as follows:

  • condition_one is true when a is not long-aligned.
  • condition_two is true when es is not a multiple of long.
  • condition_three is true when es is exactly long.

As a result,

  • swaptype == 2 is when you don't have enough guarantees about the elements to be clever about swapping,
  • swaptype == 1 is intended for arrays with elements that are aligned along long boundaries (note: but not necessarily aligned as longs!), and
  • swaptype == 0 is intended for arrays that match the previous description, that also have elements that are also long-sized.

There is explicit type conversion in this case, because a has type void*, for which type arithmetic is undefined. However, also note that ((char *)a - (char *)0) is undefined too:

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 draft N1570, section 6.5.6, clause 9 on pages 93 and 94.)

It's not exactly spelled out in C11, but the null pointer is not part of the same array as the object pointed to by a, so the basic rules for pointer arithmetic are violated, so the behaviour is undefined.