Résumé
Dans cette série d'articles, nous présentons le langage C. Il ne s'agit pas de réécrire les ouvrages de référence donnés en annexe, mais de donner, au travers du C, une méthode de programmation basée sur la notion d'interface.
Au fur et à mesure de notre progression, nous décrirons les éléments indispensables du langage et conduirons le lecteur à consulter les ouvrages de références. Le but poursuivi est clairement de parvenir à construire des programmes de manière segmentée.
Ce mois-ci, nous allons nous intéresser aux tables de hachage réalisées en C. Nous avons déjà pu aborder ce sujet avec le langage Scheme dans le numéro 6 de Linux Magazine. Cette réalisation permettra de réaliser de petites bases de données.
Description
Ce mois-ci, nous allons réaliser une bibliothèque pour créer une table de hachage. Cette présentation sera aussi le prétexte pour aborder l'arithmétique des pointeurs, les entrées / sorties en C et la manipulation des données.
Les tables de hachage sont des structures très utilisées pour réaliser de petites bases de données. En effet, elles sont assez faciles à réaliser tout en restant assez efficaces. Les tables de hachage restent utilisables jusqu'à 500 000 enregistrements ; au-delà, on utilisera des structures plus complexes comme les b-arbres.
Le principe des tables de hachages est d'associer un identificateur à une donnée dans une structure, en permettant de retrouver la donnée rapidement, en connaissant l'identificateur. Elles sont réalisées à l'aide d'un tableau de taille fixe contenant des listes associant les identificateurs et les données.
Dans le numéro précédant, nous avons réalisé une bibliothèque permettant de construire des listes à doubles chaînes. Ces listes contiennent des pointeurs vers les objets à ranger. Cette technique possède l'avantage d'être peu coûteuse en terme d'occupation mémoire puis que les objets sont manipulés par leur référence ou adresse. Cependant, cette technique reste difficilement utilisable si la liste doit être sauvegardée dans un fichier. En effet, les pointeurs représentent des emplacements en mémoire qui ne restent pas identiques d'une exécution du programme à l'autre.
Les données, dans cette réalisation, seront recopiées intégralement dans les listes de la table. Les données pourront avoir des tailles différentes dans la même table, mais les identificateurs auront une taille constante.
Interface
Nous commencerons notre réalisation par spécifier l'interface de la bibliothèque, c'est-à-dire les fonctionnalités de la table.
Nous aurons dans l'interface :
ï‚· Une fonction de création et une fonction de destruction de table. La fonction de création aura comme paramètre la taille de table ; cette taille à une influence sur les performances et l'occupation mémoire. L'autre paramètre de la fonction de création est la taille de l'identificateur que nous souhaitons constant.
ï‚· Nous aurons ensuite une fonction permettant d'ajouter un couple formé d'un identificateur et d'une donnée dans la table. Comme les données peuvent avoir une taille variable, cette taille sera un paramètre de la fonction. Par contre, la taille de l'identificateur est constante et elle est spécifiée une fois pour toute au moment de la création de la table ; elle ne sera donc par un paramètre. Par convention, nous n'accepterons que les identificateurs uniques dans la table.
ï‚· Parallèlement à la fonction de création, nous aurons aussi une fonction de suppression d'un identificateur de la table. Cette fonction aura comme paramètre une table et un identificateur.
ï‚· Une fonction ayant comme paramètre une table et un identificateur permettra d'obtenir la taille de la donnée correspondante dans la table. Cette fonction sera utilisée pour allouer préalablement un espace suffisant permettant d'accueillir les données dans le cas où elles auront des tailles variables.
ï‚· Une autre fonction retrouvera le contenu d'une donnée de la table, connaissant l'identificateur. L'espace recevant la donnée devra avoir une taille suffisante.
ï‚· Puis nous aurons une fonction permettant de parcourir l'ensemble des couples de la table. Cette fonction aura comme paramètre une table, et une procédure à appliquer à l'ensemble des couples.
ï‚· Par la suite, nous ajouterons une fonction pour sauvegarder une table dans un fichier, et une fonction permettant de construire une table à partir d'un fichier.
Maintenant, nous allons préciser cette interface en écrivant le fichier d'en-tête hash.h regroupant l'ensemble des types de données et des prototypes des fonctions publiques.
Dans ce fichier, tous les noms définis seront préfixés par le mot hash. En effet, si nous utilisons un nom de type de données trop commun, comme Ident, il risquerait d'entrer en conflit avec une autre bibliothèque définissant elle aussi le type Ident. De même, le langage C n'autorise à définir qu'une seule fois le nom d'une fonction publique ; là aussi, si nous utilisons un nom trop commun, comme creer, il risquerait de rentrer en conflit avec la fonction creer d'une autre bibliothèque.
Nous avons donc :
#ifndef
___HASH_H
#define ___HASH_H
/* TYPES DE
DONNEES */
/* Table de hachage */
typedef
struct Hash * Hash;
/* Identificateur */
typedef
char *
HashIdent;
/* codes de retour */
typedef
enum {
HASH_OK, /*
pas d'erreur */
HASH_ERREUR, /*
erreur indéfinie */
HASH_DOUBLON, /*
existe déjà */
HASH_INTROUVABLE /*
n'existe pas */
} HashStatus;
/* PROTOTYPES DES
FONCTIONS */
Hash hash_cree
(int
taille_table,
int
taille_ident);
HashStatus hash_detruit
(Hash hash_table);
HashStatus hash_ajoute
(Hash hash_table,
char
* identificateur,
void
* donnee,
int
taille);
HashStatus hash_enleve
(Hash hash_table,
char
*
identificateur);
int hash_taille (Hash hash_table,
char
* identificateur);
HashStatus hash_donne
(Hash hash_table,
char
* identificateur,
void *
donnee,
int
* taille);
HashStatus hash_tous (Hash
hash_table,
void
* paramètre,
int
(* proc) (void
* parametre,
char
* identificateur,
void
* donnee,
int
taille));
HashStatus hash_sauve
(Hash hash_table,
char
* fichier);
Hash hash_charge
(char * fichier);
#endif /* ___HASH_H */
Dans ce fichier, nous retrouvons en premier la définition des types de données publiques : le type Hash est défini comme étant un pointeur sur une structure de donnée struct Hash qui n'est pas spécifié dans ce fichier. Cette déclaration permet de garder opaque la structure de données. Ensuite, nous définissons le HashIdent comme étant un pointeur sur un caractère. C'est en fait la manière de déclarer une chaîne de caractère en C. Ensuite nous déclarons les codes de retour des fonctions comme étant une énumération. Le compilateur donnera automatiquement une valeur numérique aux valeurs symboliques définies. Nous verrons dans la réalisation la signification de ces valeurs.
Ensuite, les fonctions publiques de la bibliothèque sont déclarées. Nous retrouvons les fonctions dont nous avons parlé plus haut, comme les fonctions de création et de destruction d'une table, les fonctions d'ajout, de suppression, d'obtention de la taille et d'obtention d'une donnée dans une table, la fonction de parcours des éléments d'une table sur laquelle nous allons revenir, et les fonctions d'entrée / sortie sur fichiers.
La fonction de parcours hash_tous mérite une explication supplémentaire. Elle est destinée à appliquer une fonction proc à tous les couples d'une table. On appelle généralement la fonction proc fonction callback ou fonction de rappel. Aussi, elle prend comme paramètre la table hash, et la fonction proc. L'écriture utilisée pour déclarer le paramètre proc signifie textuellement que proc est ``un pointeur sur une fonction retournant un entier et prenant comme argument un pointeur de type void * représentant un paramètre, une chaîne de caractère représentant l'identificateur, un pointeur void * représentant la donnée et un entier représentant la taille de la donnée''. La fonction hash_tous sera invoquée avec un paramètre void * qui sera donné tel quel en argument à la fonction proc. Cette écriture permet de paramétrer la fonction de parcours sans utiliser de variables globales.
Utilisation
Ayant définit l'interface de la bibliothèque, nous pouvons dès à présent programmer un exemple l'utilisant. Ceci permettra de fixer les idées quant à son utilisation, ce qui facilitera la compréhension de la réalisation proprement dite de la bibliothèque.
#include
<stdio.h>
#include <stdlib.h>
#include
<hash.h>
void main (void) {
Ces écritures maintenant familières incluent l'en-tête de la bibliothèque standard d'entrée / sortie, l'en-tête de la bibliothèque standard et notre en-tête pour les tables de hachage. Le nom des fichiers d'en-tête à inclure est généralement donné dans les pages de manuel des fonctions ; ainsi, la commande man abort affichera la page de manuel de la fonction abort, et on peut voir dans cette page qu'il est nécessaire d'inclure stdlib.h avant d'utiliser cette fonction.
Il vient ensuite :
# define
TAILLE_IDENTIFICATEUR 5
Hash hash;
struct
{
char nom[10];
char
prenom[10];
int
age;
} personne;
char
identificateur[TAILLE_IDENTIFICATEUR];
char
format_identificateur[10];
Cette écriture commence par définir une macro TAILLE_IDENTIFICATEUR. Cette macro permet de rendre le programme plus lisible et permet aussi de modifier en une seule écriture la taille des identificateurs.
Ensuite, nous déclarons une variable hash de type Hash qui contiendra une table de hachage. Puis une structure (et non pas un type) appelée personne est déclarée. Cette structure contient deux tableaux de 10 caractères nommés nom et prenom, et un entier nommé age.
Puis une chaîne de TAILLE_IDENTIFICATEUR caractères destinée à recevoir les identificateurs est déclarée ainsi qu'une chaîne de 10 caractères scan_ident. Cette dernière contiendra la chaîne de format à utiliser avec la fonction scanf pour lire les identificateurs. En effet, les identificateurs ont une taille constante et limitée. Nous pourrions les lire avec scanf("%s",identificateur), mais cela causerait une erreur mémoire si l'utilisateur entrait une chaîne de caractère plus grande. Pour éviter ce risque, il faudrait lire les identificateurs avec scanf("%5s",identificateur) : le 5 placé entre le % et le s permet de limiter la lecture à 5 caractères au maximum. Le problème est que la taille de l'identificateur est définie par une macro. En définissant la variable scan_ident et en l'initialisant correctement, nous allons pouvoir créer une chaîne de format sur mesure.
Nous avons ensuite :
/*
création du format des identificateurs */
sprintf
(format_identificateur,
"%%%ds",
TAILLE_IDENTICATEUR);
/*
création de la table et test */
hash =
hash_cree (100, TAILLE_IDENTIFICATEUR);
if (!
hash) abort();
La première ligne initialise justement la chaîne de format pour les identificateurs. Pour cela, nous utilisons une fonction de la famille de printf qui écrit son résultat non pas à l'écran, mais dans un buffer de réception sous la forme d'un tableau de caractères. Attention, le buffer doit être suffisamment grand pour recevoir le résultat, et aucune vérification de taille n'est effectuée. Dans notre cas, la chaîne format_identificateur vaudra "%5s".
Ensuite, nous créons la table avec le résultat de la fonction hash_creer. La table créée aura une taille de 100 listes (nous verrons plus bas ce que ça signifie) et les identificateurs auront une taille constante de TAILLE_IDENTIFICATEUR caractères. Nous testons la valeur de la variable hash ; si elle vaut zéro, la table n'a pas pu etre créée et dans ce cas, nous interrompons (violemment) le programme en invoquant abort(). On pourra ici créer une fonction de traitement des erreurs plus conviviale.
Nous pouvons maintenant remplir la table :
/*
remplissage de table */
do {
/*
lecture de l'identificateur */
printf
("identificateur:");
scanf
(format_identificateur, identificateur);
if
(! * identificateur) break;
/*
lecture du nom, prénom et age */
printf
("nom:");
scanf ("%s",
personne.nom);
printf
("prenom:");
scanf
("%s", personne.prenom);
printf
("age:");
scanf ("%d",
& personne.age);
/* ajout dans
la table */
hash_ajoute
(hash,
identificateur,
&
personne,
sizeof
(personne));
} while (1);
Le remplissage est une boucle sans condition d'arrêt do...while(1).
Nous invitons l'utilisateur à entrer l'identificateur de la personne, que nous lisons avec la fonction scanf. Si l'utilisateur saisit un identificateur vide, c'est notre convention pour indiquer que la saisie est terminée ; aussi, nous effectuons un break qui nous sort de la boucle while. Nous saisissons ensuite le nom, le prénom et l'age de la personne. Enfin, nous ajoutons la structure personne dans la table. Nous rappelons que la fonction scanf lit des valeurs de l'entrée standard (généralement, le clavier) dont le type est spécifié par les champs % de sa chaîne de format, et place les résultats aux adresses correspondantes qui lui sont passées en argument. Les variables identificateur, personne.nom et personne.prenom ont pour valeur l'adresse du premier caractère du tableau ; quant à la variable age, il est nécessaire de préfixer la variable par l'opérateur & du langage C pour en obtenir l'adresse.
Maintenant que nous avons rempli la table, nous pouvons l'interroger :
/*
interrogation de table */
do {
/*
saisie de l'identificateur */
printf
("identificateur:");
scanf
(format_identificateur, identificateur);
if
(! * identificateur) break;
/*
recherche dans la table */
if
(hash_donne (hash, identificateur, & personne, 0)
!=
HASH_OK) {
printf
("Identificateur inconnu
`%s'\n",
identificateur);
continue;
}
/*
affichage des informations */
printf
("identificateur: %s\n", identificateur);
printf
("nom: %s\n",
personne.nom);
printf
("prenom: %s\n",
personne.prenom);
printf
("age:" %d\n",
personne.age);
} while (1);
}
L'interrogation de la table repose elle aussi sur une boucle sans fin. Elle commence par demander à l'utilisateur un identificateur lu avec la fonction scanf et le format_identificateur. Si l'identificateur est vide, par convention, nous interrompons la boucle, ce qui met un terme au programme.
On interroge ensuite la table. Dans notre cas, la taille de la donnée à lire est parfaitement connue puisqu'il s'agit d'une personne. Nous n'avons donc pas besoin d'obtenir la taille de la donne ; aussi nous donnons par convention un pointeur nul pour la taille. La fonction hash_donne ne retourne HASK_OK qu'en cas de succès. Si la valeur est différente, une erreur s'est produite et nous exécutons l'instruction continue, ce qui a pour effet de nous replacer au début du while.
En cas de succès, hash_donne remplit la zone dont l'adresse est donnée en second argument par la donnée elle-même. La structure personne contient donc les informations requises que nous empressons d'afficher !
Nous en avons terminé pour cette fois-ci avec les tables de hachage. La prochaine fois, nous réaliserons la bibliothèque proprement dite. Mais nous allons examiner quelques points importants.
Pointeur, tableau et arithmétique
Chaînes de caractères
Le langage C range les chaînes de caractères dans un format particulier. Lorsque nous écrivons :
char * s = "chaine";
le langage C réserve l'espace d'un pointeur pour s, puis un tableau de 7 caractères (et non pas 6). La première cellule de ce tableau contient le code ASCII du caractère 'c', la seconde, le code du caractère 'o', et ainsi de suite. La septième cellule contient le caractère nul (zéro). Le langage C stocke les chaînes de caractère en ASCIIZ, c'est-à-dire en ASCII terminé par le caractère nul. Toute chaîne de caractères occupe donc un caractère de plus que ce que l'on peut compter.
Ainsi, si on souhaite dupliquer une chaîne de caractères, on pourra écrire :
#include
<string.h>
char * duplique_chaine (char *
source) {
char * destination = 0;
if
(source) {
/* calcule de la longueur de
la source */
int longueur =
strlen (source);
/*
allocation de la detination */
destination
= malloc (longueur + 1);
if
(destination) {
/* recopie de
la source dans la
*
destination */
strcpy
(destination, source);
}
}
return
destination;
}
On notera l'allocation d'un caractère supplémentaire. Attention, l'oubli de ce caractère supplémentaire ne provoque que rarement une erreur. Cela est dû au fait que la fonction d'allocation malloc utilise une certaine granularité, et donc, dans la plupart des cas, des octets supplémentaires sont alloués à notre insu pour éviter une fragmentation trop importante de la mémoire. Cependant, ce type d'erreur reste très difficile à identifier. Il faut donc rester très prudent lorsque l'on manipule des chaînes de caractères en C.
Pointeur et tableau
Le langage C peut sembler parfois un peu confus lorsque l'on manipule des tableaux. Considérons :
int
i, * tab = malloc (sizeof (int) * 10);
for
(i = 0; i < 10; i++) {
tab[i] = i;
}
Ici, nous déclarons un entier i et un pointeur tab vers un entier. Nous allouons une zone de mémoire avec malloc dont la taille est celle de 10 entiers. Nous plaçons l'adresse de cette zone (l'adresse du premier entier) dans la variable pointeur tab. Nous avons la topologie suivante :
-
Adresse
Variable
Valeur
100
i
10
104
tab
10C
108
...
...
...
40C
0
410
2
414
3
418
4
41C
5
420
6
424
7
428
8
42C
9
430
Nous conviendrons que nous travaillons sur un processeur 32 bits comme un Pentium.
Comme il est d'usage, les adresses sont écrites en hexadécimal, base numérique dont nous avons eu l'occasion de parler dans un numéro précédent. A l'adresse 100, nous avons la variable i, tenant sur 4 octets car c'est un entier. A l'adresse suivante, nous trouvons le pointeur tab tenant lui aussi sur quatre entiers et contenant l'adresse de la zone retournée par malloc, à l'adresse 40C.
Ensuite, nous pouvons manipuler tab comme un tableau : lorsque nous écrivons tab[5], la machine lit l'adresse contenue dans la variable tab et elle lui ajoute un déplacement de 5 entiers, c'est à dire 5x4 octets (voir plus loin le paragraphe concernant l'aritmétique des pointeurs).
Considérons maintenant :
int
i, tab[10];
for (i = 0; i < 10; i++) {
tab[i]
= i;
}
Cette fois-ci, tab est l'adresse (constante) de la première du premier entier d'une zone de dix. Il n'y a plus de variable pointeur, et d'ailleurs, on ne peut modifier la valeur de tab lors qu'on le pouvait dans le premier exemple. Dans ce cas, nous avons la topologie suivante :
-
Adresse
Variable
Valeur
100
i
10
104
108
...
...
...
40C
tab
0
410
2
414
3
418
4
41C
5
420
6
424
7
428
8
42C
9
430
Attention, dans les deux exemples, le compilateur ne tient aucun compte de la taille du tableau ; dans les deux cas, on pourra écrire tab[100] sans provoquer d'erreur. Ceci est une source d'erreur que même les programmeurs expérimentés en langage C rencontrent.
Arithmétique des pointeurs
En C, 1+1 ne vaut pas forcément 2 !
En effet, si nous écrivons :
int
i = 1;
i = i + 1;
A la fin, i vaudra 2 ... Parfait ! Considérons maintenant :
int
* i = 1;
i = i + 1;
Là, i vaudra 5 !
La raison est que i est maintenant un pointeur sur un entier. Incrémenter une adresse de un signifie placer le pointeur (d'où son nom :) sur l'entier suivant en mémoire. Si le premier entier se situe à l'adresse 1, l'entier suivant se situe 4 octets plus loin car un entier occupe 4 octets et les adresses en mémoire référencent des octets.
Avec les pointeurs, le seul cas où 1+1=2 est lorsqu'il s'agit d'un pointeur sur un caractère :
char
* i = 1;
i = i + 1;
Ici, i vaut 2 parce que un caractère est codé sur un octet et que l'octet se situant immédiatement après l'octet situé à l'adresse 1 est situé à l'adresse 2.
Le seul cas où le compilateur refuse d'effectuer un calcule sur les pointeurs se rencontre lorsque le pointeur est de type void *. Dans ce cas, le compilateur est parfaitement incapable de déterminer le type de la donnée pointée, et donc d'en calculer la taille afin de déterminer l'incrément. Essayez sur votre système favori les différents exemples sans tenir compte des quelques warnings qui signalent des opérations dangereuses, et pour cause !
L'aritmétique des pointeurs peut sembler compliquée de prime abord, c'est en fait très logique et simplifie grandement la programmation.
L'auteur
Guilhem de Wailly, directeur de la société Erian Concept, partenaire NetUltra (www.netultra.net) et Getek (www.getek.fr).
|
|
Votre interlocuteur Linux ! Support, formations, configurations, administration, développements Linux. http://www.erian-concept.com |
Références
Langage C - norme ANSI : bon ouvrage de référence
Ph.
DRIX
Masson
Programmer en C++: une bonne référence
S.C.
DEWHURST et K.T. STARK
Masson
Le Langage C: la bible!
B.W. KERNIGHAN et D.M.
RITCHIE
Masson
gcc: compilateur C du GNU, et tous les outils de
développement
http://www.gnu.org
Kdevel: un environnement KDE de programmation
C
http://samuel.cs.uni-potsdam.de/~smeier/kdevelop_new/index.html