Introduction

Nous allons aborder un petit exercice de style auquel de nombreux informaticiens se sont livrés sur les sièges des facs et écoles. L'implémentation de listes doublement chaînées.

Cependant, nous allons tenter d'approcher le problème de la manière la plus générique qui puisse être et de favoriser l'aspect « composant » dont beaucoup d'éditeurs nous vantent les mérites (en particulier quand il s'agit d'acheter leurs produits).

Si la logique de la réutilisation est très importante, elle ne dépend pas d'un produit ni d'un langage spécifique. Elle dépend avant tout de la conception, phase de plus en plus délaissée au profit du « prêt-à-porter ».

Aussi, tant pis pour les adorateurs des langues « objet » et pour prouver mes dires, je ne parlerai qu'en C.

Principe des listes chaînées

Une liste chaînée est une des structures de base dans l'organisation des données.

Il s'agit d'organiser des données séquentiellement en conservant le maximum de souplesse possible quand à la gestion des objets de la liste et ce sans pour autant avoir de mauvaises performances.

Les tableaux

Soit le tableau suivant:

Si l'on veut insérer l'élément D entre le C et le E, il nous faut effectuer (d'une manière explicite ou implicite) les opérations suivantes :

1) Augmenter la capacité du tableau d'un case supplémentaire :

2) Déplacer l'ensemble des éléments du tableau après C d'une case vers les indexes croissants :

(on pourra bien sur utiliser des fonctions de déplacement de blocs mémoires relativement plus rapides, mais l'idée reste la même et le temps de traitement est toujours dépendant du nombre d'éléments à déplacer)

3) Et enfin, insérer le nouvel élément :

L'opération antagoniste d'élimination d'un élément, nécessite de reproduire la même démarche à l'inverse (écrasement de D par E, puis de E par F…; puis réduction de la taille du tableau.

Il est clair que ce type d'opérations (insertion, élimination d'un élément) sur les tableaux touche l'ensemble de la structure du tableau. S'il faut s'attendre à un grand nombre de données assez volatiles, le tableau devient alors totalement inadéquate.

Notion de liste

Plutôt que de ranger les éléments dans un tableau, il est possible de les ordonner à partir de leur position en mémoire en les reliant par des flèches :

Pour rajouter un élément à un endroit donné, il n'y a alors plus qu'à modifier l'élément qui doit précéder le nouveau :

Cette organisation conserve bien l'aspect séquentiel et favorise la vitesse d'exécution lors des opérations d'insertion et d'élimination d'éléments. En contrepartie, on perd la notion d'indexation, et par voie de conséquence, l'accès direct à un élément arbitraire.

On peut constater de plus que l'aspect séquentiel des données est aussi orienté. En effet, en partant du premier élément, l'élément "A", il est possible d'accéder à n'importe quel élément de la liste. Mais, si l'on considère l'élément "J", dernier élément de notre exemple, on ne voit aucun autre élément de la liste.

Afin de permettre l'accès à tous les éléments de la liste à partir de l'un de ses éléments donné, il est nécessaire d'ajouter un lien inverse :

On parle alors de liste doublement chaînées.

Design du composant «liste doublement chaînée»

Notes préliminaires

Afin de mieux cerner le problème et de pouvoir extraire un canevas de développement, nous devons définir au plus juste l'ensemble minimal cohérent qui définira le composant.

Contraintes principales

Le composant doit permettre une organisation séquentielle de données, sans a priori sur la forme, le contenu ni la localisation de ces données.

Pas d'a priori sur la forme

La notion d'a priori sur la forme est assez importante. Plusieurs écoles entrent en conflit sur ce point.

Ecole C

La première, celle du C, est pour le moins simple : « tout ce que l'on ne connait pas est un pointeur générique (void *) ». Le passage d'un type quelconque à un pointeur générique s'effectue par déréférencement et recasting (changement de type).

La seconde école, celle des théoriciens de l'information, considère que les recastings sont des horreurs archaïques et dangereuses.
C'est un fait, il ne faut pas s'amuser à recaster tout en n'importe quoi si l'on tient à conserver une cohérence aux données.

