Résumé

Dans cette série d'articles, nous présentons le langage C. Il ne s'agit pas de réécrire les ouvrages de référence donnés en annexe, mais de donner, au travers du C, une méthode de programmation basée sur la notion d'interface.

Au fur et à mesure de notre progression, nous décrirons les éléments indispensables du langage et conduirons le lecteur à consulter les ouvrages de références. Le but poursuivi est clairement de parvenir à construire des programmes de manière segmentée.

Dans cet article, nous utilisons nos connaissances concernant les interfaces et les pointeurs pour programmer une librairie de manipulation de pile d'entiers. Cette bibliothèque utilise toutes nos connaissances et introduit quelques nouvelles notions, comme le traitement des erreurs dans les fonctions, les tableaux alloués dynamiquement et l'utilisation des assertions.

Nous allons découvrir un certain nombre de nouvelles fonctions standard au cours de cet exemple. Nous invitons le lecteur à consulter les pages de manuel de son système pour obtenir la documentation complète des fonctions avec la commande man fonction.

Les sources de cette bibliothèque sont disponibles sur http://www.erian-concept.com/pub/pile.tgz.

A titre d'information, cet article est rédigé avec Applix (www.applix.com) et corrigé avec Corrector 101 (www.machinesapiens.com) sous Linux, bien sur !

Description

Une pile est une structure de donnée assez simple qui est inspirée des piles d'assiettes. Les actions que l'on peut effectuer sur une pile sont l'empilage d'une assiette au sommet de la pile et le dépilage du sommet de la pile. Cette structure de donnée joue dans tous nos ordinateurs car elle a permis de programmer les fonctions des langages impératifs. La pile permet d'associer à chaque appel de fonctions un environnement où sont placés les arguments. Comme cet espace est alloué dynamiquement, la fonction peut être récursive. La pile des ordinateurs est implémentée par le processeur lui-même, donnant des performances optimales.

Voici les fonctionnalités que l'on attend de la bibliothèque :

ï‚· pile-créer(): retourne une nouvelle pile vide.

ï‚· pile-détruire (pile) : détruit la pile donnée en argument.

ï‚· pile-pousse (pile, élément) : place l'élément au sommet de la pile.

ï‚· élément <- pile-retire (pile) : retourne l'élément au sommet de la pile.

La réalisation en C de ces fonctionnalités va être légèrement différente en permettant un contrôle sommaire des erreurs.

Interface

A partir des fonctionnalités exposées dans la partie précédente, on peut définir une interface, c'est-à-dire la partie publique de la bibliothèque. Cette interface doit rester simple et permettre aussi un certain contrôle des erreurs.

Nous proposons l'interface suivante pour la librairie de la pile, écrite dans le fichier pile.h :

/* évite les inclusions multiples */
#ifndef __PILE_H
#define __PILE_H

/* type de donnée abstrait */
typedef struct Pile * Pile;

/* fonctions de la bibliothèque */
Pile pile_cree ();
int pile_detruit (Pile);
int pile_pousse (Pile, int);
int pile_retire (Pile, int *);

#endif /* __PILE_H */

Le fichier d'entête effectue un test sur __PILE_H afin d'éviter les inclusions multiples.

Cette interface est opaque au niveau de la structure de donnée, puis que nous ne savons pas à ce stade comment est composée une pile. Les données manipulées par la pile sont de type entier. Nous aurions pu définir une pile d'objets de toute nature, mais cela aurait sans doute compliqué le code.

Les fonctionnalités proposées sont élémentaires et correspondent à la création / destruction d'une pile, et à l'empilage / dépilage dans une pile. Les noms des paramètres dans les prototypes peuvent être omis ; dans ce cas, leur signification est presque évidente.

La fonction de création retourne la valeur 0 en cas d'échec ; sinon, elle retourne une nouvelle pile. Les autres fonctions retournent zéro en cas d'erreur, et 1 dans les autres cas.

La fonction pile_retire place le sommet de la pile à l'adresse pointée par élément, qui ne doit pas être nul et pointer vers une adresse d'entier valide.

Implémentation

Préliminaires

