Boph : Hashs

Présentation générale

Structures de données


Survol des fonctions


Création/suppression.
Accès aux éléments et parcours des hashs.
Accès aux données des éléments.

Fichier à inclure.
Création/suppression.
Accès aux éléments et parcours des hash.
Accès aux données des éléments.

Fonctionnalités.

Permet la construction et l'accès à des tables de hachage en mémoire.
Ces tables sont parfois aussi nommées tableaux associatifs ou tables de transposition, j'ai même entendu parler de dictionary abstract data type, mais restons humbles et parlons de hash.
Pour une bonne introduction aux hashs, voir ce cours en français.

Il s'agit de l'implémentation d'un hashing utilisant des listes des éléments entrant en collision.
Dans cette version le tableau de buckets n'est pas dynamiquement extensible, ce qui peut entrainer une dégradation des performances si sa taille a été sous-évaluée à la création du hash. Dans une prochaine version, il sera possible de spécifier une stratégie d'extension à la création d'un hash.

Conçu pour être simple d'utilisation, souple et performant dans un grand nombre de cas, il est particulièrement efficace lorsque le nombre de données placées dans un hash peut être connu approximativement au moment de la création de ce hash.

Une de ses utilisation typique est le chargement puis la consultation d'un lexique, il peut aussi être utilisé comme table de symboles, pour stocker des valeurs associées à des variables dans un interpréteur etc.

Présentation générale

structures de données

Boph utilise principalement 2 types (typedef de structures) de données :

BophHandle

• Ce type référence un hash.
BophEntry

• Ce type référence un élement du hash. Par élément entendons la relation entre une clé et une donnée.
  Il contient les informations relatives aux données placées dans le hash, la clé et sa longueur, les données et leur longueur.

Survol des fonctions

Elles permettent de créer/supprimer des hashs et des éléments de ces hashs, d'associer des données à ces éléments, de parcourir les hashs etc.

Création/suppression.

• bophNew() : Allocation d'un hash éventuellement en le plaçant dans un container.
• bophDelete() : Suppression d'un hash.
• bophPut() : Allocation et ajout d'un élément dans le hash.
• bophDelEntry() : suppression d'un élément dont on fournit l'adresse.
• bophDelByKey() : suppression d'un élément dont on fournit la clé.

Accès aux éléments et parcours des hashs.

• bophGetEntry() : lecture d'un élément du hash.
• bophScan() : Appelle une fonction spécifiée pour chaque élément d'un hash.

Accès aux données des éléments.

• bophGetData() : accède à la donnée d'un élément.
• bophGetDataLength() : accède à la longueur de la donnée d'un élément.
• bophGetKey() : accède à la clé d'un élément.
• bophGetKeyLength() : accède à la longueur de la clé d'un élément.

API détaillée.

Fichier à inclure.

#include <bop.2/bop.h>

Création/suppression.

