Precedente Principale Sommario Informazioni Redazione Browser Successivo

Rubrica Programmazione C e C++ Coordinamento di Francesco Sileno

Nei dintorni di malloc

di Stefano Casini


Introduzione

La possibilità di allocare dinamicamente la memoria è una delle caratteristiche che rende versatile e potente il linguaggio C: richiede però una buona conoscenza del linguaggio, perchè un utilizzo sbagliato porta facilmente ad effetti disastrosi, sia sul programma che stiamo eseguendo sia, in ambienti multitasking non protetti tipo Windows 3.1 e Windows 95, sul sistema operativo stesso. In linea del tutto generale, ogni operazione di allocazione dinamica restituisce il puntatore al blocco di memoria che il compilatore alloca a run-time; in teoria, questo blocco diventa di nostra esclusiva proprietà, e nessun altra applicazione può leggere o scriverci dentro; quando non ci serve più, dobbiamo avvertire il compilatore di liberare la memoria, cosicchè possa essere utilizzata da altre applicazioni. Alcuni sistemi operativi, tra cui Windows, offrono la possibilità di spostare i blocchi allocati "a pelle di leopardo" nella mappa di memoria in maniera tale da rendere più efficaci le operazioni di allocazione successiva, in maniera del tutto trasparente (o quasi) per il programmatore. La memoria non è infinita, per cui è buona norma controllare la buona riuscita di ogni operazione di allocazione dinamica, prima di utilizzarne il puntatore restituito.


La rubrica telefonica: un dramma in più atti

Un giorno Eugenio, programmatore ingenuo, comprò una rubrica telefonica di quelle a fogli fissi, la aprì alla lettera C, scrisse "Colleghi di lavoro:" ed iniziò ad inserire i dati dei propri colleghi; poichè lavorava in una grande e seria azienda, aveva così tanti colleghi che ben presto saturò la lettera C della rubrica: dovette comprarne una più grossa, sempre a fogli fissi, e riscrivere tutti gli indirizzi. Nel frattempo, però, l'azienda diventava sempre più grande e sempre meno seria, per cui non c'era più posto nell'agenda per i nomi dei nuovi colleghi, e fu di nuovo sostituita: quando poi l'azienda dovette assumere centinaia di persone per eliminare i bug dell'ultimo, rivoluzionario prodotto, un sistema operativo a 24 bit (mezzo 16 e mezzo 32 uguale 24), l'agenda di Eugenio assunse le dimensioni ed il peso di un volume della Treccani. Ogni lettera conteneva 100 pagine, per un totale di 2600 pagine, il 90% delle quali inutilizzate: con 1200 indirizzi sotto la lettera C, 1 sotto la lettera M (Mamma), ed 1 sotto la lettera F (Fidanzata): le lettere X, Y, W erano desolatamente vuote, essendo difficile conoscere persone con queste iniziali. Quando poi il padrone dell'azienda si mise in testa di produrre un web browser migliore di Netscape, importando programmatori persino dalla Cina, per Eugenio fu il collasso.


La rubrica telefonica: una soluzione dinamica

Per fortuna Alberto, programmatore esperto, fornì ad Eugenio una dritta: "Compra una rubrica a fogli mobili, così puoi inserire per ogni lettera solo le pagine effettivamente necessarie!". In questo modo Eugenio potè inserire i nomi di tutti i nuovi colleghi, anche quelli che furono assunti per sviluppare GNAM2000, il nuovissimo velocissimo sistema operativo a 128 bit che avrebbe mantenuto però la compatibilità con il DOS, con il MAC, con Amiga ed anche col Televideo RAI.


Morale della favola

