Retrouvez cet article dans : Linux Magazine 86

Les listes chaînées, au même titre que les tableaux dynamiques, permettent de stocker des listes de données. Disséquons la bibliothèque Glib pour voir comment elle en implémente la gestion.

Introduction

Lorsque vous souhaitez stocker une liste de données, vous disposez de plusieurs possibilités. La première que les apprentis programmeurs découvrent est le tableau statique :

int data[10];

Très vite, ils ressentent le besoin d’avoir une liste dynamique, que l’on peut étendre à volonté. Avec malloc(), il est facile de créer un tableau de taille variable :

int *data;
data = malloc (n * sizeof (*data));

Le problème de ce tableau est qu’une fois la taille déterminée et le tableau créé, il ne peut plus changer de taille (ce qui est d’ailleurs inexact avec un realloc() bien utilisé). Aussi, si vous souhaitez insérer une donnée au milieu des autres, vous allez devoir coder un peu pour décaler les données et faire un trou pour la nouvelle.

glib

Dans les sources de glib, nous allons nous intéresser aux fichiers glib/glist.c et glib/glist.h. Remarques: Cet article est basé sur la version 2.12.1 de glib.

Un peu de théorie

Les listes chaînées sont un concept un peu différent. Au lieu d’avoir un gros bloc de données, nous avons une cellule qui ne contient qu’une seule donnée. En multipliant les cellules, nous arrivons à stocker nos données. Et pour en obtenir une liste, nous établissons des liens entre les cellules, chacune d’elle pointant vers la suivante. Voici comment coder chaque cellule avec glib (gslist.h) :

typedef struct _GSList GSList;
struct _GSList
{
  gpointer data;
  GSList *next;
};

Une cellule est donc composée de la donnée qu’elle va contenir, ou plutôt un pointeur vers cette donnée, et un pointeur vers la cellule suivante next. Nous parlons de liste doublement chaînée lorsque chaque cellule, non contente de pointer seulement vers la suivante, va également pointer vers la précédente. Voici comment glib l’implémente (glist.h) :

01 typedef struct _GList GList;
02
03 struct _GList
04 {
05   gpointer data;
06   GList *next;
07   GList *prev;
08 };

Fig. 1 : Cellule de liste chaînée

Dans la suite de l’article, nous allons nous limiter aux listes doublement chaînées à peine différentes de celles simplement chaînées. Vous vous référerez donc seulement aux fichiers glist.c et glist.h. Une opération sur une cellule (ajout, suppression, déplacement) consiste donc à simplement changer les liens entre chaque cellule (Fig. 2).

Créer une liste

D’après la documentation de glib, une liste chaînée vide est un pointeur vers NULL. Voici donc comment créer une liste, initialement vide :

Fig. 2 : Liste chaînée

GList *liste;
liste = NULL;

Ajouter des données

Avant d’ajouter des données, distinguons deux cas. Allez-vous les ajouter au début ou à la fin de la liste ? Mais quel que soit le cas, nous créons une nouvelle cellule, ce que fait glib avec la fonction _g_list_alloc() qui est une fonction interne de glib. Puis le principe consiste à modifier d’abord les champs prev et next de la nouvelle cellule, puis ceux des autres cellules. En effet, ceux de notre nouvelle cellule ne sont pas initialisés, donc autant commencer par cela. Par ailleurs, nous allons utiliser les pointeurs des cellules existantes : pas question de les écraser avant de s’en être servi !

Ajout à la fin

01 GList*
02 g_list_append (GList        *list,
03                gpointer         data)
04 {
05   GList *new_list;
06   GList *last;
07
08   new_list = _g_list_alloc ();
09   new_list->data = data;
10   new_list->next = NULL;
11
12   if (list)
13     {
14       last = g_list_last (list);
15       /* g_assert (last != NULL); */
16       last->next = new_list;
17       new_list->prev = last;
18
19       return list;
20     }
21   else
22     {
23       new_list->prev = NULL;
24       return new_list;
25     }
26 }

