FreeRTOS实时操作系统的列表与列表项操作示例

//列表项数据结构
typedef struct xLIST_ITEM
{
	TickType_t xItemValue;  //辅助值，用作节点做顺序排序
	struct xLIST_ITEM * pxNext;//后继指针
	struct xLIST_ITEM * pxPrevious;//前驱指针
	void * pvOwner;      //指向拥有该列表项的内核对象，通常是TCB
	void * pvContainer;  //指向该列表项所在的列表
}ListItem_t;

void vListInitialiseItem(ListItem_t * const pxItem)
{
//初始化该列表项所在列表指针指向NULL，表示还没插入任何列表
		pxItem->pvContainer = NULL;
}

typedef struct xLIST
{
	UBaseType_t uxNumberOfItems; //指示这条列表上有多少个列表项
	ListItem_t * pxIndex; //列表项索引指针
	MiniListItem_t xListEnd; //列表最后一个列表项
}List_t;

typedef struct xMINI_LIST_ITEM
{
	TickType_t xItemValue;//辅助值，用作节点做顺序排序
	struct xLIST_ITEM * pxNext;//后继指针
	struct xLIST_ITEM * pxPrevious;//前驱指针
}MiniListItem_t;

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);	
	//表示此时列表中有0个列表项
	pxList->uxNumberOfItems = (UBaseType_t)0U;
}

void vListInsertEnd(List_t * const pxList,ListItem_t * const pxNewListItem)
{
    //取列表项索引指针，此时该指针指向最后一个节点
	ListItem_t * const pxIndex = pxList->pxIndex;
	//新插入的列表项前驱指针指向最后一个节点
	pxNewListItem->pxNext = pxIndex;
	//新插入的列表项的后继指针也指向最后一个节点
	pxNewListItem->pxPrevious = pxIndex->pxPrevious;
	//列表的最后一个节点的后继指针指向新插入的列表项
	pxNewListItem->pxPrevious->pxNext = pxNewListItem;
	//列表的最后一个节点的前驱指针也指向新插入的列表项
	pxIndex->pxPrevious = pxNewListItem;
	//新插入的列表项是输入该列表的
	pxNewListItem->pvContainer = (void*) pxList;
	 //该列表中列表项数目+1
	(pxList->uxNumberOfItems)++;
}

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)
			{
			}
	}
	//对于下图此时pxIterator指向List_item1
	//此时pxIterator->pxNext是List_item3地址
	pxNewListItem->pxNext = pxIterator->pxNext;//1
	//pxNewListItem->pxNext->pxPrevious是item3的前驱指针指向新列表项item2
	pxNewListItem->pxNext->pxPrevious = pxNewListItem;
	//新列表项item2的前驱指针指向pxIterator即item1
	pxNewListItem->pxPrevious = pxIterator;
	//pxIterator即item1的后继指向新列表项item2
	pxIterator->pxNext = pxNewListItem;
	pxNewListItem->pvContainer = (void*) pxList;
	(pxList->uxNumberOfItems)++;
}

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;
	if(pxList->pxIndex == pxItemToRemove)
	{
			pxList->pxIndex = pxItemToRemove->pxPrevious;
	}
	//该列表项所有者置空
	pxItemToRemove->pvContainer = NULL;
	(pxList->uxNumberOfItems)--;
	return pxList->uxNumberOfItems;
}

List_t List_Test;
ListItem_t List_Item1;
ListItem_t List_Item2;
ListItem_t List_Item3;
int main(void)
{
	//初始化列表
    vListInitialise(&List_Test);
    //初始化列表项
    vListInitialiseItem(&List_Item1);
	List_Item1.xItemValue = 1;
    vListInitialiseItem(&List_Item2);
	List_Item2.xItemValue = 2;
    vListInitialiseItem(&List_Item3);
	List_Item3.xItemValue = 3;
    vListInsert(&List_Test,&List_Item1);
	vListInsert(&List_Test,&List_Item3);
	vListInsert(&List_Test,&List_Item2);
	while(1);
}