samedi 16 juillet 2022

Queue

Implémentation en C d'une queue dynamique.

Fonctions enqueue, dequeue, ...

Motivation

En cherchant dans le web comment implémenter en C une queue dynamique, je n'ai trouvé que des implémentations utilisant des tableaux, avec l'inénarable «queue overflow». Pourtant ce n'est pas sorcier d'utiliser de vrais pointeurs avec une allocation réellement dynamique de la mémoire.

Il existe cependant dans /usr/include/sys un fichier queue.h qui contient une série de macros qui réalisent cette implémentation. Voir l'excellent article de rosetta code.

Introduction

Prenons l'exemple de relevés de températures intérieure et extérieure. Un enregistrement aurait trois champs t, e, i (temps, température extérieure, température intérieure) :

typedef struct record
{
	float t, e, i; 
} record;

Ajoutons-y un pointeur qui pointe sur une structure de type record :

typedef struct record
{
	float t, e, i; 
	struct record *next;
} record;

Bien que le sujet se prête à des interprétations lubriques, je vais plutôt filer une métaphore bucolique (1)

• tige est l'identifiant de la naissance de la queue, le premier arrivé,
• pousse est un nouveau maillon de la queue,
• dard est le bout de la tige.

Et créons un premier pointeur sur un enregistrement en lui allouant la mémoire nécessaire pour vivre :

	record *tige = (record *)malloc(sizeof(record));
	*tige = (record){5.1, 21.0, 21.1, NULL};

Nous avons là une tige un peu courte réduite à une seule pousse.

Exemple complet

Voici un programme qui initialise une queue, enquille (enqueue) des relevés les relit et nettoie la queue.

/*  temp.c
:w | !gcc % -o %< -Wall
./%<
*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef struct record
{
	float t, e, i;
	struct record *next;
} record;
/* relevés des températures
5.1, 21.9, 21.1
5.6, 21.6, 20.5
6.1, 21.3, 20.1
6.5, 21.0, 19.8
7.0, 20.9, 19.5
*/
int main(int argc, char *argv[]) 
{
	// première pousse (tige est l'identifiant de la queue)
	record *tige = (record *)malloc(sizeof(record)); // espace de vie
	assert(tige != NULL); // si ça foire on arrête là
	*tige = (record){5.1, 21.0, 21.1, NULL}; // tête de la queue
	// deuxième relevé de la queue
	tige->next = (record *)malloc(sizeof(record)); // nouvelle pousse
	assert(tige->next != NULL); // en cas de gel on arrête là
	*tige->next = (record){5.6, 21.6, 20.5, NULL}; // nouveau relevé
	// pour la suite il faut avoir un repère sur la dernière pousse
	record *dard = tige->next; // à ce stade dard est la deuxième pousse
	// ajoutons encore une pousse
	dard->next = (record *)malloc(sizeof(record));
	assert(dard->next != NULL);
	*dard->next = (record){6.1, 21.3, 20.1, NULL};
	// vérifions que la queue est bien dressée
	dard = dard->next; // on tient le dard de la queue
	for(record *r = tige; r != NULL; r = r->next)
		printf("%.1f, %.1f, %.1f\n", r->t, r->e, r->i);
	// Á la fin on libère la mémoire
	record *r;
	while(tige != NULL)
	{
		r = tige;
		tige = tige->next;
		free(r);
	}
}

Commentaires

Ligne 25 : c'est raccourci de tige->t = 5.1; tige->e = 2.1; ... tige->next=NULL;

Ligne 27 : le pointeur tige->next est NULL et est le dernier bout de la queue.

Ligne 29 : je devrais écrire *(tige->next), mais comme l'opérateur de déférencement * a la priorité la plus faible, *tige->next passe.

Ligne 31 : on pouvait se passer de ce pointeur, mais il aurait fallu parcourir la queue du début jusqu'à la fin comme dans la ligne 38 ou dans les lignes 41 et 42.

Remarque : Il n'y a pas encore d'exemple de «dequeue».

Le fichier source est ici queue1.c.

Version améliorée

Source queue2.c.

Cette fois on lit les relevés depuis un fichier. Pour le tester il faut créer un fichier de relevés, par exemple :

5.75, 21.3, 21.3
6.02, 21.1, 20.8
6.5, 21.0, 20.2
7.0, 20.6, 19.7
7.5, 20.9, 19.6
7.75, 21.1, 19.6
8.5, 22.4, 20.1
9.0, 23.3, 20.7

et le passer comme argument de ce programme.

/*  temp.c
:w | !gcc % -o %< -Wall
./%<
*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef struct record
{
	float t, e, i;
	struct record *next;
} record;
int main(int argc, char *argv[]) 
{
	record *tige = (record *)malloc(sizeof(record)); 
	assert(tige != NULL); 
	FILE *fp = fopen(argv[1], "r");
	assert(fp != NULL);
	char buf[64];
	fgets(buf, 64, fp);
	sscanf(buf, "%f, %f, %f\n", &tige->t, &tige->e, &tige->i);
	tige->next = NULL;
	record * dard = tige;
	while(fgets(buf, 32, fp))
	{
		dard->next = (record *)malloc(sizeof(record)); 
		assert(dard->next != NULL);
		sscanf(buf, "%f, %f, %f\n",
			&dard->next->t, &dard->next->e, &dard->next->i);
		dard = dard->next;
		dard->next = NULL;
	}
	for(record *r = tige; r != NULL; r = r->next)
		printf("%.1f, %.1f, %.1f\n", r->t, r->e, r->i);
	// Á la fin on libère la mémoire
	record *r;
	while(tige != NULL)
	{
		r = tige;
		tige = tige->next;
		free(r);
	}
}

Encore un programme queue3.c qui ajoute une représentation graphique des données et qui utilise la librairie graphique gd. Mais ne nous égarons pas, ce n'est pas le sujet de cet article.

Librairie queue

L'application des méthodes vues dans le paragraphe précédent (le premier programme) permettent de construire une librairie queue qui comporte deux fichiers :

• Un fichier header queue.h à inclure dans le source
• Un fichier source queue.c

Par exemple le programme queue2.c peut être réécrit comme suit :

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "queue.h"
typedef struct record
{
	float t, e, i;
	struct record *next;
} record;
int main(int argc, char *argv[]) 
{
	queue q = {NULL, NULL}; // important ! 
	record *r;
	FILE *fp = fopen(argv[1], "r");
	assert(fp != NULL);
	char buf[64];
	while(fgets(buf, 32, fp))
	{
		r = (record *)malloc(sizeof(record)); 
		assert(r != NULL);
		sscanf(buf, "%f, %f, %f\n", &r->t, &r->e, &r->i);
		enqueue(&q, r);
	}
	while(dequeue(&q, (void **)&r))
	{
		printf("%.1f, %.1f, %.1f\n", r->t, r->e, r->i);
		free(r);
	}
}

On le compile selon ses habitudes :

1. Carrément avec gcc queue.c test.c -o test. Il paraît que c'est pas bon pour le disque si c'est un SSD, puique on recompile queue.c à tous les coups.
2. On compile avec gcc queue.o test.c -o test.
   Il faut, au préalable, avoir compilé le fichier objet queue.o avec gcc -o queue.c.
3. Faire un Makefile et compiler avec make.

Remarque : je n'ai pas utilisé free(q) puisque j'ai libéré la mémoire au fur et à mesure, et dqueue se charge de purger ses contenants q_node.