Different declarations of qsort_r on Mac and Linux

Question

Let's see function qsort_r in Linux (/usr/include/stdlib.h):

typedef int (*__compar_d_fn_t)(const void *, const void *, void *);

extern void qsort_r (void *__base, size_t __nmemb, size_t __size,
         __compar_d_fn_t __compar, void *__arg)
  __nonnull ((1, 4));

Let's see function qsort_r in Mac (/usr/include/stdlib.h):

void qsort_r(void *, size_t, size_t, void *, int (*)(void *, const void *, const void *));

As you can see these declarations are differ from each other (sequence of arguments). This is surprising! Will it be effective to complain somewhere to solve this problem?

Answer 1

Will it be effective to complain somewhere to solve this problem?

Alas, no. It's been this way for too long and there's too much code relying on it.

I think the underlying question is "why do these incompatibilities happen"? I'll answer that. It appears to boil down to BSD implementing it first but with a poor interface. ISO and later GNU fixed the interface and decided the compatibility breakage was worth it. And Microsoft does whatever they feel like.

As pointed out by @Downvoter (great name), qsort_r is a non-standard function. It would be nice if it were standard, but you can't rely on that. qsort_s is sort of standard in C11 Annex K, but nobody really implements C11, let alone its annexes, and whether Annex K is a good idea is in question.

Like a lot of C and Unix issues, this comes down to BSD vs GNU vs Microsoft and their inability to coordinate C extensions. Linux is GNU. OS X is a mish-mash of many things, but for C it follows BSD.

FreeBSD added qsort_r in Sept 2002. Visual Studio 2005 featured a slightly different qsort_s. ISO formalized a yet different again qsort_s in 2007. Finally GNU's came years later in glibc 2.8 in 2008 apparently following ISO. Here's an old thread spanning 2004 to 2008 requesting qsort_r be implemented in glibc which has some rationales.

For remind everyone, here is qsort as defined in C99.

void qsort(
    void *base, size_t nmemb, size_t size,
    int (*compar)(const void *, const void *)
);

---

FreeBSD was the first in Sept 2002. They decided that qsort_r should break the qsort interface and put the "thunk" argument before the comparison function.

void qsort_r(
    void *base, size_t nmemb, size_t size,
    void *thunk,
    int (*compar)(void *, const void *, const void *)
);

Why? You'll have to ask Garrett Wollman who wrote the patch. Looking at the patch you can see from his changes to CMP it was decided that having the "thunk" first was a good pattern. Maybe they decided "the comparison function goes at the end" was what people would remember. Unfortunately this means qsort and qsort_r's comparison functions have their arguments reversed. Very confusing.

---

Meanwhile Microsoft, ever the innovator, has qsort_s in Visual Studio 2005.

void qsort_s(
   void *base, size_t num, size_t width,
   int (__cdecl *compare )(void *, const void *, const void *),
   void * context
);

"s" for "secure" rather than "r" for "reentrant" that everyone else was using possibly following an ISO convention (see below) or vice-versa. They put the "thunk" at the end of qsort_s, keeping the arguments the same as qsort, but for maximum confusion the "thunk" goes at the start of the comparison function like BSD. They chose the worst possible option.

---

To make matters worse, in 2007 ISO published TR 24731-1 to add bounds checking to the C standard library (thanks @JonathanLeffler for pointing that out). And yes, they have their own qsort_r, but it's called qsort_s! And yes, it's different from everyone else's!

errno_t qsort_s(
    void *base, rsize_t nmemb, rsize_t size,
    int (*compar)(const void *x, const void *y, void *context),
    void *context
);

They wisely decided to keep the arguments to qsort_s and its comparison function a superset of qsort probably arguing it would be easier for people to remember. And they added a return value, probably a good idea. To add to the confusion, at the time this was a "Technical Report" and not part of the C standard. It's now "Annex K" of the C11 standard, still optional but carries more weight.

---

GNU decided the same, possibly following ISO's qsort_s.

void qsort_r(
    void *base, size_t nmemb, size_t size,
    int (*compar)(const void *, const void *, void *),
    void *arg
);

Looking at the glibc patch adding qsort_r it was probably also easier to implement. To know for sure you'll have to ask Ulrich Drepper.

---

BSD's decision to swap arguments with qsort and its comparison function has probably caused a lot of confusion and bugs over the years. The ISO / GNU decision to keep them the same is arguably better. ISO decided to give it a different name. GNU decided to break compatibility with the BSD function. Microsoft decided to do whatever. Now we're stuck with four incompatible implementations. Because the comparison functions have different signatures a compatibility macro is non-trivial.

(This is all a reconstruction from the code. For their actual rationales you'll have to dig through mailing list archives.)

I can't really blame GNU or BSD or ISO or Microsoft... ok, I can blame Microsoft for deliberately trying to kill C. Point is the process of standardizing C, and extending that standard, and getting compilers to follow that standard is painfully slow and the compiler writers sometimes have to do what's expedient.