Après la création de la cellule et son remplissage (champ data), il faut revoir les pointeurs. Nous disposons de list, notre cellule de référence, et new_list, la nouvelle cellule. Distinguons deux cas (ligne 12). Premier cas, le plus simple : la liste initiale est vide. Dans ce cas, nous avons seulement à initialiser notre champ prev à NULL (ligne 23) et à renvoyer un pointeur vers notre cellule (ligne 24). Dans l’autre cas, nous devons chercher la dernière cellule, ce dont se charge la fonction g_list_last() (ligne 14). Cette dernière cellule devient l’avant dernière et son champ next doit pointer vers la nouvelle cellule (ligne 16). La nôtre doit alors pointer avec son champ prev vers ce qui était la dernière cellule (ligne 17). Il ne reste plus qu’à renvoyer un pointeur vers la liste (ligne 19). On associe souvent bibliothèque GLib à GTK+, le toolkit graphique originellement créé pour The Gimp et depuis largement utilisé par un très grand nombre d’applications. GLib est indissociable de GTK+, ce qui n’est pas le cas inversement. Le code de la fonction g_list_last() se trouve un peu plus loin dans le fichier glist.c :

01 GList*
02 g_list_last (GList *list)
03 {
04   if (list)
05     {
06       while (list->next)
07         list = list->next;
08     }
09
10   return list;
11 }

Il consiste simplement pour une liste donnée (si elle existe – ligne 4) à la parcourir jusqu’à son dernier élément, donc à itérer sur son champ next tant que celui-ci pointe vers une cellule (lignes 6 et 7). Lorsqu’il ne pointe plus sur rien, nous tenons notre dernier élément que nous renvoyons (ligne 10).

Ajout au début

01 GList*
02 g_list_prepend (GList         *list,
03                 gpointer  data)
04 {
05   GList *new_list;
06
07   new_list = _g_list_alloc ();
08   new_list->data = data;
09   new_list->next = list;
10
11   if (list)
12     {
13       new_list->prev = list->prev;
14       if (list->prev)
15         list->prev->next = new_list;
16       list->prev = new_list;
17     }
18   else
19     new_list->prev = NULL;
20
21   return new_list;
22 }

Comme précédemment, après la création de la cellule et son remplissage (champ data), nous revoyons nos pointeurs. Mais vous allez vous rendre compte, à la lecture du code, que celui-ci permet non seulement d’insérer une cellule en début de liste, mais également avant n’importe quelle cellule ! En effet, à la place de la ligne 11, nous aurions pu nous contenter d’avoir simplement ceci :

11   if (list)
12       list->prev = new_list;
13
14   new_list->prev = NULL;
15
16   return new_list;
17 }

En début de liste, le champ prev pointe par définition vers NULL (ligne 14) ce qu’il fallait corriger pour l’ancien début de liste (ligne 12). Voici un petit exemple :

GList *liste;
gchar *chaine;
/* Initialisation de la liste */
liste = NULL;
/* Insertion d’une chaîne de caractères */
chaine = g_strdup("bonjour");
liste = g_list_prepend(liste, chaine);
/* Insertion d’une autre chaîne de caractères */
chaine = g_strdup("salut");
liste = g_list_prepend(liste, chaine);

Ajout au milieu

Il existe également deux autres fonctions d’ajout, g_list_insert_before() et g_list_insert(), pour insérer une nouvelle cellule entre deux autres, ou plutôt avant celle donnée en argument via une autre cellule (g_list_insert_before()) ou via la position souhaitée (g_list_insert()). Si votre liste chaînée est triée, vous pouvez également utiliser g_list_insert_sorted_with_data() qui vous placera la nouvelle cellule à l’endroit adéquat.

Supprimer des données

Supprimer une cellule