L'interface de la bibliothèque va nous guider dans la programmation de la bibliothèque. Dans les entreprises de grande taille, la définition des fonctionnalités, la définition des interfaces et la programmation des bibliothèques peuvent être effectuées par des personnes différentes. Chacune de ces étapes donne en général lieu à un rapport intermédiaire.

La bibliothèque commence par définir une macro l'identifiant. C'est une convention dont nous avons l'habitude est qui est parfois utile pour définir des fichiers d'entêtes spécifiques ; de plus, elle permet d'identifier le fichier lorsqu'il est ouvert.

Nous avons aussi l'inclusion des entêtes dont nous aurons besoin dans le corps de la bibliothèque. En général, les inclusions sont faites au fur et à mesure des besoins. Nous avons :

#define __PILE_C

#include <assert.h>
#include <pile.h>
#include <stdlib.h>

Type de données

Dans le fichier d'entête pile.h, nous avons défini un type de donnée abstrait Pile comme étant un pointeur sur une structure Pile. Maintenant, nous allons définir la structure correspondante :

typedef struct Pile {
int * tableau; /* tableau d'entiers */
int taille; /* taille du tableau */
int position; /* position dans le tableau */
} _Pile;

/* incrément de la taille du tableau */
#define PAS 100

La structure de donnée Pile contient un pointeur sur un entier appelé tableau, et deux entiers taille et position. Le champ tableau sera le tableau contenant la pile d'entiers, taille en sera sa taille, et position sera la position dans le tableau du sommet de la pile.

Nous avons besoin d'une explication pour comprendre comment un pointeur sur un entier peut être un tableau d'entiers.

Dans les articles précédents, nous avons vu comment déclarer un tableau d'entiers avec la déclaration :

int x[5];

Cette déclaration déclare un tableau de 5 entiers appelé x. Pour accéder au n^ième élément du tableau, en écriture puis en lecture, nous avons :

/* déclaration du tableau */
int tableau[5];

/* accès en écriture */
tableau[0] = 0;
tableau[4] = 4;

/*accès en lecture */
printf ("Premier: %d,Dernier: %d, x: %x\n",
tableau[0], tableau[4], tableau);

La mémoire, au moment de l'affichage pourrait ressembler à :

Adresse	Variable	Contenu
100	tableau	0
101		?
102		?
103		?
104		4
105		?

Dans ce cas, nous aurions l'affichage :

Premier: 0, Dernier: 4, tableau: 100

Nous rappelons que la valeur des adresses peut changer à chaque exécution du programme, en fonction de l'emplacement où il est placé en mémoire.

Nous avons aussi vu dans un autre article comment obtenir l'adresse d'une variable:

/* pointeur vers un entier */
int * pointeur;
/* entier */
int variable;

variable = 123;

/* le pointeur pointe maintenant sur la
* variable */
pointeur = & variable;
* pointeur = 456;
printf ("Variable: %d, &variable: %x\n",
variable, & variable);
printf ("Pointeur: %d, &pointeur: %x\n",
pointeur, & pointeur);

Nous savons qu'au moment de l'affichage, variable vaut 456, avec un plan possible de la mémoire comme :

Adresse	Variable	Contenu
100	pointeur	102
101		?
102	variable	456
103		?
104		4
105		?

Nous aurions l'affichage :

Variable: 456, &variable:102
Pointeur: 102, &pointeur: 100

Nous avons aussi vu comment allouer dynamiquement de la mémoire et placer le résultat de cette allocation, une adresse, dans un pointeur :

int * pointeur;

/* allocation d'une zone mémoire de la
* taille d'un entier */
dynamique = malloc (sizeof (int));

/* test obligatoire */
if (! dynamique) abort();

* dynamique = 123;
printf ("*dynamique: %d, dynamique: %x\n",
* dynamique, dynamique);

Cette fois-ci, l'adresse contenue par dynamique provient d'un réservoir de mémoire géré par la fonction malloc.

Ce que nous constatons, c'est que le tableau tableau est un pointeur constant. En effet, on ne peut pas écrire tableau = malloc(...) ; le compilateur retournerait une erreur.

Si tableau est un pointeur, pouvons-nous manipuler les pointeurs comme des tableaux et écrire dynamique[0] ? La réponse est oui. Dans le dernier exemple, il est possible de remplacer *dynamique par dynamique[0].

