Le langage C (19)

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 continuer à 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.

Nous allons plus particulièrement nous pencher sur la sauvegarde et la restauration d'une table sur disque. Nous examinerons aussi sommairement les modes de stockage des valeurs de plus de huit bits dans la mémoire et son influence sur la compatibilité binaire des fichiers de données lorsqu'ils sont partagés sur un réseau hétérogène.

Description

Nous étions en train de construire une bibliothèque de manipulation de tables de hachages et nous étions arrivés au point où nous allions les sauvegarger sur disque, lorsque nous nous sommes attachés à décrire les fonctions d'éntrées / sortie de la bibliothèque standard du langage C.

Il est maintenant temps de revenir aux tables de hachages en programmant les dernières fonctions.

Les sources de la bibliothèque sont disponibles à l'adresse:

http://www.erian-concept.com/pub/hash.tgz

L'interface de la bibliothèque est :

#ifndef ___HASH_H
#define ___HASH_H

/* TYPES DE DONNEES */
/* Table de hachage */
typedef struct Hash * Hash;

/* 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_donnee);
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_donnee);
HashStatus hash_tous    (Hash   hash_table,
                         void * paramètre,
                         int (* proc) (void * parametre,
                                       char * identificateur,
                                       void * donnee,
                                       int    taille_donnee));
HashStatus hash_sauve   (Hash   hash_table,
                         char * fichier);
Hash       hash_charge (char * fichier);

#endif /* ___HASH_H */

Nous allons nous occuper des fonctions hash_sauve et hash_charge qui prendront place dans le fichier hash.c. Nous rappellons que les structures de données manipulées sont :

/* cellule */
typedef struct Cellule * Cellule;

typedef struct Cellule {
Cellule suivante;
char * identificateur;
int taille_donnee;
void * donnee;
} _Cellule;

et :

/* table de hashage (hash.h) */
typedef struct Hash * Hash;

/* table de hashage (hash.c) */
typedef struct Hash {
int taille_table;
int taille_identificateur;
Cellule * table;
} _Hash;

Sauvegarde

Pour la sauvegarde, nous allons utiliser la fonction de parcourt des cellules hash_tous qui prend en argument une table de hachage, un paramètre libre et une fonction de rappel ; pour toutes les entrées de la table de hachage, la fonction de rappel est appelée avec comme arguments le paramètre libre, l'identificateur, la donnée stockée dans la table et la taille de cette donnée.

La fonction de sauvegarde est donc :

/* Mot magique pour information et contrôle */
static char _mot_magic[] = "HashTable 1.0 pour LinuxMag\n";

/* Sauve une table de hachage dans un fichier */
HashStatus hash_sauve (Hash hash_table,
                 char * nom_fichier) {
FILE     * fichier;
  HashStatus status = HASH_ERREUR;

  /* vérification des arguments */
  assert (hash_table);
  assert (nom_fichier && * nom_fichier);

  /* Ouverture du fichier en écriture. Le contenu
   * précédent, s'il existait, est effacé */
fichier = fopen (nom_fichier, "w");
if (! fichier) {
goto Erreur;
}
/* écriture du mot magique */
if (fwrite (_mot_magique,
         strlen (_mot_magic) + 1,
        1,
         fichier) != 1) {
goto Erreur;
}
/* écriture de la taille de la table */
if (fwrite (& hash_table->taille_table,
         sizeof (int),
        1,
         fichier) != 1) {
goto Erreur;
}
/* écriture de la taille des identificateurs */
if (fwrite (& hash_table->taille_identificateur,
         sizeof (int),
         1,
         fichier) != 1) {
goto Erreur;
}
  /* la fonction de rappel _sauve_cellules
   * est appelée pour toutes les entrées
   * de la table */
status = hash_tous (hash_table,
                      (void *) fichier,
                      _sauve_cellules);

Erreur:
if (fichier) fclose (fichier);
  if (status != HASH_OK) {
    /* en cas d'erreur, effacer le fichier */
    unlink (nom_fichier);
  }
  return (status);
}

Le fichier est ouvert et on commence par écrire un mot magique qui servira pour informer de la nature du fichier une fois qu'il sera écrit et pour contrôler la nature du fichier, à l'ouverture.

Puis on sauvegarde la taille de la table et la taille des identificateurs. La fonction _sauve_cellules définie ci-dessous est ensuite invoquée pour toutes les entrées de la table de hachage. Si cette fonction retourne le code d'erreur pour l'une des cellule, l'itération est interrompue et la fonction hash_tous retourne le code d'erreur, qui devient le résultat de la fonction hash_sauve. Si l'itération se poursuit jusqu'à la fin, hash_tous retourne HASH_OK, qui devient le résultat de l'appel à hash_sauve.