Supprimer une cellule s’effectue en deux étapes. Vous devez délier la cellule de la liste chaînée, puis la détruire en libérant l’espace qui lui était alloué. Voici le code de glib :

01 GList*
02 g_list_remove (GList             *list,
03                gconstpointer  data)
04 {
05   GList *tmp;
06
07   tmp = list;
08   while (tmp)
09     {
10       if (tmp->data != data)
11         tmp = tmp->next;
12       else
13         {
14           if (tmp->prev)
15             tmp->prev->next = tmp->next;
16           if (tmp->next)
17             tmp->next->prev = tmp->prev;
18
19           if (list == tmp)
20             list = list->next;
21
22           _g_list_free1 (tmp);
23
24           break;
25         }
26     }
27   return list;
28 }

D’abord, nous commençons par chercher la cellule à supprimer en fonction de la donnée qu’elle contient. C’est l’intérêt de la boucle ligne 8, avec l’itération sur tmp ligne 11 et le test de fin de boucle ligne 10. Lorsque la cellule est trouvée, elle est déliée et supprimée lignes 14 à 22. Il est surprenant de trouver ce code dans la boucle, mais, après tout, pourquoi pas puisque nous sortons dans ce cas de manière inconditionnelle de la boucle ligne 24. Cette façon de faire présente également l’avantage de ne pas nécessiter de test en sortie de boucle pour s’assurer que la cellule existe bien avant de faire le travail. Comme nous comptons supprimer la cellule, il est inutile de travailler dessus. Nous nous contentons donc seulement de raccorder les deux bouts de chaîne en modifiant les champs prev et next des cellules connexes. C’est l’objet des lignes 14 à 17 avec un test à chaque fois, des fois que nous soyons en début ou en fin de liste chaînée. Enfin, nous pouvons supprimer notre cellule, ligne 22. Cela signifie qu’avant d’appeler g_list_remove(), vous devez avoir fait le nécessaire (par exemple libérer la mémoire si besoin) avec le champ data de la cellule. Vous n’aurez plus accès à ce champ ensuite. La fonction _g_list_free1() n’est pas une fonction, mais une macro. Faites une recherche dans glist.c et vous trouverez ceci en début de fichier :

#define _g_list_free1(list)     g_slice_free (GList, list)

Digression sur l’ancienne gestion de la mémoire

Tiens, mais pourquoi avoir une telle macro et non un appel direct à g_slice_free() ? Tout simplement parce que les gestionnaires de mémoire se suivent et se remplacent dans glib. Reprenez glist.c de la version 2.10... Il n’y a pas eu de changement à ce niveau entre 2.10 et 2.12. Mais reprenez donc la version 2.8. Si g_list_remove() n’a pas changé, voici ce que signifiait _g_list_free1() :

01 static inline void
02 _g_list_free_1 (GList *list)
03 {
04   if (list)
05     {
06       list->data = NULL;
07
08 #ifdef ENABLE_GC_FRIENDLY
09       list->prev = NULL;
10 #endif /* ENABLE_GC_FRIENDLY */
11
12       G_LOCK (current_allocator);
13       list->next = current_allocator->free_lists;
14       current_allocator->free_lists = list;
15       G_UNLOCK (current_allocator);
16     }
17 }

En plus d’être joyeusement incompréhensible au premier abord, ce code a la mauvaise idée de présenter une gestion de la mémoire propre aux listes. En effet, lignes 13 et 14, vous remarquez que nous travaillons sur list->next. En regardant ces lignes de plus près, et sans négliger la ligne 09, vous voyez que nous ne faisons rien d’autre que d’insérer notre cellule en début d’une liste chaînée appelée current_allocator. Cette notion de gestion de la mémoire propre aux listes est confirmée à la lecture de _g_list_alloc() du fichier glist.c présent dans les versions 2.8 :