Ecole théorique

En pratique, le C++ fournit un mécanisme bien utile : les templates. Ces derniers représentent une écriture « paramétrique ». Une classe et ses méthodes sont paramétrées par le type des données manipulées par la classe. Nous avons donc une écriture unique forçant le respect strict du typage.
Ce mécanisme est donc très intéressant, mais son implémentation en C++ laisse beaucoup à désirer dès lors que l'on se pose des contraintes structurantes fortes telles que la taille des exécutables ou leur vitesse d'exécution.
En effet, si le code est paramétrique, l'image générée par compilation ne l'est pas. La classe est réécrite de manière binaire pour chaque paramètre passé. La factorisation n'apparaît donc que dans la partie intelligible (le code source) mais pas dans la réalité binaire et ce, même si les types manipulés ont des tailles identiques et devraient être traités de la même manière.

Si la seconde école est beaucoup plus juste d'un point de vue théorique et peut éliminer quelques soucis liés au recasting, la réalité pratique nous montre un résultat fort peu rationel.

L'approche « C » est au contraire souvent tangente du point de vue théorique, mais devient incontournable dans de nombreux domaines où l'espace mémoire se compte parfois en kilo-octets. Elle requiert aussi et surtout que le programmeur sache exactement ce qu'il fait. Et c'est précisément ce que nous allons tenter de faire ici.

Pas d'a priori sur la localisation

La notion de localisation est aussi importante. Un composant « liste » ne contient pas de notion de gestion de la mémoire des données séquencées. Il ne doit donc pas s'occuper de réserver l'espace mémoire dévolu aux données, ni même s'arroger le droit de les construire ou de les détruire.
Cette activité dépasse l'oragnisation des données et nécessiterait une connaissance des données. Elle sera dévolue aux routines de gestion des données, voire à des routines d'allocation spécialisées.

Contrainte secondaire structurante

Une autre contrainte, moins nécessaire mais utile, est de supporter le multithreading.

Souvent, les listes sont référencées par un simple pointeur sur l'élément en cours (cf glib doubly linked lists). Cette construction est impropre au multi-threading dans la mesure où il est possible de générer et de consommer des éléments à plusieurs endroits en même temps. Or, en pointant directement vers un maillon de notre chaîne, rien ne nous garantit que ce maillon conserve sa place lors du traitement des données qui lui sont associées. Une solution peut être apportée en « privatisant » la structure de maillon (appelée aussi atome) et de ne laisser paraitre qu'une structure résumant l'ensemble des chaînons. La structure émergente est ici la structure « list ». Les structures de chaînon sont de type « atom ». Enfin, afin d'obtenir la meilleure isolation possible, la structure « list » est elle aussi privée. Un code utilisateur ne percevra la liste que comme un pointeur de type « list » qui ne pourra pas être déréférencé. Toutes les opérations sur les listes s'effectueront à travers l'appel à une fonction spécialisée.

Structure de données

Les notes préliminaires nous ont permis de concevoir l'achitecture globale du composant. Voyons cette structure dans le détail.

l'atome ou maillon

L'atome est la sturcture fondamentale de la liste. Un atome doit avoir les caractéristiques suivantes :

• contenir un lien vers les données à organiser
• permettre d'accéder à l'atome suivant de la liste,
• permettre d'accéder à l'atome précédent de la liste.

Les données, comme nous l'avons vu, sont inconnues. Le lien sera donc un pointeur générique.

Les atomes suivants et précédents sont aussi des pointeurs. Ce sont des pointeurs vers des atomes.

Voici donc la structure « atom » :

/* Atom structure: */
typedef struct _atom_t {
	/* pointer to previous and next atoms (NULL if respectively first or last) */
	struct _atom_t *prev;
	struct _atom_t *next;
	/* Pointer to user data: */
	void *data;
} atom_t, *patom_t;

La liste

La liste doit contenir les caractéristiques suivantes :

