Newsgroup: it.comp.lang.c
Titolo: problemi con la gestione della memoria

Salve, vi spiego il mio problema:
ho un funzione fun(char ** arr) che prende in ingresso un array di
stringhe e ne forma una lista concatenata i cui elementi sono del
tipo
typesef struct
{ char * label;
  elem *next} elem
il campo label è una stringa mentre il campo next punta al successivo
elemento nella lista.
L'array arr puo' essere creato sia nel main e poi passato alla
funzione fun, oppure puo' essere creato a partire da un file di testo
contenete una serie di stringhe.
Ovviamente se l'array è creato da main non viene chiamata nessuna
malloc per allocare memoria per le stringhe poiché l'array stesso sarà
deallocato all'uscita del main.
Se invece viene creato a partire da un file di testo, viene mantenuto
in memoria (allocato con malloc).
Il problema nasce quando sevo sviluppare una funzione free_list che
libera tutta la memoria allocata dalla lista.
Quando devo liberare il campo label di un elemento della lista potete
capire che la free va a buon fine o meno a seconda se label punta ad
un emento di arr allocato con una malloc  oppure ad un elemento di arr
passato dal main. Come distinguere i due casi?

 di arr passato dal main. Come distinguere i due casi?
è una proposta oscena e zozza ma se non hai enormi
problemi di spazio o eleganza potresti aggiungere un campo
booleano (ev. un char) normalmente a zero, che viene
settato a uno solo quando la malloc si fa all'interno
della funzione a cui hai passato l'array.
-- 
Un corpo immerso in un liquido si bagna.
Un corpo immerso nel cemento sapeva troppo.
Un corpo immerso in un altro corpo si diverte.
Un corpo immerso in due corpi è un'orgia.

On 6 Apr, 19:48, Archaeopteryx

