Dans quelle mesure la fonction qsort_r réentrante est-elle portable par rapport à qsort?

Question

qsort_r() est la version ré-entrante de qsort() qui prend un argument 'thunk' supplémentaire et le passe dans la fonction de comparaison et j'aimerais pouvoir l'utiliser dans le code C portable. qsort() est POSIX et partout, mais qsort_r() semble être une extension BSD. En tant que question spécifique, cela existe-t-il ou a-t-il un équivalent dans le runtime de Windows C?

Answer 1

J'ai essayé d'écrire une version portable de qsort_r/qsort_s (appelée sort_r) montrée avec un exemple. J'ai aussi mis ce code dans un git (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 
} 

Exemple d'utilisation:

#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/sortie:

$ 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 

Je l'ai testé sur mac & linux. Veuillez mettre à jour ce code si vous repérez des erreurs/améliorations. Vous êtes libre d'utiliser ce code comme vous le souhaitez.

Answer 2

Pour Windows vous utilisez qsort_s: http://msdn.microsoft.com/en-us/library/4xc60xas(VS.80).aspx

Apparemment, il y a une certaine controverse à propos de BSD et GNU ayant des versions incompatibles de qsort_r, alors faites attention à l'utiliser dans le code de production: http://sourceware.org/ml/libc-alpha/2008-12/msg00003.html

BTW, la _s signifie "sécurisé" et le _r signifie "rentrant", mais les deux signifient qu'il y a un paramètre supplémentaire.

Answer 3

Il n'est spécifié dans aucune norme de portabilité. Aussi je pense que c'est une erreur de l'appeler une version "thread-safe" de qsort. La norme qsort est thread-safe, mais qsort_r vous permet effectivement de passer une fermeture comme fonction de comparaison. Il est évident que dans un environnement monothread, vous pouvez obtenir le même résultat avec une variable globale et qsort, mais cette utilisation ne sera pas adaptée aux threads. Une approche différente de la sécurité des threads consisterait à utiliser des données spécifiques aux threads et à récupérer les paramètres spécifiques des threads (pthread_getspecific avec les threads POSIX, ou __thread variables dans gcc et la prochaine norme C1x).