La Glib-2.0 et les arbres

Le mois dernier, nous avons vu comment la Glib-2.0 nous permet de gérer efficacement et simplement les listes simplement et doublement chaînées. Aujourd'hui, nous allons nous intéresser à la gestion d'un autre type de structure de données : les arbres, en commençant par les arbres binaires balancés.

Les arbres binaires balancés

Un arbre permet de stocker des données dans une structure arborescente allouée dynamiquement. Chaque donnée est stockée dans un des n uds de l'arbre. De ce n ud peuvent partir un certain nombre de branches, qui sont des pointeurs vers d'autres n uds de l'arbre. Les n uds qui ne comportent pas de branches sont appelés feuilles. Il existe un n ud particulier sur lequel aucun des autres n uds ne pointe, c'est le tronc de l'arbre, que l'on appelle communément la racine. La profondeur d'un arbre (ou plutôt la hauteur...) est le nombre maximal de branches séparant la racine de chacune de ses feuilles.

Les arbres binaires ont ceci de particulier que chacun de leur n ud comporte au plus deux branches. Un arbre est dit balancé lorsque sa profondeur est toujours minimale, c'est-à-dire que les n uds plus proches de la racine sont toujours remplis (ils ont deux branches) avant les n uds proches des feuilles.

Les arbres binaires balancés proposés par la Glib-2.0 sont donc de ce type-là. Du point de vue du programmeur, les arbres binaires balancés sont simplement une structure dans laquelle on peut placer des données de manière ordonnée, peu importe que ces données soient ou non stockées dans une structure arborescente.

Les arbres binaires balancés de la Glib-2.0 sont référencés par un pointeur sur une structure (opaque) GTree et les données qu'ils peuvent contenir sont composées d'une clef, permettant de classer la donnée et de la retrouver, et d'un pointeur générique sur la donnée proprement dite. La clef doit être unique dans un arbre donné.

Avant de pouvoir stocker des données dans un arbre, il faut le créer (vide). Cela se réalise par exemple avec la fonction suivante :
GTree *g_tree_new(GCompareFunc fonction_compare);

Le paramètre fonction_compare est une fonction de comparaison dont le prototype doit être le suivant :
gint fonction_compare(gconstpointer a, gconstpointer b);
Cette fonction doit permettre de comparer deux clefs a et b. Elle doit retourner une valeur négative si a doit être classée avant b, et une valeur positive dans le cas contraire. Les clefs peuvent être de nature quelconque, mais on utilise souvent des chaînes de caractères ou des entiers.

Dans le cas de clefs alphanumériques, une fonction de comparaison possible est strcmp(), mais vous pouvez élaborer des fonctions de comparaison bien plus complexes. En fait, il y a même une autre possibilité pour créer un arbre, permettant d'utiliser une fonction de comparaison encore plus complète :

GTree *g_tree_new_with_data(GCompareDataFunc fonction_compare,
gpointer donnee_supplementaire);

Si l'on crée un arbre avec cette fonction, fonction_compare() doit avoir le prototype suivant :
gint fonction_compare(gconstpointer a,
gconstpointer b,
gpointer donnee_supplementaire);

Le paramètre donnee_supplementaire de la fonction g_tree_new_with_data() sera transmis tel quel à la fonction de comparaison des clefs. Cela permet d'écrire une fonction de comparaison pour tous les arbres, mais qui réagira différemment suivant l'arbre qui l'utilise. Bon, d'accord, ce n'est pas très utilisé...

En réalité, les deux fonctions précédentes sont des appels déguisés à une fonction de création d'arbre bien plus générale encore :
GTree *g_tree_new_full(GCompareDataFunc fonction_compare,
gpointer donnee_supplementaire,
GDestroyNotify detruire_clef,
GDestroyNotify detruire_donnee);

Les deux premiers paramètres de cette fonction sont déjà connus. Le paramètre detruire_clef est une fonction dont le prototype est le suivant :
void detruire_clef(gpointer clef);

Cette fonction sera appelée lors de la destruction de l'arbre, avec comme paramètre chacune des clefs des n uds de l'arbre, pour éventuellement libérer la mémoire qu'elles occupaient. Si on ne veut pas utiliser de telles fonctions, il suffit de passer NULL à la place.