Mais s'il est possible d'écrire dynamique[0], est-il possible d'écrire dynamique[1] ? A priori, on pense que non, mais le langage C est permissif, et la réponse est donc ou dans la mesure ou aucun contrôle de taille n'est effectué par le compilateur. Il est même possible dynamique[2], etc. En fait, on peut même écrire tableau[10] sans erreur de compilation.

Dès qu'une variable contient une adresse, comme tableau, pointeur et dynamique, il est possible d'utiliser les crochets : le compilateur calcule une nouvelle adresse en ajoutant à l'adresse de base la valeur du déplacement (en fait les choses sont légèrement plus compliquées, mais pour l'instant, ça nous suffit). Si on écrit pointeur[5], la machine prend la valeur contenue dans pointeur, 102, et ajoute 5 pour obtenir la valeur située à l'adresse 107.

Si nous utilisons un déplacement plus grand que ce qui a été alloué, nous risquons de provoquer une erreur mémoire (les fameux core dump), mais pas forcément. Ce type d'erreur est à l'origine de bien des soucis en programmation en C, car assez difficile à détecter.

Maintenant, nous savons qu'il est possible d'allouer dynamiquement un tableau d'entiers, comme dans :

int * pointeur;

/* allocation d'une zone mémoire pouvant
* contenir 5 entiers */
dynamique = malloc (sizeof (int) * 5);
if (! dynamique) abort();
dynamique[0] = 0;
dynamique[4] = 0;
printf ("Premier: %d, Dernier:%d, dynamique: %x\n",
dynamique[0], dynamique[1], dynamique);

Lors de l'affichage, nous pourrions avoir le plan mémoire suivant :

Adresse	Variable	Contenu
100	dynamique	202
...	...	...
202		0
203		?
204		?
205		?
206		4

L'affichage serait alors :

Premier: 0, Dernier: 4, dynamique: 202

La variable dynamique est bien un pointeur contenir une adresse, 202, en l'occurrence. Cette adresse à été retournée par la fonction malloc, de son réservoir de mémoire. La fonction malloc a retourné l'adresse d'une zone mémoire pouvant contenir 5 entiers. On accède à ces entiers en ajoutant un déplacement à l'adresse contenue dans la variable dynamique.

Nous sommes maintenant en mesure d'allouer le tableau d'entiers de la pile!

Création

La fonction de création est chargée de créer une nouvelle structure de type Pile, et d'allouer le tableau d'entiers de la pile. Nous avons :

/* fonction de création */
Pile pile_cree() {
/* allocation de la structure _Pile */
Pile pile = malloc (sizeof (_Pile));

if (! pile) goto Error;

/* initialisation de la structure */
pile->position = 0;
pile->taille = PAS;

/* allocation du tableau d'entiers */
pile->tableau = malloc (sizeof (int) * PAS);
if (! pile->tableau) goto Error;
return pile;

/* traitement des erreurs centralisé
* à la fin de la fonction */
Error:
if (pile) {
if (pile->tableau) free (pile->tableau);
free (pile);
}
return 0;
}

La fonction déclare une pile (un pointeur sur une structure _Pile) et alloue de la mémoire. Si l'appel à la fonction malloc échoue (ce qui signifie qu'il n'y a plus de mémoire vive à allouer), elle retourne 0, ce qui est immédiatement testé. Dans ce cas, nous utilisons l'instruction C goto que nous n'avons pas encore décrite.

L'instruction goto permet d'aller directement sur le label spécifié dans le corps de la fonction contenant le goto, ici, Erreur. Certains diront qu'il faut bannir l'instruction goto. Cela provient de l'époque où les langages procéduraux, comme Pascal ou C, ont supplanté les langages non-procéduraux comme Basic. Dans ce dernier, il n'y avait (presque) que le goto pour structurer les programmes qui devenaient parfaitement illisibles. En fait, le goto peut parfaitement être utilisé lorsque le programme devient plus lisible et plus simple que si on ne l'avait pas utilisé. Notons que le goto ne permet de faire des sauts qu'au sein de la même fonction C.

La fonction teste donc le résultat de l'allocation. S'il n'y a pas d'erreur, on initialise les champs de la structure, puis on tente d'allouer le tableau d'entiers. De la même manière, on teste le résultat de l'allocation.

