Les listes chaînées
1. Présentation
Vous connaissez sûrement déjà les listes chaînées. Elles sont très pratiques, mais il faut s'occuper soi-même de la gestion de la mémoire, de chaîner les éléments, à chaque fois que l'on veut ajouter ou supprimer un élément. La bibliothèque
GLib? propose des listes chaînées génériques que nous allons pouvoir utiliser dans nos applications Gtk+.
2. La liste chaînée simple : GSList
2.1 Structure
Regardons tout d'abord comment est défini cet objet :
struct GSList
{
gpointer data;
struct GSList *next;
};
Nous voyons donc qu'elle nous permet de créer la plus simple des listes chaînées, celle où chaque élément connaît son suivant et rien d'autre.
2.2 Création d'une GSList
Il faut d'abord avoir le pointeur sur le premier élément de la liste. Pour cela, rien de plus simple :
GSList *premier = NULL;
Ensuite, il n'existe pas de fonction spécifique pour créer la liste, il suffit juste d'ajouter un élément à la liste.
2.3 Ajout d'éléments
Plusieurs fonctions sont disponibles mais nous allons en étudier deux.
GSList* g_slist_append (GSList *list, gpointer data);
GSList* g_slist_prepend (GSList *list, gpointer data);
La première g_slist_append ajoute un nouvel élément à la fin de la liste, alors que g_slist_prepend l'ajoute au début de la liste. La variable
list est bien sûr la liste chaînée à laquelle on veut ajouter un élément comportant la donnée
data. Il suffit de faire un cast pour donner le type de
data.
La valeur de retour est très importante : elle correspond à l'adresse du premier élément de la liste. En effet, au départ notre premier élément ne pointe nulle part (premier = NULL), il faut donc toujours récupérer cette adresse (surtout dans le cas de g_slist_prepend où le premier élément change).
2.4 Récupérer les données d'une GSList
Là aussi, nous n'allons étudier que deux fonctions :
GSList* g_slist_nth (GSList *list, guint n);
gpointer g_slist_nth_data (GSList *list, guint n);
Le paramètre
list est, bien sûr, la liste à laquelle l'élément recherché appartient, et
n est la position de l'élément dans la liste (le premier élément est à n=0). Avec ces deux fonctions, il suffit juste de connaître la position d'un élément pour récupérer la donnée qu'il contient.
La première fonction renvoie un pointeur sur une variable du type
GSList. Il faudra donc utiliser l'opérateur -> pour récupérer la valeur
data. La deuxième, par contre, renvoie directement la valeur de
data.
Si la valeur donnée à
n ne fait pas partie de la liste, la valeur de retour sera NULL.
Supposons qu'une variable de type
GtkWidget soit stockée dans le premier élément d'une liste nommé liste, et que l'on veuille récupérer ce widget, il faudra alors coder :
temp_list = g_slist_nth(liste, 0);
widget = GTK_WIDGET(temp_list->data);
ou
widget = GTK_WIDGET(g_slist_nth_data(liste, 0));
2.5 Suppression d'élément d'une GSList
Pour supprimer définitivement un élément d'une liste, la fonction à utiliser est la suivante :
GSList* g_slist_remove (GSList *list, gconstpointer data);
Cette fonction cherche le premier élément de la liste contenant la donnée
data et le supprime. La valeur de retour est, là aussi, très importante car elle correspond (comme précédemment) au nouveau premier élément de la liste. Si par hasard, plusieurs éléments contiennent la donnée
data, seul le premier sera supprimé. Dans ce cas, pour tous les supprimer, il faut utiliser cette fonction (dont l'utilisation est identique à la première) :
GSList* g_slist_remove_all (GSList *list, gconstpointer data);
Pour supprimer une liste entière, la fonction est :
void g_slist_free (GSList *list);
Avec toutes ces fonctions, nous en savons suffisamment pour pouvoir utiliser une liste simple.
3. La liste doublement chaînée : GList
En plus des
GSList, la bibliothèque
GLib? propose un autre type de liste chaînée qui est la
GList. A la différence des
GSList, les
GList sont des listes doublement chaînées. En effet en plus de connaître son élément suivant, chaque élément connaît aussi son élément précédent.
3.1 Structure
Regardons tout d'abord comment est défini cet objet :
struct GList
{
gpointer data;
struct GList *next;
struct GList *prev;
};
3.2 Création d'une GSList
Il faut d'abord avoir le pointeur sur le premier élément de la liste. Pour cela, rien de plus simple :
GList *premier = NULL;
Ensuite, il n'existe pas de fonction spécifique pour créer la liste, il suffit juste d'ajouter un élément à la liste.
3.2 Ajout d'éléments
Plusieurs fonctions sont disponibles mais nous allons en étudier deux.
GList* g_slist_append (GList *list, gpointer data);
GList* g_slist_prepend (GList *list, gpointer data);
La première g_list_append ajoute un nouvel élément à la fin de la liste, alors que g_list_prepend l'ajoute au début de la liste. La variable
list est bien sûr la liste chaînée à laquelle on veut ajouter un élément comportant la donnée
data. Il suffit de faire un cast pour donner le type de
data.
La valeur de retour est très importante : elle correspond à l'adresse du premier élément de la liste. En effet, au départ notre premier élément ne pointe nulle part (premier = NULL), il faut donc toujours récupérer cette adresse (surtout dans le cas de g_list_prepend où le premier élément change).
3.4 Récupérer les données d'une GList
Là aussi, nous n'allons étudier que deux fonctions :
GList* g_list_nth (GList *list, guint n);
gpointer g_list_nth_data (GList *list, guint n);
Le paramètre
list est bien sur la liste à laquelle l'élément recherché appartient, et
n est la position de l'élément dans la liste (le premier élément est à n=0). Avec ces deux fonctions, il suffit juste de connaître la position d'un élément pour récupérer la donnée qu'il contient.
La première fonction renvoie un pointeur sur une variable du type
GList. Il faudra donc utiliser l'opérateur -> pour récupérer la valeur
data. La deuxième, par contre, renvoie directement la valeur de
data.
Si la valeur donnée à
n ne fait pas partie de la liste, la valeur de retour sera NULL.
Supposons qu'une variable de type
GtkWidget soit stockée dans le premier élément d'une liste nommé liste, et que l'on veuille récupérer ce widget, il faudra alors coder :
temp_list = g_list_nth(liste, 0);
widget = GTK_WIDGET(temp_list->data);
ou
widget = GTK_WIDGET(g_list_nth_data(liste, 0));
3.5 Suppression d'élément d'une GList
Pour supprimer définitivement un élément d'une liste, la fonction à utiliser est la suivante :
GList* g_list_remove (GList *list, gconstpointer data);
Cette fonction cherche le premier élément de la liste contenant la donnée
data et le supprime. La valeur de retour est, là aussi, très importante car elle correspond (comme précédemment) au nouveau premier élément de la liste. Si par hasard, plusieurs éléments contiennent la donnée
data, seul le premier sera supprimé. Dans ce cas, pour tous les supprimer, il faut utiliser cette fonction (dont l'utilisation est identique à la première) :
GList* g_list_remove_all (GList *list, gconstpointer data);
Pour supprimer une liste entière, la fonction est :
void g_list_free (GList *list);
Remarque :
Les fonctions g_list_remove() et g_list_remove_all() libèrent la mémoire des données transmises. A contrario, la fonction g_list_free() ne fait que libérer l'espace mémoire utilisé par la liste chaînée. Il faut alors explicitement libérer la mémoire allouée pour les données avant g_list_free(). Une manière simple est élégante de le faire pourrait être :
g_list_foreach(GList *list, (GFunc)g_free, NULL);
g_list_free(GList *list);
Avec toutes ces fonctions, nous en savons suffisamment pour pouvoir utiliser une liste doublement chaînée.