• BophHandle * bophNew( BopcHandle * container,
  
  char * name int size,
  unsigned int (*hFunc)(char *key,size_t keyLength) ,
  void (*hDel)(BophEntry * hEntry)
  )
  
  
  Allocation d'un hash.
  
  container est le handle d'un container retourné par bopcNew() ou NULL si on ne veut pas que le hash soit placé dans un container.
  name est un nom que l'on veut associer au hash, si la valeur NULL est spécifiée aucun nom ne sera associé au hash.
  size est le nombre de postes de la table 1/2 du nombre de clés devrait déjà être un assez bon choix. 10 à 20 % de plus que le nombre de clés devrait être optimal, plus cela devient vite du gaspillage. Cela dépend de la mémoire que vous avez et que vous décidez d'occuper.
  Pifométriquement, si vous ne savez pas au moment de la création de la hash le nombre de clés que vous allez y mettre, prenez le maximum entre le nombre que vous jugerez moyen, le nombre que vous jugerez habituel et le 1/4 du nombre que vous jugerez ne jamais être dépassé.
  A moins d'être particulièrement pingre, il n'y a guère de raison de descendre au dessous de 1024 postes. Il n'est pas possible de descendre au dessous d'un poste.
  Lorsque la valeur 0 est spécifiée, une valeur par défaut est choisie par boph de façon à ce que la taille de la table des buckets occupe une page, en général cela fait 1024 postes, le programme bopinfo de Bop-utils vous indiquera cete valeur sur votre machine.
  hFunc : fonction de hashage , si NULL une fonction par defaut est utilisée
  Cette fonction a pour format :
  unsigned int myHash( void * unused, char * key, size_t keylength )
  Boph prend ensuite le reste de la division du nombre retourné par le nombre de postes de la table pour avoir l'index du poste, il est donc inutile de faire cette division dans la fonction que vous donnez.
  hDel : fonction utilisée pour liberer les données associées à une entrée dans le hash, si NULL, l'entrée sera liberée par boph.
  cet argument peut etre utile si dans ces données il y a des pointeurs vers d'autres données qui doivent être libérées au même moment.
  
  exemple :
  bophHandle * hash ; .... hash = bophNew( NULL, NULL, 0, NULL, NULL) ; // crée un hash en se fiant aux valeurs par defaut
  // crée un hash "mon-hash" de 8192 postes dans un container (préalablement alloué par bopcNew)
  // ce hash utilisera la fonction de hashage myhash
  hash = bophNew( container, "mon-hash", 8192, myHash, NULL) ;
  
  Note : j'ai emprunté la fonction par défaut qui est donnée comme exemple dans "Compilers, Principles Techniques and tools" de Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman. Je l'ai légèrement modifiée de manière à ce qu'elle ait la même interface d'appel que les fonctions de hashage de Berkeley DB
  La fonction par défaut donne une dispersion légèrement meilleure dans les tests que j'ai effectués (hashage de mots de textes anglais) mais celles de Berkeley DB sont peut-être meilleures pour d'autres types de clé. J'ai placé ces dernières dans le répertoire samples/ de la distribution. Merci de lire leur license d'utilisation qui est placée dans ce répertoire et de vous vous y conformer si vous voulez les utiliser.
  
• void bophDelete( BophHandle * hHash )
  Suppression d'un hash. Les éléments du hash sont libérés.
  
• BophEntry * bophPut( BophHandle* hHash,
  
  char *key,
  size_t keyLength,
  void * data,
  size_t dataLength,
  int replace
  )
  
  Allocation et ajout d'un élément dans le hash. clé et données sont recopiées dans le hash.
  retourne un pointeur vers cet élément ou NULL en cas de problème.
  
  key et keyLength definissent la clé.
  data et dataLength les données associées à cette clé.
  replace peut etre :
  
  BOPH_PUT : ajout d'1 élément s'il n'existe pas deja ,
  retourne NULL si l'élément est deja present.
  BOPH_REPLACE : ajout ou remplace s'il existe deja.
  BOPH_TEST : ajout ou retourne l'élément existant.
  
  A partir de l'élément retourné on peut acceder à la clé et aux données par les fonctions :
  
  bophGetKey() , bophGetKeyLength() ,
  bophGetData , bophGetDataLength()
  
• void bophDelEntry( BophEntry * hEntry , void (*hDel)(BophEntry * hEntry) )
  
  hEntry : élément à supprimer
  hDel : fonction utilisée pour liberer les données associées à un élément dans le hash, si NULL boph libère les données et la clé.
  cet argument peut etre utile si dans ces données il y a des pointeurs vers d'autres données qui doivent être libérées au même moment.
  
• int bophDelByKey( BophHandle * hHash, char *key, size_t keyLength )
  suppression d'un élément dont on fournit la clé.
  retourne non-zero si un élément correspondant à la clé a été trouvé et supprimé, 0 sinon (élément non existant).
  

Accès aux éléments et parcours des hashs.

• BophEntry * bophGetEntry( BophHandle * hHash, char * key, size_t keyLength )
  retourne un pointeur sur un élément du hash hHash ayant la clé key de longueur keyLength ou NULL si cet élément n'appartient pas au hash.
  
• int bophScan( void * data, BophHandle * hHash, int (*hScan)(void * data, BophEntry *hEntry) )
  Appelle la fonction hscan() pour chaque élément hEntry du hash hHash.
  Data est un pointeur qui sera fourni a la fonction.
  Le scan s'arrête lorsque la fonction hScan() retourne une valeur non nulle, cette valeur est alors retournée par la fonction bophScan().
  