01 static inline GList*
02 _g_list_alloc (void)
03 {
04   GList *list;
05
06   G_LOCK (current_allocator);
07   if (!current_allocator)
08     {
09       GAllocator *allocator = g_allocator_new ("GLib default
10	GList allocator", 128);
11       g_list_validate_allocator (allocator);
12       allocator->last = NULL;
13       current_allocator = allocator;
14     }
15   if (!current_allocator->free_lists)
16     {
17       list = g_chunk_new (GList, current_allocator->mem_chunk);
18       list->data = NULL;
19     }
20   else
21     {
22       if (current_allocator->free_lists->data)
23         {
24           list = current_allocator->free_lists->data;
25           current_allocator->free_lists->data = list->next;
26           list->data = NULL;
27         }
28       else
29         {
30           list = current_allocator->free_lists;
31           current_allocator->free_lists = list->next;
32         }
33     }
34   G_UNLOCK (current_allocator);
35   list->next = NULL;
36   list->prev = NULL;
37
38   return list;
39 }

Ligne 7, nous vérifions que la liste de cellules vides existe. Sinon, nous la créons lignes 9 à 13. Ligne 15, elle existe, mais dispose-t-elle encore de cellules vides ? Sinon, il suffit d’en créer, et de l’initialiser tant qu’à faire (lignes 17 et 18). Si nous disposions de cellules vides, nous observons un code assez amusant : ces cellules peuvent être stockées soit dans current_allocator->free_lists->data (code correspondant lignes 24 à 26), soit dans current_allocator->free_lists (code correspondant lignes 30 et 31). Dans les deux cas, la cellule est détachée de la liste des cellules vides. Ce genre de code vient généralement d’un souhait de compatibilité avec les versions antérieures. Il faudrait, pour s’en assurer, relire le code glist.c des versions 2.0 à 2.6 ! Enfin, notre cellule est initialisée lignes 35 et 36. Si nous nous sommes permis cette digression autour de l’allocateur de mémoire propre aux listes chaînées malgré le fait qu’il soit maintenant obsolète, c’est que si vous êtes amené à coder votre propre gestion des listes chaînées car privé de glib, cette façon de faire n’est pas sans intérêt. En effet, vous allez éviter de nombreux appels à malloc() très gourmands en temps d’exécution.

Délier une cellule de la liste

Mais revenons à la suppression de cellules. Il existe une autre fonction, g_list_remove_link(). La différence avec g_list_remove(), outre le fait qu’elle ne prend pas les mêmes arguments, est qu’elle se contente de sortir une cellule de la liste sans libérer la mémoire qu’elle utilise. Vous allez constater que ce changement peut justifier une différence de code notable avec la fonction précédente. Voici le code :

01 GList*
02 g_list_remove_link (GList *list,
03                     GList *link)
04 {
05   return _g_list_remove_link (list, link);
06 }

Ooops, manque de chance, cette fonction fait appel à une fonction interne. Elle se trouve juste au-dessus dans le fichier glist.c :

01 static inline GList*
02 _g_list_remove_link (GList *list,
03                      GList *link)
04 {
05   if (link)
06     {
07       if (link->prev)
08         link->prev->next = link->next;
09       if (link->next)
10         link->next->prev = link->prev;
11
12       if (link == list)
13         list = list->next;
14
15       link->next = NULL;
16       link->prev = NULL;
17     }
18
19   return list;
20 }

Vous reconnaissez le code lignes 7 à 10 pour délier la cellule, ou plutôt pour raccorder les deux morceaux de listes chaînées une fois la nôtre enlevée. Vous remarquez ligne 12 un test pour s’assurer que la cellule à retirer n’est pas celle du début. Sinon, ligne 13, il faut modifier le pointeur vers le début de la liste, pointeur qui sera renvoyé ligne 19. Comme notre cellule n’est pas supprimée de la mémoire, nous devons faire le nécessaire pour qu’elle ne pointe plus sur les autres cellules de la liste à laquelle elle était attachée. Pour cela, nous faisons pointer ses champs prev et next vers NULL lignes 15 et 16. Par conséquent, notre cellule, une fois déliée, si vous y regardez bien, devient une nouvelle liste chaînée à elle toute seule !

Les autres fonctions relatives à la suppression de cellules

Nous avons vu la macro _g_list_free_1(). Une fonction exécute cette macro : g_list_free_1(). En voici le code :

01 void
02 g_list_free_1 (GList *list)
03 {
04   _g_list_free1 (list);
05 }

Il existe encore quelques fonctions qui peuvent vous intéresser pour supprimer des cellules d’une liste. La fonction g_list_remove_all() fonctionne comme g_list_remove() à la différence de cette dernière qu’elle supprime toutes les cellules correspondant au critère et non seulement la première. Quant à g_list_free(), elle libère toute la mémoire utilisée par la liste.

Quelques utilitaires pour listes chaînées

Voici quelques utilitaires pour listes chaînées. Certains peuvent sembler inutiles comme la fonction pour obtenir le début d’une liste chaînée. Mais dans certains cas particuliers, ils ont leur utilité.

g_list_first()

01 GList*
02 g_list_first (GList *list)
03 {
04   if (list)
05     {
06       while (list->prev)
07         list = list->prev;
08     }
09
10   return list;
11 }

Cette fonction itère sur une liste jusqu’à trouver une cellule dont le champ prev est vide, donc par définition le début de la liste. Cette fonction montre son intérêt à la lecture du code : elle sert quand vous souhaitez trouver le début d’une liste quand vous disposez d’une cellule quelconque.

g_list_last()

01 GList*
02 g_list_last (GList *list)
03 {
04   if (list)
05     {
06       while (list->next)
07         list = list->next;
08     }
09
10   return list;
11 }

Cette fonction fait le même travail que la précédente, mais sur le champ next, ce qui nous donne la dernière cellule de la liste chaînée.

g_list_length()

En y réfléchissant bien, si vous reprenez la fonction précédente en lui ajoutant un compteur, vous pouvez obtenir le nombre de cellules dans la liste. Voici le code :

01 guint
02 g_list_length (GList *list)
03 {
04   guint length;
05
06   length = 0;
07   while (list)
08     {
09       length++;
10       list = list->next;
11     }
12
13   return length;
14 }

Il existe une autre façon, amusante parce qu’inhabituelle, de coder cela :

06   for(length = 0; list; list = list->next)
07       length++;
08
09   return length;
10 }

