Discussion :

[Erosquare]

Bonjour,

dans le cadre de plusieurs projets, afin de faciliter l'implémentation de certaines données on a eu l'idée d'utiliser une structure de données de type HashTable. Vu que la bibliothèque standard du langage C ne propose rien de tel, j'ai commencé à coder une HashTable générique. Ce qui a été commencé est fourni en pièces jointes :

Code main.c :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
#include <stdio.h>
#include <stdlib.h>
#include "HashTable.h"
 
struct personne {
    char* nom;
    char* prenom;
};
 
int main()
{
    HashTable dico = NULL;
 
    int nb = 47;
    long nb2 = 5432424;
    double reel = 4.5789;
    struct personne chuck;
 
    chuck.nom = "Norris";
    chuck.prenom = "Chuck";
 
    dico = new_HashTable("Test1", "Ceci est une chaine", sizeof("Ceci est une chaine"));
    addEntry(dico, "Entier", &nb, sizeof(int));
    addEntry(dico, "Reel", &reel, sizeof(double));
    addEntry(dico, "Entier long", &nb2, sizeof(long));
    addEntry(dico, "Structure", &chuck, sizeof(struct personne));
 
    printf("Clef : %s - Valeur : %s\n", dico->key, (char*)dico->value);
 
    dico = dico->next;
 
    printf("Clef : %s - Valeur : %d\n", dico->key, *(int*)dico->value);
 
    dico = dico->next;
 
    printf("Clef : %s - Valeur : %f\n", dico->key, *(double*)dico->value);
 
    dico = dico->next;
 
    printf("Clef : %s - Valeur : %ld\n", dico->key, *(long*)dico->value);
 
    dico = dico->next;
 
    printf("Clef : %s - Valeur : %s %s\n", dico->key, ((struct personne*)dico->value)->prenom, ((struct personne*)dico->value)->nom);
 
    return 0;
}

Code HastTable.h :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
#ifndef HASHTABLE_H_INCLUDED
#define HASHTABLE_H_INCLUDED
 
struct keyvalue {
    char* key;
    void* value;
    size_t size;
    struct keyvalue* next;
};
 
typedef struct keyvalue* HashTable;
 
HashTable new_HashTable(char* key, void* value, size_t size);
 
int addEntry(HashTable hashtable, char* key, void* value, size_t size);
 
#endif // HASHTABLE_H_INCLUDED

Code HashTable.c :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "HashTable.h"
 
/* Constructeur d'une HashTable
   But        : Permet d'instancier un dictionnaire
   Paramètres : clef [char*], associé [void*], taille de l'associé [size_t] (Généralement sizeof(associe))
   Retour     : Dictionnaire nouvellement créé
*/
HashTable new_HashTable(char* key, void* value, size_t size){
 
    // Vérifier la conformité des paramètres formels
    if (key == NULL || value == NULL || size <= 0)
        return NULL;
 
    // Allouer dynamiquement et créer des copies de la clef
    // et de l'associé
    char* newKey = (char*)malloc(sizeof(key));
    void* newValue = malloc(size);
 
    if (newKey == NULL || newValue == NULL)
        return NULL;
 
    strcpy(newKey, key);
    memcpy(newValue, value, size);
 
    // Créer un nouveau dictionnaire
    HashTable newHashTable = (HashTable)malloc(sizeof(struct keyvalue));
 
    if (newHashTable == NULL)
        return NULL;
 
    newHashTable->key = newKey;
    newHashTable->value = newValue;
    newHashTable->size = size;
    newHashTable->next = NULL;
 
    return newHashTable;
}
 
/* Fonction addEntry
   But        : Ajouter une nouvelle entrée au dictionnaire passé en paramètre
   Paramètres : dictionnaire [HashTable], clef [char*], associé [void*], taille de l'associé [size_t] (Généralement sizeof(associe))
   Retour     : 1 si tout s'est bien déroulé, 0 sinon
*/
 
int addEntry(HashTable hashtable, char* key, void* value, size_t size){
 
    // Vérifier la conformité des paramètres formels
    if (hashtable == NULL || key == NULL || value == NULL || size <= 0)
        return 0;
 
    // Créer une copie du dictionnaire et accéder au dernier
    // élément du dictionnaire
    HashTable copy = hashtable;
 
    while (copy->next != NULL)
        copy = copy->next;
 
    // Allouer dynamiquement et créer des copies de la clef
    // et de l'associé
    char* newKey = (char*)malloc(sizeof(key));
    void* newValue = malloc(size);
 
    if (newKey == NULL || newValue == NULL)
        return 0;
 
    strcpy(newKey, key);
    memcpy(newValue, value, size);
 
    // Créer une nouvelle entrée dans le dictionnaire
    struct keyvalue* newKeyvalue = (struct keyvalue*)malloc(sizeof(struct keyvalue));
 
    if (newKeyvalue == NULL)
        return 0;
 
    newKeyvalue->key = newKey;
    newKeyvalue->value = newValue;
    newKeyvalue->size = size;
    newKeyvalue->next = NULL;
 
    // Ajouter l'entrée au dictionnaire
    copy->next = newKeyvalue;
 
    return 1;
}