• pointeur sur le premier élément
• pointeur sur l'élément courant
• pointeur sur le dernier élément
• variable verrou (pour le multitreading)

En outre, on pourra ajouter les variables suivantes :

• nombre d'éléments de la liste
• un pointeur sur fonction de comparaison (fonction de tri)

Voici donc la structure « list » :

typedef struct {
	int count;
	patom_t first;
	patom_t curr;
	patom_t last;
	int	(*compare)(void *, void *);
	#ifdef __reentrant__
	pthread_mutex_t  *mp;
	#endif
} list_t, *plist_t;

L'interface

Interface de données

Comme nous l'avons évoqué plus haut, la structure de donnes n'a pas à être connue des applications clientes. Nous devons tout d'abord redifinir notre structure d'entrée, la liste, de manière non déréférensable. Il suffit pour cela de redéfinir la structure en tant que pointeur générique dans ce qui constitue le fichier d'interface (le .h), en prenant soin de positionner des marqueurs de compilation conditionnelle pour ne pas redéfinir cette structure dans le .c.

#ifndef _list_c_
typedef void *plist_t;
#endif

On définira donc la macro _list_c_ avant d'inclure le fichier d'entête dans le .c.

Les « méthodes »

Maintenant que la structure de données n'est plus accessible que comme une entité non déréférencable, il est nécessaire de définir toutes les méthodes nécessaires à l'utilisation des listes.

« Constructeur » et « destructeur »

Le fait de ne pas connaître la taille de la structure de liste implique que l'application client n'a pas la possibilité d'allouer ni de désallouer la mémoire. Ces taches sont dévolues aux constructeur et destructeurs:

plist_t list_new();
plist_t list_destroy(plist_t pl);

On les utilisera de la manière suivante:

plist_t mylist;

if (!(mylist = list_new())) {
     /* Constructor could not allocate memory for a new list */
     return 1;
}

...

if (mylist) mylist = list_destroy(mylist);

list_new

Le constructeur fonctionne comme un constructeur C++ :

list *mylist; 
if (!(mylist = new list)) {
     /* Constructor could not allocate memory for a new list */
     return 1;
}

Il est préférable de tester le retour de la fonction list_new. Ce test est d'ailleur tout aussi nécessaire (bien que rarement vu) en C++.

Comme l'indique le constructeur, aucune indication consernant la nature des données que la liste doit stocker n'est fournie. Dans la tradition du C, charge est laissée au programmeur de savoir ce que sa liste contient. On pourra au choix adopter 3 stratégies différentes :

• construire des listes homogènes (i.e. dont tous les éléments sont de type identique)
• définir un protocle de remplissage des listes pour les listes hétérogènes
• homogénéiser les éléments hétérogènes en les encapsulants dans une structure définissant le type des données ainsi qu'un nombre de méthodes communes.

list_destroy

Le destructeur list_destroy retourne un pointeur nul.
L'affectation (mylist = list_destroy(list)) a seulement pour but de prévenir toute tentation de réutiliser ce pointeur sans recréer une nouvelle liste. Elle est donc tout à fait optionnelle si l'on sait ce que l'on fait.

On voit aussi que le destructeur ne s'occupe pas de la désallocation des données. Cette opération doit être implémentée soit au niveau des « méthodes » inhérentes aux données elles-mêmes, soit au niveau d'un composant spécialisé dans l'allocation et la désallocation (comme le composant « storage » issu de la même boîte à outil que ce composant).

La liste n'est faite que pour organiser des données préexistantes, pas pour gérer ces données.

Informations sur la liste

/* number of items in the list  */
int   list_count(plist_t pl);

/* return current element       */
void *list_current(plist_t pl);

/* return current element index */
int   list_current_index(plist_t pl);

list_count

Cette fonction renvoie le nombre d'éléments contenus dans la liste passée en paramètre.

list_current

Cette fonction renvoie les données associées à l'élément courant de la liste.

list_current_index

