（一）、freeRTOS基础列表和列表项

1.0、说明

在想慢慢深入理解freeRTOS的步伐中，其中最关键的第一点，先理解freeRTOS在内部是怎么组织数据管理的，是单链表还是数据等等，所以我们在开始深入理解freeRTOS的时候，得先把基础理解，而深入理解freeRTOS的第一步就是freeRTOS的数据结构——列表和列表项。

1.1、列表

在freeRTOS结构中，关于数据结构的列表是基础，只有理解这一块，后面理解起创建任务会方便很多，列表和列表项在list.c和.h文件中。

在freeRTOS代码宗声明了列表的定义：

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;

其中关于这两个listFIRST_LIST_INTEGRITY_CHECK_VALUE 和listSECOND_LIST_INTEGRITY_CHECK_VALUE这两个是检查列表完整性的，在这里我们不深入理解这一块。

所以最终确定的列表如下：

typedef struct xLIST
{
			
	volatile UBaseType_t uxNumberOfItems;
	ListItem_t * configLIST_VOLATILE pxIndex;			
	MiniListItem_t xListEnd;							
		
} List_t;

我们学过链表的时候，一般都会设定一个链表头，你可以这么理解这个就是链表头，所以下面三个参数分别是：

uxNumberOfItems：列表项的统计记录
pxIndex：当前索引
这个我得解释一下，在freeRTOS中，采用的是双环列表来做数据管理的，也就是所列表头会随着列表项的移动而改变，所以需要一个变量来记录当前列表项的开头，而这个参数就是记录环形列表的开头。

xListEnd：这个尾部记录。
这个同上面个一个道理，你存在一个开头，肯定存在一个结尾，方便遍历。

关于上面那三个参数，我们先了解到这里。

我们了解一下程序的初始化：

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 );
	listSET_LIST_INTEGRITY_CHECK_2_VALUE( pxList );
}

在这里我们要记住freeRTOS里面是采用双环链表做结构的，而且变量xListEnd是一个迷你的列表项。

对于第1行：
因为当前是空列表，所以当前pxIndex指针指向最后一个列表项，所以我们也可以知道如果当前索引指向最后一个列表项的话，就意味着该列表是空列表。

对于第2行：
对最后一个列表项赋值，为最大，通过跳转发现portMAX_DELAY是0xffffffffUL。

对于第3行：
因为是空列表项，所以下一个指向最后一个列表项。

对于第4行：
因为是空列表项，所以上一个指向最后一个列表项。

对于第5行：
因为是空列表项，所以当前列表个数uxNumberOfItems统计为0。

所以最终如下图所示：

1.2、列表项

既然有列表，那么肯定存在列表项作为列表的元素，前面我们提到过freeRTOS采用的是双环形链表来存储和管理数据。

我们看一下定义：

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;										
	void * configLIST_VOLATILE pvContainer;				
	listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE			
typedef struct xLIST_ITEM ListItem_t;					

同样的，我们将安全列表完整性删除掉，我们不深入了解。

struct xLIST_ITEM
{		
	configLIST_VOLATILE TickType_t xItemValue;			
	struct xLIST_ITEM * configLIST_VOLATILE pxNext;		
	struct xLIST_ITEM * configLIST_VOLATILE pxPrevious;	
	void * pvOwner;										
	void * configLIST_VOLATILE pvContainer;						
typedef struct xLIST_ITEM ListItem_t;					

一下几个变量的解释：
xItemValue：这个就是记录值
pxNext：因为是双向列表，所以这个是指向下一个链表的指针。
pxPrevious：因为是双向列表，所以这个是指向上一个链表的指针。
pvOwner：该列表项归谁所有。
pvContainer：归哪个列表所有。

这里注意一下，pvOwner和pvContainer是有区别的，一般pvOwner指的是任务，就是归属于这个任务，但是在同一个任务下，存在多个链表，而pvContainer就是指向那个列表。

了解了基本参数，我们看一下初始化过程：

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

列表项的初始化很简单，只是初始化pxItem->pvContainer这个值，为何这样我猜想是再别的地方做处理，所以这里我们暂时不去深究他了，遇到我们在作总结。

1.3、列表项的插入

列表和列表项这些基础的概念了解，接下来就是如何插入列表项到列表中呢？在我没有贴代码的时候，你会怎么做呢？在这里freeRTOS是采用两种方式来管理双环列表，第一种是根据列表项的值进行升序插入。

另外一种是直接插入尾部，因为我们记录着尾部的信息。

我们先看一下升序插入的方法，也没那么复杂。

void vListInsert( List_t * const pxList, ListItem_t * const pxNewListItem )
{
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 ) 
		{
		}
	}

	pxNewListItem->pxNext = pxIterator->pxNext;
	pxNewListItem->pxNext->pxPrevious = pxNewListItem;
	pxNewListItem->pxPrevious = pxIterator;
	pxIterator->pxNext = pxNewListItem;

	pxNewListItem->pvContainer = ( void * ) pxList;

	( pxList->uxNumberOfItems )++;
}

