8

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?

Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
gmoryes
  • 93
  • 1
  • 5

2 Answers2

21

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.

Schwern
  • 153,029
  • 25
  • 195
  • 336
  • 2
    And, because of the difference between Linux and BSD, POSIX will not standardize `qsort_r()` because the differences are irreconcilable. The best it can do is add an alternative — maybe `qsort_s()`, but that has the wrong connotations of TR 24731-1 / Annex K of C11 — and promulgate that. But those in at least one of the camps will be unhappy that it requires more than a simple name change. – Jonathan Leffler Sep 18 '16 at 18:52
  • 2
    @JonathanLeffler Oh no, Microsoft's `qsort_s` isn't even compatible with the ISO `qsort_s`! Also it appears TR 24731-1 predates glibc's `qsort_r`. – Schwern Sep 18 '16 at 18:58
  • 2
    Ah; I'd not gone to check whether Annex K had `qsort_s()`, much less what Microsoft did that was different from Annex K. There's an outside chance that POSIX might standardize on the Annex K `qsort_s()`, which appears to match GNU's `qsort_r()` except for the name, leaving BSD as the victim. Or they could use `posix_qsort_r()`, or whatever. It basically means that until (unless) POSIX makes a decision and platforms implement it, if you need `qsort_r()` functionality, you can't write 100% portable code and use the system-provided function. – Jonathan Leffler Sep 18 '16 at 19:03
  • @JonathanLeffler POSIX has [accepted](https://austingroupbugs.net/view.php?id=900) `qsort_r()` for issue 8, with the glibc prototype. There's also a [patch](https://reviews.freebsd.org/D17083) to switch the FreeBSD function over to the glibc prototype. – Craig Barnes Nov 07 '21 at 04:40
  • @CraigBarnes — interesting! Thank you! I identified the issues; I didn't expect POSIX to make a decision that breaks (a small minority) of existing, perfectly valid code. For the most part, the decision makes sense. – Jonathan Leffler Nov 07 '21 at 05:05
  • Microsoft's argument ordering is actually the best option of the lot, not the worst. The state/context/thunk pointer is analogous to the "this"/"self" parameter of methods in object orientation and to partial application in function orientation. And of course state goes after the function because of the function has natural primacy over the state in this case: a comparator function which does not have or use state is a sensible thing but a state without a comparator function is invalid use of this API (put another way: function+data pointer is a callback which is optionally a closure). – mtraceur Dec 06 '21 at 18:13
  • 1
    @mtraceur Having one sort function behave differently from every other sort function because that one function is designed with a foreign paradigm in mind (C is not an OO language) is not a good choice. Not that I believe that was the rationale. No, it's the worst decision because it's incompatible with the existing `qsort_r`, *and* its cmp function is inconsistent with `qsort`, *and* they predicted the standard wrong. The standard, predictably, did it the standard C way: put the new arguments on the end. But this was in the bad old days when MSVC did not care about the C standard. – Schwern Dec 06 '21 at 22:46
  • It behaves differently by having three parameters instead of two, regardless of whether that parameter goes at the beginning or at the end. (Except perhaps at the ABI level: if you put it at the end, then on a lot of ABIs, comparators for qsort can still be called with that third argument and end up implicitly ignoring it - if you want to rely on that even though it is undefined behavior at the C level.) – mtraceur Dec 07 '21 at 02:26
  • 1
    Consistency with a design which is wrong for the problem is pretty low value (actually negative value, because solutions should be designed to best fit the actual problem, and motivation to superficially resemble solutions to related simpler problems tends to get in the way of that). – mtraceur Dec 07 '21 at 02:49
  • As for "C is not an OO language"... It's not a functional language either, and yet I mentioned function-orientation and closures too. Why? Because I am pointing at a similarity/pattern in logical shape (or the value in matching that with our code) which transcends languages/paradigms. There is value to following those patterns in all languages, often enough value to break from previous conventions which were written with a lack of vision for them. – mtraceur Dec 07 '21 at 02:58
2

As written here, qsort is standardized (C99), but qsort_r is a GNU-extension ("qsort_r() was added to glibc in version 2.8"). So, there are no requirements for it to be the same across platforms, let alone portable.

cadaniluk
  • 15,027
  • 2
  • 39
  • 67