GLib/GLib Data Types

**GLib Data Types**
Leçon : GLib

Chapitre n^o 4
Chap. préc. :	GLib Utilities

En raison de limitations techniques, la typographie souhaitable du titre, « GLib : GLib Data Types
GLib/GLib Data Types », n'a pu être restituée correctement ci-dessus.

GString

GString 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

Le 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

Faisons 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

Faisons 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

Pour 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

Une 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;
}

GLib

GLib Utilities