Quello che la parabola insegna è che bisogna sapere a priori il numero massimo di oggetti che devono entrare in un contenitore, prima di dimensionare il contenitore: è poi importante sapere se il contenitore sarà sempre e comunque riempito, o se viceversa sarà quasi sempre vuoto; solo così potremo scegliere oculatamente tra un contenitore di dimensioni fisse ed uno a dimensione variabile: il primo caso corrisponde alla dichiarazione statica di variabili, il secondo corrisponde all'allocazione dinamica delle stesse. In breve, quello che si fa a livello logico è: allocazione dinamica della memoria, operazioni sul contenuto delle celle di memoria allocate, eventuale aumento o diminuzione (riallocazione) delle celle di memoria, liberazione della memoria quando non è più necessaria; fisicamente, il compilatore va a cercare nella mappa di memoria un blocco di celle che abbia la dimensione da noi richiesta nell'operazione di allocazione: quando lo trova, lo marca in maniera che risulti "occupato" per altre richieste, e restituisce al programma un puntatore con l'indirizzo della prima cella di memoria del blocco; il programma potrà, utilizzando il puntatore, accedere in lettura e scrittura alle celle del blocco; quando poi il programma chiama la funzione di deallocazione, il compilatore toglie il segnale di "occupato" alle celle del blocco di memoria, che ridiventano così disponibili. Come si vede, il meccanismo è simile a quello di allocazione statica delle variabili esaminato nell'articolo "Chi ha paura dei puntatori?" (BETA 1/96), con la differenza che nell'allocazione dinamica la memoria non viene liberata automaticamente dal compilatore, ma solo su ordine esplicito del programmatore, ed inoltre spetta al programmatore controllare che le operazioni di scrittura e lettura non debordino all'esterno del blocco allocato. Questi infatti sono gli errori più comuni: andare ad operare, utilizzando male il puntatore, su celle di memoria non allocate o magari su celle allocate da altri programmi, oppure dimenticarsi di liberare la memoria. Ecco un esempio molto schematico di come procedere:

void EsempioAllocazioneDinamica(void)
{
     char * dinamicmemory;
     /* variabile allocata staticamente di tipo puntatore a caratteri */
     unsigned int memorysize;
     /* dimensioni del blocco di memoria da allocare */

    dinamicmemory = malloc(memorysize);
    /* allochiamo dinamicamente la memoria di cui abbiamo bisogno */
    if(dinamicmemory == NULL)
	return;
    /* controlliamo se l'allocazione dinamica di memoria ha avuto successo */

    UtilizzaLaMemoria(dinamicmemory, memorysize);
    /* scriviamo qualcosa nella memoria allocata dinamicamente */

    free(dinamicmemory);
    /* liberiamo la memoria allocata dinamicamente */
}

void UtilizzaLaMemoria(char * dinamicmemory, unsigned int memorysize)
{
    unsigned int i;

    for(i = 0; i < memorysize; i++)
	dinamicmemory[i] = 'A' + (i % 26);
    /* scriviamo le lettere dell'alfabeto nella memoria */
    /* allocata dinamicamente */
}

Come noto, dal solo puntatore non è possibile ottenere informazioni sulla dimensione del blocco di memoria puntata: per questo motivo alla funzione che utilizza la memoria è stato passato come parametro anche la dimensione del blocco, cosicchè si è stati in grado di controllare fino a quale cella di memoria scrivere. I nuovi linguaggi object-oriented, quali C++ e Java, sono strutturati in modo tale che l'allocazione dinamica di un oggetto permette di inserire, tra le proprietà dell'oggetto stesso, la sua dimensione. Inoltre è presente in alcuni casi un meccanismo di garbage collection che esegue l'operazione di deallocazione della memoria quando l'oggetto viene distrutto anche se il programmatore dimentica di farlo.


Costruiamo un array evoluto

Vediamo adesso di fare un esempio per tutti coloro che utilizzano il vecchio C del tentativo di oggettizzare un array; basterà adottare un semplice trucco: i primi 2 (o 4, a seconda del sistema operativo) byte della memoria allocata per l'array conterranno la dimensione dell'array, mentre i byte successivi conterranno i valori dei singoli elementi.

#define OFFSET sizeof(unsigned int)

void main(void)
{
    char * dinamicarray;
    unsigned int dimensione = 8;

    dinamicarray = AllocazioneArray(dimensione, sizeof(char));
    if(!dinamicarray)
	return;
    /* allocazione dinamica di un array di 8 caratteri */

    RiempiArray(dinamicarray);
    /* carichiamo i dati nell'array */
	
    StampaArray(dinamicarray);
    /* stampiamo l'array, solo i caratteri per= */

    LiberazioneArray(dinamicarray);
    /* liberiamo la memoria allocata per l'array */
}

char * AllocazioneArray(unsigned int dimensione, int typesize)
{
    unsigned int arraysize = 0;
    char * dinamicarray;
	
    arraysize = dimensione * typesize + OFFSET;
    /* calcoliamo il numero di elementi veri dell'array
    aggiungendo i byte necessari per contenere le informazioni 
    sulla dimensione dell'array */
	
    dinamicarray = malloc(arraysize);
    /* allochiamo la memoria per contenere l'array 
    e le altre informazioni */
	
    if(!dinamicarray)
	return NULL;
	
    ((unsigned int *)dinamicarray)[0] = dimensione;
    /* scriviamo nei primi byte 
    dell'array la sua dimensione */
	
    return dinamicarray;
}

