Les signaux
Implémentation d'une table d'association (~90 min)
Le but de cet exercice est de s'exercer à l'utilisation de pointeurs, tout en faisant un peu d'algorithmique.
Pour cela, nous allons implémenter une table d'association (map en anglais). Le principe d'une table d'association est d'associer une clé à une valeur. Les tables d'associations sont très souvent utilisées comme mémoire cache afin d'augmenter la vitesse de réponse de site web. Par exemple, la table d'association memcached est utilisée par facebook ou twitter.
Pour cet exercice, nous vous fournissons plusieurs fichiers (dans map.tgz):
- map.h: contient l'interface de la table d'association
- test_map.c: un programme de test utilisant la table d'association. Ce programme simule le comportement d'un site web. Des requêtes de clients souhaitant consulter un produit sont générées. Si le produit est dans la table d'association, il est affiché. Sinon, il la description du produit est chargée depuis un fichier et ajouté à la table d'association.
- products.dat: un fichier contenant la liste des produits disponibles
Pour commencer, mettons en place la chaîne de compilation. Dans le fichier map.c, créez des fonctions "vides" dont les prototypes sont dans map.h.
Créez ensuite un Makefile permettant de générer l'exécutable test_map à partir de test_map.c et map.c.
Dans un premier temps, nous allons implémenter la table d'association sous la forme d'un tableau de struct couple. Définissez le type struct couple comme une structure contenant une clé de type int, et une valeur de type void*.
Un struct map peut maintenant être défini comme une structure contenant un tableau de struct couple, et un entier représentant le nombre de couples (clé, valeur) stockés dans le tableau.
Implémentez la fonction map_init. Cette fonction alloue un struct map. Lors de l'initialisation de la structure, le pointeur est initialisé à NULL (donc le tableau est vide).
Implémentez la fonction map_put. Cette fonction cherche le couple dont la clé est passée en paramètre. Si aucun couple n'est trouvé, le tableau de couple est agrandi (en utilisant la fonction realloc), et le couple est stocké dans la dernière case du tableau. Enfin, la clé et la valeur passées en paramètre sont affectées au couple.
Implémentez la fonction map_get. Cette fonction cherche le couple dont la clé est passée en paramètre et retourne la valeur associée. Si la clé n'est pas trouvée, la fonction retourne NULL.
Enfin, implémentez la fonction map_free qui libère le tableau de couples et la structure map.
Vous pouvez maintenant tester votre implémentation en utilisant le programme test_map. Voici un exemple d'exécution attendu:
L'implémentation d'une table d'association en utilisant des tableaux extensibles est certes simple mais très inefficace quand le nombre d'entrées devient grand (l'insertion d'un nouveau couple se fait en O(n), où n est le nombre des couples de la table d'association). Nous allons maintenant fournir une autre implémentation se basant sur un arbre binaire de recherche.
Faites une copie du fichier map.c nommée map_tree.c, et modifiez le Makefile pour créer un deuxième exécutable test_map_tree utilisant cette iméplementation à la place de celle présente dans map.c.
Pour stocker les couples dans un arbre binaire de recherche, définissez un type struct node contenant une clé, une valeur, et deux pointeurs vers struct node nommés left et right. La structure node représente un noeud de l'arbre, et left et right représentent les fils gauche et droit du noeud.
Modifiez la structure map afin qu'elle contienne un pointeur sur struct node nommé root. Ce pointeur fait référence à la racine de l'arbre binaire de recherche.
Implémentez la fonction map_init. Cette fonction alloue un struct map, et initialise root à NULL.
Implémentez la fonction map_free. Une façon simple d'implémenter cette fonction consiste à créer une fonction void free_node(struct node*n) qui libère récursivement les fils gauche et droit de n avant de libérer n.
Implémentez une fonction static struct node* insert_node(struct node* tree, struct node* n). Cette fonction insère le noeud n dans l'arbre tree et retourne la nouvelle racine de l'arbre. Cette fonction doit créer un arbre binaire de recherche: toutes les clés inférieures à la clé d'un noeud sont stockées dans son sous-arbre gauche, et toutes les clés supérieures à la clé d'un noeud sont stockées dans son sous-arbre droit.
Modifiez la fonction map_put afin d'utiliser insert_node lorsqu'un nouveau couple est inséré.
Modifiez la fonction map_get afin qu'elle recherche un couple dans l'arbre binaire de recherche.
Equilibrage de l'arbre (Challenge, ~ 2h)
L'utilisation d'un arbre binaire de recherche permet de réduire la complexité de la recherche d'une clé. Toutefois, il existe des cas pathologiques pour lesquels l'arbre construit est déséquilibré, et pour lequel la recherche d'une clé ne se fait pas en O(log(n)), mais en O(n) (où n est le nombre de couples (clé, valeur) stockés dans l'arbre).
Par exemple, en insérant les clés dans l'ordre croissant:
chaque élément est inséré à droite de l'élément précédent, et l'arbre généré est donc une liste. La recherche d'un élément se fait donc en O(n).
Pour palier ce problème, il est nécessaire d'équilibrer l'arbre lors de l'insertion d'un élément. Une façon d'équilibrer l'arbre consiste à implémenter un arbre rouge-noir.
Implémentez la fonction void print_tree(struct map* map) qui affiche l'arbre binaire de recherche. Vérifiez avec cette fonction que l'insertion des clés 1, 2, ..., 10 mène à un déséquilibre de l'arbre.
Modifiez ensuite la fonction map_put afin qu'elle garantisse l'équilibre de l'arbre en utilisant l'algorithme décrit sur cette page. Vérifiez avec print_tree que l'équilibrage fonctionne.
Signaux et variables globales (~ 60mn)
- associer le gestionnaire hello au signal SIGALRM et non à SIGINT,
- utiliser judicieusement la fonction alarm pour générer un signal toutes les secondes.
- modifier la macro N de façon à quitter après l'arrivée de 5000 signaux,
- modifier la fonction hello de façon à n'afficher Hello que toute les 1000 réceptions de signaux.
- définir une variable globale volatile de type unsigned long long (64 bits) nommée k et initialisée à 0,
- définir une variable locale de type unsigned long long dans la fonction main nommée ref et initialisée à 0n
- incrémenter k et ref à chaque tour de boucle dans la fonction main,
- afficher la différence entre ref et k avant de quitter dans la fonction main,
- quitter après avoir reçu 100 signaux au lieu de 5000.
