retour

Boite à outils en C : module btree

Description

btree est une bibliothèque de gestion d'abres binaires triés selon des clefs quelconques.

Interface

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.

Construction et destruction

btree_new

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);

btree_destroy

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);

store/get

btree_store

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);

btree_get

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);

Navigation

btree_goto

 void     *btree_goto(pbtree_t pb, void *data); 

btree_leftmost

 void     *btree_leftmost(pbtree_t pb); 

btree_rightmost

 void     *btree_rightmost(pbtree_t pb); 

btree_left

 void     *btree_left(pbtree_t pb); 

btree_right

 void     *btree_right(pbtree_t pb); 

btree_parent

 void     *btree_parent(pbtree_t pb); 

btree_prev

 void     *btree_prev(pbtree_t pb); 

btree_next

 void     *btree_next(pbtree_t pb); 

Boucles

btree_foreach

void      btree_foreach(pbtree_t pb,     void (*userf)(void *)); 

btree_foreach_reverse

void      btree_foreach_reverse(pbtree_t pb,     void (*userf)(void *)); 

Maintenance

 void      *btree_save(pbtree_t pb);
 void       btree_restore(pbtree_t pb, void *handle);

debug

btree_dump

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 btree_dump(pbtree_t p, void (*f_dumpdata)(void *));

Exemple

    #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