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

Erratum

Dans le paragraphe ``les indiens sont là'' d'un précédent numéro, les processeurs Intel sont dits en mode big-endian, alors que c'est le contraire, ils sont en mode little-endian.

Je vous propose le code de Frederic Raynal qui écrit aussi dans ces colonnes pour détecter le mode de fonctionnement du processeur :

/* endian.c */
#include <stdio.h>

void main(int argc, char **argv) {

union {
int entier;
char octets[4]
} nb;
unsigned char o0, o1, o2, o3;

nb.entier = atoi(argv[1]);
printf("int : %x (%d)\n", nb.entier, nb.entier);
printf("octets : %.2x %.2x %.2x %.2x\n",
nb.octets[0],
nb.octets[1],
nb.octets[2],
nb.octets[3]);

o0 = (nb.entier >> 24) & 0xff; //MSB
o1 = (nb.entier >> 16) & 0xff;
o2 = (nb.entier >> 8) & 0xff;
o3 = (nb.entier ) & 0xff; //LSB
printf("msb -> lsb : %.2x %.2x %.2x %.2x\n",
o0, o1, o2, o3);
}

Ainsi que ces commentaires :

Ceci, outre les warnings de compilation provoque l'affichage suivant sur mon Pentium 350 :

>>uname -am ; ./a.out 65538
Linux xxx.inria.fr 2.2.18ow1 #3 SMP Mon Jan 8 13:44:33 CET 2001 i686
unknownint : 10002 (65538)
octets : 02 00 01 00
msb -> lsb : 00 01 00 02

Et sur une Sun :

>>uname -am; ./endian-sun 65538
SunOS continuum 4.1.4 2 sun4m
int : 10002 (65538)
octets : 00 01 00 02
msb -> lsb : 00 01 00 02