void RiempiArray(char * dinamicarray, char startchar)
{
    unsigned int dimensione = 0;
    unsigned int i = 0;   
    char * iniziodati;                      
		
    dimensione = ((unsigned int *)dinamicarray)[0];
    iniziodati = dinamicarray + OFFSET;
    if(iniziodati == NULL)
	return;
    /* ricaviamo la dimensione dell'array
    ed il puntatore all'inizio dei dati */
		
    for(i = 0; i < dimensione; i++)
	iniziodati[i] = startchar + (i % 26);
    /* carichiamo le lettere dell'alfabeto nell'array */

    iniziodati[dimensione - 1] = '\0';
    /* chiudiamo con un NULL byte l∆array */
}

void StampaArray(char * dinamicarray)
{
    unsigned int dimensione = 0;
    char * iniziodati;                      
		
    dimensione = ((unsigned int *)dinamicarray)[0];
    iniziodati = dinamicarray + OFFSET;
    if(iniziodati == NULL)
	return;
    /* ricaviamo la dimensione dell'array
    ed il puntatore all'inizio dei dati */
	
    printf("%u\r\n", dimensione);
    printf("%s", iniziodati);
    /* stampiamo l'array di caratteri */
}

void LiberazioneArray(char * dinamicarray)
{
    free(dinamicarray);
}


Visto che è andata bene, proviamo con un array bidimensionale

Ora, per la gioia di Eugenio, proviamo ad applicare l'allocazione dinamica della memoria ad un array bidimensionale. Se ci pensate bene, una matrice bidimensionale altro non è che un array monodimensionale le cui componenti altro non sono che array monodimensionali; ovvero possiamo rappresentarla dinamicamente come un puntatore ad un array di puntatori; possiamo anche riutilizzare le funzioni scritte per l∆array monodimensionale.

void main(void)
{
    char ** dinamicmatrice;
    unsigned int dimensioni[2] = {6, 12};

    dinamicmatrice = AllocazioneMatrice(dimensioni, sizeof(char *));
    if(!dinamicmatrice)
	return;
    /* allocazione dinamica di una matrice di 6 righe, ciascuna riga */
    /* di 12 caratteri */

    RiempiMatrice(dinamicmatrice);
    /* carichiamo i dati nella matrice */
	
    StampaMatrice(dinamicmatrice);
    /* stampiamo la matrice, solo i caratteri però */

    LiberazioneArray(dinamicmatrice);
    /* liberiamo la memoria allocata per la matrice */
}

char ** AllocazioneMatrice(unsigned int * dimensioni, int typesize)
{
    unsigned int matricesize = 0;
    char ** dinamicmatrice;
    unsigned int i = 0;   
    char ** iniziodati;
	
    matricesize = dimensioni[0] * typesize + OFFSET;
    /* calcoliamo il numero di elementi veri della matrice 
    aggiungendo i byte necessari per contenere le informazioni 
    sulla dimensione della matrice */
	
    dinamicmatrice = malloc(matricesize);
    /* allochiamo la memoria per contenere 
    la matrice e le sue dimensioni */
	
    if(!dinamicmatrice)
	return NULL;
	
    ((unsigned int *)dinamicmatrice)[0] = dimensioni[0];
    /* scriviamo nei primi byte 
    della matrice la sua dimensione */
	
    iniziodati = dinamicmatrice + OFFSET;
    for(i = 0; i < dimensioni[0]; i++)
	iniziodati[i] = AllocazioneArray(dimensioni[1], sizeof(char));
    /* allochiamo lo spazio per gli array che costituiranno 
    le righe della matrice */
			
    return dinamicmatrice;
}

void RiempiMatrice(char ** dinamicmatrice)
{
    unsigned int dimensione = 0;
    unsigned int i = 0;   
    char ** iniziodati;                      
		
    dimensione = ((unsigned int *)dinamicmatrice)[0];
    iniziodati = dinamicmatrice + OFFSET;
    if(iniziodati == NULL)
	return;
    /* ricaviamo la dimensione della matrice
    ed il puntatore all'inizio dell'array 
    di puntatori alle righe */
			
    for(i = 0; i < dimensione; i++)
	RiempiArray(iniziodati[i], 'A' + (i % 26));
    /* carichiamo le lettere dell'alfabeto 
    negli array delle righe */
}


void StampaMatrice(char ** dinamicmatrice)
{
    unsigned int dimensione = 0;
    unsigned int i = 0;   
    char ** iniziodati;                      
		
    dimensione = ((unsigned int *)dinamicmatrice)[0];
    iniziodati = dinamicmatrice + OFFSET;
    if(iniziodati == NULL)
	return;
    /* ricaviamo la dimensione della matrice
    ed il puntatore all'inizio dell'array 
    di puntatori alle righe */
	
    for(i = 0; i < dimensione; i++)
    {
	StampaArray(iniziodati[i]);
	printf("\r\n");
    }
}


