btree est une bibliothèque de gestion d'abres binaires triés selon des clefs quelconques.
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 _btree_t *pbtree_t;
L'interface est constituée de 5 groupes de fonctions: construction/destruction, store/get, de navigation, de maintenace et de BOUcles.
Cette fonction sert à créer l'arbre.
Elle prend en paramètre la fonction de tri des données.
typedef int (*comp_t)(void *, void *); pbtree_t btree_new(comp_t comp);
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.
pbtree_t btree_destroy(pbtree_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 ett
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.
void * btree_store(pbtree_t p, 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 * btree_retrieve(pbtree_t p, char *key);
void *btree_goto(pbtree_t pb, void *data);
void *btree_leftmost(pbtree_t pb);
void *btree_rightmost(pbtree_t pb);
void *btree_left(pbtree_t pb);
void *btree_right(pbtree_t pb);
void *btree_parent(pbtree_t pb);
void *btree_prev(pbtree_t pb);
void *btree_next(pbtree_t pb);
void btree_foreach(pbtree_t pb, void (*userf)(void *));
void btree_foreach_reverse(pbtree_t pb, void (*userf)(void *));
void *btree_save(pbtree_t pb);void btree_restore(pbtree_t pb, void *handle);
void btree_dump(pbtree_t p, void (*f_dumpdata)(void *));
#include <stdio.h>
#include "storage.h"
#include "btree.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) {
pbtree_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("btree 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 = btree_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 à btree l'association avec le nom de la couleur:
*/
btree_store(pa, cols[i], (void *) storage_add(ps, (char *) &rgb));
i++;
}
}
fclose(pf);
printf("\n*********\nbtree dump:\n");
btree_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) btree_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: */
btree_destroy(pa);
return 0;
}
retour