Aller au contenu

TP — C et mémoire

Travaux pratiques · MP2I · 2021-2022 · C

Cours : Gestion de la mémoire · Tableaux dynamiques

Remarque : on a fait du OCaml récemment, vous retournez au C. Comme à chaque changement de contexte, vous allez prendre beaucoup de temps. C'est normal. Plus on alternera souvent, plus vous retrouverez vos repères rapidement.

Développement en C

Environnement

Pour ce retour au C, je vous propose d'utiliser :

  • soit votre ordinateur directement avec un éditeur de texte et gcc ou clang dans le terminal pour compiler ;
  • soit la machine virtuelle ;
  • soit, et je pense que c'est une bonne solution, directement le serveur Jupyter de la classe :
    • dans le menu en haut à droite New vous choisissez Terminal ;
    • il suffit de créer un répertoire pour votre TP et un fichier C :
      • mkdir tp10
      • cd tp10
      • touch main.c
    • ensuite, naviguez vers le fichier main.c vide dans le Jupyter, cliquez dessus et vous avez un éditeur, il suffit de faire Sauvegarder ou Ctrl-S puis de compiler.

Compilation

Pour compiler, on va directement lancer le compilateur dans le terminal. Pour cela, en tenant compte du fait que votre fichier est main.c, on pourra écrire gcc -o main main.c puis ./main pour le lancer.

Vous risquez d'avoir des programmes qui font plein d'erreurs de mémoire ou de crash. Je vous recommande donc de compiler avec la commande suivante :

gcc -Wall -Werror -g -fsanitize=address -o main main.c

Découpons cette commande :

  • gcc est le compilateur, on peut le remplacer par clang qui est plus récent ;
  • -Wall signifie qu'on active tous les avertissements (Warning) ;
  • -Werror signifie qu'on traite les avertissements comme des erreurs de compilation ;
  • -g qu'on compile avec les informations de débogage, c'est-à-dire le lien entre votre code source et l'endroit où une erreur se produit ;
  • -fsanitize=address signifie qu'on active le vérificateur d'erreurs de gestion mémoire.

Comme c'est un peu long à taper, vous pouvez tirer parti de l'historique du shell, c'est-à-dire qu'en utilisant la touche fléchée vers le haut, on retrouve la commande précédente, en appuyant deux fois, la commande qui précède la précédente et ainsi de suite. Il suffit alors d'appuyer sur la touche Entrée pour exécuter la bonne commande ainsi retrouvée.

Rendu et tests

Pas de rendu pour ce TP et pas de tests automatiques. Je vais vous demander de faire vos propres tests progressivement. La démarche sera alors d'écrire les fonctions dans votre fichier main.c et de rajouter des tests dans votre fonction main, éventuellement, ces tests seront groupés par thème dans des fonctions de tests comme dans les TP précédents.

Tableaux non statiques

On va définir ici une structure de données pour gérer des tableaux dont la taille ne sera connue qu'à l'exécution. Pour simplifier, ce seront des tableaux d'entiers int mais la méthode s'adapte naturellement pour des tableaux de n'importe quoi.

Type array

On définit le type suivant :

struct array {
    int *elements;
    unsigned int size;
};
typedef struct array array;

Un array est donc une structure qui contient :

  • un pointeur vers un tableau elements d'entiers ;
  • un entier indiquant la taille de ce tableau.

Remarque importante : quand on copie un pointeur, on copie uniquement un entier qui est l'adresse pointée. Ainsi, quand on copie un array, ce n'est finalement qu'un couple d'entiers qu'on copie. C'est pourquoi, dans la suite, on passe tous les array par valeur. C'est-à-dire que pour définir une fonction de recherche d'un élément dans un array on va écrire :

int search(array t, int x)
{
    for(int i = 0; i < t.size; i++)
    {
        if(t.elements[i] == x)
        {
            return i;
        }
    }

    return -1;
}

Quand on va appeler la fonction, on va avoir une copie de l'argument, c'est-à-dire du array, mais le tableau elements lui sera toujours à la même place. L'alternative serait de passer les valeurs array par pointeurs comme dans la variante suivante :

int search(array *t, int x)
{
    for(int i = 0; i < t->size; i++)
    {
        if(t->elements[i] == x)
        {
            return i;
        }
    }

    return -1;
}

