从零开始，教你写FreeRTOS双向链表

嵌入式ARM 2022-07-11 12:00 1476浏览 0评论 0点赞

TOLG 技术采用超紧凑的海鸥翼式引脚设计 从周级到天级：云仿真加速实战

摘要：前几天给大家讲了单向链表，今天再结合FreeRTOS的链表源码，说一下双向链表。

注：链表项就是节点，节点就是链表项，都是指的一个东西，叫啥都无所谓。

一、定义链表结构体

//定义链表，同时也是链表头
typedef struct xLIST
{  
    volatile unsigned   int uxNumberOfItems;   
    ListItem_t *  pxIndex; 
    MiniListItem_t xListEnd;                          
} List_t;

二、定义mini节点项

迷你节点也是节点，但迷你节点仅用于标记链表的末尾和挂载其他插入链表中的节点，用户是用不到迷你节点的，链表头节点和普通节点可以不一样。

typedef struct xMINI_LIST_ITEM
{
    volatile unsigned   int xItemValue;   /* 辅助值，用于帮助节点做升序排列. */
    struct xLIST_ITEM   * pxNext; 
    struct xLIST_ITEM   * pxPrevious;
}MiniListItem_t;

下面这个头即使链表定义，也是链表头，链表头节点和普通节点可以不一样。

三、定义节点

节点在FreeRTOS中叫做链表项。

//定义链表节点
typedef struct xLIST_ITEM
{       
    volatile unsigned   int  xItemValue;          
    struct xLIST_ITEM *  pxNext;     
    struct xLIST_ITEM *  pxPrevious; 
    void * pvOwner;                       //用于指向该节点的拥有者              
    struct xLIST *  pxContainer;          //用于指向该节点所在的链表，通常指向链表的根节点
              
}ListItem_t;

四、初始化链表

初始化链表就是给链表的头结点各个参数赋值。

void vListInitialise( List_t * const pxList)
{
    /*初始化时，列表中的列表项数量为 0（不包含 xListEnd） */
    pxList->uxNumberOfItems = 0;    
    /* 初始化时，列表中只有 xListEnd，因此 pxIndex 指向 xListEnd */
    pxList->pxIndex = (ListItem_t *) &(pxList->xListEnd); 
    /* xListEnd 的值初始化为最大值，用于列表项升序排序时，排在最后 */
    pxList->xListEnd.xItemValue = portMAX_DELAY;    
    /* 初始化时，列表中只有 xListEnd，因此上一个和下一个列表项都为 xListEnd 本身 */
    pxList->xListEnd.pxNext =(ListItem_t *) &(pxList->xListEnd); 
    pxList->xListEnd.pxPrevious = (ListItem_t *) &(pxList->xListEnd); 
}

五、初始化节点

void vListInitialiseItem(ListItem_t * const pxItem )
{
   /* 初始化时，列表项所在列表设为空 */
    pxItem->pxContainer = NULL;
}

六、将节点插入到链表的尾部

void vListInsertEnd( List_t * const pxList,ListItem_t * const pxNewListItem )
{
    /* 获取列表 pxIndex 指向的列表项 */
    ListItem_t * const headEnd = pxList->pxIndex;
    /* 更新待插入列表项的指针成员变量 */
    pxNewListItem->pxNext = headEnd;
    pxNewListItem->pxPrevious = headEnd->pxPrevious;
    /* 更新列表中原本列表项的指针成员变量 */
    headEnd->pxPrevious->pxNext = pxNewListItem;
    headEnd->pxPrevious = pxNewListItem;
        /* 标记待插入列表项的所在列表成员变量 */
    pxNewListItem->pxContainer = pxList;
   /* 列表中列表项的数量+1 */
    (pxList->uxNumberOfItems)++;
}

此函数就是将待插入的列表项插入到列表 pxIndex 指向列表项的前面，要注意的时，pxIndex 不一定指向 xListEnd，而是有可能指向列表中任意一个列表项。

我手画一张图来解释吧！

七、链表节点插入并排序

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

    /* 如果待插入列表项的值为最大值 */
    if( xValueOfInsertion == portMAX_DELAY)
    {
        /* 插入的位置为列表 xListEnd 前面 */
        pxIterator = pxList->xListEnd.pxPrevious;
    }
    else
    {
         /* 遍历列表中的列表项，找到插入的位置 */
        for( pxIterator = (ListItem_t*)&(pxList->xListEnd); pxIterator->pxNext->xItemValue <= xValueOfInsertion; pxIterator = pxIterator->pxNext )
        {
            
        }
    }
 /* 根据升序排列，将节点插入  在pxIterator后面插入新节点*/   
    pxNewListItem->pxNext = pxIterator->pxNext;
    pxNewListItem->pxNext->pxPrevious = pxNewListItem;
    pxNewListItem->pxPrevious = pxIterator;
    pxIterator->pxNext = pxNewListItem;
     
    /* 记住该节点所在的链表 */
    pxNewListItem->pxContainer = pxList;
   /* 链表节点计数器++ */
    ( pxList->uxNumberOfItems )++;
}

在将待插入列表项插入列表之前，会前遍历列表，找到待插入列表项需要插入的位置。待插入列表项需要插入的位置，是依照列表中列表项的值，按照升序排序确定的。

八、删除链表节点

