FaqNote < Labprog2

Tags: view all tags

---++ FAQ e Note

----
%TOC%
----


---+++ Uso della realloc (03/04/07)

La realloc e' una funzione molto utile nel caso si debbano utilizzare dei blocchi di memoria (ad esempio, array e stringhe) che crescono dinamicamente. Si osservi pero' che una chiamata alla realloc puo' causare la copia dell'intero blocco precendentemente allocato in una nuova area di memoria (attenzione, questo puo' verificarsi non solo nel caso di ampliamento, ma anche nel caso di restringimento, a seconda di come e' realizzato l'allocatore di memoria). Quindi, la realloc puo' avere un costo lineare nella dimensione del blocco da ridimensionare. Inoltre, si tenga anche conto che, nel caso in cui si voglia allargare un blocco, anche la semplice verifica dell'esistenza di uno spazio libero sufficiente per l'ampliamento senza spostamento puo' avere un costo non trascurabile (a seconda di come e' realizzato l'allocatore, potrebbe richiedere la scansione della lista dei blocchi di memoria liberi per verificare se contiene quello che segue il blocco da ampliare). In definitiva, se possibile, e' bene cercare di mimizzare il numero di chiamate alla realloc.

Per questo motivo, se si vuole usare la realloc per memorizzare una stringa letta carattere per carattere di cui non si conosce la lunghezza massima, e' assolutamente sconsigliato procedere al ridimensionamento dell'array contenente la stringa dopo ogni carattere letto. Un seguente modo di procedere corre il rischio di realizzare con un costo quadratico un'operazione di costo lineare. Un esempio di questo modo di procedere e' riportato in  [[%ATTACHURL%/realloc1.c][realloc1.c]].

L'esempio mostra anche uno degli errori classici legati all'uso della realloc. Si osservi infatti che, nel caso in cui non riesca a ridimensionare il blocco, la realloc non modifica il bloccco da ridimensionare (non lo dealloca) e restituisce il puntatore NULL. Di conseguenza, una chiamata alla realloc del tipo:
<pre>
    p = realloc(p, newsize);
</pre>
nel caso in cui la realloc non possa ridimensionare il blocco di memoria, corre il rischio di perdere ogni riferimento al blocco inizialmente puntato da =p=. In particolare, dopo un tale errore non si potra' piu' accedere al contenuto del blocco, ne' il blocco potra' essere deallocato.

Nel caso in cui come conseguenza del mancato ridimensionamento del blocco il programma debba necessariamente terminare, quanto appena visto non e' un problema. Se invece, come conseguenza del mancato ridimensionamento il programma deve proseguire provvedendo in modo diverso all'allocazione di nuova memoria, il precedente codice e' un grave errore (errore che e' stato riscontrato anche in sofware commerciali).

La maniera corretta di procedere e' pertanto quella di utilizzare un puntatore di appoggio, verificare se il puntatore e' NULL, e infine, nel caso di ridimensionamento completato con successo, spostare il puntatore nella variabile da usare per il riferimento al blocco.

Questo corretto modo di procedere e' mostrato nell'esempio [[%ATTACHURL%/realloc3.c][realloc3.c]] . L'esempio legge una sequenza di numeri e li memorizza in un vettore che cresce man mano che si leggono i numeri. Per cercare di minimizzare il numero di chiamate alla realloc, si parte da un vettore di dimensione base e, quando necessario, si raddoppia la dimensione del vettore (un altro approccio potrebbe essere quello di aggiungere un blocco di dimensione fissa). La dimensione del blocco iniziale puo' essere scelta in ragione della lunghezza media (o minima) dell'input. In una fase iniziale dello sviluppo, per verificare il corretto funzionamento del programmma, si puo' partire da una dimensione molto piccola che costringa ad eseguire immediatamente il ridimensionamento del vettore.

Per quanto riguarda l'uso della realloc si veda anche:

   * Kerhighan e Pike, Programmazione nella pratica. Addison-Wesley, 1999.<br> Paragrafo 2.6: Crescita negli array

Per completezza, va detto che in alcuni casi la realloc potrebbe essere anche particolarmente efficiente, soprattutto se il blocco da ridimensionare cresce di poco. Infatti, molto spesso l'allocatore di memoria non alloca blocchi di qualsiasi dimensione. Quindi, potrebbe anche darsi che il blocco da ridimensionare in realta' occupi gia' piu' memoria di quella che il programma assume gli sia riservata. In questo caso, se la nuova dimensione del blocco non esce al di fuori di quella gia' assegnatagli dall'allocatore,
la realloc non deve fare praticamente nulla, se non notificare al chiamante che puo' utilizzare anche il nuovo pezzo di blocco richiesto. Nonostante questi casi particolari dipendenti dalla implementazione dell'allocatore, e' comunque buona norma cercare di minimizzare il numero di chiamate alla realloc.

*Allegati*
   * [[%ATTACHURL%/realloc1.c][realloc1.c]]: Realloc: esempio di uso improprio
   * [[%ATTACHURL%/realloc3.c][realloc3.c]]: Realloc: minimizzazione del numero di chiamate


---+++ Memoria dinamica, memoria statica e variabili dinamiche (03/04/07)

Prendo spunto da una domanda sul primo modulo del progetto in cui si chiedeva se si poteva evitare di allocare memoria dinamica per memorizzare le stringhe dei token. In alternativa all'allocazione dinamica nella domanda si proponeva di dichiarare una variabile di tipo array di caratteri, scrivere la stringa nell'array e restituire infine il puntatore all'array.

