Vendredi 28 mars 2003 |
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.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.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); |
char *
est que la fin d'une chaînes de
caractères est marquée en mémoire par le caractère '\0'
.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 |
#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 |
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
.
/* Fonction auxiliaire référençant le fichier en mémoire*/ void* map_file(char* file, long* fsize) { int fd; /* Descripteur du fichier */ void* ptr; /* Début de la zone */ struct stat st; /* Attributs du fichier référencé */ /* Ouverture et récupération des attributs du fichier */ if ((stat(file, &st) != 0) || (fd = open(file, O_RDWR)) < 0) { perror("open"); return NULL; } /* Vérification que le fichier n'est pas vide */ if (st.st_size == 0) { (void) printf("%s: is empty\n", file); (void) close(fd); return NULL; } /* Récupération de la taille du fichier */ *fsize = st.st_size; /* Référencement du fichier en mémoire. On ajoute un octet à la taille du fichier pour pouvoir éventuellement ajouter le caractère '\0' en fin de fichier */ ptr = mmap(NULL, st.st_size+1, PROT_READ|PROT_WRITE, MAP_PRIVATE, fd, 0); (void) close(fd); if (ptr == MAP_FAILED) { (void) printf("%s: cannot be map\n", file); return NULL; } return ptr; } |
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.
/* Lecture d'une ligne */ char* next_line(char *start,char *end) { assert(start <= end); /* Recherche de la fin de la ligne */ while (1) { if (start==end || *start == '\n' ) { *start = '\0'; start++; return start; } start++; } } |
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; } |
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
.
/* Comparaison du contenu de deux lignes */ int map_strcmp(const void *a_pt, const void *b_pt) { char *a = *((char**)a_pt); char *b = *((char**)b_pt); return strcmp(a,b); } |
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.
/* Fonction principale */ int main(int argc, char **argv) { char *usage = "Usage: %s <file>\n"; /* Usage */ char **lines; /* Tableau de lignes */ int size = INITIAL_SIZE; /* Taille du tableau de lignes */ int n = 0; /* Nombre de lignes déjà lues */ char *line; /* Ligne courante */ long fsize; /* Taille du fichier */ char *map_start; /* Début de la zone référençant le fichier */ char *end; /* Adresse de fin du fichier initial */ int i; /* Indice de travail */ /* Vérification du nombre d'arguments */ if (argc != 2) { (void) fprintf(stderr, usage, argv[0]); return EXIT_FAILURE; } /* Allocation initiale du tableau de lignes */ lines = (char **) malloc(size * sizeof(char*)); if (lines == NULL) { fprintf(stderr,"No more memory available\n"); return EXIT_FAILURE; } /* Référencement du fichier en mémoire et récupération de sa taille */ map_start = (char *) map_file(argv[1], &fsize); if (map_start == NULL ) { fprintf(stderr, "Abort\n"); return EXIT_FAILURE; } /* Calcul du pointeur correspondant à la fin de fichier */ end = map_start + fsize; /* Lecture des lignes du fichiers */ line = map_start; do { /* Vérification qu'il y a assez de place dans le tableau de lignes */ if (n == size) { size *= 2; lines = (char**) realloc(lines, size * sizeof(char*)); if (lines == NULL ) { fprintf(stderr, "Abort\n"); return EXIT_FAILURE; } } lines[n] = line; n++; } while ((line = next_line(line,end)) < end); /* Trier les lignes. */ qsort(lines, n, sizeof(char*), map_strcmp); /* Afficher les lignes triees. */ for (i = 0 ; i < n ; ++i) { printf("%s\n",lines[i]); } (void)fflush(stdout); if (munmap(map_start,fsize) < 0) { perror("munmap"); return EXIT_FAILURE; } return EXIT_SUCCESS; } |
Ce document a été traduit de LATEX par HEVEA