FreeRTOS—列表和列表项

一、列表与列表项

1.1.列表与列表项的简介

列表是 FreeRTOS 中的一个数据结构，概念上和链表有点类似，列表被用来追踪 FreeRTOS 中的任务，列表项就是存放在列表中的项目；列表相当于链表，列表项相当于节点，FreeRTOS 中的列表是一个双向环形链表，列表和列表项的关系和下图所示：

下面这几点说明了使用链表的好处：

• 列表的特点：列表项间的地址非连续，是人为的连接到一起的，列表项的数目是由后期添加的个数决定的，随时可以改变。
• 数组的特点：数组成员地址是连续的，数组在最初确定了成员数量后期无法改变。
• 在 OS 中任务的数量是不确定的，并且任务状态是会发生改变的，所以非常适用列表这种数据结构

1.2.列表与列表项相关结构体

1.2.1.列表结构体

有关列表的均在文件 list.c 和 list.h 中，下面代码是 list.h 文件有关列表相关的结构体：

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;

• 在该结构体中，包含了两个宏，这两个宏是确定的已知常量，FreeRTOS 通过检查这两个常量的值，来判断列表的数据在程序运行过程中，是否遭到破坏，该功能一般用于调试，默认是不开启的
• 成员uxNumberOfItems，用于记录列表中列表项的个数（不包含 xListEnd）
• 成员pxIndex用于指向列表中的某个列表项，一般用于遍历列表中的所有列表项
• 成员变量xListEnd是一个迷你列表项，排在最末尾

下图是列表结构示意图：

1.2.2.列表项结构体

有关列表项的均在文件 list.c 和 list.h 中，下面代码是 list.h 文件有关列表项相关的结构体：

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 				 /* 用于检测列表项的数据完整性 */
};
typedef struct xLIST_ITEM ListItem_t;						 /* 重定义成 ListItem_t */

• 成员变量xItemValue为列表项的值，这个值用于按升序对列表中的列表项进行排序，例如：有任务一，数值是10；任务二，数值是20；任务三，数值是30，添加一个任务四，数值是25，任务四应该加入在任务二和任务三之间
• 成员变量pxNext和pxPrevious分别用于指向列表中列表项的下一个列表项和上一个列表项
• 成员变量pvOwner用于指向包含列表项的对象（通常是任务控制块）
• 成员变量pxContainer用于指向列表项所在列表，例如：运行态、就绪态、堵塞态、挂起态

下图是列表项结构示意图：

1.2.3.迷你列表项

迷你列表项也是列表项，但迷你列表项仅用于标记列表的末尾和挂载其他插入列表中的列表项，用户是用不到迷你列表项的，在 list.h 文件中，有迷你列表项的相关定义，具体的代码所示：

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; /* 上一个列表项 */
};
typedef struct xMINI_LIST_ITEM MiniListItem_t;			/* 重定义成 MiniListItem_t */

• 成员变量xItemValue为列表项的值，这个值多用于按升序对列表中的列表项进行排序。
• 成员变量pxNext和pxPrevious分别用于指向列表中列表项的下一个列表项和上一个列
  表项。
• 迷你列表项相比于列表项，因为只用于标记列表的末尾和挂载其他插入列表中的列表项，
  因此不需要成员变量pxOwner和pxContainer，以节省内存开销。

挂载其他插入列表中的列表项：初始化列表的时候总需要一个列表项提供指向上一个和下一个的指针，用于挂载新来的列表项，迷你列表项结构示意图如下图所示：

二、列表相关API函数

2.1.列表相关API函数介绍

2.1.1.vListInitalise( )初始化列表函数

下面代码实现的功能是将列表结构体里面的成员赋值，将遍历列表的指针指向最后一个列表项；将列表项的值初始化至最大值为0xFFFFFFFF；将指向上一个和下一个的指针指向最后一个列表项；将列表中的列表项数量赋值为 0：

