Cartouche

Barème

Règlement

La réalisation de cet exercice est assujettie aux règles en vigueur dans l’école en matière de triche et de normalisation. Tricher vous expose à de graves sanctions.

Vous devez respecter les règles de normalisation suivantes : https://git.ecole-89.com/eriizu/coding_style/src/branch/main/norm.md

Le non-respect de la norme vous fera perdre une partie ou la totalité des points qui auraient pu être acquis, sur l’ensemble du rendu.

Instructions de rendu

Respectez à la lettre les noms de fichiers et leur emplacement dans le dépôt de rendu. S’il vous est demandé de rendre un fichier nommé hello.c sans qu’un nom de dossier soit précisé : rendez un fichier hello.c à la racine de votre dépôt.

La présence d’une étoile * signifie que le nom du fichier peut être n’importe lequel dès lors qu’il porte l’extension ou l’affixe (préfixe/suffixe) demandée. Elle signifie aussi qu’il est possible de rendre plusieurs fichiers.

La présence d’une double étoile ** signifie que les fichiers peuvent être placés n’importe où dans un dossier, y compris dans des sous-dossiers.

Pensez à faire des commits et des push fréquemment. Autrement nous ne pouvons pas vous aider à retrouver vos fichiers perdus.

Fonctions autorisées et interdites

Par défaut, toute fonction système (comme write) ou fonction des bibliothèques (comme printf ou puts) sont interdites.

À chaque exercice vous sera donné une liste de fonction autorisées, le cas échéant.

Tests unitaires

Vous devez rendre un fichier de test unitaire pour chaque fonction demandée.

Correction du code source en C

Le ou les livrables de votre dépôt doivent compiler avec la commande make.

Votre Makefile doit absolument avoir les règles :

• all ;
• fclean ;
• clean ;
• re.

Avec le .PHONY approprié.

Synopsis

L’objectif de ce sujet c’est d’utiliser vos fonctions de gestion de la mémoire pour créer votre propre conteneur de données.

Ce qu’on appelle un vector, c’est rien de plus qu’un tableau accompagné de fonctions et d’une structure qui permettent :

• sa ré-allocation si on a besoin de plus de place ;
• l’insertion d’un élément en plein milieu ou au début du tableau ;
• son utilisation en toute sécurité.

Notre vector doit pouvoir fonctionner avec n’importe quel type de données, il aura besoin de stocker la taille des éléments à stocker.

Étape 1 : structure et allocation initiale

Fichiers à rendre : include/vector.h, src/{vector_create,vector_delete}.c et tests Fonctions autorisées : malloc, free

Écrivez la structure du vector.

Dedans, on a besoin :

• du pointeur de la zone mémoire allouée ;
• de la taille d’un élément ;
• de la taille allouée (en nombre d’éléments ou en octet) ;
• de la taille utilisée (en nombre d’éléments ou en octet).

Le pointeur doit être de type void *.

Implémentez les fonctions :

struct vector *vector_create(unsigned int elem_size,
			     unsigned int initial_capacity);
void vector_delete(struct vector *ve);

create doit allouer un nouveau vector avec à l’intérieur la capacité initial_capacity. La capacité ici est exprimée en nombre d’éléments.

Étape 2 : push et pop back

Fichiers à rendre : include/vector.h, src/{vector_push_back,vector_pop_back}.c et tests Fonctions autorisées : malloc, free

// envoie l'adresse à laquelle se trouve l'élément, dans le tableau ou NULL en cas d'erreur
void *vector_push_back(struct vector *ve, void *elem);
void vector_pop_back(struct vector *ve);

push_back ajoute un élément à la fin du tableau, et augmente la taille utilisée. pop_back retire un élément de la fin du tableau en diminuant la taille utilisée.

Si le tableau n’est pas assez grand pour accueillir le nouvel élément : faite une nouvelle allocation, copiez-y l’ancien contenu du tableau et ajoutez-y le nouvel élément.

La nouvelle allocation doit être suffisamment grande pour accueillir le nouvel élément en plus de ce qu’il y avait déjà dans le tableau.

Étape 3 : getters

Fichiers à rendre : include/vector.h, src/{vector_get}.c et tests Fonctions autorisées : aucune

