Wie tragbar ist die Wiedereintrittsfunktion qsort_r im Vergleich zu qsort?

Question

qsort_r() ist die Re-Entrant-Version von qsort(), die ein zusätzliches "Thunk" -Argument nimmt und es in die Vergleichsfunktion übergibt, und ich möchte es in portablem C-Code verwenden können. qsort() ist POSIX und überall aber qsort_r() scheint eine BSD-Erweiterung zu sein. Als eine spezifische Frage, existiert diese oder hat eine Entsprechung in der Windows C-Laufzeit?

Answer 1

Ich habe versucht, eine portable Version von qsort_r/qsort_s (genannt sort_r) mit einem Beispiel gezeigt zu schreiben. Ich habe auch diesen Code in einem Git-Repo (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 
} 

Beispiel zur Nutzung setzen:

#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/run/Ausgabe:

$ 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 

ich auf dem Mac getestet haben & Linux. Bitte aktualisieren Sie diesen Code, wenn Sie Fehler/Verbesserungen feststellen. Sie können diesen Code frei verwenden.

Answer 2

Für Windows würden Sie qsort_s verwenden: http://msdn.microsoft.com/en-us/library/4xc60xas(VS.80).aspx

Offenbar gibt es einige Kontroversen über BSD und GNU mit inkompatiblen Versionen von qsort_r, so vorsichtig sein, es in der Produktion Code verwendet: http://sourceware.org/ml/libc-alpha/2008-12/msg00003.html

BTW, die _s steht für "secure" und die _r steht für "reentry", aber beide bedeuten, dass es einen zusätzlichen Parameter gibt.

Answer 3

Es ist in keinem Portabilitätsstandard angegeben. Ich denke auch, es ist ein Fehler, es eine "thread-safe" Version von qsort zu nennen. Der Standard qsort ist Thread-sicher, aber qsort_r ermöglicht Ihnen effektiv, eine Schließung als Ihre Vergleichsfunktion zu übergeben.

Offensichtlich in einer single-threaded-Umgebung können Sie das gleiche Ergebnis mit einer globalen Variablen und qsort erzielen, aber diese Verwendung wird nicht Thread-sicher sein. Ein anderer Ansatz zur Thread-Sicherheit wäre, thread-spezifische Daten zu verwenden und Ihre Vergleichsfunktion ihren Parameter aus den Thread-spezifischen Daten abzurufen (pthread_getspecific mit POSIX-Threads oder __thread Variablen in gcc und dem kommenden C1x-Standard).