Accès aux données des éléments.

• void * bophGetData( hEntry )
  retourne un pointeur sur la donnée d'un élément.
  
• size_t bophGetDataLength( hEntry )
  retourne la longueur de la donnée d'un élément.
  
• void * bophGetKey( hEntry )
  retourne un pointeur sur la clé d'un élément.
  
• size_t bophGetKeyLength()
  retourne la longueur de la clé d'un élément.
  

Exemples.

Des programmes de test de Bop, par ailleurs inutiles, peuvent servir d'exemples :

• boprel.c
  Ce programme compare deux fichiers qu'il charge dans des hashs.
• bopwc.c
  Ce programme compte et affiche les mots d'un fichier qu'il charge dans un hash.
• bopmakeh.c et bopmakeh.h
  Fonction de chargement d'un fichier dans un hash, utilisé par boprel.c et bopwc.c.
  

Reste à faire.

Dans l'ordre de priorité décroissante ;

• Procurer une stratégie paramétrable d'extension des hashs.
• Ameliorer encore les performances.
• De meilleurs tests voire des benchmarks.
• De la cosmétologie dans les sources. Certains datent du paleolithique ...

Voir aussi.

• Les fonctions hsearch() etc. de la libc.
  elles ont les désavantages suivant :
  • Elles ne permettent de n'avoir qu'un seul hash à un niveau global dans un programme (Les extensions GNU corrigent cependant ce grave défaut.)
  • L'allocation et la libération des éléments de la table est laissé à la responsabilité du programmeur, ce qui lui donne un surcroit de travail, l'expose à des bugs et/ou à des "memory-leaks".
  • Il semble qu'il ne soit pas possible de supprimer un élément de la table (du moins, je n'ai pas trouvé comment).
  • Le hash n'est pas extensible, ce qui est aussi le cas de boph (Ce sera amélioré dans une prochaine version de bop).
  • Elles ne gèrent que des données de type string (chaines de caractères terminées par un zero), Boph traite tout type de donnée.
  Elles peuvent cependant être utilisées dans certains cas, lorsqu'à la fois :
  • Le nombre d'éléments est connu au moins approximativement au moment de la création du hash.
  • Le hash doit être relativement statique, sans suppression d'éléments.
  • Le données et les clés sont des strings.
  • Le hash est utilisé jusqu'à la fin du programme, ce qui rend facultatif la libération des éléments du hash.
  C'est utilisable dans un programme qui chargerait un lexique et dont la principale fonction serait d'y effectuer des recherches. Il peut difficilement être utilisé dans une librairie car si 2 librairies voulaient utiliser le même hash...
  

• La libraririe Roy.
  elle a les désavantages suivants :
  • L'allocation et la libération des éléments de la table est laissé à la responsabilité du programmeur, ce qui lui donne un surcroit de travail, l'expose à des bugs et/ou à des "memory-leaks".
  • Le données et les clés doivent être des strings.
  • Elle est en bonne partie implémentée sous formes de macros qui ont un effet de bord qui peut être indésirable (ce que boph n'a pas) mais ce n'est pas un très gros problème quand on le connait.
  • Elle est seulement documentée sous forme de pages man (mais Boph est très peu documenté sous forme de pages man, ce qui n'est pas non plus un avantage). Les pages man sont peu pratiques lorsque l'on veut avoir une vue d'ensemble d'une API, elles sont surtout utiles pour se rememorer l'utilisation des fonctions dont on connait la fonctionnalité mais que l'on emploie pas souvent.
  elle a les avantages suivants :
  • La taille des hashs est extensible (ce qui sera aussi le cas dans boph).
  Elle doit pouvoir (je n'ai pas fait l'essai, j'ai juste regardé les sources) être utilisée dans les mêmes circonstances que Boph lorsque ce dernier aura implémenté une stratégie d'extensibilité de la taille des hashs, cependant l'API de bop décharge le programmeur de l'allocation et la desallocation des éléments du hash.
  Je pense que ses performances doivent être à peu près équivalentes à celles de boph. A priori, c'est très correct.