void vListInitialise(List_t * const pxList)		//参数内容：待初始化列表
{
	/* 初始化时，列表中只有 xListEnd，因此 pxIndex 指向 xListEnd */
	pxList->pxIndex = ( ListItem_t * ) &( pxList->xListEnd );
	 
	/* xListEnd 的值初始化为最大值，用于列表项升序排序时，排在最后 */
	pxList->xListEnd.xItemValue = portMAX_DELAY;
	 
	/* 初始化时，列表中只有 xListEnd，因此上一个和下一个列表项都为 xListEnd 本身 */
	pxList->xListEnd.pxNext = ( ListItem_t * ) &( pxList->xListEnd );
	pxList->xListEnd.pxPrevious = ( ListItem_t * ) &( pxList->xListEnd );
	 
	/*初始化时，列表中的列表项数量为 0（不包含 xListEnd） */
	pxList->uxNumberOfItems = ( UBaseType_t ) 0U;
}

下图是初始化后列表的结构图：

2.1.2.vListInitaliseItem( )初始化列表项函数

该函数只是把列表项所在列表指针指向空，其他成员都没有改动：

void vListInitialiseItem(ListItem_t * const pxItem)		//参数内容：待初始化列表项
{
 /* 初始化时，列表项所在列表设为空 */
 pxItem->pxContainer = NULL;
 
}

下图是初始化后的列表项结构图：

2.1.3.vListInsertEnd( )列表末尾插入列表项函数

该函数用于新的列表项插入 pxIndex 指针指向的列表项的前面，是一种无序的插入方法，它的参数有两个，第一个是需要插入的列表；第二个是新的列表项：

void vListInsertEnd(List_t * const pxList, ListItem_t * const pxNewListItem)
{
	/* 获取列表 pxIndex 指向的列表项 */
	ListItem_t * const pxIndex = pxList->pxIndex;
	
	/* 更新待插入列表项的指针成员变量 */
	pxNewListItem->pxNext = pxIndex;
	pxNewListItem->pxPrevious = pxIndex->pxPrevious;
	 
	/* 更新列表中原本列表项的指针成员变量 */
	pxIndex->pxPrevious->pxNext = pxNewListItem;
	pxIndex->pxPrevious = pxNewListItem;
	
	/* 更新待插入列表项的所在列表成员变量 */
	pxNewListItem->pxContainer = pxList;
	 
	/* 更新列表中列表项的数量 */
	( pxList->uxNumberOfItems )++;
}

下图插入列表项后的列表结构图：

2.1.4.vListInsert( )列表插入列表项函数

该函数用于新的列表项按升序排列插入列表，它有两个参数，第一个参数是需要插入的列表；第二个是待插入的新列表项：

void vListInsert(List_t * const pxList, ListItem_t * const pxNewListItem)
{
	//先定义一个指针用于寻找待插入的新列表项的上一个列表项，再定义一个变量用于获取新列表项的值用于比较
	ListItem_t * pxIterator;
	const TickType_t xValueOfInsertion = pxNewListItem->xItemValue;
	 
	/* 如果待插入列表项的值为最大值 */
	if( xValueOfInsertion == portMAX_DELAY )
	{
		/* 插入的位置为列表 xListEnd 前面 */
		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 )++;
}

下图是插入列表项后的列表结构图：

2.1.5.vListRemove( )列表移除列表项函数

该函数用于将列表项所在列表中移除，它的参数是待移除的列表项，返回值是一个整数，表示所在列表剩余的列表项的数量：

UBaseType_t uxListRemove(ListItem_t * const pxItemToRemove)
{
	List_t * const pxList = pxItemToRemove->pxContainer;
	 
	/* 从列表中移除列表项 */
	pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;
	pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;
	
	/* 如果 pxIndex 正指向待移除的列表项 */
	if( pxList->pxIndex == pxItemToRemove )
	{
		/* pxIndex 指向上一个列表项 */
		pxList->pxIndex = pxItemToRemove->pxPrevious;
	}
	else
	{
		mtCOVERAGE_TEST_MARKER();
	}
	 
	/* 将待移除列表项的所在列表指针清空 */
	pxItemToRemove->pxContainer = NULL;
	/* 更新列表中列表项的数量 */
	( pxList->uxNumberOfItems )--;
	 
	/* 返回列表项移除后列表中列表项的数量 */
	return pxList->uxNumberOfItems;
}

