247 | | 1 #ifndef _HTE_H_ |
248 | | 2 #define _HTE_H_ |
249 | | 3 |
250 | | 4 #include <stdlib.h> |
251 | | 5 |
252 | | 6 |
253 | | 7 /* |
254 | | 8 * Les deux structures ci-dessous ne sont pas définies ici |
255 | | 9 * elles seront redéfinies dans chaque fichier |
256 | | 10 */ |
257 | | 11 typedef struct hte_item_s hte_item_t; |
258 | | 12 typedef struct hte_data_s hte_data_t; |
259 | | 13 |
260 | | 14 |
261 | | 15 /* |
262 | | 16 * structure définissant la table de hachage |
263 | | 17 * On y trouve le nombre de liste de liste et |
264 | | 18 * un pointeur vers le tableau de liste |
265 | | 19 */ |
266 | | 20 typedef struct hte_root_s |
267 | | 21 { |
268 | | 22 size_t NB_LIST; /* nombre de liste d'ITEM du dictionnaire */ |
269 | | 23 hte_item_t **LIST; /* pointeur sur un tableau de liste d'ITEM */ |
270 | | 24 } hte_root_t; |
271 | | 25 |
272 | | 26 |
273 | | 27 /* |
274 | | 28 * Calcul de l'index de hachage de Donald Knuth |
275 | | 29 * Elle produit un nombre entier à partir d'une chaine de caractères. |
276 | | 30 */ |
277 | | 31 extern unsigned hte_hash (char *key); |
278 | | 32 |
279 | | 33 |
280 | | 34 /* |
281 | | 35 * hte_create fabrique une table de hachage vide |
282 | | 36 * parametres: |
283 | | 37 * nb_item = nombre d'item maximum prévu dans la table de hachage |
284 | | 38 */ |
285 | | 39 extern hte_root_t *hte_create (size_t nb_item); |
286 | | 40 |
287 | | 41 |
288 | | 42 /* ------------------------------------------------------------------------ */ |
289 | | 43 |
290 | | 44 |
291 | | 45 /* |
292 | | 46 * hte_add ajoute l'item (key,data) |
293 | | 47 * parametres: |
294 | | 48 * root = pointeur sur la table de hachage |
295 | | 49 * key = pointeur sur une chaine de caractères (la clé) |
296 | | 50 * data = donnée associée à key |
297 | | 51 * comportement: |
298 | | 52 * La clé key passée en parametre est comparée à celles présentes dans |
299 | | 53 * la table. Si la clé n'est pas trouvée alors un nouvel item est créé |
300 | | 54 * avec le couple (key,data). La clé key est en fait duppliquée. |
301 | | 55 * Si la clé est trouvée, le champ DATA de l'item présent dans la |
302 | | 56 * table est remplacé par le paramètre data de la fonction. |
303 | | 57 * retour: |
304 | | 58 * Si l'item n'a pu etre créé faute d'espace, on sort du programme. |
305 | | 59 */ |
306 | | 60 extern void hte_add (hte_root_t * root, char *key, hte_data_t * data); |
307 | | 61 |
308 | | 62 |
309 | | 63 /* |
310 | | 64 * hte_get recherche item, et en cas d'absence l'ajoute |
311 | | 65 * parametres: |
312 | | 66 * root = pointeur pour la table de hachage |
313 | | 67 * key = pointeur sur une chaine de caractères (la clé) |
314 | | 68 * comportement: |
315 | | 69 * La clé passée en parametre est comparé a celles présentes dans la |
316 | | 70 * table de hachage. |
317 | | 71 * retour: |
318 | | 72 * Si la clé est trouvée alors la fonction retourne le champ data |
319 | | 73 * sinon la fonction rend NULL. |
320 | | 74 */ |
321 | | 75 extern hte_data_t *hte_get (hte_root_t * root, char *key); |
322 | | 76 |
323 | | 77 |
324 | | 78 /* ------------------------------------------------------------------------ */ |
325 | | 79 |
326 | | 80 |
327 | | 81 /* |
328 | | 82 * namealloc permet de garantir l'unicité des chaines de caractères |
329 | | 83 * parametres: |
330 | | 84 * name = chaine de caractères |
331 | | 85 * comportement: |
332 | | 86 * name est recherché dans la table, |
333 | | 87 * s'il est absent on ajoute une copie de name dans la table |
334 | | 88 * retour: |
335 | | 89 * un pointeur sur la copie de la table |
336 | | 90 */ |
337 | | 91 char *namealloc (char *name); |
338 | | 92 |
339 | | 93 /* nombre maximum de noms dans la table */ |
340 | | 94 #define MAX_NAMEALLOC 1000 |
341 | | 95 |
342 | | 96 |
343 | | 97 /* ------------------------------------------------------------------------ */ |
344 | | 98 |
345 | | 99 /* |
346 | | 100 * dejavu permet de savoir si un nom a déjà été vu |
347 | | 101 * parametres: |
348 | | 102 * name = chaine de caractères |
349 | | 103 * comportement: |
350 | | 104 * name est recherché dans la table, |
351 | | 105 * s'il est absent on ajoute une copie de name dans la table |
352 | | 106 * retour: |
353 | | 107 * rend 1 s'il était déjà présent sinon 0 |
354 | | 108 */ |
355 | | 109 unsigned dejavu (char *name); |
356 | | 110 |
357 | | 111 /* nombre maximum de noms dans la table */ |
358 | | 112 #define MAX_DEJAVU 1000 |
359 | | 113 |
360 | | 114 #endif |
| 247 | #ifndef _HTE_H_ |
| 248 | #define _HTE_H_ |
| 249 | |
| 250 | #include <stdlib.h> |
| 251 | |
| 252 | /* |
| 253 | * Les deux structures ci-dessous ne sont pas définies ici |
| 254 | * elles seront redéfinies dans chaque fichier |
| 255 | */ |
| 256 | typedef struct hte_item_s hte_item_t; |
| 257 | typedef struct hte_data_s hte_data_t; |
| 258 | |
| 259 | /* |
| 260 | * structure définissant la table de hachage |
| 261 | * On y trouve le nombre de liste de liste et |
| 262 | * un pointeur vers le tableau de liste |
| 263 | */ |
| 264 | typedef struct hte_root_s |
| 265 | { |
| 266 | size_t NB_LIST; /* nombre de liste d'ITEM du dictionnaire */ |
| 267 | hte_item_t **LIST; /* pointeur sur un tableau de liste d'ITEM */ |
| 268 | } hte_root_t; |
| 269 | }}} |
| 270 | {{{ |
| 271 | /* |
| 272 | * Calcul de l'index de hachage de Donald Knuth |
| 273 | * Elle produit un nombre entier à partir d'une chaine de caractères. |
| 274 | */ |
| 275 | extern unsigned hte_hash (char *key); |
| 276 | |
| 277 | /* |
| 278 | * hte_create fabrique une table de hachage vide |
| 279 | * parametres: |
| 280 | * nb_item = nombre d'item maximum prévu dans la table de hachage |
| 281 | */ |
| 282 | extern hte_root_t *hte_create (size_t nb_item); |
| 283 | }}} |
| 284 | {{{ |
| 285 | /* |
| 286 | * hte_add ajoute l'item (key,data) |
| 287 | * parametres: |
| 288 | * root = pointeur sur la table de hachage |
| 289 | * key = pointeur sur une chaine de caractères (la clé) |
| 290 | * data = donnée associée à key |
| 291 | * comportement: |
| 292 | * La clé key passée en parametre est comparée à celles présentes dans |
| 293 | * la table. Si la clé n'est pas trouvée alors un nouvel item est créé |
| 294 | * avec le couple (key,data). La clé key est en fait duppliquée. |
| 295 | * Si la clé est trouvée, le champ DATA de l'item présent dans la |
| 296 | * table est remplacé par le paramètre data de la fonction. |
| 297 | * retour: |
| 298 | * Si l'item n'a pu etre créé faute d'espace, on sort du programme. |
| 299 | */ |
| 300 | extern void hte_add (hte_root_t * root, char *key, hte_data_t * data); |
| 301 | |
| 302 | /* |
| 303 | * hte_get recherche item, et en cas d'absence l'ajoute |
| 304 | * parametres: |
| 305 | * root = pointeur pour la table de hachage |
| 306 | * key = pointeur sur une chaine de caractères (la clé) |
| 307 | * comportement: |
| 308 | * La clé passée en parametre est comparé a celles présentes dans la |
| 309 | * table de hachage. |
| 310 | * retour: |
| 311 | * Si la clé est trouvée alors la fonction retourne le champ data |
| 312 | * sinon la fonction rend NULL. |
| 313 | */ |
| 314 | extern hte_data_t *hte_get (hte_root_t * root, char *key); |
| 315 | }}} |
| 316 | {{{ |
| 317 | /* |
| 318 | * namealloc permet de garantir l'unicité des chaines de caractères |
| 319 | * parametres: |
| 320 | * name = chaine de caractères |
| 321 | * comportement: |
| 322 | * name est recherché dans la table, |
| 323 | * s'il est absent on ajoute une copie de name dans la table |
| 324 | * retour: |
| 325 | * un pointeur sur la copie de la table |
| 326 | */ |
| 327 | char *namealloc (char *name); |
| 328 | |
| 329 | /* nombre maximum de noms dans la table */ |
| 330 | #define MAX_NAMEALLOC 1000 |
| 331 | }}} |
| 332 | {{{ |
| 333 | /* |
| 334 | * dejavu permet de savoir si un nom a déjà été vu |
| 335 | * parametres: |
| 336 | * name = chaine de caractères |
| 337 | * comportement: |
| 338 | * name est recherché dans la table, |
| 339 | * s'il est absent on ajoute une copie de name dans la table |
| 340 | * retour: |
| 341 | * rend 1 s'il était déjà présent sinon 0 |
| 342 | */ |
| 343 | unsigned dejavu (char *name); |
| 344 | |
| 345 | /* nombre maximum de noms dans la table */ |
| 346 | #define MAX_DEJAVU 1000 |
| 347 | |
| 348 | #endif |