mathcom - 22 days ago 4x
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;
else
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
``````

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.

Source (Stackoverflow)