下图是移除列表项后的列表结构图：

三、列表项的插入和删除实验

3.1.实验设计

设计三个任务如下所示：

• start_task：用来创建下面两个任务
• task1：实现 LED0 每 500ms 闪烁一次，用来提示系统正在运行
• task2：调用列表和列表项相关的 API 函数，并且通过串口输出相应信息

3.2.软件设计

在 FreeRTOS 入口函数前面，定义测试列表和三个列表项：

List_t                  TestList;  
ListItem_t              ListItem1; 
ListItem_t              ListItem2; 
ListItem_t              ListItem3; 

并在 task2 函数里初始化列表和三个列表项，给这个三列表项进行赋值：

vListInitialise(&TestList);     
vListInitialiseItem(&ListItem1);
vListInitialiseItem(&ListItem2);
vListInitialiseItem(&ListItem3);

ListItem1.xItemValue = 40;
ListItem2.xItemValue = 60;
ListItem3.xItemValue = 50;

把列表项的地址打印出来，证明列表项之间的准确性。

3.2.1.列表插入列表项

在 task2 函数里面编写所有插入和删除函数，通过下面代码打印，可以知道最后的列表项地址为0cc，列表项 1、2、3 的地址分别是：

• ListItem1：0d8
• ListItem2：0ec
• ListItem3：100

printf("项目\t\t\地址\r\n");
printf("TestList\t\t0x%p\t\r\n", &TestList);
printf("TestList->pxIndex\t0x%p\t\r\n", TestList.pxIndex);
printf("TestList->xListEnd\t0x%p\t\r\n", (&TestList.xListEnd));
printf("ListItem1\t\t0x%p\t\r\n", &ListItem1);
printf("ListItem2\t\t0x%p\t\r\n", &ListItem2);
printf("ListItem3\t\t0x%p\t\r\n", &ListItem3);
printf("/**************************结束***************************/\r\n");
printf("按下KEY0键继续!\r\n\r\n\r\n");
while (key_scan(0) != KEY0_PRES)
{
    vTaskDelay(10);
}

在前面的初始化，task3 的值为 50，应该插入在 task1 和 task2 之间，下面将列表项 1、2、3 简称为 1、2、3；理论上来说，按升序排列，1 是最小的数值，2 是最大的数值，3 排中间，因此 1 的 Next 应该指向 3 的地址，1 的 Previous 应该指向 End （0cc）；2 的 Next 应该指向 End （0cc），2 的 Previous 应该指向 3 的地址；而 3 的 Next 应该指向 2 的地址，3 的 Previous 应该指向 1 的地址；最后通过串口输出的数据证明，情况确实如此：

//在列表分别插入列表项1、2、3
vListInsert((List_t*    )&TestList,        
            (ListItem_t*)&ListItem1); 
vListInsert((List_t*    )&TestList,       
            (ListItem_t*)&ListItem2);       
vListInsert((List_t*    )&TestList,        
            (ListItem_t*)&ListItem3);      
printf("项目\t\t\地址\r\n");
printf("TestList->xListEnd->pxNext\t0x%p\r\n", (TestList.xListEnd.pxNext));
printf("ListItem1->pxNext\t\t0x%p\r\n", (ListItem1.pxNext));
printf("ListItem2->pxNext\t\t0x%p\r\n", (ListItem2.pxNext));
printf("ListItem3->pxNext\t\t0x%p\r\n", (ListItem3.pxNext));
printf("TestList->xListEnd->pxPrevious\t0x%p\r\n", (TestList.xListEnd.pxPrevious));
printf("ListItem1->pxPrevious\t\t0x%p\r\n", (ListItem1.pxPrevious));
printf("ListItem2->pxPrevious\t\t0x%p\r\n", (ListItem2.pxPrevious));
printf("ListItem3->pxPrevious\t\t0x%p\r\n", (ListItem3.pxPrevious));
printf("/**************************结束***************************/\r\n");
printf("按下KEY0键继续!\r\n\r\n\r\n");
while (key_scan(0) != KEY0_PRES)
{
    vTaskDelay(10);
}

3.2.2.列表移除列表项