Le paramètre detruire_donnee est une fonction du même genre qui permet de libérer la mémoire utilisée des données de chacun des n uds de l'arbre lors de sa destruction.

Le rôle exact de detruire_clef et detruire_donnee sera plus clair en regardant l'exemple de programme.

Pour être tout à fait exhaustif avec les créations d'arbres, sachez que
arbre = g_tree_new(fonction); est strictement équivalent à
arbre = g_tree_new_full(fonction, NULL, NULL, NULL);
et
arbre = g_tree_new_with_data(fonction, donnee) est strictement équivalent à
arbre = g_tree_new_full(fonction, donnee, NULL, NULL);

La destruction d'un arbre se fait à l'aide de la fonction suivante :
void g_tree_destroy(GTree *tree);

Cette fonction libère toute la mémoire utilisée par chacun des n uds de l'arbre et appelle les éventuelles fonctions de libération de la mémoire occupées par les clefs ou les données de chaque n ud.

Lorsqu'un arbre vide a été créé, on peut commencer à y introduire des données. Cela ce fait simplement grâce à la fonction :
void g_tree_insert(GTree *arbre,
gpointer clef,
gpointer donnee);
Cette fonction insère la donnée donnee dans l'arbre. Le paramètre clef sert à classer la donnée dans l'arbre. Si la clef existe déjà dans cet arbre, la donnée du n ud correspondant est remplacée par la nouvelle donnée. Si l'arbre a été créé avec g_tree_new_full() et qu'une fonction detruire_donnee() a été spécifiée, l'ancienne donnée est libérée par un appel à cette fonction. De même, si une fonction detruire_clef() a été spécifiée, la clef passée en paramètre (la nouvelle) est libérée par un appel à detruire_clef().

Cela peut sembler bizarre de détruire la nouvelle clef si une clef équivalente existe déjà. On peut vouloir que ce soit l'ancienne clef qui soit détruite dans ce cas. C'est ce que réalise la fonction suivante :
void g_tree_replace(GTree *arbre,
gpointer clef,
gpointer donnee);
qui fonctionne exactement comme g_tree_insert().

Pour supprimer un n ud d'un arbre, on peut utiliser la fonction suivante :
void g_tree_remove(GTree *arbre,
gconstpointer clef);
Le paramètre clef est évidemment la clef permettant de retrouver le n ud dans l'arbre. Si les fonctions detruire_clef() et detruire_donnee() ont été spécifiées, elles sont employées pour libérer la mémoire utilisée respectivement par la clef et la donnée de ce n ud.

Si vous voulez juste retirer le n ud de l'arbre, sans libérer la mémoire, il faut alors utiliser la fonction suivante :
void g_tree_steal(GTree *arbre,
gconstpointer clef);
Notez que si l'arbre a été créé avec g_tree_new() ou g_tree_new_with_data(), ces deux fonctions sont strictement équivalentes.

Lorsque l'arbre est construit et garni de n uds, on peut retrouver une donnée très rapidement à partir de sa clef associée, avec la fonction suivante :
gpointer g_tree_lookup(GTree *arbre,
gconstpointer clef);
La valeur de retour de cette fonction est la donnée que l'on cherche, ou NULL si la clef n'a pas été trouvée. La recherche d'une donnée dans un arbre est extrêmement rapide, surtout si on la compare à une recherche dans une liste chaînée par exemple.

Cependant, si on veut que notre arbre puisse contenir des données NULL, un appel à g_tree_lookup() ne nous dira pas si une donnée valant NULL a été trouvée ou non. C'est pourquoi on peut utiliser la fonction, un peu plus complexe, suivante :
gboolean g_tree_lookup_extended(GTree *arbre,
gconstpointer clef,
gpointer *clef_originale,
gpointer *donnee);
Cette fonction renvoie TRUE si la clef a été trouvée dans l'arbre, et FALSE sinon. De plus, si le n ud a été trouvé, la donnée de ce n ud est transmise dans le pointeur donnee, et la clef de ce n ud (qui peut être physiquement différente de la clef de recherche, puisque ces deux clefs ne doivent être identiques que dans le sens de la fonction fonction_compare() définie lors de la création de l'arbre). La récupération de ces pointeurs peut par exemple permettre de libérer la mémoire utilisée par la clef et la donnée avant un g_tree_remove(), si l'arbre n'a pas été créé avec g_tree_new_full().

