1. 列表和列表项

列表和列表项

列表

列表是一个数据结构，用来追踪任务，列表中有一个指针指向列表项

列表是一个结构体，内部携带一个指针，指针指向列表项，列表项形成双向链式结构挂载在列表下

一个列表下面可以有很多的列表项，每个列表项都会有一个指针指向这个列表，下面是一个列表

typedef struct xLIST
{
	listFIRST_LIST_INTEGRITY_CHECK_VALUE
	configLIST_VOLATILE UBaseType_t uxNumberOfItems;	// 记录列表挂载列表项数量
	ListItem_t * configLIST_VOLATILE pxIndex;			// 指向列表项的指针，用于遍历列表
	MiniListItem_t xListEnd;							// 不会改变，永远指向首/尾列表项，xListEnd
	listSECOND_LIST_INTEGRITY_CHECK_VALUE
} List_t;
1
2
3
4
5
6
7
8

listFIRST_LIST_INTEGRITY_CHECK_VALUE与listSECOND_LIST_INTEGRITY_CHECK_VALUE用于检测列表的完整性，使能后自动添加变量

uxNumberOfItems：记录列表中列表项的数量

pxIndex：记录当前某个列表项的地址，用于遍历列表(指针，记录当前列表项位置，列表项按照升序排列，寻址访问对应列表项)

xListEnd：列表中的最后一个列表项，用来表示列表结束，是一个阉割版的列表项，迷你列表项（不要不必要的东西）

列表初始化

void vListInitialise( List_t * const pxList )
{
	pxList->pxIndex = ( ListItem_t * ) &( pxList->xListEnd );				// 初始化索引地址，默认挂载 xListEnd
	pxList->xListEnd.xItemValue = portMAX_DELAY;							// 辅助值 排序节点，xListEnd为最后一节点
	pxList->xListEnd.pxNext = ( ListItem_t * ) &( pxList->xListEnd );		// 当前列表为空，只挂载 xListEnd
	pxList->xListEnd.pxPrevious = ( ListItem_t * ) &( pxList->xListEnd );	// 再挂载是通过 xListEnd
	pxList->uxNumberOfItems = ( UBaseType_t ) 0U;							// 当前挂载列表项数量为0，链表节点计数器
	listSET_LIST_INTEGRITY_CHECK_1_VALUE( pxList );							// 宏，变量定义
	listSET_LIST_INTEGRITY_CHECK_2_VALUE( pxList );
}
1
2
3
4
5
6
7
8
9
10

初始化列表，由于列表项的数量为0，所以大多数据被初始化为0，各种指针指向xListEnd，也就是列表中的迷你列表项，也是双向列表的首尾

列表项

struct xLIST_ITEM
{
	listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE			// 宏值，列表项完整性考虑
	configLIST_VOLATILE TickType_t xItemValue;			// 列表项辅助值，进行排序
	struct xLIST_ITEM * configLIST_VOLATILE pxNext;		// 列表项 next 指针
	struct xLIST_ITEM * configLIST_VOLATILE pxPrevious;	// 列表项 prev 指针
	void * pvOwner;										// 列表项归属TCB
	void * configLIST_VOLATILE pvContainer;				// 列表项归属列表
	listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE
};
typedef struct xLIST_ITEM ListItem_t;
1
2
3
4
5
6
7
8
9
10
11

listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE与listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE用于检测列表项的完整性

xItemValue：当前列表项挂载的位置，记录列表项在链表中的位置（xListEnd是0）

pxNext：指向下一个列表项

pxPrevious：指向上一个列表项(实现双向链表)

pvOwner：记录列表项的拥有者(归属TCB)

pvContainer：记录列表项归属列表（就绪，阻塞列表）

迷你列表项

列表项的阉割版(主要是节省资源)，作为列表下挂列表项的头和尾

struct xMINI_LIST_ITEM		// 一般是xEndList
{
   listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE
   configLIST_VOLATILE TickType_t xItemValue;			// 列表项挂载值，列表项排序
   struct xLIST_ITEM * configLIST_VOLATILE pxNext;		// 列表项 next 指针
   struct xLIST_ITEM * configLIST_VOLATILE pxPrevious;	// 列表项 prev 指针
};
typedef struct xMINI_LIST_ITEM MiniListItem_t;
1
2
3
4
5
6
7
8

listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE用于检测迷你列表项的完整

xItemValue：用于记录列表项值

pxNext：指向下一个列表项

pxPrevious：指向上一个列表项

列表项初始化

void vListInitialiseItem( ListItem_t * const pxItem )
{
   pxItem->pvContainer = NULL;									// 仅仅只需要初始化列表项归属列表，表示该列表项没插入任何列表
   listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );
   listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE( pxItem );
}
1
2
3
4
5
6

列表项插入

末尾插入

找到列表项最后一项，也就是xListEnd的previous指针指向列表项

步骤：

1、移动列表项指针，找到列表最终列表项的项值(xListEnd是首也是尾，最后一个列表项就是(xListEnd - 1))

2、改变新插入列表项的指针，previous指向（xListEnd - 1）与next指向（xListEnd ）

3、改变(xListEnd - 1)的next指针

4、改变（xListEnd）的previous指针(xListEnd->privious 指向新插入的列表项)

