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.