g_list_find()

01 GList*
02 g_list_find (GList         *list,
03              gconstpointer  data)
04 {
05   while (list)
06     {
07       if (list->data == data)
08         break;
09       list = list->next;
10     }
11
12   return list;
13 }

Cette fonction recherche la première cellule dont le champ data correspond à votre critère. Lorsque le test (ligne 7) est positif, la cellule est trouvée et nous sortons de la boucle avec break ligne 8. Si la cellule n’est pas trouvée, la boucle sur list (ligne 5) prend fin car la variable d’itération list devient nulle. Par effet de bord, nous renvoyons donc NULL ligne 12 dans ce cas. Il existe encore quelques autres fonctions aussi utiles que les précédentes (donc pas tant que cela) et dont le code revient toujours au même, une itération sur la liste jusqu’à un certain point, avec renvoi de la cellule correspondante, sa donnée ou sa position dans la liste. Nous préférons vous laisser continuer à explorer le sujet et allons passer à un type de liste un peu particulier, les listes triées.

Les listes triées

Une liste triée n’est rien d’autre qu’une liste, mais elle se distingue par le fait qu’elle est triée en permanence. Pour y arriver, il existe deux moyens. Soit vous partez d’une liste vide et, à chaque ajout, vous utilisez g_list_insert_sorted() ou g_list_insert_sorted_with_data(), soit vous triez votre liste puis utilisez la fonction précédente pour chaque nouvel ajout. Intéressons-nous à ces fonctions :