2 constatations donc :

 les x86 sont en little endian (i.e. les bytes de poids faibles sont à la fin, et la lecture se fait de droite à gauche) alors que les Sparcs sont en big endian (i.e. les bytes de poids faibles sont à droite et la lecture se fait de gauche à droite),

 les opérateurs de décalage sont indépendants des architectures (heureusement d'ailleurs ;-)

Je remercie aussi Serageldine Abdalla et Christiane Dridi pour leur commentaires sur le sujets.

Description

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

Interface

Rappelons l'interface que nous souhaitons réaliser. En rouge sont les fonctions présentées dans ces lignes :

#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);

/* 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 */

Table

On rappelle que la réalisation propose des indexes ``tout en mémoire'' basés sur des tables de hachage. Dans la réalité, il faudrait réaliser des indexes paginés ou seule une partie de l'index reste en mémoire.

La fonction de fermeture doit donc sauver tous les indexes associés à la table et libérer les zones de mémoire allouées :

int donnee_ferme (Donnee donnee) {
int i;

/* Ecriture des enregistrements modifiés et
* libération de tous les enregistrements. */
hash_tous (donnee->enregs, 0, _free_enreg);

/* Sauvegarde des indexes ... */
for (i = 0;
donnee->descripteur.champs[i].type !=
CHAMP_DERNIER && i < MAX_CHAMPS;
i++) {
if (donnee->descripteur.champs[i].index) {
char nom_index[100];

/* Création du nom de l'index */
_fichier_index (donnee,
donnee->descripteur.champs + i,
nom_index);
/* Sauvegarde de l'index */
hash_sauve ((Hash) donnee->descripteur.champs[i].hash,
nom_index);
/* Destruction de l'index en mémoire */
hash_detruit ((Hash) donnee->descripteur.champs[i].hash);
}
}
/* Destruction de tables de hachage internes. */
hash_detruit (donnee->champs);
hash_detruit (donnee->enregs);

/* Fermeture du fichier */
close (donnee->id);
free (donnee->nom);
free (donnee);
return (1);
}

La fonction _free_enreg écrit dans le fichier des données l'enregistrement, s'il a été modifié, et libère les ressources mémoires qu'il utilise :

/* Libère un enregistrement */
static int _free_enreg (void * parametre,
char * identificateur,
void * donnee,
int taille_donnee) {
Enreg enreg = * (Enreg *) donnee;

if (enreg->modifie) {
_ecrit_enreg (enreg);
}
free (enreg->tampon);
free (enreg);
return (1);
}

La fonction _ecrit_enreg écrit dans le fichier des données l'enregistrement. Si l'enregistrement est nouveau (lors d'une création), un nouvel emplacement est recherché ; sinon, on utilise l'emplacement initial :

/* Ecrit un enregistrement sur disque */
static int _ecrit_enreg (Enreg enreg) {
/* Emplacement nouveau ? */
if (! enreg->deplacement) {
/* Recherche d'un emplacement libre dans la
liste des emplacements libres. */
 enreg->deplacement = _libre (enreg->donnee);
/* S'il n'y a pas d'emplacement libre, l'enregistrement
est placé à la fin du fichier. */
 if (! enreg->deplacement) {
lseek (enreg->donnee->id, 0, SEEK_END);
enreg->deplacement = lseek (enreg->donnee->id,
0,
SEEK_END);
}
/* Ajout dans la table des enregistremenbts. */
 hash_ajoute (enreg->donnee->enregs,
(char *) & enreg->deplacement,
& enreg,
sizeof (enreg));
}
/* On se place sur l'enregistrement. */
 lseek (enreg->donnee->id,
enreg->deplacement,
SEEK_SET);

/* On l'écrit. */
 write (enreg->donnee->id,
enreg->tampon,
enreg->donnee->taille);

/* Maintenant, l'enregistrement est synchronisé
avec le disque. */
 enreg->modifie = 0;

 return (1);
}

La fonction suivante retourne le déplacement du premier enregistrement libre de la table. On rappelle que lorsqu'un enregistrement est supprimé, il n'est pas effectivement supprimé du fichier des données, mais simplement inséré dans la liste des enregistrements libres. De cette manière, l'emplacement qu'il occupe pourra être réutilisé :

/* Retourne le déplacement du premier enregistrement
* libre de la base
*/
static unsigned _libre (Donnee donnee) {
 unsigned libre = donnee->descripteur.libre;

if (libre) {
lseek (donnee->id,
libre,
SEEK_SET);
read (donnee->id,
& donnee->descripteur.libre,
sizeof (unsigned));
lseek (donnee->id,
0,
SEEK_SET);
write (donnee->id,
& donnee->descripteur.libre,
sizeof (unsigned));
}
return (libre);
}

Lorsqu'un trop grand nombre d'enregistrements sont libérés sans être réutilisés, une réorganisation du fichier s'impose sinon le fichier grossit inutilement. Cette réorganisation passe en général par la suppression des indexes, la réécriture du fichier des données sans tenir compte des enregistrements libres, et enfin par la réindexation du fichier des données. Cette opération est coûteuse en temps, aussi elle n'est pas automatique.

Enfin, la fonction _fichier_index retourne le nom du fichier d'index associé à un champ :

/* Fabrique le nom du fichier d'index associé
* à un index
*/
static char * _fichier_index (Donnee donnee,
Champ champ,
char * tampon) {
char * str;

/* Recopie du nom dans le tampon */
 strcpy (tampon, donnee->nom);

/* recherche du point qui sépare l'extension */
str = strchr (tampon, '.');

/* Par défaut, aller à la fin du nom */
if (! str) str = tampon + strlen (tampon);

/* ajout du nom de champ et de l'extension */
sprintf (str, "-%s.idx", champ->nom);

return (tampon);
}

Enregistrement

La fonction donnee_nouveau retourne un enregistrement vierge :

/* Création d'un enregistrement */
Enreg donnee_nouveau (Donnee donnee) {
/* Allocation de l'enregistrement */
 Enreg enreg = (Enreg) malloc (sizeof (_Enreg));

if (! enreg) return (0);

/* Allocation de tampon associé à l'enregistrement */
 enreg->tampon = (char *) calloc (1, donnee->taille);
if (! enreg->tampon) (
free (enreg);
return (0);
}
/* Initialisation */
 enreg->donnee = donnee;
enreg->deplacement = 0;
enreg->creation = 1;
enreg->modifie = 0;
enreg->relache = 0;

/* Ecriture de l'enregistrement */
 _ecrit_enreg (enreg);

return (enreg);
}

Le nouvel enregistrement est associé à un déplacement dans le fichier des données par l'utilisation de la fonction _ecrit_enreg.

La fonction suivante retourne un enregistrement étant donné un index identifié par son nom, et une valeur de l'index :

/* Lecture d'un enregistrement */
Enreg donnee_lit (Donnee donnee,
char * index,
char * valeur) {
Champ champ;
unsigned deplacement;

  /* Récupération du champs correspondant au nom
   * index */
 if (hash_donne (donnee->champs,
index,
& champ,
0) != HASH_OK) {
fprintf (stderr,
"Erreur: champ %s introuvable\n",
index);
return (0);
}
  /* Vérification que c'est bien un index */
if (! champ->index) {
fprintf (stderr,
"Erreur: le champ %s n'est pas un index\n",
index);
return (0);
}
  /* Récupération du déplacement de l'enregistrement
   * étant données la valeur d'index */
 if (hash_donne (champ->hash,
valeur,
& deplacement,
0) != HASH_OK) {
fprintf (stderr,
"Erreur: pas d'enregistrement"
" avec cette valeur\n");
return (0);
}
  /* Lecture de l'enregistrement */
return (_lit_enreg (donnee, deplacement));
}

La fonction _lit_renreg retourne un enregistrement étant donné son déplacement dans le fichier. L'enregistrement est soit retrouvé dans la table des enregistrements, soit lu à partir du fichier des données :

/* Lit un enregistrement à partir du disque
* ou de la mémoire.
*/
static Enreg _lit_enreg (Donnee   donnee,
                         unsigned deplacement) {
Enreg enreg;

  /* L'enregistrement est-il déjà chargé
  * en mémoire ? */
 if (hash_donne (donnee->enregs,
(char *) & deplacement,
& enreg,
0)
!= HASH_OK) {
/* Allocation de l'enregistrement et du tampon */
enreg = (Enreg) malloc (sizeof (_Enreg));
if (! enreg) return (0);
enreg->tampon = (char *)
                        calloc (1, donnee->taille);
if (! enreg->tampon) {
free (enreg);
return (0);
}
/* Initialisation */
enreg->donnee = donnee;
enreg->deplacement = deplacement;
enreg->modifie = 0;
enreg->relache = 0;

/* Positionnement dans le fichier et lecture */
lseek (donnee->id, deplacement, SEEK_SET);
read (donnee->id, enreg->tampon, donnee->taille);

/* Ajout dans la table des enregistrements */
 hash_ajoute (donnee->enregs,
(char *) & deplacement,
& enreg,
sizeof (enreg));
}
enreg->relache = 0;
return (enreg);
}

Le mois prochaine, nous terminerons cette présentation avec les autres fonction de manipulation des enregistrements et les fonction de manipulation des champs.

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