Contrôle Final 1 – Année 2023/2024
- Durée du CF: 2h
- Tous les documents sont autorisés
- Vous avez à votre disposition le code des fichiers server_code_etudiant.h, et server_code_etudiant.c.
Echauffement (2 points)
Pour cet exercice, on s'intéresse au tableau client_t* clients[MAX_CLIENTS] défini à la ligne 8.
Quel est le type de chacune de ces expressions:
- clients[0]
- clients[0]->pid
- *clients[0]->client_conn
- &clients[0]->uid
Implémentation d'une hashtable (10 points)
Dans le code fourni, les clients sont stockés sous la forme d'un tableau clients
(défini à la ligne 8). Le but de cet exercice est de remplacer ce tableau par une
Pour rappel, une hashtable est une structure de données qui associe une clé (dans notre cas, le nom d'un client) à une valeur (ici, l'adresse de la structure client). Ce type de structure de données est fréquemment utilisé pour indexer des bases de données ou pour mettre en cache des données.
Fig 1: Exemple de hashtable
Dans notre mise en œuvre, la clé (une chaîne de caractères) est hachée par la fonction int hash(char key[NAME_MAX_LENGTH]). Le hash obtenu identifie la case du tableau buckets (défini dans server_code_etudiant.h) dans laquelle est stockée la valeur.
Comme plusieurs clés peuvent avoir le même hash, chaque case du tableau contient une liste chaînée d'éléments de type struct bucket dont les clés ont toutes le même hash.
Par exemple, dans la Figure 1, le hash de la clé beef vaut 2. Le couple (beef, tzyx) est donc stocké dans l'entrée 2 du tableau buckets. Le couple (help, zxty) est également stocké dans l'entrée 2, car le hash de help est également 2.
2 points
Implémentez la fonction struct bucket* ht_alloc(char key[NAME_MAX_LENGTH], client_t* value).
Cette fonction initialise un struct bucket en recopiant la clé key et la valeur value. La fonction retourne l'adresse du struct bucket initialisé.
Pour recopier des données d'une zone mémoire à une autre, nous vous demandons d'utiliser la fonction memcpy
- dest est l'adresse de la zone mémoire où recopier les données
- src est l'adresse des données à recopier
- n est le nombre d'octets à recopier
2 points
Implémentez la fonction struct bucket* ht_search(char key[NAME_MAX_LENGTH]).
Cette fonction calcule le hash d'une clé, puis parcourt la liste chaînée ht.buckets[hash] et cherche l'élément dont la clé vaut key et le retourne. Si aucun élément correspondant n'est trouvé, la fonction retourne NULL.
2 points
Implémentez la fonction void ht_insert(char key[NAME_MAX_LENGTH], client_t* value).
Cette fonction recherche (en appelant ht_search) si un élément key existe dans la hashtable et met à jour sa valeur value en appelant memcpy. Si l'élement key n'est pas présent dans la hashtable, la fonction alloue un nouvel élément (avec ht_alloc), et l'insère dans la liste ht.buckets[hash]. Si un nouvel élément est inséré, le champ nb_entries de la structure hash_table est incrémenté.
4 points
Implémentez la fonction void ht_remove(char key[NAME_MAX_LENGTH]).
Cette fonction supprime de la hashtable l'élément dont la clé vaut key. Si un élément est supprimé, le champ nb_entries de la structure hash_table est décrémenté.
Utilisation de la hashtable (8 points)
On souhaite implémenter 2 nouvelles commandes dans notre système de messagerie.
- La commande /dump_users <filename> enregistre la liste des utilisateurs actuellement connectés (et stockés dans la hashtable ht) dans le fichier filename.
- La commande /show_users affiche la liste des utilisateurs stockée dans un fichier par la commande dump_users
Le fichier utilisé pour stocker la liste des utilisateurs doit contenir:
- Un double représentant la date, obtenu en appelant la fonction void ht_get_clock(double *date)
- Un int représentant le nombre d'utilisateurs
- Une suite de char[NAME_MAX_LENGTH] représentant les noms des utilisateurs.
4 points
Implémentez la fonction void ht_dump(char* filename).
Cette fonction crée le fichier filename et y stocke la liste des utilisateurs actuellement connectés en respectant le format présenté ci-dessus.
4 points
Implémentez la fonction void ht_load(client_t* client, char* filename).
Cette fonction ouvre le fichier filename et y lit la liste des utilisateurs en respectant le format présenté ci-dessus. La fonction envoie au client client les informations lues, par exemple:
