TME2 : Langage C: étude de cas sur les tables de hachage

Objectif

Pour la majorité d'entre-vous, vous connaissez déjà le C, mais certains ne le connaissent que superficiellement. Nous devons essayer de mettre tout le monde au niveau, en vous faisant étudier un petit programme. L'objectif de ce programme est double :

1. Il doit d'une part vous permettre de faire une auto-évaluation de vos connaissances des outils de developpement C en vous posant des questions auxquelles vous devriez savoir répondre. Si ce n'est pas le cas, vous devez trouver les réponses dans les documentations (man, web), ou auprès de vos camarades.
2. Il vous offre un modèle de programme, avec makefile et man pour vos futurs développements.

Pour réaliser une application en C, vous devez savoir:

• Ecrire un programme C en respectant des conventions d'écriture.
• Compiler en plusieurs fichiers objet et en constituant une librairie.
• Décrire un makefile.
• Debugger en utilisant gdb ou xgdb.
• Faire des mesures de performances avec gprof.
• Ecrire un man sur l'outil.

Travail demandé

• Vous devez commencer par copier sur votre compte le répertoire :

cp -rp /users/enseig/encadr/cao/tme2 ~/cao/tme2

• Ce répertoire contient un programme utilisant une table de hachage.
• Le travail consiste:
  1. à répondre aux questions portant sur le code fourni. Les questions sont sur cette page. Vous rédigerez un compte rendu informatique pour vous même avec les réponses.
  2. à programmer des évolutions du programme:
• L'évaluation sera individuelle et orale au début du tme3.
• Commencez par lire le programme en entier et faîtes le tourner pour comprendre son fonctionnement.
• Répondez ensuite aux questions et faîtes les évolutions demandées.

Evolution du programme

Le programme fourni compte le nombre de mots d'un fichier texte et indique le nombre de mots présents et le nombre de mots différents. Votre programme devra indiquer pour chaque mot:

• le nombre d'occurences
• les numéros de lignes où il est présent

Vous donnerez également des statistiques sur l'usage des tables de hachage:

• taux de remplissage.
• moyenne du nombre de comparaisons nécessaire lors de la recherche d'un mot

Description des sources fournies

• Makefile ....................... description du processus de construction de l'exécutable.
• main.c, main.h ................. programme principal source et déclaration.
• count.c, count.h ............... algorithme de parcours d'un fichier texte en vue de comptage.
• hte.c, hte.h ................... fonction de création des tables de hachage et déclaration de toutes fonctions de gestion.
• dico.c, dejavu.c, namealloc.c .. fonctions de gestion des tables pour trois types d'usage
• man1/tool.1 .................... fichier au format man

Questions

Le Makefile

1. Completez la liste des dépendances lignes 24 à 28
2. Réécrivez les commandes en utilisant les variables automatiques : $@ $< $^
   • $@ : désigne la cible d'une règle
   • $< : désigne le premier fichier de la liste des sources d'une règle
   • $^ : désigne la liste des sources d'une règle
3. Donnez une raison à la definition des commandes et parametres au début du Makefile
4. A quoi servent les options -p, -g, -wall, -werror, -ansi
5. Comment demander l'optimisation maximale du compilateur
6. L'option -p est présente dans LDFLAGS et CFLAGS, pourquoi n'est-ce pas le cas de -g
7. Que fait la regle indent ? quelle est la signification des flags utilisés par le programme indent?

  1 # Definition des commandes 
  2 CC      = gcc 
  3 AR      = ar 
  4 RM      = rm 
  5 INDENT  = indent 
  6  
  7 # Definition des parametres 
  8 LDFLAGS = -p 
  9 CFLAGS  = -g -p -Wall -ansi -Werror
 10 ARFLAGS = -r
 11 IDFLAGS = -gnu  -bli0 -npsl -l90
 12 
 13 # Definition de la liste des librairies necesaires a l'edition de lien
 14 LDLIBS  = -L. -lhte
 15 
 16 .PHONY: all clean realclean
 17 
 18 stat : main.o count.o libhte.a
 19         $(CC) $(LDFLAGS) main.o count.o -o stat $(LDLIBS) 
 20 
 21 libhte.a : hte.o dico.o dejavu.o namealloc.o
 22         $(AR) $(ARFLAGS) libhte.a hte.o dico.o dejavu.o namealloc.o 
 23 
 24 main.o: 
 25 count.o:
 26 hte.o:
 27 dejavu.o: 
 28 namealloc.o: 
 29 
 30 all: clean stat
 31 
 32 clean:
 33         $(RM) *.o *.a *.out *~ 2> /dev/null || true
 34 
 35 realclean: clean
 36         $(RM) stat 2> /dev/null || true
 37 
 38 indent:
 39         $(INDENT) $(IDFLAGS) *.c *.h