Getting Started with FreeRTOS: A Guide to Writing Doubly Linked Lists

Getting Started with FreeRTOS: A Guide to Writing Doubly Linked Lists

by

Abstract: A few days ago, I talked about single linked lists, today I will discuss doubly linked lists in conjunction with the FreeRTOS linked list source code.

Note: A linked list item is a node, and a node is a linked list item, they refer to the same thing, it doesn’t matter what you call it.

1. Define the Linked List Structure

// Define the linked list, which is also the linked list head
typedef struct xLIST
{  
    volatile unsigned   int uxNumberOfItems;   
    ListItem_t *  pxIndex; 
    MiniListItem_t xListEnd;                          
} List_t;

2. Define Mini Node Item

The mini node is also a node, but it is only used to mark the end of the linked list and to attach other nodes inserted into the linked list. The user does not need to use the mini node; the head node and ordinary nodes can be different.

typedef struct xMINI_LIST_ITEM
{
    volatile unsigned   int xItemValue;   /* Auxiliary value used to help nodes sort in ascending order. */
    struct xLIST_ITEM   * pxNext; 
    struct xLIST_ITEM   * pxPrevious;
}MiniListItem_t;

The following head is also the definition of the linked list, and the head node can be different from ordinary nodes.

Getting Started with FreeRTOS: A Guide to Writing Doubly Linked Lists

3. Define Nodes

Nodes in FreeRTOS are called linked list items.

// Define linked list nodes
typedef struct xLIST_ITEM
{       
    volatile unsigned   int  xItemValue;          
    struct xLIST_ITEM *  pxNext;     
    struct xLIST_ITEM *  pxPrevious; 
    void * pvOwner;                       // Used to point to the owner of this node              
    struct xLIST *  pxContainer;          // Used to point to the linked list this node belongs to, usually points to the root node of the linked list
              
}ListItem_t;
Getting Started with FreeRTOS: A Guide to Writing Doubly Linked Lists

4. Initialize the Linked List

Initializing the linked list means assigning values to the various parameters of the head node.

void vListInitialise( List_t * const pxList)
{
    /* When initializing, the number of items in the list is 0 (excluding xListEnd) */
    pxList->uxNumberOfItems = 0;    
    /* At initialization, the list only contains xListEnd, so pxIndex points to xListEnd */
    pxList->pxIndex = (ListItem_t *) &(pxList->xListEnd); 
    /* The value of xListEnd is initialized to the maximum value, used for ascending order sorting of list items, placed at the end */
    pxList->xListEnd.xItemValue = portMAX_DELAY;    
    /* At initialization, the list only contains xListEnd, so the previous and next list items are both xListEnd itself */
    pxList->xListEnd.pxNext =(ListItem_t *) &(pxList->xListEnd); 
    pxList->xListEnd.pxPrevious = (ListItem_t *) &(pxList->xListEnd); 
}
Getting Started with FreeRTOS: A Guide to Writing Doubly Linked Lists
The meanings of the two images are the same

5. Initialize Nodes

void vListInitialiseItem(ListItem_t * const pxItem )
{
   /* At initialization, the list item’s container list is set to NULL */
    pxItem->pxContainer = NULL;
}
Getting Started with FreeRTOS: A Guide to Writing Doubly Linked Lists
Getting Started with FreeRTOS: A Guide to Writing Doubly Linked Lists

6. Insert Nodes at the End of the Linked List

void vListInsertEnd( List_t * const pxList,ListItem_t * const pxNewListItem )
{
    /* Get the list item pointed to by pxIndex */
    ListItem_t * const headEnd = pxList->pxIndex;
    /* Update the pointer members of the new list item to be inserted */
    pxNewListItem->pxNext = headEnd;
    pxNewListItem->pxPrevious = headEnd->pxPrevious;
    /* Update the pointer members of the original list item in the list */
    headEnd->pxPrevious->pxNext = pxNewListItem;
    headEnd->pxPrevious = pxNewListItem;
        /* Mark the list member variable of the new item being inserted */
    pxNewListItem->pxContainer = pxList;
   /* Increment the count of items in the list */
    (pxList->uxNumberOfItems)++;
}

This function inserts the new list item before the list item pointed to by pxIndex. It is important to note that pxIndex may not point to xListEnd, but could point to any item in the list.

Let me draw a picture to explain it!

Getting Started with FreeRTOS: A Guide to Writing Doubly Linked Lists
Getting Started with FreeRTOS: A Guide to Writing Doubly Linked Lists
Getting Started with FreeRTOS: A Guide to Writing Doubly Linked Lists

7. Insert and Sort Linked List Nodes

