FreeRTOS列表与列表项

时间:2024-10-03 18:29:56

1.什么是列表与列表项

列表与列表项实际上是FreeRTOS中一个大量使用的一种数据结构

1.列表

列表的概念有点像链表,在 FreeRTOS 中,列表主要用于以下几个方面:

  1. 任务的管理:FreeRTOS 使用列表来管理不同的任务,包括就绪任务列表、阻塞任务列表等。任务列表按任务优先级或其他条件进行排序,以便调度器能够快速选择下一个要执行的任务
  2. 定时器:FreeRTOS 使用列表来管理软件定时器。定时器列表按定时器到期时间排序,这样在系统时钟中断时,可以快速检查是否有定时器到期
  3. 事件管理:FreeRTOS 使用列表来管理事件和资源,如信号量、互斥量等。这些列表有助于跟踪哪些任务在等待某个事件或资源

在list.h种,有如下结构体定义

typedef struct xLIST
{
    listFIRST_LIST_INTEGRITY_CHECK_VALUE      /*< Set to a known value if configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
    volatile UBaseType_t uxNumberOfItems;
    ListItem_t * configLIST_VOLATILE pxIndex; /*< Used to walk through the list.  Points to the last item returned by a call to listGET_OWNER_OF_NEXT_ENTRY (). */
    MiniListItem_t xListEnd;                  /*< List item that contains the maximum possible item value meaning it is always at the end of the list and is therefore used as a marker. */
    listSECOND_LIST_INTEGRITY_CHECK_VALUE     /*< Set to a known value if configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
} List_t;
  • listFIRST_LIST_INTEGRITY_CHECK_VALUE:

这个实际上是一个用于列表完整性检查的一个宏,它的主要作用是帮助检测内存损坏或者意外的列表结构修改。它通常被定义为某个常量值,当 FreeRTOS 创建或修改列表时,会使用这个常量值来设置列表结构中的特定字段。然后,在后续的操作中,FreeRTOS 会检查这些字段的值,以确保列表没有被意外修改或损坏

我们后续编程不需要关心这个宏。

  • uxNumberOfItems

列表中列表项的数量

  • pxIndex:

记录当前列表项的索引号,用于遍历列表

  • xListEnd:

列表中最后一个列表项

2.列表项

列表项(List Item)是一个数据结构,用于在列表(List)中存储和管理信息。每个列表项代表一个节点或单元,可以包含指向其他相关数据的指针

FreeRTOS共有两种列表项,分别是列表项和迷你列表项

1.列表项的结构体定义如下:

struct xLIST_ITEM
{
    listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE           /*不用关心< Set to a known value if configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
    configLIST_VOLATILE TickType_t xItemValue;          /*实际的数据< The value being listed.  In most cases this is used to sort the list in ascending order. */
    struct xLIST_ITEM * configLIST_VOLATILE pxNext;     /*指向下一个列表项< Pointer to the next ListItem_t in the list. */
    struct xLIST_ITEM * configLIST_VOLATILE pxPrevious; /*指向前一个列表项< Pointer to the previous ListItem_t in the list. */
    void * pvOwner;                                     /*指向列表项的创建者< Pointer to the object (normally a TCB) that contains the list item.  There is therefore a two way link between the object containing the list item and the list item itself. */
    struct xLIST * configLIST_VOLATILE pxContainer;     /*此列表项所属的列表< Pointer to the list in which this list item is placed (if any). */
    listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE          /*不用关心< Set to a known value if configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
};
typedef struct xLIST_ITEM ListItem_t;                   /* For some reason lint wants this as two separate definitions. */
  • listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE:

检查列表项完整性

  • xItemValue

列表项值

  • pxNext

指向下一个列表项

  • pxPrevious

指向前一个列表项

  • pvOwner

指向拥有该列表项的对象,列表项用于管理任务时,通常指向该任务的任务控制块(TCB)

  • pxContainer

指向此列表项所属的列表。

注意这个和pvOwner并不冲突,我们在前面讲TCB程序控制块时,TCB有两个列表项,比如说这个状态列表项,当创建一个任务后,这个状态列表项中的pvOwner就指向这个任务的TCB,如果这个任务进入就绪状态后,那么这个状态列表项的pxContainer就指向就绪列表,表明此列表项在就绪列表中。如果程序进入挂起状态后,那么pxContainer就指向挂起列表,表明此列表项在挂起列表中

2.迷你列表项

在某些情况下,我们不需要列表项的所有功能,为了节省资源,我们可以采用迷你列表项,比如我们列表中最后一个列表项的类型就是xMINI_LIST_ITEM类型的迷你列表项,其定义如下:

struct xMINI_LIST_ITEM
    {
        listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE /*< Set to a known value if configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
        configLIST_VOLATILE TickType_t xItemValue;
        struct xLIST_ITEM * configLIST_VOLATILE pxNext;
        struct xLIST_ITEM * configLIST_VOLATILE pxPrevious;
    };
  • listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE

检查列表项完整性

  • xItemValue

列表项值

  • pxNext

指向下一列表项

  • pxPrevious

指向上一列表项

2.列表与列表项相关操作

1.列表与列表项初始化

新建列表需要初始化,通过调用函数vListInitialise()完成,列表项也是如此,通过函数vListInitialiseItem()完成。虽然函数的内部构造很复杂,但我们使用起来是叫较为简单的,所以不需要花费太多时间。

2.列表项插入

1)插入

列表项的插入通过函数vListInsert()完成,其函数原型如下

void vListInsert( List_t * const pxList,
                  ListItem_t * const pxNewListItem )

参数

pxList: 列表项要插入的列表

pxNewListItem 要插入的列表项

需要注意的是,列表项插入是根据列表项值的升序进行排列的


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 ) /*lint !e826 !e740 The mini list structure is used as the list end to save RAM.  This is checked and valid. */
            {}
        }

    pxNewListItem->pxNext = pxIterator->pxNext;//列表项的下一节点
    pxNewListItem->pxNext->pxPrevious = pxNewListItem;//列表项的尾节点指向头结点,类似循环列表
    pxNewListItem->pxPrevious = pxIterator;//列表项的上一节点
    pxIterator->pxNext = pxNewListItem;

    pxNewListItem->pvContainer = ( void * ) pxList;//修改列表项的所属者,属于就绪列表、阻塞列表

        ( pxList->uxNumberOfItems )++;//长度加1
}

2)末尾插入

列表项末尾插入通过函数vListInsertEnd()完成,其原型如下,其入参和vListInsert()一样:


void vListInsertEnd( List_t * const pxList,
                     ListItem_t * const pxNewListItem )

需要注意的是,这个末尾并不是同学们想象的那样,因为我们列表本身是个环形列表,列表中pxIndex是用来遍历列表的,所以它指向的列表项实际上就是表头,所以新的列表项会插入到pxIndex所指向列表项的前面(即最后遍历),而非插到xListEnd的后面。

3)列表项删除

列表项的删除也比较简单,通过uxListRemove()完成,其函数原型如下,传参只有一个,就是要删除的列表项:

UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove )

4)遍历

列表中的成员变量pxInedx,FreeRTO提供了函数接口listGET_OWNER_OF_NEXT_ENTRY(),其实现如下:

listGET_OWNER_OF_NEXT_ENTRY( pxTCB, pxList )