Le langage C

Base de donnée: (suite)



Par :

Guilhem de Wailly (gdw@erian-concept.com)



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 terminer le mini moteur base de donnée utilisant les tables de hachages.

Description

Le mois dernier, nous avons continué la réalisation d'un petit moteur base de données sans plus de prétentions que d'utiliser les tables de hachages et de montre ce que peut être la complexité des vrais moteurs. Nous terminons cette fois-ci cette présentation. Le code précédent et le code présenté ici sont rassemblés à l'URL http://www.erian-concept.com/pub/donnee.tgz.

Enregistrement

Ecriture

L'écriture des enregistrements intervient lorsqu'ils sont ``relâchés``, c'est à dire lorsque l'on a fini de les modifier. Ceci est effectué par la fonction suivante :

int donnee_relache (Enreg enreg) {
if (enreg->modifie) {
/* Ecriture */
 _ecrit_enreg (enreg);
/* Réindextation */
 _reindexe (enreg->donnee, enreg);
}
/* Remise à zéro des indicateurs */
 enreg->modifie = 0;
enreg->creation = 0;
enreg->relache = 1;
return (1);
}

On observe que si l'enregistrement n'a pas été modifié, aucune écriture n'intervient. Lorsque l'enregistrement est modifié, il est supprimé des indexes (voir article précédent) : nous écrivons donc les données, et nous réindexons l'enregistrement dans les différents indexes.

L'écriture est effectuée par la fonction :

/* Ecrit un enregistrement sur disque */
static int _ecrit_enreg (Enreg enreg) {
if (! enreg->deplacement) {
/* Enregistrement nouvellement créé */
/* Y-a-t-il un espace libre ? */
 enreg->deplacement = _libre (enreg->donnee);
if (! enreg->deplacement) {
/* Sinon, placer l'enregistrement à la fin */
 lseek (enreg->donnee->id, 0, SEEK_END);
enreg->deplacement = lseek (enreg->donnee->id, 0, SEEK_END);
}
hash_ajoute (enreg->donnee->enregs,
(char *) & enreg->deplacement,
& enreg,
sizeof (enreg));
}
/* Ecriture dans le fichier */
 lseek (enreg->donnee->id, enreg->deplacement, SEEK_SET);
write (enreg->donnee->id, enreg->tampon, enreg->donnee->taille);
enreg->modifie = 0;
return (1);
}

