L'exemple de code est basé sur FreeRTOS V9.0.0

Listes Chaînées dans FreeRTOS

1 Introduction

FreeRTOS utilise une conception de liste chaînée circulaire double pour ses besoins internes. Contrairement aux listes chaînées simples qui ne possèdent que des nœuds successeurs, les listes chaînées doubles offrent à la fois des liens vers les nœuds précédents et suivants.

Il existe deux approches fondamentales pour concevoir des listes chaînées :

Approche 1 : L'élément est intégré dans la structure de la liste

typedef struct element {
    int donnees;
} element_t;

typedef struct liste_noeud {
    liste_noeud* precedent;
    liste_noeud* suivant;
    element_t contexte;
} liste_noeud;

Approche 2 : La structure de liste est incluse dans l'élément

typedef struct liste_noeud {
    liste_noeud* precedent;
    liste_noeud* suivant;
} liste_noeud;

typedef struct element {
    liste_noeud nœud;
    int donnees;
} element_t;

FreeRTOS adopte la deuxième approche, principalement pour connecter les blocs de contrôle de tâche (TCB).

2 Srtuctures de Données

2.1 Structure du Nœud de Liste

/*
 * Définition du type d'objet qu'une liste peut contenir.
 */
struct xELEMENT_LISTE
{
    listPREMIER_VERIFICATION_INTEGRITE_LISTE     /*< Défini à une valeur connue si configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES est à 1. */
    configLIST_VOLATILE TickType_t xValeurElement;   /*< La valeur listée. Utilisée généralement pour trier la liste en ordre décroissant. */
    struct xELEMENT_LISTE * configLIST_VOLATILE pSuivant;   /*< Pointeur vers le prochain élément de la liste. */
    struct xELEMENT_LISTE * configLIST_VOLATILE pPrecedent; /*< Pointeur vers l'élément précédent de la liste. */
    void * pProprietaire;                            /*< Pointeur vers l'objet (généralement un TCB) contenant l'élément de liste. */
    void * configLIST_VOLATILE pConteneur;           /*< Pointeur vers la liste qui contient cet élément. */
    listDEUXIEME_VERIFICATION_INTEGRITE_LISTE        /*< Défini à une valeur connue si configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES est à 1. */
};
typedef struct xELEMENT_LISTE ElementListe_t;

struct xMINI_ELEMENT_LISTE
{
    listPREMIER_VERIFICATION_INTEGRITE_LISTE
    configLIST_VOLATILE TickType_t xValeurElement;
    struct xELEMENT_LISTE * configLIST_VOLATILE pSuivant;
    struct xELEMENT_LISTE * configLIST_VOLATILE pPrecedent;
};
typedef struct xMINI_ELEMENT_LISTE MiniElementListe_t;

ElementListe_t représente un nœud de liste utilisé pour connecter les éléments. Ses composants incluent :

• Les champs de vérification de liste aux extrémités (activés lorsque configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES est à 1)
• xValeurElement : Utilisée pour le tri des éléments, généralement en ordre décroissant
• pSuivant et pPrecedent : Pointeurs vers les nœuds suivant et précédent
• pProprietaire : Pointeur vers l'élément référencé par le nœud, généralement un TCB
• pConteneur : Pointeur vers la Liste_t à laquelle le nœud appartient

MiniElementListe_t est une version allégée du nœud de liste, utilisée pour décrire le nœud final de la liste.

2.2 Structure du Contrôle de Liste

/*
 * Définition du type de liste utilisé par l'ordonnanceur.
 */
typedef struct xLISTE
{
    listPREMIER_VERIFICATION_INTEGRITE_LISTE         /*< Défini à une valeur connue si configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES est à 1. */
    configLIST_VOLATILE UBaseType_t xNombreElements;
    ElementListe_t * configLIST_VOLATILE pIndex;    /*< Utilisé pour parcourir la liste. Pointe vers le dernier élément retourné par listGET_OWNER_OF_NEXT_ENTRY(). */
    MiniElementListe_t xFinListe;                   /*< Élément de liste contenant la valeur maximale, servant de marqueur à la fin. */
    listDEUXIEME_VERIFICATION_INTEGRITE_LISTE        /*< Défini à une valeur connue si configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES est à 1. */
} Liste_t;

