FreeRTOS内核——数据结构链表

1.数据结构

1.1 list与list item

也就是c语言中的链表与链表结点

单项链表很少用，多用双向链表

1.1.1 list (List_t)

list就是一串链表，具体来说就是这一串链表的头结点。因此，一个list对象就代表着一串链表，通过它可以找到这一串链表中的每一个结点

结构体定义如下：

typedef struct xLIST
{	
	UBaseType_t uxNumberOfItems;		/*链表结点计数器*/
	ListItem_t * pxIndex;				/*链表结点索引地址*/
	MiniListItem_t xListEnd;			/*链表最后一个结点*/

} List_t

1.1.2 list item (ListItem_t)

所谓item就是链表中每一个结点的结构体

struct xLIST_ITEM
{
	TickType_t xItemValue;						/* 辅助值，用于结点进行顺序排列  */
	struct xLIST_ITEM *  pxNext;				/* 指向链表下一个节点 */
	struct xLIST_ITEM *  pxPrevious;			/* 指向链表上一个结点 */
	void * pvOwner;								/* 指向拥有该节点的内核对象，通常是TCB */
	void * pvContainer							/* 指向该节点所在的链表 */
}

1.2 链表的相关操作

1.2.1 链表节点初始化 vListInitialiseItem()

void vListInitialiseItem( ListItem_t * const pxItem )
{
	pxItem->pvContainer = NULL;
}

1.2.2 链表根节点初始化 vListInitialise()

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()

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;

   /* Remember which list the item is in. */
   pxNewListItem->pvContainer = ( void * ) pxList;

   ( pxList->uxNumberOfItems )++;
}

1.2.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 )
	{
		pxIterator = pxList->xListEnd.pxPrevious;
	}
	else
	{
	/* 不断迭代，找到节点要插入的位置 ,因为链表的最后一个节点的pxNext永远指向第一个节点 */
		for( pxIterator = ( ListItem_t * ) &( pxList->xListEnd ); pxIterator->pxNext->xItemValue <= xValueOfInsertion; pxIterator = pxIterator->pxNext ) 
		{
			/* There is nothing to do here, just iterating to the wanted
			insertion position. */
		}
	}
	/* 将节点插入 */
	pxNewListItem->pxNext = pxIterator->pxNext;
	pxNewListItem->pxNext->pxPrevious = pxNewListItem;
	pxNewListItem->pxPrevious = pxIterator;
	pxIterator->pxNext = pxNewListItem;

	/* Remember which list the item is in.  This allows fast removal of the
	item later. */
	pxNewListItem->pvContainer = ( void * ) pxList;

	( pxList->uxNumberOfItems )++;
}

1.2.5 将节点从链表中删除 uxListRemove()

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

1.2.6 节点带参宏函数

1.2.6.1 初始化节点拥有者

#define listSET_LIST_ITEM_OWNER( pxListItem, pxOwner )		( ( pxListItem )->pvOwner = ( void * ) ( pxOwner ) )

1.2.6.2 获取节点拥有者

#define listGET_LIST_ITEM_OWNER( pxListItem )	( ( pxListItem )->pvOwner )

1.2.6.3 初始化节点排序辅助值

#define listSET_LIST_ITEM_VALUE( pxListItem, xValue )	( ( pxListItem )->xItemValue = ( xValue ) )

1.2.6.4 获取节点排序辅助值

#define listGET_LIST_ITEM_VALUE( pxListItem )	( ( pxListItem )->xItemValue )

1.2.6.5 获取链表根节点的节点计数器的值

#define listGET_ITEM_VALUE_OF_HEAD_ENTRY( pxList )	( ( ( pxList )->xListEnd ).pxNext->xItemValue )

1.2.6.6 获取链表的入口节点

#define listGET_HEAD_ENTRY( pxList )	( ( ( pxList )->xListEnd ).pxNext )

1.2.6.7 获取节点的下一个节点

#define listGET_NEXT( pxListItem )	( ( pxListItem )->pxNext )

1.2.6.8 获取链表的最后一个节点

#define listGET_END_MARKER( pxList )	( ( ListItem_t const * ) ( &( ( pxList )->xListEnd ) ) )

1.2.6.9 判断链表是否为空

#define listLIST_IS_EMPTY( pxList )	( ( BaseType_t ) ( ( pxList )->uxNumberOfItems == ( UBaseType_t ) 0 ) )

1.2.6.10 获取链表节点数

#define listCURRENT_LIST_LENGTH( pxList )	( ( pxList )->uxNumberOfItems )

1.2.6.11 获取链表第一个节点的OWNER即TCB

#define listGET_OWNER_OF_NEXT_ENTRY( pxTCB, pxList )										\
{																							\
List_t * const pxConstList = ( pxList );													\
	/* Increment the index to the next item and return the item, ensuring */				\
	/* we don't return the marker used at the end of the list.  */							\
	( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext;							\
	if( ( void * ) ( pxConstList )->pxIndex == ( void * ) &( ( pxConstList )->xListEnd ) )	\
	{																						\
		( pxConstList )->pxIndex = ( pxConstList )->pxIndex->pxNext;						\
	}																						\
	( pxTCB ) = ( pxConstList )->pxIndex->pvOwner;											\
}