Comme pour les listes chaînées, il est possible d'appeler une fonction qui recevra en paramètre successivement chacun des n uds de l'arbre. Pour cela, il faut utiliser la fonction :
void g_tree_foreach(GTree *arbre,
GTraverseFunc fonction,
gpointer donnee_sup);
La fonction fonction doit avoir le prototype suivant :
gboolean fonction(gpointer clef,
gpointer donnee,
gpointer donnee_sup);
Cette fonction doit renvoyer FALSE si l'on souhaite continuer le parcours et TRUE sinon. En pratique, ce genre de fonction renvoie toujours FALSE, car il est bien rare que l'on doive arrêter un parcours en cours de route. Les paramètres clef et donnee sont les contenus de chacun des n uds et le paramètre donnee_sup est celui passé à la fonction g_tree_foreach(). Ici encore, tout cela sera bien plus clair dans le programme exemple.

Justement, avant de voir le premier exemple de ce mois-ci, voyons les deux dernières fonctions de la Glib-2.0 concernant les arbres binaires balancés.

La première renvoie la profondeur actuelle de l'arbre :
gint g_tree_height(GTree *arbre);

Et la seconde renvoie le nombre de n uds qu'il contient :
gint g_tree_nnodes(GTree *arbre);

Voyons maintenant toutes ces fonctions dans un programme exemple :

/* arbre.c */

#include <stdio.h>
#include <string.h>
#include <glib.h>

/* Fonction pour afficher chacun des noeuds d'un arbre */
static gboolean afficher_noeud(gpointer clef,
gpointer donnee,
gchar *format)

printf(format, clef, donnee);

return FALSE;


/* Fonction de comparaison de deux clefs entières */
static gint compare_entier(gconstpointer data1, gconstpointer data2)

gint valeur1, valeur2;

valeur1 = GPOINTER_TO_INT(data1);
valeur2 = GPOINTER_TO_INT(data2);
return valeur1 - valeur2;


int main(int argc, char *argv[])

GTree *arbre_entier, *arbre_chaine;
gint i;
gchar *recherche;

/* Affichage du numéro de version de la glib */
printf("glib version : %d.%d.%dn",
GLIB_MAJOR_VERSION,
GLIB_MINOR_VERSION,
GLIB_MICRO_VERSION);

/* On crée un premier arbre où les clefs sont des entiers et les
* données seront des chaînes de caractères */
arbre_entier = g_tree_new((GCompareFunc)compare_entier);

/* Ensuite, on insère quelques couples (clefs, données) */
for (i=20 ; i>0 ; i--)

gchar *donnee;

donnee = g_strdup_printf("donnée n°%d : %d", i, i);
g_tree_insert(arbre_entier, GINT_TO_POINTER(i), donnee);


/* On vérifie la hauteur et le nombre de noeuds de l'arbre : */
printf("hauteur : %d, nombre de noeuds : %dn",
g_tree_height(arbre_entier),
g_tree_nnodes(arbre_entier));

/* On affiche maintenant tous les noeuds */
g_tree_foreach(arbre_entier,
(GTraverseFunc)afficher_noeud,
"clef: %d, donnee %sn");

/* Puis on fait le ménage, en libérant la mémoire occupée par les données */
for (i = 1 ; i<=20 ; i++)

gchar *donnee;

if (g_tree_lookup_extended(arbre_entier,
GINT_TO_POINTER(i),
NULL,
(gpointer *)(&donnee)))
g_free(donnee);

/* puis on détruit cet arbre */
g_tree_destroy(arbre_entier);

/* On crée maintenant un nouvel arbre, dont les clefs et les données
* seront des chaînes. Ces deux chaînes seront libérées automatiquement
* par la fonction g_free() */
arbre_chaine = g_tree_new_full((GCompareDataFunc)strcmp, NULL,
(GDestroyNotify)g_free,
(GDestroyNotify)g_free);
/* Ajoutons quelques noeuds */
for (i=0 ; i < 100 ; i++)

gchar *clef, *donnee;

