Aujourd'hui, nous allons nous intéresser à deux types de données terriblement pratiques proposés par la Glib-2.0. Ce sont les tableaux dynamiques (empruntés à des langages «haut niveau») et les hashs (empruntés à Perl).

Les tableaux dynamiques de la Glib-2.0 allient le meilleur des tableaux statiques du C et des listes chaînées. La contrepartie est une faible surconsommation de la mémoire et une légère lourdeur syntaxique.

On utilisera un tableau dynamique lorsque le nombre d'éléments que ce tableau devra contenir n'est pas connu au moment de la création du tableau. Les éléments d'un tableau dynamique peuvent être de n'importe quel type mais doivent tous avoir la même taille.

Le paramètre taille_element représente la taille d'un élément du tableau, en octets. fin_par_NULL indique si l'on souhaite que le tableau soit automatiquement terminé par un élément nul, c'est-à-dire une zone mémoire de taille_element octets, tous égaux à zéro ; dans ce cas, il faut mettre fin_par_NULL à TRUE. Dans le cas contraire (si fin_par_NULL vaut FALSE), le seul moyen de connaître la taille du tableau sera de consulter le champ len de la structure GArray. Le paramètre mise_a_zero, s'il vaut TRUE, indique que l'on souhaite que tous les éléments soient initialisés à zéro lors de leur création. La fonction g_array_new() renvoie un pointeur sur le tableau nouvellement créé. Ce tableau est initialement vide et aucune place mémoire n'est réservée pour y stocker des éléments. C'est généralement ce que l'on veut. Cependant, si, au moment de la création du tableau, on sait déjà qu'il va devoir contenir plusieurs milliers d'éléments, il est possible d'optimiser un peu les choses. En effet, plutôt que de partir d'un tableau vide et de le remplir par la suite en ajoutant les éléments un à un (ce qui est lent, puisque la Glib-2.0 devra réserver de la mémoire pour chacun des éléments introduits), il est possible de réserver de la mémoire pour un certain nombre d'éléments au moment de la création du tableau. Pour ceci, il suffit d'utiliser la fonction suivante:

