Oggi ho finalmente dato l’esame che preparavo da due settimane, Laboratorio di algoritmi e strutture dati (per chi se lo stesse chiedendo, esiste solo per gli immatricolati prima del 2005/2006). Voto superiore alle mie aspettative, perchè il progettino richiesto… ecco, per farla breve, non funzionava. Ma avevo studiato la teoria e ho capito da solo i miei errori nella pratica, e questo mi è valso la promozione e un voto accettabile, anzi buono, tutto sommato.

Il progettino in questione prevedeva di implementare, in C o C++, l’algoritmo di Kosaraju per trovare le componenti fortemente connesse di un grafo orientato. Diviso in 4 parti: lettura dei dati da un file e implementazione delle strutture dati necessarie, implementazione della visita in profondità (DFS) sul grafo, creazione del grafo trasposto, isolamento delle componenti fortemente connesse. Corrispondono grosso modo ai passi dell’algoritmo, che consiste in:

• Dato un grafo, effettuarne una DFS;
• Creare il grafo trasposto;
• Effettuare una DFS del grafo trasposto, visitando i vertici nell’ordine di fine visita decrescente dato dalla prima DFS;
• Isolare gli alberi DFS dell’ultima visita, che risultano essere le componenti fortemente connesse.

L’implementazione di questi algoritmi è di per sé facile, una volta conosciute le basi del linguaggio. Non serve altro che tradurre in C (o C++) l’algoritmo in pseudocodice presentato nell’ottimo libro Introduzione agli algoritmi e strutture dati di Cormen, Leiserson, Rivest e Stein, una vera bibbia per trovare velocemente tutto ciò che c’è da sapere sugli algoritmi e le strutture di dati elementari (si parla di astrazioni naturalmente, non dell’implementazione in un particolare linguaggio).

I problemi vengono a monte, quando si tratta di implementare la struttura dati necessaria, soprattutto per me che da troppo poco tempo mastico il linguaggio C.

Questo potente strumento di programmazione, con tutta la sua libertà, ha uno svantaggio: non gestisce automaticamente la memoria del sistema, ma ne affida la gestione completamente al programmatore. Che, nel mio caso, può essere inesperto, non sapere esattamente come funzionano le cose e trovarsi davanti ad errori del tutto inaspettati e a prima vista incomprensibili.

Ogni variabile che non sia di un tipo primitivo di dati, dev’essere allocata: bisogna, con un comando esplicito (cioè malloc e le sue varianti calloc e realloc), dichiarare che si vuole riservare X bytes di memoria per quell’oggetto. Alla fine dell’utilizzo, è buona norma liberare la memoria così riservata, con il comando free. Se non lo si fa, si rischia di “scrivere dove non si dovrebbe” (parole del mio professore di Laboratorio di algoritmi). Stesso discorso se si alloca la quantità sbagliata di memoria o se si usa più memoria del previsto, andando, per esempio, fuori dei confini di un array. Supponiamo di avere allocato spazio per 10 caratteri, assegnati a una variabile name di tipo char *, usando regolarmente una malloc:

E ora, supponiamo di aver dichiarato, per esempio, un array di int, numbers[], senza dichiararne la dimensione e dimenticando di allocare la memoria necessaria, riempendolo volta per volta. Come può benissimo accadere, il primo valore, numbers[0] (ogni int occupa una parola di 4 bytes, qui sto rappresentando i bytes come caratteri ASCII) non è molto distante dal blocco di memoria puntato da name.

Ora, ecco cosa succede se assegno qualche valore a numbers[1] e numbers[2]:

E infine, assegnando un valore anche a numbers[3]:

E’ successo un guaio: i valori per cui non era stato allocato spazio, scritti su blocchi di memoria contigui, sono andati a sovrascrivere parte del mio nome, che credevo memorizzato al sicuro nella variabile name. Per evitare questo problema, sarebbe stato sufficiente dichiarare la dimensione dell’array, o allocare una dimensione massima (ad esempio 1024 bytes), o ancora mantenere un indice che segnalasse la dimensione corrente dell’array e riallocasse lo spazio (con realloc), secondo il bisogno. C’è più di un modo per gestire efficacemente la memoria in C, l’importante è non trascurare questo aspetto della programmazione.

Il prototipo della funzione standard per allocazione di memoria è void *malloc(size_t size). Per utilizzarla con successo, bisogna ricordare che:

1. malloc restituisce un puntatore a void che deve essere esplicitamente convertito nel tipo della variabile per cui allocare memoria;
2. Bisogna allocare la giusta quantità di memoria, altrimenti si va incontro agli errori di cui ho parlato prima.

Adempiere al secondo punto è importante. Di solito si usa la funzione sizeof(...) con, come parametro, il tipo di dato che la variabile allocata conterrà. Non so quanto sia banale, ma è un errore che ho ripetuto spesso, prima di rendermi conto cosa stavo facendo. Se si alloca un puntatore a char, bisogna richiedere spazio per char; se si alloca una variabile di tipo Node, definito come struct _node *, bisogna richiedere spazio per struct _node, e così via. Un errore come quello precedentemente descritto, porta a perdere la metà di una stringa; errori del genere con variabili più complesse e di maggiori dimensioni, porta a errori di paginazione, corruzione dello heap, sovrascrittura della memoria di sistema, vulnerabilità nel programma, cecità, tumori e morte.

In definitiva, ho capito che programmare in C richiede disciplina, forse più degli altri linguaggi. Tutto considerato, posso dire che finora mi è andata bene!