int uxListRemove( ListItem_t * const pxItemToRemove )
{
 /* 获取节点所在的链表 */
    List_t * const pxList = pxItemToRemove->pxContainer;
 
 /* 将指定的节点从链表删除*/
    pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;
    pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;
    

    /* 如果 pxIndex 正指向待移除的列表项 */
    if( pxList->pxIndex == pxItemToRemove )
    {
        /* pxIndex 指向上一个列表项 */
        pxList->pxIndex = pxItemToRemove->pxPrevious;
    }
    else
    {

    }
   /* 将待移除列表项的所在列表指针清空 */
    pxItemToRemove->pxContainer = NULL;
   /* 链表节点计数器-- */
    ( pxList->uxNumberOfItems )--;
   /* 返回链表中剩余节点的个数 */
    return pxList->uxNumberOfItems;
}

要删除节点，首先就必须要找到节点。

需要注意的是，函数 uxListRemove()移除后的列表项，依然于列表有着单向联系，即移除后列表项中用于指向上一个和下一个列表项的指针，依然指向列表中的列表项。

九、实例

#include 
#include 
#include 

//定义链表节点
typedef struct xLIST_ITEM
{       
    volatile unsigned   int  xItemValue;          
    struct xLIST_ITEM *  pxNext;     
    struct xLIST_ITEM *  pxPrevious; 
    void * pvOwner;                       //用于指向该节点的拥有者              
    struct xLIST *  pxContainer;          //用于指向该节点所在的链表，通常指向链表的根节点
              
}ListItem_t;

typedef struct xMINI_LIST_ITEM
{
    volatile unsigned   int xItemValue;   /* 辅助值，用于帮助节点做升序排列. */
    struct xLIST_ITEM   * pxNext; 
    struct xLIST_ITEM   * pxPrevious;
}MiniListItem_t;

//定义链表，同时也是链表头
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;
}
//列表项(节点)末尾插入函数，将节点插入到链表的尾部  
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;
    
    /* 记住该节点所在的链表. */
    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 )
        {
            
        }
    }
 /* 根据升序排列，将节点插入  在pxIterator后面插入新节点*/   
    pxNewListItem->pxNext = pxIterator->pxNext;
    pxNewListItem->pxNext->pxPrevious = pxNewListItem;
    pxNewListItem->pxPrevious = pxIterator;
    pxIterator->pxNext = pxNewListItem;
     
    /* 记住该节点所在的链表 */
    pxNewListItem->pxContainer = pxList;
 /* 链表节点计数器++ */
    ( pxList->uxNumberOfItems )++;
}
int uxListRemove( ListItem_t * const pxItemToRemove )
{
 /* 获取节点所在的链表 */
    List_t * const pxList = pxItemToRemove->pxContainer;
 
 /* 将指定的节点从链表删除*/
    pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;
    pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;
    

    /*调整链表的节点索引指针 */
    if( pxList->pxIndex == pxItemToRemove )
    {
        pxList->pxIndex = pxItemToRemove->pxPrevious;
    }
    else
    {

    }
 /* 初始化该节点所在的链表为空，表示节点还没有插入任何链表 */
    pxItemToRemove->pxContainer = NULL;
 /* 链表节点计数器-- */
    ( pxList->uxNumberOfItems )--;
 /* 返回链表中剩余节点的个数 */
    return pxList->uxNumberOfItems;
}

/* 定义链表根节点 */
struct xLIST List_Test;

/* 定义节点 */
struct xLIST_ITEM List_Item1;
struct xLIST_ITEM List_Item2;
struct xLIST_ITEM List_Item3;

int main(void)
{
    /* 定义链表根节点 */
    struct xLIST List_Test;

    /* 定义节点 */
    struct xLIST_ITEM List_Item1;
    struct xLIST_ITEM List_Item2;
    struct xLIST_ITEM List_Item3;
    
    /* 链表根节点初始化 */
    vListInitialise(&List_Test); 

    /* 节点 1 初始化 */
    vListInitialiseItem(&List_Item1);
    List_Item1.xItemValue = 1;

    /* 节点 2 初始化 */
    vListInitialiseItem(&List_Item2);
    List_Item2.xItemValue = 2;

    /* 节点 3 初始化 */
    vListInitialiseItem(&List_Item3);
    List_Item3.xItemValue = 3;

    /* 将节点插入链表，按照升序排列 */ 
    vListInsert( &List_Test, &List_Item2);
    vListInsert( &List_Test, &List_Item1);
    vListInsert( &List_Test, &List_Item3);
 
 while(1);
}

然后随便找个32的代码，用keil仿真试一试。

仔细看一下这张图：

这个其实就是FreeRTOS的链表源码，是不是很简单？

工程下载源码：

链接：https://pan.baidu.com/s/1g34z7l3MSrf12lawF4hKLA?pwd=o8xc 
提取码：o8xc

其实这个工程是一个普通的裸机例程，只是加入了FreeRTOS的链表源码，建议大家自己动手试一下，深入理解链表。因为要想学好任何一个RTOS，必须掌握的基础知识就是链表和队列！

END

来源：果果小师弟

版权归原作者所有，如有侵权，请联系删除。

▍推荐阅读

手把手教你搭建一个轻量级电子实验室

如何写一个健壮且高效的串口接收程序？

大规模裁员后，计算机专业会成下一个土木吗？

→点关注，不迷路←

登录阅读全文



免责声明：该内容由专栏作者授权发布或作者转载，目的在于传递更多信息，并不代表本网赞同其观点，本站亦不保证或承诺内容真实性等。若内容或图片侵犯您的权益，请及时联系本站删除。侵权投诉联系： nick.zong@aspencore.com！

嵌入式ARM 关注这个时代最火的嵌入式ARM，你想知道的都在这里。

进入专栏

嵌入式ARM 关注这个时代最火的嵌入式ARM，你想知道的都在这里。

文章：3717篇粉丝：187人

关注  私信