frammenti di razionalità

Nel post precedente ho parlato di come poter usar i void* in C come tipi generici da usare per render estremamente flessibile le funzioni e il codice in generale; ho parlato pure dellla funzione qsort della libreria standard del C che è l’esempio più concreto di come si possa fare uso dei void*.

In questo post scendo nei particolari del problema mettendo a vostra disposizione il codice di una mia implementazione generica del quicksort. Premetto che non mi soffermerò sull’algoritmo in se, visto che su internet ci sono abbondanti trattazioni al riguardo.

Ecco il blocco di codice:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//prototipi delle funzioni
typedef int (*compare_function)(const void*,const void*); 

void generic_quicksort(void *v, int i, int f, size_t size, compare_function compare);
void generic_swap(void *a, void *b, size_t size);
int generic_partition(void *v, int i, int f, size_t size, compare_function compare);

//funzione di confronto
int compare_int(const void*,const void*); 

int main(){
	int v[]={5,4,3,2,1};

	int n=sizeof(v)/sizeof(int);

	generic_quicksort((void*),0,n-1,sizeof(int),compare_int);

	return 0;
} 

int compare_int(const void *a, const void *b){
	return *((int*)a)-*((int*)b);
} 

void generic_quicksort(void *v, int i, int f, size_t size, compare_function compare){
    if(i>=f)
        return;

    int p=generic_partition(v,i,f,size,compare);

    generic_quicksort(v,i,p-1,size,compare);
    generic_quicksort(v,p+1,f,size,compare);

}

void generic_swap(void *a, void *b, size_t size){
    void *tmp=malloc(size);

    memcpy(tmp,a,size);
    memcpy(a,b,size);
    memcpy(b,tmp,size);

    free(tmp);
}

int generic_partition(void *v, int i, int f, size_t size, compare_function compare){
    void *x=malloc(size);

    memcpy(x,v+(i*size),size);

    int inf=i;
    int sup=f+1;

    while(1){
        do
            inf++;
        while(compare(v+(inf*size),x)<=0 && inf<=f);

        do
            sup–;
        while(compare(v+(sup*size),x)>0);

        if(inf<sup)
            generic_swap(v+(inf*size),v+(sup*size),size);

        else
            break;
    }

    generic_swap(v+(i*size),v+(sup*size),size);

    free(x);

    return sup;
}

La funzione generic_quicksort prende come argomento:

• un void* che puterà al vettore da ordinare;
• gli indici del primo e dell’ultimo elemento dell’array da ordinare;
• la dimensione size di ogni element dell’array;
• un puntatore a funzione che servirà per comparare gli elementi del vettore;

I parametri size e compare sono fondamentali. Avendo a che fare con un tipo non definito, è necessario conoscer la dimensione in byte di ogni elemento dell’array per poter acceder ad ognuno di essi attrverso l’aritmetica dei puntatori; la funzione di comparazione è indispensabile sia perchè senza di essa non potremmo fare alcun confronto tra tipi generici, sia perchè rende ancor più flessibile il nostro algoritmo di ordinamento (l’uso di una funzione di comparazione ci permette di definire la relazione d’ordine tra gli elementi dell’array secondo le nostre esigenze).

Le cose più interessanti si trovano nella funzione generic_partition, dove si vede chiaramente l’approccio “a basso livello” necessario per gestire la situazione. Dato che i void* non possono esser dereferenziati, l’unico modo per acceder agli elemnti del vettore è tramite il loro indirizzo. Nell’utilizzare l’aritmetica dei puntatori occore usare la dimensione del tipo di dato, passata come parametro alla funzione, per incrementare in maniera corretta il puntatore.

Di solito, quando si usano i puntatori ai tipi definiti (int ,double….), l’incremento del puntatore di uno comporta uno spostamento in memoria di “sizeof(type)” bytes. Nel caso dei void* occorre specificare “manualmente” tale scostameto; un incremento di uno per un puntatore a void comporta uno spostamento in memoria di un solo byte.

Altra cosa che occorre per la gestione a basso livello della memoria è l’uso delle funzioni della classe mem*, come la memcpy, che permettono di manipolare porzioni di byte semplicemente specificandone dimensione e indirizzo.

Il prototipo della memcpy è il seguente:

#include <string.h>

void memcpy(void *a, const void *b, size_t size);

Tale funzione copia “size” bytes puntati da b all’indirizzo puntato da a.L’implementazione di “funzioni generiche” in C necessita un controllo a basso livello della memoria da parte del programmatore; se da un lato questo può esser particolarmente stimolante (io mi diverto un casino!), dall’altro richiede molta attenzione (la segmentation fault è sempre dietro l’angolo se non si fanno gli opportuni controlli!).Enjoy……….