clef = g_strdup_printf("%02d", i);
donnee = g_strdup_printf("donnée %d", i);
g_tree_replace(arbre_chaine, clef, donnee);

/* Affichage de l'arbre */
g_tree_foreach(arbre_chaine,
(GTraverseFunc)afficher_noeud,
"clef : %s, donnee %sn");
/* On cherche la donnée associée à la clef "57" */
recherche = g_tree_lookup(arbre_chaine, "57");
printf("recherche : '%s'n", recherche);

/* On peut maintenant détruire l'arbre.
*/
g_tree_destroy(arbre_chaine);

return 0;


Compilez ce programme avec la ligne de commande suivante :
gcc arbre.c -o arbre `pkg-config --cflags --libs glib-2.0` -O2 -g -Wall

Vous remarquerez que les arbres trient les n uds d'après les clefs et, si vous utilisez g_mem_profile(), vous pourrez constater que la mémoire est correctement libérée à la fin de l'exécution de ce programme.

Les arbres généraux

Les arbres binaires balancés ne sont en fait qu'un cas particulier des arbres plus généraux que sait gérer la Glib-2.0. Plus exactement, la Glib-2.0 sait gérer des n uds nettement plus complexes que les n uds des arbres binaires balancés.

Un n ud (de type GNode) d'un arbre général est une structure qui contient un pointeur sur une donnée et quatre pointeurs sur d'autres n uds. Voici cette structure :

typedef struct _GNode GNode;

struct _GNode

gpointer data;
GNode *next;
GNode *prev;
GNode *parent;
GNode *children;
;

Le champ data est la donnée. Le champ parent pointe sur le n ud parent de notre n ud. Les champs next et prev pointent vers le n ud suivant et le n ud précédent de la liste des enfants du n ud parent de notre n ud. En effet, les arbres généraux n'étant pas forcément binaires, il peuvent contenir autant de n uds fils que l'on veut. Et le pointeur children pointe justement sur le premier de ces n uds fils. En général, on n'a jamais à utiliser ces champs directement, puisque des fonctions sont là pour nous simplifier la vie. Chacun des pointeurs GNode * peut être NULL.

Il n'existe pas de réelle structure pour les arbres généraux de la Glib-2.0. On utilise directement les n uds pour chacune des opérations. On reconnaît simplement la racine d'un tel arbre au fait que c'est un n ud dont les pointeurs parent, prev et next sont NULL. Plus simplement, on peut utiliser la macro suivante :
gboolean G_NODE_IS_ROOT(GNode *noeud);
qui renvoie TRUE si n ud est une racine d'un arbre et FALSE sinon.

De la même façon, on peut savoir si un n ud est une feuille ou non à l'aide de la macro suivante :
gboolean G_NODE_IS_LEAF(GNode *node);

La création et le placement des n uds

Pour créer un n ud (vide), le mieux est d'utiliser la fonction suivante :
GNode *g_node_new(gpointer donnee);
Cette fonction réserve la mémoire pour la structure GNode, initialise le champ data à donnee, et tous les autres pointeurs à NULL.

Une fois le n ud créé, on peut le placer dans un arbre, ou plus exactement dans une branche. Il existe beaucoup de manières de faire cela. La première consiste à appeler la fonction suivante :
GNode *g_node_insert_after(GNode *parent,
GNode *frere,
GNode *noeud);
qui insère le noeud parmi les fils de parent, juste après le n ud frere. frere peut être NULL, dans quel cas, noeud est placé en dernier dans les enfants de parent. Mais si frere n'est pas NULL, il doit absolument avoir parent comme n ud parent.

La fonction suivante réalise à peu près la même chose, mais place le n ud avant frere, ou en premier parmi les enfants de parent si frere est NULL :
GNode *g_node_insert_before(GNode *parent,
GNode *frere,
GNode *noeud);

Les deux fonctions suivantes (la première est en réalité une macro) permettent de simplifier les cas où l'on veut ajouter un n ud respectivement en dernier et en premier parmi les enfants de parent :
GNode *g_node_append(GNode *parent,
GNode *noeud);
GNode *g_node_prepend(GNode *parent,
GNode *noeud);