Écrivez les getters suivants qui permettent de récupérer soit l’adresse d’un élément du vector, soit la taille ou la capacité du vector.

void *vector_get_at(const struct vector *ve, unsigned int pos);
void *vector_get_front(const struct vector *ve);
void *vector_get_back(const struct vector *ve);

// size et capacity exprimés en nombre d'éléments
unsigned int vector_get_size(const struct vector *ve);
unsigned int vector_get_capacity(const struct vector *ve);

Étape 4 : insertions

Fichiers à rendre : include/vector.h, src/vector_{push_front,pop_front,insert_at,erase_at}.c et tests Fonctions autorisées : malloc, free

La difficulté principale lorsqu’on travaille avec un tableau en C c’est l’insertion d’élément au début et au milieu du tableau.

La fonction push_front doit :

• déplacer tout le contenu du tableau vers la droite ;
• écrire le nouvel élément à la première position du tableau.

La fonction insert_at doit :

• déplacer vers la droite le contenu du tableau à partir de pos ;
• écrire le nouvel élément à la position pos.

Enfin, faites l’opération inverse avec pop_front et erase_at qui font un déplacement vers la gauche depuis :

• la 2ème case vers la 1ère dans le cas de pop_front ;
• la case pos + 1 vers la case pos dans le cas d’erase_at.

void *vector_push_front(struct vector *ve, void *elem);
void *vector_insert_at(struct vector *ve,
		       void *elem,
		       unsigned int pos);

void vector_pop_front(struct vector *ve);
void vector_erase_at(struct vector *ve, unsigned int pos);

Étape 5 : destructeur

Dans notre vector si on veut pouvoir stocker des structures dans lesquelles il y a des champs qui ont été alloués avec malloc voir même juste stocker des chaînes de caractères, on va avoir besoin d’un mécanisme pour les free.

Une façon de faire c’est de stocker une fonction de destruction dans le vector qu’il appellera dès qu’il supprime un élément.

void vector_set_destructor(struct vector *ve,
			   void (*dtor)(void *elem));

Exemple d’utilisation :

struct player {
	char *name;
	int hp;
	int ac;
};

void player_init(struct player *pl, const char *name)
{
	pl->name = strdup(name);
	pl->hp = 30;
	pl->ac = 15;
}

void player_delete_inside(void *elem)
{
	struct player *ve;

	ve = elem;
	printf("debug: freing player name %s\n", pl->name);
	free(pl->name);
}

int main(void)
{
	struct vector *ve;
	struct player pl;

	ve = vector_create(sizeof(struct player), 5);
	vector_set_destructor(player_delete_inside);
	player_init(&pl, "riri");
	vector_push_back(ve, &pl);
	player_init(&pl, "fifi");
	vector_push_back(ve, &pl);
	player_init(&pl, "loulou");
	vector_push_back(ve, &pl);
	printf("vector pop back\n");
	vector_pop_back(ve);
	printf("vector delete\n");
	vector_delete(ve);
}

Lorsqu’on exécute l’exemple :

vector pop back
debug: freing player name loulou
vector delete
debug: freing player name riri
debug: freing player name fifi

L’objectif étant à la fin de ne pas avoir de fuites mémoires.

Annexe : toutes les fonctions implémentées

struct vector *vector_create(unsigned int elem_size, unsigned int initial_capacity);
void vector_delete(struct vector *ve);

// envoie l'adresse à laquelle se trouve l'élément, dans le tableau ou NULL en cas d'erreur
void *vector_push_back(struct vector *ve, void *elem);
void vector_pop_back(struct vector *ve);

void *vector_get_at(const struct vector *ve, unsigned int pos);
void *vector_get_front(const struct vector *ve);
void *vector_get_back(const struct vector *ve);

// size et capacity exprimés en nombre d'éléments
unsigned int vector_get_size(const struct vector *ve);
unsigned int vector_get_capacity(const struct vector *ve);


void *vector_push_front(struct vector *ve, void *elem);
void *vector_insert_at(struct vector *ve, void *elem, unsigned int pos);

void vector_pop_front(struct vector *ve);
void vector_erase_at(struct vector *ve, unsigned int pos);