本次目标是移除列表项 2，只需要证明 1 的 Next 指向 3，1 的 Previous 指向 End（0cc）；3 的 Next 指向 End（0cc） ，3 的 Previous 指向 1：

uxListRemove((ListItem_t*   )&ListItem2); 	//需要移除的列表项
printf("项目\t\t\地址\r\n");
printf("TestList->xListEnd->pxNext\t0x%p\r\n", (TestList.xListEnd.pxNext));
printf("ListItem1->pxNext\t\t0x%p\r\n", (ListItem1.pxNext));
printf("ListItem3->pxNext\t\t0x%p\r\n", (ListItem3.pxNext));
printf("TestList->xListEnd->pxPrevious\t0x%p\r\n", (TestList.xListEnd.pxPrevious));
printf("ListItem1->pxPrevious\t\t0x%p\r\n", (ListItem1.pxPrevious));
printf("ListItem3->pxPrevious\t\t0x%p\r\n", (ListItem3.pxPrevious));
printf("/**************************结束***************************/\r\n");
printf("按下KEY0键继续!\r\n\r\n\r\n");
while (key_scan(0) != KEY0_PRES)
{
    vTaskDelay(10);
}

3.2.3.列表末尾插入列表项

该函数的设定是将新的列表项，插入到 pxIndex 所指的列表项的前面，由第一个步骤可以发现，指针 pxIndex 指向 End ，因此现在新的列表项将会在 End 前面插入，输出的结果和升序排列插入一样：

vListInsertEnd((List_t*     )&TestList,     //列表
               (ListItem_t* )&ListItem2);   //需要插入的列表项
printf("项目\t\t\地址\r\n");
printf("TestList->pxIndex\t\t0x%p\r\n", TestList.pxIndex);
printf("TestList->xListEnd->pxNext\t0x%p\r\n", (TestList.xListEnd.pxNext));
printf("ListItem1->pxNext\t\t0x%p\r\n", (ListItem1.pxNext));
printf("ListItem2->pxNext\t\t0x%p\r\n", (ListItem2.pxNext));
printf("ListItem3->pxNext\t\t0x%p\r\n", (ListItem3.pxNext));
printf("TestList->xListEnd->pxPrevious\t0x%p\r\n", (TestList.xListEnd.pxPrevious));
printf("ListItem1->pxPrevious\t\t0x%p\r\n", (ListItem1.pxPrevious));
printf("ListItem2->pxPrevious\t\t0x%p\r\n", (ListItem2.pxPrevious));
printf("ListItem3->pxPrevious\t\t0x%p\r\n", (ListItem3.pxPrevious));
printf("/**************************结束***************************/\r\n");

想要将 2 插入在指定列表项之前，只需修改指针 pxIndex 所指的列表项即可，例如：在列表项 1 前面插入：

TestList.pxIndex = &ListItem1; //pxIndex指向列表项1
vListInsertEnd((List_t*     )&TestList,     //列表
               (ListItem_t* )&ListItem2);   //需要插入的列表项
printf("项目\t\t\地址\r\n");
printf("TestList->pxIndex\t\t0x%p\r\n", TestList.pxIndex);
printf("TestList->xListEnd->pxNext\t0x%p\r\n", (TestList.xListEnd.pxNext));
printf("ListItem1->pxNext\t\t0x%p\r\n", (ListItem1.pxNext));
printf("ListItem2->pxNext\t\t0x%p\r\n", (ListItem2.pxNext));
printf("ListItem3->pxNext\t\t0x%p\r\n", (ListItem3.pxNext));
printf("TestList->xListEnd->pxPrevious\t0x%p\r\n", (TestList.xListEnd.pxPrevious));
printf("ListItem1->pxPrevious\t\t0x%p\r\n", (ListItem1.pxPrevious));
printf("ListItem2->pxPrevious\t\t0x%p\r\n", (ListItem2.pxPrevious));
printf("ListItem3->pxPrevious\t\t0x%p\r\n", (ListItem3.pxPrevious));
printf("/**************************结束***************************/\r\n");

2 的 Next 指向 1 ；2 的 Previous 指向 End：