Je compile donc le code en "Debug" sous CodeBlocks sous Ubuntu 8.10 (Compilateur gcc), tout se passe bien :

Clef : Test1 - Valeur : Ceci est une chaine
Clef : Entier - Valeur : 47
Clef : Reel - Valeur : 4.578900
Clef : Entier long - Valeur : 5432424
Clef : Structure - Valeur : Chuck Norris

pourtant quand je compile en "Release", j'ai plein d'erreurs qui s'affichent à l'exécution (en l'occurrence un buffer overflow) :



J'essaie aussi de compiler "à la main" avec gcc, pas d'erreur apparente :

erosquare@mvk-desktop:~/Documents/HashTable$ gcc *.c -I . -o test
erosquare@mvk-desktop:~/Documents/HashTable$ ./test
Clef : Test1 - Valeur : Ceci est une chaine
Clef : Entier - Valeur : 47
Clef : Reel - Valeur : 4.578900
Clef : Entier long - Valeur : 5432424
Clef : Structure - Valeur : Chuck Norris
erosquare@mvk-desktop:~/Documents/HashTable$

Quelqu'un saurait d'où pourrait venir ce "bug" svp? Merci d'avance.

[orfix]

Salut,

Je ne vois aucun free ...c'est normal ?
Je n'ai pas tout regarder, mais quand tu écrits :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
char* newKey = malloc(sizeof(key));
<...>
strcpy(newKey, key);

sais-tu que sizeof retourneras la taille de key un pointeur sur char qui dans les arcitectures 32bit est égale à 4 ?

EDIT : Essaie de mettre ton code entre les balises

[Erosquare]

Pour les free c'est normal, comme je l'ai précisé je viens de commencer à coder ce TAD. J'ai juste fait une fonction permettant d'instancier l'HashTable et une fonction addEntry pour ajouter une entrée, je n'ai pas encore codé les fonctions permettant de libérer la mémoire. Quand je fais :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
char* newKey = (char*)malloc(sizeof(key));
<...>
strcpy(newKey, key);

Je veux allouer autant d'octets dans la mémoire que key en contient. Vois ça comme :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

char* newKey = (char*)malloc((strlen(key) + 1) * sizeof char);

[crocodilex]

Essayes d'ajouter ça dans ton code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

printf("SIZE OF KEY = %d\n", sizeof(key));

Tu risques d'être surpris...

[Erosquare]

En effet, j'ai recompilé le code en effectuant quelques modifications dans le code, à savoir :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
char* newKey = (char*)malloc((strlen(key)+1) * sizeof(char));
memcpy(newKey, key, (strlen(key)+1)*sizeof(char));

Tout en mettant dans le code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
printf("SIZE OF KEY = %d\n", sizeof(key));
printf("SIZE OF KEY = %d\n", (strlen(key)+1)*sizeof(char));

Et le code s'exécute parfaitement maintenant en mode "Release" :

erosquare@mvk-desktop:~/Documents/HashTable/bin/Release$ ./HashTable
SIZE OF KEY = 4
SIZE OF KEY = 6
Clef : Test1 - Valeur : Ceci est une chaine
Clef : Entier - Valeur : 47
Clef : Reel - Valeur : 4.578900
Clef : Entier long - Valeur : 5432424
Clef : Structure - Valeur : Chuck Norris

J'étais persuadé que sizeof(key) me donnerait la même chose que strlen(key)+1) * sizeof(char). Enfin bref, merci beaucoup de votre efficacité

[ram-0000]

Juste une info,

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
char* newKey = (char*)malloc((strlen(key)+1) * sizeof(char));
memcpy(newKey, key, (strlen(key)+1)*sizeof(char));

peut se remplacer par :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

char* newKey = strdup(key);

[Erosquare]

Je ne connaissais pas strdup et effectivement c'est très utile, merci beaucoup.

[diogene]

J'étais persuadé que sizeof(key) me donnerait la même chose que strlen(key)+1) * sizeof(char).

Il faut quand même comprendre pourquoi :
sizeof donne la taille en byte de l'opérande (ou d'un objet du même type que l'opérande). key étant un pointeur sur char,

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

....new_HashTable(char* key, ......)

il donnera la taille d'un pointeur sur char, ce qui n'a rien à voir avec la taille d'un tableau dont l'adresse serait key.

En règle générale, une fonction n'a comme seuls moyens pour connaître la taille d'un tableau
- qu'on la lui indique en argument
- ou que le tableau soit constitué de telle façon que sa taille puisse se déduire de son contenu (cas des chaînes de caractères en C par la présence du zéro terminal, ce que détecte la fonction strlen())

Dans la fonction new_HashTable, il reste du travail à faire pour gérer correctement les erreurs d'allocation.
Par exemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
    if (newKey == NULL || newValue == NULL)
        return NULL;

Et si l'un des deux n'est pas NULL, comment récupérer la mémoire allouée ?

[Erosquare]

Ah oui, je n'avais pensé à ce cas en effet. Ca pourrait conduire à une fuite de mémoire si l'un des deux n'était pas libéré de la mémoire qu'il occupe, merci