Table de hashage: Comment libérer la mémoire

Bonjour à tous,

Le titre du message est peut-être faux parce qu'au final, je ne suis pas sûr qu'on puisse appeler ça "table de hashage", mais en tout cas c'était mon but. J'ai trouvé une explication théorique sur internet que j'ai essayé de mettre en oeuvre. Donc tout à l'air de marcher, quand je compile, pas de message d'erreur ,et le programme fait bien ce que j'attend de lui. Le seul souci que j'ai, c'est pour libérer toute la mémoire que j'ai utilisé. Quand je demande l'avis de Valgrind, il me dit :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
 
==7396== Invalid write of size 1
==7396==    at 0x4009C4: set_personne (main.c:94)
==7396==    by 0x40072B: main (main.c:31)
==7396==  Address 0x51c2d26 is 0 bytes after a block of size 6 alloc'd
==7396==    at 0x4C28BED: malloc (vg_replace_malloc.c:263)
==7396==    by 0x4008F6: set_personne (main.c:81)
==7396==    by 0x40072B: main (main.c:31)
==7396== 
==7396== Invalid write of size 1
==7396==    at 0x400A04: set_personne (main.c:97)
==7396==    by 0x40072B: main (main.c:31)
==7396==  Address 0x51c2d7b is 0 bytes after a block of size 11 alloc'd
==7396==    at 0x4C28BED: malloc (vg_replace_malloc.c:263)
==7396==    by 0x400948: set_personne (main.c:87)
==7396==    by 0x40072B: main (main.c:31)
==7396== 
==7396== Invalid write of size 1
==7396==    at 0x4009C4: set_personne (main.c:94)
==7396==    by 0x400754: main (main.c:36)
==7396==  Address 0x51c2e26 is 0 bytes after a block of size 6 alloc'd
==7396==    at 0x4C28BED: malloc (vg_replace_malloc.c:263)
==7396==    by 0x4008F6: set_personne (main.c:81)
==7396==    by 0x400754: main (main.c:36)
==7396== 
==7396== Invalid write of size 1
==7396==    at 0x400A04: set_personne (main.c:97)
==7396==    by 0x400754: main (main.c:36)
==7396==  Address 0x51c2e75 is 0 bytes after a block of size 5 alloc'd
==7396==    at 0x4C28BED: malloc (vg_replace_malloc.c:263)
==7396==    by 0x400948: set_personne (main.c:87)
==7396==    by 0x400754: main (main.c:36)
==7396== 
==7396== Invalid read of size 1
==7396==    at 0x4E74CBA: vfprintf (vfprintf.c:1623)
==7396==    by 0x4E7D479: printf (printf.c:35)
==7396==    by 0x400A84: print_personne (main.c:108)
==7396==    by 0x4007AC: main (main.c:44)
==7396==  Address 0x51c2d26 is 0 bytes after a block of size 6 alloc'd
==7396==    at 0x4C28BED: malloc (vg_replace_malloc.c:263)
==7396==    by 0x4008F6: set_personne (main.c:81)
==7396==    by 0x40072B: main (main.c:31)
==7396== 
durand jean-michel 32 
==7396== Invalid read of size 1
==7396==    at 0x4E74CBA: vfprintf (vfprintf.c:1623)
==7396==    by 0x4E7D479: printf (printf.c:35)
==7396==    by 0x400A84: print_personne (main.c:108)
==7396==    by 0x4007B8: main (main.c:45)
==7396==  Address 0x51c2e26 is 0 bytes after a block of size 6 alloc'd
==7396==    at 0x4C28BED: malloc (vg_replace_malloc.c:263)
==7396==    by 0x4008F6: set_personne (main.c:81)
==7396==    by 0x400754: main (main.c:36)
==7396== 
dupont alain 54 
==7396== Conditional jump or move depends on uninitialised value(s)
==7396==    at 0x4C27D04: free (vg_replace_malloc.c:427)
==7396==    by 0x4007E0: main (main.c:48)
==7396== 
==7396== 
==7396== HEAP SUMMARY:
==7396==     in use at exit: 28 bytes in 4 blocks
==7396==   total heap usage: 7 allocs, 3 frees, 40,076 bytes allocated
==7396== 
==7396== LEAK SUMMARY:
==7396==    definitely lost: 28 bytes in 4 blocks
==7396==    indirectly lost: 0 bytes in 0 blocks
==7396==      possibly lost: 0 bytes in 0 blocks
==7396==    still reachable: 0 bytes in 0 blocks
==7396==         suppressed: 0 bytes in 0 blocks
==7396== Rerun with --leak-check=full to see details of leaked memory
==7396== 
==7396== For counts of detected and suppressed errors, rerun with: -v
==7396== Use --track-origins=yes to see where uninitialised values come from
==7396== ERROR SUMMARY: 5006 errors from 7 contexts (suppressed: 4 from 4)

Donc j'ai des problèmes de mémoire, c'est sûr, mais je ne trouve pas comment les résoudre. Ma fonction de hashage est toute bête, elle additionne les valeurs ASCII de chaque caractère de la chaîne passée en argument, pour mes essais ça suffit bien. Sinon, pour les 5000 appels à free(), je peux arranger ça et libérer que les cases du tableau que j'ai alloué, mais dans le doute et en attendant vos conseils, je libère les 5000. Donc voici mon code:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
typedef struct _personne pers;
struct _personne
{
  char *nom;
  char *prenom;
  int age;
  int id;
};
 
