EPITA:Atelier:C:WE:2013:2014

Introduction

Voici le projet du Week-end pour l'atelier C (année 2013-2014.)

L'objectif cette année est d'implémenter une table de Hash complète.

Interface

Vous devez implémenter l'ensemble des opérations décrites dans l'en-tête suivant:

/* hash_table.h */
/* Hash Table implementation: header */
 
#include <stdlib.h>
#include <stdint.h>
 
#ifndef _HASH_TABLE_H_
#define _HASH_TABLE_H_
 
struct pair {
  uint32_t              hkey;
  char                 *key;
  void                 *value;
  struct pair          *next;
};
 
struct htable {
  size_t                size, capacity;
  struct pair         **tab;
};
 
/*
 * hash(data):
 * compute the hash of the nul terminated string data.
 */
uint32_t hash(char *data);
 
/*
 * create_htable(capacity):
 * build a new hash table with initial capacity.
 */
struct htable *create_htable(size_t capacity);
 
/*
 * access_htable(htable, key):
 * returns a pointer to the pair containing the given key
 */
struct pair *access_htable(struct htable *htable, char *key);
 
/*
 * add_htable(htable,key,value):
 * add the pair (key,value) to the hash table
 */
int add_htable(struct htable *htable, char *key, void *value);
 
/*
 * remove_htable(htable, key):
 * removes the pair containing the given key from the hash table
 */
void remove_htable(struct htable *htable, char *key);
 
/*
 * clear_htable(htable):
 * delete all pairs in the table
 */
void clear_htable(struct htable *htable);
 
#endif

Vous devez respecter la structure de données fournie, les tests pourront venir examiner la structure interne de votre table.

Travail

Vous devez fournir un seul fichier hash_table.h contenant au minimum les fonctions décrites dans l'en-tête hash_table.c

Votre fichier ne devra pas contenir de fonction main

La fonction de hash à implémenter est décrite dans la section suivante.

Les propriétés liées à l'insertion (augmentation de taille automatique, gestion des collisions … ) seront décrites dans les sections suivantes.

Le rendu

Votre rendu se fera sous la forme usuelle:

• une archive nommée: login-rushwc2014.tar.bz2
• cette archive contiendra:
  • un répertoire login-rushwc2014 qui contiendra:
    • un fichier AUTHORS au format * login
    • le fichier fourni hash_table.h
    • votre fichier hash_table.c

Le rendu est ouvert et fermera à 23h42 lundi 12 janvier 2014. Il se fera à ici: [1]

Description générale et fonction de Hash

Votre table de hashage stockera des pairs formées d'une clef (une chaine de caractères à la C) et d'un pointeur générique (void*) servant de valeur.

Les collisions seront gérées par chaînage: les pairs contiennent un pointeur next pointant sur une autre pair avec le même index.

Notre table de hash utilisera la fonction de hashage décrite plus loin et pour l'égalité des clefs nous utiliserons la fonction strcmp(3) de la libc.

Fonction de Hash

Nous utiliserons un algorithme de hash classique (vous pouvez essayer de retrouver son nom … )

En entrée vous avez une chaîne de caractère (terminée par un caractère de code ASCII 0, comme d'habitude) et en sortie un entier 32bits non-signé (type uint32_t défini dans stdint.h.)

• On démarre avec une valeur de hash (notée h) égale à 0
• On effectue une boucle sur chaque caractère de la clef:
  • on ajoute le caractère courant à h
  • on ajoute h multiplié par 1024 à lui même
  • on remplace h par le XOR (opérateur ^ en C) entre h et h divisé par 64
• Après la boucle, on ajoute h multiplié par 8 à h
• on remplace h par le XOR entre h et h divisé par 2048
• on ajoute h multiplié par 32768 à h
• on renvoie h

Création et recherche dans la table

La fonction create_htable(capacity) crée la table initiale avec une capacité initiale correspondant à capacity.

Dans notre table, toutes les cellules non-utilisées du tableau doivent être NULL</t>.

La recherche

La fonction <tt>accees_htable(htable, key) cherche une pair contenant la clef key. Cette fonction devra renvoyer le pointeur sur la paire correspondante contenu dans la table. Votre fonction renverra un pointeur NULL si la clef n'existe pas.

Pour la recherche de la clef key:

• vous devez calculer h = hash(key)
• vous devez calculer i = h % capacity pour avoir l'index dans le tableau
• Il faut maintenant chercher dans la liste chaînée dont la tête est à la case i une paire contenant la même valeur de hash (champ hkey) et bien sûr une clef égale (utiliser strcmp(3) pour ça.)

On notera que la fonction renvoie la pair complète, ce qui permet par exemple de mettre à jour le champ value de la pair.

Insertion et suppression

La fonction add_htable(htable,key,value) ajoute une nouvelle pair à la table. La fonction renvoie 0 si la clef existe déjà dans la table et une valeur différente de 0 sinon.

On commence comme pour la recherche, afin d'obtenir la position dans la table, si se faisant on rencontre la clef, on retourne 0 directement.

Une fois la case obtenue, on crée une nouvelle pair avec la clef, la valeur et le hashé de la clef. On ajoute cette nouvelle pair en tête de la liste dans la case correspondante.

La fonction remove_htable(htable, key) cherche la clef key et supprime la pair de sa liste.

Auto-ajustement de la taille

Lorsque la table est remplie au delà d'un certain seuil, le nombre de collisions augmente rapidement. Pour pallier à ça, nous allons redimensionner la table.

Lorsque que le rapport capacity/size est supérieur à 0.75 (75%) on double la taille de la table, pour se faire, il faut allouer le nouveau tableau et réinsérer toutes les pairs de l'original. Attention, la capacité aillant changée (bien mettre le champ à jour) il faut recalculer toutes les positions.

Vider la table

La dernière opération, clear_htable(htable) supprime toutes les pairs de la table. Attention, vous devez libérer la mémoire de chaque pairs !