4 列表和列表项
列表是FreeRTOS中的一个数据结构,概念上和链表有点类似,列表被用来跟踪FreeRTOS中的任务。
4.1 数据结构
列表数据结构定义如下:
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;
列表项ListItem_t的定义如下:
typedef struct xLIST_ITEM ListItem_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 //检查列表完整性
};
Mini列表项MiniListItem_t的定义如下:
typedef struct xMINI_LIST_ITEM MiniListItem_t;
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; //指向前一个列表项
};
4.2 列表和列表项初始化
列表初始化:列表初始化是对列表结构体List_t中的各个成员变量进行初始化,列表的初始化通过vListInitialise()来完成,函数实现如下:
void vListInitialise( List_t * const pxList )
{
pxList->pxIndex = ( ListItem_t * ) &( pxList->xListEnd ); //(1)
pxList->xListEnd.xItemValue = portMAX_DELAY; //(2)
pxList->xListEnd.pxNext = ( ListItem_t * ) &( pxList->xListEnd ); //(3)
pxList->xListEnd.pxPrevious = ( ListItem_t * ) &( pxList->xListEnd );//(4)
pxList->uxNumberOfItems = ( UBaseType_t ) 0U;//(5)
listSET_LIST_INTEGRITY_CHECK_1_VALUE( pxList );//(6)
listSET_LIST_INTEGRITY_CHECK_2_VALUE( pxList );//(7)
}
(1)xListEnd用来表示列表的末尾,pxIndex表示列表项的索引号,此时只有一个列表项xListEnd。
(2)xListEnd的列表项值初始化为portMAX_DELAY,这是个宏,不同MCU值不同,可能为0xfff或0xffffffffULL。
(3)xListEnd的pxNext变量指向自身。
(4)xListEnd的pxPrevious变量指向自身。
(5)此时没有其他列表项,uxNumberOfItems为0,这里没有算xListEnd。
(6)(7)初始化列表项中用于完整性检查字段。
初始化之后的结果如下:
列表项初始化:列表项在使用的时候也需要初始化。列表项初始化函数为vListInitialiseItem()。
void vListInitialiseItem( ListItem_t * const pxItem )
{
pxItem->pxContainer = NULL;
listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );
listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );
}
列表项初始化仅将列表项成员pxContainer初始化为NULL。
4.3 列表和列表项相关函数
4.3.1 列表项插入函数
函数原型:
#include "FreeRTOS.h"
#include "list.h"
void vListInsert( List_t * const pxList,
ListItem_t * const pxNewListItem );
函数说明:列表项插入函数。列表项的插入位置由列表项中成员变量xItemValue决定,根据xItemValue的值反照升序的方式排列。
参数说明:pxList:列表项要插入的列表;pxNewListItem:要插入的列表项。
函数实现:
#include "FreeRTOS.h"
#include "list.h"
void vListInsert( List_t * const pxList,
ListItem_t * const pxNewListItem )
{
ListItem_t * pxIterator;
const TickType_t xValueOfInsertion = pxNewListItem->xItemValue; //(1)
listTEST_LIST_INTEGRITY( pxList ); //(2)
listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );
if( xValueOfInsertion == portMAX_DELAY ) //(3)
{
pxIterator = pxList->xListEnd.pxPrevious; //(4)
}
else
{
for( pxIterator = ( ListItem_t * ) &( pxList->xListEnd );
pxIterator->pxNext->xItemValue <= xValueOfInsertion;
pxIterator = pxIterator->pxNext ) //(5)
{
/* There is nothing to do here,
* just iterating to the wanted insertion position. */
}
}
pxNewListItem->pxNext = pxIterator->pxNext; //(6)
pxNewListItem->pxNext->pxPrevious = pxNewListItem;
pxNewListItem->pxPrevious = pxIterator;
pxIterator->pxNext = pxNewListItem;
pxNewListItem->pxContainer = pxList; //(7)
( pxList->uxNumberOfItems )++; //(8)
}
(1)获取要插入的列表项值,根据这个值确认列表项的插入位置。
(2)检查列表和列表项 的完整性。
(3)插入的列表项值为portMAX_DELAY,插入的位置就在列表最末尾。
(4)插入的列表项值为portMAX_DELAY,列表项插入在xListEnd前面。
(5)插入的列表项值不等于portMAX_DELAY,在列表中一个一个找插入的位置,找到合适的位置就退出,当前for循环体没有代码,这个查找过程就按照升序的方式查找列表项插入点。
(6)从本行开始的四行代码就是将列表项插入到列表中,插入过程和双向链表类似。
(7)列表项的成员变量pxContainer记录此列表项属于哪个列表。
(8)列表的成员变量uxNumberOfItems加一,表示又添加了一个列表项。
列表项插入过程演示:
在一个空的列表中插入三个列表项,这三个列表项的值分别为40、60、50。
1、插入值为40的列表项
在一个空的列表插入一个列表值为40的列表项ListIterm1,插入完成后如下图所示,可看出列表是一个环形列表:
2、插入值为60的列表项
在上面列表中插入值为60的列表项,插入完成后如下图所示:
3、插入值为50的列表项
在上面列表中插入值为50的列表项,插入完成后如下图所示:
4.3.2 列表项末尾插入函数
函数原型:
#include "FreeRTOS.h"
#include "list.h"
void vListInsertEnd( List_t * const pxList,
ListItem_t * const pxNewListItem );
函数说明:列表末尾插入列表项。
参数说明:pxList:列表项要插入的列表;pxNewListItem:要插入的列表项。
函数实现:
void vListInsertEnd( List_t * const pxList,
ListItem_t * const pxNewListItem )
{
ListItem_t * const pxIndex = pxList->pxIndex;
listTEST_LIST_INTEGRITY( pxList ); //(1)
listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );
pxNewListItem->pxNext = pxIndex; //(2)
pxNewListItem->pxPrevious = pxIndex->pxPrevious;
mtCOVERAGE_TEST_DELAY();
pxIndex->pxPrevious->pxNext = pxNewListItem;
pxIndex->pxPrevious = pxNewListItem;
pxNewListItem->pxContainer = pxList; //(3)
( pxList->uxNumberOfItems )++; //(4)
}
(1)这行和下一行代码完成对列表和列表项的完整性检查。
(2)从本行开始的代码就是将要插入的列表项插入到列表末尾。这里所谓的末尾是根据列表的成员变量pxIndex来确定的。pxIndex成员变量用于遍历列表,pxIndex所指向的列表项就是要遍历的开始列表项,也就是pxIndex所指向的列表项就代表列表头。新的列表项就插入到pxIndex所指向的列表项的前面。
(3)标记新的列表项pxNewListItem属于列表pxList。
(4)记录列表中的列表项数目的变量加一,更新列表项数目。
列表项插入过程演示:
1、默认列表
插入列表项前先准备一个默认列表,如下图所示:
2、插入值为50的列表项
在上面的列表中插入一个值为50的列表项,插入完成之后如下图所示:
4.3.2 列表项删除函数
函数原型:
#include "FreeRTOS.h"
#include "list.h"
UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove );
函数说明:列表项删除函数。
参数说明:pxItemToRemove:要删除的列表项。注意:列表项的删除只是将指定的列表项从列表中删除掉,并不会将这个列表项的内存给释放掉,如果这个列表项是动态内存分配的话。
返回值:返回删除列表项以后的列表剩余列表项数目。
函数实现:
UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove )
{
List_t * const pxList = pxItemToRemove->pxContainer; //(1)
pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious; //(2)
pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;
mtCOVERAGE_TEST_DELAY();
if( pxList->pxIndex == pxItemToRemove )
{
pxList->pxIndex = pxItemToRemove->pxPrevious; //(3)
}
else
{
mtCOVERAGE_TEST_MARKER();
}
pxItemToRemove->pxContainer = NULL; //(4)
( pxList->uxNumberOfItems )--;
return pxList->uxNumberOfItems; //(5)
}
(1)读取列表项中的成员pxContainer,得到列表项处于哪个列表中。
(2)与下一行完成列表项的删除。将要删除的列表项的前后两个列表项连接在一起。
(3)如果列表的pxIndex正好指向要删除的列表项,则pxIndex重新指向被删除的列表项的前一个列表项。
(4)被删除列表项的成员变量pxContainer清零。
(5)返回新列表的当前列表项数目。
4.3.2 列表的遍历
列表的遍历是通过listGET_OWNER_OF_NEXT_ENTRY宏实现的。每调用一次这个函数列表的pxIndex变量就会指向下一个列表项,并且返回这个列表项的pxOwner变量值。
宏的实现:
#include "FreeRTOS.h"
#include "list.h"
#define listGET_OWNER_OF_NEXT_ENTRY( pxTCB, pxList ) \//(1)
{ List_t * const pxConstList = ( pxList ); ( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext; \//(2)
if( ( void * ) ( pxConstList )->pxIndex == ( void * ) &( ( pxConstList )->xListEnd))\//(3)
{ ( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext; \//(4)
} ( pxTCB ) = ( pxConstList )->pxIndex->pvOwner; \//(5)
}
(1)pxTCB用来保存pxIndex所指向的列表项的pvOwner变量值,也就是这个列表项的所有者,通常是一个任务的任务控制块。pxList表示要遍历的列表。
(2)列表的pxIndex变量指向下一个列表项。
(3)如果pxIndex指向了列表的xListEnd成员变量,表示到了列表末尾。
(4)如果到了列表末尾的话就跳过xListEnd,pxIndex再一次重新指向处于列表头的列表项,这样就完成了一次对列表的遍历。
(5)将pxIndex所指向的新列表项的pvOwner赋值给pxTCB。
4.3 列表和列表项实验
创建一个任务,用于操作列表和列表项。调用列表和列表项相关的API函数。
configSTACK_DEPTH_TYPE Task06_STACK_SIZE = 5;
UBaseType_t Task06_Priority = 1;
TaskHandle_t Task06_xHandle;
List_t TestList;
ListItem_t ListItem1;
ListItem_t ListItem2;
ListItem_t ListItem3;
void vTask06_Code(void *para)
{
//初始化列表和列表项
vListInitialise(&TestList);
vListInitialiseItem(&ListItem1);
vListInitialiseItem(&ListItem2);
vListInitialiseItem(&ListItem3);
ListItem1.xItemValue = 40;
ListItem2.xItemValue = 60;
ListItem3.xItemValue = 50;
//打印列表和其他列表项地址
PRINT(" ==== list and listItem address ====");
PRINT(" type address");
PRINT(" ------------------------------");
PRINT(" TestList %#x", &TestList);
PRINT(" TestList->pxIndex %#x", TestList.pxIndex);
PRINT(" TestList->xListEnd %#x", &TestList.xListEnd);
PRINT(" ListItem1 %#x", &ListItem1);
PRINT(" ListItem2 %#x", &ListItem2);
PRINT(" ListItem3 %#x", &ListItem3);
PRINT(" =============== end ===============\n");
//向列表中添加列表项ListItem1,观察列表项中成员变量的值。
vListInsert(&TestList, &ListItem1);
PRINT(" ====== add listItem1 in TestList =======");
PRINT(" type address");
PRINT(" ----------------------------------------");
PRINT(" TestList->xListEnd->pxNext %#x", TestList.xListEnd.pxNext);
PRINT(" ListItem1->pxNext %#x", ListItem1.pxNext);
PRINT(" -------- 前后向连接切割线 ---------");
PRINT(" TestList->xListEnd->pxPrevious %#x", TestList.xListEnd.pxPrevious);
PRINT(" ListItem1->pxPrevious %#x", ListItem1.pxPrevious);
PRINT(" ================= end ==================\n");
//向列表中插入列表项ListItem2,观察列表项中成员变量的变化
vListInsert(&TestList, &ListItem2);
PRINT(" ====== add listItem2 in TestList =======");
PRINT(" type address");
PRINT(" ----------------------------------------");
PRINT(" TestList->xListEnd->pxNext %#x", TestList.xListEnd.pxNext);
PRINT(" ListItem1->pxNext %#x", ListItem1.pxNext);
PRINT(" ListItem2->pxNext %#x", ListItem2.pxNext);
PRINT(" -------- 前后向连接切割线 ---------");
PRINT(" TestList->xListEnd->pxPrevious %#x", TestList.xListEnd.pxPrevious);
PRINT(" ListItem1->pxPrevious %#x", ListItem1.pxPrevious);
PRINT(" ListItem2->pxPrevious %#x", ListItem2.pxPrevious);
PRINT(" ================= end ==================\n");
//向列表中插入列表项ListItem3,观察列表项中成员变量的变化
vListInsert(&TestList, &ListItem3);
PRINT(" ====== add listItem3 in TestList =======");
PRINT(" type address");
PRINT(" ----------------------------------------");
PRINT(" TestList->xListEnd->pxNext %#x", TestList.xListEnd.pxNext);
PRINT(" ListItem1->pxNext %#x", ListItem1.pxNext);
PRINT(" ListItem3->pxNext %#x", ListItem3.pxNext);
PRINT(" ListItem2->pxNext %#x", ListItem2.pxNext);
PRINT(" -------- 前后向连接切割线 ---------");
PRINT(" TestList->xListEnd->pxPrevious %#x", TestList.xListEnd.pxPrevious);
PRINT(" ListItem1->pxPrevious %#x", ListItem1.pxPrevious);
PRINT(" ListItem3->pxPrevious %#x", ListItem3.pxPrevious);
PRINT(" ListItem2->pxPrevious %#x", ListItem2.pxPrevious);
PRINT(" ================= end ==================\n");
//删除ListItem2,观察列表项中成员变量的变化
uxListRemove(&ListItem2);
PRINT(" ========== delete listItem2 ============");
PRINT(" type address");
PRINT(" ----------------------------------------");
PRINT(" TestList->xListEnd->pxNext %#x", TestList.xListEnd.pxNext);
PRINT(" ListItem1->pxNext %#x", ListItem1.pxNext);
PRINT(" ListItem3->pxNext %#x", ListItem3.pxNext);
PRINT(" -------- 前后向连接切割线 ---------");
PRINT(" TestList->xListEnd->pxPrevious %#x", TestList.xListEnd.pxPrevious);
PRINT(" ListItem1->pxPrevious %#x", ListItem1.pxPrevious);
PRINT(" ListItem3->pxPrevious %#x", ListItem3.pxPrevious);
PRINT(" ================= end ==================\n");
//pxIndex向后移一项
TestList.pxIndex = TestList.pxIndex->pxNext;
//在列表末尾插入列表项ListItem2
vListInsertEnd(&TestList, &ListItem2);
PRINT(" ===== add listItem2 in TestList end =====");
PRINT(" type address");
PRINT(" ----------------------------------------");
PRINT(" TestList->pxIndex %#x", TestList.pxIndex);
PRINT(" TestList->xListEnd->pxNext %#x", TestList.xListEnd.pxNext);
PRINT(" ListItem2->pxNext %#x", ListItem2.pxNext);
PRINT(" ListItem1->pxNext %#x", ListItem1.pxNext);
PRINT(" ListItem3->pxNext %#x", ListItem3.pxNext);
PRINT(" -------- 前后向连接切割线 ---------");
PRINT(" TestList->xListEnd->pxPrevious %#x", TestList.xListEnd.pxPrevious);
PRINT(" ListItem2->pxPrevious %#x", ListItem2.pxPrevious);
PRINT(" ListItem1->pxPrevious %#x", ListItem1.pxPrevious);
PRINT(" ListItem3->pxPrevious %#x", ListItem3.pxPrevious);
PRINT(" ================= end ==================\n");
for (;;)
{
static unsigned int cnt = 0;
PRINT(" task06 cnt %u...", cnt);
cnt++;
vTaskDelay(1000);
}
}
void creat_task_test_list(void)
{
if (xTaskCreate(vTask06_Code, "list test task06", Task06_STACK_SIZE,
NULL, Task06_Priority, &Task06_xHandle) != pdPASS)
PRINT("creat task failed!\n");
}
编译,运行,打印结果如下:
$ ./build/freertos-simulator
==== list and listItem address ====
type address
------------------------------
TestList 0x60f000
TestList->pxIndex 0x60f010
TestList->xListEnd 0x60f010
ListItem1 0x60f0c0
ListItem2 0x60f120
ListItem3 0x60f080
=============== end ===============
====== add listItem1 in TestList =======
type address
----------------------------------------
TestList->xListEnd->pxNext 0x60f0c0
ListItem1->pxNext 0x60f010
-------- 前后向连接切割线 ---------
TestList->xListEnd->pxPrevious 0x60f0c0
ListItem1->pxPrevious 0x60f010
================= end ==================
====== add listItem2 in TestList =======
type address
----------------------------------------
TestList->xListEnd->pxNext 0x60f0c0
ListItem1->pxNext 0x60f120
ListItem2->pxNext 0x60f010
-------- 前后向连接切割线 ---------
TestList->xListEnd->pxPrevious 0x60f120
ListItem1->pxPrevious 0x60f010
ListItem2->pxPrevious 0x60f0c0
================= end ==================
====== add listItem3 in TestList =======
type address
----------------------------------------
TestList->xListEnd->pxNext 0x60f0c0
ListItem1->pxNext 0x60f080
ListItem3->pxNext 0x60f120
ListItem2->pxNext 0x60f010
-------- 前后向连接切割线 ---------
TestList->xListEnd->pxPrevious 0x60f120
ListItem1->pxPrevious 0x60f010
ListItem3->pxPrevious 0x60f0c0
ListItem2->pxPrevious 0x60f080
================= end ==================
========== delete listItem2 ============
type address
----------------------------------------
TestList->xListEnd->pxNext 0x60f0c0
ListItem1->pxNext 0x60f080
ListItem3->pxNext 0x60f010
-------- 前后向连接切割线 ---------
TestList->xListEnd->pxPrevious 0x60f080
ListItem1->pxPrevious 0x60f010
ListItem3->pxPrevious 0x60f0c0
================= end ==================
===== add listItem2 in TestList end =====
type address
----------------------------------------
TestList->pxIndex 0x60f0c0
TestList->xListEnd->pxNext 0x60f120
ListItem2->pxNext 0x60f0c0
ListItem1->pxNext 0x60f080
ListItem3->pxNext 0x60f010
-------- 前后向连接切割线 ---------
TestList->xListEnd->pxPrevious 0x60f080
ListItem2->pxPrevious 0x60f010
ListItem1->pxPrevious 0x60f120
ListItem3->pxPrevious 0x60f0c0
================= end ==================
task06 cnt 0...
task06 cnt 1...
过程分析:
(1)列表和列表项的地址如下:
TestList 0x60f000
ListItem1 0x60f0c0
TestList->pxIndex 0x60f010
TestList->xListEnd 0x60f010
ListItem2 0x60f120
ListItem3 0x60f080
(2)列表TestList添加列表项ListItem1后的地址如下:
type address
----------------------------------------
TestList->xListEnd->pxNext 0x60f0c0 //ListItem1
ListItem1->pxNext 0x60f010 //TestList->xListEnd
-------- 前后向连接切割线 ---------
TestList->xListEnd->pxPrevious 0x60f0c0 //ListItem1
ListItem1->pxPrevious 0x60f010 //TestList->xListEnd
用示意图表示如下图所示:
(2)列表TestList添加列表项ListItem2后的地址如下:
type address
----------------------------------------
TestList->xListEnd->pxNext 0x60f0c0 //ListItem1
ListItem1->pxNext 0x60f120 //ListItem2
ListItem2->pxNext 0x60f010 //TestList->xListEnd
-------- 前后向连接切割线 ---------
TestList->xListEnd->pxPrevious 0x60f120 //ListItem2
ListItem1->pxPrevious 0x60f010 //TestList->xListEnd
ListItem2->pxPrevious 0x60f0c0 //ListItem1
用示意图表示如下图所示:
(3)列表TestList插入列表项ListItem3后的地址如下:
TestList->xListEnd->pxNext 0x60f0c0 //ListItem1
ListItem1->pxNext 0x60f080 //ListItem3
ListItem3->pxNext 0x60f120 //ListItem2
ListItem2->pxNext 0x60f010 //TestList->xListEnd
-------- 前后向连接切割线 ---------
TestList->xListEnd->pxPrevious 0x60f120 //ListItem2
ListItem1->pxPrevious 0x60f010 //TestList->xListEnd
ListItem3->pxPrevious 0x60f0c0 //ListItem1
ListItem2->pxPrevious 0x60f080 //ListItem3
用示意图表示如下图所示:
(4)列表TestList删除列表项ListItem2之后的地址如下:
TestList->xListEnd->pxNext 0x60f0c0 //ListItem1
ListItem1->pxNext 0x60f080 //ListItem3
ListItem3->pxNext 0x60f010 //TestList->xListEnd
-------- 前后向连接切割线 ---------
TestList->xListEnd->pxPrevious 0x60f080 //ListItem3
ListItem1->pxPrevious 0x60f010 //TestList->xListEnd
ListItem3->pxPrevious 0x60f0c0 //ListItem1
用示意图表示如下图所示:
(4)列表TestList在末端插入列表项ListItem2之后的地址如下:
这里所说的末端就是TestList->pxIndex指向的列表项(代表列表头),新的列表项就插入到TestList->pxIndex所指向的列表项的前面。
TestList->pxIndex 0x60f0c0 //ListItem1
TestList->xListEnd->pxNext 0x60f120 //ListItem2
ListItem2->pxNext 0x60f0c0 //ListItem1
ListItem1->pxNext 0x60f080 //ListItem3
ListItem3->pxNext 0x60f010 //TestList->xListEnd
-------- 前后向连接切割线 ---------
TestList->xListEnd->pxPrevious 0x60f080 //ListItem3
ListItem2->pxPrevious 0x60f010 //TestList->xListEnd
ListItem1->pxPrevious 0x60f120 //ListItem2
ListItem3->pxPrevious 0x60f0c0 //ListItem1
用示意图表示如下图所示: