Ce cours a pour but de montrer que la gestion de la mémoire en C(++) peut être réalisée octet par octet, indépendamment du type de donnée stockée. Ce type de programmation est fréquemment utilisé dans le cadre de la programmation générique, pour proposer des fonctionnalités qui sont indépendantes du type de données manipulées.
Utiliser ce type de programmation requiert une maîtrise fine de la mémoire et de sa gestion. Ce cours n'est qu'une introduction et ne doit pas être considéré comme suffisant pour maîtriser entièrement le concept. Nous ne voyons en particulier pas en détail les notions d'alignement des données qui sont essentielles pour maîtriser pleinement le concept.
void*¶Il existe un type particulier en C(++), permettant d'introduire de la généricité dans un programme. Tout d'abord, un exemple d'une fonction générique dans la bibliothèque standard, utilisant ce type.
Cette fonction est disponible dans la bibliothèque standard dans l'entête string.h (C) ou cstring (C++). Elle permet de recopier des données d'un emplacement à un autre, quelles que soient les données recopiées. Extrait de la page de manuel :
NAME memcpy - copy memory area
SYNOPSIS
#include <string.h> void *memcpy(void *dest, const void *src, size_t n);DESCRIPTION The memcpy() function copies n bytes from memory area src to memory area dest. The memory areas must not overlap. Use memmove(3) if the memory areas do over‐ lap.
RETURN VALUE The memcpy() function returns a pointer to dest.
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
{
int a = 6 ;
int b = 10 ;
std::printf("%d %d\n", a, b) ;
std::memcpy(&b, &a, sizeof(int)) ;
std::printf("%d %d\n", a, b) ;
}
void¶La fonction memcpy utilise un type particulier pour être générique : le type void. En anglais, void signifie rien. C'est d'ailleurs pour ça qu'une procédure (qui ne renvoie pas de valeur) a void pour type de retour. Il n'est pas possible de déclarer d'objet de type void en C(++) :
void c ;
Il est par contre possible de déclarer une variable de type void * :
void *ptr ;
Le type void * désigne une adresse générique. En effet, quelle que soit la donnée, une adresse mémoire a toujours le même format. Sur la plupart des machine modernes, il s'agit d'un nombre encodé sur 64 bits soient 8 octets (32 / 4 pour les machines plus anciennes).
std::printf("%lu\n",sizeof(void*) ) ;
std::printf("%lu\n",sizeof(int*) ) ;
std::printf("%lu\n",sizeof(double*)) ;
std::printf("%lu\n",sizeof(char*) ) ;
Le langage C(++) vous permet (à vos risques et périls) de convertir une adresse d'un type en une autre. En faisant cela, vous cassez le système de vérification de types du compilateur, et devenez responsable de la correction de votre code sur ces aspects. Un exemple (à ne pas reproduire) :
{
int itab[2] ;
double *ptr_dbl ;
itab[0] = -1 ;
itab[1] = 1 ;
ptr_dbl = (double*) itab ; //conversion de type d'adresse
std::printf("%g\n", *ptr_dbl) ;
itab[0] = 0 ;
std::printf("%g\n", *ptr_dbl) ;
itab[1] = 13 ;
std::printf("%g\n", *ptr_dbl) ;
*ptr_dbl = 5.2 ;
std::printf("%d %d\n", itab[0], itab[1]) ;
}
Ici, nous avons créé un tableau de deux entiers. Chaque entier occupe 4 octet, et la norme du C assure que les deux entiers sont stockés côte à côte en mémoire. L'espace mémoire réservé pour le tableau correspond donc à un ensemble de 8 octets consécutifs. Nous avons ensuite converti l'adresse du premier des entiers (le pointeur correspondant au tableau) en un pointeur sur un double. Le type double sert à représenter des nombres décimaux, avec une précision deux fois supérieure à celle du type float. Pour cette précision, un double occupe 8 octets.
Lorsque nous affichons *ptr_dbl, nous allons chercher dans la mémoire 8 octets (la taille d'un double étant donné que ptr_dbl est de type double*). Ces 8 octets sont ensuite interprétés comme un double selon la norme, et affichés selon cette interprétation.
Nous n'avons fait que convertir le type d'adresse. Les 8 octets sont donc partagés. Modifier le tableau d'entier ou le double poité par ptr_dbl modifie dans les deux cas les octets.
Nous allons utiliser cette idée pour proposer une implémentation naïve de memcpy. En C(++), il existe plusieurs types dont la taille fait 1 octet :
std::printf("%lu\n", sizeof(char)) ;
std::printf("%lu\n", sizeof(unsigned char)) ;
En convertissant une adresse quelconque en une adresse de type char * ou unsigned char * il est ainsi possible de manipuler les octets un par un et de recopier le nombre d'octets souhaité.
void my_memcpy(void* dest, const void* from, unsigned int octets ) {
unsigned char* c_dest = (unsigned char*) dest ;
unsigned char* c_from = (unsigned char*) from ;
for(int i = 0; i < octets; ++i) {
c_dest[i] = c_from[i] ;
}
}
{
int i1 = 12 ;
int i2 = 7 ;
double d1 = 5.3 ;
double d2 = 3.4 ;
std::printf("%d %d | %g %g\n", i1, i2, d1, d2) ;
my_memcpy(&i2, &i1, sizeof(int)) ;
my_memcpy(&d2, &d1, sizeof(double)) ;
std::printf("%d %d | %g %g\n", i1, i2, d1, d2) ;
}
Notez bien que cette implémentation est naïve et que des considérations plus subtiles doivent être utilisées pour la rendre efficace, en particulier le fait qu'aller chercher les octets un par un en mémoire est très inefficace.
Nous allons nous servir de ces concepts pour programmer un tableau dynamique générique.
typedef struct dyntab_ {
char* data ;
int taille ;
int capacite ;
int octets ;
} dyntab ;
Commençons par l'initialisation et la destruction de notre tableau dynamique. Nous choisirons comme capacité initiale un élément.
void dyntab_init(dyntab* tab, int octets) {
tab->data = (char*) malloc(octets) ;
tab->taille = 0 ;
tab->capacite = 1 ;
tab->octets = octets ;
}
void dyntab_free(dyntab* tab) {
free(tab->data) ;
}
Ajoutons ensuite le nécessaire pour faire grandir l'espace de stockage en cas de besoin. Nous choisirons comme politique d'agrandissement de doubler la capacité du tableau à chaque agrandissement.
void dyntab_grow(dyntab* tab) {
tab->capacite *= 2 ;
char* tmp = (char*)realloc(tab->data, tab->capacite*tab->octets) ;
assert(tmp) ;
tab->data = tmp ;
}
La fonction d'ajout est générique, elle ne dépend pas du type de données stockées, et prend donc en paramètre l'adresse générique où se trouvent les données à stocker.
void dyntab_push(dyntab* tab, const void* src) {
if(tab->capacite == tab->taille) {
dyntab_grow(tab) ;
}
std::memcpy(tab->data + tab->octets * tab->taille, src, tab->octets) ;
++tab->taille ;
}
De même la fonction d'accès à l'élément d'un certain indice est générique, et demande l'adresse de la zone mémoire où la valeur de l'élément doit être recopiée.
void dyntab_get(const dyntab* tab, int index, void* dest) {
std::memcpy(dest, tab->data + tab->octets * index, tab->octets) ;
}
Testons maintenant notre implémentation d'un tableau dynamique pour des entiers.
{
dyntab tab ;
dyntab_init(&tab, sizeof(int)) ;
for(int i = 0; i < 20; ++i) {
dyntab_push(&tab, &i) ;
printf("%d %d\n", tab.taille, tab.capacite) ;
}
printf("[ ") ;
for(int i = 0; i < tab.taille; ++i) {
int elem ;
dyntab_get(&tab, i, &elem) ;
printf("%d ", elem) ;
}
printf("]\n") ;
dyntab_free(&tab) ;
}
Dans le code précédent, pour tester le fonctionnement de notre tableau dynamique, nous avons écrit une petite boucle pour afficher les données du tableau. Pour éviter d'avoir à le refaire, nous aimerions doter notre tableau dynamique d'une fonction d'affichage. Essayons de la coder.
void dyntab_affiche_proto(dyntab* tab) {
printf("[ ") ;
for(int i = 0; i < tab->taille; ++i) {
void* elem = tab->data + i * tab->octets ;
printf("" /* que mettre ici ??? */) ;
}
printf("]\n") ;
}
Le problème est ici que dans la fonction d'affichage, nous avons besoin de savoir comment un élément individuel doit être affiché. Sauf que selon les données stockées dans le tableau, le procédé d'affichage est différent. Il est même possible que les données stockées ne soient pas affichables directement, par exemple si vous stockez vos propres structures dans le tableau. Nous avons donc besoin de fournir en plus à la méthode d'affichage la fonction qui réalise l'affichage d'un élément. C'est le but de la section qui suit.
En C(++), chaque fonction est compilée pour produire un ensemble d'instructions processeur. Ces instructions sont stockées dans le fichier exécutable obtenu suite à la compilation. Lorsque vous lancez le programme, ces instructions sont chargées en mémoire, et le système d'exploitation va les lire pour réaliser l'exécution de votre programme. Il commence par le main, et saute de fonction en fonction au fil des appels réalisés. Une fonction a donc une adresse en mémoire qui désigne l'endroit où se trouvent ses instructions.
int f(int i) {
return i+1 ;
}
void* ptr_f = (void*) f ;
std::printf("%p\n", ptr_f) ;
std::printf("%p\n", f) ;
La zone mémoire dans laquelle les instructions du programme est chargé n'est ni la pile, ni le tas. Cette zone est accessible en lecture uniquement, et le système d'exploitation se chargera de tuer votre programme s'il n'y accède pas correctement. La lecture est autorisée :
double* ptr_dbl = (double*) ptr_f ;
double test_d = *ptr_dbl ;
printf("%g\n", test_d) ;
L'écriture est interdite.
*ptr_dbl = 5.2 ;
std::printf("%d\n", f(2)) ;
La syntaxe d'un pointeur de fonction est définie comme suit :
<type de retour> (*<nom>)(<type param1>, <type param2>, ...)Par exemple :
int f(int i) {
return i+1 ;
}
int (*g)(int) = f ;
std::printf("%d\n", g(2)) ;
Comme n'importe quel pointeur, il est possible de changer l'adresse stockée par le pointeur. Ainsi il est possible de faire pointer g successivement sur plusieurs fonctions.
int f2(int i) {
return 2*i ;
}
g = f2 ;
printf("%d\n", g(2)) ;
g = f ;
printf("%d\n", g(2)) ;
Les pointeurs de fonction permettent en particulier de passer des fonctions en paramètre d'autres fonctions pour déterminer le comportement d'un programme générique. Un exemple de fonction de la bibliothèque standard utilisant un paramètre de ce type est la fontcion qsort. Extrait de la page de manuel correspondante :
NAME qsort, qsort_r - sort an array
SYNOPSIS
#include <stdlib.h> void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *)); void qsort_r(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *, void *), void *arg);Feature Test Macro Requirements for glibc (see feature_test_macros(7)):
qsort_r(): _GNU_SOURCEDESCRIPTION
The qsort() function sorts an array with nmemb elements of size size. The base argument points to the start of the array. The contents of the array are sorted in ascending order according to a compari‐ son function pointed to by compar, which is called with two arguments that point to the objects being compared. The comparison function must return an integer less than, equal to, or greater than zero if the first argument is considered to be respectively less than, equal to, or greater than the second. If two members compare as equal, their order in the sorted array is undefined. The qsort_r() function is identical to qsort() except that the comparison func‐ tion compar takes a third argument. A pointer is passed to the comparison func‐ tion via arg. In this way, the comparison function does not need to use global variables to pass through arbitrary arguments, and is therefore reentrant and safe to use in threads.RETURN VALUE
The qsort() and qsort_r() functions return no value.
La fonction qsort sert à trier un tableau, quel que soit son contenu, et quelle que soit la façon de comparer les éléments contenus dans le tableau.
int compare_int(const void* i1, const void* i2) {
const int* ii1 = (const int*) i1 ;
const int* ii2 = (const int*) i2 ;
return *ii1 - *ii2 ;
}
{
int tab[] = {3, 0, 1, 8, 6, 9, 4, 5, 7, 2} ;
std::qsort(tab, 10, sizeof(int), compare_int) ;
std::printf("[ ") ;
for(int i = 0; i < 10; ++i) {
std::printf("%d ", tab[i]) ;
}
std::printf("]\n") ;
}
int compare_str(const void* p1, const void* p2) {
const char** c1 = (const char**) p1 ;
const char** c2 = (const char**) p2 ;
return std::strcmp(*c1, *c2) ;
}
{
const char* tab[] = {"ludo", "mabrouka", "catherine", "jean-pierre", "said", "isabelle", "brigitte"} ;
std::qsort(tab, 7, sizeof(char*), compare_str) ;
std::printf("[ ") ;
for(int i = 0; i < 5; ++i) {
std::printf("%s ", tab[i]) ;
}
std::printf("]\n") ;
}
Nous pouvons maintenant ajouter écrire une fonction d'affichage d'un tableau dynamique, et qui prend en paramètre la fonction d'affichage d'un élément. Écrivons une fonction d'affichage pour un entier passé via son adresse générique :
void print_int(const void* p) {
const int* pi = (const int*) p ;
printf("%d", *pi) ;
}
Le type d'une telle fonction est donc : void (*)(const void*). Nous pouvons écrire la fonction d'affichage du tableau dynamique qui prend une telle fonction en paramètre. Attention pour interpréter le code qui suit, il est probablement nécessaire de réexécuter les cellules définissant le tableau dynamique plus haut, car nous avons tué l'interpréteur en tentant d'écrire à l'adresse d'une fonction.
void dyntab_print(const dyntab* tab, void (*elem_print)(const void* elem)) {
printf("[ ") ;
for(unsigned int i = 0; i < tab->taille; ++i) {
elem_print(tab->data + i * tab->octets) ;
printf(" ") ;
}
printf("]\n") ;
}
Il est maintenant temps de tester notre implémentation !
{
dyntab t ;
dyntab_init(&t, sizeof(int)) ;
for(int i = 0; i < 10; ++i) {
dyntab_push(&t, &i) ;
}
dyntab_print(&t, print_int) ;
dyntab_free(&t) ;
}
Testont désormais notre implémentation pour un autre type de taille différente.
void print_double(const void* p) {
const double* pd = (const double*) p ;
printf("%g", *pd) ;
}
{
dyntab t ;
dyntab_init(&t, sizeof(double)) ;
for(int i = 1; i < 10; ++i) {
double d = 1. / i ;
dyntab_push(&t, &d) ;
}
dyntab_print(&t, print_double) ;
dyntab_free(&t) ;
}
Les données ne sont pas rangées complètement aléatoirement dans la mémoire, et les processeurs n'accèdent en réalité pas indifféremment à chaque octet de la mémoire. Le compilateur prend bien garde à respecter ces aspects. Un exemple de ce que fait le compilateur sans nous le dire :
struct bla1 {
char c1 ;
double d ;
char c2 ;
} ;
struct bla2 {
char c1 ;
char c2 ;
double d ;
} ;
printf("%lu %lu %lu\n", sizeof(char), sizeof(double), sizeof(bla1)) ;
printf("%lu %lu %lu\n", sizeof(char), sizeof(double), sizeof(bla2)) ;
Cette bizarrerie est dûe à l'alignement. Nous ne ferons pas un cours sur le sujet, mais vous devez maîtriser ces sujet si vous souhaitez aller plus loin sur ces notions de gestion de la mémoire.