示例源码基于FreeRTOS V9.0.0
链表
1 概述
链表一般可分为单向链表、双向链表、环形链表。FreeRTOS采用的是环形双向链表设计；
单向链表只有后继节点，双向链表有后继和前驱节点；
链表的目的是把元素串联，其设计方式一般有两种：
- 将元素放置在链表结构体中；
- 将链表结构体放置在元素中；
方式1：
typedef struct content{
int data;
}content_t;
typedef struct list_t{
list_t* prev;
list_t* next;
content_t ctx;
}list_t;
方式2：
typedef struct list_t{
list_t* prev;
list_t* next;
}list_t;
typedef struct content{
list_t node;
int data;
}content_t;
FreeRTOS采用的是方式2的链表设计，一般用于串联TCB，即任务控制块；
2 链表结构
2.1 链表节点
/*
* Definition of the only type of object that a list can contain.
*/
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 descending 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. */
void * configLIST_VOLATILE pvContainer; /*< 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. */
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;
};
typedef struct xMINI_LIST_ITEM MiniListItem_t;
ListItem_t 表示链表节点，用来串联链表，其内包含：
- listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE和listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE为节点的边界校验字段，宏configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES配置为1时生效；
- xItemValue，该值被用来链表项排序，一般根据此值，链表降序排列；
- pxNext和pxPrevious，后继和前驱节点，用来串联链表；
- pvOwner，指向链表节点指向的元素，通常是TCB；
- pvContainer，指向List_t，表示节点所属的链表；
MiniListItem_t 也表示链表节点，但仅包含链表所需的最小元素，用此结构体来描述链表尾节点；
2.2 链表控制块
/*
* Definition of the type of queue used by the scheduler.
*/
typedef struct xLIST
{
listFIRST_LIST_INTEGRITY_CHECK_VALUE /*< Set to a known value if configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
configLIST_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和listSECOND_LIST_INTEGRITY_CHECK_VALUE为List_t的边界校验字段，宏configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES配置为1时生效；
- uxNumberOfItems，表示链表长度，链表元素个数；
- pxIndex，指向链表节点，用来遍历链表；
- xListEnd，链表尾节点，可用此节点找到链表首个元素和最后一个元素；
3 接口API
3.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 ); /*lint !e826 !e740 The mini list structure is used as the list end to save RAM. This is checked and valid. */
/* 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;
/* 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 ); /*lint !e826 !e740 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 The mini list structure is used as the list end to save RAM. This is checked and valid. */
pxList->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 );
}
- pxIndex 初始化指向尾节点；
- xListEnd 尾节点初始化，其xItemValue赋为TickType_t能表示的最大值（portMAX_DELAY），其前驱后继节点指向本身；
- uxNumberOfItems 链表长度初始化为0；
- 如果宏configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES配置为1，则对pxList边界字段赋值（常量，用于校验）；
3.2 链表节点初始化
void vListInitialiseItem( ListItem_t * const pxItem )
{
/* Make sure the list item is not recorded as being on a list. */
pxItem->pvContainer = NULL;
/* Write known values into the list item if
configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );
listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );
}
实现简单，仅将节点的pvContainer初始化为NULL，另外根据宏开关，若开启则对节点边界字段赋值（常量，用于校验）；
3.3 链表插入
FreeRTOS对链表的插入提供了两个API，一个用于在当前节点之前插入，一个用于有序链表的插入。
3.3.1 在当前节点之前插入
void vListInsertEnd( List_t * const pxList, ListItem_t * const pxNewListItem )
{
ListItem_t * const pxIndex = pxList->pxIndex;
/* Only effective when configASSERT() is also defined, these tests may catch
the list data structures being overwritten in memory. They will not catch
data errors caused by incorrect configuration or use of FreeRTOS. */
listTEST_LIST_INTEGRITY( pxList );
listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );
/* Insert a new list item into pxList, but rather than sort the list,
makes the new list item the last item to be removed by a call to
listGET_OWNER_OF_NEXT_ENTRY(). */
pxNewListItem->pxNext = pxIndex;
pxNewListItem->pxPrevious = pxIndex->pxPrevious;
/* Only used during decision coverage testing. */
mtCOVERAGE_TEST_DELAY();
pxIndex->pxPrevious->pxNext = pxNewListItem;
pxIndex->pxPrevious = pxNewListItem;
/* Remember which list the item is in. */
pxNewListItem->pvContainer = ( void * ) pxList;
( pxList->uxNumberOfItems )++;
}
- listTEST_LIST_INTEGRITY和listTEST_LIST_ITEM_INTEGRITY是分别对链表和链表节点的校验，校验边界字段的常量值，当宏configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES配置为1时生效；
- pxIndex 是用来遍历链表节点的（遍历的方式通过宏函数listGET_OWNER_OF_NEXT_ENTRY实现），它指向当前的节点；
- 修改pxNewListItem的后继和前驱指向，后继指向pxIndex，前驱指向pxIndex->pxPrevious；
- 修改pxIndex->pxPrevious的后继指向，指向新节点；
- 修改pxIndex的前驱指向，指向新节点；
- 新节点的pvContainer指向pxList，标识该节点属于链表pxList；
- 链表长度加1；
插入步骤示意图如下：
3.3.2 有序列表插入
void vListInsert( List_t * const pxList, ListItem_t * const pxNewListItem )
{
ListItem_t *pxIterator;
const TickType_t xValueOfInsertion = pxNewListItem->xItemValue;
/* Only effective when configASSERT() is also defined, these tests may catch
the list data structures being overwritten in memory. They will not catch
data errors caused by incorrect configuration or use of FreeRTOS. */
listTEST_LIST_INTEGRITY( pxList );
listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );
/* Insert the new list item into the list, sorted in xItemValue order.
If the list already contains a list item with the same item value then the
new list item should be placed after it. This ensures that TCB's which are
stored in ready lists (all of which have the same xItemValue value) get a
share of the CPU. However, if the xItemValue is the same as the back marker
the iteration loop below will not end. Therefore the value is checked
first, and the algorithm slightly modified if necessary. */
if( xValueOfInsertion == portMAX_DELAY )
{
pxIterator = pxList->xListEnd.pxPrevious;
}
else
{
/* *** NOTE ***********************************************************
If you find your application is crashing here then likely causes are
listed below. In addition see http://www.freertos.org/FAQHelp.html for
more tips, and ensure configASSERT() is defined!
http://www.freertos.org/a00110.html#configASSERT
1) Stack overflow -
see http://www.freertos.org/Stacks-and-stack-overflow-checking.html
2) Incorrect interrupt priority assignment, especially on Cortex-M
parts where numerically high priority values denote low actual
interrupt priorities, which can seem counter intuitive. See
http://www.freertos.org/RTOS-Cortex-M3-M4.html and the definition
of configMAX_SYSCALL_INTERRUPT_PRIORITY on
http://www.freertos.org/a00110.html
3) Calling an API function from within a critical section or when
the scheduler is suspended, or calling an API function that does
not end in "FromISR" from an interrupt.
4) Using a queue or semaphore before it has been initialised or
before the scheduler has been started (are interrupts firing
before vTaskStartScheduler() has been called?).
**********************************************************************/
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. */
{
/* 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->pvContainer = ( void * ) pxList;
( pxList->uxNumberOfItems )++;
}
- listTEST_LIST_INTEGRITY和listTEST_LIST_ITEM_INTEGRITY是分别对链表和链表节点的校验，校验边界字段的常量值，当宏configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES配置为1时生效；
- 如果新节点的xItemValue为portMAX_DELAY，则将新节点插入在尾节点前，即作为最后一个节点。pxIterator指向插入位置；
- 如果新节点的xItemValue不为portMAX_DELAY，则从尾节点开始遍历，找到比xItemValue大的节点（pxIterator->pxNext）。链表是降序排列的，从尾到头遍历则为升序；
- pxIterator指向插入位置，新节点在pxIterator前插入；
- 新节点pvContainer指向pxList，标识节点属于列表pxList；
- 列表长度加1；
插入步骤示意图如下：
3.4 链表删除
UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove )
{
/* The list item knows which list it is in. Obtain the list from the list
item. */
List_t * const pxList = ( List_t * ) pxItemToRemove->pvContainer;
pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;
pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;
/* Only used during decision coverage testing. */
mtCOVERAGE_TEST_DELAY();
/* Make sure the index is left pointing to a valid item. */
if( pxList->pxIndex == pxItemToRemove )
{
pxList->pxIndex = pxItemToRemove->pxPrevious;
}
else
{
mtCOVERAGE_TEST_MARKER();
}
pxItemToRemove->pvContainer = NULL;
( pxList->uxNumberOfItems )--;
return pxList->uxNumberOfItems;
}
- 移除节点步骤
- 更改待移除节点的后继节点（pxItemToRemove->pxNext）的前驱指向；
- 更改待移除节点的前驱节点（pxItemToRemove->pxPrevious）的后继指向；
- 如果待删除节点是当前节点（pxList->pxIndex == pxItemToRemove），将当前节点指向待删除节点的前驱；
- 待删除节点的pvContainer置为NULL；
- 链表长度减1；
- 返回链表长度；
删除步骤示意图:
4 宏函数
// 设置链表节点指向的元素，通常为TCB
#define listSET_LIST_ITEM_OWNER( pxListItem, pxOwner ) ( ( pxListItem )->pvOwner = ( void * ) ( pxOwner ) )
// 获取链表节点指向的元素，通常为TCB
#define listGET_LIST_ITEM_OWNER( pxListItem ) ( ( pxListItem )->pvOwner )
// 设置链表节点 value值，该值用于链表排序
#define listSET_LIST_ITEM_VALUE( pxListItem, xValue ) ( ( pxListItem )->xItemValue = ( xValue ) )
// 获取链表节点 value值，该值用于链表排序
#define listGET_LIST_ITEM_VALUE( pxListItem ) ( ( pxListItem )->xItemValue )
// 获取链表头节点 value值
#define listGET_ITEM_VALUE_OF_HEAD_ENTRY( pxList ) ( ( ( pxList )->xListEnd ).pxNext->xItemValue )
// 获取链表头节点
#define listGET_HEAD_ENTRY( pxList ) ( ( ( pxList )->xListEnd ).pxNext )
// 获取指定节点的后继
#define listGET_NEXT( pxListItem ) ( ( pxListItem )->pxNext )
// 获取尾节点
#define listGET_END_MARKER( pxList ) ( ( ListItem_t const * ) ( &( ( pxList )->xListEnd ) ) )
// 判断链表是否为空
#define listLIST_IS_EMPTY( pxList ) ( ( BaseType_t ) ( ( pxList )->uxNumberOfItems == ( UBaseType_t ) 0 ) )
// 获取链表长度
#define listCURRENT_LIST_LENGTH( pxList ) ( ( pxList )->uxNumberOfItems )
// 用于遍历链表，pxList->pxIndex指向当前节点，pxTCB指向当前节点的元素
#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; \
}
// 获取头节点指向的元素
#define listGET_OWNER_OF_HEAD_ENTRY( pxList ) ( (&( ( pxList )->xListEnd ))->pxNext->pvOwner )
// 判断列表pxList中是否存在节点pxListItem
#define listIS_CONTAINED_WITHIN( pxList, pxListItem ) ( ( BaseType_t ) ( ( pxListItem )->pvContainer == ( void * ) ( pxList ) ) )
// 根据节点获取列表
#define listLIST_ITEM_CONTAINER( pxListItem ) ( ( pxListItem )->pvContainer )
// 判断列表是否初始化（粗暴校验，仅根据尾节点的value值判读是否初始化）
#define listLIST_IS_INITIALISED( pxList ) ( ( pxList )->xListEnd.xItemValue == portMAX_DELAY )