Insertion d’une cellule dans une liste triée

01 GList*
02 g_list_insert_sorted (GList        *list,
03                       gpointer      data,
04                       GCompareFunc  func)
05 {
06   return g_list_insert_sorted_real (list, data, (GFunc) func, NULL);
07 }
01 GList*
02 g_list_insert_sorted_with_data (GList            *list,
03                                 gpointer          data,
04                                 GCompareDataFunc  func,
05                                 gpointer          user_data)
06 {
07   return g_list_insert_sorted_real (list, data, (GFunc) func, user_data);
08 }

Ces deux fonctions font la même chose, et vous voyez que g_list_insert_sorted(liste, donnees, ftri) est équivalent à g_list_insert_sorted_with_data(liste, donnees, ftri, NULL). Voyons le code de g_list_insert_sorted_real() qui est une fonction interne :

01 static GList*
02 g_list_insert_sorted_real (GList    *list,
03                            gpointer  data,
04                            GFunc     func,
05                            gpointer  user_data)
06 {
07   GList *tmp_list = list;
08   GList *new_list;
09   gint cmp;
10
11   g_return_val_if_fail (func != NULL, list);

Après quelques initialisations, nous devons tester si la fonction de tri existe. Sinon, nous ne pouvons rien faire ! Ci-dessous, lignes 13 à 18, nous traitons le cas où la liste est vide. Nous n’avons en effet qu’à créer une cellule et renvoyer un pointeur dessus.

12
13   if (!list)
14     {
15       new_list = _g_list_alloc0 ();
16       new_list->data = data;
17       return new_list;
18     }
19

Lignes 20 à 27, à l’aide de notre fonction de comparaison, nous itérons sur chaque élément de la liste, jusqu’à trouver un élément qui ne soit pas supérieur à notre donnée de référence data. La condition pour rester dans la boucle est bien sûr d’avoir des éléments à comparer (tmp_list->next), mais que le résultat de la comparaison, stocké dans la variable cmp (lignes 20 et 26), reste strictement positif (cmp > 0).

20   cmp = ((GCompareDataFunc) func) (data, tmp_list->data, user_data);
21
22   while ((tmp_list->next) && (cmp > 0))
23     {
24       tmp_list = tmp_list->next;
25
26       cmp = ((GCompareDataFunc) func) (data, tmp_list->data, user_data);
27     }
28

Une fois trouvé l’endroit où insérer notre nouvelle cellule, il ne reste plus qu’à faire ce que nous avons déjà vu dans la fonction g_list_prepend(), mais avec quelques cas particuliers.

29   new_list = _g_list_alloc0 ();
30   new_list->data = data;
31
32   if ((!tmp_list->next) && (cmp > 0))
33     {
34       tmp_list->next = new_list;
35       new_list->prev = tmp_list;
36       return list;
37     }

Premier cas particulier : notre cellule est supérieure à toutes les autres (cmp > 0). Elle se trouve donc naturellement à la fin (!tmp_list->next). Dans ce cas, l’insertion est plus facile et nous retrouvons le même code que dans la fonction g_list_append(). Second cas particulier : notre cellule est inférieure à toutes les autres. Ici, si tmp_list->prev est nul, cmp est forcément inférieur ou égal à zéro car les autres cas ont été balayés auparavant. Dans ce cas, nous n’avons pas à modifier de cellule précédente. Sinon, nous exécutons les lignes 41 et 42. Il ne reste plus qu’à lier notre cellule à la cellule suivante, lignes 44 et 45 et à traiter le dernier cas particulier...

38    
39   if (tmp_list->prev)
40     {
41       tmp_list->prev->next = new_list;
42       new_list->prev = tmp_list->prev;
43     }
44   new_list->next = tmp_list;
45   tmp_list->prev = new_list;
46

Dans l’hypothèse où nous aurions inséré notre cellule en début de liste, nous devons retourner un pointeur vers notre nouvelle cellule (ligne 48). Sinon, le début de liste est inchangé et nous le renvoyons tel quel (ligne 50).

47   if (tmp_list == list)
48     return new_list;
49   else
50     return list;
51 }

Tri d’une liste chaînée

Si vous partez d’une liste qui n’est pas triée, ces fonctions d’insertion n’ont pas l’effet escompté. Vous devez trier votre liste, grâce à g_list_sort() ou g_list_sort_with_data() :

01 GList *
02 g_list_sort (GList        *list,
03              GCompareFunc  compare_func)
04 {
05   return g_list_sort_real (list, (GFunc) compare_func, NULL);
06
07 }
01 GList *
02 g_list_sort_with_data (GList            *list,
03                        GCompareDataFunc  compare_func,
04                        gpointer          user_data)
05 {
06   return g_list_sort_real (list, (GFunc) compare_func, user_data);
07 }

Ces deux fonctions font appel à g_list_sort_real(), avec NULL pour la donnée user_data dans le cas de g_list_sort().

01 static GList*
02 g_list_sort_real (GList    *list,
03                   GFunc     compare_func,
04                   gpointer  user_data)
05 {
06   GList *l1, *l2;
07
08   if (!list)
09     return NULL;
10   if (!list->next)
11     return list;
12
13   l1 = list;
14   l2 = list->next;
15
16   while ((l2 = l2->next) != NULL)
17     {
18       if ((l2 = l2->next) == NULL)
19         break;
20       l1 = l1->next;
21     }
22   l2 = l1->next;
23   l1->next = NULL;
24
25   return g_list_sort_merge (g_list_sort_real (list, compare_func, user_data),
26                             g_list_sort_real (l2, compare_func, user_data),
27                             compare_func,
28                             user_data);
29 }

Avant d’expliquer cette fonction, veuillez décortiquer les lignes 25 à 29. Nous faisons appel à g_list_sort_merge(). Regardez ses deux premiers arguments : ce sont le résultat de deux appels à g_list_sort_real(). Pour ceux qui connaissent l’algorithme de tri dit " quicksort ", cela devrait vous faire penser à des choses... Il s’agit bien de cela : notre liste est découpée en deux comme nous allons le voir plus loin. Chacune des deux sous-listes est triée par un appel, qui se veut donc récursif, à g_list_sort_real(). Nous supposons donc que g_list_sort_merge() prend en argument deux listes triées et rassemble leurs cellules en les triant. Commençons par étudier g_list_sort_real(). Lignes 8 à 11, nous nous débarrassons d’entrée de jeu des cas triviaux de listes vides ou unicellulaires, par définition déjà triées. Puis lignes 13 à 21, nous avons une boucle étrange qui consiste à itérer à la fois sur l2 = l2->next et l1 = l1->next, mais deux fois plus vite pour l2 que pour l1. L’intérêt de cette boucle est que lorsque l2 pointe sur la dernière cellule, l1 pointe sur celle du milieu. Ligne 22, nous faisons pointer l2 vers la cellule suivant celle du milieu. Ligne 23, nous coupons notre liste en deux en faisant pointer le champ next de la cellule du milieu vers NULL. Nous obtenons ainsi deux listes, l’une pointée par list puisqu’il s’agit du début de notre liste, et l’autre par l2, première cellule après le milieu de la liste complète. Lignes 25 à 29, chacune de ces deux listes sont triées par la même fonction g_list_sort_real(), donc récursivement, suivant l’adage diviser pour mieux régner. Une fois ces deux listes triées, elles sont remises ensemble avec g_list_sort_merge() que nous voyons maintenant :

