Mis à jour le 30 janvier 2006
TD 9

TD 9

Vendredi 28 mars 2003

On désire écrire, en C, une commande permettant de trier les lignes d'un fichier équivalente à la commande Unix sort. Toutefois, nous désirons restreindre notre commande au tri de fichiers réguliers afin pouvoir utiliser l'appel système mmap (man mmap) qui permet de référencer directement des fichiers en mémoire.

Une fois qu'un fichier est référencé en mémoire, il est possible accéder directement à son contenu via un pointeur comme s'il avait été copié dans un tableau. Les données sont effectivement copiées en mémoire lorsqu'elles sont accédées. Il existe deux modes principaux pour référencer un fichier en mémoire : le mode partagé MAP_SHARED et le mode privé MAP_PRIVATE. En mode partagé, les modifications effectuées sur la zone mémoire correspondant au fichier modifie le fichier (modulo la synchronisation) et elles sont visibles par tous les processus qui référence le même fichier en mémoire ; tout le monde partage les mêmes pages mémoire. En mode privée, une copie privée des pages est associée au processus dès que le processus modifie la zone mémoire correspondante ; les modifications effectuées en mémoire ne sont pas répercutées sur le fichier.

L'appel suivant référence en mémoire, en mode privé, nb octets du fichier accessible via le descripteur fd à partir de l'octet offset. La zone mémoire sera accessible en lecture et écriture. La valeur retournée correspond au début de la zone mémoire référençant le fichier ou vaut MAP_FAILED en cas d'échec.

      
char *start_pt =
  (char *) mmap(NULL, nb, PROT_READ|PROT_WRITE, MAP_PRIVATE, fd, offset);

Rappelons que les chaînes de caractères en C sont manipulées au moyen de pointeurs de type char * est que la fin d'une chaînes de caractères est marquée en mémoire par le caractère '\0'.

Pour compiler un programme sort dont les sources sont dans un fichier sort.c, il suffit d'exécuter make sort. Pour disposer des bonnes options de compilation, il suffit de créer un fichier Makefile contenant uniquement les lignes suivantes :
      
CC=gcc
CFLAGS=-ansi -Wall -pedantic -g

Afin de déclarer toutes les fonctions nécessaires à la réalisation de ce td inclure les directives de pré-traitement suivantes :
      
#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>
#include <fcntl.h>
#include <stdio.h>
#include <sys/mman.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
/* Taille initiale du tableau de lignes */
#define INITIAL_SIZE 10

1  Une commande sort utilisant des fichiers référencés en mémoire

Écrire une fonction C map_file qui prend en argument un nom de fichier, qui référence ce fichier en mémoire (si cela est possible) et permet de récupérer son adresse de début ainsi que la taille du fichier référencé. Afin de pouvoir modifier les données référencées en mémoire sans que ces modifications soient répercutées sur le fichier on utilisera le mode MAP_PRIVATE pour l'appel système mmap.
(corrigé)
Écrire une fonction next_line qui recherche en mémoire l'adresse de début de la ligne suivante à partir d'une adresse dans la ligne courante et jusqu'à l'adresse de fin de fichier. De plus, cette fonction devra remplacer en mémoire les caractères '\n' trouvés par le caractère '\0' afin de pouvoir utiliser les fonctions standard d'affichage et de manipulation de chaînes de caractères en C.
(corrigé)
Pour trier les lignes on utilisera la fonction qsort (man qsort) qui permet de trier un tableau contenant des données d'un type quelconque. Par exemple le programme suivant trie un tableau contenant des entiers.
      
#include <stdlib.h>
#include <stdio.h>
#define SIZE 4

int compare_int(const void *pt1, const void *pt2) {
  int a = * ((int *)pt1);
  int b = * ((int *)pt2);
  return a-b;
}
int main(int argc, char *argv[]) {
  int tab[SIZE] = {3,4,2,1};
  int i;
  qsort(tab,SIZE,sizeof(int),compare_int);
  for (i=0;i<SIZE;i++) {
    printf("%d\n",tab[i]);
  }
  return 0;
}
Écrire une fonction map_strcmp qui enveloppe la fonction de comparaison de deux chaînes de caractères C, strcmp (man strcmp), afin de pouvoir l'utiliser pour trier les lignes du fichier avec la fonction qsort.
(corrigé)
Écrire la fonction principale main réalisant le tri des lignes d'un fichier dont le nom est passé en argument. Celle-ci commence par créer un tableau de type char ** contenant toutes les lignes du fichier (attention, le nombre de lignes dans le fichier n'est pas connu à l'avance, il faudra donc utiliser les fonctions malloc et realloc), les trie en place avec la fonction qsort puis affiche toutes les lignes.
(corrigé)
Ce document a été traduit de LATEX par HEVEA