Comment libérer la mémoire dans l'arborescence de préfixes? (ANSI C)

Question

J'ai essayé de libérer de la mémoire dans la fonction dict_free(), mais cela ne fonctionne pas et je ne sais pas pourquoi. Est-ce que je manque quelque chose? Impossible de comprendre, ce qui ne va pas.

Éditer: Si j'appelle free() dans dict_free(), je m'attends à voir que le pointeur free'd pointe vers NULL, mais ce n'est pas le cas.

Voici mon code:

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 

typedef struct Dict 
{ 
    struct Dict *branches[256]; 
    int index; 

}Dict; 


void dict_insert_depth(unsigned char*,Dict *,int); 
void dict_insert(unsigned char*,Dict *); 

void dict_free(Dict *d) 
{ 
    if(d!=NULL){ 
    int i; 
    for(i=0; i<256; i++){ 
     if(d->branches[i] != NULL){ 
     dict_free(d->branches[i]); 
     free(d->branches[i]); 
     printf("Is it free?? %s\n",d==NULL?"yes":"no"); 
     } 
    } 
    } 
} 
/** 
* Insert word into dictionaR 
*/ 
void dict_insert(unsigned char *w, Dict *d) 
{ 
    dict_insert_depth(w,d,0); 
} 

void dict_insert_depth(unsigned char *w, Dict *d, int depth) 
{ 
    if(strlen(w) > depth){ 
    int ch = w[depth]; 

    if(d->branches[ch]==NULL){ 
     d->branches[ch] = malloc(sizeof(struct Dict)); 
     dict_insert_depth(w,d->branches[ch],depth+1); 

    }else{ 
     dict_insert_depth(w,d->branches[ch],depth+1); 
    } 
    } 
} 

/** 
* Check whether a word exists in the dictionary 
* @param w Word to be checked 
* @param d Full dictionary 
* @return If found return 1, otherwise 0 
*/ 
int in_dict(unsigned char *w, Dict *d) 
{ 
    return in_dict_depth(w,d,0); 
} 

int in_dict_depth(unsigned char *w, Dict *d, int depth) 
{ 
    if(strlen(w)>depth){ 
    int ch = w[depth]; 
    if(d->branches[ch]){ 
     return in_dict_depth(w, d->branches[ch], depth+1); 
    }else{ 
     return 0; 
    } 
    }else{ 
    return 1; 
    } 

} 

Answer 1

Votre code libre semble bien, sauf qu'il ne parviendra pas à libérer le nœud racine.

Votre test de liberté est erroné. free ne définira aucune variable à NULL. Il est souvent une bonne idée de le faire explicitement, donc vous êtes sûr de ne pas lire la mémoire déjà libérée:

free(d->branches[i]); 
    d->branches[i] = NULL; // clobber pointer to freed memory 

Pour gérer le problème du nœud racine, et probablement un peu plus propre aussi bien, faites ceci:

void dict_free(Dict *d) 
{ 
    if(d!=NULL){ 
    int i; 
    for(i=0; i<256; i++){ 
     if(d->branches[i] != NULL){ 
     dict_free(d->branches[i]); 
     d->branches[i] = NULL; 
     } 
    } 
    free(d); 
    } 
} 

Answer 2

dict_free(d->branches[i]); 
free(d->branches[i]); 
printf("Is it free?? %s\n",d==NULL?"yes":"no"); 

Cette vérifie d, mais vous ne modifiez pas d dans la boucle. Puisque vous vérifiez que d n'est pas null ci-dessus, cela imprime toujours non.

void dict_free(Dict* d) { 
    if (d) { 
    for(int i = 0; i < 256; i++) { 
     if (d->branches[i]) { 
     dict_free(d->branches[i]); 
     free(d->branches[i]); 

     d->branches[i] = 0; // mark this branch as freed 
     // important if d is reused, and since dict_free doesn't 
     // free(d), it could be 
     } 
    } 
    } 
} 

J'ai suivi votre code existant à ne pas libérer d, mais vous voudrez peut-être changer les choses si un Dict est toujours affecté de la même façon (par exemple ajouter une fonction dict_new) avec dict_free libérant aussi le passé objet.