freertos 源码解读 list链表图解

FreeRTOS 链表结构图解

本文涉及的FreeRTOS Kernel 代码源文件
FreeRTOS-Kernel-10.4.6list.c
FreeRTOS-Kernel-10.4.6includelist.h

零）链表基础
链表分类

链表分为单链表、双向链表、循环链表（双向、单向）。上图非常清晰

链表操作，FreeRTOS采用双向循环链表

双向链表的删除动作，插入动作如下

双向链表的删除

阅读完链表的基本操作，开始对freertos的链表做分析

FreeRTOS 链表的结构分解

一）链表的元素/节点/Item

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

链表节点的结构图
链表值：链表所存值
上一个/下一个集节点：链表的基本结构，指向本身结构体的数据结构
所在链表：节点所处的链表
所在的数据结构：链表Item作为一个其他数据结构的成员，指向这个结构

二）精简/最小链表节点/Item

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;

链表节点的基本形态，主要作用是描述根节点，根节点不需要像平常节点一样保存那么多信息，更多的是表明自己是根节点

非常基础的链表结构

三）链表

typedef struct xLIST
{
	listFIRST_LIST_INTEGRITY_CHECK_VALUE				
	configLIST_VOLATILE UbaseType_t uxNumberOfItems;
	ListItem_t * configLIST_VOLATILE pxIndex;			
	MiniListItem_t xListEnd;							
	listSECOND_LIST_INTEGRITY_CHECK_VALUE				
} List_t;

链表本身通过listEnd找到链表，是链表结构的抽象。

四）链表结构体之间的关系

五）链表的初始化

void vListInitialise( List_t * const pxList )
{
	
	pxList->pxIndex = ( ListItem_t * ) &( pxList->xListEnd );			

	
	pxList->xListEnd.xItemValue = portMAX_DELAY;

	
	pxList->xListEnd.pxNext = ( ListItem_t * ) &( pxList->xListEnd );	
	pxList->xListEnd.pxPrevious = ( ListItem_t * ) &( pxList->xListEnd );

	pxList->uxNumberOfItems = ( UbaseType_t ) 0U;

	
	listSET_LIST_INTEGRITY_CHECK_1_VALUE( pxList );
	listSET_LIST_INTEGRITY_CHECK_2_VALUE( pxList );
}

空链表初始化，因为末尾节点是存在的所以初始化就是把ListEnd进行装填
因为只有一个元素

当前索引，上一个/下一个Item 都指向唯一的节点ListEnd，End需要保持在末尾所以ItemValue为数据结构最大值FFFF（freertos的链表排序依照ItemValue大小排序）

ListEnd末尾元素是为了链表抽象结构而存在的，本身没有数据意义。此时链表数据记为 0

六）链表操作

void vListInsertEnd( List_t * const pxList, ListItem_t * const pxNewListItem )
void vListInsert( List_t * const pxList, ListItem_t * const pxNewListItem )
UbaseType_t uxListRemove( ListItem_t * const pxItemToRemove )

FreeRtos 的链表是专用的，所以在结构定义上有它自己的特点。归根结底它还是链表，有着基本的链表结构（数据，前指针，后指针）。那么基本的数据操作也是适用的。

链表的删除动作，请产考文章开头的链表图解链表元素删除动作

freertos的链表节点是按照Value值排序的，做操作的时通过Value值找到索引，并且有index的概念

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;

	
	mtCOVERAGE_TEST_DELAY();

	
	if( pxList->pxIndex == pxItemToRemove )
	{
		pxList->pxIndex = pxItemToRemove->pxPrevious;
	}
	else
	{
		mtCOVERAGE_TEST_MARKER();
	}

	pxItemToRemove->pvContainer = NULL;
	( pxList->uxNumberOfItems )--;

	return pxList->uxNumberOfItems;
}

链表的插入动作。操作请参考文章开头图片，请注意pxIndex的位置从而确定在什么位置加入新节点

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

本文开头零章使用了 “半纸渊”博主的图片，在此注明

freertos 源码解读 list链表图解

Java相关栏目本月热门文章