Lorsque tout s'est bien passé, on retourne la pile nouvellement créée.

En cas d'erreur, il faut en général libérer toutes les zones de mémoire qui ont été allouées, fermer les fichiers ouverts, etc. Ici, nous devons simplement tester si pile est non nulle. Dans ce cas, on libère le tableau, s'il a été alloué, puis on libère la pile. Si la structure avait contenu plusieurs zones allouées, ce code aurait causé des erreurs. En effet, la zone allouée par malloc n'est pas initialisée. Les champs de la structure, juste après le malloc, contiennent des valeurs aléatoires, quasiment toujours non nulles. Il y donc un risque, dans le traitement de l'erreur, de libérer une zone non allouée, mais contenant une adresse invalide. Pour éviter cela, on initialise à zéro la zone nouvellement allouée, juste après avoir testé le retour de malloc :

Pile pile = malloc (sizeof (_Pile));

if (! pile) goto Error;

/* initialisation d'une zone mémoire à 0 */
memset (pile, 0, sizeof (_Pile));

La fonction memset(adresse,valeur,taille) remplit la zone de mémoire située à l'adresse adresse et de taille taille par des octets ayant pour valeur valeur.

Pour allouer et initialiser une zone de mémoire, on pourra aussi utiliser la fonction calloc.

Destruction

La destruction de la pile consiste à libérer les ressources allouées par la fonction de création et/ou les autres fonctions de manipulation. Ces ressources peuvent être des fichiers ouverts, ou d'autres ressources, mais en général, elles sont des zones de mémoire allouées dynamiquement. Dans le cas de la pile, il est nécessaire de libérer le tableau et la pile. La fonction de libération est donc la suivante :

int pile_detruit (Pile pile) {
/* assertion */
assert (pile && pile->tableau);

/* libération des zones allouées */
free (pile->tableau);
free (pile);
return 1;
}

Nous commençons par tester le fait que la valeur de la pile est bien non nulle. Pour cela, nous utilisons la macro assert qui termine le programme en cours si l'expression en argument retourne un résultat nul, en affichant un message d'erreur contenant le nom du fichier source et la ligne où l'erreur a été trouvée. La macro assert n'est utilisée qu'en phase de débogage, tant que les programmes ne sont pas compilés avec la définition NDEBUG. On pourra définir cette macro sur la ligne de commande du compilateur gcc en ajoutant l'option -DNDEBUG. Si NDEBUG est définie, tout ce passe au niveau du compilateur comme si les lignes contenant des assert n'avaient pas été écrites. En phase de production des programmes, on suppose que toutes les assertions sont vérifiées car le programme est bien testé.

Nous sommes donc maintenant en mesure de libérer le tableau d'entiers et la pile avec deux appels à la fonction free. Par convention, nous indiquons qu'aucune erreur n'est survenue en retournant la valeur 1.

Empilage

La fonction d'empilage fonctionne en plaçant la nouvelle valeur à empiler au sommet de la pile, après avoir vérifié qu'elle est assez grande pour contenir la valeur. Si ce n'est pas le cas, la pile est réallouée avec une plus grande taille. Nous avons :

int pile_pousse (Pile pile, int element) {
assert (pile && pile->tableau);

if (pile->position == pile->taille) {
/* la pile est trop petite */
pile->tableau = realloc (pile->tableau,
pile->taille + PAS);
if (! pile->tableau) return 0;
pile->taille += PAS;
}
/* on place le nouvel élément à la
* position courante */
pile->tableau[pile->position] = element;

/* La position courante est incrémentée */
pile->position++;
return 1;
}

Lorsque la pile est trop petite pour contenir une nouvelle valeur (lorsque pile->position est égal à pile->taille), nous utilisons la fonction standard realloc. Cette fonction prend comme argument le pointeur vers la zone en mémoire à réallouer et la nouvelle taille.

La fonction retourne soit un pointeur vers la nouvelle zone soit la valeur nulle si la mémoire est saturée. Lorsque la mémoire est saturée, nous retournons 0. Dans le cas contraire, nous plaçons la nouvelle valeur dans la pile.

Dépilage

