freeRTOS链表学习笔记

链表是RTOS的核心之一，链表的作用主要服务于RTOS的任务之间的调度。任务的唤醒和休眠、任务的调度等都基于链表实现。阅读了freeRTOS链表的源码后，决定梳理一遍链表相关的源码，用于加深对链表的理解。其中对源码进行了一些删减，方便理解理解和阅读。文中的代码重新书写了一遍，可能和源码有些不一样。

头文件其中只涉及3个结构体，其中struct xMiniLIST_ITEM 是struct xLIST_ITEM 的简化版，则实际上只涉及2个结构体。

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

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

全部源码

#ifndef _LIST_H
#define _LIST_H

#define TickType_t  unsigned int
#define UbaseType_t unsigned int

#define portMAX_DELAY 0xFFFFFFFF

struct  xLIST_ITEM
{
	TickType_t xItemValue;			

	struct xLIST_ITEM *pxNext; 	
	struct xLIST_ITEM *pxPrevious;
	void* pvOwner; 	

	void* pvContainer; 	

};


typedef	struct xLIST_ITEM ListItem_t;


struct  xMiniLIST_ITEM
{
	TickType_t xItemValue;  
	struct xLIST_ITEM *pxNext;
	struct xLIST_ITEM *pxPrevious;
};


typedef	struct xMiniLIST_ITEM MiniListItem_t;

typedef struct xLIST 
{
	UbaseType_t uxNumberOfItems;  	
	ListItem_t* pxIndex;		  
	MiniListItem_t xListEnd;	  	

}List_t;

void xListInitialiseItem(ListItem_t* const pxItem);

void xListInitialise(List_t* const pxList);

void xListInsertEnd(List_t* const pxList, ListItem_t*const pxNewListItem);

void xListInsert(List_t* const pxList, ListItem_t* const pxNewListItem);

void uxListRemove(ListItem_t* const pxItemToRemove);

​ C文件中具体涉及操作也不是很多，主要有初始化、插入和删除操作。其中不太好理解的为xListInsertEnd 和 xListInsert ，这里需要结合RTOS的设计思想（实时性），注释中做了说明。

#include 
#include "list.h"

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

void xListInitialise(List_t* const pxList)
{
	
	pxList->pxIndex = (ListItem_t* )pxList->xListEnd;
	
	pxList->uxNumberOfItems = 0;
	
	pxList->xListEnd.xItemValue = portMAX_DELAY;
	
	pxList->xListEnd.pxNext = (ListItem_t*)pxList->xListEnd;
	pxList->xListEnd.pxPrevious = (ListItem_t*)pxList->xListEnd;

}

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

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

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

	
	pxList->uxNumberOfItems++;
	
	pxNewListItem->pvContainer = pxList;

}

void xListInsert(List_t* const pxList, ListItem_t* const pxNewListItem)
{
	ListItem_t* pxIterator;
	const TickType_t xValueOfInsertion = pxNewListItem->xItemValue;

	if (xValueOfInsertion == portMAX_DELAY)
	{
		xValueOfInsertion = pxList->xListEnd.xItemValue;
	}
	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;
	 
	pxList->uxNumberOfItems++;
	pxNewListItem->pvContainer = (void*)pxList;

}

UbaseType_t int uxListRemove(ListItem_t* const pxItemToRemove)
{
	
	xLIST * const pxList = pxItemToRemove->pvContainer;

	
	pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;
	pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious; 

	
	if (pxList->pxIndex == pxItemToRemove)
	{
		pxList->pxIndex = pxItemToRemove->pxPrevious;
	}
	
	pxItemToRemove->pvContainer = NULL;
	
	
	pxList->uxNumberOfItems--;

	return pxList->uxNumberOfItems;
}

​

== pxItemToRemove)
{
pxList->pxIndex = pxItemToRemove->pxPrevious;
}

pxItemToRemove->pvContainer = NULL;

pxList->uxNumberOfItems--;

return pxList->uxNumberOfItems;

}

​