Le traitement des erreurs est grandement simplifié par l'utilisation de l'instruction goto ; il faut cependant faire très attention à ce que les variables soient correctement initialisées.

La fonction _sauve_cellules est invoquée pour toutes les cellules de la table ; elle est responsable de la sauvegarde de l'entrée dans le fichier. Le fichier est le paramètre libre passé à la fonction hash_tous dans hash_sauve.

On a :

/* Fonction de rappel de la fonction hash_tous.
* Sauve l'entrée de la table à la fin du fichier
* passé en paramètre libre.
*/
static int _sauve_cellules (void * parametre,
                         char * identificateur,
                         void * donnee,
                         int taille_donnee) {
int status;
/* récupération du fichier */
FILE * fichier = (FILE *) parametre;
int longeur = strlen (identificateur) + 1;

/* écriture de la longueur de l'identificateur */
status = fwrite (& longeur,
                 sizeof (int),
                 1,
                 fichier);
if (status != 1) return (0);

/* écriture de l'identificateur */
status = fwrite (identificateur,
                 longeur,
                 1,
                 fichier);
if (status != 1) return (0);

/* écriture de la longueur de la donnée */
status = fwrite (& taille_donnee,
                 sizeof (int),
                 1,
                 fichier);
if (status != 1) return (0);

/* écriture de la donnée */
status = fwrite (donnee,
                 taille_donnee,
                 1,
                 fichier);
if (status != 1) return (0);

return (1);
}

La fonction de sauvegarde des cellules se contente d'écrire à la fin du fichier les informations concernant la cellule en cours. Le pointeur de fichier est toujours position à la fin des données écrites ou lues. Elle reçoit en argument un argument libre sous la forme d'un pointeur anonyme, un identificateur sous la forme d'une chaîne de caractères en ASCIIZ, une données sous la formes d'un tableau d'octet, et la longueur de la donnée. L'argument libre est, dans notre cas, un pointeur vers la structure du fichier où écrire les données.

Nous écrivons la longueur de l'identificateur, puis l'identificateur, suivit de la longueur de la donnée pour terminer par la donnée elle-même. Les écritures sont effectuées avec la fonction fwrite vue dans l'article précédent ; elle retourne le nombre d'items écrits. Ici, nous testons que la valeur de retour de chaque fwrite est 1, pour un item. Dans le cas où cette valeur est différente, nous interrompons l'itération en retournant zéro.

Il ne nous reste maintenant qu'à décrire la fonction de chargement.

Chargement

La fonction de chargement procède de manière inverse à la fonction de sauvegarde. Elle est aussi bâtie en deux fonction, une fonction principale qui ouvre le fichier et initialise une table et une fonction qui lit chaque entrée de la table à partir du fichier :

/* Lecture d'une table à partir d'un fichier */
Hash hash_charge (char * nom_fichier) {
int taille_table;
int taille_identificateur;
  char       tampon[100];
Hash hash_table = 0;
FILE * fichier;

  /* vérification des arguments */
  assert (nom_fichier && * nom_fichier);

/* Ouverture du fichier en lecture */
fichier = fopen (nom_fichier, "r");
if (! fichier) {
goto Erreur;
}
  /* lecture du mot magique */
if (fread (tampon,
         strlen (_mot_magic) + 1,
         1,
         fichier) != 1) {
goto Erreur;
}
/* vérification du mot magique */
if (strcmp (tampon, _mot_magique)) {
    goto Erreur;
  }
/* lecture de la taille de la table */
if (fread (& taille_table,
         sizeof (int),
         1,
         fichier) != 1) {
goto Erreur;
}
/* lecture de la taille des identificateurs */
if (fread (& taille_identificateur,
         sizeof (int),
         1,
        fichier) != 1) {
goto Erreur;
}
/* création de la table */
hash_table = hash_cree (taille_table,
                          taille_identificateur);
if (! hash_table) {
goto Erreur;
}
/* lecture des enregistrements jusqu'à
   * la fin de fichier */
while (! feof (fichier)) {
if (! _charge_cellule (fichier, hash_table)) {
goto Erreur;
}
}
fclose (fichier);
return (hash_table);

Erreur:
/* en cas d'erreur, fermer le fichier
   * et détuire la table */
if (fichier) fclose (fichier);
if (hash_table) hash_detruit (hash_table);
return (0);
}

