Qsort e puntatori

L'intento di questo testo è completare la spiegazione fornita durante l'ultima lezione di laboratorio (venerdì 25 gennaio 2008) a proposito del casting di puntatori in relazione all'uso di qsort, nella speranza di chiarire definitivamente i dubbi espressi da alcuni studenti.

Esercizio: ordinamento di un vettore di stringhe

Consideriamo il seguente programma, che ordina un array di stringhe:

1:    #include<stdio.h>
2:    #include<stdlib.h>
3:    #include<string.h>
4:
5:
6:    /* compar_str confronta due puntatori a void assumendo che puntino a stringhe */
7:    int compar_str ( const void *p, const void *q ) {
8:      return strcmp( *( char ** ) p, *( char ** ) q ) ;
9:    }
10:
11:   /* programma che ordina un array di stringhe */
12:   int main( void ) {
13:
14:     char * a[] = { "vio", "abi", "car", "aaa" };
15:     int n = 4, i;
16:
17:     qsort( a, n, sizeof( a[0] ), compar_str );
18:
19:     for ( i = 0; i < n; i++ )
20:       printf( "%s\n", a[i] );
21:
22:     return 0;
23:   }

Osservate che la chiamata di qsort alla riga 17 ha l'effetto di ordinare il vettore a, usando la funzione compar_str come funzione di confronto tra gli elementi di a.

Definizione della funzione compar_str

In coerenza con quanto previsto dal prototipo di qsort, la funzione compar_str ha prototipo

      int compar_str( const void *p, const void *q )
(vedi riga 8). Tale funzione riceve come argomenti due puntatori a void e ha l'obiettivo di confrontare gli oggetti puntati da tali puntatori. Per come è fatta qsort, siamo costretti ad essere vaghi e dichiarare genericamente i due argomenti come puntatori a void, anche se sappiamo che la applicheremo sempre a puntatori a stringhe!!

Ora, l'idea è quella di definire compar_str sfruttando l'usuale funzione di confronto tra stringhe, ovvero strcmpr, che però ha prototipo:

      int strcmp( const char *s1, const char *s2 )

Come fare? Osservate che gli argomenti da passare a strcmp sono esattamente gli oggetti puntati da p e q, ovvero *p e *q. Tuttavia non è possibile passare a strcmp proprio *p e *q, poichè questi sono oggetti di tipo void, mentre strcmp si aspetta oggetti di tipo char *. Pertanto, prima di deferenziare, è necessario fare il cast di p e q, forzandoli ad essere non semplicemente puntatori a void, ma puntatori a char *, ovvero oggetti di tipo char **.

Ripetendo schematicamente:

In conclusione si ottiene la chiamata di strcmp come nella riga 8.

Prima variante -sbagliata!- della funzione compar_str

Notate che il casting di p e q è necessario. Se sostituissimo la chiamata in riga 8 con la chiamata
        return strcmp( *p, *q )
in fase di compilazione otterremmo un errore del tipo
    qsort_str_sbagliato3.c:8: error: invalid use of void expression
poich è *p e *q sono oggetti di tipo void.

Seconda variante -sempre sbagliata!- della funzione compar_str

Consideriamo la seguente definizione alternativa di compar_str:

      /* compar_str confronta due puntatori a void assumendo che puntino a stringhe  */
      /* versione sbagliata!!! */
      int compar_str( const void *p, const void *q ) {
        return strcmp( ( char * ) p, ( char * ) q ) ;

I programma viene compilato correttamente, infatti è facile verificare che, dal punto di vista dei tipi, tutto fila: p e q sono puntatori a void che vengono promossi a puntatori a char con il casting; e strcmp vuole come parametro due puntatori a char, quindi nessun problema di incompatibilità.

Tuttavia, il programma non funziona correttamente. Sostanzialmente, il motivo sta nel fatto che è necessario dereferenziare p e q nella chiamata di strcmp.

Più esplicitamente, la funzione strcmp deve ricevere i due oggetti da ordinare, che non sono p e q, bensì gli oggetti da essi puntati, ovvero *p e *q; questi sono dunque gli argomenti che bisogna passare a strcmp, dopo averli forzati ad essere del tipo giusto.

Per semplificare, potete pensare che, dal punto di vista dell'argomento effettivamente passato, la chiamata

        strcmp( ( char * ) p, ( char * ) q )
equivale alla chiamata
        strcmp( p, q )
ma entrambe sono sbagliate in quanto è necessario dereferenziare.

E se dichiarassimo a come array di array di char?

Consideriamo ora un'altra variante del programma precedente, ottenuta sostituendo la riga 14 con la seguente:

      char a[][5] = { "vio", "abi", "car", "aaa" };
Questo significa che a non è più dichiarato come array frastagliato, ma come array bidimensionale.

Affinchè il programma funzioni correttamente, è necessario modificare la funzione compar_str. Infatti, la funzione qsort chiama compar_str passandogli come argomenti p e q due elementi di a, ovvero due array di caratteri. Questi due array sono proprio gli oggetti da ordinare, e quindi sono proprio p e q che devono essere passati a strcmp nella chiamata di riga 8. In questo caso, quindi, non c'è bisogno di dereferenziare p e q e la chiamata corretta diventa la seguente:

    strcmp( p, q );

E' possibile anche esplicitare la conversione di tipo, usando:
    strcmp( (char *) p, (char *) q );