D3:EPITA:Atelier:C:TP:2013:2014
Sommaire
Vecteurs chaînées
Dans cet exercice nous allons mettre en œuvre une structure de données mélangeant vecteurs et listes chaînées.
La structure de données ressemble à la chose suivante:
#define BASE_SIZE 256 struct chain_vector { struct chain_vector *next; size_t size; int tab[BASE_SIZE]; };
Une cellule de cette structure contient un tableau et le nombre d'élément dans ce tableau (ce qu'on a dans un vecteur classiquement) et un pointeur sur la cellule suivante. Les données dans le tableau sont triées dans l'ordre croissant et les cellules également.
Recherche d'une valeur
Dans un premier temps nous allons écrire les fonctions de recherche (test de présence) dans notre structure.
Nous commencerons par la recherche dans la cellule courante. Cette fonction sera réutilisée pour l'insertion. Nous allons donc adopter une approche moins classique: la fonction renverra vrai (différent de 0) si l'élément est présent, mais en même temps renverra la position de l'élément via un pointeur. Si l'élément n'est pas présent, la fonction renverra faux et mettra dans le pointeur la position d'insertion (c'est à dire la position du plus petit élément supérieur à l'élément cherché.) Si l'élément cherché est plus grand que le dernier élément du tableau, la fonction donnera comme index la taille (nombre d'élément) du vecteur courant.
Les tableaux sont triés, il est donc judicieux d'utiliser une dichotomie et évuentuellement de vérifier que l'élement se trouve bien dans l'interval des valeurs du tableau avant de le chercher.
int local_find(struct chain_vector *v, int x, int *pos);
Il ne reste plus que la fonction de recherche principale: elle va parcourir l'ensemble des cellules tant que l'élément recherché n'est pas trouvé. Cette fonction ne renvoie que vrai ou faux.
int find(struct chain_vector *v, int x);
Insertion
Pour l'insertion, nous devons:
- chercher la position d'insertion
- décaller le contenu du tableau
- mettre l'élément à insérer à sa place
Il faut également gérer les cas suivants:
- lorsque le tableau de la cellule courante est pleine, il faut transférer l'élément de fin dans la cellule suivante (il s'agit simplement d'une autre insertion.)
- lorsque la cellule est la dernière de la liste, il faut prévoir de créer une nouvelle cellule et plutôt que d'attendre que la dernière cellule soit pleine, on va créer une nouvelle cellule dès que la moitié de la capacité est atteinte.
- si l'élément à insérer est déjà présent, la fonction ne fait rien.
void insert(struct chain_vector *v, int x);
cat(1)
La commande cat est un outil de base sous Unix. Sans option, elle affiche sur la sortie standard le contenu des fichiers listés sur sa ligne de commande. Nous allons faire notre propre version.
- Écrire la fonction mycat(fd) qui à partir du file descriptor fd (ouvert en lecture), affiche le contenu du fichier sur la sortie standard (STDOUT_FILENO):
void mycat(int fd);
Vous devrez, bien sûr gérer les erreurs en utilisant errno(3) et perror(3) comme vu en cours.
- Écrire le programme complet (on nommera le binaire mycat aussi)
mycat (le programme) devra ouvrir les fichiers qui lui sont passés sur la ligne de commande (un par un, dans l'ordre.) De plus, si le (un des) nom(s) du fichier passé en paramètre est - (juste le caractère moins), mycat affichera le contenu de l'entrée standard (STDIN_FILENO) jusqu'à la fin de fichier (cf le cours sur read(2).)
- Effectuer quelques tests de performance (voir time(1)) sur votre programme en changeant le nombre de caractères lus dans la boucle principale.
file splitter
Un file splitter est un programme qui divise un fichier en plusieurs bout de tailles données (en général pour les distribuer sur des médias de taille fixe comme des disquettes … )
En gros, le programme prend un nom de fichier f et une taille t et engendre taille(f)/t fichiers (plus 1 au besoin.)
La fonction suivante produira les noms des fichiers:
char *produce_next_name(char *pref) { static char *name = NULL; static char c1 = 'a', c2 = 'a'; static int pos; if (!name) { name = malloc(strlen(pref) + 4); pos = strlen(pref) + 1; strncpy(name, pref, strlen(pref)); name[pos-1] = '.'; } name[pos] = c1; name[pos+1] = c2++; if (c2 > 'z') { ++c1; //handle no more than 26*26 blocks c2 = 'a'; } return name; }
Elle s'utilise relativement simpement: on l'appelle avec un nom de fichier et elle renvoie une chaîne où un nouveau suffixe (de la forme aa, puis ab … ) est ajouté. On notera que le paramètre n'est utilisé que la première fois et que la chaîne est en fait toujours au même endroit (donc pas de free(3) sur le résultat.)
Le bout de code suivant fait une démonstration de cette fonction:
int main() { for (int i=0; i < 27; ++i) printf("%s\n",produce_next_name("pref")); return 0; }
- Écrire le programme mysplit qui prend sur la ligne de commande un nom de fichier et une taille et split le fichier en sous fichier de la taille donnée. On notera que même si le fichier est de taille inférieure, un nouveau fichier est produit.
lseek(2)
L'objectif ici est de manipuler l'appel système lseek(2). Tout d'abord, voici un programme qui génère un fichier avec l'alphabet de base (ce qui nous offrira un bon référent pour lire à une position précise.)
/* genfile.c : generate alphabetical file for testing */ #include <stdlib.h> #include <unistd.h> #include <string.h> #include <fcntl.h> #include <stdio.h> static inline void build_alpha(char *buf) { for (char c = 'a'; c <= 'z'; ++c, ++buf) *buf = c; } static inline void build_spec_range(char *buf, char start, char end) { if (start <= end) for (; start <= end; ++start, ++buf) *buf = start; } /* * usage: * * no param: out alpha on stdout * * first param is the filename (if at least one parameters) * * second and third define the interval (both needed) */ int main(int ac, char* av[]) { int fd = STDOUT_FILENO; char *buf; if (ac > 1) if ( (fd = open(av[1],O_WRONLY|O_CREAT|O_TRUNC, 0666)) == -1 ) { perror(av[0]); exit(3); } if (ac > 2) { char start, end; if (ac < 4) { write(STDERR_FILENO, av[0], strlen(av[0])); write(STDERR_FILENO,": missing parameter\n",20); exit(2); } start = av[2][0]; end = av[3][0]; if (end < start) { write(STDERR_FILENO, av[0], strlen(av[0])); write(STDERR_FILENO,": parameters mismatch\n",22); exit(2); } buf = malloc(1 + end - start); build_spec_range(buf, start, end); write(fd, buf, 1 + end - start); } else { buf = malloc(26); build_alpha(buf); write(fd, buf, 26); } write(fd,"\n",1); if (ac > 1) close(fd); return 0; }
- Écrire la fonction pos_char(fd, p) qui à l'aide de lseek(2), lit le caractère à la position p dans le fichier (les positions commencent à 0.):
char pos_char(int fd, int p);
- Écrire le programme complet (seek) qui prend un nom de fichier et une position (sous forme de caractère) et affiche le caractère à la position donnée dans le fichier (n'oubliez pas la gestion des erreurs.)
On ne gère que 26 positions de a à z, pour pouvoir faire le genre de tests décrits plus loin.
Notre programme s'utilise:
$ genfile test_file # generate test file $ ./seek test_file j j $
- Pour aller plus loin: écrire une variante où la position est indiquée vis à vis de la fin du fichier.
lstat(2) : information sur les fichiers
Le but de <tt>lstat(2) est d'obtenir des informations sur les fichiers (existence, taille, type, permissions … )
- Écrire un programme qui prend sur sa ligne de commande un nom de fichier, teste son existence et affiche s'il existe son type (voir le man) et sa taille (pour les fichiers standard)
Lorsque le fichier est présent, on utilisera le format suivant (une ligne en exemple pour chaque type de fichier):
regular file: taille directory character device block device FIFO symbolic link socket
Pour cette exercice printf(3) est autorisé.
Dans le cas d'une erreur, on utilisera l'affichage via perror(3) comme habituellement.
Format BMP
Nous allons travailler avec le format de fichier (l'une des versions) BMP.
Le format est relativement simple et correspond à une structure C dumpée dans un fichier.
Les définitions suivantes correspondent aux en-têtes (il y en a 2 par fichier) d'un fichier BMP.
struct s_bmp_img_head { unsigned int header_size; unsigned int width; unsigned int height; short int planes; short int bit; unsigned int comp_method; unsigned int image_size; int hres; int vres; unsigned int color_number; unsigned int important_color; }; struct s_bmp_header { short padding; char magic[2]; unsigned int file_size; unsigned int reserved; unsigned int offset; struct s_bmp_img_head dib; unsigned char data[4]; }; typedef struct s_bmp_header *bmp;
La structure struct s_bmp_header décrit l'en-tête principal du fichier, le premier champ sert juste à assurer l'alignement sur 32 bits. Normalement, le champ offset permet de déterminer la taille du second en-tête, cette taille permet de savoir quelle version du format BMP est utilisée. Dans notre cas, nous supposerons que le fichier utilise le format le plus répandu (24bits, pas de compression … )
Enfin, le tableau data à la fin permet d'avoir accès simplement aux données de l'image (celles-ci se trouvent immédiatement après les en-têtes.)
Pour l'ouverture et le chargement, vous aurez besoin de open(2) et d'une fonction comme lstat(2) pour déterminer la taille du fichier.
L'objectif est de faire une ouverture avec le support en lecture et en écriture, on va modifier l'image chargée.
- Ecrire une fonction qui prend un nom de fichier en argument, l'ouvre avec open(2) et utilise mmap(2) pour charger le contenu du fichier en mémoire.
Une fois l'image ouverte, vous allez pouvoir faire des traitements pixels par pixels. Le seul détail important à noter est que les lignes de l'image sont alignées sur un multiple de 4 octets et donc, si la longueur de la ligne n'est pas un multiple de 4, il y aura des 0 pour combler avant le début de la ligne suivante.
- Écrire une fonction de conversion en niveau de gris des pixels. Cette fonction devra modifier les pixels en place.
Penser à fermer l'image et à rendre les pages obtenues via mmap(2).
Pour finir vous pourrez englober tout ça dans un programme de test.
