FreeRTOS列表与列表项及其操作

本文介绍FreeRTOS中的列表与列表项，及列表项的插入，删除等操作，仅作参考。

1.列表与列表项

列表是FreeRTOS中的一种数据结构，类似于C语言中的双向环形链表，用于跟踪FreeRTOS中的任务，记录任务的当前状态或事件，比如就绪列表，任务创建完成时就会添加至就绪列表，等待调度器调用。

列表结构体如下：

typedef struct xLIST            //列表结构体
{
    listFIRST_LIST_INTEGRITY_CHECK_VALUE         //用于校验
    volatile UBaseType_t uxNumberOfItems;        //列表中列表项数量
    ListItem_t * configLIST_VOLATILE pxIndex;    //指向某个列表项，用于遍历
    MiniListItem_t xListEnd;                     //末尾列表项
    listSECOND_LIST_INTEGRITY_CHECK_VALUE       //用于校验
} List_t;

列表项是存放于列表中的数据，如果列表相当于数组，列表项就相当于数组中的元素，如果列表相当于链表，列表项就相当于链表的节点。

列表项结构体如下：

struct xLIST_ITEM
{
    listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE            //校验值      
    configLIST_VOLATILE TickType_t xItemValue;           //列表项的值，用于升序排序  
    struct xLIST_ITEM * configLIST_VOLATILE pxNext;      //指向下一个列表项的指针
    struct xLIST_ITEM * configLIST_VOLATILE pxPrevious;  //指向前一个列表项的指针
    void * pvOwner;                                      //列表项的拥有者，也就是任务控制块
    struct xLIST * configLIST_VOLATILE pxContainer;      //此列表项所属的列表
    listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE          //校验值    
};

 迷你列表项：存放于列表的最后一项，只有列表项值，前指针和后指针。

struct xMINI_LIST_ITEM        //迷你列表项
    {
        listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE         //校验值，无需理会
        configLIST_VOLATILE TickType_t xItemValue;        //列表项值，用于列表项升序排序
        struct xLIST_ITEM * configLIST_VOLATILE pxNext;   //指向前一个列表项的指针
        struct xLIST_ITEM * configLIST_VOLATILE pxPrevious;
        //指向后一个列表项的指针，因为它是最后一项，所以这个指向第一项，环形列表
    };

2.列表的操作

（1）列表与列表项的初始化

void vListInitialise( List_t * const pxList )//列表初始化函数，参数为待初始化的列表
{
    pxList->pxIndex = ( ListItem_t * ) &( pxList->xListEnd );//将索引值指向末尾列表项

    listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE( &( pxList->xListEnd ) );//校验

    pxList->xListEnd.xItemValue = portMAX_DELAY;//将末尾列表项的值设置为最大
    //末尾列表项的后向指针指向自己
    pxList->xListEnd.pxNext = ( ListItem_t * ) &( pxList->xListEnd );   
    //末尾列表项的前向指针指向自己  
    pxList->xListEnd.pxPrevious = ( ListItem_t * ) &( pxList->xListEnd ); 

    pxList->uxNumberOfItems = ( UBaseType_t ) 0U;//列表项的数量初始化为0，末尾列表项不算

    listSET_LIST_INTEGRITY_CHECK_1_VALUE( pxList );//校验
    listSET_LIST_INTEGRITY_CHECK_2_VALUE( pxList );//校验
}

void vListInitialiseItem( ListItem_t * const pxItem )//列表项初始化，参数为待初始化的列表项
{
    
    pxItem->pxContainer = NULL;//将列表项的所属列表设置为NULL

    listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );//校验
    listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );//校验
}

（2）列表的升序插入

void vListInsert( List_t * const pxList,        //升序插入函数，第一个参数为要插入的列表
                  ListItem_t * const pxNewListItem )//第二个参数为要插入的列表项
{
    ListItem_t * pxIterator;        //定义一个中间变量列表项指针
    //获取要插入的列表项的值，以此确定要插入的位置
    const TickType_t xValueOfInsertion = pxNewListItem->xItemValue;

    listTEST_LIST_INTEGRITY( pxList );//检验参数
    listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );//检验参数

    if( xValueOfInsertion == portMAX_DELAY )//如果列表项值为最大值
    {
        pxIterator = pxList->xListEnd.pxPrevious;//则插入末尾列表项的前面
    }
    else//如果不是最大值
    {
        for( pxIterator = ( ListItem_t * ) &( pxList->xListEnd ); pxIterator->pxNext->            
            xItemValue <= xValueOfInsertion; pxIterator = pxIterator->pxNext ) 
        {
            //这个循环就在找列表项值大于前一项而小于后一项的位置
            //具体是将中间变量=末尾列表项，如要插入的列表项值大于末尾列表项的下一项的列表项值，也就是第一项，则中间变量=下一项，由此循环，直到找到列表项值大于要插入的列表项值为止
        }
    }
    //找到的这个中间变量就是要插入的位置，以下操作就是将新列表项插入到找到的位置后面
    pxNewListItem->pxNext = pxIterator->pxNext;    
    pxNewListItem->pxNext->pxPrevious = pxNewListItem;
    pxNewListItem->pxPrevious = pxIterator;
    pxIterator->pxNext = pxNewListItem;

    pxNewListItem->pxContainer = pxList;//将新插入项的所属列表更新为要插入的列表

    ( pxList->uxNumberOfItems )++;//列表项数量++
}

（3）列表的尾部插入：其实是插入到列表索引值的前面，初始化时这个索引值指向末尾列表项

void vListInsertEnd( List_t * const pxList,        //第一个参数为要插入到的列表
                     ListItem_t * const pxNewListItem )//第二个参数为要插入的列表项
{
    ListItem_t * const pxIndex = pxList->pxIndex;    //获取列表的索引值


    listTEST_LIST_INTEGRITY( pxList );//检验参数
    listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );//检验参数

    //以下操作将新列表项插入到索引值前面，因为初始化时索引值指向末尾列表项，
    //所以也就是插到末尾列表项前面
    pxNewListItem->pxNext = pxIndex;
    pxNewListItem->pxPrevious = pxIndex->pxPrevious;
    mtCOVERAGE_TEST_DELAY();
    pxIndex->pxPrevious->pxNext = pxNewListItem;
    pxIndex->pxPrevious = pxNewListItem;

    pxNewListItem->pxContainer = pxList;//更新列表项所属列表

    ( pxList->uxNumberOfItems )++;//列表项数量++
}

（4）列表项的删除

UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove )//列表项删除，参数待删除列表项
{

    List_t * const pxList = pxItemToRemove->pxContainer;//先获取该列表项所属列表

    //以下两句就是将该列表项的前面一项指向其后面一项，后面一项指向其前面一项
    //这样该列表项从列表中脱离出去了
    pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;
    pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;

    mtCOVERAGE_TEST_DELAY();

    if( pxList->pxIndex == pxItemToRemove )//如果列表的索引值指向要删除的该列表项
    {
        pxList->pxIndex = pxItemToRemove->pxPrevious;//则将索引值指向其前面一项
    }
    else
    {
        mtCOVERAGE_TEST_MARKER();
    }

    pxItemToRemove->pxContainer = NULL;//更新该列表项所属列表为空
    ( pxList->uxNumberOfItems )--;//列表项数量--

    return pxList->uxNumberOfItems;//返回剩余列表项数量
}