Fino a questo punto del corso di linguaggio C abbiamo sempre lavorato con variabili e array la cui dimensione era decisa nel momento in cui scrivevamo il codice. Funziona, ma prima o poi ci si scontra con un problema molto concreto: cosa succede quando la quantità di dati da gestire si scopre solo durante l’esecuzione del programma? Lo avevamo già sfiorato leggendo file con un numero di valori non noto a priori, e la soluzione adottata allora era definire un numero massimo di elementi e dimensionare un array su quel valore. Una strada poco efficiente, che spreca memoria e introduce un limite artificiale che spesso non ha nulla a che vedere con il problema reale.

La risposta del C a questa esigenza è l’allocazione dinamica della memoria: chiedere al sistema, mentre il programma è in esecuzione, esattamente lo spazio che serve, usarlo e poi restituirlo. È un argomento che ho lasciato volutamente nella parte più avanzata del corso, perché poggia interamente sui puntatori, ed è anche la base delle strutture dati che vedremo nei prossimi episodi.

Un nuovo ambiente di lavoro: CLion

Da questo episodio in poi gli esempi sono sviluppati in locale con CLion, l’ambiente di sviluppo scelto nella puntata precedente dopo aver visto come installare una toolchain su Windows, Linux o Mac. Chi preferisce può continuare a usare OnlineGDB, che resta adatto a quanto faremo; se arriveremo ad argomenti che richiedono un ambiente locale, lo segnalerò.

Il passaggio porta con sé alcuni vantaggi evidenti già in questo video: un autocompletamento molto più evoluto, capace di intuire con buona precisione cosa si sta per scrivere, e suggerimenti come la visualizzazione dei nomi dei parametri delle funzioni di libreria, che il C di per sé non prevede. Nel video si vede anche come adattare lo stile di formattazione alle proprie preferenze, per esempio la posizione della parentesi graffa di apertura, che personalmente preferisco a fianco della dichiarazione della funzione piuttosto che sulla riga successiva: è un’impostazione che si trova nelle opzioni di code style per C e C++.

Come è organizzata la memoria di un programma

Per capire dove finiscono i dati che allochiamo, conviene guardare come viene disposto in memoria un programma C quando è caricato in RAM, la memoria di lavoro che contiene sia il codice da eseguire sia i dati su cui opera. Nella parte bassa c’è il codice, cioè il linguaggio macchina generato dal compilatore per il processore su cui stiamo lavorando. Sopra si trovano le aree dei dati, e infine una zona condivisa tra due strutture che crescono una verso l’altra: lo stack e lo heap. Quando i due arrivano a toccarsi, il programma ha esaurito la memoria a sua disposizione.

Su questa mappa si collocano i tre tipi di allocazione che il C mette a disposizione:

• allocazione statica: si ottiene con le variabili globali o con la parola chiave static, è definita in fase di compilazione e risiede nell’area dati per tutta la durata del programma;
• allocazione automatica: è quella delle normali variabili locali delle funzioni, main compreso, senza static. È definita in compilazione ma vive nello stack, che cresce quando si entra in una funzione e si riduce quando se ne esce. Uscendo dalla funzione la variabile scompare, e rientrandovi non possiamo contare sul fatto che abbia mantenuto il valore precedente;
• allocazione dinamica: è quella richiesta esplicitamente dal programma a runtime, e finisce nello heap.

Questa visione spiega anche qualcosa che avevamo incontrato parlando di ricorsione: ogni chiamata di una funzione ricorsiva alloca nello stack una nuova porzione di memoria per le proprie variabili. È il meccanismo che fa funzionare la ricorsione, ma è anche il motivo per cui una ricorsione senza limite finisce per esaurire lo stack e mandare in crash il programma.

Sia la memoria automatica sia quella dinamica vengono di fatto gestite a runtime. La differenza è che la prima è amministrata dai meccanismi predisposti dal compilatore, mentre la seconda è sotto il nostro controllo diretto. Ed è qui che sta tutta la responsabilità.

Una gestione completamente manuale

Molti linguaggi più moderni usano anch’essi memoria dinamica, ma la mascherano allo sviluppatore con meccanismi automatici o semiautomatici, come il garbage collector. Il C non ha nulla di tutto questo: la gestione è interamente a carico di chi scrive il codice. Questo significa tre cose:

• quando chiediamo memoria al sistema, siamo noi a doverla restituire quando non ci serve più;
• se il sistema ci concede 10 byte, dobbiamo usarne esattamente 10. Andare oltre significa scrivere in una zona che non ci appartiene, con effetti che dipendono da piattaforma e sistema operativo: un crash nei casi più comuni, oppure, peggio, la sovrascrittura silenziosa di altre variabili del programma o di aree ancora più delicate;
• dobbiamo essere pronti a gestire il caso in cui la memoria richiesta non sia disponibile, decidendo se terminare con un messaggio d’errore o provare una strada alternativa, a seconda del programma.

malloc: chiedere memoria al sistema

La funzione per allocare memoria è malloc, che fa parte della libreria standard e richiede l’inclusione di stdlib.h. Riceve un parametro di tipo size_t, il numero di byte richiesti, e restituisce un puntatore void *, cioè un puntatore generico che può essere assegnato a un puntatore di qualunque tipo.

Due buone abitudini accompagnano sempre la chiamata. La prima è usare sizeof per calcolare la dimensione da richiedere, lasciando al sistema il compito di sapere quanti byte occupa un certo tipo su quella piattaforma. La seconda è il cast esplicito al tipo di puntatore che ci serve: spesso il compilatore lo dedurrebbe da solo, ma renderlo esplicito rende il codice più chiaro e sicuro. Una volta ottenuto un puntatore tipizzato, tutta l’aritmetica dei puntatori funziona come già sappiamo, senza doverci preoccupare di quanti byte occupi un intero.

