Pointeurs

Le but de ce TP est de manipuler les pointeurs, il existe d’autre solutions parfois plus efficace mais elles ne seront pas discutés ici.

Rappel: size_t représente un unsigned int ou unsigned long en fonction de la plate-forme utilisé. Si ce type vous pose problème utilisez un des types unsigned de votre choix.

De la même manière, un maximum de prototypes sont écrits avec des const, pour vous habituer à les lires. Si ce const vous embête, ignorez-le !

Comme pour les TPs précédents, prévoyez des main pour tester vos fonctions.

Exercice 1

Écrire la fonction swap qui inverse la valeur de ses paramètres entiers. Cette fonction ayant été écrite en cours, il vous est demandé de ne pas la copier/coller mais bien de la réécrire tout seul.
En utilisant swap, écrire la fonction order qui s’assure que ses deux paramètres entiers sont, à la fin de l’exécution, dans l’ordre croisant.

Exercice 2

On veut écrire une fonction qui retourne en même temps le minimum et le maximum d’un tableau. On se propose d’utiliser les pointeurs pour arriver à ce résultat (vous pouvez faire le parallèle avec retourner un tableau).

Écrire la fonction void min_max(int l, int t[], int *min, int *max) telle que après l’appel min (resp. max) représentent le minimum (resp. le maximum) du tableau.

Avant de l’écrire dessinez ce que vous voulez !
En utilisant NULL, améliorer cette fonction de manière à ce qu’elle retourner que le min ou que le max.

Exercice 3

(r)Écrivez, en n’utilisant que la notation pointeur, les fonctions :

char *stpcpy(char *dst, const char *src), qui copie la chaine source dans la destination. Cette fonction retourne un pointeur sur le 0 terminal de la destination. Remarque: il s’agit d’une variante de strcpy très utile.
size_t strlen(const char *s), qui retourne la taille de la chaine s.
int strcmp(const char *s1, const char *s2), qui compare les chaines s1 et s2 et retourne un nombre négatif si s1 avant s2 dans l’ordre lexicographique, positif si s1 est après s2, zéro s’il s’agit des mêmes chaines.
char *strcat(char *s1, const char *s2), qui concatène la chaine s2 à la chaine s1 et retourne un pointeur sur s1.

Exercice 4

Écrivez la fonction array_zero qui étant donné un pointeur (char*) et un nombre d’octets, remplis ce tableau de zéro. Peut on l’utiliser avec tous les types de tableaux ? A quoi faut-il faire attention pour que cela marche.

Remarque: la même fonction avec un paramètre de type void* est définie dans string.h (ou strings.h) sous le nom de bzero. Il est cependant déconseillé de s’en servir depuis 2001, la fonction memset (cf exercice suivant) doit lui être préférée. Depuis 2008 cette fonction a été retirée de la norme.

Exercice 5

Il est enfin tant de jouer avec le type polymorphe (ou amorphe :) ) void *.

Au cas où je n’en ai pas (ou pas assez) parlé en cours. Le type polymorphe void * est compatible avec tous les types de pointeurs (en lecture comme en écriture). Il n’est cependant pas possible d’utiliser l’opérateur * sur ce type, vous ne pouvez pas ni lire ni écrire dans le néant. Vous ne pouvez pas non plus faire d’arithmétique de pointeurs sur void * puisqu’il n’y a pas de taille au néant. Mais à quoi sert-il ? Il sert a passer des arguments génériques. En général la premiere chose à faire dans une fonction qui reçoit des paramètres typés par void * est de les “transformer” en quelque chose de plus pratique, par exemple, char * voire unsigned char *. Par exemple :

void foo(void *v)
{
  unsigned char *c = v;
  c[0] = 0;
}
// Je vous l'accorde cette fonction est plus qu'inutile ...
// elle est limite dangereuse !

Écrivez les fonctions (consultez le manuel pour en savoir plus) :

void* memcpy(void *dst, const void *src, size_t len), qui copie la zone pointé par src dans dst sur len octets. Elle retourne le pointeur dst.
int memcmp(void *src, void *dst, size_t len), qui compare les zones mémoires src et dst sur une longueur maximale len. (voir strcmp).
void *memset(void *src, int c, size_t len). La fonction memset() écrit len octets de la valeur c (convertie vers un unsigned char) vers la zone de mémoire src. Cette fonction retourne son premier argument.
Bonus void swab(const void *src, void *dest, size_t nbytes). Cette fonction copie n-octets de src vers dest en permutant les octets pairs et les impairs.
Bonus Les processeurs modernes travaillent nettement plus vite sur des mots (long 32 ou 64 bits pour vos machines), proposez une variante de memset, qui tire parti de cette caractéristiques. Au final sous quelle condition cette version est plus efficace.

Exercice 6

Nous nous proposons de réaliser un allocateur mémoire simpliste (et inefficace). Un allocateur, en général, est constitué de deux fonctions une qui alloue de la mémoire (si elle est disponible), et une autre qui restitue la mémoire allouée.

Dans le cadre de l’exercice nous ajouterons des restrictions qui n’auraient pas lieu d’être dans un système généraliste. Tout d’abord la mémoire que nous allouerons sera limitée à des longs, de plus, ces entiers ne pourrons pas contenir la valeur minimale LONG_MIN (définie dans limits.h). En effet, nous nous servirons de cette valeur pour définir qu’une case mémoire est disponible. Enfin la mémoire elle même sera réservée (une fois n’est pas coutume) dans une tableau global (variable globale), nommé pool.

Définir la macro (préprocesseur) UNUSED à une valeur choisie judicieusement (LONG_MIN).
Écrire la fonction void release(long *ptr, size_t length), qui remplit la zone pointée (le tableau quoi) ptr par la valeur UNUSED.
Écrire la fonction void intialize_pool() qui initialise pool à UNUSED. Pensez à réutiliser ce que vous avez déjà écrit (et ce, sans copier/coller).
Écrire la fonction long *allocate(size_t length) qui recherche dans le tableau pool la première zone contigüe contenant au moins length UNUSED d’affilée. Si il n’existe pas une telle zone la fonction retournera NULL, sinon le pointeur vers le début de cette zone sera retourné; de plus la zone sera remplie de zéros.
Vous pourrez tester votre allocateur avec n’importe laquelle des fonctions déjà réalisés dans la feuille 1.

Pour aller plus loin, on se propose de réaliser la fonction int lower_triangular_matrix(int n, int m, long *matrix[]), qui remplira le tableau matrix par n lignes de tailles variant de 1 à m. Cette fonction retourne zéro si tout c’est bien passé autre chose sinon. Si n est supérieur à m nous répéterons des lignes de tailles m.

Pour tester cette fonction, réalisez la fonction print_lower_triangular_matrix … et testez :)