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