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 S<« STUFF »> pourrait être défini comme S<suit :>
/* Calcule la valeur de hachage de S<« tohash »> (implémenté ailleurs) */
unsigned long STUFF_hash(const STUFF *tohash);
/* Ordonne S<« arg1 »> et S<« 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 un succès 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.