Je v te résumer ce qu'il y a ds la bible du C là dessus.
on considere 2 fn principales :
install(s, t) qui enregistre le nom s et sa valeur de remplacement ds une table
lookup(s) qui recherche la chaine ds la table, et qui transmet un pointeur sur S, ou alors NULL si not found.
On utilise un algo de type 'hash'
=> le nom est transformé en un entier qui sert d'index ds le tableau. (un element du tableau pointe sur le debut d'une chaine de blocs possedant la meme valeur de type hash. (ou NULL s'il n'existe aucun nom ac cette valeur 'hash')
un bloc est defini comme suit :
struct nlist {
char *name ; //pointe sur le nom
char *def ; //pointe sur la valuer de remplacement.
struct nlist *next ; //pointe sur le prochain bloc.
}
hash : en fait, il fait la somme des valeurs des octets de la chaine et la retourne apres l'avoir ramenée à la taille du tableau.
hash(s)
char *s
{
int hashval;
for (hashval = 0 ; *s != '' ; )
hashval += *s++;
return(hashval % HASHSIZE) //hashsize c la taille du tableau ;)
}
pratik non ?
ça permet de diminuer pas mal le temps de recherche
voyons maintenant lookup :
struct nlist *lookup(s)
char *s ;
{
struct nlist *np ;
for (np = hashtab[hash(s)] ; np != NULL ; np = np->next) //cherche de bloc en bloc, jusqu'à la fin de la chaine de blocs.
if (strcmp(s, np->name) == 0)
return(np) ; //trouvé :)
return(NULL) ; //fin de chaine de bloc atteinte et pas trouvé => on transmet NULL
}
et la fonction install :
(si le nom à installer est déjà present, install remplace la definition par la nouvelle)
struct nlist *install(name, def)
char *name, *def ;
{
struct nlist *np, *lookup() ;
char *strsave(), alloc() ;
int hashval() ;
if ((np = lookup(name)) == NULL) { //si pas encore défini
np = (struct nlist *) alloc(sizeof(*np)) ; //reserve de la mem d'une maniere ou d'une autre
if (np == NULL)
return(NULL) ; //pas assez de place.
if ((np->name = strsave(name)) == NULL) //recopie la chaine à l'endroit que alloc à indiqué
return(NULL) ; //pas assez de place.
hashval = hash(np->name) ; //génère l'index du tableau (ie la valeur de type hash correspondant au nom)
np->next = hashtab[hashval] ; //met l'ancien pointeur ds next. (qui pointait vers le debut de la chaine de bloc avt qu'on ne remete ce bloc en plus). #attention# pour que ça fonctionne bien, je pense qu'il faudrait verifier que le tableau est bien initialisé avec des NULL au debut. Sinon en fin de chaine de bloc on risque d'avoir next qui contient n'importe quoi au lieu de NULL (ce qui ferait que la fin de chaine ne serait pas detectée ;))
hashtab[hashval] = np ; //actualise le pointeur d'origine de chaine.
} else //deja defini
free(np-def) ; //free previous def
if ((np->def = strsave(def)) == NULL)
return(NULL) ;
return(np) ;
}
voilà
bon, les fn ne sont pas de moi, mais les commentaires, si. donc i se peut qu'il y ait des conneries, mais je ne pense pas.
[edit]Edité par Pen^2 le 19-01-2002 à 15:35:27[/edit]
(surtout si on alloue juste un bloc mem 
)
