Newsgroup: it.comp.lang.c
Titolo: liberare la memoria occupata da un albero

A pag 179 del K&R2 vi è la descrizione di un albero il cui nodo è
descritto dalla struttura
struct tnode {
 char* word;
 int count;
 struct tnode* left;
 struct tnode* right;
};
nel main() a pag 190 manca una funzione per cancellare l'albero in
questione. Poichè non sono molto pratico (sopratutto delle funzioni
ricorsive) vorrei domandare se questa funzione (che sembra essere
compilata) và bene oppure no?
void Free(struct tnode* p)
{if(p!=NULL)
  {if(p->left!=NULL)
          Free(p->left);
   if(p->right!=NULL)
          Free(p->right);
   if(p->word!=NULL) 
          free(p->word);
   free(p);
  }
}

}
Secondo me si, con una piccola eccezione sulla scelta del nome:
chiamare una funzione Free non conflitta certo con la free perche' il
C e case sensitive, ma non e' il caso che il nome di 2 funzioni si
differenzino solo per una lettera maiuscola/minuscola, meglio che i
nomi siano differenti, ad es my_free(), btree_free().
-- 
Mox
"Trust the programmer."
"Don't prevent the programmer from doing what needs to be done."
"Keep the language small and simple."
"Provide only one way to do an operation."

 }
Avrei una domanda su questo codice; io avrei scritto:
void free_tree(struct tnode* p){
  if(p!=NULL){
    free_tree(p->left);
    free_tree(p->right);
    if(p->word!=NULL)
       free(p->word);
    free(p);
  }
}
In pratica tolgo i test sui figli, visto che comunque viene testata
all'entrata di free_tree(). Qual e' la soluzione migliore? a me sembra
chiaro che la mia ha bisogno di una ricorsione in piu' (per testare i
nodi figli), ma mi sembra piu' semplice da leggere. Ha qualche altro
vantaggio oppure tutti i prg che ho scritto sono sotto-ottimizzati?
Ciao
Scola

vantaggio oppure tutti i prg che ho scritto sono sotto-ottimizzati?
Per i test sui figli io li faccio sempre, giudico il costo di una
chiamata ricorsiva in piu' maggiore che non un test + deferenziamente
di un puntatore.
Su un albero ovviamente conviene di piu' testare prima della chiamata
perche' potenzialmente hai molti puntatori a null, su una lista
avrebbe meno senso... visto che avrai sempre e solo 1 puntatore null e
il costo di una chiamata ricorsiva e' accettabile.
Il testo sulla free non serve: free(NULL) non fa nulla, o meglio testa
al suo interno il puntatore nullo.


GRazie!
Ciao

al suo interno il puntatore nullo.
in altre parole tu dici che è meglio:
void lib_tree(struct tnode* p)
{if(p!=NULL)
  {if(p->left!=NULL)
          lib_tree(p->left);
   if(p->right!=NULL)
          lib_tree(p->right);
   free(p->word);
   free(p);
  }
}
ma secondo voi quali sono le operazioni da intraprendere nel caso di
*non* allocazione di memoria per un nodo dell'albero o per una parola
del nodo?
 

 del nodo?
Non sono sicuro di capirti. Ogni nodo  ha due puntatori ai figli, ognuno
di questi due puntatori puo` essere solo in due stati: NULL (e quindi il
figlio non esiste) oppure non NULL (e  in questo caso la funzione che ha
costruito l'albero garantisce che il puntatore e` consistente [1]).
Il controllo all'inizio della lib_tree garantisce che andremo ad operare
solo su  puntatori non  NULL (e  quindi che  fanno riferimento  ad altri
nodi).
Stesso discorso per la stringa. Il puntatore puo` essere NULL o non NULL
(e consistente  [2]). Visto che free(NULL) ha  un comportamento definito
chiamiamo comunque free sul puntatore.
[1]
struct tnode* new_node(void) {
        struct tnode *p = malloc(sizeof(struct tnode));
        if (p == NULL)
                return NULL;
        p->left = p->right = p->word = NULL;
        return p;
}
[2]
int set_word(struct tnode *p, char *word) {
        int l;
 
        if (p->word)
                free(p->word)
        l = strlen(word) + 1;
        if ((p->word = malloc(l)) == NULL)
                return -1;
        memcpy(p->word, word, l);
        return 0;
}
void unset_word(struct tnode *p) {
        free(p->word);
        p->word = NULL;
}
ciao
Kronos
-- 
Home: 
http://kronoz.cjb.net
Dicono che  il cane sia  il miglior  amico dell'uomo. Secondo me  non e`
vero. Quanti dei vostri amici avete fatto castrare, recentemente?