Cette structure décrit les informations de la liste :

• Champs de vérification aux extrémités (activés selon la configuration)
• xNombreElements : Nombre d'éléments dans la liste
• pIndex : Pointeur vers le nœud actuel pour le parcours
• xFinListe : Nœud final utilisé comme marqueur

3 Fonctions d'Interface

3.1 Initialisation de Liste

void vListInitialiser(Liste_t * const pListe)
{
    /* La structure de liste contient un élément servant de marqueur de fin.
     Pour initialiser, on insère cet élément comme seule entrée. */
    pListe->pIndex = (ElementListe_t *) &(pListe->xFinListe);
    
    /* La valeur maximale est assignée au marqueur de fin pour qu'il reste à la fin. */
    pListe->xFinListe.xValeurElement = portMAX_DELAY;
    
    /* Les pointeurs suivant et précédent du marqueur pointent sur lui-même. */
    pListe->xFinListe.pSuivant = (ElementListe_t *) &(pListe->xFinListe);
    pListe->xFinListe.pPrecedent = (ElementListe_t *) &(pListe->xFinListe);
    
    pListe->xNombreElements = (UBaseType_t) 0U;
    
    /* Assignation de valeurs de vérification si activé. */
    listDEFINIR_VERIFICATION_INTEGRITE_LISTE_1(pListe);
    listDEFINIR_VERIFICATION_INTEGRITE_LISTE_2(pListe);
}

3.2 Initialisation d'Élément de Liste

void vListInitialiserElement(ElementListe_t * const pElement)
{
    /* S'assurer que l'élément n'est pas enregistré dans une liste. */
    pElement->pConteneur = NULL;
    
    /* Assignation de valeurs de vérification si activé. */
    listDEFINIR_PREMIER_VERIFICATION_ELEMENT_LISTE(pElement);
    listDEFINIR_DEUXIEME_VERIFICATION_ELEMENT_LISTE(pElement);
}

3.3 Insertion dans une Liste

FreeRTOS propose deux méthodes d'insertion : insertion après un élément spécifique et insertion ordonnée.

3.3.1 Insertion après un élément spécifique

void vListInsererFin(Liste_t * const pListe, ElementListe_t * const pNouvelElement)
{
    ElementListe_t * const pIndex = pListe->pIndex;
    
    /* Vérification de l'intégrité des structures. */
    listTESTER_INTEGRITE_LISTE(pListe);
    listTESTER_INTEGRITE_ELEMENT_LISTE(pNouvelElement);
    
    /* Insertion sans tri, l'élément devient le dernier à être traité. */
    pNouvelElement->pSuivant = pIndex;
    pNouvelElement->pPrecedent = pIndex->pPrecedent;
    
    pIndex->pPrecedent->pSuivant = pNouvelElement;
    pIndex->pPrecedent = pNouvelElement;
    
    /* Mémorisation de la liste parente. */
    pNouvelElement->pConteneur = (void *) pListe;
    
    (pListe->xNombreElements)++;
}

3.3.2 Insertion ordonnée

void vListInserer(Liste_t * const pListe, ElementListe_t * const pNouvelElement)
{
    ElementListe_t *pIterateur;
    const TickType_t xValeurInsertion = pNouvelElement->xValeurElement;
    
    /* Vérification de l'intégrité des structures. */
    listTESTER_INTEGRITE_LISTE(pListe);
    listTESTER_INTEGRITE_ELEMENT_LISTE(pNouvelElement);
    
    /* Insertion triée selon xValeurElement. */
    if(xValeurInsertion == portMAX_DELAY)
    {
        pIterateur = pListe->xFinListe.pPrecedent;
    }
    else
    {
        for(pIterateur = (ElementListe_t *) &(pListe->xFinListe); 
            pIterateur->pSuivant->xValeurElement <= xValeurInsertion; 
            pIterateur = pIterateur->pSuivant)
        {
            /* Parcours jusqu'à la position d'insertion. */
        }
    }
    
    pNouvelElement->pSuivant = pIterateur->pSuivant;
    pNouvelElement->pSuivant->pPrecedent = pNouvelElement;
    pNouvelElement->pPrecedent = pIterateur;
    pIterateur->pSuivant = pNouvelElement;
    
    /* Mémorisation de la liste parente. */
    pNouvelElement->pConteneur = (void *) pListe;
    
    (pListe->xNombreElements)++;
}

