Casting puntatori a funzione

Question

Sto scrivendo una funzione che riceve un puntatore a una funzione di confronto e una serie di MyStructs e si suppone per ordinare l'array in base alla funzione di confronto:

void myStructSort(
        struct MyStruct *arr, 
        int size, 
        int (*comp)(const struct MyStruct *, const struct MyStruct *)) { 
    qsort(arr, size, sizeof(struct MyStruct), comp); 
} 

Purtroppo questo non viene compilato poiché qsort prevede che il comparatore riceverà gli argomenti void * e non const struct MyStruct *. Ho pensato a diverse soluzioni sbagliate e mi chiedevo quale fosse la soluzione corretta.

Opzione 1

Fusioni comp-int (*)(const void *, const void*). Compilare ma è un comportamento non definito (vedere this SO question).

Opzione 2

Creare una variabile globale int (*global_comp)(const struct MyStruct *, const struct MyStruct *) e impostare global_comp=comp all'interno myStructSort. Quindi creare una funzione:

int delegatingComp(const void *a, const void *b) { 
    return globalComp((const struct MyStruct *)a, (const struct MyStruct *)b); 
} 

E in myStructSort chiamata qsort(arr, size, sizeof(struct MyStruct), delegatingComp). Il problema con questa è la variabile globale icky.

Opzione 3

reimplementare qsort. Questa è una pratica funzionalmente sicura ma molto cattiva.

Esiste una magica quarta opzione perfetta?

Modifica

Non posso cambiare le API di myStructSort e sto compilando il mio codice utilizzando gcc c99 -Wall -Wextra -Wvla.

Answer 1

L'opzione 2 interrompe la sicurezza del thread, quindi non sceglierei quella.

L'opzione 3 è semplicemente errata come si fa notare. Non c'è motivo di re-implementare quicksort e potenzialmente commettere un errore.

L'opzione 1 è UB ma funzionerà su qualsiasi compilatore sano di mente. Se scegli questa opzione assicurati di aggiungere un commento.

Vorrei anche prendere in considerazione:

Opzione 4. ridisegnare l'interfaccia di myStructSort prendere int (*)(const void *, const void*) o rottami del tutto e chiamare qsort direttamente. In pratica, rimandalo all'architetto, perché ha fatto una pessima scelta di design.

Answer 2

l'approccio seguente funziona solo per gcc. È parte dell'estensione di GNU. inoltre si prega di riferimento per https://gcc.gnu.org/onlinedocs/gcc-4.8.5/gcc/Nested-Functions.html#Nested-Functions

prima assicuriamoci il prototipo di qsort è in such a form:

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

allora si può:

void myStructSort(
        struct MyStruct *arr, 
        int size, 
        int (*comp)(const struct MyStruct *, const struct MyStruct *)) { 
    int comparator(const void * a, const void *b) { 
    return comp((const struct MyStruct *)a, (const struct MyStruct *)b); 
    } 
    qsort(arr, size, sizeof *arr, comparator); 
} 

Ma ancora una volta, dal momento che utilizza un'estensione GNU, don' Mi aspetto troppa portabilità.

INFORMAZIONI SUL TUO COMMENTO: per il moderno gcc, lo standard gnu è predefinito al posto di quelli iso. in particolare, l'ultimo gcc deve utilizzare lo standard gnu11. quelli più vecchi utilizzano gnu89. quindi, non conosco i parametri della riga di comando, ma se -std non è impostato, funzionerà.

seguito è un esempio preso da info gcc, nel caso in cui il collegamento è morto.mostra un uso simile alla chiusura della funzione nidificata:

bar (int *array, int offset, int size) 
{ 
    int access (int *array, int index) 
    { return array[index + offset]; } 
    int i; 
    /* ... */ 
    for (i = 0; i < size; i++) 
    /* ... */ access (array, i) /* ... */ 
} 

Answer 3

Se si utilizza gcc, quindi è possibile utilizzare la funzione qsort_r in glibc dal 2.8, che consente di specificare una funzione di confronto con un argomento fornito dall'utente aggiuntivo:

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

Questo non è portatile, naturalmente, e si richiede di definire la macro funzione di test:

#define _GNU_SOURCE 

(su FreeBSD - e, presumibilmente, Mac OS X - v'è una simile, ma non compatibile qsort_r; la differenza è che l'utente - contesto contestato ent è fornito come primo argomento alla funzione di confronto, piuttosto che l'ultimo argomento)

Ma se lo avete, esso consente di evitare il mondiale in Opzione 2:.

/* This struct avoids the issue of casting a function pointer to 
* a void*, which is not guaranteed to work. It might not be 
* necessary, but I know of no guarantees. 
*/ 
typedef struct CompContainer { 
    int (*comp_func)(const struct MyStruct *, const struct MyStruct *); 
} CompContainer; 

int delegatingComp(const void *a, const void *b, void* comp) { 
    return ((CompContainer*)comp)->comp_func((const struct MyStruct *)a, 
              (const struct MyStruct *)b); 
} 

void myStructSort(
       struct MyStruct *arr, 
       int size, 
       int (*comp_func)(const struct MyStruct *, 
           const struct MyStruct *)) { 
    const CompContainer comp = {comp_func}; 
    qsort_r(arr, size, sizeof(struct MyStruct), delegatingComp, &comp); 
} 

(Live on ideone)

Answer 4

L'unica opzione ragionevole è riscrivere l'interfaccia creata o crearne una nuova.

I've done something very similar with bubble sort on another answer of mine.

In breve, con C, volete che il vostro funzione di ordinamento per essere di forma:

void* bubbleSort(void* arr, int (*compareFcn)(void*, void*), 
    size_t sizeOfElement, size_t numElements) 

E la vostra funzione di confronto per essere della forma:

int compareFunction(void *a, void *b); 

Answer 5

L'approccio corretto è quello di trasmesso da void const * a MyStruct const * nella funzione di confronto.

Questo è ben definito per il primo oggetto, perché il puntatore che è stato passato alla funzione di confronto è stato creato da un cast da MyStruct const * a void const *, e lanciando un puntatore a void al suo tipo originale è consentito (ed è davvero l'unica cosa che è).

Per gli altri membri dell'array, si presume che la fusione void const * a char const *, aggiungendo l'offset dell'oggetto, generato moltiplicando la dimensione dell'oggetto con la posizione dell'oggetto nella matrice, e colata che ritorna void const * darà un puntatore che può essere ricondotto a MyStruct const *.

Questa è un'ipotesi audace, ma di solito funziona. Potrebbero esserci casi in cui questo non funziona, ma in generale i compilatori eseguono il rilievo di qualsiasi struct foo su un multiplo del suo allineamento per garantire che gli indirizzi iniziali dei membri dell'array abbiano una distanza di sizeof(struct foo).

Casting puntatori a funzione è generalmente pericoloso e deve essere evitato, come diversi tipi di dati possono avere rappresentazioni diverse - per esempio, un void * devono essere in grado di esprimere ogni indirizzo possibile in quanto avrebbe potuto essere convertito da un char *, mentre a MyStruct * è garantito che alcuni dei bit meno significativi siano chiari come qualsiasi oggetto valido sarebbe allineato, quindi è del tutto possibile che la convenzione di chiamata per questi tipi possa essere diversa.