La fonction commence par ouvrir le fichier dont le nom est donnée en argument ; en cas d'erreur, on utilise un branchement goto pour simplifier le traitement. En général, le traitement des erreur doit défaire tout ce qui a été fait, c'est à dire, généralement, fermer les fichiers ouverts, déallouer des blocs de mémoires et détruire des structures de données. Dans notre cas, nous fermons le fichier s'il est ouvert et nous détruisons la structure de la table de hachage s'il elle est créée. Ce mode de fonctionnement impose que les variables testées soient initialisées, ce qui est le cas pour la variable fichier et la variable hash_table.

Nous lisons ensuite le mot magique. Le tampon doit être déclaré suffisamment grand pour contenir le mot qui est lu. On compare le mot lu au mot magique afin de vérifier que le fichier ouvert est bien un fichier de table de hachage.

Nous lisons ensuite la taille de la table et la taille des identificateurs. Ces dernières informations nous permettent de créer une table de hachage vierge que nous remplissons avec les entrées sauvée dans le fichier avec une itération. Cette itération prend fin lorsque la fin de fichier est atteinte.

Enfin, nous retournons la table.

La fonction _charge_celule qui lit chaque entrée de la table est :

/* Lecture d'une cellule */
static int _charge_cellule (FILE * fichier,
Hash hash_table) {
int taille_identificateur;
int taille_donnee;
char * identificateur = 0;
void * donnee = 0;
int erreur = 1;

/* lecture de la taille de l'identificateur */
if (fread (& taille_identificateur,
sizeof (int),
1,
fichier) != 1) {
goto Erreur;
}
/* allocation pour l'identificateur */
identificateur = malloc (taille_identificateur);
if (! identificateur) {
goto Erreur;
}
/* lecture de l'identificateur */
if (fread (identificateur,
taille_identificateur,
1,
fichier) != 1) {
goto Erreur;
}
/* lecture de la taille de la donnée */
if (fread (& taille_donnee,
sizeof (int),
1,
fichier) != 1) {
goto Erreur;
}
/* allocation pour la donnée */
donnee = malloc (taille_donnee);
if (! donnee) {
goto Erreur;
}
/* lecture de la donnée */
if (fread (donnee,
taille_donnee,
1,
fichier) != 1) {
goto Erreur;
}
/* ajout dans la table du couple
* identificateur-donnée */
hash_ajoute (hash_table,
identificateur,
donnee,
taille_donnee);
erreur = 0;

Erreur:
/* libération des allocations */
if (identificateur) free (identificateur);
if (donnee) free (donnee);
return (erreur);
}

La fonction lit la taille de l'identificateur et alloue une zone de mémoire de cette taille, puis elle lit l'identificateur. Ensuite, elle lit la taille de la donnée et alloue une zone de mémoire de cette taille ; elle y lit la donnée. Elle ajoute ensuite à la table le couple identificateur-donnée. Enfin, elle libère les ressources allouées.

Les indiens sont là !

En C, un tableau de caractères est un tableau de caractères ! C'est une suite d'octets dont l'adresse est chaque fois supérieure de 1 de la précédente. Lorsque l'on écrit une chaîne de caractères dans un fichier, les caractères sont écrits dans l'ordre, du premier au dernier. L'ordre dans lequel sont écrit les octets est immuable, quelque soit l'ordinateur.

Ceci n'est pas vrai pour les entiers ! En effet, il y a deux manière de ranger un entier en mémoire, soit en plaçant le poids fort en premier, soit en plaçant le poids fort en dernier. Ces modes de stockages sont appelés respectivement little endian et big endian. Par exemple, les processeurs Intel (PC) sont en mode big endian alors que les PowerPC (Machintoch) ou Sparc (Sun) sont en little endian. Si on désire qu'un fichier soit lisible sur plusieurs systèmes, il convient de faire attention à ces modes de stockage. Il existe moins deux solutions : écrire toutes les données sous la forme de chaînes de caractères (les entiers sont préalablement convertis en chaînes), soit écrire une fonction d'écriture des entiers tenant compte du mode de fonctionnement.

Pour détecter le mode de fonctionnement, considérons le programme :

#include <stdio.h>

void main (void) {
union {
int entier;
char octet[4];
} u;

u.entier = 0x12345678;

printf ("entier=0x%x, c[0]=0x%x, c[1]=0x%x, c[2]=0x%x, c[3]=0x%x\n",
         u.entier,
         (unsigned) u.octet[0],
         (unsigned) u.octet[1],
         (unsigned) u.octet[2],
         (unsigned) u.octet[3]);
if (u.octet[0] == 0x12)
printf ("Cet ordinateur est en little endian\n");
else
printf ("Cet ordinateur est en big endian\n");
}