Cette fonction renvoie l'index de la liste courante. Elle ne modifie pas la position courante. Elle recalcule cet index en parcourant la liste depuis son premier élément. Il est donc fortement recommendé de n'utiliser cette fonction que dans des cas extrêmes et seulement sur de courtes listes. Elle n'est présente que par soucis d'éxhaustivité mais elle fait perdre tous les avantages des listes chaînées par rapport aux tableaux.

Navigation

/* standard list navigation */
void *list_first(plist_t pl);
void *list_prev(plist_t pl);
void *list_next(plist_t pl);
void *list_last(plist_t pl);

list_first

Repositionne l'élément courant sur le premier maillon de la chaîne et retourne les données qui y sont associées.

list_prev

Repositionne le pointeur courant sur l'élément précédent et renvoie les données associées au nouvel élément courant.

list_next

Repositionne le pointeur courant sur l'élément suivant et renvoie les données associées au nouvel élément courant.

list_last

Repositionne l'élément courant sur le dernier maillon de la chaîne et retourne les données qui y sont associées.

Navigation complémentaire

/* Advanced motions */
void *list_moveto_i(plist_t pl, int index);
void *list_moveto_p(plist_t pl, void *data);

Ces deux fonctions ne sont présentes qu'en tant que complément. Elles sont intrinsèquement impropres à l'optimisation dans le cadre de listes chaînées.

En effet, leur calcul nécessite de passer en revue toute la chaine jusqu'à l'élément voulu. Il est en conséquence recommandé d'éviter leur utilisation trop souvent, ou encore sur des listes de grandes tailles.

list_moveto_i

Cette fonction positionne l'élément courant sur le i-ème élément de la liste et retourne les données associées.

Ce calcul étant effectué à partir du premier élément, il est recommandé d'éviter autant que possible l'utilisation de cette fonction sur de grandes listes. On préférera utiliser dans ce cas une organisation des données sous forme de tableau.

list_moveto_p

Cette fonction positionne la liste sur l'élément de la chaîne dont les données associées sont pointées par le pointeur fourni en paramètre.
Cette fonction est lente et ne garanti pas des résultats attendus dans le cas de redondances de références aux données. L'élément retrouvé dans un tel cas cas sera le premier à avoir un pointeur de données identique à celui passé en paramètre.

D'ajout / Suppression / Modifications d'élements

/* stacks and queues (LIFOs et FIFOs) */
void *list_push(plist_t pl, void * pdata);
void *list_pop_first(plist_t pl);
void *list_pop_last(plist_t pl);

/* standard add/insert/del */
void *list_add(plist_t pl, void *pdata);
void *list_insert(plist_t pl, void *pdata);
void *list_del(plist_t pl);
void *list_change(plist_t pl, void *pnew);

list_push

Cette fonction déplace la position courante en fin de liste et y ajoute un nouvel atome. Il suffit de lui passer en paramètre le pointeur vers les données à séquencer.

Si tout se passe bien, la fonction renvoie le pointeur de données. Dans le cas contraire, elle renvoie un pointeur nul.

list_pop_first

Cette fonction émule la fonction pop d'une file d'attente (FIFO, premier entré, premier sorti).

Le dernier élément de la liste est détruit et ses données sont retournées.

list_pop_last

Cette fonction émule la fonction pop d'une pile (LIFO, dernier entré, dernier sorti).

Le premier élément est détruit et ses données sont retournées.

list_add

list_add ajoute un élément à la liste après l'élément courant et positionne la liste sur ce nouvel élément.

En cas de succès le pointeur vers les données est retourné. Sinon, c'est un pointeur null.

list_insert

Insère un nouveau chaînon avant le chaînon en cours. Le nouvel élément créé devient l'élément courant.

list_del

Elimine l'élément courant de la list et renvoie le pointeur sur ses données.

list_change

Remplace le pointeur sur les données de l'élément en cours et retourne l'ancien pointeur.

Fonction de boucle

/* Fonction de boucle: */
void  list_foreach(plist_t pl, list_cbk_f callback);

list_foreach

La fonction list_foreach passe en revue les éléments de la liste. Pour chacun d'eux, elle appelle la fonction callback(void *data) en lui passant le pointeur sur les données associées.

