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 utiliser les tables de hachage pour concevoir un petit gestionnaire de bases de données. Ce gestionnaire est sans grandes prétentions et il est a cent mille lieux d'un vrai moteur de bases de données. Il a cependant le mérite de poser les problèmes et de faire prendre conscience de la complexité de ces engins.
Description
Le mois dernier, nous avons fini la réalisation de la bibliothèque de manipulation des tables de hachage. Ce mois-ci, nous allons utiliser cette bibliothèque pour réaliser un petit moteur de bases de données. Notre propos n'est pas ici de réaliser un vrai moteur, mais plutôt un gestionnaire de tables à vocation pédagogique.
Nous avons modifié la bibliothèque des tables de hachages pour qu'elles puissent gérer les identificateurs binaire en plus des chaînes de caractères. La nouvelle version est intégrée dans le fichier http://www.erian-concept.com/pub/donnee.tgz.
Le principe d'un gestionnaire de tables est de permettre de manipuler des données constituées d'enregistrements, eux-mêmes composés de champs. Pour permettre un accès rapide, on associe aux tables des indexes sur certains de leurs champs. Bien entendu, ces indexes seront réalisés ici à l'aide de tables de hachage. Dans de vrais moteur, des structures plus complexes, comme les b-arbres (b-trees) sont utilisés.
Mais examinons l'utilisation des tables par l'exemple. Voici un exemple de programme les utilisant :
#include
<assert.h>
#include <stdio.h>
#include
<stdlib.h>
#include <donnee.h>
/*
Programme principal */
int main (void)
{
/* Une structure de donnée représentant une
personne.
* Cette structure n'est utilisée que
temporairement
*/
struct {
int
numero;
char nom[20+1];
char
prenom[20+1];
char sexe;
int age;
}
personnel;
/* Descripteur des champs de la base de
données */
_Descripteur descripteur =
{/* Mot
réservé */
0,
/* Entête du
fichier des données */
"Fichier du personnel
:)",
/* Tableau des champs de la base */
/*
type nom longueur index? */
{{
CHAMP_ENTIER, "numéro", 0, 1},
{
CHAMP_CHAINE, "nom", 20, 0},
{
CHAMP_CHAINE, "prénom", 20, 0},
{CHAMP_CARACTERE, "sexe", 0, 0},
{
CHAMP_ENTIER, "age", 0, 0},
/*
indicateur de fin de champ */
{CHAMP_DERNIER}}};
Donnee donnee;
Enreg enreg;
int i, n;
/*
Création d'une base de donnée */
donnee =
donnee_cree ("personnel.dta",
&
descripteur);
/* Création de 20 personnes */
for (i = 0; i < 20; i++) {
/* Remplissage du nom
*/
for (n = 0; n < 20; n++) {
personnel.nom[n] = (char) _aleatoire ('A', 'Z');
}
personnel.nom[_aleatoire (5, 20)] = 0;
/* Remplissage
du prénom. La fonction _aleatoire
*
est définie plus bas */
for (n = 0; n <
20; n++) {
personnel.prenom[n] = (char) _aleatoire
('a', 'z');
}
personnel.prenom[_aleatoire (5, 20)] =
0;
/* Age et sexe */
personnel.sexe =
_aleatoire (0, 100) % 2 ? 'M' : 'F';
personnel.age =
_aleatoire (18, 70);
/* Création d'un
enregistrement */
enreg = donnee_nouveau (donnee);
/* Remplissage des champs */
donnee_change (enreg,
"numéro", & i);
donnee_change (enreg,
"nom", personnel.nom);
donnee_change (enreg,
"prénom", personnel.prenom);
donnee_change
(enreg, "sexe", & personnel.sexe);
donnee_change (enreg, "age", & personnel.age);
/* Relâchement de l'enregistrement */
donnee_relache (enreg);
}
/* Affichage des personnes. La
fonction
* _affiche_personnel est
définie plus bas. */
donnee_tous
(donnee,
"numéro",
_affiche_personnel_proc,
0);
/* Fermeture de la base */
donnee_ferme (donnee);
/* Ouverture de la base de données */
donnee =
donnee_ouvre ("personnel.dta");
/* Vérification
*/
donnee_tous
(donnee,
"numéro",
_affiche_personnel_proc,
0);
/* Lecture de la personne numéro 1 */
i = 1;
enreg = donnee_lit (donnee, "numéro", (char *) &
i);
assert (enreg);
/* La fonction
_affiche_personnel est
* définie
plus bas */
_affiche_personnel (enreg);
donnee_relache
(enreg);
/* Lecture de la personne numéro 123,
* qui n'existe pas
*/
i = 123;
enreg = donnee_lit
(donnee, "numéro", (char *) & i);
assert (!
enreg);
/* Fermeture de la base */
donnee_ferme
(donnee);
return (0);
}
Ce programme d'exemple construit une table. Pour cela, il initialise la structure de donnée de type Descripteur définie dans donnee.h avec les éléments de la table : un entier réservé, une chaîne de caractères et les champs de la table. Chaque champ est constitué d'un type, d'un nom, d'une longueur lorsque le champ est une chaîne de caractères et d'un booléen indiquant si ce champ doit être indexé.
Puis la table est remplie avec vingt enregistrements initialisés de manière aléatoire. Le programme affiche le contenu de la table en utilisant une fonction de parcourt appelée avec la fonction de rappel _affiche_personnel_proc(), définie plus bas.
Nous refermons la table ; à ce stade, toutes les informations sont conservées dans des fichiers. Nous ouvrons la table avec son nom de fichier, et nous vérifions que son contenu est resté identique.
Ensuite, nous effectuons deux accès directs à des enregistrements avec une clef. Le premier accès doit réussir, et nous affichons l'enregistrement obtenu avec la fonction _affiche_personnel(), définie plus bas, alors que le second accès doit échouer car la valeur de la clef est introuvable.
Maintenant, voici les fonctions statiques qui devront être placées au-dessus de la fonction main. La première fonction retourne en entier aléatoire compris entre une valeur minimale et une valeur maximale :
/*
Cette fonction génère un entier aléatoire entre
une
* valeur minimale et une valeur maximale
*/
static
int _aleatoire (int bas, int haut) {
int
entier = rand ();
int ecart = haut - bas;
assert
(bas <= haut);
return (bas + (entier % ecart));
}
Cette fonction utilise la fonction rand() de la librairie standard. Elle ne présente pas de difficultés. Notez cependant que la série de nombres pseudo-aléatoires peut être initialisée en invoquant la fonction standard srand().
Vient maintenant la fonction d'affichage d'un enregistrement de la table :
/*
Cette fonction affiche une personne en lisant la valeur
* des
champs avec les fonctions de bases de donnée
*/
static
void _affiche_personnel (Enreg enreg) {
printf
("numéro = %d\n",
*
(int *) donnee_valeur (enreg, "numéro"));
printf ("nom = %s\n",
(char *) donnee_valeur (enreg, "nom"));
printf ("prénom = %s\n",
(char *) donnee_valeur (enreg, "prénom"));
printf ("sexe = %c\n",
* (char *) donnee_valeur (enreg, "sexe"));
printf ("age = %d\n\n",
* (int *) donnee_valeur (enreg, "age"));
}
Cette fonction se contente de récupérer la valeur des champs de l'enregistrement qui lui est passé en argument. Enfin, la fonction de rappel pour la fonction de parcourt des enregistrements d'une table :
/*
Fonction de rappel pour les enregistrements de la base
* de
données
*/
static int
_affiche_personnel_proc (void * parametre,
Enreg
enreg) {
_affiche_personnel (enreg);
return
(1);
}
Comme on peu le voir, l'utilisation des tables ne semble pas très compliqué. L'interface qui définie les fonctionnalités vues dans cet exemple est donnée dans la section suivante.
Interface
Comme d'habitude, l'interface est le contrat entre l'utilisateur de la bibliothèque et son réalisateur. Elle définie les fonctionnalités proposées par la réalisation. Cependant, elle seule ne suffit pas, et il aussi nécessaire de fournir une documentation expliquant les détails qui ne peuvent se voir à la seule lecture de l'interface. Dans notre cas, par exemple, la documentation devra préciser que les valeurs de clefs doit être uniques, ce qui est une limitation.
L'interface est donc :
#ifndef
___DONNEE_H
#define ___DONNEE_H
/* Type des
champs */
typedef enum {
CHAMP_DERNIER = 0,
/* Indicateur de fin */
CHAMP_BOOLEEN = 1,
CHAMP_CARACTERE = 2,
CHAMP_ENTIER = 3,
CHAMP_REEL =
4,
CHAMP_CHAINE = 5
} Type;
/* Descripteur d'un
champ d'une table */
typedef struct __Champ {
Type
type; /* Type de champ */
# define
LONGUEUR_NOM 15
char nom[LONGUEUR_NOM]; /*
Son nom */
unsigned longueur; /*
Longueur de la chaîne */
unsigned index;
/* Est-il indéxé ? */
void
* reserve_1; /* Mots réservés */
unsigned reserve_2;
} _Champ, * Champ;
/*
Descripteur d'un table */
typedef struct
__Descripteur {
unsigned reserve_3; /* mot
réservé */
# define LONGUEUR_ENTETE
100 /* Entête du fichier */
char
entete[LONGUEUR_ENTETE];
# define MAX_CHAMPS 50
_Champ champs[MAX_CHAMPS]; /* Champs de la table */
}
_Descripteur, * Descripteur;
/* Types de données
opaques */
typedef struct __Donnee *
Donnee;
typedef struct __Enreg * Enreg;
/*
Fonctions de l'interface */
/* Gestion des tables
*/
Donnee donnee_cree (char *
nom,
Descripteur);
Donnee donnee_ouvre (char *
nom);
int donnee_ferme (Donnee);
Descripteur
donnee_descripteur (Donnee);
/* Gestion des
enregistrements */
Enreg donnee_nouveau
(Donnee);
Enreg donnee_lit
(Donnee,
char
* index,
char
* valeur);
int donnee_supprime
(Donnee,
char
* index,
char
* valeur);
int donnee_relache (Enreg);
void
donnee_tous (Donnee,
char
* index,
int
(* proc) (void *
param,
Enreg),
void
* param);
/* Gestion des champs */
void *
donnee_valeur (Enreg,
char
* champ);
int donnee_change
(Enreg,
char
* champ,
void * valeur);
#endif /* ___DONNEE_H */
Les premières fonctions permettent de créer, d'ouvrir et de fermer une table. La fonction suivante retourne le descripteur d'une table existante.
Les quatre fonctions qui suivent sont relatives aux enregistrements. Elles permettent respectivement de créer un enregistrement, d'obtenir un enregistrement en spécifiant la valeur d'une clef, de supprimer un enregistrement étant donnée sa valeur clef, de relâcher une enregistrement et enfin de parcourir tous les enregistrements d'une table. Tant qu'un enregistrement est manipulé, il est ``tenu'' par le système, c'est à dire que la valeur de l'un des ses champs est susceptible d'être modifiée. Le système ne peut donc en aucun cas remiser cet enregistrement sur le disque. Dès qu'il est relâché, l'enregistrement peut, en cas de saturation de la mémoire, être supprimer de la mémoire. Un prochain accès à cet enregistrement provoquera donc une lecture du disque.
Les deux dernières fonctions permettent d'accéder aux valeurs des champs d'un enregistrement, étant donné leur nom.
La principale limitation que nous voyons apparaître est l'impossibilité de gérer des enregistrements ayant des valeurs identiques de clefs. Cette limitation est en fait due à une limitation de notre réalisation des tables de hachage. Les lecteurs courageux pourront modifier la bibliothèque des tables de hachage pour permettre une telle gestion.
Maintenant que l'interface est définie, commençons la réalisation. Nous ne pourrons pas tout voir ce mois-ci, aussi, cette description sera poursuivie le mois prochain.
Réalisation
Le fichier des données est organisé de la manière suivante : le descripteur est écrit en premier, puis suivent les enregistrements. Le premier entier du descripteur, reserve_3 contient l'index dans le fichier du premier enregistrement libre. De cette manière, une liste chaînée d'enregistrement libres est constitué au fur et à mesure de leur suppression :
+---------------------------+
| |
| DESCRIPTEUR |--
| | |
+---------------------------+ |
| ENREGISTREMENT | |
| | |
+---------------------------+ |
|****ENREGISTREMENT
LIBRE***|<-
|***************************|--
+---------------------------+ |
| | |
| | |
+---------------------------+ |
|***************************|<-
|***************************|--
+---------------------------+ |
|***************************|<-
|***************************|
+---------------------------+
| |
| |
+---------------------------+
La structure de donnée des tables doit permettre un accès rapide aux champs de la table représentés par un pointeur vers une zone du descripteur, étant donnée le nom du champ. On aura donc une table de hachage dont les identificateurs seront les noms de champs et les données, les pointeurs de type Champ.
De plus, nous aurons en permanence un certains nombre d'enregistrements chargés en mémoire. Les enregistrements sont représentés par un pointeur sur une structure de donnée de type Enreg ; ils sont identifiés par leur position dans le fichier de donnée. On aura donc aussi une table de hachage dont les identificateurs seront des positions dans le fichier de donnée et les données des pointeurs de type Enreg.
Les indexes permettent d'accéder aux enregistrements avec une valeur de clef. Ce sont donc des tables de hachage dont les identificateurs sont des clefs et les données, des positions d'enregistrements, c'est à dire des entiers. On aurait pu placer dans les indexes des pointeurs de type Enreg, mais cela oblige à garder en permanence la totalité des enregistrements en mémoire. En plaçant la valeur des déplacements des enregistrements, il devient possible de ne conserver en mémoire qu'un petit nombre d'enregistrements.
Notez que pour placer dans les tables de hachage des identificateurs qui ne sont pas des chaînes de caractères, nous avons apporté un certain nombre de modifications à la réalisation présentée les mois précédents dans ces colonnes. Ces modifications sont disponibles sur le WEB.
Pour démarrer, nous trouvons tout en haut du fichier de réalisation les traditionnelles déclarations et inclusions :
#define
___DONNEE_C
#include <assert.h>
#include
<fcntl.h>
#include <stdio.h>
#include
<stdlib.h>
#include <string.h>
#include
<sys/stat.h>
#include <sys/types.h>
#include
<time.h>
#include <unistd.h>
#include
<donnee.h>
#include <hash.h>
/*
Traduction des noms de champs réservés de
* manière
plus explicite
*/
#define hash
reserve_1
#define deplacement reserve_2
#define
libre reserve_3
Une petite astuce : dans le fichier publique donnee.h, nous avons nommé des champs de certaines structures reserve_x car nous ne souhaitions pas que l'utilisateur final sache à quoi ces champs correspondent pour que le les utilise pas. Cependant, maintenant que nous allons les utiliser nous-mêmes, nous aimerions bien leur donner un nom plus explicite. Laissons au pré-processeur faire la conversion pour nous : partout où ces noms apparaîtront, ils seront remplacés. Attention tout de même, les noms réels restent, et ce sont ces noms qu'un débogueur affichera.
La structure privée des tables est :
/*
Table */
typedef struct __Donnee {
char
* nom; /* Nom du fichier */
unsigned
taille; /* Taille des enregistrements */
int
id; /* Identificateur du fichier */
Hash
champs; /* Champs de la base */
Hash
enregs; /* Enregistrement de la base */
_Descripteur
descripteur; /* Descripteur de la base */
} _Donnee;
Nous retrouvons le nom du fichier de donnée, la taille des enregistrements (qui est constante, c'est une limitation de la réalisation), l'identificateur du fichier de données, la table de hachage permettant d'obtenir un pointeur sur un champ moyennant son nom, la table de hachage permettant d'obtenir un pointeur sur un enregistrement moyennant sa position dans le fichier des données et le descripteur du fichier. Les pointeurs vers les champs pointent en réalité vers les champs du descripteur.
Les enregistrements sont, de manière interne, des structures de données dont voici la définition :
/*
Enregistrement */
typedef struct __Enreg {
Donnee
donnee; /* Base associée */
unsigned
deplacement; /* Déplacement dans le fichier */
char * tampon; /* Tampon en mémoire */
unsigned creation : 1; /* Indicateur de création
*/
unsigned modifie : 1; /* Indicateur de
modification */
unsigned relache : 1; /*
Indicateur de relâchement */
} _Enreg;
On y trouve un pointeur vers la table à qui appartient l'enregistrement, le déplacement dans le fichier de données, la zone de mémoire tampon contenant un copie de l'enregistrement, l'indicateur de création d'enregistrement, de modification et de relâchement. On notera que les indicateurs ne font qu'un bit, ce qui permet d'économiser la mémoire, car à eux trois, ils n'occupent que trois bits.
La fonction de création d'une table est la suivante :
Donnee
donnee_cree (char * nom,
Descripteur
descripteur) {
int i, id;
Donnee donnee = 0;
/*
Création du fichier */
id = open (nom, O_RDWR
| O_CREAT);
if (id == -1) goto Erreur;
/*
Allocation de la structure, avec
*
initialisation à zéro */
donnee = (Donnee)
calloc (1, sizeof (_Donnee));
if (! donnee)
goto Erreur;
/* Ecriture du descripteur
*/
write (id, descripteur, sizeof
(_Descripteur));
donnee->nom = strdup (nom);
donnee->id = id;
/* Table de hachage
des enregistrements */
donnee->enregs = hash_cree (200, -
sizeof (unsigned));
if (! donnee->enregs) goto
Erreur;
/* Table de hachage des noms de champs
*/
donnee->champs = hash_cree (20, LONGUEUR_NOM);
if
(! donnee->champs) goto Erreur;
/*
Recopie du descripteur */
memcpy (&
donnee->descripteur,
descripteur,
sizeof (_Descripteur));
/*
Initialisation des champs et création des indexes */
for (i = 0;
donnee->descripteur.champs[i].type
!= CHAMP_DERNIER
&&
i < MAX_CHAMPS;
i++) {
Champ champ =
donnee->descripteur.champs + i;
/*
Vérification de l'unicité des noms de champs */
if (hash_donne (donnee->champs,
champ->nom,
0,
0) != HASH_INTROUVABLE) {
fprintf
(stderr,
"Erreur: champ %s déjà existant\n",
champ->nom);
goto Erreur;
}
/* Les
chaînes de caractères doivent avoir
*
une longueur */
if (champ->type == CHAMP_CHAINE)
{
if (! champ->longueur) {
fprintf
(stderr,
"Erreur: longueur de la chaîne non
"
"spécifiée
pour %s\n",
champ->nom);
goto
Erreur;
}
}
/* Création
des indexes */
if (champ->index) {
champ->hash = hash_cree (200,
champ->type
== CHAMP_CHAINE
? champ->longueur
: - _taille (champ));
if (! champ->hash) goto
Erreur;
}
/* Ajout du champs
dans la table des champs */
hash_ajoute
(donnee->champs,
champ->nom,
& champ,
sizeof (Champ));
/* Calcul
de la taille et du déplacement des
* champs.
Ces fonctions seront définies la
*
prochaine fois */
champ->deplacement = i
?
_deplacement (champ - 1)
: 0;
donnee->taille += _taille (champ);
}
/* Il
doit y avoir au moins un champ */
if (! i) {
fprintf (stderr,
"Erreur:
aucun champ pour cette table\n");
goto Erreur;
}
/* C'est ok */
return
(donnee);
Erreur:
/* En cas d'erreur,
défaire tout ce qui a été fait */
if
(donnee) {
if (donnee->nom) free
(donnee->nom);
for (i = 0; i < MAX_CHAMPS; i++)
{
if (donnee->descripteur.champs[i].hash)
{
hash_detruit
((Hash)
donnee->
descripteur.champs[i].hash);
}
}
if (donnee->champs) hash_detruit
(donnee->champs);
if (donnee->enregs)
hash_detruit (donnee->enregs);
free (donnee);
}
if (id != -1) close (id);
return (0);
}
La fonction de création commence par créer un fichier de donnée vide. Puis elle alloue la structure de donnée avec la fonction calloc pour que la zone allouée soit initialisée à zéro. Certains champs de la structure sont initialisés et les tables de hachage locales sont créées. Pour l'ensemble des champs, on effectue ensuite des vérifications d'intégrité, et on crée les indexes lorsque cela est nécessaire. Les champs de la tabls sont progressivement ajoutés dans la table des champs.
La fonction d'ouverture est similaire, mais plus simple car les vérifications ont déjà été effectuées par la fonction de création :
Donnee
donnee_ouvre (char * nom) {
int i, id;
Donnee donnee = 0;
/* Ouverture du fichier des
données */
id = open (nom, O_RDWR);
if
(id == -1) goto Erreur;
/* Allocation
de la structure */
donnee = (Donnee) calloc (1,
sizeof (_Donnee));
if (! donnee) goto
Erreur;
/* Initialisation */
donnee->nom = strdup (nom);
donnee->id =
id;
/* Création de la table des
enregistrements */
donnee->enregs = hash_cree (200, -
sizeof (unsigned));
if (! donnee->enregs)
goto Erreur;
/* Création de la
table des champs */
donnee->champs = hash_cree (20,
LONGUEUR_NOM);
if (! donnee->champs) goto
Erreur;
/* Lecture du descripteur */
read (id, & donnee->descripteur, sizeof
(_Descripteur));
/* Ouverture des indexes et
ajout des champs */
for (i = 0;
donnee->descripteur.champs[i].type != CHAMP_DERNIER
&& i < MAX_CHAMPS;
i++) {
Champ champ =
donnee->descripteur.champs + i;
if
(champ->index) {
char nom_index[100];
/*
Fabrication du nom du fichier index. La fonction
*
sera définie le mois prochain */
_fichier_index
(donnee, champ, nom_index);
/*
Ouverture du fichier index */
champ->hash =
hash_charge (nom_index);
if (! champ->hash) goto
Erreur;
}
/* Ajout du champ dans
la table des champs */
hash_ajoute
(donnee->champs,
champ->nom,
&
champ,
sizeof
(Champ));
/* Initialisation du
champ */
champ->deplacement = i ? _deplacement (champ -
1) : 0;
donnee->taille += _taille (champ);
}
/*
C'est ok*/
return (donnee);
Erreur:
/*
C'est ko */
if (donnee) {
if
(donnee->nom) free (donnee->nom);
for (i =
0; i < MAX_CHAMPS; i++) {
if
(donnee->descripteur.champs[i].hash) {
hash_detruit
((Hash)
donnee->
descripteur.champs[i].hash);
}
}
if (donnee->champs) hash_detruit
(donnee->champs);
if (donnee->enregs)
hash_detruit (donnee->enregs);
free (donnee);
}
if (id != -1) close (id);
return (0);
}
Cette fonction ne présente aucune difficultés.
Le mois prochain, nous continuerons cette réalisation ...
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