Si l'enregistrement n'a pas de position dans le fichier (il vient dans d'être créé), nous essayons de récupérer un emplacement libre. Si nous n'en trouvons pas, nous positionnons l'enregistrement à la fin du fichier. Nous ajoutons alors l'enregistrement dans la tables de hachage des enregistrements qui permettra de le retrouver rapidement, connaissant son déplacement.

Lorsque l'enregistrement possède un emplacement dans le fichier, il suffit d'y écrire ses données.

La fonction de réindexation permet de replacer dans tous les indexes la clef concernée associée au déplacement de l'enregistrement :

/* Réindexe un enregistrement dans tous les indexes */
static int _reindexe (Donnee donnee, Enreg enreg) {
int i;

/* Pour tous les descripteurs ...*/
 for (i = 0;
donnee->descripteur.champs[i].type != CHAMP_DERNIER
&& i < MAX_CHAMPS;
i++) {
Champ champ = donnee->descripteur.champs + i;

/* Si c'est un index ...*/
 if (champ->index) {
/* et si la valeur de clef existe déjà ...*/
 if (hash_donne ((Hash) champ->hash,
enreg->tampon + champ->deplacement,
0,
0) != HASH_INTROUVABLE) {
  /* il y a erreur !*/
 fprintf (stderr,
"Erreur: la clef %d existe déjà\n",
champ->index);
return (0);
}
/* sinon, ajouter la valeur de clef.*/
 hash_ajoute ((Hash) champ->hash,
enreg->tampon + champ->deplacement,
& enreg->deplacement,
sizeof (unsigned));
}
}
return (1);
}

L'indexation des enregistrements par leur clef permet de connaître rapidement leur emplacement connaissant la clef.

Suppression

Nous nous intéressons à la fonction de suppression des enregistrements. Cette fonction doit supprimer toute trace de l'enregistrement, à la fois dans les indexes et dans la mémoire :

int donnee_supprime (Donnee donnee,
char * index,
char * valeur) {
/* Obtention de l'enregistrement */
 Enreg enreg = donnee_lit (donnee, index, valeur);

if (enreg) {
/* Suppression des indexes */
 _deindexe (donnee, enreg);
/* Libération de la mémoire */
 _libere (donnee, enreg->deplacement);
return (1);
}
return (0);
}

Nous avons arbitrairement choisit de le pas vérifier que l'enregistrement est inutilisé avant de le supprimer. La fonction supprime l'enregistrement des indexes et libère la mémoire allouée. La fonction suivante supprime un enregistrement des indexes associés à la table :

/* Supprime un enregistrement des indexes */
static void _deindexe (Donnee donnee, Enreg enreg) {
int i;

/* Pour tous les descripteurs ...*/
 for (i = 0;
donnee->descripteur.champs[i].type != CHAMP_DERNIER
&& i < MAX_CHAMPS;
i++) {
Champ champ = donnee->descripteur.champs + i;

/* si c'est un index ...*/
 if (champ->index) {
/* supprimer la clef de l'index.*/
 hash_enleve ((Hash) champ->hash,
enreg->tampon + champ->deplacement);
}
}
}

Elle parcourt simplement tous les descripteurs indexés ; elle supprime l'entrée de la table de hachage correspondant à l'enregistrement.

La fonction suivante marque un enresitrement comme étant réutilisable et l'intègre dans la liste des enregistrements libres :

/* Libère l'espace disque occupé par un
* enregistrement en le remplaçant dans une liste
* chaînée.
*/
static void _libere (Donnee donnee, unsigned deplacement) {
lseek (donnee->id, deplacement, SEEK_SET);
write (donnee->id, & donnee->descripteur.libre, sizeof (unsigned));
donnee->descripteur.libre = deplacement;
lseek (donnee->id, 0, SEEK_SET);
write (donnee->id, & donnee->descripteur.libre, sizeof (unsigned));
}

La fonction se positionne au début de l'enregistrement dans le fichier des données et écrit le déplacement du premier bloc libre sur le disque, puis elle modifie l'entête du fichier de façon à ce que le premier bloc libre soit celui que l'on est en train de supprimer. Nous rappelons que les effacements sur le disque sont logiques, c'est à dire que les données sont conservées, mais simplement placées dans une liste de blocs réutilisables.

Parcours

La fonction de parcours permet d'appliquer une fonction de rappel à tous les enregistrements de la table. La fonction de rappel utilise la structure ci-dessous comme paramètre :

/* Structure utilisée dans le parcours des
* tables de hachages
*/
typedef struct __HashTous {
Donnee donnee; /* Table parcourue */
void * param; /* Paramètre de la fonction */
int (* proc) (void *, /* Fonction de rappel */
Enreg);
} _HashTous, * HashTous;

La fonction de parcours est définie par :

void donnee_tous (Donnee donnee,
char * index,
int (* proc) (void * param,
Enreg),
void * param) {

_HashTous ht;
Champ champ;

/* Vérifier que le champ existe ...*/
 if (hash_donne (donnee->champs, index, & champ, 0)
!= HASH_OK) {
fprintf (stderr,
"Erreur: champ %s introuvable\n",
index);
return;
}
/* ... et que c'est bien un index.*/
 if (! champ->index) {
fprintf (stderr,
"Erreur: le champ %s n'est pas un index\n",
index);
return;
}
/* Préparer les données du parcours.*/
 ht.donnee = donnee;
ht.param = param;
ht.proc = proc;

/* Parcourir tous les enregistrement indexés. */
 hash_tous ((Hash) champ->hash,
& ht,
_proc_hash_tous);
}

Cette fonction utilise simplement la fonction de parcours des tables de hachage avec la fonction de rappel décrite ci-dessous :

/* Fonction de rappel pour parcourir tous les
* enregistrements d'un index
*/
static int _proc_hash_tous (void * parametre,
char * identificateur,
void * valeur,
int taille_donnee) {
int retour;
Enreg enreg;

/* Récupérer les données du parcours. */
 HashTous ht = (HashTous) parametre;
unsigned deplacement = * (unsigned *) valeur;

/* Lire l'enregistrement */
 enreg = _lit_enreg (ht->donnee, deplacement);

/* Appeler la fonction de rappel. */
 retour = ht->proc (ht->param, enreg);

/* Relâcher l'enregistrement */
 donnee_relache (enreg);

return (retour);
}

La fonction de rappel lit l'enregistrement en cours et invoque la fonction de rappel passée en argument de donnee_tous.

Champ

Les dernières fonctionnalités à examiner permettent d'accéder aux champs des tables afin d'en obtenir les valeurs :

void * donnee_valeur (Enreg enreg, char * index) {
Champ champ;

/* Vérifier que le champ existe bien. */
 if (hash_donne (enreg->donnee->champs,
index,
& champ,
0) != HASH_OK) {
fprintf (stderr,
"Erreur: champs %s introuvable\n",
index);
return (0);
}
/* Retourner l'adresse de la valeur du champ. */
 return ((void *) ( enreg->tampon
+ champ->deplacement));
}

Les valeurs ne sont pas retournées directement. Au lieu de cela, leur adresse est retournée. Cela est potentiellement dangereux si on écrit à cette adresse une donnée plus grande que prévue.

La fonction suivante permet de modifier la valeur d'un champ d'un enregistrement de la table :

int donnee_change (Enreg enreg,
char * index,
void * valeur) {
Champ champ;

/* Vérifier que le champ existe. */
 if (hash_donne (enreg->donnee->champs,
index,
& champ,
0) != HASH_OK) {
fprintf (stderr,
"Erreur: champs %s introuvable\n",
index);
return (0);
}
/* Si l'enregistrement n'est pas encore modifié ...*/
 if (! enreg->modifie) {
/* Et s'il n'est pas nouvellement créé ...*/
 if (! enreg->creation) {
/* le supprimer de tous les indexes ...*/
 _deindexe (enreg->donnee, enreg);
}
/* et le marquer comme étant modifié.*/
 enreg->modifie = 1;
}
/* Copier à l'adresse de la valeur, la nouvelle valeur */
 memcpy (enreg->tampon + champ->deplacement,
valeur,
_taille (champ));
return (1);
}

Conclusion

Voila ce petit moteur de base de donnée terminé. Il est pleinement fonctionnel et assez rapide. Cependant, il devrait subir certaines améliorations pour être réellement utilisable, parmi lesquelles :

ï‚· Mise en place d'index paginés : dans la réalisation actuelle, les indexes sont chargés entièrement en mémoire avant d'être utilisable.

ï‚· Meilleur gestion des indexes : actuellement, les enregistrements sont déindexés dès qu'ils sont modifiés, ce qui est un peu consommateur en temps de calcul.

ï‚· Indexes performants : Les indexes à base de table de hachages sont couramment utilisés car ils sont assez facile à mettre en oeuvre. Cependant, il existe des techniques d'indexation plus performantes garantissant un temps d'accès maximum, comme les b-arbres.

ï‚· Valeurs de clefs multiples : Actuellement, les valeurs de clefs doivent être uniques ; il est nécessaire de permettre à plusieurs enregistrement d'avoir la même valeur de clef.

ï‚· Champs de taille variable : les enregistrements sont de taille fixe, ce qui facilite grandement la programmation ; il serait cependant utile de permettre aux champs ``chaînes de caractères'' d'avoir une taille variable. Cela complique la réalisation mais permet une meilleurs utilisation de l'espace disque.

ï‚· Contraintes d'intégrité : Les contraintes d'intégrités permettent de placer des relations entre les tables imposant certaines contraintes qui garantissent l'intégrité des la base de données.

ï‚· Transactions: Actuellement, si une écriture dans la table est interrompue, par une coupure de courant par exemple, la table n'est plus cohérente. Il est nécessaire de mettre en place des procédures transactionnelles (un peu à la manière des systèmes de fichiers journalisés décrit dans un numéro précédent) qui garantissent la cohérence du système. En effet, une transaction est soit entièrement effectuée, soit abolument pas effectuée car elle est atomique.

Toutes ces fonctionnalités sont mises en oeuvre dans le moteur base de données d'OpenScheme appelé OSD. La prochaine évolution de ce moteur sera de mettre en place une interface SQL. Ce moteur est disponible librement, avec OpenScheme.

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