On n'a rien à gagner au surplus de complexité induit par cela. L'unique avantage serait de permettre de modifier les paramètres de la structure passée en argument, mais on réservera ça aux fonctions qui le nécessitent.

Allocation, initialisation, libération

À l'aide de malloc et free (dans stdlib.h ; vous pouvez taper man malloc pour avoir la documentation), on vous demande :

Question 1

Écrire une fonction de prototype array array_alloc(unsigned int size) qui alloue un tableau de size entiers avec malloc et renvoie le array pointant dessus.

Conformément à ce qui est écrit au-dessus, on peut créer un array en variable locale et le renvoyer avec return, ce qui compte c'est la mémoire pointée.

Corrigé 
array array_alloc(unsigned int size)
{
    array a;
    a.elements = (int *)malloc(sizeof(int) * size);
    a.size = size;
    return a;
}

Question 2

Écrire une fonction de prototype void array_free(array t) qui libère le tableau pointé par t avec free. À partir de ce moment, on ne peut plus utiliser cette adresse sans faire d'erreurs.

Corrigé 
void array_free(array a)
{
    free(a.elements);
}

Question 3

Le tableau alloué n'est pas initialisé : écrire une fonction de prototype array array_make(unsigned int size, int def) qui alloue un tableau et initialise toutes les valeurs de celui-ci à def.

Corrigé 
array array_make(unsigned int size, int def)
{
    array a = array_alloc(size);
    for(int i = 0; i < size; i++)
    {
        a.elements[i] = def;
    }
    return a;
}

Question 4

Il est possible de mesurer le temps pris par un programme à l'aide de la commande time :

$> time ./main
./main  0.38s user 0.00s system 99% cpu 0.379 total

Comparer le temps d'exécution d'un programme qui

  • alloue puis libère 100 fois un tableau d'un million d'entiers ;
  • alloue en initialisant à 0 avec make puis libère 100 fois un tableau d'un million d'entiers.

Que peut-on en conclure ?

Explorons la libc

Il existe d'autres fonctions que malloc comme

void *calloc(size_t nmemb, size_t size);
void *realloc(void *ptr, size_t size);

qui permettent :

  • pour calloc d'allouer un tableau de nmemb membres qui sont chacun de taille size et d'initialiser les octets à 0. Cette fonction prend donc un temps linéaire en le nombre d'octets ;
  • pour realloc de déplacer en mémoire un tableau en changeant sa taille (en plus ou en moins). Si jamais il y a de la place, on ne bouge pas le tableau. C'est donc forcément plus efficace que de le faire à la main.

Ces deux fonctions sont hors programme !

Affichage, copie

Question 5

Écrire une fonction void array_print(array a) qui affiche [a1,a2,...,an] si a contient les éléments de a1 à an.

Remarque : cette fonction vous sera utile pour tester ce que vous avez fait dans la suite.

Corrigé 
void array_print(array a)
{
    printf("[");
    for(int i = 0; i < a.size; i++)
    {
        printf("%d", a.elements[i]);
        if(i < a.size - 1)
            printf(",");
    }
    printf("]\n");
}

Question 6

Écrire une fonction de prototype

void array_blit(array src, int src_start, array dst, int dst_start, int len)

qui copie len éléments depuis le tableau src à partir de l'indice src_start dans le tableau dst à partir de l'indice dst_start.

Remarque : on a déjà écrit cette fonction en OCaml, vous pouvez vous en inspirer.

Corrigé 
void array_blit(array src, int src_start,
            array dst, int dst_start, int len)
{
    for(int i = 0; i < len; i++)
        dst.elements[i + dst_start] =
            src.elements[i + src_start];
}

Implémentation d'une pile non bornée

Question 7

Écrire une fonction de prototype void array_push(array *a, int x) qui rajoute x à la fin du array a, c'est-à-dire :

  • on va allouer un nouveau array b dont le tableau contient a->size+1 éléments ;
  • on va copier les anciennes valeurs de *a dans b ;
  • écrire x ;
  • libérer *a ;
  • remplacer avec *a = b.

Remarque : on peut tout à fait écrire *a = b pour que a ait les mêmes valeurs que b en dehors de la fonction.

Rappel : pour une struct passée par pointeur, on utilise -> pour accéder aux champs. Donc a->elements et a->size ici.

