How portable is qsort_r for re-entry compared to qsort?

Question

qsort_r() is a re-version of qsort() that takes an additional argument "thunk" and passes it to the comparison function, and I would like to be able to use it in portable C code. qsort() is POSIX everywhere, but qsort_r() seems to be a BSD extension. As a specific question, does this exist or have an equivalent in the Windows C runtime?

Answer 1

I tried to write a portable version of qsort_r / qsort_s (called sort_r), shown in the example. I also put this code in the git repository https://github.com/noporpoise/sort_r )

 struct sort_r_data { void *arg; int (*compar)(const void *a1, const void *a2, void *aarg); }; int sort_r_arg_swap(void *s, const void *aa, const void *bb) { struct sort_r_data *ss = (struct sort_r_data*)s; return (ss->compar)(aa, bb, ss->arg); } void sort_r(void *base, size_t nel, size_t width, int (*compar)(const void *a1, const void *a2, void *aarg), void *arg) { #if (defined _GNU_SOURCE || defined __GNU__ || defined __linux__) qsort_r(base, nel, width, compar, arg); #elif (defined __APPLE__ || defined __MACH__ || defined __DARWIN__ || \ defined __FREEBSD__ || defined __BSD__ || \ defined OpenBSD3_1 || defined OpenBSD3_9) struct sort_r_data tmp; tmp.arg = arg; tmp.compar = compar; qsort_r(base, nel, width, &tmp, &sort_r_arg_swap); #elif (defined _WIN32 || defined _WIN64 || defined __WINDOWS__) struct sort_r_data tmp = {arg, compar}; qsort_s(*base, nel, width, &sort_r_arg_swap, &tmp); #else #error Cannot detect operating system #endif } 

Usage example:

 #include <stdio.h> /* comparison function to sort an array of int, inverting a given region `arg` should be of type int[2], with the elements representing the start and end of the region to invert (inclusive) */ int sort_r_cmp(const void *aa, const void *bb, void *arg) { const int *a = aa, *b = bb, *p = arg; int cmp = *a - *b; int inv_start = p[0], inv_end = p[1]; char norm = (*a < inv_start || *a > inv_end || *b < inv_start || *b > inv_end); return norm ? cmp : -cmp; } int main() { /* sort 1..19, 30..20, 30..100 */ int arr[18] = {1, 5, 28, 4, 3, 2, 10, 20, 18, 25, 21, 29, 34, 35, 14, 100, 27, 19}; /* Region to invert: 20-30 (inclusive) */ int p[] = {20, 30}; sort_r(arr, 18, sizeof(int), sort_r_cmp, p); int i; for(i = 0; i < 18; i++) printf(" %i", arr[i]); printf("\n"); } 

Compile / start / exit:

 $ gcc -Wall -Wextra -pedantic -o sort_r sort_r.c $ ./sort_r 1 2 3 4 5 10 14 18 19 29 28 27 25 21 20 34 35 100 

I tested mac and linux. Update this code if you notice errors / improvements. You can use this code as you wish.

Answer 2

For Windows you should use qsort_s : http://msdn.microsoft.com/en-us/library/4xc60xas(VS.80).aspx

There seems to be some disagreement regarding BSD and GNU having incompatible versions of qsort_r , so be careful with using it in production code: http://sourceware.org/ml/libc-alpha/2008-12/msg00003.html

BTW, _s means “secure”, and _r means “re-login”, but both mean that there is an additional parameter.

Answer 3

It is not specified in any portability standard. I also consider it a mistake to call this a "thread safe" version of qsort . The qsort standard is thread safe, but qsort_r effectively allows you to close a closure as a comparison function.

Obviously, in a single-threaded environment, you can achieve the same result with the global variable and qsort , but this use will not be thread safe. Another approach to thread safety will be to use thread-specific data, and have your comparison function extract its parameter from thread-specific data ( pthread_getspecific with POSIX streams or __thread variables in gcc and the upcoming C1x standard).