3.4 Suppression d'un Élément

UBaseType_t vListSupprimer(ElementListe_t * const pElementASupprimer)
{
    Liste_t * const pListe = (Liste_t *) pElementASupprimer->pConteneur;
    
    pElementASupprimer->pSuivant->pPrecedent = pElementASupprimer->pPrecedent;
    pElementASupprimer->pPrecedent->pSuivant = pElementASupprimer->pSuivant;
    
    /* Ajustement de l'index si nécessaire. */
    if(pListe->pIndex == pElementASupprimer)
    {
        pListe->pIndex = pElementASupprimer->pPrecedent;
    }
    
    pElementASupprimer->pConteneur = NULL;
    (pListe->xNombreElements)--;
    
    return pListe->xNombreElements;
}

4 Macros Utilitaires

// Définition du propriétaire d'un élément de liste (généralement un TCB)
#define listDEFINIR_PROPRIETAIRE_ELEMENT(pxElement, pxProprietaire)  ((pxElement)->pProprietaire = (void *) (pxProprietaire))

// Récupération du propriétaire d'un élément de liste
#define listOBTENIR_PROPRIETAIRE_ELEMENT(pxElement)  ((pxElement)->pProprietaire)

// Définition de la valeur d'un élément de liste
#define listDEFINIR_VALEUR_ELEMENT(pxElement, xValeur)  ((pxElement)->xValeurElement = (xValeur))

// Récupération de la valeur d'un élément de liste
#define listOBTENIR_VALEUR_ELEMENT(pxElement)  ((pxElement)->xValeurElement)

// Récupération de la valeur du premier élément
#define listOBTENIR_VALEUR_TETE_LISTE(pxListe)  (((pxListe)->xFinListe).pSuivant->xValeurElement)

// Récupération du premier élément
#define listOBTENIR_TETE_LISTE(pxListe)  (((pxListe)->xFinListe).pSuivant)

// Récupération de l'élément suivant
#define listOBTENIR_SUIVANT(pxElement)  ((pxElement)->pSuivant)

// Récupération du marqueur de fin
#define listOBTENIR_FIN_LISTE(pxListe)  ((ElementListe_t const *) (&((pxListe)->xFinListe)))

// Vérification si la liste est vide
#define listLISTE_VIDE(pxListe)  ((BaseType_t) ((pxListe)->xNombreElements == (UBaseType_t) 0))

// Récupération de la longueur de la liste
#define listLONGUEUR_COURANTE(pxListe)  ((pxListe)->xNombreElements)

// Parcours de la liste
#define listOBTENIR_PROPRIO_ENTRE_SUIVANT(pxTCB, pxListe)                                     \
{                                                                                           \
    Liste_t * const pxListeConst = (pxListe);                                                \
    /* Incrémentation de l'index et retour de l'élément, en évitant le marqueur de fin. */     \
    (pxListeConst)->pIndex = (pxListeConst)->pIndex->pSuivant;                               \
    if((void *) (pxListeConst)->pIndex == (void *) &((pxListeConst)->xFinListe))             \
    {                                                                                       \
        (pxListeConst)->pIndex = (pxListeConst)->pIndex->pSuivant;                           \
    }                                                                                       \
    (pxTCB) = (pxListeConst)->pIndex->pProprietaire;                                         \
}

// Récupération du propriétaire du premier élément
#define listOBTENIR_PROPRIETAIRE_TETE(pxListe)  ((&((pxListe)->xFinListe))->pSuivant->pProprietaire)

// Vérification si un élément est contenu dans une liste
#define listEST_CONTENU_DANS(pxListe, pxElement)  ((BaseType_t) ((pxElement)->pConteneur == (void *) (pxListe)))

// Récupération de la liste parente à partir d'un élément
#define listOBTENIR_CONTENEUR_ELEMENT(pxElement)  ((pxElement)->pConteneur)

// Vérification si la liste est initialisée
#define listLISTE_INITIALISEE(pxListe)  ((pxListe)->xFinListe.xValeurElement == portMAX_DELAY)