freertos内核原理学习 Day1(链表)

这篇具有很好参考价值的文章主要介绍了freertos内核原理学习 Day1(链表)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1.freertos列表与列表操作

1.1链表各节点定义（头文件list.h中）

1.1.1普通节点定义

1.1.2mini节点定义

1.1.3根节点定义

1.2链表操作（源文件list.c中）

1.2.1链表节点初始化

1.2.2链表根节点初始化

1.2.3插入节点到链表尾部

1.2.4将节点按“升序”排列后插入到链表中

1.2.5将节点从链表中删除

1.3仿真

1.freertos列表与列表操作

1.1链表各节点定义（头文件list.h中）

1.1.1普通节点定义

普通节点元素：

辅助排序值(xitemvalue);节点排序时确定当前节点处于链表的第几位

指向下一节点指针(pxnext);

指向上一节点指针(pxprevious);

指向内核对象指针(pvowner);

指向节点所在链表(pvcontainer);根节点代表的就是当前链表

freertos内核原理学习 Day1(链表),7天学会freertos内核原理,学习

struct xLIST_ITEM
{
	TickType_t xItemValue;             /* 辅助值，用于帮助节点做顺序排列 */			
	struct xLIST_ITEM *  pxNext;       /* 指向链表下一个节点 */		
	struct xLIST_ITEM *  pxPrevious;   /* 指向链表前一个节点 */	
	void * pvOwner;					   /* 指向拥有该节点的内核对象，通常是TCB */
	void *  pvContainer;		       /* 指向该节点所在的链表 */
};
typedef struct xLIST_ITEM ListItem_t;  /* 节点数据类型重定义 */

1.1.2mini节点定义

mini节点：作为双向链表的结尾；（双向链表的头即是尾，尾即是头）
mini节点元素组成：
辅助排序值(xitemvalue);
指向下一节点指针(pxnext);
指向上一节点指针(pxprevious);

struct xMINI_LIST_ITEM
{
	TickType_t xItemValue;                      /* 辅助值，用于帮助节点做升序排列 */
	struct xLIST_ITEM *  pxNext;                /* 指向链表下一个节点 */
	struct xLIST_ITEM *  pxPrevious;            /* 指向链表前一个节点 */
};
typedef struct xMINI_LIST_ITEM MiniListItem_t;

1.1.3根节点定义

根节点元素组成：
链表节点计数器(uxnumberofitems);
链表节点索引指针(pxindex);用于指向链表节点时用
链表最后节点(MiniListItem_t);
mini节点元素；根节点作为双向链表的起始，故其也是链表的结尾

typedef struct xLIST
{
	UBaseType_t uxNumberOfItems;    /* 链表节点计数器 */
	ListItem_t *  pxIndex;			/* 链表节点索引指针 */
	MiniListItem_t xListEnd;		/* 链表最后一个节点 */
} List_t;

1.2链表操作（源文件list.c中）

1.2.1链表节点初始化

执行操作如下：
普通节点其所在链表指针置空（表节点还未被加入任何链表）

void vListInitialiseItem( ListItem_t * const pxItem )
{
	/* 初始化该节点所在的链表为空，表示节点还没有插入任何链表 */
	pxItem->pvContainer = NULL;
}

1.2.2链表根节点初始化

执行操作如下：
根节点的下/上一节点指针指向自己(表还未有节点加入链表)，xItemValue置为最大(由于根节点必须在链表末尾/起始，为保证根节点在链表末尾，置根节点的辅助排序值为所允许的最大值，portMAX_DELAY为32位的最大值：0xffffffff)，初始化节点计数器为0(表还未有节点加入链表)

void vListInitialise( List_t * const pxList )
{
	/* 将链表索引指针指向最后一个节点 */
	pxList->pxIndex = ( ListItem_t * ) &( pxList->xListEnd );
	/* 将链表最后一个节点的辅助排序的值设置为最大，确保该节点就是链表的最后节点 */
	pxList->xListEnd.xItemValue = portMAX_DELAY;
    /* 将最后一个节点的pxNext和pxPrevious指针均指向节点自身，表示链表为空 */
	pxList->xListEnd.pxNext = ( ListItem_t * ) &( pxList->xListEnd );
	pxList->xListEnd.pxPrevious = ( ListItem_t * ) &( pxList->xListEnd );
	/* 初始化链表节点计数器的值为0，表示链表为空 */
	pxList->uxNumberOfItems = ( UBaseType_t ) 0U;
}

1.2.3插入节点到链表尾部

注：vListInsertEnd函数操作只能用于插入第一个节点时用，因为其并没有考虑到当根节点下已有普通节点的情况；

执行操作如下：

普通节点的下一节点指针->根节点；普通节点的上一节点指针->根节点；

根节点的下一节点指针->加入的普通节点；根节点的上一节点指针->加入的普通节点；

普通节点的链表指针->根节点（表其处于当前根节点的链表中）；
节点插入完成初始化节点计数器+1(表有1个节点加入链表)；

void vListInsertEnd( List_t * const pxList, ListItem_t * const pxNewListItem )
{
	ListItem_t * const pxIndex = pxList->pxIndex;

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

	/* 记住该节点所在的链表 */
	pxNewListItem->pvContainer = ( void * ) pxList;

	/* 链表节点计数器++ */
	( pxList->uxNumberOfItems )++;
}

1.2.4将节点按“升序”排列后插入到链表中

执行操作如下：

注：迭代指针pxinteror指向的是待插入节点在其插入链表后的上一节点；

1.插入节点排序值 = 根节点初始化排序值时：认为此节点要插入到链表末尾，迭代指针指向上一次链表末尾的普通节点；

2.插入节点排序值 < 根节点初始化排序值时：迭代指针指向根节点，并开始遍历直到找到序号刚好<=插入节点排序值，此时迭代指针刚好指向要插入节点插入后的上一个节点；

由于迭代指针指向的是“待插入节点插入链表后的上一节点”，则在新节点插入时迭代指针的下一节点指针指向新节点，新节点的上一节点指针指向迭代指针，新节点的下一节点等于“新节点未插入时迭代指针的下一节点”，新节点的下一节点的上一节点更新指向为新节点；

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

1.2.5将节点从链表中删除

执行操作如下：

获取要被移除节点所在的链表信息，被移除节点的上一节点其下一节点指针更新为被移除节点的上一节点，被移除节点的下一节点其上一节点指针更新为被移除节点的上一节点，若此时pxindex引导指针指向的是被移除的节点则将其指向更新为被移除节点的上一节点（pxindex引导指针必须指向其自己所在的链表，被移除节点已经不属于当前链表，所以索引指针不能指向它），将被移除节点所属链表项置空（表被移除节点现在已不属于任何链表），最后将链表节点计数器-1；

UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove )
{
	/* 获取节点所在的链表 */
	List_t * const pxList = ( List_t * ) pxItemToRemove->pvContainer;
	pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;
	pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;
	/* Make sure the index is left pointing to a valid item. */
	if( pxList->pxIndex == pxItemToRemove )
	{
		pxList->pxIndex = pxItemToRemove->pxPrevious;
	}
	/* 初始化该节点所在的链表为空，表示节点还没有插入任何链表 */
	pxItemToRemove->pvContainer = NULL;
	/* 链表节点计数器-- */
	( pxList->uxNumberOfItems )--;
	/* 返回链表中剩余节点的个数 */
	return pxList->uxNumberOfItems;
}