Purtroppo non esistono trucchi o scappatoie per evitare l'allocazione dinamica della memoria nei casi in cui i dati da memorizzare non hanno una dimensione (massima) nota a priori e, soprattutto, i dati memorizzati devono rimanere accessibili anche al termine della funzione che li ha memorizzati (che li ha allocati).

---++++ Memoria dinamica e variabili locali

Si osservi il seguente esempio:

<pre>
void g(char *v) {
    printf("g: %s\n", v);
}

char *f(char c) {
    char v[3];
	v[0] = c = v[1] = c; v[2] = '\0'; 
    g(v);
    return v;
}

int main(void) {
    char *v = f('a');
	
    printf("main: %s\n", v);
}
</pre>

La funzione =f= ha tra le sue variabili locali un array di caratteri =v=. Il tempo di vita di questo array e' pari al tempo in cui rimane attiva la funzione =f=. In particolare, l'array =v= rimane allocato se la funzione =f= chiama un'altra funzione. E' pertanto corretto passare alla funzione =g= chiamata da =f= il puntatore a =v=. Invece, al termine di =f= il vettore =v= viene deallocato ed e' pertanto errato restituire alla funzione che ha chiamato =f= un riferimento a tale vettore per comunicare come risultato la stringa in esso contenuto.

Si osservi anche che, siccome l'indirizzo di =v= e' un indirizzo valido, il precedente programma e' sintatticamente lecito e molto probabilmente, se lo si compila e lo si esegue, si otterra' come output:

<pre>
g: aa
main: aa
</pre>

che sembrerebbe indicare che nonostante tutto il main ha ricevuto come valore di ritorno proprio la stringa "aa". Per pura fortuna questo e' vero (ed e' legato al sistema e al compilatore usati per questo esempio). Il  problema e' che il vettore =v=, allocato sullo stack al momento della chiamata della funzione, non viene immediatamente cancellato, e al termine di =f= si trova su di una parte dello stack non piu' utilizzata e sulla quale andranno ad allocare le proprie variabili locali (e non solo) le successive chiamate di funzione. Nell'esempio, dato che non c'e' nessuna chiamata di funzione tra il termine di =f= e la stampa della stringa ricevuta da =f=, questa parte di stack non e' stata riscritta e il valore che si ottiene e' proprio quello che vi ha lasciato la funzione =f=. Anche se per fortuna il prgramma si comporta come voluto, basare il corretto funzionamento del programma su considerazioni di questo tipo e' comunque un errore. Infatti, lo stack puo' essere utilizzato per memorizzare valori temporanei anche indipendentemente dalla chiamata di funzioni (ad esempio, nel calcolo di espressioni complesse).

Per verificare esplicitamente che il contenuto della stringa restituita da =f= potrebbe cambiare a seconda di quello che segue. Si provi a compilare ed eseguire il seguente main:

<pre>
int main(void) {
    char *v = f('a');
    char *w = f('b');
	
    printf("main: %s\n", v);
}
</pre>

E' molto probabile che l'output sia qualcosa del tipo:

<pre>
g: aa
g: bb
main: bb
</pre>

anche se,  a seconda del sistema e del compilatore che si sta usando, si potrebbe ottenere un output diverso o verifarsi un errore di esecuzione.

Infine, il =gcc= riconosce il potenziale errore legato alla restituzione dell'indirizzo di =v= con un warning del tipo:
<pre>
warning: function returns address of local variable
</pre>
Si osservi comunque che l'assenza di warning di tale tipo non garantisce l'assenza del problema. Infatti, la situazione potrebbe essere piu' complessa e l'indirizzo del vettore =v= potrebbe essere restituito in modo indiretto per mezzo di un puntatore. Ad esempio, compilando questa versione della funzione

<pre>
char *f(char c) {
    char v[3];
    char *p = v;
	v[0] = c = v[1] = c; v[2] = '\0'; 
    g(v);
    return p;
}
</pre>

non si hanno warning, ma si ha lo stesso tipo di problema.

---++++ Memoria dinamica e variabili globali

Se invece si cerca di rimpiazzare la memoria dinamica con una variabile globale ci si puo' trovare di fronte a problemi di altro tipo. Si prenda ad esempio il seguente codice:

<pre>
char v[3];

char *f(char c) {
	v[0] = c = v[1] = c; v[2] = '\0'; 
    g(v);
    return v;
}

int main(void) {
    char *v = f('a');
    char *w = f('b');
	
    printf("%s %s\n", v, w);
}
<pre>

Le stringhe =v= e =w= contengono lo stesso valore, anzi fanno riferimento sempre allo stesso indirizzo di memoria: il valore che si pensava di aver ottenuto in =v= dopo la prima chiamata di =f= sara' sovrascritto dalla seconda chiamata di =f=. Pertanto, se si vuole che =v= e =w= siano stringhe diverse, non resta che allocare dinamicamente la memoria ad ogni chiamata di =f= (o alternativamente copiare in una nuova area di memoria il valore restituito da =f= prima di una nuova chiamata).

-- Users.StefanoGuerrini - 02 Apr 2007

Attachments

Topic attachments
I	Attachment	History	Action	Size	Date	Who	Comment
c	realloc1.c	r1	manage	0.7 K	2007-04-03 - 16:45	StefanoGuerrini	Realloc: esempio di uso improprio
c	realloc3.c	r1	manage	1.5 K	2007-04-03 - 16:46	StefanoGuerrini	Realloc: minimizzazione del numero di chiamate