Ci avevo pensato anch'io, ma ti illustro una situazione particolare.
Innanzitutto c'è da dire che io non ho alcun controllo sul metodo
main. viene scritto da altri.
comunque..
supponiamo di avere una variabile di controllo char b impostata a 0.
Se l'array viene creato dal main questa variabile resta a 0.
Se l'array viene creato da una funzione (chiamiamola f) che lo
costruisce allocando memoria, la variabile b viene settata a 1.
Quindi ipoteticamente prima di fare una free posso testare la
variabile b e vedere in quale caso mi trovo.
Supponiamo però questo scenario.
1) si crea un array ar1 da main (b resta a 0)
2) si crea un array con f (b viene settata a 1)
3)si crea un altro array ar3 da main (b è sempre 1)
Se ora passo alla mia funzione free_list l'array ar3 questa lo tratta
come un array allocato in memoria, ma in realtà non è cosi' e si
genera un errore.
Una volta che b viene settata a 1 non credo ci sia modo di farla
tornare a 0 se non da main...sul quale però non ho accesso :(((
Grazie per la risposta

 accesso :(((
Allora forse si potrebbe wrappare l'allocatore. Una specie
di my_malloc che viene chiamata solo nella funzione.
my_malloc chiama a sua volta malloc ma mette pure una
copia del valore dell'indirizzo in una lista. Quando
accedi a un puntatore per la deallocazione, lo passi a
un'altra funzione che controlla se sta nella lista
precedente. O variazione sul tema....


Oppure, dato che la main() non la sviluppi tu ma qualcun altro, e
questo qualcun altro saprà benissimo se gli oggetti sono stati
allocati o meno, tantovale mettergli a disposizione una funzione
free_list() che accetta due parametri: il primo un puntatore alla
lista di elementi concatenati, il secondo un valore booleano che serve
a deallocare memoria se questa è stata allocata.


ops, avevo capito che qualsiasi lista passata potesse
avere elementi allocati singolarmente in contesti diversi.
Ma se è così, certo che come dici tu è decisamente meglio.


On 7 Apr, 09:46, Archaeopteryx

Questa sembra la soluzione migliore...
Grazie a tutti per le risposte

 [...]
Ciao   Manlio

On 7 Apr, 12:12, Manlio Perillo <manlio_perill...@SPAMlibero.it>
wrote:

Il chiamante non puo' deallocare le stringhe se non chiamando una
funzione free_list implementata da me.
Il problema nasce proprio qui:
se lbl è creato nello spazio utente (tramite main), quindi non
allocato in memoria la free_list fallisce
se lbl viene creato da file, quindi allocato, la free_list termina
correttamente.
Io invece avevo pensato ad un altra soluzione: allocare memoria per
lbl anche quando creato dal main. Se l'utente crea una nuova lista da
main passando un array di stringhe, la funzione che crea la lista
andrà a copiare tale array interamente in memoria. Questo è magari un
uso improprio della memoria, ma nel chiamare la free_list non nascono
problemi.
Grazie ancora per l'interessamento

Comunque, a scanso di problemi, converrebbe sempre creare funzioni che
separino nettamente l'operato di un programmatore esterno dall'operato
interno degli oggetti.
Cioè se vuoi dare la possibilità ad un programmatore di utilizzare una
tua struttura dati in modo da:
a) creare la lista manualmente allocando le sue label piuttosto che
utilizzare const * statici,
b) creare la lista fornendo il path del file che contiene le label
allora dovresti creare delle funzioni di init() distinte.
Potresti ad esempio creare una funzione: int init_by_file(list_t *p,
const char *path) che restituisce 1 in caso di successo (e setta un
flag interno della lista in modo da ricordarsi che lei stessa sta
usando malloc()), oppure un codice d'errore in caso di fallimento
(lista già inizializzata oppure file non trovato, ecc.). In questo
modo una lista inizializzata non può essere re-inizializzata per
errore, e comunque la lista sa (internamente) di stare allocando
memoria che andrà liberata.
Un'altra funzione potrebbe essere una semplice init_raw(list_t *p) che
dev'essere usata per chi volesse costruirsi la lista manualmente,
allocando e deallocando per conto proprio la memoria per i singoli
elementi. Stesso principio di prima: la init fallisce se la lista è
già inizializzata.
In ogni caso, al termine dell'utilizzo della tua struttura dati, il
programmatore dovrà invocare la clear(list_t *p) che deve eliminare
gli elementi della lista e quindi renderla *vuota* (azzerare il
puntatore al primo elemento, azzerare il contatore dei nodi, ecc). La
clear() saprà quindi se la lista è stata inizializzata in un modo o
nell'altro e di conseguenza richiamerà o meno le varie free().
L'utilizzatore esterno, ovviamente, avrà il compito di deallocare i
singoli elementi che lui stesso ha allocato.
In genere una buona norma è che le free() devono essere allo stesso
livello delle malloc(). Se una funzione *interna* (cioè una funzione
di supporto ad una struttura dati) alloca memoria in maniera
trasparente all'utilizzatore, dovrà essere la struttura stessa a
deallocarla in maniera altrettanto trasparente. Se un utilizzatore
esterno alloca spazio, avrà lui l'onere di deallocarlo e non la
struttura dati che lo sta utilizzando.


A parte la proposta la proposta d'implementazione, stra-quoto il concetto: chi alloca libera.
Ciao!

 Ciao!
Uh? Perchè, che cos'ha che non va la proposta d'implementazione? Tu
come implementeresti?
Così magari ci si confronta :)


ok :)
Personalmente trovo tutto troppo cervellotico: o si alloca statico (e la lista non fa niente), o si alloca dinamico (e la lista alloca e dealloca), punto. Se questo non fosse possibile per una ragione o per l'altra, si sceglie l'approccio dinamico e si copia sempre la memoria.
Quando nemmeno questo fosse possibile per motivi di performance (anche se ne dubito fortemente, visto che si sta scegliendo di utilizzare una lista e non un array statico..), se proprio non se ne può fare a meno, si fanno due moduli separati.
IMO quella che era sbagliata è la richiesta al principio..
Ciao!

 Ciao!
Beh dài, mica detto. Un array di stringhe può effettivamente essere
istanziato staticamente in una determinata funzione che poi passa il
puntatore del suddetto array alla fun(...) che crea la lista.
Può esser comodo.
Può esser comodo anche allocare dinamicamente tante stringhe e
popolarle da un file.
Non è sbagliata la richiesta al principio. E' sbagliato l'approccio
che vien _dopo_, cioè quello di avere la lista concatenata formata da
elementi che possono (ma anche no) essere allocati dinamicamente e
pretendere che sia la lista a dover capire come comportarsi.
Secondo me a questo punto le soluzioni sono due:
1) la fun(...) prende gli elementi così come gli sono stati nell'array
e li disloca lungo la lista, fregandosene di liberare la memoria (chi
l'ha allocata la liberi).
2) la fun(...) prende gli elementi, alloca internamente lo spazio per
le tante label e crea quindi una copia degli originali, mantenendo la
propria struttura interna integra anche nel caso in cui gli originali
vengano alterati nel tempo. Però poi deve occuparsi di liberare la
memoria occupata. Anche qui, come prima, chi ha allocato la memoria
iniziale la liberi.
Forse sono due approcci effettivamente migliori del precedente da me
suggerito.

 suggerito.
Infatti, l'importante è che faccia sempre la stessa cosa.
Il fatto secondo me importante è che l'implementazione di una lista, essendo la lista uno dei "blocchetti di base" di un applicativo, dev'essere così semplice e ovvia da non poter contenere errori: andare a complicare le strutture e gli algoritmi di base è il primo passo verso la fine.
Il discorso vale per tutte strutture dati (che di solito infatti sono di libreria, custom o meno, e che quindi possiedono test-set separati) che servono in altri tipi di algoritmi di più alto livello, quindi liste, alberi, tabelle di hashing, etc.etc.
Non c'è niente di peggio che, correggendo un bug su un proprio algoritmo, scoprire dopo ore che l'errore è su l'implementazione della lista, e dover sbacare del codice incasinato a morire - cosa che personalmente mi è successa più di una volta :-(
Quindi, se proprio non si usa una libreria sicura e testata per queste cose, almeno scrivere il codice il più semplice possibile!
Ciao!

> Non c'è niente di peggio che, correggendo un bug su un proprio algoritmo, scoprire dopo ore che l'errore è su l'implementazione della lista, e dover sbacare del codice incasinato a morire - cosa che personalmente mi è successa più di una volta :-(
Guarda non ne parliamo. Avevo scritto in C++ un template per un B-
Tree, testato con il dizionario italiano per popolamento/eliminazione.
Funzionava. Nessun crash.
Però il server che lo usava andava in crash. Non vuoi che fosse
proprio il B-Tree ad essere buggato? :D
Vabè ora per fortuna ho risolto, testato con 10 milioni di elementi e
va senza problemi... Ma vatti a fidare! Poi capita che il 29 febbraio
alla mezzanotte esatta se inserisci il 1234 esimo elemento si verifica
un'anomalia :D

Un buon esempio di implementazione delle liste concatenate lo trovate
nelle librerie GLib (
www.gtk.org
).
Queste librerie gestiscono l'allocazione e la deallocazione dei nodi
della lista, mentre non si interessano minimamente del contenuto.
In questo modo chi utilizza la lista sa che prima di distruggerla deve
scorrerla tutta per distruggere anche il contenuto.
esempio di contenuto statico, in questo caso basta liberare la lista e
non il contenuto:
GList *list = NULL;
list = g_list_appen(list, "ciao");
list = g_list_appen(list, "evviva");
...
g_list_free(list);
esempio di contenuto dinamico, in questo caso bisogna occuparsi anche
di liberare le stringhe caricate dal file:
GList *list = NULL;
FILE *f;
char buf[1024];
f=fopen("file.txt", "rt");
while( fgets(buf, sizeof(buf), f)!=NULL )
{
    list = g_list_appen(list, strdup(buf) );
}
fclose(f);
...
g_list_foreach(list, free);
g_list_free(list);

Il 06/04/2011 19:23, drummolo ha scritto:

Se ho capito bene fun prende in input un array di stringhe e restituisce 
una lista il cui elemento label punta ad un elemento dell' array.
Dopo esiste una funzione free_list che passandogli la lista output di 
fun la libera.
Il tuo problema non sussiste perchè non è compito di free_list  liberare 
gli elementi dell' array ma solo di chi l'array lo ha allocato.
La funzione free_list deve solo eventualmente liberare la memoria 
occupata per ogni singolo elem non prendendo in considerazione la 
memoria puntata da label perchè appartiene all' array