Il est également possible d'ajouter un n ud parmi les enfants d'un n ud parent à une position donnée avec cette fonction :
GNode *g_node_insert(GNode *parent,
gint position,
GNode *noeud);
Le paramètre position indique où l'on veut que le n ud soit placé. S'il vaut 0, le noeud sera le premier des enfants de parent ; s'il est négatif, il sera le dernier, sinon il sera à la position position.

Enfin, sachez qu'il existe trois macros permettant de créer un n ud et de le placer dans un arbre en une seule opération. Elles fonctionnent de la même façon que leur contrepartie qui ne comportent pas le suffixe «_data»:
GNode *g_node_insert_data(GNode *parent,
gint position,
gpointer data);
GNode *g_node_prepend_data(GNode *parent,
gpointer data);
GNode *g_node_append_data(GNode *parent,
gpointer data);

Toutes les fonctions présentées jusqu'à maintenant renvoient un pointeur sur le n ud qui vient d'être créé ou inséré.

La navigation d'un n ud à l'autre

A l'intérieur d'un arbre, on peut facilement naviguer d'un n ud à l'autre à l'aide d'une foule de fonctions. Par exemple, il est facile de trouver le n ud précédant ou suivant un n ud donnée dans la liste des enfants d'un n ud parent à l'aide des deux macros suivantes:
GNode *g_node_prev_sibling(GNode *noeud);
GNode *g_node_next_sibling(GNode *noeud);

Dans le même ordre d'idées, on peut trouver respectivement le premier et le dernier des frères d'un n ud avec les deux fonctions suivantes :
GNode *g_node_first_sibling(GNode *noeud);
GNode *g_node_last_sibling(GNode *noeud);

