Préambule

Ce travail pratique est de loin le plus difficile que vous ayiez eu à faire depuis le début de l’année. Il fait intervenir beaucoup de notions déjà vues, telles que l’allocation dynamique de mémoire, les pointeurs de fonctions, etc. Mais en bonus il y a le généricité, qui est un concept très difficile en C. Au nom de toute l’équipe de ce cours, je vous supplie de participer activement à sa réalisation et d’aller également au libre-service pour poser des questions.

Buts

• Allocation dynamique de mémoire.
• Utilisation des tableaux.
• Utilisation de pointeurs de fonctions.
• Utilisation de void * pour la généricité.

Énoncé

En C il existe deux façons de créer des tableaux.

1. Les tableaux statiques, stockés sur la pile, qui se déclarent comme ceci:

   int size = 10;
   int tab[size];

2. Les tableaux dynamiques, stockés sur le tas, qui se déclarent comme cela:

   int size = 10;
   int *tab = malloc(size * sizeof(*tab));
   // On pourrait aussi écrire sizeof(int)

Notez comme dans les deux cas les tableaux sont de type int (un entier).

Une fois ces tableaux créés il n’est pas possible de rajouter ou d’enlever des éléments aux tableaux de façon simple. Dans ce travail pratique, il s’agit d’implémenter un type vecteur (c’est comme ça qu’ils sont appelés en général dans la plupart des librairies standards des langages “haut niveau”). Pour ce faire vous allez implémenter une structure vector, qui offre la possibilité de stocker efficacement des objets de type générique. Cette façon de faire est efficace pour le parcours du vecteur, le modifier en place, faire des opérations dessus, etc. mais n’est pas optimale si on passe plus de temps à ajouter/enlever des éléments. Cette structure aura une interface similaire à ce qui existe dans les librairies standard de la plupart des langages modernes (mais pas en C) et sera représentée par une structure de donnée de tableau dynamique (comme dans les librairies standard des langages modernes).

La structure vector

Pour ce faire, il faut déclarer une structure vector

#define VECTOR_INIT_CAPACITY 4

typedef struct _element {
    void **content; // actual content of the vector, note the '**'
    int capacity; // capacity allocated
    int length; // actual length
} element;

qui contient:

1. Un entier représentant la capacité du vecteur.
2. Un entier représentant la longueur du vecteur.
3. Un pointeur de void * contenant les données du vecteur (ça fait donc un double pointeur).

Nous voulons que le type des données soit générique, par exemple un int, un char, etc… Pour avoir cette généricité nous utiliserons le type void *. C’est un moyen en C pour que les données soient génériques, on peut mettre ce que l’on veut à l’adresse pointée par content. Cela comporte évidemment des risques car aucune vérification de type ne peut être faite.

Les fonctionnalités de vector

Puis il faudra implémenter les fonctions suivantes:

1. Une fonction vector_create() qui retourne un vecteur vide avec une capacité par défaut VECTOR_INIT_CAPACITY.
2. Une fonction vector_length(vector v) qui retourne la longueur d’un vecteur.
3. Une fonction vector_push(vector *v, void *data) qui ajoute data à la fin du vecteur et le retourne. Il faut réallouer de la mémoire si la capacité maximale a été atteinte en doublant la capacité.
4. Une fonction vector_pop(vector *v) qui retire le dernier élément du vecteur passé en argument et le retourne. Si le vecteur est vide il faut retourner NULL. Si la capacité utilisée du vecteur est le quart de la capacité courante, il faut réallouer le vecteur à la moitié de sa capacité. Si la capacité est VECTOR_INIT_CAPACITY il ne faut pas réallouer.
5. Une fonction vector_set(vector *v, int index, void *data, void (*custom_free)(void *)) qui assigne la index-ème valeur du vecteur à la valeur de data et retourne le vecteur. Si index dépasse la longueur actuelle du vecteur ou est négatif il faut retourner NULL. La fonction custom_free permettra de libérer la mémoire occupée par l’élément qui occupait précédement la case index du contenu du vecteur.
6. Une fonction vector_get(vector *v, int index) qui retourne les données contenues dans le index-ème élément du vecteur (sans le retirer l’élément du vecteur). Si index dépasse la longueur actuelle du vecteur ou est négatif il faut retourner NULL.
7. Une fonction vector_remove(vector *v, int index) qui retire l’index-ème élément du vecteur et retourne les données qu’il contient. Il faut ensuite bien penser à décaler les données du vecteur. Si index dépasse la longueur actuelle du vecteur ou est négatif il faut retourner NULL.
8. Une fonction vector_insert(vector *v, void *data, int index) qui insère data au index-ème indice du vecteur et retourne le vecteur. Il faut ensuite bien penser à décaler les données du vecteur. Si index dépasse la longueur actuelle du vecteur ou est négatif il faut retourner NULL.
9. Une fonction vector_empty(vector *v, void (*custom_free)(void *)) qui vide un vecteur, libère la mémoire (d’où le besoin de la fonction custom_free()) et le met dans le même état que s’il venait d’être créé.
10. Une fonction vector_destroy(vector *v, void (*custom_free)(void *)) qui vide un vecteur, libère la mémoire (d’où le besoin de la fonction custom_free()), met capacity, length à -1, et content à NULL.
11. Une fonction vector_print(vector *v, void (*print)(void *)) qui affiche tous les éléments contenus dans un vecteur.

Puis implémenter également trois fonctions encore un peu plus complexes syntaxiquement.

11. Une fonction vector_map(vector *v, void *(*f)(void *)) qui itère sur tous les éléments du vecteur v, applique la fonction f sur les données de chaque élément, et retourne un nouveau vecteur avec le résultat.
12. Une fonction vector_filter(vector *v, bool (*f)(void *)) applique le prédicat f sur toutes les données contenues dans les éléments d’un vecteur et retourne ceux qui le satisfont dans un nouveau vecteur. Les éléments qui ne satisfont pas le prédicat doivent être libérés.
13. Une fonction vector_reduce(vector *v, void *(*f)(void *, void *)) applique la réduction f sur toutes les élément du vecteur et retourne un élément unique (cela serait typiquement une somme).

Afin d’utiliser les fonctions vector_map(), vector_filter(), vector_reduce() vous devez écrire deux fonctions. La première, square, calculera le carré d’un élément. La seconde, is_even, vérifiera si les éléments sont pairs, et finalement sum qui fera la somme des éléments. Vous pouvez implémenter d’autres fonctions si vous le souhaitez parce que ça vous amuse.

Pour tester votre programme utilisez des entiers. Cela signifie que par exemple la fonction vector_push() s’utilisera de la façon suivante

vector v = vector_create();
int *val = malloc(sizeof(*val));
*val = 1;
v = vector_push(&v, val);
vector_free(v, free);

La gestion des erreurs

Un certain nombre de fonctions peuvent échouer (push¹, get, set, pop, …). Dans ce cas, il suffit de retourner un vecteur NULL. Cette façon de faire ne donne pas une très grande granularité aux erreurs possibles, mais est bien plus simple.

Tests

Écrivez un petit programme avec des assertions permettant de tester votre code.

En fait, si vous le souhaitez, vous pouvez commencer par écrire les tests pour chaque fonction, et petit à petit écrire le code pour que les tests passent! Cela s’appelle le “test-driven-development” en bon français.