01 static GList *
02 g_list_sort_merge (GList     *l1,
03                    GList     *l2,
04                    GFunc     compare_func,
05                    gpointer  user_data)
06 {
07   GList list, *l, *lprev;
08   gint cmp;
09
10   l = &list;
11   lprev = NULL;
12
13   while (l1 && l2)
14     {
15       cmp = ((GCompareDataFunc) compare_func) (l1->data, l2->data, user_data);
16
17       if (cmp <= 0)
18         {
19           l->next = l1;
20           l1 = l1->next;
21         }
22       else
23         {
24           l->next = l2;
25           l2 = l2->next;
26         }
27       l = l->next;
28       l->prev = lprev;
29       lprev = l;
30     }
31   l->next = l1 ? l1 : l2;
32   l->next->prev = l;
33
34   return list.next;
35 }

Outre les deux listes à fusionner (l1 et l2) données en argument, nous avons besoin d’une variable pour construire la liste résultant de la fusion. C’est le rôle de list, ou plutôt de list.next (remarquez que ce n’est exceptionnellement pas un pointeur). Deux variables jouant le rôle d’itérateurs sont également nécessaires : l et lprev. Elles sont initialisées lignes 10 et 11. Le cœur de la fusion se trouve dans la boucle lignes 13 à 30. Nous allons itérer sur l1 et l2 en les comparant (ligne 15) à chaque étape. Chaque fois, le plus petit des deux (test ligne 17) est relié à la liste list grâce à l’itérateur l (et son associé lprev). Celui-ci est donc incrémentée à chaque fois (lignes 27 à 29). Lorsque l’une des deux listes est vide, il ne reste plus qu’à concaténer purement et simplement l’autre à la liste résultat dont la dernière cellule est pointée par l (lignes 31 et 32). Enfin, le résultat list.next est renvoyé (ligne 34). Dans tout ce code, vous remarquez que nous avons peu fait cas de la variable user_data. Cherchez son utilité : elle ne sert qu’en argument de la fonction de comparaison (ligne 15).

Itérer sur une liste chaînée

Avant de nous quitter, voyons comment itérer sur une liste chaînée. Nous avons vu plus haut plusieurs façons de faire. En général, voici comment coder une boucle :

01 GList *l;
02 for(l = list, l; l = l->next) {
03         /* votre code ici */
04 }

glib propose également une façon de faire avec g_list_foreach(). En voici son code :

01 void
02 g_list_foreach (GList         *list,
03                 GFunc          func,
04                 gpointer  user_data)
05 {
06   while (list)
07     {
08       GList *next = list->next;
09       (*func) (list->data, user_data);
10       list = next;
11     }
12 }

Cette fonction propose une boucle avec une itération directement sur list, ce qui contrairement à notre code ci-dessus ne pose pas de problème : nous sommes dans une fonction où list n’est modifiée que dans le cadre de cette fonction. Vous remarquez l’utilisation d’une variable temporaire next ligne 8. Nous ne nous expliquons pas son utilité vu que l’appel à la fonction utilisateur ligne 9 ne permet aucune action sur la cellule, donc aucune modification de l’ordre des cellules. L’incrément de la variable d’itération a lieu ligne 10 avec cette fameuse variable next.

Conclusion

Nous avons, grâce au code contenu dans la bibliothèque glib, pu faire un tour des fonctionnalités attendues d’un code de gestion des listes chaînées. Nous espérons que cet article aura rempli ses objectifs, à savoir vous faire découvrir les listes chaînées si vous ne les connaissiez pas, vous montrer comment les coder, et surtout vous faire voir un extrait de code d’un gros projet, en l’occurrence glib, qui n’est pas loin des 500 000 lignes de code. En effet, lire le code des autres est toujours intéressant. Quand ce code a été lu et relu, corrigé quand nécessaire, vous avez de grandes chances d’avoir une bonne qualité de code. Le mois prochain : les chaînes de caractères de type GString... Références :

• Le site de GTK+ : http://www.gtk.org/
• C en action (O’Reilly) – chapitre 6

Retrouvez cet article dans : Linux Magazine 86