Un n ud peut évidemment avoir accès à son premier ou à son dernier enfant (s'il existe) avec les deux fonctions suivantes:
GNode *g_node_first_child(GNode *noeud);
GNode *g_node_last_child(GNode *noeud);

Plus généralement, la fonction suivante renvoie le nième fils d'un n ud :
GNode *g_node_nth_child(GNode *noeud,
guint n);

Réciproquement, on peut savoir à quelle position un n ud fils apparaît parmi les enfants d'un n ud. C'est ce que réalise la fonction suivante:
gint g_node_child_position(GNode *noeud,
GNode *fils);
Cette fonction renvoie un entier positif correspondant à la position de fils dans les enfants de noeud. Le premier n ud a la position 0. Si fils n'est pas un des enfants de noeud, -1 est renvoyé.

De la même façon, la fonction suivante renvoie la position du fils de noeud dont la donnée est donnee.
gint g_node_child_index(GNode *noeud,
gpointer donnee);

La fonction suivante renvoie le nombre de n uds enfants que possède un n ud:
guint g_node_n_children(GNode *noeud);

On peut retrouver quel est le n ud racine de l'arbre auquel appartient un n ud donné par un appel à la fonction:
GNode *g_node_get_root(GNode *noeud);

Plus généralement, la fonction suivante permet de savoir si un n ud est dans la descendance d'un autre:
gboolean g_node_is_ancestor(GNode *noeud,
GNode *descendant);
Si noeud est le père de descendant, ou le père de son père, etc., cette fonction renvoie TRUE. Dans le cas contraire, elle renvoie FALSE.

Et la fonction suivante inverse l'ordre des enfants d'un n ud :
void g_node_reverse_children(GNode *noeud);

Il existe également des fonctions permettant de savoir comment est situé un n ud dans un arbre. Par exemple, la fonction suivante permet de savoir quel est le nombre maximal de générations qui suivent un n ud:
guint g_node_max_height(GNode *racine);
Si racine a au moins un fils et aucun petit-fils, cette fonction renvoie 1 ; si racine possède au moins un petit-fils et aucun arrière-petit-fils, elle renverra 2, etc.

A l'inverse, la fonction suivante renvoie le nombre de générations qui séparent un n ud de la racine de l'arbre auquel il appartient:
guint g_node_depth(GNode *noeud);

Enfin, la fonction suivante renvoie le nombre de descendants d'un n ud, c'est-à-dire le nombre de ses enfants plus le nombre de ses petits-enfants, plus le nombre de ses arrières-petits-enfants, etc.:
guint g_node_n_nodes(GNode *racine,
GTraverseFlags type);
Le paramètre type peut prendre l'une de ces trois valeurs:
•         G_TRAVERSE_LEAFS, alors seuls les n uds feuilles seront comptabilisés ;
•        
G_TRAVERSE_NON_LEAFS, seuls les n uds non-feuilles (c'est-à-dire ayant des fils) seront comptabilisés ;
•         G_TRAVERSE_ALL, tous les n uds, feuilles et non-feuilles seront comptabilisés.

Les opérations sur les n uds et les arbres

Maintenant que l'on sait créer et placer des n uds dans un arbre, et avoir un maximum d'informations sur chacun de ces n uds, on peut voir quelles sont les opérations que l'on peut appliquer à un n ud ou à un arbre tout entier.

Tout d'abord, pour un n ud donné, il est possible de retrouver quel est le n ud (s'il existe), parmi ses enfants directs (c'est-à-dire à l'exclusion des petits-enfants ou des arrières-petits-enfants), qui contient la donnée donnee. Cela se réalise à l'aide de la fonction suivante:
GNode *g_node_find_child(GNode *noeud,
GTraverseFlags type,
gpointer donnee);
Le paramètre type a le même sens que pour la fonction g_node_n_nodes(). Si aucun n ud ne contient la donnée donnee, g_node_find_child() renvoie NULL.

Il est également possible d'effectuer une recherche d'une donnée parmi toute la descendance d'un n ud, ce qui revient à effectuer une recherche dans tout un arbre si le n ud en question en est la racine. Pour cela, il faut utiliser la fonction:
GNode *g_node_find(GNode *racine,
GTraverseType ordre,
GTraverseFlags type,
gpointer donnee);
Le seul paramètre qui nécessite une explication est le paramètre ordre. Il indique dans quel ordre doit s'effectuer la recherche. Il peut prendre les valeurs suivantes:
•        
G_PRE_ORDER, chaque n ud est alors testé avant ses enfants;
•         G_IN_ORDER, pour chaque n ud, le premier enfant est testé, puis le n ud lui-même, et les autres enfants ensuite;
•         G_POST_ORDER, chaque n ud est testé après ses enfants;
•         G_LEVEL_ORDER, la recherche s'effectue alors niveau par niveau: la racine, puis les enfants de la racine, puis les petits-enfants, etc.

Suivant les cas, tel ou tel ordre est plus approprié. Par exemple, pour un arbre binaire, l'ordre G_IN_ORDER est le mieux adapté (essayez de comprendre pourquoi); alors que pour la recherche d'un fichier dans une arborescence de répertoires, on utilisera plutôt G_LEVEL_ORDER.

L'ordre est important car, bien évidemment, seul le premier n ud correspondant est retourné.

Comme c'est le cas avec les autres types de structures, la Glib-2.0 permet d'appeler une fonction donnée pour chacun des enfants d'un n ud avec la fonction suivante:
void g_node_children_foreach(GNode *noeud,
GTraverseFlags type,
GNodeForeachFunc fonction,
gpointer donnee_sup);

La fonction
fonction doit avoir le prototype suivant:
void fonction(GNode *noeud, gpointer donnee_sup);

Cette fonction sera appelée pour chacun des n uds enfants de noeud, suivant la règle imposée par type, avec comme premier paramètre un pointeur sur le n ud enfant et comme second paramètre le pointeur donnee_sup.

Mais g_node_children_foreach() n'est pas très puissante puisqu'elle ne concerne que la première génération en dessous d'un n ud (ce qui signifie qu'elle n'est pas récursive).

La fonction suivante est beaucoup plus générale puisqu'elle permet d'appeler une fonction pour chacun des n uds d'un arbre, suivant un ordre donné, en se limitant éventuellement à une profondeur donnée:
void g_node_traverse(GNode *racine,
GTraverseType ordre,
GTraverseFlags type,
gint profondeur_max,
GNodeTraverseFunc fonction,
gpointer        donnee_sup);
Les paramètres ordre et type ont le même sens que précédemment. La fonction fonction doit avoir le prototype suivant:
gboolean fonction(GNode *noeud, gpointer donnee_sup);
Si elle renvoie TRUE, le parcours des n uds s'arrête immédiatement, elle doit renvoyer FALSE sinon. Cela peut être utile si fonction est une fonction de recherche, qui doit s'arrêter à la première occurrence trouvée.

Le paramètre profondeur_max indique la profondeur maximale des appels. Par exemple, s'il vaut 1, fonction n'est appelée que pour la racine ; s'il vaut 2, fonction est appelée pour la racine et ses fils ; s'il vaut 3, fonction est appelée pour la racine, ses fils et ses petits-fils, etc. Si profondeur_max vaut -1, fonction est appelée sans limite de profondeur. 0 et les autres valeurs négatives ne doivent pas être utilisés.

La fonction suivante copie un n ud ainsi que tout le sous-arbre associé:
GNode *g_node_copy(GNode *noeud);
Par conséquent, malgré son nom, cette fonction est également capable de copier des arbres entiers.

Enfin, les deux fonctions suivantes permettent respectivement de séparer un n ud d'un arbre (ce qui revient en gros à remettre certains pointeurs à NULL, et de détruire complètement un arbre ou un sous-arbre:
void g_node_unlink(GNode *noeud);
void g_node_destroy(GNode *racine);

L'exemple suivant utilise quelques-unes de ces fonctions pour afficher une arborescence de répertoires:

/* noeud.c */

#include <stdio.h>
#include <string.h>

#include <sys/types.h>
#include <sys/stat.h>
#include <dirent.h>
#include <unistd.h>

#include <glib.h>

/* Fonction pour afficher chacun des noeuds d'un arbre */
static gboolean affiche_noeud(GNode *noeud)

if (G_NODE_IS_LEAF(noeud))
/* Si c'est une feuille, on l'indente */
gint profondeur = g_node_depth(noeud);
gchar *indentation;
gint i;

indentation = g_malloc(profondeur*2+1);
for (i=0 ; i<profondeur*2 ; i++)
indentation[i]=' ';
indentation[profondeur*2] = 0;
printf("%s%sn", indentation, g_basename(noeud->data));
else
printf("%sn", (char*)(noeud->data));

/* Il faut toujours renvoyer FALSE ! */
return FALSE;


/* Fonction récursive de parcours des répertoires. Cette fonction
* construit notre arbre */
static void construit_arbre(GNode *parent)

DIR *repertoire;
struct dirent *fichier;
struct stat etat;
GNode *noeud;

stat(parent->data, &etat);
if (!S_ISDIR(etat.st_mode))
return;

repertoire = opendir(parent->data);
if (repertoire)

fichier = readdir(repertoire);
while (fichier)

if (fichier->d_name[0] != '.')
/* Les noms de fichiers commençant par '.' sont ignorés */
gchar *chemin_complet;

chemin_complet = g_strconcat(parent->data, "/",
fichier->d_name, NULL);
stat(chemin_complet, &etat);
if (S_ISDIR(etat.st_mode))
/* Si c'est un répertoire, on récurse */
noeud = g_node_append_data(parent, chemin_complet);
construit_arbre(noeud);
else

noeud = g_node_append_data(parent,
g_strdup(fichier->d_name));
g_free(chemin_complet);


fichier = readdir(repertoire);

closedir(repertoire);



int main(int argc, char *argv[])

GNode *racine;
/* Affichage du numéro de version de la glib */
printf("glib version : %d.%d.%dn",
GLIB_MAJOR_VERSION,
GLIB_MINOR_VERSION,
GLIB_MICRO_VERSION);

/* Création du premier noeud */
racine = g_node_new(argv[1]);

/* On construit l'arbre des fichiers et des répertoires */
construit_arbre(racine);

/* Et on affiche le tout !
*/
g_node_traverse(racine, G_PRE_ORDER,
G_TRAVERSE_ALL, -1,
(GNodeTraverseFunc)affiche_noeud,
NULL);

return 0;


Compilez ce programme et lancez-le par exemple avec:
./noeud /tmp
Il affichera tout ce que contient ce répertoire.
Assurez-vous de bien comprendre comment fonctionne ce programme.
Vous pouvez également grandement l'améliorer, ne serait-ce qu'en libérant la mémoire qu'il utilise...

La prochaine fois

La prochaine fois, nous continuerons notre tour d'horizon des structures de données gérées par la Glib-2.0.

--
<David@dindinx.org> <odin@mandrakesoft.com>
Créateur et coordinateur de Giram.