Introduction

Le besoins ne indexation sont nombreux et souvent différents les uns des autres. Parfois, la priorité doit être donnée à la vitesse d'exécution, parfois à la trace mémoire.

L'idée à la base des arbres ASCII est avant tout d'avoir un mécanisme de recherche des données à partir de chaine exactes de manière très rapide, en se servant du caractère comme d'un index de tableau.
Le temps d'accès aux données n'est alors fonction que de la longueur de la chaîne clef, et les opérations de recherches sont simple : déréférencement de pointeur, indexation.

A contrario, on réserve beaucoup de mémoire, et la plupart du temps pour rien.

Cette surconsommation peut être nettement diminuée en ne prenant pas l'ensemble du code ASCII en entrée, mais, en utilisant une table de traduction, de se restreindre à un sous ensemble de caractères. Une seconde version des arbre ASCII ne prenant en compte que les caractères alpha numérique et du souligné est présentée.

Description

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 *).

Architecture du composant « arbre ASCII »

Structure de données

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 _atree_t *patree_t;

L'interface est constituée de 4 fonctions simples et d'une fonction de débug.

Fonctions de base

atree_new

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

atree_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.

	patree_t atree_destroy(patree_t p);

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

atree_retrieve

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

Fonction de débug

atree_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 atree_dump(patree_t p, void (*f_dumpdata)(void *));

Exemple

#include <stdio.h> #include "storage.h" #include "atree.h" #include "mem.h" /* Fichier contentant les noms des couleurs prédéfinis de X11 (/usr/X11*/include/X11/rgb.txt) : */ #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; }

Composant plus économe : atr

Le composant atr est directement dérivé du composant atree. Il restreint la quantité de mémoire allouée en ne s'occupant que d'un sous-ensemble du code ASCII : les caractères alpha numérique augmentés du souligné ([A-z0-9_]).

Son interface est rigoureusement identique à celle du composant atree mais les points d'entrées sont préfixés par atr_ au lieu de atree_

Le mécanisme d'indexation ne se fait plus directement par code ASCII mais par la traduction du code ASCII en index via une table de traduction :

/* [A-z0-9_]; ==> 26 * 2 + 10 + 1 = 63; 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 01234567890123456789012345678901234567890123456789012345678901234567890 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz_ ^ ^ ^ */ static int atr_char2index(char c) { static char __atr__tt__[] = { /* 0 1 2 3 4 5 6 7 */ /*0*/ 63, 63, 63, 63, 63, 63, 63, 63, /*1*/ 63, 63, 63, 63, 63, 63, 63, 63, /*2*/ 63, 63, 63, 63, 63, 63, 63, 63, /*3*/ 63, 63, 63, 63, 63, 63, 63, 63, /*4*/ 63, 63, 63, 63, 63, 63, 63, 63, /*5*/ 63, 63, 63, 63, 63, 63, 63, 63, /*6*/ 0, 1, 2, 3, 4, 5, 6, 7, /*7*/ 8, 9, 63, 63, 63, 63, 63, 63, /*8*/ 63, 10, 11, 12, 13, 14, 15, 16, /*9*/ 17, 18, 19, 20, 21, 22, 23, 24, /*A*/ 25, 26, 27, 28, 29, 30, 31, 32, /*B*/ 33, 34, 35, 63, 63, 63, 63, 62, /** <--- '_' = 62!!! **/ /*C*/ 63, 36, 37, 38, 39, 40, 41, 42, /*D*/ 43, 44, 45, 46, 47, 48, 49, 50, /*E*/ 51, 52, 53, 54, 55, 56, 57, 58, /*F*/ 59, 60, 61, 63, 63, 63, 63, 63 }; return __atr__tt__[c];

Notice