Abstraction des données stockées

Paramétrer le type des éléments

Nous voulons adapter nos implémentations de set pour pouvoir stocker n’importe quel type de données et non pas seulement des int. Nous pourrions par exemple vouloir stocker, des nombres flottants float, ou des types structurés, comme le type struct person suivant (le triplet (day,month,year) représente la date de naissance):

struct person {
  char * firstname;
  char * lastname;
  unsigned int year;
  unsigned char month;
  unsigned char day;
};

Une solution consiste à avoir plusieurs définitions du type struct set, par exemple (pour l’implémentation avec sentinelle):

struct int_set {
   int t[SET__SIZE];
};

struct person_set {
   struct person t[SET__SIZE];
};

Cependant, cela oblige à définir chaque fonction set__* pour chacune des deux structures ci-dessus. Ce faisant, on duplique une grande quantité de code, ce qui n’est pas souhaitable.

Le pointeur polymorphe

Nous allons donc explorer une solution basée sur un type générique qui permet de stocker aussi bien des int que des float ou des struct person dans nos ensembles. Et ceci, avec une unique implémentation des fonctions set__*.

En langage C, le type void * permet de déclarer un pointeur polymorphe (ou plutôt amorphe). Un pointeur polymorphe est compatible avec tous les pointeurs typés: int *, float *, struct person *, etc. Plus précisément, cela signifie que l’on peut affecter une valeur de type int * (ou float * ou struct person *) dans une variable de type void *. Inversement, on peut affecter une valeur de type void * dans une variable de type int * (ou float * ou struct person *). Cela permet ainsi de stocker une adresse en oubliant le type des valeurs pointées.

Le pointeur void * est notamment le type de retour et le type des paramètres des fonctions d’allocation dynamique malloc, realloc, free. L’annexe 1 présente des exemples d’utilisation d’un tel pointeur (cf. également la norme 2011 du langage C WG14 N1570).

  1. On souhaite remplacer le type int des données par void * dans les réalisations de set. Donner les nouveaux prototypes des fonctions set__add, set__remove, set__find et set_filter.
  2. Écrire une fonction is_even compatible avec le nouveau prototype de set__filter et qui indique si son paramètre (supposé pointer sur un int) est pair.
  3. Que se passe-t-il si on utilise la fonction is_even ci-dessus pour filtrer un struct set dont les données sont des struct person?
  4. Quelle contrainte sur les entiers stockés dans les set ne peut-on plus garantir suite à l’utilisation du type void *? Pourquoi?

Mise en œuvre

Commencer par poser un tag nommé withstar sur votre dépôt git. Dans la suite, nous allons modifier l’API de set. Ce tag permettra de revenir facilement à la version actuelle au besoin (correction de bugs, etc).

Changement du type des données stockées

  1. Modifier les structures de données pour qu’elles stockent des valeurs de type void * plutôt que int.
  2. Modifier également les prototypes des fonctions conformement à l’exercice précédent. Attention à modifier les prototypes des fonctions outils find, shift_left, shift_right. Mettre à jour le code afin de pouvoir compiler (NB: set__print affiche maintenant les valeurs de l’ensemble avec %p plutôt que %d).
  3. Commentez vos tests structurels (ne conserver qu’une fonction main() vide). Vous vous reposerez sur les tests structurels fournis sur thor.
  4. Mettre à jour vos tests fonctionnels de manière à pouvoir compiler votre code.

Effets de bords

Le passage du stockage d’une valeur int au stockage d’un pointeur void* a des conséquences non négligeables. Compiler les programmes problem1.c, problem2.c, problem3.c et problem4.c avec la mise en œuvre de set par la liste chaînée.

  1. Expliquer le comportement de chacun d’eux à l’aide d’un schéma de la mémoire.
  2. Quelle solution proposez-vous pour résoudre ces problèmes ?
  3. Pour quels types de données, cette solution est-elle contraignante et pourquoi?

Paramétrer le traitement des données

Afin de pallier aux problèmes précédents, il est nécessaire de transmettre à la structure de données un certain nombre d’informations concernant les données (de type void *) qu’elle va contenir :

  • une fonction permettant de comparer deux données dans la structure;

  • une fonction permettant de réaliser une copie indépendante de la donnée à l’intérieur de la structure;

  • une fonction permettant de libérer une donnée à l’intérieur de la structure.

  1. Donner les prototypes de ces 3 fonctions en C.

  2. Proposer une mise en œuvre de ces fonctions pour le type int et une mise en œuvre pour le type struct person

Rétablir le comportement attendu

On choisit finalement de placer ces fonctions dans le TAD lui-même plutôt que de les passer en paramètre.

  1. Comment paramétrer le TAD à l’aide de ces fonctions?
  2. Programmer la solution décrite dans les exercices précédents dans les trois mises en œuvre de set (voir l’annexe 2 pour les nouveaux prototypes de set__empty et set__print)
  3. Adapter vos tests fonctionnels et structurels et vérifier votre implémentation. Ajouter des tests avec des données de type struct person.

Annexe 1

Exemple d’utilisation des pointeurs void*:

struct interest {
  char * firstname;
  char * lastname;
};

void *p = NULL;

int number = 10;

struct interest identity = {"Finch", "Harold"};
struct interest * other;

p = &number;
p = &identity;

other = p;

Il y a des restrictions sur la manipulation de ce pointeur: pas d’arithmétique sur les pointeurs, pas d’opérateurs d’indirection * et ->, etc.

Annexe 2

Ci-après, les nouveaux prototypes de set__empty et de set__print pour l’implémentation avec pointeur polymorphe :

struct set * set__empty(int (*cmp)(const void*, const void*),
                        void * (*copy)(void const *),
                        void (*del)(void *));

void set__print(const struct set * se, void (*print)(void *));

  • Le prototype de set__empty permet d’initialiser la structure en mettant les pointeurs de fonctions à l’intérieur.

  • Il est attendu que la fonction cmp ait un retour un entier indiquant le résultat de la comparaison entre deux valeurs s1 et s2

    • 0 si s1 et s2 sont égaux;
    • < 0 si s1 est plus petit que s2;
    • > 0 si s1 est plus grand que s2.

    Il s’agit du même comportement que la fonction strcmp de la libc. Faire attention à ne pas écrire de code supposant que cette fonction renvoie des valeurs comme 1 ou -1.

  • Le prototype de set__print choisit de laisser libre la fonction d’affichage.

  • Pour les autres fonctions de set.h, il est demandé de ne pas leur ajouter de paramètre fonctionnel.