Abstract: Today, we will discuss the doubly linked list by combining the source code of FreeRTOS’s linked list. Note: A linked list item is a node, and a node is a linked list item; they refer to the same thing, and it doesn’t matter what you call it.

1. Defining the Linked List Structure

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

2. Defining Mini Node Items

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

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

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

Mastering FreeRTOS: A Comprehensive Guide to Doubly Linked Lists

3. Defining Nodes

Nodes are called list items in FreeRTOS.

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

4. Initializing the Linked List

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

void vListInitialise( List_t * const pxList)
{
    /* At initialization, the number of items in the list is 0 (not including xListEnd) */
    pxList->uxNumberOfItems = 0;    
    /* At initialization, the list only contains xListEnd, so pxIndex points to xListEnd */
    pxList->pxIndex = (ListItem_t *) &(pxList->xListEnd); 
    /* Initialize the value of xListEnd to the maximum value, used for sorting list items in ascending order, 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); 
}

5. Initializing Nodes

void vListInitialiseItem(ListItem_t * const pxItem )
{
   /* At initialization, the list the item belongs to is set to NULL */
    pxItem->pxContainer = NULL;
}

6. Inserting 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 member variable of the item to be inserted */
    pxNewListItem->pxNext = headEnd;
    pxNewListItem->pxPrevious = headEnd->pxPrevious;
    /* Update the pointer member variable of the original list item in the list */
    headEnd->pxPrevious->pxNext = pxNewListItem;
    headEnd->pxPrevious = pxNewListItem;
        /* Mark the list member variable of the item to be inserted */
    pxNewListItem->pxContainer = pxList;
   /* Increment the number of items in the list */
    (pxList->uxNumberOfItems)++;
}

This function inserts the item to be inserted before the list item pointed to by pxIndex. Note that pxIndex may not necessarily point to xListEnd, but may point to any item in the list.

Let me draw a picture to explain.

7. Inserting and Sorting 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 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 which list the node belongs to */
    pxNewListItem->pxContainer = pxList;
   /* Increment the linked list node counter */
    ( pxList->uxNumberOfItems )++;
}

Before inserting the item to be inserted into the list, we will traverse the list to find the position where the item to be inserted needs to be inserted. The position for insertion is determined according to the values of the items in the list in ascending order.

8. Deleting Linked List Nodes

int uxListRemove( ListItem_t * const pxItemToRemove )
{
 /* Get the linked list where the node is located */
    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 )
    {
        /* Point pxIndex to the previous item */
        pxList->pxIndex = pxItemToRemove->pxPrevious;
    }
    else
    {
    }
   /* Clear the pointer of the list where the item to be removed belongs */
    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.

It should be noted that after the function uxListRemove() removes the item, the item still has a unidirectional relationship with the list, meaning that the pointers used to point to the previous and next items still point to the 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;                       // Points to the owner of this node              
    struct xLIST *  pxContainer;          // Points to the linked list this node belongs to, usually points to the root node
              
}ListItem_t;

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

// Define the linked list, which is also the head of the linked list
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;
}
// List item (node) insertion function, insert 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 which list the 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 )
        {
        }
    }
 /* According to ascending order, insert the node after pxIterator */   
    pxNewListItem->pxNext = pxIterator->pxNext;
    pxNewListItem->pxNext->pxPrevious = pxNewListItem;
    pxNewListItem->pxPrevious = pxIterator;
    pxIterator->pxNext = pxNewListItem;
     
    /* Remember which list the node belongs to */
    pxNewListItem->pxContainer = pxList;
 /* Increment the linked list node counter */
    ( pxList->uxNumberOfItems )++;
}
int uxListRemove( ListItem_t * const pxItemToRemove )
{
 /* Get the linked list where the node is located */
    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's node index pointer */
    if( pxList->pxIndex == pxItemToRemove )
    {
        pxList->pxIndex = pxItemToRemove->pxPrevious;
    }
    else
    {
    }
 /* Initialize the node's container to NULL, indicating 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, just find a 32-bit code and simulate it using Keil;

Take a close look at this image.

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

Download the source code for the project:

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

This project is an ordinary bare-metal example that only includes the source code of FreeRTOS’s linked list. You can try it yourself to gain a deeper understanding of the linked list because to learn any RTOS well, the fundamental knowledge you must master is linked lists and queues.

Source: Guo Guo Xiao Shidi

Warm Reminder:

Due to recent changes in the WeChat public platform’s push rules, many readers have reported not seeing updated articles in time. According to the latest rules, it is recommended to click on “Recommended Reading, Share, Favorite,” etc., to become a regular reader.

Recommended Reading:

14/16nm chips sued, will Samsung and TSMC’s foundry chips face sales bans in the US?
This company continues to cooperate with China despite multiple objections to chip restrictions.
Can semiconductors determine modern warfare?
To do things thoroughly, semiconductor giants turn against each other despite their relationships?

Please click 【View】 to give the editor a thumbs up.

Mastering FreeRTOS: A Comprehensive Guide to Doubly Linked Lists

1. Defining the Linked List Structure

2. Defining Mini Node Items

3. Defining Nodes

4. Initializing the Linked List

5. Initializing Nodes

6. Inserting Nodes at the End of the Linked List

7. Inserting and Sorting Linked List Nodes

8. Deleting Linked List Nodes

9. Example

Understanding the Relationship Between Micro:bit and Arduino

Getting Started with the Arduino ESP32 Core Library

Implementing Neural Networks on a 10-Cent RISC-V MCU Without a Multiplier

Getting Started with Arduino: Light Up Your First LED from Scratch

How Highly Integrated Embedded Processors Drive the Development of Industrial Robots

Leave a Comment Cancel reply

Menu