Cette fonction pourrait être remplacée par:

	plist_t list;
	struct mydata_t *dat;
	...
	for (dat = list_first(list); dat; dat = list_next(list)) {
		callback((void *) dat);
	}

Cependant, dans un contexte multithread, cette version ne garantit pas que la structure de liste reste constante pendant toute la durée de la boucle.

C'est pourquoi la fonction list_foreach est faite. Elle pose un verrou lors de son appel et ne l'élimine qu'à sa sortie. Ainsi chaque appel à callback() assure que les données de la liste ne sont pas accédées par un autre thread.

En contrepartie, callback ne devra pas ouvrir un autre thread pour y effectuer des manipulations de cette même liste. Si cela était, un « deadlock » surviendrait car le thread fils attendrait que le tread parent libère le verrou, alors même que ce le thread parent attend la fin la fin des callbacks.

Fonctions de tri

/* Set a comparision function */
int list_compare_set(plist_t pl, list_cmp_f compare);

/* sorting functions */
void *list_min(plist_t pl);
void *list_max(plist_t pl);
int   list_sort(plist_t pl);

list_compare_set

Cette fonction fournit une fonction de comparaison à la structure de liste. La fonction de comparaison est de même type que celle passée à la fonction standard qsort.

Elle doit retourner :

• une valeur négative si premier argument est inférieur au second
• une valeur nulle si les 2 éléments sont égaux,
• une valeur positive si le pemier élement est supérieur au second.

list_min

Si une fonction de tri a été fournie à la liste, list_min extrait le pointeur de données pointant vers les données correspondant à la valeur minimale.

list_max

Si une fonction de tri a été fournie à la liste, list_max extrait le pointeur de données pointant vers les données correspondant à la valeur maximale.

list_sort

Si une fonction de tri a été fournie à la liste, list_sort réordonne les éléments en fonction de la valeur de leur contenu.

Fonctions de déverminage

/* Debug functions: */
void  list_dump(plist_t pl);
void  list_dump_callback(plist_t pl, list_cbk_f callback);

list_dump

Cette fonction affiche toutes les informations de liste et atomes sur la sortie erreur.

list_dump_callback

Cette fonction est identique à la précédente, mais appelle la fonction callback(void *data) avec les pointeurs sur données de chaque élément. Le callback permet d'effectuer un traitement sur les données, comme par exemple leur affichage sur la sortie erreur au sein même des informations

Implémentation

Le but de ce chapitre n'est pas de paraphraser le code source, mais d'examiner plus finement la méthode d'implémentation eu égard aux contraintes initiales à travers 3 exemples: list_next, _list_push_, list_min.

Notes préliminaires

Dépendances du composant list

Ce composant fait partie d'une boite à outil. Il requiert les fichiers mem.c et mem.h.

Le composant « mem » servait à l'origine à détecter les problèmes mémoire et incluait aussi quelques simplifications. La patie supervision a été refondue en une bibliothèque séparée (memdbg) et mem n'inclut maintenant que des simplifications d'écriture. Deux d'entre elles sont présentes dans le composant list:

void *mem_zmalloc(size_t s) {
	void *p;
	if ((p = mem_zmalloc(s))) memset(p, 0, s);
	return p;
}

#define mem_clean(p)	if (p) { free(p); (p) = NULL; }

test systématique des pointeurs (sanity check)

Afin d'éviter autant que faire ce peut les core dump, tout pointeur devant être déréférencé sera préalablement être testé (pointeur nul).

Un test de pointeur nul n'est pas entièrement satisfaisant car 0x0 n'est pas la seule adresse non autorisée. Cependant, quand les pointeurs sont bien gérés (initialisés à nul), les éventuels core dump ne proviennent en général que d'erreurs de programation (pointeur sur une zone mémoire ne correspondant pas à une liste, ou débordement mémoire écrasant tout ou partie d'une liste).