La fonction de dépilage se contente de placer la valeur au sommet de la pile à l'adresse passée en argument et décrémente la valeur de la position courante de la pile :

int pile_retire (Pile pile, int * element) {
assert (pile && pile->tableau);
if (pile->position) {
pile->position--;
* element = pile->tableau[pile->position];
return 1;
}
else return 0;
}

La fonction de dépilage devrait être améliorée pour diminuer la taille de la pile lorsque le nombre de cellules utilisables passe sous un certain seuil. En effet, la fonction d'empilage possède la capacité d'augmenter la taille de la pile sans qu'aucune fonction ne permette d'en diminuer la taille.

Utilisation

Nous allons utiliser la pile pour programmer une petite calculatrice en notation polonaise inverse. Avec ce type de notation, on donne à la calculatrice les arguments du calcul, des entiers, puis l'opérateur arithmétique à appliquer à ces arguments. Le résultat du calcul est placé sur le sommet de la pile.

Exemple d'utilisation

Commençons par faire fonctionner le programme :

# calc
1
2
3
+
Le résultat est 6
1
-
Le résultat est -7
r
La pile est vide
+
Le résultat est 0
x
#

Dans ce test, nous empilons les valeurs 1, 2 et 3 puis nous effectuons leurs sommes. Le résultat, 6, est placé automatiquement au sommet de la pile. Puis nous empilons la valeur 1 pour ensuite effectuer une soustraction. Le résultat final -7 est affiché. La commande r permet de vider la pile. Nous effectuons ensuite l'opération d'addition, sans argument car la pile est vide ; 0 est retourné, affiché et empilé. Enfin, la commande x permet de quitter la calculatrice.

Le programme est composé de la fonction principale qui réalise la boucle de calcul, est de la fonction de calcul.

Fonction principale

La fonction principale construit tout d'abord une pile de calcul. Puis elle entre dans la boucle lisant opérateur, commandes ou entier :

#include <pile.h>
#include <stdio.h>

void main (void) {
/* entier lu */
int n;
/* buffer d'entrée */
char buffer[500];
/* la pile ! */
Pile pile = pile_cree();

if (! pile) {
printf ("Erreur: la pile ne peut pas être créée\n");
return;
}
/* boucle sans fin. Le test de terminaison
* est situé à l'intérieur */
while (1) {
/* lecture d'une commande au clavier */
gets (buffer);

/* cas selon le premier caractère */
switch (buffer[0]) {
case '+':
case '-':
case '*':
case '/':
/* opération */
n = calcule (pile, buffer[0]);
printf ("le résultat est %d\n", n);
if (! pile_pousse (pile, n)) goto Erreur;
break;

case 'r':
/* vider la pile */
while (pile_retire (pile, & n));
printf ("La pile est vide\n");
break;

case 'x':
/* quitter le programme */
if (! pile_detruit (pile)) goto Erreur;
exit (0);

default:
/* empilage d'un entier */
n = atoi (buffer);
if (! pile_pousse (pile, n)) goto Erreur;
break;
}
}

Erreur:
printf ("Une erreur est survenue. Terminé\n");
abort();
}

Dans la boucle, la fonction lit une chaîne de caractère à partir du clavier. Cette lecture est effectuée à l'aide de la fonction d'entrée standard gets qui remplit le buffer passé en argument par les caractères tapés au clavier. Notons que l'usage de cette fonction n'est pas encouragé car aucun test sur la taille du buffer n'est effectué. On préférera la fonction fgets, plus sécurisée, mais dans le cadre de cet exemple, restons avec gets, plus simple à utiliser.

Si le premier caractère de la commande située dans buffer est un opérateur arithmétique, la fonction de calcul décrite plus bas est invoquée.

Si le premier caractère est 'r', la pile est vidée, ce qui permet de réinitialiser la calculatrice.

Si le premier caractère est 'x', la pile est détruite est le programme se termine en invoquant la fonction standard exit qui permet de terminer un programme de n'importe quel endroit dans le code en retournant un code d'erreur. Le code de retour 0 indique qu'aucune erreur ne s'est produite.

Par défaut, la chaîne entrée est considérée comme un entier ; l'entier est converti en utilisant la fonction atoi (alphanumeric to integer). Notons que cette fonction ne permet pas de contrôler les erreurs ; on pourra lui préférer la fonction standard strtol.