void LiberazioneMatrice(char ** dinamicmatrice)
{
    unsigned int dimensione = 0;
    unsigned int i = 0;   
    char ** iniziodati;                      
		
    dimensione = ((unsigned int *)dinamicmatrice)[0];
    iniziodati = dinamicmatrice + OFFSET;
    if(iniziodati == NULL)
	return;
    /* ricaviamo la dimensione della matrice
    ed il puntatore all'inizio dell'array 
    di puntatori alle righe */

    for(i = 0; i < dimensione; i++)
	free(iniziodati[i]);                           
    /* liberiamo la memoria dei singoli array */

    free(dinamicmatrice);
    /* infine liberiamo la memoria per l'array di puntatori */
}


E se gli array non fossero tutti della stessa dimensione?

Con minime modifiche al codice appena scritto possiamo allocare un array che contiene come elementi degli array di differente dimensione; comodo, no?

void main(void)
{
    char ** dinamicmatrice;
    int dimensioni[7] = {6, 12, 7, 3, 9, 5, 10};

    dinamicmatrice = AllocazioneMatrice(dimensioni, sizeof(char *));
    if(!dinamicmatrice)
	return;
    /* allocazione dinamica di un array di 6 elementi, ciascuna riga */
    /* da n caratteri */

    RiempiMatrice(dinamicmatrice);
    /* carichiamo i dati nella matrice */
	
    StampaMatrice(dinamicmatrice);
    /* stampiamo la matrice, solo i caratteri per= */

    LiberazioneArray(dinamicmatrice);
    /* liberiamo la memoria allocata per la matrice */
}

char ** AllocazioneMatrice(unsigned int * dimensioni, int typesize)
{
    unsigned int matricesize = 0;
    char ** dinamicmatrice;
    unsigned int i = 0;   
    char ** iniziodati;
	
    matricesize = dimensioni[0] * typesize + OFFSET;
    /* calcoliamo il numero di elementi veri della matrice 
    aggiungendo i byte necessari per contenere le informazioni 
    sulla dimensione della matrice */
	
    dinamicmatrice = malloc(matricesize);
    /* allochiamo la memoria per contenere 
    la matrice e le sue dimensioni */
	
    if(!dinamicmatrice)
	return NULL;
	
    ((unsigned int *)dinamicmatrice)[0] = dimensioni[0];
    /* scriviamo nei primi byte 
    della matrice la sua dimensione */
	
    iniziodati = dinamicmatrice + OFFSET;
    for(i = 0; i < dimensioni[0]; i++)
	iniziodati[i] = AllocazioneArray(dimensioni[1 + i], sizeof(char));
    /* allochiamo lo spazio per gli array che costituiranno 
    le righe della matrice */
			
    return dinamicmatrice;
}


Conclusioni

  • l'allocazione dinamica della memoria rende possibile un codice veloce ed efficiente, senza dover imporre i limiti dovuti alla dimensione degli array che deve venir fissata quando si scrive il codice;
  • quando si usa l'allocazione dinamica, è importantissimo sia controllare che l'allocazione abbia avuto successo, sia liberare la memoria quando non è più necessaria;
  • allocando dinamicamente memoria per contenere un array, la cui dimensione possiamo fissarla noi da programma o prenderla a run-time da un input esterno (file, tastiera) possiamo "allungare" l'array ed inserire l'informazione sulla sua lunghezza: così anche noi potremo sapere (oltre al compilatore che ne tiene traccia internamente) la dimensione del blocco di memoria referenziato dal puntatore;
  • ci si può divertire ad allocare dinamicamente array i cui elementi sono puntatori ad altri array i cui elementi sono puntatori ad altri array i cui elementi ... etc. creando così strutture dati molto complesse che ci portiamo a spasso dentro il nostro codice passando come parametro alle funzioni solo il puntatore (2 o 4 byte) all'ultima allocazione;
  • se fino a qua avete capito tutto, siete pronti ad allocare matrici tridimensionali, quadrimensionali etc., da fare come compito a casa, e potete mettervi a studiare per partecipare al concorso mondiale su chi scrive il codice C più indecifrabile (questo concorso esiste davvero).

    Arrivederci al prossimo numero.

Stefano Casini è raggiungibile su Internet tramite la redazione

Copyright © 1996 BETA. Tutti i diritti riservati.


Precedente Principale Sommario Informazioni Redazione Browser Successivo