Le minimum est donc de s'assurer que tout pointeur utilisé a bien été préalablement initialisé. Cela ne veut pas forcément dire qu'il soit toujours nécessaire d'initialiser manuellement à 0 (NULL). En effet, dans le cas suivant:

	int *vecteur;
	if (!(vecteur = (int *) malloc(n * sizeof(int)))) {
	...

L'initialisation du pointeur est faite par malloc(). Si la mémoire est correctement allouée, vecteur pointera vers une zone réservée. Dans le cas contraire, vecteur vaudra 0.

Gestion des erreurs

Comme le composant list est un composant de bas niveau, les erreurs ne doivent pas arrêter l'application (exit()). En effet, c'est au programme utilisateur de juger si l'impossibilité de créer une nouvelle liste ou un nouvel élément de liste est un facteur rédhibitoire ou non.

Le sujet des messages d'erreur à l'usage de l'utilisateur ou du programmeur est plus difficile à décider. Plus le composant est de bas niveau, moins un message d'erreur ou d'information présente d'intérêt à la compréhension d'un mécomportement d'une application.

Plus un composant est simple et utilisé, moins il a de chance de poser de problème et moins les messages sont nécessaires.

Gestion des verouillages/déverrouillages

Dans le cadre d'un programme multithread, il est nécessaire de bloquer l'accès aux structures pour tout autres thread que celui en cours. Le verrou doit donc être posé avant d'accéder aux structures et après les tests de pointeurs.

L'opération de déverrouillage devra être effectuée avant le retour de chaque fonction.

Conventions

Le chaptire des conventions est invariablement sujet à controverses. S'il est important d'adopter une convention, ET SURTOUT DE LA RESPECTER, le choix de cette convention est à la base, totalement subjectif, quels que soient les arguments justificatifs.

Le formattage adopté ici est celui dit de « K&R » (est-il besoin de préciser l'origine de cette appellation?), que je trouve élégant (chacun son mauvais goût) et surtout concis.

Les nom des fonctions sont préfixés par « list » pour éviter les conflits de nommage des points d'entrée, pour faciliter la lecture des codes clients et surtour pour éviter de se tromper.

Les fonctions privées (i.e. non exportées) sont préfixées et suffixée par « _ » (e.g. _list_lock_).

Les pointeurs ne sont pas systématiquement préfixés par la lettre p. Aucune convention de nommage portant sur le typage ou la portée des variables n'est utilisée. Ceci ne constitue pas réellement un problème car:

• Les fonctions sont très courtes et ne présentent aucune équivoque possible
• Les variables employées ne sont que de 2 types: pointeur ou, dans de rares cas, entier
• Les variables ont toutes une portée locale

Examen de routines

list_next

Cette fonction est aussi simple que courte. Elle contient cepentdant le canevas minimal de toutes les fonctions présentes dans ce module et permet donc de le présenter:

void *
list_next(plist_t pl) {

Définition de la fonction list_next. Elle reprend son prototype à l'identique, mais ici, plist_t est entièrement défini, à savoir comme pointeur sur une structure de type list_t, alors que dans un client qui inclut le fichier d'entête list.h, plist_t est un pointeur générique void *.

Notons que le pointeur pl a ici la même valeur que la variable implicite this du C++.

La fonction retourne un pointeur générique qui pointe vers les données stockées dans le prochain chainon, ou un pointeur nul si le composant courant est le dernier.

    /* sanity check */
    if (!pl || !pl->curr || !pl->curr->next) return NULL;

La première étape est la vérification des pointeurs. Cette vérification permet d'éviter toute tentative de déréférencement d'un pointeur nul et de là, de nombre d'erreurs de segmentation.
Le test de pointeur pl->curr->next vérifie que la liste n'est pas déjà positionnée sur son dernier élément.

    _list_lock_(pl);

Avant chaque manipulation des données de la chaîne en cours, et afin de permettre une relative sécurité en environnement multithread, un verrou est posé.

Dans ce module, la fonction _list_lock n'est réellement appelée que si le symbole __REENTRANT__ est défini.

Le verrou posé par le thread en cours empèche les autres threads d'accéder (cf man pthread_mutex_lock) tant que le verrou n'est pas enlévé par le thread courant.

    pl->curr = pl->curr->next;

Cette partie de la fonction correspond au traitement réel des données. Toutes les opérations sont à considérer comme des prérequis (pré-traitements).

Ici, le traitement se borne à déplacer le pointeur sur l'élément courant vers l'élément suivant quand celui-ci existe.

    _list_unlock_(pl);

Une fois le traitement terminé, il est nécessaire de débloquer le verrou pour permettre aux autres threads d'accéder à nouveau à la liste.

    return pl->curr->data;
}

Les traitements accomplis et le verrou déloqué, il nous faut retourner le pointeur sur les données en cours.

_list_push_

_list_push_ est la fonction privée qui ajoute un élément en fin de liste. Elle ne verrouille pas la structure list car elle est appelée par plusieurs fonctions publiques qui, elles, se chargent de poser les verrous.

/* private atom push function (non locking) for internal use in higher level functions: */
void *
_list_push_(plist_t pl, void *data) {

la fonction prend en paramètre le pointeur sur list pl (équivalent de this), et un pointeur vers les données à ajouter en fin de liste. Elle renvoit ce même pointeur si l'ajout s'est bien passé, ou nul sinon.

    patom_t pa;

On définit un pointeur sur atome qui servira à créer le nouvel élément de la liste

    /* sanity check */
    if (!pl) return NULL; 

On teste ici aussi la validité du pointeur, bien que la fonction ne soit appelée que par des fonctions de manipulation de liste, qui elles-même effectuent ce test.

    if (!(pa = (patom_t) mem_zmalloc(sizeof(atom_t)))) return NULL;    

Allocation, mise à zéro et test de la zone mémoire pour le nouvel élément. Si l'allocation a échoué, on renvoie un pointeur nul.

    /* set atom data: */
    pa->data = data;
    pa->next = NULL;
    pa->prev = pl->last;

Cette étape initialise les données de l'atome (données utilisateur) et positionne le nouvel atome en fin de liste.

    /* link new atom to last list atom: */
    if (pl->last) pl->last->next = pa;

Si la liste possède déjà au moins un élement, on relie le dernier élément de la liste au nouveau.

    /* fix list: */
    pl->last = pa;
    pl->curr = pa;
    pl->count++;

Puis on met à jour les données de la liste:

• le dernier élément est maintenant le nouvel élément,
• l'élément courant est maintant le nouvel élément,
• la liste possède maintenant un élément de plus.

    /* check if the new atom is the 1st element: */
    if (!pl->first) pl->first = pa;

Si le nouvel élément est le seul de la liste, alors on fait pointer le premier élement vers le nouvel élément.

    return data;
}

Puis on renvoie le pointeur sur les données utilisateur pour signifier que tout s'est bien passé.

list_min

Cette fonction permet d'extraire les données utilisateurs représentant la valeur minimale. Cette notion implique l'existence d'une fonction de tri des données utilisateurs. Cette fonction de type homogène à celle passée à la fonction qsort doit être passée au préalable à la liste par la « méthode » list_compare_set.
On ne suppose pas ici que la liste soit triée. si elle l'était, il suffirait de rappeler le premier (ou le dernier, suivant la fonction de tri!) élément de la liste.
Comme nous l'avons vu, cette fonction ne modifie pas la position courante.

void *
list_min(plist_t pl) {

La fonction prend en paramètre le pointeur sur liste pl et retourne les données utilisateurs correspondant à la valeur minimale des données ou null si quelque chose ne va pas.

    void *pmin;
    patom_t pa;   

On définit un pointeur générique pmin qui pointera vers les données utilisateur minimales et un pointeur vers atome.

    /* sanity checks: */
    if (!pl || !pl->curr || !pl->compare) return NULL;     

On teste les pointeurs en entre : le pointeur sur la liste, le pointeur vers l'élément courant, et le pointeur vers la fonction de comparaison.
En l'absence d'élement (élément courant null), la demande n'a pas de sens et il suffit de renvoyer un pointeur nul.
De même, en l'absence de fonction de comparaison, la requête ne peut être effectuée. Un pointeur nul est encore une réponse adéquate.

    _list_lock_(pl);    

Ici encore, on doit nécessairement poser un verrou pour éviter toute modification pendant la durée de la recherche. Une modification des données pourrait induire un résultat faux, voire générer une erreur de segmentation.

 
    /* 
     * initialize pmin to 1st data, 
     * loop from second atom to end of list to check if "smaller" data found: 
     */
    for (pmin = pl->first->data, pa = pl->first->next; pa; pa = pa->next)
        if (pl->compare(pmin, pa->data) > 0) 
            /* keep this data: */
            pmin = pa->data;

Voici le gros morceau du traitement. Il s'agit d'une boucle qui passe en revue tous les éléments de la liste.

On initialise tout d'abord pmin avec les données du premier élement de la liste, puis le pointeur sur atom pa avec le deuxième élément (le premier étant déjà utilisé lors de l'initialisation de pmin).

La boucle continue tant que le pointeur pa n'est pas nul (i.e. tant qu'il reste des éléments dans la liste).

Le dernier terme du for fait passer pa à l'élément suivant.

A l'intérieur de la boucle, on teste les données utilisateurs pointées par chaque élement. Si les données sont déclarées inférieures à pmin par la fonction de comparaison, on remplace pmin par le pointeur sur les données de l'atome en cours.

    _list_unlock_(pl);

    return pmin;
}