在这里我将注释去掉，感兴趣的同学可以直接查阅源代码。

因为我们是根据升序来插入的，那么第一步就是取值出来做比较，如果是最大值，直接插入到最后，但是插入到最后的前面还是后面呢，因为最后一个也是最大值。

要想理解这个，我们时刻记得这是一个双环链表，那就简单了，我们看这两句代码：

pxIterator = pxList->xListEnd.pxPrevious;
....
pxNewListItem->pxNext = pxIterator->pxNext;

pxIterator是xListEnd上一个列表项，那么pxIterator->pxNext就意味着是xListEnd本身了，所以新链表pxNewListItem下一个pxNext指向xListEnd就说名是他插入在xListEnd的前面。

如果不是最大值，这执行下面这个语句：

for( pxIterator = ( ListItem_t * ) &( pxList->xListEnd ); pxIterator->pxNext->xItemValue <= xValueOfInsertion; pxIterator = pxIterator->pxNext ) 
{
}

他就是遍历到比他大的位置，但是在这发现判断条件是<=，如果相等的话，这里是插入到最后面去的，并不是之前最大值插入的那个前面，这里注意一下。

可能会有人有疑惑，为什么起始是pxIterator = ( ListItem_t * ) &( pxList->xListEnd );，在这里我在声明一下，记得他是一个双环链表，这个是最大的位置，那么他下一个位置肯定是最小的，这也是为啥如果你再插入一个最大值得列表项进来需要插入在他前面，因为方便遍历，我最大的下一个肯定是最小。

接下来就是插入的四句重点语句了：

	pxNewListItem->pxNext = pxIterator->pxNext;
	pxNewListItem->pxNext->pxPrevious = pxNewListItem;
	pxNewListItem->pxPrevious = pxIterator;
	pxIterator->pxNext = pxNewListItem;

我暂时不讲这四个语句，我们先根据自己的想来进行图示列表项插入过程。

假如下面这个列表：

突然来了一个列表项，想要插入进去。

我们再来看一遍遍历的那个代码：

因为这个ListItem3的值是50，也就是当他执行到ListItem1->next的时候就指向ListItem2，可是此刻ListItem2的值是60，所以条件不成立，那么此刻 pxIterator就是ListItem1了，因为ListItem3需要插入ListItem1的后面所以,如果你是在无法理解下面这四句代码，可以将ListItem1 替换pxIterator，你可能就容易理解多了。

（我提问一下，他为啥是这个顺序，能换么？）
ListItem3->next = pxIterator->next
ListItem3->next ->pxPrevious = ListItem3;
ListItem3->pxPrevious = pxIterator;
pxIterator->next = ListItem3;

你会发现上面那四句代码就是我们源码中的这四句：

	pxNewListItem->pxNext = pxIterator->pxNext;
	pxNewListItem->pxNext->pxPrevious = pxNewListItem;
	pxNewListItem->pxPrevious = pxIterator;
	pxIterator->pxNext = pxNewListItem;

最后这两句语句：

	pxNewListItem->pvContainer = ( void * ) pxList;

	( pxList->uxNumberOfItems )++;

一个是确定归属到那个列表，一个是列表个数自增1。

1.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;

	/* Only used during decision coverage testing. */
	mtCOVERAGE_TEST_DELAY();

	pxIndex->pxPrevious->pxNext = pxNewListItem;
	pxIndex->pxPrevious = pxNewListItem;

	pxNewListItem->pvContainer = ( void * ) pxList;

	( pxList->uxNumberOfItems )++;
}

前面我们提到过pxIndex是双环链表的开头，所以想要往尾部插入，只需要pxIndex上一个就是尾部，直接插入即可。

目前因为我涉及还未深入，所以关于升序插入和尾部插入可能在freeRTOS中各有各的用途，目前我们先明白这两种插入方式。

1.5、列表项删除

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

删除也不难理解，如果删除的是开头索引，则将上一个作为开头索引。

关于freeRTOS中的列表和列表项写到这里。