Le paramètre supplémentaire, pre_reserves, indique la taille mémoire qui devra être pré-réservée (en nombre d'éléments). Attention ! Le tableau créé est toujours vide, simplement l'insertion des pre_reserves premiers éléments se fera très rapidement.

Justement, voyons maintenant comment insérer des éléments dans un tableau dynamique. Il existe six fonctions pour faire cela, suivant le nombre d'éléments que l'on souhaite insérer et l'endroit de cette insertion dans le tableau. Ainsi, pour insérer un élément à la fin du tableau, on utilisera la fonction suivante:

Vous remarquerez que l'element ajouté n'a pas de type précis. La fonction g_array_append_val() (qui est en réalité une macro, mais ne chipotons pas...) s'occupe elle-même de vérifier et d'adapter la taille du tableau avant de placer le nouvel element à la fin du tableau.

Le paramètre premier_element est l'adresse du premier élément que l'on souhaite ajouter et nb_elements est le nombre d'éléments que l'on souhaite ajouter en une seule opération. Ces éléments doivent être consécutifs en mémoire, c'est-à-dire que l'adresse du deuxième élément doit être égale à l'adresse du premier élément, plus la taille d'un élément. g_array_append_vals() est donc très pratique pour copier un tableau (que ce soit un tableau statique du C standard ou un tableau dynamique de la Glib-2.0) vers une partie d'un tableau dynamique.

De façon similaire, les deux fonctions suivantes permettent d'ajouter un ou plusieurs élément(s) au début d'un tableau. Les autres éléments, présents avant l'insertion, sont décalés vers la fin du tableau.

Les deux fonctions suivantes, quant à elles, permettent l'insertion d'un ou plusieurs élément(s) au milieu d'un tableau, à partir d'un index donné:

Bien évidemment, il est possible d'accéder à chacun des éléments du tableau à l'aide de la macro suivante:

où tableau est notre tableau dynamique (de type GArray *), type est le type des éléments du tableau, et index, le numéro de l'élément auquel on souhaite accéder.

Lorsque l'on n'a plus besoin du tableau, on peut libérer la mémoire qu'il utilisait à l'aide de la fonction :

Le paramètre libere_donnee, s'il vaut TRUE, indique que l'on souhaite vraiment que la place occupée par les éléments du tableau soit libérée de la mémoire, sinon g_array_free() renvoie un pointeur sur le premier élément de cet espace mémoire qui peut alors être considéré comme un tableau statique, qui devra être libéré par un g_free().

Il est possible de redimensionner un tableau dynamique à tout moment à l'aide de la fonction suivante:

Le paramètre longueur indique la nouvelle taille du tableau en nombre d'éléments. Si la nouvelle taille est inférieure à l'ancienne, les éléments supplémentaires sont perdus, sinon des nouveaux éléments (nuls si le tableau a été créé avec mise_a_zero à TRUE) sont créés.

Il est également possible de supprimer un élément du tableau, à partir de son index, avec la fonction:

Tous les éléments suivants l'élément supprimé sont décalés vers le début du tableau afin de garder la continuité et l'ordre des éléments. Cela peut être un peu lent si le tableau est très grand. Donc, si l'ordre des éléments n'est pas important, il vaut mieux utiliser la fonction suivante:

Avec cette fonction, l'élément supprimé est remplacé par le dernier élément du tableau, ce qui permet de «boucher le trou» très rapidement, sans décaler les autres éléments.

Enfin, une fois un tableau dynamique constitué, il est possible d'en trier les éléments avec:

Le paramètre fonction_comparaison doit être une fonction permettant de classer deux éléments. Son prototype doit être le suivant:

où a et b sont deux pointeurs sur des éléments du tableau. Cette fonction doit renvoyer une valeur positive si a doit être classé avant b et une valeur négative dans le cas contraire.

Il est même possible d'utiliser une fonction de comparaison plus complexe si l'on trie le tableau avec la fonction suivante:

Le comportement de g_array_sort_with_data() est similaire à celui de g_array_sort(). Simplement, le paramètre supplémentaire donnee_sup est transmis à la fonction de comparaison. Cela peut être utile, par exemple, pour utiliser la même fonction de comparaison pour trier un tableau par ordre croissant et décroissant, comme nous le verrons dans notre exemple.

Comme les tableaux de pointeurs sont très utilisés en C, la Glib-2.0 prévoit une interface simplifiée pour les tableaux dynamiques de pointeurs.

Cette fonction ajoute le pointeur à la fin du tableau. Il n'y a pas de fonction particulière permettant d'ajouter un nouveau pointeur au début ou au milieu du tableau ou encore pour ajouter plusieurs pointeurs d'un seul coup.

Comme pour les tableaux «normaux», on peut accéder à un pointeur particulier du tableau à partir de son index à l'aide de la macro suivante:

De même, on peut libérer la place occupée par un tableau de pointeurs ou simplement changer sa taille à l'aide, respectivement, des deux fonctions suivantes:

Pour enlever un pointeur du tableau, en connaissant son index, on retrouve les deux fonctions suivantes:

Mais il est également possible de retirer un pointeur directement d'après sa valeur, à l'aide des deux fonctions suivantes:

Ces deux fonctions se comportent de la même façon que les deux précédentes, mais elles suppriment la première occurrence du pointeur dans le tableau. Elles renvoient TRUE si le pointeur a été trouvé et correctement supprimé et FALSE dans le cas contraire.

Enfin, il est également possible de trier les tableaux de pointeurs, comme les autres types de tableaux à l'aide des deux fonctions suivantes:

Il existe aussi une interface simplifiée pour les tableaux dynamiques de guint8 (d'octets non signés). Les fonctions utilisées pour cela ressemblent grandement à celles des tableaux de pointeurs. Simplement, elles commencent par «g_byte_array_». Je ne les détaillerai pas ici puisque les tableaux d'octets sont bien souvent mieux représentés par des chaînes de caractères ou par les GStrings de la Glib-2.0, que nous étudierons prochainement.

Voyons maintenant comment utiliser les fonctions des tableaux dynamiques dans un exemple:

Regardez bien ce qu'il affiche, et essayez de bien comprendre la dernière ligne affichée.

Les hashs, ou «tables de hashage», sont des structures permettant de stocker des données sans ordre particulier. Chaque donnée est associée à une clef qui doit permettre de retrouver la donnée. Cette clef est souvent une chaîne de caractères, mais elle peut être à peu près n'importe quoi. Il suffit simplement qu'elle soit suffisamment discriminante pour que l'on puisse retrouver la donnée sans ambiguïté.

Les hashs stockent les données dans une structure à deux niveaux afin de retrouver très rapidement une donnée en fonction de sa clef. Tout d'abord, la clef est passée au travers d'une «fonction de hashage» qui renvoie un nombre entier. Ce nombre indique dans quelle partie du hash se trouve la donnée. La recherche de la donnée peut alors se faire uniquement dans cette partie du hash, qui est normalement aussi petite que possible.

Les deux paramètres de g_hash_table_new() sont des pointeurs sur des fonctions. Le premier, fonction_hashage est la fonction de hashage du hash que l'on veut créer. Son prototype doit être le suivant:

Elle doit donc prendre en paramètre un pointeur quelconque, qui est la clef associée à une donnée, et renvoyer un entier dépendant de cette clef. Il n'y a pas de règle absolue pour écrire cette fonction. L'idéal serait qu'elle répartisse au mieux l'ensemble des clefs que le hash contiendra. Ainsi, si le hash doit contenir une centaine de clefs et que la fonction de hashage ne renvoie que dix nombres différents, l'idéal serait que dix clefs renvoient chacun des nombres. Dans la pratique, cela est quasiment impossible si l'on ne connaît pas à l'avance l'ensemble de toutes les clefs. En fait, le plus simple (et le plus sage) est d'utiliser des fonctions existantes que l'on trouve dans la littérature appropriée, ou directement dans la Glib-2.0. Par exemple, si nos clefs sont des chaînes de caractères, on peut utiliser la fonction prédéfinie g_str_hash() comme fonction de hashage. De même, pour des clefs numériques, on peut utiliser g_int_hash().

Cette fonction doit renvoyer TRUE si les deux clefs a et b sont égales, et FALSE sinon. Ici aussi, le plus simple est d'utiliser les fonctions fournies par la Glib-2.0, à savoir g_str_equal() pour des clefs alphanumériques et g_int_equal() pour des clefs numériques.

Les deux premiers paramètres ont le même sens pour la fonction g_hash_table_new(). Les deux derniers sont des fonctions qui seront appelées pour éventuellement libérer la mémoire utilisée respectivement par une clef et sa donnée associée lors du retrait de la donnée du hash ou lors de la destruction hash. Souvent, on n'a besoin de libérer la mémoire que pour la donnée (ou que pour la clef) ; on peut alors mettre l'un de ces paramètres à NULL.

Une fois la table de hashage créée à l'aide des fonctions précédentes, on peut commencer à y ajouter des données, par exemple à l'aide de la fonction suivante:

Les paramètres clef et donnee peuvent être de nature quelconque, mais comme indiqué précédemment, clef est souvent une chaîne de caractères ou un entier. Si la clef existe déjà dans le hash, sa donnée associée est remplacée par la donnee passée en paramètre ; dans ce cas, si fonction_destruction_valeur() a été définie lors de la création de la table de hashage, l'ancienne donnée est libérée à l'aide de cette fonction, et si fonction_destruction_clef() a été définie, le paramètre clef est libéré par cette fonction.

Cette fonction est très semblable à g_hash_table_insert(), sauf lorsque la clef donnée en paramètre est déjà dans le hash. Dans ce cas là, c'est l'ancienne clef qui est libérée avec fonction_destruction_clef(), et la nouvelle clef remplace l'ancienne. En règle générale, g_hash_table_insert() et g_hash_table_replace() sont équivalentes. Pour comprendre la différence entre ces deux fonctions, il faut garder à l'esprit que les clefs sont comparées à l'aide de la fonction fonction_comparaison, qui n'est pas forcément une fonction d'égalité stricte.

Pour retirer une donnée et sa clef associée d'une table de hashage, il suffit d'utiliser la fonction suivante:

Si la clef est trouvée dans le hash, cette fonction renvoie TRUE et la clef et la donnée sont éventuellement libérées grâce aux fonctions fonction_destruction_clef() et fonction_destruction_valeur(). Si la clef n'est pas trouvée, cette fonction renvoie FALSE.

Il est également possible de réaliser la même opération sans que la mémoire utilisée par la clef et la donnée ne soit libérée. C'est le rôle de la fonction suivante:

Bien entendu, il est possible de retrouver les données que l'on a placées dans une table de hashage. La façon la plus simple est en général d'utiliser la fonction suivante:

Cette fonction renvoie tout simplement la donnée associée à la clef ou NULL si la clef n'est pas trouvée dans le hash.

Cependant, NULL peut être une donnée valide. Il devient alors impossible de savoir si une donnée dont la valeur est NULL a été trouvée ou si NULL est renvoyé pour indiquer que la donnée n'a pas été trouvée. Il faut alors utiliser la fonction suivante:

Le paramètre clef indique toujours la clef de la donnée que l'on recherche, mais cette fois-ci, la donnée est renvoyée dans le pointeur donnee. De plus, la clef associée à la donnée est renvoyée dans le pointeur clef_originale, ce qui peut être utile dans le cas où les clefs sont identiques dans le sens de la fonction fonction_comparaison(), alors qu'elles sont physiquement différentes. Enfin, cette fonction renvoie TRUE si la clef a été trouvée et FALSE sinon.

Comme pour la plupart des structures de données proposées par la Glib-2.0, il est possible d'appeler une fonction ayant pour paramètre chacune des données présentes dans le hash. Cela se fait à l'aide de la fonction suivante:

La fonction fonction est appelée pour chacune des données du hash sans ordre particulier. Cette fonction doit avoir le prototype suivant:

Les paramètres clef et donnee sont les clefs et données successives du hash et donnee_sup est la donnée supplémentaire passée comme troisième paramètre à la fonction g_hash_table_foreach().

Dans le même ordre d'idées, la fonction suivante permet de supprimer toutes ou seulement une partie des données d'une table de hashage:

Un peu comme g_hash_table_foreach(), cette fonction appelle la fonction fonction pour chacune des paires clef/donnée du hash. Cette fonction doit avoir le prototype suivant:

Les paramètres de cette fonction ont le même sens que pour la fonction de g_hash_table_foreach(). Si la valeur de retour de cette fonction est TRUE, la donnée et sa clef sont retirées du hash et les éventuelles fonctions de libération de mémoire sont appelées. Si la fonction renvoie FALSE, rien ne se passe, et le processus continue avec la donnée suivante.

De même que pour g_hash_table_remove(), il est possible d'effectuer la même opération sans appeler les fonctions de libération de mémoire avec la fonction suivante:

Toutefois, pour retirer complètement toutes les données d'un hash, libérer la mémoire des données et des clefs, et détruire la table de hashage en une seule fois, le plus efficace sera d'utiliser la fonction suivante:

Voyons maintenant comment utiliser toutes ces fonctions dans un programme exemple: