GLib/GLib Data Types
GString
modifierGString est un type proposé par la GLib, qui encapsule un "char*" standard. L'intérêt est de profiter d'une API autour de ce type, permettant de:
- Gérer une chaine de taille dynamique sans s'occuper de l'allocation mémoire
- Faire intuitivement un certain nombre d'opérations classiques (append, prepend, insertion à un index donné...)
Créez un nouveau fichier source C avec les includes suivants:
#include <stdio.h>
#include <stdlib.h>
#include <glib.h>
Grâce à la GLib, nous pouvons gérer proprement une entrée de taille dynamique sans nous préoccuper de la gestion de la mémoire.
g_string_new est une fonction permettant d'initialiser une structure GString. Elle prend en paramètre un pointeur "char*" classique. g_string_append et g_string_prepend permettent d'ajouter à la fin ou au début d'une GString la chaine donnée en argument.
Écrivons une fonction lisant une entrée de taille dynamique depuis l'entrée standard, et retournant un pointeur vers la structure GString correspondante:
GString* gstring_getLineFromStdin() {
char c = (char) 0;
GString* str = g_string_new( "" );
c = getchar();
while( (c != '\r') && (c != '\n') && (c != EOF) ) {
// g_string_append_c ajoute le caractère donné à une GString
// l'allocation mémoire est gérée par la GLib
str = g_string_append_c(str,c);
c = getchar();
}
return str;
}
Voyons comment utiliser des GString. Pour cela, écrivons un main:
int main(int argc, char* argv[]) {
g_string_new prend en parametre un char* et renvoie un pointeur vers une structure GString.
GString* strCas = g_string_new("cas");
// le membre str de cette structure est un pointeur char* standard.
printf("strCas=%s\n", strCas->str);
La fonction g_string_append concatene une GString avec la chaine donnée en argument. L'allocation mémoire est gérée par la GLib.
strCas = g_string_append(strCas,"soulet");
printf("strCas=%s\n", strCas->str);
La fonction g_string_prepend rajoute la chaine donnée en argument au début d'une GString.
GString* strBurger = g_string_new("burger");
strBurger = g_string_prepend(strBurger,"ham");
printf("strBurger=%s\n", strBurger->str);
Utilisons la fonction que nous avons écris plus haut:
printf("saisissez votre nom: ");
GString* nom = gstring_getLineFromStdin();
printf("Bonjour %s!\nTaille de votre nom: %i\n",nom->str, nom->len);
g_string_free libère la mémoire occupée. Le deuxième argument détermine si le champ str de la GString sera libéré aussi. Si c’est FALSE, il est retourné par la fonction, afin qu'on puisse en disposer.
g_string_free(nom,TRUE);
return 0;
}
GList
modifierLe deuxième type que nous verrons est la GList classique, qui est une liste doublement chainée. Une liste doublement chainée est représentée par un ensemble de nœuds, chacun ayant un pointeur vers le nœud précédent et le nœud suivant.
Les 3 premières fonctions que nous verrons sont:
- g_list_append, qui permet d'ajouter un élément à une liste.
- g_list_length, qui permet de connaitre la taille d'une liste.
- g_list_nth, qui permet d'obtenir un élément en fonction de son index.
Ajouter et obtenir les éléments
modifierFaisons maintenant un programme simple, dans lequel nous verrons comment ajouter, et obtenir les éléments d'une GList à l'aide de ces fonctions.
#include <stdio.h>
#include <stdlib.h>
#include <glib.h>
// Fonction de libération de la mémoire, voir plus bas
void freeFunction(gpointer data) {
free(data);
}
int main(int argc, char* argv[]) {
Initialisons nos variables:
// Déclaration d'un pointeur vers un entier
int* currentEntry = NULL;
// Déclaration d'un compteur
int cpt = 0;
// Déclaration et instantiation d'une GList
GList* list = NULL;
Comme vous l'avez peut être noté, NULL suffit à remplir un pointeur vers une GList vide. En effet, la fonction g_list_append s'occupera d'initialiser ce pointeur lors de l'ajout du premier élément.
glist_append renvoie un pointeur vers la nouvelle adresse de départ de la liste, car celle ci peut changer. Son premier paramètre est un pointeur vers la liste. Son deuxième paramètre est un pointeur vers la donnée à ajouter. Si list vaut NULL, création d'une nouvelle GList.
Nous allons faire saisir 10 nombres à l'utilisateur.
while(cpt < 10) {
// Allocation mémoire pour un nombre entier
currentEntry = malloc(sizeof(int));
// Demande de saisie
printf("veuillez saisir le nombre %i: ",cpt);
scanf("%i",currentEntry);
// Ajout du nombre entier à la liste
/* Cette fonction renvoie un pointeur vers la nouvelle
* adresse de départ de la liste, car celle ci peut changer
*/
list = g_list_append(list,currentEntry);
// Incrémentation du compteur
cpt++;
}
Voyons comment déterminer la taille de la liste et accéder aux éléments par leur index.
printf("démonstration de l'accès aux éléments par leur index:\n");
// g_list_length prend en paramètre une liste et renvoie sa taille
int i = 0;
for( i=0; i<g_list_length(list); i++ ) {
/* g_list_nth prend en paramètre une liste et un index
* et renvoie une structure GList
* dont le membre data est le pointeur vers l'élément contenu
*/
printf("élément %i: %i\n", i, * ((int*) (g_list_nth(list,i)->data)) );
}
g_list_free_full prend en paramètre une GList qu'elle désalouera, en appelant auparavant freeFunction sur chacun de ses éléments. freeFunction est un pointeur de fonction cette fonction ne renvoie rien et prend en paramètre un pointeur vers un élément de notre liste. La fonction freeFunction se chargera de désallouer proprement les éléments qui ont été réservés par malloc.
g_list_free_full(list,freeFunction);
return 0;
}
Rechercher et retirer des éléments
modifierFaisons maintenant un nouveau petit programme dans lequel nous apprendrons à Rechercher et retirer des éléments d'une GList.
Au début de notre programme, remplissons une liste avec quelques chaines de caractères.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <glib.h>
int main(int argc, char* argv[]) {
GList* list = NULL;
char* tagada = "tagada";
char* kebab = "kebab";
char* chocolat = "chocolat";
char* crepe = "crepe";
list = g_list_append (list, tagada);
list = g_list_append (list, kebab);
list = g_list_append (list, chocolat);
list = g_list_append (list, crepe);
printf("La taille de la liste après ajout de 4 éléments est: %i\n",g_list_length(list));
La fonction g_list_remove retire le premier élément dont la valeur est égale à celle fournie en paramètre. g_list_remove prend en paramètre une GList et la valeur à supprimer. La variante g_list_remove_link prend en paramètre la référence du nœud à supprimer.
list = g_list_remove(list,kebab);
printf("Après avoir retiré \"kebab\", la taille de la liste est: %i\n",g_list_length(list));
g_list_position prend en paramètre une GList et un nœud, et renvoie l'index du nœud dans la liste s'il est présent, sinon -1. La fonction g_list_find recherche une valeur dans une GList. Cette fonction compare simplement la valeur de l'élément ajouté. g_list_find prend en paramètre une GList et une valeur à rechercher. Elle renvoie le nœud correspondant si trouvé, sinon NULL.
GList* noeudChocolat = g_list_find(list,chocolat);
if(noeudChocolat != NULL) {
int positionChocolat = g_list_position(list, noeudChocolat);
printf("La position de \"chocolat\" est: %i\n",positionChocolat);
}
Étant donné que nous manipulons généralement des pointeurs, il est judicieux d'étudier sa variante g_list_find_custom, qui prend en dernier paramètre une fonction de comparaison. Nous allons maintenant voir comment rechercher une chaine à l'aide d'une fonction de comparaison.
L'utilisateur devra saisir une chaine de caractère, qui sera recherchée dans la liste.
char input[16];
memset(input,0,16);
printf("Veuillez saisir la chaine à rechercher: ");
scanf("%16s",&input);
g_list_find custom prend un troisième paramètre: une fonction de comparaison. Elle renvoie le nœud trouvé, sinon NULL. Une fonction de comparaison prend deux pointeurs en paramètres, compare les éléments pointés et renvoie un nombre négatif si le premier est inférieur au deuxième, 0 s'ils sont égaux, et un nombre positif s'il est supérieur. C'est précisément ce que fait strcmp avec des chaînes de caractères, nous allons donc l’utiliser.
GList* search = g_list_find_custom(list,&input,(GCompareFunc)strcmp);
if(search != NULL) {
printf("Trouvé!\n");
}
else {
printf("Non trouvé!\n");
}
Enfin, désallouons la liste et terminons notre programme:
g_list_free(list);
return 0;
}
Tri, foreach
modifierPour trier une GList, nous allons utiliser une GCompareFunc. Une GCompareFunc est une fonction de comparaison prenant en paramètre 2 gconstpointer et renvoyant un entier. Cet entier est négatif si le premier argument est inférieur au second, 0 en cas d'égalité, positif sinon. Toute valeur est possible, néanmoins il est de convention pour ce type de fonction de renvoyer -1, 0 et 1.
int trierEntiers(gconstpointer a, gconstpointer b) {
if( *((int*)a) < *((int*)b) ) return -1;
else if ( *((int*)a) == *((int*)b) ) return 0;
else return 1;
}
Faisons maintenant un petit programme qui démontrera comment utiliser le tri et le foreach (boucle itérative).
Son début ressemble à un exemple vu plus haut, plus la fonction de tri ci-dessus.
#include <stdio.h>
#include <stdlib.h>
#include <glib.h>
// Fonction de libération de la mémoire, voir plus bas
void freeFunction(gpointer data) {
free(data);
}
/* Cette fonction est conforme au prototype d'une GCompareFunc
* une GCompareFunc est une fonction prenant en paramètre 2 gconstpointer et renvoyant un entier
* cet entier est négatif si le premier argument est inférieur au second, 0 en cas d'égalité, positif sinon.
* un gconstpointer est un const void*
*/
int trierEntiers(gconstpointer a, gconstpointer b) {
if( *((int*)a) < *((int*)b) ) return -1;
else if ( *((int*)a) == *((int*)b) ) return 0;
else return 1;
}
/* Cette fonction est conforme au prototype d'une GFunc
* Le premier paramètre est l'élément courant d'une GList dans le cadre d'un appel de g_list_foreach,
* Le deuxième argument est commun à chaque appel (troisième argument de g_list_foreach).
*/
void additionnerEntiers(gpointer nb, gpointer total) {
* ((int*)total) += * ((int*)nb);
}
int main(int argc, char* argv[]) {
// Déclaration d'un pointeur vers un entier
int* currentEntry = NULL;
// Déclaration d'un compteur
int cpt = 0;
// Déclaration et instantiation d'une GList
GList* list = NULL;
// Nous allons faire saisir 10 nombres à l'utilisateur
while(cpt < 10) {
// Allocation mémoire pour un nombre entier
currentEntry = malloc(sizeof(int));
// Demande de saisie
printf("veuillez saisir le nombre %i: ",cpt);
scanf("%i",currentEntry);
// Ajout du nombre entier à la liste
/* Cette fonction renvoie un pointeur vers la nouvelle
* adresse de départ de la liste, car celle ci peut changer
*/
list = g_list_append(list,currentEntry);
// Incrémentation du compteur
cpt++;
}
g_list_sort prend en paramètre une GList et une fonction de comparaison.
list = g_list_sort(list, trierEntiers);
printf("Voici les éléments triés:\n");
int i = 0;
for( i=0; i<g_list_length(list); i++ ) {
printf("élément %i: %i\n", i, * ((int*) (g_list_nth(list,i)->data)) );
}
Faisons maintenant un foreach sur notre liste. Un foreach est une boucle qui itère sur chaque élément contenu dans une liste. g_list_foreach est une fonction qui prend en paramètre une GList ainsi qu'un pointeur vers une GFunc (fonction ne renvoyant rien et recevant deux gpointer) et un pointeur vers une donnée commune à chaque appel qui sera effectué (deuxième argument de la GFunc, le premier étant l'élément courant de la liste).
g_list_foreach(list, additionnerEntiers, total);
printf("Le total des nombres saisis est: %i\n",*total);
Terminons proprement l'exécution de notre programme.
// Libération de la liste
/* La fonction freeFunction se chargera de désallouer
* proprement les éléments qui ont été réservés avec malloc
*/
g_list_free_full(list,freeFunction);
return 0;
}
GHashTable
modifierUne hashtable est une collection de données réalisant une association clé/valeur, utilisant en interne un mécanisme de hashage de la clé afin d’en générer un identifiant unique. Ces collections sont très efficaces et permettent souvent de réaliser des optimisations puissantes.
Nous allons étudier les fonctionnalités suivantes:
- ajouter une association clé/valeur
- récupérer une valeur à l'aide de sa clé
- itérer sur la collection
On construit une hashmap en précisant une fonction de hash, une fonction de comparaison, une fonction de désallocation de clé et une fonction de désallocation de valeur.
GHashTable* hashtable = g_hash_table_new_full ( (GHashFunc)g_string_hash, (GEqualFunc)g_string_equal, (GDestroyNotify)free_gstring, freeFunction );
Le code de free_gstring et freeFunction est visible plus bas.
Pour les besoins de ce tutorial, nous allons définir dans le début de notre programme d'exemple quelques fonctions utilitaires. En effet, nous allons réaliser un programme qui compte le nombre occurrences de chaque mot.
Voici le début de ce programme:
#include <stdio.h>
#include <stdlib.h>
#include <glib.h>
// Cette fonction capte ce qui a été poussé en entrée du programme, et le renvoie dans une GString
GString* gstring_getAllFromStdin() {
char c = (char) 0;
GString* str = g_string_new( "" );
while( (c = getchar()) != EOF) {
str = g_string_append_c(str,c);
}
return str;
}
// Cette fonction affiche une entrée de hashtable
void display_entry(gpointer key, gpointer data, gpointer user_data) {
printf("%s : %i\n", ((GString*)key)->str, *((int*)data));
}
// Cette fonction remplace les séparateurs les plus courants par des espaces
void clean_str(GString* gstr) {
int i = 0;
char c = 0;
while(i < gstr->len ) {
c = (gstr->str)[i];
if(c == '\n' || c == '\r' | c == '.' | c == ',' || c == '\t') {
(gstr->str)[i] = ' ';
}
i++;
}
}
// Fonctions de libération de la mémoire
void freeFunction(gpointer data) {
free(data);
}
void free_gstring(GString* data) {
g_string_free(data,TRUE);
}
Voyons comment utiliser la GHashTable:
// Cette fonction renseigne la hashmap avec chaque mot et son nombre d'occurrences
void split_gstring_into_ghashtable(GString* input, GHashTable* hashtable) {
// g_strsplit sert à spliter une chaine
// On récupère un tableau de char*
// PS: gchar est un alias pour char
gchar** split = g_strsplit( input->str, " ", 0 );
// On va utiliser la table de hashage pour compter le nombre d'occurrence de chaque mot
int i = 0;
gchar* current = split[0];
while (current != NULL) {
GString* current_gstr = g_string_new(current);
g_hash_table_lookup cherche la clé dans la hashmap, et retourne la valeur associée si trouvé. Sinon, on obtient NULL
gpointer value = g_hash_table_lookup(hashtable, current_gstr);
// Si lookup n'a rien renvoyé, on doit insérer cette clé dans la hashmap
// donc on doit aussi créer la valeur à insérer avec
if( value == NULL ) {
value = malloc(sizeof(int));
* ((int*)value) = 1;
g_hash_table_insert prend en paramètre une hashtable, la clé, et la valeur.
// si la clé n’est pas une chaine vide, on l'ajoute
if( strcmp( current, "" ) != 0 ) g_hash_table_insert( hashtable, current_gstr, value );
}
// si on a trouvé la valeur associée à la clé, on l'incrémente
else {
(* (int*)value)++;
}
i++;
current = split[i];
}
g_strfreev(split);
}
Et enfin, voici le main:
int main(int argc, char* argv[]) {
GString* input = gstring_getAllFromStdin();
clean_str(input);
// On construit une hashmap en précisant une fonction de hash, une fonction de comparaison,
// une fonction de désallocation de clé et une fonction de désallocation de valeur.
GHashTable* hashtable = g_hash_table_new_full ( (GHashFunc)g_string_hash, (GEqualFunc)g_string_equal, (GDestroyNotify)free_gstring, freeFunction );
split_gstring_into_ghashtable(input,hashtable);
// Itération sur les membres de la hashmap
g_hash_table_foreach( hashtable, display_entry, "useless" );
// Désallocation
g_hash_table_destroy(hashtable);
return 0;
}