void vListInsert( List_t * const pxList,ListItem_t * const pxNewListItem )
{
    ListItem_t * pxIterator;
    const int xValueOfInsertion = pxNewListItem->xItemValue;

    /* If the value of the new item to be inserted is the maximum value */
    if( xValueOfInsertion == portMAX_DELAY)
    {
        /* The insertion position is before xListEnd */
        pxIterator = pxList->xListEnd.pxPrevious;
    }
    else
    {
         /* Traverse the list to find the insertion position */
        for( pxIterator = (ListItem_t*)&(pxList->xListEnd); pxIterator->pxNext->xItemValue <= xValueOfInsertion; pxIterator = pxIterator->pxNext )
        {
        
        }
    }
 /* Insert the new node after pxIterator according to ascending order */   
    pxNewListItem->pxNext = pxIterator->pxNext;
    pxNewListItem->pxNext->pxPrevious = pxNewListItem;
    pxNewListItem->pxPrevious = pxIterator;
    pxIterator->pxNext = pxNewListItem;
     
    /* Remember the linked list this node belongs to */
    pxNewListItem->pxContainer = pxList;
   /* Increment the linked list node counter */
    ( pxList->uxNumberOfItems )++;
}

Before inserting the new list item into the list, we first traverse the list to find the position where the new list item needs to be inserted. The position for the new item is determined based on the values of the list items in ascending order.

Getting Started with FreeRTOS: A Guide to Writing Doubly Linked Lists

8. Delete Linked List Nodes

int uxListRemove( ListItem_t * const pxItemToRemove )
{
 /* Get the linked list the node belongs to */
    List_t * const pxList = pxItemToRemove->pxContainer;
 
 /* Remove the specified node from the linked list*/
    pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;
    pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;


    /* If pxIndex is pointing to the item to be removed */
    if( pxList->pxIndex == pxItemToRemove )
    {
        /* pxIndex points to the previous item */
        pxList->pxIndex = pxItemToRemove->pxPrevious;
    }
    else
    {

    }
   /* Clear the container pointer of the item to be removed */
    pxItemToRemove->pxContainer = NULL;
   /* Decrement the linked list node counter */
    ( pxList->uxNumberOfItems )--;
   /* Return the number of remaining nodes in the linked list */
    return pxList->uxNumberOfItems;
}

To delete a node, you must first find the node.

Getting Started with FreeRTOS: A Guide to Writing Doubly Linked Lists
Getting Started with FreeRTOS: A Guide to Writing Doubly Linked Lists

It should be noted that after the uxListRemove() function removes the list item, the remaining list items still have a unidirectional link, meaning that the pointers used to point to the previous and next list items still point to the list items in the list.

9. Example

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

// Define linked list nodes
typedef struct xLIST_ITEM
{       
    volatile unsigned   int  xItemValue;          
    struct xLIST_ITEM *  pxNext;     
    struct xLIST_ITEM *  pxPrevious; 
    void * pvOwner;                       // Used to point to the owner of this node              
    struct xLIST *  pxContainer;          // Used to point to the linked list this node belongs to, usually points to the root node of the linked list
              
}ListItem_t;

typedef struct xMINI_LIST_ITEM
{
    volatile unsigned   int xItemValue;   /* Auxiliary value used to help nodes sort in ascending order. */
    struct xLIST_ITEM   * pxNext; 
    struct xLIST_ITEM   * pxPrevious;
}MiniListItem_t;

// Define the linked list, which is also the linked list head
typedef struct xLIST
{  
    volatile unsigned   int uxNumberOfItems;   
    ListItem_t *  pxIndex; 
    MiniListItem_t xListEnd;                          
} List_t;

void vListInitialise( List_t * const pxList)
{
    pxList->uxNumberOfItems = 0;    
    pxList->pxIndex = (ListItem_t *) &(pxList->xListEnd); 
    pxList->xListEnd.xItemValue = 100;    
    pxList->xListEnd.pxNext =(ListItem_t *) &(pxList->xListEnd);     /*lint !e826 !e740 !e9087 The mini list structure is used as the list end to save RAM.  This is checked and valid. */
    pxList->xListEnd.pxPrevious = (ListItem_t *) &(pxList->xListEnd); /*lint !e826 !e740 !e9087 The mini list structure is used as the list end to save RAM.  This is checked and valid. */
}

void vListInitialiseItem(ListItem_t * const pxItem )
{
    pxItem->pxContainer = NULL;
}
// The function to insert a list item at the end of the list, inserting the node at the end of the linked list  
void vListInsertEnd( List_t * const pxList,ListItem_t * const pxNewListItem )
{
    ListItem_t * const headEnd = pxList->pxIndex;

    pxNewListItem->pxNext = headEnd;
    pxNewListItem->pxPrevious = headEnd->pxPrevious;

    headEnd->pxPrevious->pxNext = pxNewListItem;
    headEnd->pxPrevious = pxNewListItem;
    
    /* Remember the linked list this node belongs to. */
    pxNewListItem->pxContainer = pxList;
 
    (pxList->uxNumberOfItems)++;
}