Le principe est de placer dans une union un entier et un tableau de caractère. On rappelle que les unions placent tous leurs camps dans la même zone mémoire. En écrivant une valeur entière dans le champs entier et en examinant la manière avec laquelle sont stockés les octets dans le tableau, on peut déterminer le mode de fonctionnement du processeur sur lequel le programme fonctionne.

Exécuté sur un PC, ce programme affiche :

(Intel) $ ./a.out
entier=0x12345678, c[0]=0x78, c[1]=0x56, c[2]=0x34, c[3]=0x12
Cet ordinateur est en big endian

Exécuté sur une stations Sun 32 bits, ce programme affiche :

(Sparc) $ ./a.out
entier=0x12345678, c[0]=0x12, c[1]=0x34, c[2]=0x56, c[3]=0x78
Cet ordinateur est en little endian

Cela se traduit par l'occupation en mémoire suivante :

Adresse	Octet	Adresse	Octet
100	0x78	100	0x12
101	0x56	101	0x34
102	0x34	102	0x56
103	0x12	103	0x78

Big endian

Little endian

Nous allons écrire une fonction d'écriture d'entier et une fonction de lecture, indépendante du mode de stockage. De cette manière, les fichiers seront compatibles avec les différents processeurs, quelque soit leur mode de fonctionnement. Par défaut, on choisit d'utiliser le mode little endian pour sauver les entiers. On a :

static int ecrit_entier32 (int entier, FILE * fichier) {
union {
int entier;
char octet[4];
} u;

u.entier = 0x12345678;

/* détection du mode */
if (u.octet[0] == 0x12) {
/* little endian --> little endian */
if (fwrite (& entier, 4, 1, fichier) != 1) return (0);
}
else {
/* big endian --> little endian */
u.entier = entier;
if (fwrite (& u.octet[3], 1, 1, fichier) != 1) return (0);
if (fwrite (& u.octet[2], 1, 1, fichier) != 1) return (0);
if (fwrite (& u.octet[3], 1, 1, fichier) != 1) return (0);
if (fwrite (& u.octet[0], 1, 1, fichier) != 1) return (0);
}
return (1);
}

La fonction connexe de lecture est définie par :

static int lit_entier32 (int * entier, FILE * fichier) {
union {
int entier;
char octet[4];
} u;

u.entier = 0x12345678;

/* détection du mode */
if (u.octet[0] == 0x12) {
/* little endian --> little endian */
if (fread (entier, 4, 1, fichier) != 1) return (0);
}
else {
/* little endian --> big endian */
if (fread (& u.octet[3], 1, 1, fichier) != 1) return (0);
if (fread (& u.octet[2], 1, 1, fichier) != 1) return (0);
if (fread (& u.octet[3], 1, 1, fichier) != 1) return (0);
if (fread (& u.octet[0], 1, 1, fichier) != 1) return (0);
* entier = u.entier;
}
return (1);
}

On pourrait décliner, en fonction des besoins, ces fonctions pour lire et écrire des entiers sur seize et soixante quatre bits.

Nous devons maintenant utiliser ces fonctions pour écrire et lire les différentes entier dans le programme des tables de hachage. Par exemples, on replace dans la fonction hash_sauve le fragment de code :

/* écriture de la taille de la table */
if (fwrite (& hash_table->taille_table,
         sizeof (int),
        1,
         fichier) != 1) {
goto Erreur;
}

par le fragment :

/* écriture de la taille de la table */
if (ecrit_entier32 (hash_table->taille_table,
fichier) != 1) {
goto Erreur;
}

et dans la fonction hash_charge, on remplace le fragment de code :

/* lecture de la taille de la table */
if (fread (& taille_table,
           sizeof (int),
         1,
         fichier) != 1) {
goto Erreur;
}

par le fragment :

/* lecture de la taille de la table */
if (lit_entier32 (& taille_table,
fichier) != 1) {
goto Erreur;
}

De cette manière, les fichiers seront indépendant de la plate-forme y ayant accès, ce qui est important avec les possibilités de partages des fichiers qu'offre les systèmes d'exploitation évolué comme Linux, notamment avec NFS.

La bibliothèque de manipulation des tables de hachage est maintenant terminée et utilisable pour créer de petites bases de données.

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