《FreeRTOS列表和列表项篇》

FreeRTOS列表和列表项

1. 什么是列表和列表项？
- 1.1 列表list
- 1.2 列表项list item
2. 列表和列表项的初始化
- 2.1 列表的初始化
- 2.2 列表项的初始化
3. 列表项的插入
4. 列表项末尾插入
5. 列表项的删除
6. 列表的遍历

列表和列表项是FreeRTOS的一个数据结构，是FreeRTOS的基石。

1. 什么是列表和列表项？

1.1 列表list

列表在概念上类似双向链表，用来追踪FreeRTOS中的任务。

/** Definition of the type of queue used by the scheduler.* 任务调度器使用的队列的定义*/
typedef struct xLIST
{listFIRST_LIST_INTEGRITY_CHECK_VALUEvolatile UBaseType_t uxNumberOfItems;	  /* 用来记录列表中列表项的个数，其中不包含末尾列表项。 */ListItem_t * configLIST_VOLATILE pxIndex; /* 用来记录当前列表项的索引号，用于遍历列表。 */MiniListItem_t xListEnd;                  /* 末尾列表项（迷你列表项），用来表示列表的结束。 */listSECOND_LIST_INTEGRITY_CHECK_VALUE
} List_t;

列表结构示意图

1.2 列表项list item

列表项指存放在列表中的对象，FreeRTOS提供了2个类型：列表项和迷你列表项。

/** Definition of the only type of object that a list can contain.* 定义列表可以包含的唯一对象类型*/
struct xLIST_ITEM
{listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUEconfigLIST_VOLATILE TickType_t xItemValue;          /* 列表项的值，这用于按升序对列表进行排序 */struct xLIST_ITEM * configLIST_VOLATILE pxNext;     /* 指向下一个列表项 */struct xLIST_ITEM * configLIST_VOLATILE pxPrevious; /* 指向上一个列表项 */void * pvOwner;                                     /* 指向包含列表项的对象（通常是TCB）的指针。*/struct xLIST * configLIST_VOLATILE pxContainer;     /* 用来记录此列表项属于哪个列表。 */listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE
};
typedef struct xLIST_ITEM ListItem_t;

列表项结构示意图

#if ( configUSE_MINI_LIST_ITEM == 1 ) /* 若为1，则为普通列表项，若为0，则为迷你列表项。 */struct xMINI_LIST_ITEM{listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUEconfigLIST_VOLATILE TickType_t xItemValue;		/* 列表项的值，这用于按升序对列表进行排序 */struct xLIST_ITEM * configLIST_VOLATILE pxNext;		/* 指向下一个列表项 */struct xLIST_ITEM * configLIST_VOLATILE pxPrevious;	/* 指向上一个列表项 */};typedef struct xMINI_LIST_ITEM MiniListItem_t;
#elsetypedef struct xLIST_ITEM      MiniListItem_t;
#endif

迷你列表项结构示意图

2. 列表和列表项的初始化

2.1 列表的初始化

void vListInitialise( List_t * const pxList )
{/* The list structure contains a list item which is used to mark the* end of the list.  To initialise the list the list end is inserted* as the only list entry. * 列表结构体中包含一个用于标记列表的结束的列表项（即末尾列表项）。* 为了初始化列表，末尾列表项被插入作为唯一的列表条目。*/pxList->pxIndex = ( ListItem_t * ) &( pxList->xListEnd ); /* 列表的列表项索引号指向末尾列表项。*/listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE( &( pxList->xListEnd ) );/* The list end value is the highest possible value in the list to* ensure it remains at the end of the list. * 末尾列表项的列表项值是列表中可能的最高值，以确保它保持在列表的末尾。*/pxList->xListEnd.xItemValue = portMAX_DELAY; /* 0xFFFFFFFFUL *//* The list end next and previous pointers point to itself so we know* when the list is empty. * 末尾列表项的下一个和前一个列表项指针指向自身，因此我们知道列表何时为空。*/pxList->xListEnd.pxNext = ( ListItem_t * ) &( pxList->xListEnd );pxList->xListEnd.pxPrevious = ( ListItem_t * ) &( pxList->xListEnd );/* Initialize the remaining fields of xListEnd when it is a proper ListItem_t * 当末尾列表项是普通列表项时，初始化其剩余字段。*/#if ( configUSE_MINI_LIST_ITEM == 0 ){pxList->xListEnd.pvOwner = NULL;pxList->xListEnd.pxContainer = NULL;listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE( &( pxList->xListEnd ) );}#endifpxList->uxNumberOfItems = ( UBaseType_t ) 0U; /* 末尾列表项不算在列表项个数中。 *//* Write known values into the list if* configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */listSET_LIST_INTEGRITY_CHECK_1_VALUE( pxList );listSET_LIST_INTEGRITY_CHECK_2_VALUE( pxList );
}

初始化后的列表结构

2.2 列表项的初始化

列表项的初始化此处只对pxContainer设置了初始值，其他成员变量需要根据实际使用情况初始化。

void vListInitialiseItem( ListItem_t * const pxItem )
{/* Make sure the list item is not recorded as being on a list. * 确保列表项未被记录为在列表中。*/pxItem->pxContainer = NULL;listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );
}

初始化后的列表项结构

3. 列表项的插入

void vListInsert( List_t * const pxList, /* 决定列表项要插入到哪一个列表中。 */ListItem_t * const pxNewListItem ) /* 准备插入列表中的列表项。要插入的位置由列表项中的成员变量xItemValue决定 */
{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 ){/* There is nothing to do here, just iterating to the wanted* insertion position. */}}pxNewListItem->pxNext = pxIterator->pxNext;pxNewListItem->pxNext->pxPrevious = pxNewListItem;pxNewListItem->pxPrevious = pxIterator;pxIterator->pxNext = pxNewListItem;/* Remember which list the item is in.  This allows fast removal of the* item later. */pxNewListItem->pxContainer = pxList; /* 将列表项的成员变量pxContainer赋值为插入的列表。 */( pxList->uxNumberOfItems )++; /* 列表的列表项总个数自增1 */
}

初始化列表中插入列表项值为40的列表项
列表中插入列表项值为60的列表项
列表中插入列表项值为50的列表项

4. 列表项末尾插入

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;/* Remember which list the item is in. */pxNewListItem->pxContainer = pxList;( pxList->uxNumberOfItems )++;
}

默认列表
在默认列表中进行末尾插入列表项值为30的列表项

5. 列表项的删除

如果这个列表项是动态分配内存的，列表项的删除只是将指定的列表项从列表中删除掉，并不会将这个列表项的内存释放掉。

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;
}

列表删除列表项2

6. 列表的遍历

列表结构体中的成员变量pxIndex是用来遍历列表的。
FreeRTOS提供了一个函数来完成列表的遍历，函数是listGET_OWNER_OF_NEXT_ENTRY( pxTCB, pxList )。每调用一次这个函数，列表的pxIndex变量就会指向下一个列表项，并且返回这个列表项的pvOwner变量值。

#define listGET_OWNER_OF_NEXT_ENTRY( pxTCB, pxList )                                           \{                                                                                          \List_t * const pxConstList = ( pxList );                                               \/* Increment the index to the next item and return the item, ensuring */               \/* we don't return the marker used at the end of the list.  */                         \( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext;                           \if( ( void * ) ( pxConstList )->pxIndex == ( void * ) &( ( pxConstList )->xListEnd ) ) \{                                                                                      \( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext;                       \}                                                                                      \( pxTCB ) = ( pxConstList )->pxIndex->pvOwner;                                         \}