|
Composants, réutilisation et généricité : Une application aux arbres ASCII. |
atree est une bibliothèque de gestion d'abres dont les clefs sont des chaines ASCII.
Elle associe des données (pointeurs génériques) à une clef et retrouve les données associées à des clefs
Ce module a été écrit afin d'obtenir un parsing très rapide d'un nombre raisonnable de mots-clef.
Il peut aussi être utilisé comme gestionnaire de table de symboles.
Optimisé pour la vitesse d'execution, ils est par contre très gourmand en mémoire.
Chaque niveau de l'arbre est représenté par un tableau de 256 pointeurs sur un niveau suivant et d'un pointeur générique (void *).
La structure n'est pas décrite dans le fichier header. Elle est donc considérée comme privée et ne peut pas être déréférencée:
typedef struct _atree_t *patree_t;
L'interface est constituée de 4 fonctions simples et d'une fonction de débug.
Cette fonction sert à créer le premier niveau de l'arbre.
Elle ne prend aucun paramètre et retourne le premier niveau de l'arbre.
patree_t atree_new();
Cette fonction détruit la structure et libère la mémoire.
Elle prend en paramètre le pointeur vers la structure et retourne un pointeur NULL.
patree_t atree_destroy(patree_t p);
Cette fonction stocke un pointeur vers la donnée dans l'arbre.
Elle prend en paramètre le pointeur vers la structure de l'arbre, la clef d'insertion et
le pointeur vers les données.
Attention, cette fonction ne prend pas en charge l'allocation ni la désallocation de la donnée
elle même.
Attention, cette fonction ne vérifie pas la présence de données déjà indexées par la même clef.
Si des données sont présentées avec une clef, déjà existante, les anciennes données seront remplacées par
les nouvelles.
void * atree_store(patree_t p, char *key, void *data);
Cette fonction permet de retourner le pointeur sur la donnée indexée par la clef.
Elle prend en paramètre le pointeur vers la structure d'arbre et la clef recherchée.
Elle retourne le pointeur vers les données si la clef est connue, ou 0 dans le cas contraire.
void * atree_retrieve(patree_t p, char *key);
Cette fonction permet d'afficher le contenu complet de l'arbre.
Elle prend en paramètre le pointeur sur l'arbre et une fonction d'affichage des données.
void atree_dump(patree_t p, void (*f_dumpdata)(void *));
#include <stdio.h>
#include "storage.h"
#include "atree.h"
#include "mem.h"
/* Fichier contentant les noms des couleurs prédéfinis de X11: */
#define RGBFILE "rgb.txt"
/* structure des données r/g/b des couleurs */
typedef struct {
int r, g, b;
} rgb_t, *prgb_t;
/* fonction d'affichage d'une structure */
void rgb_print(void *p) {
prgb_t pr;
pr = (prgb_t) p;
printf("(%03d, %03d, %03d)", pr->r, pr->g, pr->b);
}
int main(void) {
patree_t pa;
pstorage_t ps;
/* déclaration d'une table contenant les 752 noms de couleur du fichier rgb.txt: */
char *cols[752];
int i;
char name[128];
FILE *pf;
mem_init(mem_VERBOSE);
printf("atree test\n");
/*
* initialise une zone de stockage dont
* chacun des éléments à pour taille sizeof(rgb_t)
* et allouant la mémoire par paquets de 100 éléments:
*/
ps = storage_new(sizeof(rgb_t), 100);
/* initialise la structure d'arbre ascii: */
pa = atree_new();
/* ouvre le fichier rgb.txt en lecture */
pf = fopen(RGBFILE, "r");
printf("store rgb data from %s\n", RGBFILE);
i = 0;
while (!feof(pf)) {
/* déclaration d'une structure rgb sur la pile servant de tampon: */
rgb_t rgb;
memset(name, 0, 128);
/* lit les données r/g/b et le nom (le premier seulement) de la couleur associée: */
if (fscanf(pf, "%d %d %d\t%[^\n]", &rgb.r, &rgb.g, &rgb.b, name) == 4) {
/* recopie le nom de la couleur dans le tableau des noms de couleurs: */
cols[i] = mem_strdup(name);
/*
* recopie le contenu de la structure rgb dans la zone de stockage.
* et ajoute demande à atree l'association avec le nom de la couleur:
*/
atree_store(pa, cols[i], (void *) storage_add(ps, (char *) &rgb));
i++;
}
}
fclose(pf);
printf("\n*********\natree dump:\n");
atree_dump(pa, rgb_print);
printf("\n*********\nretrieval\n");
/*
* pour toute les couleurs stockées, vérifie que l'on retrouve les
* paramètres r/g/b:
*/
for (i = 0; i < storage_used(ps); i++) {
prgb_t prgb0, prgb1;
prgb0 = (prgb_t) storage_get(ps, i);
prgb1 = (prgb_t) atree_retrieve(pa, cols[i]);
printf("%d --> %s: (%d, %d, %d) /// (%d, %d, %d)\n",
i, cols[i],
prgb0->r, prgb0->g, prgb0->b,
prgb1->r, prgb1->g, prgb1->b);
/* et libère au passage la mémoire où est stocké le nom de la couleur: */
mem_free(cols[i]);
}
/* détruit l'espace de strockage et libère la mémoire: */
storage_destroy(ps);
/* détruit la table de symbole: */
atree_destroy(pa);
return 0;
}