tra le altre cose non capisco perchè la funzione ricorsiva 
label() che dovrebbe costruire un vettore lineare di puntatori a
struct tnode di tutti i nodi dell'albero, non mi funziona quando tento
di accedere agli elementi da detto vettore di puntatori **pnt mentre
mi funziona se conto i nodi e alloco prima dinamicamente la memoria 
unsigned  conta;
....
int main()
{struct tnode *root;
 struct tnode **pnt=NULL;
 char word[MAXWORD];
 unsigned i;
 root=NULL;
 while( getword(word, MAXWORD)!=EOF )
   if(isalpha(word[0]))
           root=addtree(root, word);
 P("\n\n conta=%d", conta);
 //pnt=realloc(pnt, (conta+100) * sizeof(*pnt));
 conta=0;
 label(root, pnt);
 print_pnt(pnt);
 //treeprint(root);
 Free(root);
 free(pnt);
 return 0;
}
....
/*non funziona */
void label(struct tnode* p, struct tnode** pnt)
{if(p!=NULL)
  {if(p->left!=NULL)
          label(p->left, pnt);
   if(p->right!=NULL)
          label(p->right, pnt);
   pnt=realloc(pnt, (conta+2)* sizeof(*pnt));
   pnt[conta++]=p;
  }
}
da chiamarsi con label(root, pnt); mi và fuori memoria se tento di
accedere agli elementi 
 pnt[i]->count o pnt[i]->word con 0<=i<conta 
[conta è unsigned globale]
rigrazio 

 rigrazio
// nota pnt come è dichiarato
void label(struct tnode* p, struct tnode*** pnt)
{if(p!=NULL){
   if(p->left!=NULL)  
                label(p->left, pnt);
   if(p->right!=NULL) 
                label(p->right, pnt);
   *pnt=realloc(*pnt, (conta+2)* sizeof(tnode*));
   (*pnt)[conta++]=p;
  }
}
Scusate ma qua aggiungo come la scriverei io ( il mio narcisismo me lo 
impone )
void label(struct tnode* p, struct tnode*** pnt)
{
  if(!p) return;
  if(p->left!=NULL)  label(p->left, pnt);
  if(p->right!=NULL) label(p->right, pnt);
  *pnt=realloc(*pnt, (conta+2)* sizeof(tnode*));
  // aggiungi un bel check se (*pnt) == 0
  (*pnt)[conta++]=p;
}

costruito l'albero garantisce che il puntatore e` consistente [1]).
intendevo dire nel caso che qualche malloc fallisce.
Nel tuo caso mi sembra non tieni conto di segnalare un eventuale
parola scartata per fallimento di malloc. 
Mi sono regolato così: 
prendi parole dal testo
le compatibili inseriscili nell'albero
se qualche malloc fallisce continua il processo scartando la parola
che ha fatto fallire la malloc, ma tieni conto del fallimento di
qualche malloc immagazzinando un valore in una variabile "stato"
stampa l'albero e indica se tutto è andato bene (controllando il
valore della variabile "stato")
O sbaglio?

   (*pnt)[conta++]=p;
^^^^^^^^^^
Non ci avevo pensato, ok funziona grazie
Questa è la mia:
unsigned cont=0;
int label(struct tnode* p, struct tnode*** pnt)
{if(p!=NULL)
  {if(cont%98==0)
    if( (*pnt=realloc( *pnt,(cont+99)*sizeof(struct tnode*) ))==NULL )
               return 0;
   (*pnt)[cont++]=p;
   if(p->left!=NULL)
           label(p->left, pnt);
   if(p->right!=NULL)
           label(p->right, pnt);
  }
 return 1;
}
da chiamarsi così
int main()
{struct tnode *root;
 struct tnode **pnt=NULL;
 char word[MAXWORD];
...
label(root, &pnt);
...
free(&pnt);
___________________
è giusto free(&pnt);?
Ci guadagno qualche cosa ad allocare ogni 100 puntatori piuttosto che
a ogni puntatore?

che ha fatto fallire la malloc, ma tieni conto del fallimento di
mi sto orientando su una funzione che inzializza il nodo tipo:
/* new_node: inizializza un tnode con w  stringa */
struct tnode* new_node(char* w,  int* stato) 
  {struct tnode * p=malloc(sizeof(struct tnode));
   if (p==NULL) {*stato=0; return NULL;}
   p->word=strdup1(w);
   if(p->word==NULL) 
                   {free(p); 
                    *stato=0; 
                    return NULL;
                   }
   p->left=p->right=NULL;
   p->count=1;
   return p;
  }
pareri critici ?

č giusto free(&pnt);?
no, forse č meglio free(pnt), vero?
Ho leggermente modificato la versione di prima in modo da levare la
variabile globale;
char label(struct tnode* p, struct tnode*** pnt, unsigned long* cont)
{char i=1,j=1;
 if(p!=NULL)
  {if(*cont%98==0)
     if( (*pnt=realloc(*pnt,(*cont+99)*sizeof(struct tnode*)))==NULL )
               return 0;
   (*pnt)[(*cont)++]=p;
   if(p->left!=NULL)
           i=label(p->left, pnt, cont);
   if(p->right!=NULL)
           j=label(p->right, pnt, cont);
  }
 return i*j;
}
secondo voi se un realloc falla il risultato della funzione alla fine
della ricorsione č zero?
Alla fine della ricorsione *cont č il numero degli elementi trattati?
Saluti