Lorsqu'une erreur est détectée, nous utilisons l'instruction goto, très pratique dans le traitement des erreurs.

Notons que lorsque le compilateur C compile ce programme, il commence par effectuer les inclusions, puis il traite le fichier. Dans le fichier pile.h, on déclare un nouveau type de donnée nommé Pile comme étant un pointeur sur une structure de donnée. Le compilateur ne connaît rien du contenu de cette structure de donnée, mais il n'a pas besoin de plus d'information car nous n'utilisons la pile qu'au travers des fonctions de la bibliothèque, sans jamais accéder aux champs internes de cette structure. De cette manière, la bibliothèque offre une structure de donnée opaque, ce qui facilite la maintenance du code en réduisant les dépendances aux seules fonctions.

Fonction de calcul

La fonction de calcul est invoquée lorsqu'un opérateur arithmétique est entré dans la boucle. Elle attend comme argument la pile de calcul et l'opérateur entré :

int calcule (Pile pile, char op) {
int acc, n;

switch (op) {
case '+': case '-': acc = 0; break;
case '*': case '/': acc = 1; break;
}
while (pile_retire (pile, & n)) {
switch (op) {
case '+': acc += n; break;
case '-': acc -= n; break;
case '*': acc *= n; break;
case '/': acc /= n; break;
}
}
return acc;
}

La fonction initialise un accumulateur de résultat en fonction du calcul à effectuer : 1 pour la multiplication et la division, 0 pour l'addition et la soustraction. Puis elle effectue le calcul arithmétique entre chacune des valeurs dans la pile et l'accumulateur. Les résultats intermédiaires sont replacés dans l'accumulateur. Lorsque la pile est vidée, la valeur de l'accumulateur est retournée.

Compilation

Nous allons dans un premier temps créer le programme calc à partir des sources main.c, pile.c et pile.h :

# gcc -I. -o calc pile.c main.c

Cette commande construit un binaire exécutable appelé calc à partir de toutes les sources, sans distinction.

L'autre manière de compiler le programmer permet de tirer parti de la compilation modulaire.

Pour cela, nous recommençons la compilation en construisant tout d'abord la bibliothèque pile.a à partir de pile.h et pile.c :

# gcc -I. -c pile.c
# ar qc pile.a pile.o

Puis nous construisons le programme à partir de main.c et de la bibliothèque constituée de pile.h, l'interface, et pile.a, l'implémentation :

# gcc -I. -o calc main.c pile.a

Cet ensemble de taches de construction peuvent être automatisées à l'aide d'un fichier makefile et du programme make que nous décrirons ultérieurement.

Critique

La bibliothèque de pile permet de ne manipuler que des entiers. Il serait possible d'empiler des valeurs plus complexes, comme des objets. Pour cela, nous devrions modifier le type des valeurs empilées.

La bibliothèque peut augmenter la taille de la pile, mais il n'existe aucun moyen d'en diminuer dynamiquement la taille. Pour remédier à cela, il serait nécessaire de modifier la fonction de dépilage pour réallourer, le cas échéant, la taille de la pile vers une taille plus petite dès que la position courante passe en dessous d'un seuil à définir.

Pour le reste, la bibliothèque est conforme au cahier des charges, c'est-à-dire qu'elle utilise l'allocation dynamique et qu'elle est réalisée de manière parfaitement modulaire. En effet, elle comporte une bibliothèque binaire et une interface dans laquelle la structure de donnée est opaque, réduisant ainsi les dépendances avec le code utilisateur.

L'auteur

Guilhem de Wailly, directeur de la société Erian Concept, partenaire NetUltra, Idealx et Getek.

Votre interlocuteur Linux ! Support, formations, configurations, administration, développements Linux. http://www.erian-concept.com

Références

Langage C - norme ANSI
Ph. DRIX
Masson

Programmer en C++
S.C. DEWHURST et K.T. STARK
Masson

Le Langage C
B.W. KERNIGHAN et D.M. RITCHIE
Masson

Kdevel
http://samuel.cs.uni-potsdam.de/~smeier/kdevelop_new/index.html