---

Interface de gestion de listes
[Implémentation de FRED]

Ce module est une gestion de liste FIFO. Plus de détails...

Composants
struct	FredCell
	descripteur de cellule de liste Plus de détails...
struct	FredList
	descripteur de liste Plus de détails...
Définitions des macros
#define	NIL   ((FredCell*)0)
	macro pour définir le pointeur vide
#define	FredCELL   FredCell _cell
	macro pour définir une structure comme une cellule de liste
#define	FredListEmpty(Q)   (((Q)->last) == (FredCell*)0)
	Test de file vide.
Définitions des types
typedef FredCell	FredCell
	descripteur de cellule de liste
typedef FredList	FredList
	descripteur de liste
Fonctions
void	FredListPutLast (FredList *q, FredCell *b)
	Insertion en queue d'une cellule.
FredCell *	FredListGetFirst (FredList *q)
	Retrait de la cellule de tête.
void	FredListInit (FredList *q)
	Initialisation de la liste.

---

Description détaillée

Elle est implantée comme une liste circulaire doublement chaînée avec insertion en queue et retrait en tête.

---

Documentation de la macro

#define FredCELL   FredCell _cell

Pour définir une structure qyelconque comme pouvant être insérer dans une liste, il suffit d'insérer FredCELL en premiere définition des composants de la structure struct MyCell{ FredCELL; int x; int y; ... };

#define FredListEmpty (  Q    )     (((Q)->last) == (FredCell*)0)

#define NIL   ((FredCell*)0)

---

Documentation du type

typedef struct FredCell FredCell

Dans une liste circulaire à 1 élément, celui ci est son propre successeur et prédécesseur. Il est donc doublement rechainé sur lui-même.

typedef struct FredList FredList

Une liste circulaire pointe sur le dernier élément. Pour une liste vide, ce derrnier élément est nul.

---

Documentation de la fonction

FredCell* FredListGetFirst (  FredList *    q )

Paramètres: q  liste où retirer Renvoie : cellule retirer Implantation Le retrait en tête nécessite de traiter le cas d'une file vide et le cas d'une file à 1 élément. Le cas d'une file à 2 cellules qui devient à 1 cellule(qui est chainée sur elle même) peut se traiter comme le cas général. { FredCell* b; if(FredListEmpty(q)){ /* file vide */ return NIL; }else if ( q->last->next==q->last){ /* file à 1 item */ b=q->last; q->last=NIL; /* la file devient vide */ }else { b=q->last->next; b->pred->next=b->next; b->next->pred=b->pred; } b->next=b->pred=NIL; /* la cellule n'est plus chainée */ return b; }

void FredListInit (  FredList *    q )

Paramètres: q  liste à initialiser Implantation { q->last=NIL; }

void FredListPutLast (  FredList *    q, FredCell *    b )

Paramètres: q  liste où insérer b  cellule à insérer Implantation L'insertion en queue place la nouvelle cellule entre le dernier et le premier. Elle devient le nouveau dernier item. Deux cas particuliers sont la file vide et la file à une cellule (qui est chainée sur elle même). Ce dernier cas peut se programmer comme le cas général. { if(FredListEmpty(q)){ /* file vide */ b->next=b->pred=b; q->last=b; }else{ b->next=q->last->next; b->pred=q->last; b->next->pred=b; b->pred->next=b; q->last=b; } }

---