Il punto da non dimenticare è il valore di ritorno: se nello heap non c’è spazio sufficiente, malloc restituisce NULL. Verificarlo prima di usare il puntatore è fondamentale, altrimenti il primo accesso porterà a un errore di puntatore nullo.

free, calloc e realloc

La funzione gemella di malloc è free, che riceve il puntatore restituito in precedenza e comunica al sistema che quella memoria può essere riutilizzata. Va usata solo su memoria allocata dinamicamente: chiamarla sul puntatore di una variabile statica o automatica ha un comportamento non definito, oltre a non avere alcun senso dal punto di vista concettuale. Dopo la free è buona norma, pur non obbligatoria, assegnare NULL al puntatore, e controllare che un puntatore non sia nullo prima di usarlo. Prevenire queste condizioni costa molto meno che andare a capire a posteriori dove e perché un programma si è piantato.

Non liberare la memoria che non serve più è invece un errore logico che il sistema non segnalerà mai: il memory leak. Immaginiamo una funzione ricorsiva che alloca memoria a ogni chiamata senza mai liberarla: alla risalita perderemo traccia dei puntatori e quella memoria resterà occupata per tutta la vita del programma, fino a una possibile saturazione. In un sistema operativo multitasking, dove la memoria è una risorsa condivisa tra tutte le applicazioni, un programma che non rilascia ciò che non usa penalizza l’intero sistema. È proprio per eliminare questo rischio che i linguaggi più recenti hanno scelto la gestione automatica.

Completano il quadro altre due funzioni, meno frequenti ma utili da conoscere:

• calloc riceve il numero di elementi e la dimensione di ciascuno, quindi è pensata per allocare array. A differenza di malloc garantisce che la memoria sia inizializzata a zero, al prezzo di un piccolo overhead: conviene usarla solo quando serve davvero;
• realloc ridimensiona un blocco già allocato. In caso di aumento i dati esistenti vengono conservati, ma poiché la memoria restituita è sempre contigua, il sistema potrebbe dover copiare tutto il blocco in un’altra zona dello heap, con un costo in termini di tempo. In caso di riduzione non c’è overhead, ma i dati in eccesso vanno persi.

Dagli esempi alle strutture collegate

Nel video si passano in rassegna alcuni casi tipici: l’allocazione di un singolo float, quella di una struct che rappresenta una coordinata bidimensionale, dove sizeof evita di dover calcolare a mano l’occupazione della struttura, e un array di cento interi, che si può poi scorrere con la consueta notazione con le parentesi quadre, equivalente all’aritmetica dei puntatori.

L’esempio più interessante, però, è un’anticipazione dei prossimi episodi: una struttura che contiene un valore intero e un puntatore a una struttura dello stesso tipo. Allocando dinamicamente due nodi, assegnando a ciascuno un valore e facendo puntare il primo al secondo e il secondo a NULL, si ottiene una piccola catena di elementi collegati. Messo in pratica su CLion, completo di controllo sull’esito delle allocazioni e delle relative free, l’esempio mostra come un unico ciclo while possa percorrere tutta la catena seguendo i puntatori fino a incontrare NULL. È l’idea alla base delle liste, e più in generale di strutture come alberi e grafi.

L’esercizio: ordinare un file di interi di dimensione sconosciuta

L’esercizio della puntata mette insieme quanto visto: leggere da un file di testo una serie di interi con segno separati da virgola, di cui non conosciamo né il numero né un limite massimo, ordinarli in modo crescente e scriverli in un altro file.

La strategia è in due passaggi. Si apre il file in lettura, verificando che l’apertura sia andata a buon fine, e lo si scandisce una prima volta con fscanf all’interno di un ciclo do while che prosegue finché la funzione trova elementi, limitandosi a contarli. Nel file di prova gli elementi risultano 501. A quel punto rewind riporta la lettura all’inizio del file, si alloca con malloc un array di interi della dimensione esatta, si controlla che il puntatore non sia nullo e si rilegge il file, questa volta riempiendo l’array.

Un dettaglio su cui vale la pena soffermarsi riguarda la gestione degli errori: se l’allocazione fallisce, prima di uscire va chiuso il file già aperto. In questo caso il programma termina comunque e il sistema libererebbe tutto da solo, ma in altri contesti l’errore non chiude il programma, e abituarsi a rilasciare tutto ciò che si è allocato quando si devia dal flusso regolare è una disciplina che ripaga. Del resto il meccanismo di fopen e fclose è concettualmente lo stesso di malloc e free: si ottiene una risorsa e la si restituisce quando non serve più.

Per l’ordinamento, invece di riutilizzare uno degli algoritmi visti nei video dedicati, si sfrutta qsort della libreria standard, che implementa il Quicksort e richiede il puntatore all’array, il numero di elementi, la dimensione di ciascuno e una funzione di confronto. Quest’ultima riceve due puntatori void, li converte in puntatori a interi costanti e restituisce un valore negativo, zero o positivo a seconda dell’ordine dei due elementi. Il file di uscita, scritto con un valore per riga, contiene così i numeri ordinati da -997 a 998.

Cosa aspettarsi

L’allocazione dinamica è uno degli aspetti più importanti e insieme più delicati del C. L’esercizio ne mostra l’uso più immediato, dimensionare un array solo quando se ne conosce l’effettiva necessità, ma il potenziale vero emerge con le strutture collegate tra loro tramite puntatori: liste, alberi e grafi saranno l’argomento dei prossimi episodi del corso.

Per vedere lo sviluppo completo del codice su CLion, dall’esempio con i nodi collegati all’esercizio con qsort, il video di questa settimana è disponibile sul canale.