Mise en œuvre du TAD `set` à l'aide d'un tableau trié de capacité variable

Notre première mise en œuvre du type set repose sur un tableau d’entiers de capacité SET__SIZE, fixée à la compilation. Nous souhaitons réaliser une deuxième mise en œuvre où la capacité du tableau varie dynamiquement à l’exécution du progamme, en fonction de la taille de l’ensemble à représenter.

Pour cela, il est nécessaire que le tableau d’entiers dans struct set soit alloué dynamiquement. La bibliothèque standard stdlib.h fournit trois fonctions décrites en annexe.

Dans cette seconde mise en œuvre de set, la définition de struct set devient:

struct set {
  int * s;
  size_t capacity;
  size_t size;
};

où s pointe sur un tableau d’entiers alloué dynamiquement, capacity est le nombre d’entiers alloués dans la zone mémoire pointée par s et size est le nombre d’entiers stockés dans le tableau s. Cette mise en œuvre stocke la taille de l’ensemble, il n’est donc pas nécessaire d’utiliser une butée.

Allocation de la mémoire

Afin de valider les tests automatiques sur thor, l’implémentation d’un tableau trié à capacité variable doit vérifier les propriétés suivantes:

  • l’ensemble vide est tel que .size=0, .capacity=0, et .s=NULL
  • si, avant d’ajouter un élément dans le tableau, celui-ci était tel que (size == capacity), alors on réalloue le tableau de manière à doubler sa capacité si elle était non nulle, sinon fixer cette capacité à 1.
  • si, après avoir retiré un élément dans le tableau, celui-ci était tel que (size <= capacity/2), alors on réalloue le tableau de manière à ce que sa capacité devienne capacity/2 (et donc vaut 0 si capacity valait 1).
  • Invariant: le champ capacity est toujours représentatif de la taille mémoire allouée pour le tableau pointé par s

Dans l’exemple suivant, on affiche les tailles, capacités, et contenus du tableau lors de l’ajout successif de 5 éléments, puis le retrait successif de ces 5 éléments:

{ .size = 0, .capacity = 0, .s = {} }      // s is the NULL pointer
{ .size = 1, .capacity = 1, .s = {1} }
{ .size = 2, .capacity = 2, .s = {1,2} }
{ .size = 3, .capacity = 4, .s = {1,2,3} }
{ .size = 4, .capacity = 4, .s = {1,2,3,4} } 
{ .size = 5, .capacity = 8, .s = {1,2,3,4,5} }
{ .size = 4, .capacity = 4, .s = {2,3,4,5} }
{ .size = 3, .capacity = 4, .s = {3,4,5} }
{ .size = 2, .capacity = 2, .s = {4,5} }
{ .size = 1, .capacity = 1, .s = {5} }
{ .size = 0, .capacity = 0, .s = {} }      // s is the NULL pointer
  1. Justifier le stockage de la taille de l’ensemble (size) au lieu de l’utilisation d’une butée comme précédemment.

Algorithmes d’allocation

  1. Donner un algorithme prenant en compte l’allocation mémoire dans set__add qui double la capacité de s lorsqu’il est plein.
  2. Donner un algorithme prenant en compte l’allocation mémoire dans set__remove qui divise par 2 la capacité de s quand il est à moitié vide.

Libération de la mémoire

Pour que cette mise en œuvre gère la mémoire de façon satisfaisante, la mémoire allouée dynamiquement pour une struct set doit être libérée explicitement par le programme. Il faut donc mettre en œuvre la fonction:

void set__free(struct set * se);
  1. Pourquoi cette fonction n’apparaît-elle pas dans le TAD?
  2. Expliquer ce qu’il est nécessaire de libérer dans la mise en œuvre du tableau dynamique et donner le code de la fonction void set__free().

Mise en œuvre

Comme pour le tableau trié à sentinelle, cette mise en œuvre va se baser sur 3 fonctions outils:

// returns the first position p in s such that s[p]>=c
// or size if no such p exists
size_t find(int const s[], size_t size, int c);

// moves elements in s[begin..end[ to s[begin+1..end+1[
// assuming all indices are valid, s[begin] is left unchanged
void shift_right(int s[], size_t begin, size_t end);

// moves elements in s[begin..end[ tp [begin-1..end-1[
// assuming all indices are valid, s[end-1] is left unchanged
void shift_left(int s[], size_t begin, size_t end);
  1. Écrire le fichier en-tête dynamic/set_dynamic.h qui contient la définition de la structure struct set, ainsi que les prototypes des fonctions outils find, shift_left et shift_right ci-dessus.
  2. Programmer les trois fonctions outils, puis celles du type set (définies dans set/set.h) en utilisant les fonctions outils, dans le fichier dynamic/set_dynamic.c.

Test structurels

Écrire les tests structurels dans le fichier dynamic/test_dynamic_struc.c. En particulier, veuillez à tester les trois fonctions outils find, shift_left et shift_right de manière exhaustive.

Annexe

La bibliothèque standard stdlib.h fournit trois fonctions pour la gestion dynamique de la mémoire:

  • void * malloc(size_t size); alloue (au moins) size octets consécutifs dans le tas. Elle retourne l’adresse du 1er octet alloué, ou NULL si l’allocation a échoué;
  • void * realloc(void * ptr, size_t size); alloue size octets consécutifs dans le tas, si possible à partir de l’adresse ptr. Plus précisément, la fonction realloc tente de modifier la taille du bloc précédemment alloué pointé par ptr. Si ce n’est pas possible, la fonction realloc alloue size octets à une autre adresse, puis elle recopie le contenu pointé par ptr à cette nouvelle adresse, et enfin elle libère le bloc pointé par ptr. Elle retourne l’adresse du 1er octet alloué (qui peut donc être ptr ou pas). Elle renvoie NULL si la réallocation a échoué. Attention, si size vaut 0, le comportement de realloc est non spécifié.
  • void free(void * ptr); libère le bloc pointé par ptr. Celui-ci doit avoir été alloué par malloc ou realloc.

Une documentation complète est fournie par les pages de manuel malloc(3), realloc(3) et free(3). Alors que la mémoire allouée sur la pile est gérée automatiquement, toute mémoire allouée dynamiquement doit être libérée par le programme.