Nos allocateurs précédents proposent l’allocation d’un unique bloc d’une taille donnée.
Nous allons proposer une nouvelle interface permettant l’allocation d’un bloc mémoire d’une taille choisie, ou ce qui revient au même, de plusieurs blocs mémoire contigus.
Supposant que l’on réponde à une demande d’allocation de plusieurs blocs mémoire, disons n blocs contigus. La primitive d’allocation retourne l’adresse de début de cette zone mémoire.
Lors de la désallocation de cette zone mémoire, la primitive de désallocation reçoit cette adresse. Il lui faut pouvoir retrouver combien de blocs mémoire avaient été alloués.
Nous allons donc, lors de l’allocation, mémoriser cette information, cette valeur n, dans le bloc précédant le premier bloc.
Ainsi une demande d’allocation de n blocs va rechercher n+1 blocs libres contigus, utiliser le bloc 0 pour y mémoriser la taille n de la zone mémoire allouée, et retourner la zone mémoire constituée des blocs 1 à n.
L’allocateur amb propose l’interface suivante :
#define AMB_BLOCSIZE ... void * amb_newbloc(unsigned int nbloc); int amb_freebloc(void *bloc); int amb_init();
La fonction amb_newbloc() retourne l’adresse d’une zone mémoire de nbloc de AMB_BLOCSIZE octets.
Il s’agit de trouver une série de blocs libres contigus d’une taille donnée. Comme pour l’allocateur précédent cbl, nos séries de blocs libres contigus sont gardées dans une liste chaînée.
Deux algorithmes sont possibles :
Une fois la série de blocs libres identifiée, il s’agit de la scinder en deux parties : la zone mémoire qui sera utilisée (y compris son bloc d’entête), et le reste des blocs de la série qui forme une nouvelle série de blocs libres contigus.
Lors de la libération d’une zone mémoire, il est possible
La première solution entraîne un émiettement de la mémoire, on parle aussi de fragmentation.
La seconde solution est coûteuse, un parcours de l’ensemble des séries de blocs libres étant nécessaire.
On considère dans la suite des chaînes de caractères ascii décompréssées exclusivement composées de lettres (elles ne comportent aucun chiffre).
Une méthode primaire de compression consiste à repérer les motifs répétés dans la chaîne à compresser puis à construire une nouvelle chaîne constituée du nombre de répétitions suivi du motif. Par exemple, la chaîne :
AAAAAAAAAABABABCCD
est compressée en
10A2BA1B2C1D
Vous trouverez dans le dépôt
https://gitlab-etu.fil.univ-lille1.fr/ls4-pdc/validation_amb
du code implantant l’opération de décompression par le biais d’une fonction de prototype :
char * decompresse (char *) ;
qui prend en argument un pointeur sur une chaîne de caractères compressée et qui renvoit un pointeur sur une nouvelle chaîne de caractères non compressée.
Dans cette fonction, vous devez utiliser la fonction amb_newbloc de votre allocateur mémoire.
Nous allons maintenant utiliser cette fonction dans un filtre pour manipuler des fichiers.
Pour ce faire, on considère le format de fichier d’entrée suivant :
Le programme decompression.c dont la compilation donne un filtre (decompression) prend sur l’entrée standard un fichier au format ci-dessus et retourne sur la sortie standard pour chaque ligne compressée du fichier d’entrée, la forme décompressée.
Vous prendrez soin à ce que les chaînes de caractères décompressée déjà retournée sur la sortie standard soit désallouée avec votre fonction amb_freebloc.
Pour tester votre code, vous pouvez utiliser le fichier d’entrée decompression.input
et comparer votre sortie (en utilisant par exemple le filtre diff) avec le fichier de sortie decompression.output.