Remarque : faites des tests, par exemple en créant un tableau de taille 0, en empilant les entiers de 1 à 10 et en affichant le résultat. Faites les tests avec -fsanitize=address et tout.

Corrigé 
void array_push(array *a, int x)
{
    array b = array_alloc(a->size+1);
    array_blit(*a, 0, b, 0, a->size);
    b.elements[a->size] = x;
    array_free(*a);
    *a = b;
}

// Note qu'on aurait pu proposer une interface persistante pour push/pop ainsi
// pas de pointeurs mais on renvoie le nouveau array
array array_push_2(array a, int x)
{
    array b = array_alloc(a.size+1);
    array_blit(a, 0, b, 0, a.size);
    b.elements[a.size] = x;
    // pas de raison de faire de free ici de a, c'est
    // a l'appelant de gérer.
    return b;
}

Question 8

Écrire une fonction int array_pop(array *a) qui retire le dernier élément du tableau a et renvoie sa valeur. Il faudra donc :

  • allouer un nouveau array b dont le tableau contient a->size-1 éléments ;
  • copier les anciennes valeurs sauf une ;
  • récupérer dans une variable x la valeur de la dernière case de a (parce qu'il n'est pas possible d'y accéder après l'étape suivante) ;
  • libérer l'ancien tableau ;
  • remplacer avec *a = b.
Corrigé 
int array_pop(array *a)
{
    array b = array_alloc(a->size-1);
    array_blit(*a, 0, b, 0, a->size-1);
    int x = a->elements[a->size-1];
    array_free(*a);
    *a = b;
    return x;
}

int main(void)
{
    array a = array_alloc(0);
    for(int i = 0; i < 10; i++)
        array_push(&a, i);
    for(int i = 0; i < 3; i++)
        printf("Pop %d\n", array_pop(&a));
    array_print(a);
    array_free(a);
}

Tableaux dynamiques

Question 9

Reprendre toutes les questions précédentes en changeant la structure de données pour permettre de faire des tableaux dynamiques. Il faudra ainsi avoir deux entiers : int p_size qui contiendra la taille physique en mémoire et int l_size qui contiendra la taille logique, c'est-à-dire les éléments signifiants stockés.

On fera des tests !

Corrigé 
#include <stdio.h>
#include <stdlib.h>

struct array {
    int *elements;
    unsigned int p_size;
    unsigned int l_size;
};

typedef struct array array;

array array_alloc(unsigned int size)
{
    array a;
    a.elements = (int *)malloc(sizeof(int) * size);
    a.p_size = size;
    a.l_size = 0;
    return a;
}

void array_free(array a)
{
    free(a.elements);
}

array array_make(unsigned int size, int def)
{
    array a = array_alloc(size);
    for(int i = 0; i < size; i++)
    {
        a.elements[i] = def;
    }
    a.l_size = size;
    return a;
}

void array_print(array a)
{
    printf("[");
    for(int i = 0; i < a.l_size; i++)
    {
        printf("%d", a.elements[i]);
        if(i < a.l_size - 1)
            printf(",");
    }
    printf("]\n");
}

void array_blit(array src, int src_start,
            array dst, int dst_start, int len)
{
    for(int i = 0; i < len; i++)
        dst.elements[i + dst_start] =
            src.elements[i + src_start];
}

void array_push(array *a, int x)
{
    if (a->l_size < a->p_size)
    {
        a->elements[a->l_size] = x;
        a->l_size += 1;
    }
    else
    {
        array b = array_alloc(a->l_size == 0 ? 1 : 2*a->l_size);
        array_blit(*a, 0, b, 0, a->l_size);
        b.elements[a->l_size] = x;
        b.l_size = a->l_size + 1;
        array_free(*a);
        *a = b;
    }
}

int array_pop(array *a)
{
    a->l_size -= 1;
    return a->elements[a->l_size];
}


int main(void)
{
    array a = array_alloc(0);
    for(int i = 0; i < 10; i++)
        array_push(&a, i);
    for(int i = 0; i < 3; i++)
        printf("Pop %d\n", array_pop(&a));
    array_print(a);
    array_free(a);
}

Partant d'un tableau de capacité nulle (array_alloc(0), comme dans le test), le corrigé d'origine allouait \(2 \times 0 = 0\) case puis écrivait dans b.elements[0], hors du tableau : on alloue maintenant au moins une case.