Changes between Version 6 and Version 7 of CaoCourseTme2

Timestamp:

Feb 15, 2007, 3:12:54 PM (18 years ago)

Author:

franck

Comment:

--

CaoCourseTme2

@@ -73 +73 @@
  1. Que fait la regle indent ? quelle est la signification des flags utilisés par le programme indent ?
 
+'''Makefile'''
 {{{
   1 # Definition des commandes 
@@ -120 +121 @@
  *  Pourquoi inclure {{{stdio.h}}} ici ?
 
+'''main.c'''
 {{{
   1 #ifndef _MAIN_H_
@@ -151 +153 @@
  1. Que faut-il faire pour transformer ce programme en filtre ?
 
+'''main.c'''
 {{{
   1 #include <stdlib.h>
@@ -233 +236 @@
 }}}
 
+== Les fonctions de bases de la tables de hachage ==
+
+'''hte.h'''
+{{{
+  1 #ifndef _HTE_H_
+  2 #define _HTE_H_
+  3 
+  4 #include <stdlib.h>
+  5 
+  6 
+  7 /*
+  8  * Les deux structures ci-dessous ne sont pas définies ici
+  9  * elles seront redéfinies dans chaque fichier
+ 10  */
+ 11 typedef struct hte_item_s hte_item_t;
+ 12 typedef struct hte_data_s hte_data_t;
+ 13 
+ 14 
+ 15 /*
+ 16  * structure définissant la table de hachage
+ 17  * On y trouve le nombre de liste de liste et
+ 18  * un pointeur vers le tableau de liste
+ 19  */
+ 20 typedef struct hte_root_s
+ 21 {
+ 22     size_t NB_LIST;             /* nombre de liste d'ITEM du dictionnaire */
+ 23     hte_item_t **LIST;          /* pointeur sur un tableau de liste d'ITEM */
+ 24 } hte_root_t;
+ 25 
+ 26 
+ 27 /*
+ 28  * Calcul de l'index de hachage de Donald Knuth
+ 29  * Elle produit un nombre entier à partir d'une chaine de caractères.
+ 30  */
+ 31 extern unsigned hte_hash (char *key);
+ 32 
+ 33 
+ 34 /*
+ 35  * hte_create fabrique une table de hachage vide
+ 36  * parametres:
+ 37  *      nb_item = nombre d'item maximum prévu dans la table de hachage
+ 38  */
+ 39 extern hte_root_t *hte_create (size_t nb_item);
+ 40 
+ 41 
+ 42 /* ------------------------------------------------------------------------ */
+ 43 
+ 44 
+ 45 /*
+ 46  * hte_add ajoute l'item (key,data)
+ 47  * parametres: 
+ 48  *      root = pointeur sur la table de hachage
+ 49  *      key  = pointeur sur une chaine de caractères (la clé)
+ 50  *      data = donnée associée à key
+ 51  * comportement:
+ 52  *      La clé key passée en parametre est comparée à celles présentes dans
+ 53  *      la table. Si la clé n'est pas trouvée alors un nouvel item est créé
+ 54  *      avec le couple (key,data). La clé key est en fait duppliquée.
+ 55  *      Si la clé est trouvée, le champ DATA de l'item présent dans la
+ 56  *      table est remplacé par le paramètre data de la fonction.
+ 57  * retour:
+ 58  *      Si l'item n'a pu etre créé faute d'espace, on sort du programme.
+ 59  */
+ 60 extern void hte_add (hte_root_t * root, char *key, hte_data_t * data);
+ 61 
+ 62 
+ 63 /*
+ 64  * hte_get recherche item, et en cas d'absence l'ajoute
+ 65  * parametres: 
+ 66  *      root = pointeur pour la table de hachage
+ 67  *      key  = pointeur sur une chaine de caractères (la clé)
+ 68  * comportement:
+ 69  *      La clé passée en parametre est comparé a celles présentes dans la 
+ 70  *      table de hachage. 
+ 71  * retour:
+ 72  *      Si la clé est trouvée alors la fonction retourne le champ data
+ 73  *      sinon la fonction rend NULL.
+ 74  */
+ 75 extern hte_data_t *hte_get (hte_root_t * root, char *key);
+ 76 
+ 77 
+ 78 /* ------------------------------------------------------------------------ */
+ 79 
+ 80 
+ 81 /*
+ 82  * namealloc permet de garantir l'unicité des chaines de caractères
+ 83  * parametres:
+ 84  *      name = chaine de caractères
+ 85  * comportement:
+ 86  *      name est recherché dans la table, 
+ 87  *      s'il est absent on ajoute une copie de name dans la table
+ 88  * retour:
+ 89  *      un pointeur sur la copie de la table
+ 90  */
+ 91 char *namealloc (char *name);
+ 92 
+ 93 /* nombre maximum de noms dans la table */
+ 94 #define MAX_NAMEALLOC 1000
+ 95 
+ 96 
+ 97 /* ------------------------------------------------------------------------ */
+ 98 
+ 99 /*
+100  * dejavu permet de savoir si un nom a déjà été vu
+101  * parametres:
+102  *      name = chaine de caractères
+103  * comportement:
+104  *      name est recherché dans la table, 
+105  *      s'il est absent on ajoute une copie de name dans la table
+106  * retour:
+107  *      rend 1 s'il était déjà présent sinon 0
+108  */
+109 unsigned dejavu (char *name);
+110 
+111 /* nombre maximum de noms dans la table */
+112 #define MAX_DEJAVU 1000
+113 
+114 #endif
+}}}
+
+'''hte.c'''
+{{{
+  1 #include <stdio.h>
+  2 #include <string.h>
+  3 #include <stdlib.h>
+  4 #include "hte.h"
+  5 
+  6 /*
+  7  * Calcul de l'index de hachage de Donald Knuth
+  8  * Elle produit un nombre entier à partir d'une chaine de caractères.
+  9  */
+ 10 unsigned hte_hash (char *key)
+ 11 {
+ 12     char *c = key;
+ 13     unsigned h;
+ 14     for (h = 0; *c; c++)
+ 15     {
+ 16         h += (h ^ (h >> 1)) + 314159 * (unsigned char) *c;
+ 17         while (h >= 516595003)
+ 18             h -= 516595003;
+ 19     }
+ 20     return h;
+ 21 }
+ 22 
+ 23 
+ 24 /*
+ 25  * Création d'un dictionnaire vide 
+ 26  */
+ 27 hte_root_t *hte_create (size_t nb_item)
+ 28 {
+ 29     hte_root_t *root;
+ 30     unsigned i, nb_list;
+ 31     static unsigned primes[] = { /*suite croissante de nombres premiers */
+ 32         101, 149, 223, 347, 499, 727, 1163, 1697, 2503, 3989, 5839, 8543,
+ 33         12503, 20143, 29483, 43151, 63179, 92503, 101747, 148961, 218107,
+ 34         319313, 514243, 752891, 1212551, 1613873, 2599153, 3805463,
+ 35         5571523, 8157241, 11943011, -1
+ 36     };
+ 37 
+ 38     /* détermination de la taille réelle du dictionnaire */
+ 39     for (i = 0; primes[i] < nb_item; i++);
+ 40     nb_list = primes[i];
+ 41     if (nb_item != -1)
+ 42     {
+ 43         /* allocation et initialisation du dictionnaire */
+ 44         if ((root = malloc (sizeof (hte_root_t))))
+ 45         {
+ 46             root->NB_LIST = nb_list;
+ 47             if ((root->LIST = calloc (nb_list, sizeof (hte_item_t *))))
+ 48                 return root;
+ 49         }
+ 50     }
+ 51     fprintf (stderr, "hte_create: not enough memory\n");
+ 52     exit (1);
+ 53 }
+}}}