int set_personne(pers **tab, char *nom , char *prenom, unsigned int age);
pers *get_personne(pers **tab, char *nom);
void print_personne(pers *p);
int hash_me(const char* chaine);
 
 
int main(void)
{
  pers **tab_hash;
  int i;
 
  if((tab_hash = malloc(sizeof(pers*) * 5000)) == NULL)
	{
  	  fprintf(stderr, "alloc échouée");
  	  return (-1);
	}
 
  if((set_personne(tab_hash, "durand", "jean-michel", 32)) == 0)
	{
	  return (-1);
	}
 
  if((set_personne(tab_hash, "dupont", "alain", 54)) == 0)
	{
	  fprintf(stderr, "Erreur \n");
	}
 
  pers *personne1 = get_personne(tab_hash, "durand");
  pers *personne2 = get_personne(tab_hash, "dupont");
 
  print_personne(personne1);
  print_personne(personne2);
 
  for(i = 0; i < 5000; i++)        /* C'est moche, mais j'en suis conscient  */
	free(tab_hash[i]);
 
  free(tab_hash);
  tab_hash = NULL;
 
  return 0;
}
 
 
int hash_me(const char* chaine)
{
  int hash = 0, i;
  for(i = 0; chaine[i] != '\0'; i++)
    hash += chaine[i]; 
 
  return hash;
}
 
pers *get_personne(pers **tab, char *nom)
{ 
  return tab[hash_me(nom)];
}
 
int set_personne(pers **tab, char *nom , char *prenom, unsigned int age)
{
  pers *nouv = NULL;
 
  if((nouv = malloc(sizeof(pers))) == NULL) 
	{
  	  fprintf(stderr, "alloc échouée");
  	  return (-1);
	}
 
  if((nouv->nom = malloc(strlen(nom) * sizeof(char))) == NULL) 
	{
  	  fprintf(stderr, "alloc échouée");
  	  return (-1);
	}
 
  if((nouv->prenom = malloc(strlen(prenom) * sizeof(char))) == NULL) 
	{
  	  fprintf(stderr, "alloc échouée");
  	  return (-1);
	}
 
  strncpy(nouv->nom, nom, strlen(nom));
  nouv->nom[strlen(nom)] = '\0';
 
  strncpy(nouv->prenom, prenom, strlen(prenom));
  nouv->prenom[strlen(prenom)] = '\0';
 
  nouv->age = age;
  nouv->id = hash_me(nom);
  tab[nouv->id] = nouv;
 
  return nouv->id;
}
 
void print_personne(pers *p)
{
  printf("%s %s %d \n", p->nom, p->prenom, p->age);
}

Voilà, je me pose des questions .. Est-ce que c'est mon code qui est mal foutu et qui m'empêche de trouver comment régler le problème, je ne sais pas.

Je vous remercie pour votre aide et vos conseils.

Bon, et bien je suis désolé mais j'ai compris mon erreur et j'ai réussi à régler tous les problèmes. Je passe donc le sujet en résolu.

Citation:

Envoyé par jujudelyon

Bon, et bien je suis désolé mais j'ai compris mon erreur et j'ai réussi à régler tous les problèmes. Je passe donc le sujet en résolu.

Est-il possible d'indiquer et d'expliquer ton erreur pour les lecteurs stp ?

Citation:

Envoyé par _-Slash-_

Est-il possible d'indiquer et d'expliquer ton erreur pour les lecteurs stp ?

Bonsoir, oui sans problème.

Alors, en premier j'ai supprimé mon affreuse boucle:
Code:

1 2 for(i = 0; i < 5000; i++) /* C'est moche, mais j'en suis conscient */ free(tab_hash[i]);
Ce qui a fait fait tomber mon nombres d'erreur dans Valgrind à 8.

Pour toute les erreurs Invalid write of size 1 et Invalid read of size 1, c'était dû à mes malloc sur nouv->nom et nouv->prénom ligne 81 et 87. J'allouais:

Code:

strlen(nom) * sizeof(char)

Alors qu'il fallait en fait allouer strlen(nom) + 1 pour le caractère nul de fin de chaîne. Donc en gros, si j'ai bien compris, j'écrasais une case de trop dans la mémoire, ce qui provoquait l'erreur "invalid write" et l'erreur "invalid read" allait avec puisque je lisais cette même case dans laquelle je n'avais déjà pas le droit d'écrire.

Je me suis renseigné après coup, et j'ai compris que strlen() ne comptait pas le caractère de fin de chaine, il faut donc rajouter 1 à l'allocation. A partir de là, je n 'avais plus d'erreur mais il me restait à désallouer la mémoire que j'avais utilisé sans passer ma boucle de 5000 free(). J'ai donc compris qu'il fallait que je désalloue dans l'ordre mes chaines de caractères nom, prenom puis ma structure. J'ai créé une fonction:
Code:

1 2 3 4 5 6 void liberer_mem(pers *personne) { free(personne->nom); free(personne->prenom); free(personne); }
Voilà, plus d'erreur et toute la mémoire a été libérée.