5、标记列表项归属

6、列表的列表项数量自增(列表项的项值也要改变)

void vListInsertEnd( List_t * const pxList, ListItem_t * const pxNewListItem )// 指定列表项要插入哪个列表，以及要插入的列表项
{
	ListItem_t * const pxIndex = pxList->pxIndex;	// 列表项索引，获取当前索引，
	pxNewListItem->pxNext = pxIndex;				// 新插入列表项 加入链表， pxNewListItem->pxNext 指向 xEnd
	pxNewListItem->pxPrevious = pxIndex->pxPrevious;// 新插入列表项 加入链表， pxNewListItem->pxPrev 指向 xEnd->pre 
	pxIndex->pxPrevious->pxNext = pxNewListItem;	// 改变 （xEnd - 1）的 next 指针，
	pxIndex->pxPrevious = pxNewListItem;			// 改变 xEnd 的 previous 指针
	pxNewListItem->pvContainer = ( void *) pxList;	// 新插入列表项的归属列表
	( pxList->uxNumberOfItems )++;					// 列表项数目自增
}
1
2
3
4
5
6
7
8
9
10

相当于是在 xListEnd 前面插入一个新的列表项（改变 xListEnd的pre指针）

一共需要改变四个指针，新插入的列表项的per和next指针，之（xListEnd - 1）的next指针，xListEnd的pre指针

pxIndex 值是第0个列表项，也是最后一个列表项(双向列表) xListEnd，通过next指针遍历链表

升序插入

通过列表项项值xItemValue比对，查找插入位置

步骤：

1、通过要插入的列表项的项值，找到要插入列表项的前一个列表项( 项值 - 1)

2、改变(项值 - 1)的next指针，新插入列表项的previous指针，新插入列表项的next指针

3、改变(项值 + 1)的previous指针

4、标记新插入列表项归属列表

5、列表的列表项数量自增

void vListInsert( List_t * const pxList, ListItem_t * const pxNewListItem )
{
	ListItem_t pxIterator;							// 新建临时列表项，用于遍历列表
	const TickType_t xValueOfInsertion = pxNewListItem->xItemValue;	// 获取要插入列表项的项值
	if ( xValueOfInsertion == portMAX_DELAY )		// 要插入列表项项值判断位置，是否在链表最后
	{
		pxIterator = pxList->xListEnd.pxPrevious;	// 索引值在链表最后，直接挂载在 End后，改变 xListEnd.pxPrevious
	}
	else
	{
		for (	pxIterator = ( ListItem_t * ) &( pxList->xListEnd );// 索引从链表最后开始往前索引
				pxIterator->pxNext->xItemValue <= xValueOfInsertion;// 通过next索引，与要插入列表项值比较
				pxIterator = pxIterator->pxNext )					// 移动next指针进行索引
		{
			// xValueOfInsertion > pxIterator->pxNext->xItemValue，即pxIterator为要插入列表项位置前一个
		}
	}
	pxNewListItem->pxNext = pxIterator->pxNext;			// 改变要插入列表项的 next 指针
	pxNewListItem->pxNext->pxPrevious = pxNewListItem;	// 改变要插入列表项的 prev 指针
	pxNewListItem->pxPrevious = pxIterator;				// 
	pxIterator->pxNext = pxNewListItem;

	pxNewListItem->pvContainer = ( void * ) pxList;		// 通过pvContainer标记列表项属于哪个列表
	( pxList->uxNumberOfItems )++;						// 列表的列表项数目自增
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

删除

步骤：

1、设置要删除列表项(项值 - 1)的next指针

2、设置要删除列表项(项值 + 1)的previous指针

3、清空要删除列表项的previous与next指针

4、清除列表项归属列表标记

5、列表项数量自减

void vListDelete( List_t * const pxList, ListItem_t * const pxNewListItem )
{
   ListItem_t presentListItem;				// 使用临时列表项遍历列表项
   presentListItem = pxList->pxIndex;		// 获取当前列表项，此时为xListEnd

   if( pxNewListItem->xItemValue == portMAX_DELAY)	// 当前索引位置为链表最后位置
   {
   	  presentListItem->xItemValue = pxList->pxIndex;	// 直接插入最后
   }
   else
   {
   	for( presentListItem->xItemValue = pxList->pxIndex;				/* 从起始列表项开始*/
   		 presentListItem->xItemValue = pxNewListItem->xItemValue;	/* 当列表项匹配就结束*/
   		  presentListItem = presentListItem->next);					/* 移动next指针*/
   }
   presentListItem->pxPrevious->pxNext = pxList->pxIndex;				// 要删除节点 前一个的next指针
   presentListItem->pxNext->pxPrevious = presentListItem->pxPrevious;	// 要删除节点 下一个的prev指针
   presentListItem->pxNext = NULL;										// 要删除节点自己的指针
   presentListItem->pxPrevious = NULL;

   presentListItem->pvContainer = NULL;
   pxList->xItemValue--;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

任务的执行由系统来调度，为了调度任务每个任务都会定义一个任务控制块，这个任务控制块相当于任务的身份证，保存有任务的所有信息

系统堆任务的全部操作都是通过任务控制块来实现的

任务块中的列表项，都标记有归属列表，通过列表可以遍历所有的列表项