void vListInsert( List_t * const pxList,ListItem_t * const pxNewListItem )
{
    ListItem_t * pxIterator;
    const int xValueOfInsertion = pxNewListItem->xItemValue;


    if( xValueOfInsertion == 100 )
    {
        pxIterator = pxList->xListEnd.pxPrevious;
    }
    else
    {
        for( pxIterator = (ListItem_t*)&(pxList->xListEnd); pxIterator->pxNext->xItemValue <= xValueOfInsertion; pxIterator = pxIterator->pxNext )
        {
            
        }
    }
 /* Insert the new node after pxIterator according to ascending order */   
    pxNewListItem->pxNext = pxIterator->pxNext;
    pxNewListItem->pxNext->pxPrevious = pxNewListItem;
    pxNewListItem->pxPrevious = pxIterator;
    pxIterator->pxNext = pxNewListItem;
     
    /* Remember the linked list this node belongs to */
    pxNewListItem->pxContainer = pxList;
 /* Increment the linked list node counter */
    ( pxList->uxNumberOfItems )++;
}
int uxListRemove( ListItem_t * const pxItemToRemove )
{
 /* Get the linked list the node belongs to */
    List_t * const pxList = pxItemToRemove->pxContainer;
 
 /* Remove the specified node from the linked list*/
    pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;
    pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;


    /* Adjust the linked list node index pointer */
    if( pxList->pxIndex == pxItemToRemove )
    {
        pxList->pxIndex = pxItemToRemove->pxPrevious;
    }
    else
    {

    }
 /* Initialize the node’s container list to NULL, indicating that the node has not been inserted into any list */
    pxItemToRemove->pxContainer = NULL;
 /* Decrement the linked list node counter */
    ( pxList->uxNumberOfItems )--;
 /* Return the number of remaining nodes in the linked list */
    return pxList->uxNumberOfItems;
}

/* Define the root node of the linked list */
struct xLIST List_Test;

/* Define nodes */
struct xLIST_ITEM List_Item1;
struct xLIST_ITEM List_Item2;
struct xLIST_ITEM List_Item3;

int main(void)
{
    /* Define the root node of the linked list */
    struct xLIST List_Test;

    /* Define nodes */
    struct xLIST_ITEM List_Item1;
    struct xLIST_ITEM List_Item2;
    struct xLIST_ITEM List_Item3;
    
    /* Initialize the root node of the linked list */
    vListInitialise(&List_Test); 

    /* Initialize Node 1 */
    vListInitialiseItem(&List_Item1);
    List_Item1.xItemValue = 1;

    /* Initialize Node 2 */
    vListInitialiseItem(&List_Item2);
    List_Item2.xItemValue = 2;

    /* Initialize Node 3 */
    vListInitialiseItem(&List_Item3);
    List_Item3.xItemValue = 3;

    /* Insert nodes into the linked list in ascending order */ 
    vListInsert( &List_Test, &List_Item2);
    vListInsert( &List_Test, &List_Item1);
    vListInsert( &List_Test, &List_Item3);
 
 while(1);
}

Then find a 32-bit code and try it out with Keil simulation.

Getting Started with FreeRTOS: A Guide to Writing Doubly Linked Lists

Take a close look at this picture:

Getting Started with FreeRTOS: A Guide to Writing Doubly Linked Lists

This is actually the FreeRTOS linked list source code, isn’t it very simple?

Project download source code:

Link: https://pan.baidu.com/s/1g34z7l3MSrf12lawF4hKLA?pwd=o8xc 
Extraction code: o8xc

This project is a regular bare-metal example, just added the FreeRTOS linked list source code. I recommend everyone to try it out themselves to gain a deeper understanding of linked lists. Because to learn any RTOS well, the foundational knowledge you must master is linked lists and queues!

END
Source: Guoguo Little Master
Copyright belongs to the original author. If there is any infringement, please contact for deletion.
▍Recommended Reading
Step-by-step guide to setting up a lightweight electronic laboratory
How to write a robust and efficient serial reception program?
After large-scale layoffs, will computer majors become the next civil engineering?
→ Follow to avoid getting lost ←

Related posts:

  1. FreeRTOS Learning Notes: Software Structure of FreeRTOS
  2. FreeRTOS Queue Usage Example
  3. Deploying OpenWrt 23.05.3 on VMware ESXi

Leave a Comment

×