Le traitement étant terminé, on peut enlever le verrou et renvoyer le pointeur vers les données de valeur minimale.

Limitations

Comme tout théorème, le code est basé sur des postulats. Ces postulats sont par essence des points d'achoppement fréquents car, d'une part le développeur les prend en général pour acquis et oublie de tester que les paramètres entrés s'y conforment, et d'autre part, l'utilisateur ne l'entend pas forcément de cette oreille et utilise volontiers ces cas limites.

La connaissance des limitations est un point important et permet à l'utilisateur de vérifier que le périmètre de validité du composant recouvre le périmètre de son problème.

Elle permet aussi éventuellement d'étendre les fonctionnalités du composant à la vue des besoins utilisateurs.

Cependant, il est nécessaire de garder à l'esprit que les évolutions ne doivent pas se faire au détriment de la conception du composant, ni contredire des points essentiels tels que la simplicité du code : « un programme terminé n'est pas un programme auquel il n'y a plus rien à ajouter, mais plus rien à enlever ».

Qualité des données

Le premier postulat touche à la qualité des données, ou tout du moins à la qualité de ce que le composant voit des données, à savoir, les pointeurs.

Le composant listimpose des pointeurs de données non nuls. En effet, la présence d'un pointeur nul à la place d'un pointeur vers des données est impossible, au risque d'occulter une partie des données de la liste.

Ce postulat n'est cependant pas particulèrement problématique dans la mesure où le fait de créer une liste d'éléments vides n'a, a priori, que peu d'intérêt.

Multithreading

Comme nous l'avons vu plus haut, le modèle de gestion du multithreading est imparfait et repose lui aussi sur des postulats, tels que l'atomicité du code.

Afin de généraliser et de renforcer la gestion du multithreading, on pourra exporter les fonctions de verrouillage/déverrouillage, et demander à l'utilisateur de les utiliser avant et après chaque appel aux « méthodes » du composant list.

Conclusions

Nous avons tracé les bases d'un composant générique utile et simple à utiliser dans un langage performant et concis. Nous avons tenté d'adopter une démarche rigoureuse et dans le respect de contraintes fortes, tout en identifiant les limites.

J'espère que tant la démarche que la réalisation vous aura intéressé.

Pour ma part, la rédaction de ce document m'a permis de prendre du recul vis à vis ce de code et d'y apporter quelques modifications et corrections.

Télechargement

list.c
list.h
mem.c
mem.h
Le toolbox complet (mais pas forcément tout à fait à jour...) (documentation en cours de rédaction)