Provided by: manpages-fr-extra_20151231_all 
NOM
lh_new, lh_free, lh_insert, lh_delete, lh_retrieve, lh_doall, lh_doall_arg, lh_error -
table de hachage dynamique
SYNOPSIS
#include <openssl/lhash.h>
DECLARE_LHASH_OF(<type>);
LHASH *lh_<type>_new();
void lh_<type>_free(LHASH_OF(<type> *table);
<type> *lh_<type>_insert(LHASH_OF(<type> *table, <type> *data);
<type> *lh_<type>_delete(LHASH_OF(<type> *table, <type> *data);
<type> *lh_retrieve(LHASH_OF<type> *table, <type> *data);
void lh_<type>_doall(LHASH_OF(<type> *table, LHASH_DOALL_FN_TYPE func);
void lh_<type>_doall_arg(LHASH_OF(<type> *table, LHASH_DOALL_ARG_FN_TYPE func,
<type2>, <type2> *arg);
int lh_<type>_error(LHASH_OF(<type> *table);
typedef int (*LHASH_COMP_FN_TYPE)(const void *, const void *);
typedef unsigned long (*LHASH_HASH_FN_TYPE)(const void *);
typedef void (*LHASH_DOALL_FN_TYPE)(const void *);
typedef void (*LHASH_DOALL_ARG_FN_TYPE)(const void *, const void *);
DESCRIPTION
Cette bibliothèque implémente des tables de hachage dynamiques qui ont une vérification de
type. Les entrées de la table de hachage peuvent être des structures arbitraires. En
général, elles consistent en des champs de clés et de valeurs.
h_<type>_new() crée une nouvelle structure LHASH_OF(<type)> pour stocker des données
arbitraires et offre les rétroactions « hachage » et « comparer » pour organiser les
entrées de la table. La rétroaction hash prend un pointeur vers une entrée de la table
comme argument et renvoie un unsigned long haché comme champ clé. La valeur de hachage est
normalement tronquée à une puissance de 2, faites donc attention à ce que la fonction de
hachage renvoie des bits de poids faibles mélangés. L'appel compare prends deux arguments
(deux pointeurs vers deux entrées de la table de hachage), et renvoie 0 si leurs clés sont
différentes, une valeur différente de 0 sinon. Si la table de hachage contient des valeurs
d'un type particulier et que hash et compare hache/compare ces types, alors les macros
DECLARE_LHASH_HASH_FN et IMPLEMENT_LHASH_COMP_FN peuvent être utilisées pour créer des
emballages de rétroaction d'un prototype requis par lh_<type>_new(). Elles offrent un
typage par variable avant d'appeler une rétroaction spécifique à un type écrite par
l'auteur de l'application. Ces macros, ainsi que celles utilisées pour les appels
« doall », sont définies comme suit :
#define DECLARE_LHASH_HASH_FN(name, o_type) \
unsigned long name##_LHASH_HASH(const void *);
#define IMPLEMENT_LHASH_HASH_FN(name, o_type) \
unsigned long name##_LHASH_HASH(const void *arg) { \
const o_type *a = arg; \
return name##_hash(a); }
#define LHASH_HASH_FN(name) name##_LHASH_HASH
#define DECLARE_LHASH_COMP_FN(name, o_type) \
int name##_LHASH_COMP(const void *, const void *);
#define IMPLEMENT_LHASH_COMP_FN(name, o_type) \
int name##_LHASH_COMP(const void *arg1, const void *arg2) { \
const o_type *a = arg1; \
const o_type *b = arg2; \
return name##_cmp(a,b); }
#define LHASH_COMP_FN(name) name##_LHASH_COMP
#define DECLARE_LHASH_DOALL_FN(name, o_type) \
void name##_LHASH_DOALL(void *);
#define IMPLEMENT_LHASH_DOALL_FN(name, o_type) \
void name##_LHASH_DOALL(void *arg) { \
o_type *a = arg; \
name##_doall(a); }
#define LHASH_DOALL_FN(name) name##_LHASH_DOALL
#define DECLARE_LHASH_DOALL_ARG_FN(name, o_type, a_type) \
void name##_LHASH_DOALL_ARG(void *, void *);
#define IMPLEMENT_LHASH_DOALL_ARG_FN(name, o_type, a_type) \
void name##_LHASH_DOALL_ARG(void *arg1, void *arg2) { \
o_type *a = arg1; \
a_type *b = arg2; \
name##_doall_arg(a, b); }
#define LHASH_DOALL_ARG_FN(name) name##_LHASH_DOALL_ARG
Un exemple de table de hachage qui stocke (des pointeurs vers) des
structures du type « STUFF » pourrait être défini comme suit :
/* Calcule la valeur de hachage de « tohash » (implémenté ailleurs) */
unsigned long STUFF_hash(const STUFF *tohash);
/* Ordonne « arg1 » et « arg2 » (implémenté ailleurs) */
int stuff_cmp(const STUFF *arg1, const STUFF *arg2);
/* Crée un emballage de fonction ayant un type sûr pour utilisation interne dans LHASH */
static IMPLEMENT_LHASH_HASH_FN(stuff, STUFF);
static IMPLEMENT_LHASH_COMP_FN(stuff, STUFF);
/* ... */
int main(int argc, char *argv[]) {
/* Crée une nouvelle table de hachage en utilisant les emballages de hachage/comparaison */
LHASH_OF(STUFF) *hashtable = lh_STUFF_new(LHASH_HASH_FN(STUFF_hash),
LHASH_COMP_FN(STUFF_cmp));
/* ... */
}
lh_<type>_free() libère la structure LHASH_OF(<type)> de table. Les entrées de la table de
hachage allouées ne seront pas libérées ; pensez à utiliser lh_<type>_doall() pour
désallouer les entrées restantes dans la table de hachage (voir ci-dessous).
lh_<type>_insert() insère la structure pointée par data dans table. S'il y a déjà une
entrée avec la même clé, l'ancienne valeur est remplacée. Notez que lh_<type>_insert()
stocke le pointeur, les données ne sont pas copiées.
lh_<type>_delete() supprime une entrée de table.
lh_<type>_retrieve() cherche une entée dans table. Normalement, data est une structure
avec de(s) champ(s) clé(s) initialisés ; la fonction renverra un pointeur vers une
structure entièrement peuplée.
lh_<type>_doall() fera, pour toutes les entrées de la table de hachage, appel à func avec
en paramètre l'objet contenant les données. Pour lh_<type>_doall() et
lh_<type>_doall_arg(), le forçage de type du pointeur doit être évité dans les
rétroactions (voir NOTE) — au lieu de cela il faut utiliser les macros de déclaration ou
implémentation pour créer des emballages avec un type vérifié qui typent les variables
avant d'appeler les rétroactions spécifiques aux types. Un exemple de cela est illustré
ici avec une rétroaction qui est utilisée pour nettoyer les ressources pour les objets
contenus dans la table de hachage avant que la table elle-même soit désallouée.
/* Nettoie les resources qui appartiennent à S<« a »> (ceci est implémenté ailleurs) */
void STUFF_cleanup_doall(STUFF *a);
/* implémentation d'un prototype compatible d'emballage pour S<"STUFF_cleanup »> */
IMPLEMENT_LHASH_DOALL_FN(STUFF_cleanup, STUFF)
/* ... puis plus tard dans le code ... */
/* pour lancer S<« STUFF_cleanup »> sur toutes les entrées dans la table de hachage ... */
lh_STUFF_doall(hashtable, LHASH_DOALL_FN(STUFF_cleanup));
/* Puis le hachage de la table peut être désalloué */
lh_STUFF_free(hashtable);
Quand vous faites cela, faites attention si vous supprimez des entrées dans la table de
hachage dans vos retours de fonction : la table peut rétrécir, ce qui fera changer de
place dans la table de hachage l'objet sur lequel vous travaillez en ce moment, — cela
peut causer un saut de certaines entrées pendant l'itération. La deuxième meilleure
solution est de régler hash->down_load=0 avant de commencer (ce qui empêchera la table de
hachage de se raccourcir). La meilleure solution est probablement d'éviter de supprimer
des objets de la table de hachage dans un retour « doall ».
lh_<type>_doall_arg() est identique à lh_<type>_doall() sauf que func sera appelé avec arg
comme second argument et func devrait être du type LHASH_DOALL_ARG_FN_TYPE (un prototype
de rétroaction qui est passé à la table d'entrée comme un argument supplémentaire). Pour
lh_doall(), il est possible de choisir de déclarer une rétroaction personnelle avec un
prototype correspondant aux types présents et déclarer ou implémenter des macros pour
créer des emballages qui forcent le type des variables avant d'appeler les rétroactions
spécifiques à un type. Un exemple de cela est expliqué ici (affichage de toutes les
entrées de la table de hachage vers un BIO qui est fourni par l'appelant) :
/* Imprime l'objet S<« a »> dans S<« output> S<bit »> (cela est implémenté ailleurs) */
void STUFF_print_doall_arg(const STUFF *a, BIO *output_bio);
/* implémentation d'un prototype compatible d'emballage pour S<« STUFF_print »> */
static IMPLEMENT_LHASH_DOALL_ARG_FN(STUFF, const STUFF, BIO)
/* ... puis plus tard dans le code ... */
/* Imprimer toute la table de hachage dans un BIO particulier */
lh_STUFF_doall_arg(hashtable, LHASH_DOALL_ARG_FN(STUFF_print), BIO,
logging_bio);
lh_<type>_error() peut être utilisée pour déterminer si une erreur s'est produite dans la
dernière opération. lh_<type>_error() est une macro.
VALEURS DE RETOUR
lh_<type>_new() renvoie NULL en cas d'erreur, sinon elle renvoie un pointeur vers la
nouvelle structure LHASH.
Quand une entrée d'une table de hachage est remplacée, lh_<type>_insert() renvoie la
valeur remplacée. NULL est renvoyée lors d'une opération normale et en cas d'erreur.
lh_<type>_delete() renvoie l’entrée qui est supprimée. NULL est renvoyée si cette valeur
n'existe pas dans la table de hachage.
lh_<type>_retrieve() renvoie l'entrée de la table de hachage si elle a été trouvée, NULL
sinon.
lh_<type>_error() renvoie 1 si une erreur s'est produite dans la dernière opération, 0
sinon.
lh_<type>_free(), lh_<type>_doall() et lh_<type>_doall_arg() ne renvoient pas de valeurs.
NOTE
Les différentes macros et les types retour de fonction LHASH existent pour faire en sorte
de rendre la vérification de type du code possible sans forcer une conversion de type — un
mal qui rend l'application du code plus difficile à vérifier et qui offre une fenêtre vers
les corruptions de pile et d'autres bogues difficiles à trouver. Cela, apparemment, viole
la convention ANSI-C.
Le code LHASH voit les entrées de la table comme des données constantes. De ce fait, il
représente les objets insérés avec lh_insert() avec un type de pointeur « const void * ».
C'est pour cela que les rétroactions comme celles utilisées par lh_doall() et
lh_doall_arg() déclarent leurs prototypes avec « const », même pour les paramètres qui
renvoient les pointeurs vers les objets de table — par esprit de cohérence, les données
fournies par l'utilisateur sont toujours considérées « const » pour le code de LHASH.
Mais, comme les appelants fournissent eux-mêmes ces pointeurs, ils peuvent choisir si tous
les paramètres doivent être traités comme constants.
Comme exemple, une table de hachage peut être maintenue par du code qui, pour des raisons
d'encapsulation, a uniquement un accès « const » aux données qui sont indexées dans la
table de hachage (c'est-à-dire, il est renvoyé comme « const » dans une autre partie du
code) — dans ce cas les prototypes LHASH sont corrects tels quels. Inversement, si
l'appelant est responsable de la durée de vie des données en question, alors il souhaitera
probablement faire des modifications des objets de la table, envoyés dans lh_doall() ou
lh_doall_arg() de façon rétroactive (voir l'exemple « STUFF_cleanup » ci-dessus). Si c'est
le cas, l'appelant peut soit forcer le type (s'il fournit les rétroactions elles-mêmes) ou
utiliser les macros pour déclarer ou implémenter les emballages des fonctions sans les
types « const ».
Les appelants qui ont seulement un accès à des données « const » dans leurs tables
d'indexation, mais qui déclarent des retours sans types constants (ou forcent la
suppression de type), créent de ce fait leurs propres risques ou bogues sans y être
encouragés par l'API. Dans le même ordre d'idées, lespersonnes vérifiant le code doivent
porter une attention toute particulière à une quelconque instance des macros
DECLARE/IMPLEMENT_LHASH_DOALL_[ARG_]_FN qui fournissent un type sans qualificatif
« const ».
BOGUES
lh_<type>_insert() renvoie NULL pour une réussite ou un échec.
FONCTIONNEMENT INTERNE
La description suivante est basée sur la documentation de SSLeay :
La bibliothèque lhash implémente une table de hachage décrite dans Communications of the
ACM en 1991. Ce qui rend cette table de hachage différente est que lors du remplissage de
cette table de hachage, sa taille augmente (ou décroît) grâce à OPENSSL_realloc(). Quand
un redimensionnement est terminé, au lieu d'avoir une redistribution sur deux fois plus de
« compartiments », un compartiment est découpé. De ce fait lorsqu'une « expansion » est
faite, le coût de redistribution de certaines valeurs reste minimal. Les insertions
suivantes auront pour effet de faire des redistributions sur un seul « compartiment » mais
il n'y aura jamais de coût élevé à cause d'une redistribution sur tous les
« compartiments ».
L'état d'une table de hachage en particulier est gardé dans une structure LHASH. La
décision d'agrandir ou de rapetisser la taille de la table de hachage est faite selon la
« charge » de cette table de hachage. La charge est le nombre d'objets divisé par la
taille de la table de hachage. Les valeurs par défaut sont les suivantes. Si
(hash->up_load < load) =>, agrandir. Si (hash->down_load > load) =>, rapetisser. La valeur
par défaut de up_load est 1 et la valeur par défaut de down_load est 2. Ces nombres
peuvent être modifiés par l'application en jouant sur la valeur des variables up_load et
down_load. La « charge » est gardée sous une forme qui est multipliée par 256. Donc
hash->up_load=8*256; mettra une charge de 8.
Si les performances vous intéressent, le champ à regarder est num_comp_calls. La
bibliothèque de hachage garde en mémoire toutes les valeurs de hachage pour chaque objet,
donc quand une recherche est terminée, les « hachages » sont comparés, s'il y a une
correspondance, alors une comparaison entière est faite, et hash->num_comp_calls est
incrémenté. Si num_comp_calls n'est pas égal à num_delete plus num_retrieve, cela veux
dire que les fonctions de hachage génèrent des hachages identiques pour des valeurs
différentes. Il est probablement préférable de changer vos fonctions de hachage si c'est
le cas car si votre table de hachage a 10 objets dans un « compartiment », il peut être
recherché avec 10 comparaisons de unsigned long et des traversées de 10 listes chaînées.
Le coût sera bien moins élevé que 10 appels à la fonction de comparaison.
lh_strhash() est un exemple de fonction de hachage de chaîne.
unsigned long lh_strhash(const char *c);
Puisque les routines LHASH sont normalement passées comme structure, cette routine ne
serait normalement pas passée à lh_<type>_new(), au lieu de cela elle devrait être
utilisée dans la fonction passée à lh_<type>_new(),
VOIR AUSSI
lh_stats(3)
HISTORIQUE
La bibliothèque lhash est disponible dans toutes les versions de SSLeay et d'OpenSSL.
lh_error() a été ajoutée dans SSLeay 0.9.1b.
Cette page man est dérivée de la documentation de SSLeay
Dans OpenSSL 0.9.7, toutes les fonctions de hachage qui étaient passées comme pointeurs de
fonction ont été modifiées pour une meilleure sécurité de type, et les types de fonction
LHASH_COMP_FN_TYPE, LHASH_HASH_FN_TYPE, LHASH_DOALL_FN_TYPE et LHASH_DOALL_ARG_FN_TYPE
sont devenus disponibles.
Dans OpenSSL 1.0.0 l'interface lhash a été remaniée pour une meilleure vérification de
types.
TRADUCTION
La traduction de cette page de manuel est maintenue par les membres de la liste
<debian-l10n-french AT lists DOT debian DOT org>. Veuillez signaler toute erreur de
traduction par un rapport de bogue sur le paquet manpages-fr-extra.